Versioned finite-state machines with Postgres (2019)

I definitely like materializing the transitions into a table instead of the switch statement

I always wondered about this, a while ago I saw a library similar to this that modeled FSMs in Postgres, and had a comment saying "todo: cycle detection". And made me wonder if it's even possible to do this.

Hmm… consider the following. Your FSM is acyclic iff you can assign each state an integer depth such that a state at depth d only ever transitions to states at depths strictly greater than d. So consider the following tables:

    CREATE TABLE states (
        state order_state PRIMARY KEY,
        depth int NOT NULL,
        UNIQUE(state, depth)
    );
    CREATE TABLE transitions (
        start_state order_state NOT NULL,
        event order_event NOT NULL,
        end_state order_state NOT NULL,
        start_depth int NOT NULL,
        end_depth int NOT NULL,
        CONSTRAINT transitions_start_depth_correct
            FOREIGN KEY(start_state, start_depth) REFERENCES states(state, depth)
            ON UPDATE CASCADE,
        CONSTRAINT transitions_end_depth_correct
            FOREIGN KEY(end_state, end_depth) REFERENCES states(state, depth)
            ON UPDATE CASCADE,
        CONSTRAINT transitions_depth_increases CHECK(end_depth > start_depth),
        PRIMARY KEY(start_state, event)
    );

Let's bang on it for a quick test. You can define a state machine; here's one that roughly matches the regex `^(AB|BA)$` (I know I'm being a bit sloppy):

    fsm=> CREATE DOMAIN order_state AS text;
    CREATE DOMAIN
    fsm=> CREATE DOMAIN order_event AS text;
    CREATE DOMAIN
    fsm=> -- "CREATE TABLE"s as above, then:
    fsm=> INSERT INTO states(state, depth) VALUES('start', 1), ('a', 2), ('b', 2), ('done', 3), ('error', 3);
    INSERT 0 5
    fsm=> INSERT INTO transitions(start_state, event, end_state, start_depth, end_depth) VALUES('start', 'A', 'a', 1, 2), ('start', 'B', 'b', 1, 2), ('a', 'B', 'done', 2, 3), ('b', 'A', 'done', 2, 3), ('a', 'A', 'error', 2, 3), ('b', 'B', 'error', 2, 3);
    INSERT 0 6

And, as you need to modify it, you can increase a node's depth to make room for intervening nodes:

    fsm=> UPDATE states SET depth = 4 WHERE state = 'error';
    UPDATE 1
    fsm=> TABLE transitions;
     start_state | event | end_state | start_depth | end_depth 
    -------------+-------+-----------+-------------+-----------
     start       | A     | a         |           1 |         2
     start       | B     | b         |           1 |         2
     a           | B     | done      |           2 |         3
     b           | A     | done      |           2 |         3
     a           | A     | error     |           2 |         4
     b           | B     | error     |           2 |         4
    (6 rows)

But you can't decrease a node's depth too far:

    fsm=> UPDATE states SET depth = 2 WHERE state = 'error';
    ERROR:  new row for relation "transitions" violates check constraint "transitions_depth_increases"
    DETAIL:  Failing row contains (a, A, error, 2, 2).
    CONTEXT:  SQL statement "UPDATE ONLY "public"."transitions" SET "end_state" = $1, "end_depth" = $2 WHERE $3::pg_catalog.text OPERATOR(pg_catalog.=) "end_state"::pg_catalog.text AND $4 OPERATOR(pg_catalog.=) "end_depth""

And you can't introduce transitions that don't increase depth:

    fsm=> INSERT INTO transitions(start_state, event, end_state, start_depth, end_depth) VALUES('done', 'AGAIN!', 'start', 3, 1);
    ERROR:  new row for relation "transitions" violates check constraint "transitions_depth_increases"
    DETAIL:  Failing row contains (done, AGAIN!, start, 3, 1).

Now, I don't know that I would immediately recommend this for high-throughput production use. You're storing "unnecessary" state not once but many times (each state's depth appears `1 + \deg(v)` times), plus additional indices and lookups. But I do think it meets the desired consistency goals!

They also derisk deploys of application code. If you deploy a bug that doesn't uphold your constraints, you get failures rather than corruption.

not sure what you are onto but SQL is just old and useless, glad i never had to learn it