\echo Use "CREATE EXTENSION pg_statecharts" to load this file. \quit
-- pg_statecharts 0.1.0
-- GENERATED FILE, DO NOT EDIT. Concatenated from the files in sql/parts.txt.

-- sql/schema.sql
-- ltree has to be in public, because the triggers that fire during pg_restore
-- write it as public.ltree. pg_restore runs with an empty search_path, so a
-- bare "ltree" cannot be resolved there and the restore of the fsm data fails;
-- an explicit schema is the only way out, and it has to be a literal one.
--
-- ltree is relocatable, and CREATE EXTENSION ... CASCADE propagates its own
-- SCHEMA option to the extensions it creates, so "create extension
-- pg_statecharts schema app cascade" puts ltree in app. Without this check
-- that succeeds -- a PL/pgSQL body is not resolved at creation time -- and
-- dies on the first insert into fsm.state instead.
do $ltree_check$
declare
  ltree_schema name;
begin
  if to_regtype('public.ltree') is null then
    select n.nspname into ltree_schema
    from pg_extension e
    join pg_namespace n on n.oid = e.extnamespace
    where e.extname = 'ltree';

    raise exception 'pg_statecharts requires the ltree extension in the public schema'
      using detail = case
              when ltree_schema is null then 'ltree is not installed'
              else format('ltree is installed in schema %I', ltree_schema)
            end,
            hint = 'install pg_statecharts without a SCHEMA option, or move ltree: '
                   'alter extension ltree set schema public;';
  end if;
end
$ltree_check$;

create schema fsm;

comment on schema fsm is 'Schema containing the statecharts implementation.';

-- sql/type/semver.sql
-- A pure SQL replacement for the `semver` PGXN extension.
--
-- The only reason `semver` was ever a dependency is that `fsm.statechart`
-- needs a version column that sorts correctly. `semver` is a C extension, so
-- depending on it means every user needs a compiler and the PostgreSQL server
-- headers just to install pg_statecharts.
--
-- An integer array gets that for free. Arrays compare element by element, so
-- `order by version desc` is correct with no helper function and no chance of
-- a caller getting it wrong: 1.10.0 outranks 1.9.0 because 10 > 9. The cost is
-- that the natural text form is '{1,10,0}' rather than '1.10.0'; use
-- fsm.semver_text() when a version is being shown to a person.
--
-- Everything lives in the fsm schema. That matters for more than tidiness:
-- the `semver` extension defines its own to_semver(text) in the schema it is
-- installed into, so an unqualified to_semver(text) here would collide with
-- it and make `create extension pg_statecharts` fail outright in any database
-- that happens to use `semver` for unrelated reasons. The only unqualified
-- object is the compatibility shim at the bottom of this file, and it is
-- skipped when the name is already taken.

-- The check is deliberately thorough. A CHECK that evaluates to NULL passes,
-- so `value[2] >= 0` alone would let array[1,null,3] through; and an array
-- with a lower bound other than 1 compares unequal to the same elements
-- starting at 1, which would let two rows that mean the same version both
-- into the unique index on (name, version).
--
-- The length test is cardinality(), not array_length(): for the empty array
-- '{}' array_ndims, array_lower and array_length are all NULL, so a check
-- built only from those is NULL for it and lets it through. cardinality('{}')
-- is 0, which makes that term FALSE and the whole conjunction with it.
create domain fsm.semver as integer[]
  check (array_ndims(value) = 1
         and array_lower(value, 1) = 1
         and cardinality(value) = 3
         and array_position(value, null) is null
         and value[1] >= 0
         and value[2] >= 0
         and value[3] >= 0);

comment on domain fsm.semver is $comment$
    A semantic version as a three element integer array: {major, minor, patch}.
    '1.10.0' is array[1, 10, 0].

    Stored as integers rather than text so that ordering is correct by default.
    Arrays compare element by element, so `order by version desc` ranks 1.10.0
    above 1.9.0 with no helper function involved.

    Build one with fsm.to_semver('1.10.0') and render one with
    fsm.semver_text(version). Casting to text gives the array form, '{1,10,0}'.

    Prerelease and build metadata suffixes (1.0.0-rc1, 1.0.0+build5) are not
    supported.
$comment$;

create or replace function fsm.to_semver(version text)
returns fsm.semver as
$$
  declare
    dot_count integer;
    padded text;
  begin
    if version is null then
      return null;
    end if;

    dot_count := length(version) - length(replace(version, '.', ''));

    if dot_count > 2 then
      raise exception 'invalid version %', quote_literal(version)
        using hint = 'expected at most three components, e.g. 1.2.3';
    end if;

    -- pads with '.0' if the provided value has fewer than two dots, so that
    -- both '1' and '1.2' are accepted and normalised to 1.0.0 and 1.2.0
    padded := version || repeat('.0', 2 - dot_count);

    if padded !~ '^\d+\.\d+\.\d+$' then
      raise exception 'invalid version %', quote_literal(version)
        using hint = 'expected digits separated by dots, e.g. 1.2.3';
    end if;

    return string_to_array(padded, '.')::integer[]::fsm.semver;
  end;
$$ language plpgsql immutable parallel safe;

comment on function fsm.to_semver(text) is $comment$
    Parses text into an fsm.semver, padding out omitted components so that '1'
    and '1.2' become 1.0.0 and 1.2.0.

    This is the canonical name. An unqualified to_semver(text) is also created
    when that name is free, for the benefit of statechart migrations generated
    against older versions of pg_statecharts.
$comment$;

create or replace function fsm.semver_text(version fsm.semver)
returns text as
$$
  select array_to_string(version, '.')
$$ language sql immutable strict parallel safe;

comment on function fsm.semver_text(fsm.semver) is $comment$
    Renders a version the way people write it: fsm.semver_text(array[1,10,0])
    is '1.10.0'. Casting to text instead gives the array form, '{1,10,0}'.
$comment$;

-- Compatibility shim.
--
-- Statechart migrations generated by pg_statecharts 0.0.0 call an unqualified
-- to_semver(...), which back then resolved to the `semver` extension's
-- function. Creating one here keeps those migrations deploying, reverting and
-- verifying unchanged.
--
-- It is conditional because that is exactly the name `semver` occupies. If
-- something else already provides to_semver(text) we leave it alone and carry
-- on: a database that uses `semver` for its own purposes can still install
-- pg_statecharts, it just does not get the shim. Note that in that case those
-- 0.0.0 migrations cannot work whatever we do here -- `semver`'s to_semver
-- returns its own type, which has no assignment cast to anything we could
-- store -- so they have to be regenerated. Migrations generated from 0.1.0
-- onwards call fsm.to_semver(...) and never needed the shim.
--
-- Objects created inside a DO block during CREATE EXTENSION are still
-- recorded as members of the extension, so this is dropped by DROP EXTENSION
-- like any other object here.
--
-- The skip is reported at WARNING rather than NOTICE deliberately: PostgreSQL
-- runs extension scripts with client_min_messages set to warning, so a NOTICE
-- here would never reach whoever ran CREATE EXTENSION.
do $shim$
  begin
    if exists (
      select 1
      from pg_proc p
      where p.proname = 'to_semver'
        and p.pronamespace = current_schema()::regnamespace
        and pg_get_function_identity_arguments(p.oid) = 'text'
    ) then
      raise warning 'to_semver(text) already exists in schema %, skipping the pg_statecharts compatibility shim', current_schema()
        using hint = 'use fsm.to_semver(text) instead; migrations generated by '
                     'pg_statecharts 0.0.0 will need regenerating';
      return;
    end if;

    create function to_semver(version text)
    returns fsm.semver as
    $body$
      select fsm.to_semver(version)
    $body$ language sql immutable parallel safe;

    comment on function to_semver(text) is $c$
    Deprecated alias for fsm.to_semver(text), kept so that statechart
    migrations generated by pg_statecharts 0.0.0 keep working. Not created if
    the name was already taken, so do not rely on it in new code.
    $c$;
  end;
$shim$;

-- sql/type/fsm_event_payload.sql
create type fsm_event_payload as
( shard_id bigint
, machine_id bigint
, event_name text
, data jsonb
, from_state text
, to_state text
, payload_type text
);

comment on type fsm_event_payload is
    'The argument passed to every on_entry and on_exit callback function.';

-- sql/type/fsm_callback_name.sql
create type fsm_callback_name as (
  schema_name name,
  function_name name
);

comment on type fsm_callback_name is
    'Type for on_entry and on_exit callbacks. Should contain both the schema and the function name to invoke';

-- sql/table/statechart.sql
create table fsm.statechart (
  id bigint not null generated by default as identity ( start with 1 cache 32767 ) primary key,
  created_at timestamptz not null default now(),
  name text not null,
  version fsm.semver not null,

  constraint name_must_be_within_bounds
    check (char_length(name) >= 1 and char_length(name) <= 200)
);

create unique index idx_unique_name_version on fsm.statechart(name, version);

comment on table fsm.statechart is 'All the different statecharts and their versions.';

-- sql/table/state.sql
create table fsm.state (
  statechart_id bigint not null,
  is_initial bool not null,
  is_final bool not null,
  id text not null,
  name text not null,
  parent_path ltree not null,
  node_path ltree not null,
  parent_id text,
  on_entry fsm_callback_name[] not null default array[]::fsm_callback_name[],
  on_exit fsm_callback_name[] not null default array[]::fsm_callback_name[],
  primary key (statechart_id, id),

  constraint id_must_be_within_bounds
    check (char_length(id) >= 1 and char_length(id) <= 50),

  constraint id_must_be_alphanumeric
    check (id ~ '^[a-zA-Z0-9_]+$'),

  constraint cannot_be_both_initial_and_final
    check (not (is_initial and is_final)),

  constraint fk_statechart
    foreign key(statechart_id)
    references fsm.statechart(id)
    on delete cascade,

  constraint fk_parent_state
    foreign key(statechart_id, parent_id)
    references fsm.state(statechart_id, id)
    on delete cascade
);

create index idx_parent on fsm.state(statechart_id, parent_id);
create index idx_parent_path on fsm.state using gist (parent_path) include (statechart_id);
create index idx_node_path on fsm.state using gist (node_path) include (statechart_id);

-- https://statecharts.dev/glossary/state.html
comment on table fsm.state is $comment$
    A state in a state machine describes a particular behaviour of the machine.
    When we say that a machine is “in” a state, it means that the machine behaves
    in the way that state describes.

    The behaviour of a state is defined as how the state reacts to events.
    Each state can specify a number of events that it “understands”, and specifies,
    for each event, any number of transitions that could be taken, if that event happens.
    A state also describes a set of actions to execute when the state is entered or
    exited, and in some implementations, activities that should be happening for the
    entire duration of time that the machine is in the state.

    When a state machine is executed, it enters the initial state, and adopts the
    behaviour associated with that state.  As the machine handles events, it
    transitions to other states, thus changing the behaviour of the machine over time.
$comment$;

-- https://statecharts.dev/glossary/initial-state.html
comment on column fsm.state.is_initial is $comment$
    The initial state in the state machine. There can only be one initial state
    in a state machine, but there can be many for parallel states.
    
    When a state machine starts, it starts by entering the machine’s initial state.
    Likewise, when a compound state is entered, its initial state is also entered.
    The initial state is not a separate state, but more like an indication of which
    state that the machine should start in by default.

    An initial state should be thought of as the default starting point of a compound state
    if a transition points directly to the compound state.
$comment$;

-- https://statecharts.dev/glossary/final-state.html
comment on column fsm.state.is_final is $comment$
    The final state in the state machine. There cannot be any transitions from
    the final state.

    A final state is a state in a compound state that designates that the compound
    state in question has completed, i.e. will not process any further events.
    Reaching a final state will generate an internal event, which in turn can allow
    other parts of the state machine to react to the fact that the compound state has
    “completed”.
$comment$;

comment on column fsm.state.parent_path is $comment$
    Parent path of the state. This is used to represent that a state is a
    child state, or part of a parallel state.

    This column is automatically set based on the "parent_id" column.
$comment$;

comment on column fsm.state.node_path is $comment$
    Path of the state that is represented from the root of the tree.

    This column is automatically set based on the "parent_id" column.
$comment$;

comment on column fsm.state.parent_id is $comment$
    Id of the parent state.
    NULL means that the state has no parent, i.e. it is not part of a composite
    nor parallel state.
$comment$;

comment on column fsm.state.on_entry is $comment$
    The functions to execute when this state is entered.
$comment$;

comment on column fsm.state.on_exit is $comment$
    The functions to execute when the state is exited.
$comment$;

-- sql/table/transition.sql
create table fsm.transition (
  statechart_id bigint not null,
  event text not null,
  source_state text not null,
  target_state text not null,
  primary key (statechart_id, event, source_state),

  constraint event_must_be_within_bounds
    check (char_length(event) >= 1 and char_length(event) <= 100),

  constraint fk_source_state
    foreign key(statechart_id, source_state)
    references fsm.state(statechart_id, id)
    on delete cascade,

  constraint fk_target_state
    foreign key(statechart_id, target_state)
    references fsm.state(statechart_id, id)
    on delete cascade
);

-- https://statecharts.dev/glossary/transition.html
comment on table fsm.transition is $comment$
    In an executing state machine, a transition is the instantaneous transfer
    from one state to another.  In a state machine, a transition tells us
    what happens when an event occurs.
    
    When an event happens, the currently active state(s) are inspected,
    looking for an outbound transition that could be triggered by the event.
$comment$;

comment on column fsm.transition.event is 'Name of the transition event.';

comment on column fsm.transition.source_state is 'The from state of the transition.';

comment on column fsm.transition.target_state is 'The to state of the transition.';

-- sql/table/state_machine.sql
create table fsm.state_machine (
  shard_id bigint not null,
  id bigint not null generated by default as identity ( start with 1 cache 32767 ),
  statechart_id bigint not null,
  created_at timestamptz not null default now(),

  primary key (shard_id, id),

  constraint fk_statechart
    foreign key(statechart_id)
    references fsm.statechart(id)
    on delete cascade
);

create index idx_statechart on fsm.state_machine(statechart_id);

comment on table fsm.state_machine is
    'Runtime information of a statechart. Contains state machine instances that have started.';

-- sql/table/state_machine_state.sql
create table fsm.state_machine_state (
  shard_id bigint not null,
  state_machine_id bigint not null,
  statechart_id bigint not null,
  entered_at timestamptz not null default now(),
  exited_at timestamptz,
  state_id text not null,

  constraint entered_should_be_before_exited
    check (entered_at <= exited_at),

  constraint fk_state_machine
    foreign key(shard_id, state_machine_id)
    references fsm.state_machine(shard_id, id)
    on delete cascade,

  constraint fk_state
    foreign key(statechart_id, state_id)
    references fsm.state(statechart_id, id)
    on delete cascade
);

create unique index idx_state on fsm.state_machine_state(shard_id, state_machine_id, state_id)
  where exited_at is null;

comment on table fsm.state_machine_state is $comment$
  Contains a log of the states that have been activated by a given state machine and
  is used to determine which states are currently active.
$comment$;

comment on column fsm.state_machine_state.entered_at is $comment$
    The timestamp when the state machine has transitioned to this state.
    This is the column that indicates that a state is currently active
    for a state machine.
    Should be before exited_at.
$comment$;

comment on column fsm.state_machine_state.exited_at is $comment$
    The timestamp when the state machine has transitioned away from this state.
    Should be after entered_at.
$comment$;

-- sql/table/state_machine_event.sql
create table fsm.state_machine_event (
  shard_id bigint not null,
  id bigint not null generated by default as identity ( start with 1 cache 32767 ),
  state_machine_id bigint not null,
  created_at timestamptz not null default now(),
  handled_at timestamptz,
  name text not null,
  data jsonb not null,

  primary key (shard_id, id),

  constraint created_should_be_before_handled
    check (created_at <= handled_at),

  constraint fk_state_machine
    foreign key(shard_id, state_machine_id)
    references fsm.state_machine(shard_id, id)
    on delete cascade
);

create index idx_state_machine on fsm.state_machine_event(shard_id, state_machine_id)
  where handled_at is null;

comment on table fsm.state_machine_event is
    'Queue of events that need to be processed for the state machine.';

comment on column fsm.state_machine_event.created_at is $comment$
    The timestamp when this event was created. The timestamp should be
    before "handled_at".
$comment$;

comment on column fsm.state_machine_event.handled_at is $comment$
    The timestamp when this event was handled. The timestamp should be
    after "created_at".
$comment$;

comment on column fsm.state_machine_event.data is $comment$
    The data to be sent to the callback handlers in on_entry, on_exit.
$comment$;

-- sql/function/get_latest_statechart.sql
create or replace function fsm.get_latest_statechart(named text)
returns setof fsm.statechart as
$$
    select *
    from fsm.statechart
    where name = named
    -- fsm.semver is an integer array, so this is already a numeric comparison
    -- component by component: 1.10.0 outranks 1.9.0 because 10 > 9.
    order by version desc
    limit 1
$$ language sql
    strict
    stable
    parallel safe
    rows 1;

comment on function fsm.get_latest_statechart(text) is $comment$
    Get the latest statechart of given name.
$comment$;

-- sql/function/create_machine.sql
create or replace function fsm.create_machine(shard bigint, statechart bigint)
  returns fsm.state_machine as
  $$
      insert into fsm.state_machine (shard_id, statechart_id) values
        (shard, statechart)
      returning *;
  $$ language sql volatile strict;

comment on function fsm.create_machine(bigint, bigint) is $comment$
    creates a state machine without starting it
$comment$;

-- sql/function/create_state_machine_with_latest_statechart.sql
create or replace function fsm.create_state_machine_with_latest_statechart(shard_id_ bigint, named text)
returns fsm.state_machine as
$$
    with desired_chart as (
        select id from fsm.get_latest_statechart(named)
    )
    insert into fsm.state_machine (shard_id, statechart_id)
    select
        shard_id_ as shard_id,
        desired_chart.id as statechart_id
    from desired_chart
    returning *

$$ language sql volatile strict;

comment on function fsm.create_state_machine_with_latest_statechart(bigint, text) is $comment$
    Creates a new state machine but does not start it.
    You need to call fsm.start_machine after this
$comment$;

-- sql/function/get_finalized_parents.sql
create or replace function fsm.get_finalized_parents(shard bigint, machine_id bigint, active_state_parent_path ltree)
  returns setof fsm.state as
$$
  with all_parents as (
   select a_parent.*
   from fsm.state a_parent
   -- check that active_state_path is a child of a_parent
   where a_parent.node_path @> active_state_parent_path
     and exists (
        select 1
        from fsm.state_machine_state current_state
        where current_state.shard_id = shard
          and current_state.state_machine_id = machine_id
          and current_state.exited_at is null -- the state is currently active
          and current_state.statechart_id = a_parent.statechart_id
     )
  )
  select *
  from all_parents parent
  where
  -- A state can only be finalizable if it has no outgoing transitions. Here, we look
  -- at all the active children for the parent we are inspecting and make sure that
  -- all of them are at a point where the machine cannot move further inside that parent.
  not exists (
    select 1
    from fsm.state s
    join fsm.state_machine_state current_state
      on  current_state.shard_id = shard
      and current_state.state_machine_id = machine_id
      and current_state.state_id = s.id
      and current_state.exited_at is null -- the state is currently active
    where parent.id = s.parent_id
      and s.statechart_id = parent.statechart_id
      and exists (
        select 1 -- check that there is at least one outgoing transition for this state
        from fsm.transition t
        where t.statechart_id = s.statechart_id
          and t.source_state = s.id
      )
  )

  -- Parallel states are a special case. A parallel node is finalized when all its internal states
  -- have finilized already. Without this filter, we would end up considering parents with pending
  -- internal transitions.
  -- The key is to "dive-in" into the children of the parent we are inspecting and verify
  -- that only active states are marked as "is_final".
  -- The filter below is expressed in the negative: active non-final states should not exist.
  and not exists (
    select 1
    from fsm.state s -- the possible non-final, active state
    join fsm.state_machine_state current_state -- active parent state
      on  current_state.shard_id = shard
      and current_state.state_machine_id = machine_id
      and current_state.state_id = s.id
      and current_state.exited_at is null
    -- Dive into the children of the parent we are inspecting
    where parent.node_path @> s.parent_path -- check that the active parent state is actually a parent
      and parent.statechart_id = s.statechart_id
      -- get only the non "is_final" active states, since they determine wether or not there is
      -- more work to do for this sub-machine
      and not s.is_final -- check that the state under inspection is non-final
      -- Only non-final states can have children. Having an active parent state is fine, so
      -- we only need to make sure that this non-final state is a leaf in the tree. That is,
      -- it should not have any children.
      and not exists (
        select 1
        from fsm.state child
        where s.node_path @> child.parent_path
      )
  )
$$ language sql strict stable parallel safe;

comment on function fsm.get_finalized_parents (bigint, bigint, ltree) is
$comment$
A finalized parent can be defined as a compound state where all its children have reached
a state where no other transitions are possible.

We can determine this property by analyzing the possible transitions for internal active states
and whether or not these active states are final.

This function is used to generate "done.state.*" events for a state machine for all the parents
in an inheritance chain.
$comment$;

-- sql/function/get_initial_state.sql
-- Returns all the chains of nodes that are marked as initial. The chain
-- is interrupted whenever there is a child marked a non-initial
create or replace function fsm.get_initial_state(statechart bigint)
returns setof fsm.state as
$$
    with root as (
      select s.*
      from fsm.state s
      where s.statechart_id = statechart
        and s.is_initial
        and parent_id is null
    )
    select * from root

    union

    select child_s.*
    from fsm.state child_s
    where child_s.statechart_id = statechart
      and child_s.is_initial
      and child_s.parent_path <@ (select node_path from root)
      -- we make sure that the chaing of parents only contain initial nodes
      and not exists (
        select *
        from fsm.state parent
        -- <@ = left is descendant or equals to right
        where child_s.node_path <@ parent.node_path
          and not parent.is_initial
      )

$$ language sql stable strict parallel safe;

comment on function fsm.get_initial_state(bigint) is $comment$
    Get all initial states, when an initial state has children all of its
    initial states are also returned.
$comment$;

-- sql/function/handle_machine_events.sql
create or replace function fsm.handle_machine_events(shard bigint, machine_id bigint)
  returns void as
$$
  declare
    handled fsm.state_machine_event%rowtype;
    state_transition record;
    on_exit_function_call record;
    on_entry_function_call record;
  begin

    -- First mark all pending events as handled and then select the set of source
    -- active states and future target states based on the event transition. This
    -- selection will be used to perform the transition effects and record the new
    -- machine current states.

    -- regardless of whether or not there exists a valid transition for the
    -- unhandled events, we need to mark them as handled. This is why we start
    -- the process with the update.

    -- The reason for using a select and then an update, instead of just issuing a plain
    -- update with conditions is that we want access to the list of events in creation order
    -- rather than the order that postgres found most convenient.
    for handled in
        with unhandled as (
          select *
          from fsm.state_machine_event
          where shard_id = shard
            and state_machine_id = machine_id
            and handled_at is null
          order by created_at, id asc
        )
        , handling as (
          update fsm.state_machine_event set handled_at = now()
          where (shard_id, id) in (select shard_id, id from unhandled)
        )
        select * from unhandled
    loop
      for state_transition in

        -- {{{transition-query
        select
            source as source_state
          , target as target_state
          , coalesce(source_tree.states, array[]::fsm.state[]) as children_source_states
          , coalesce(target_tree.states, array[]::fsm.state[]) as children_target_states
          , target.is_final as target_is_final

        -- we need to lookup the states the machine is at. Since this will
        -- yield multiple states, we will need to filter the relevant ones
        from fsm.state_machine_state as current_state

        -- this filters the currently active states down to the list of states
        -- that accept the named transition. The effect of this join should be
        -- that only one source state is matched per named event
        join fsm.transition transition
          on  transition.statechart_id = current_state.statechart_id
          and handled.name = transition.event
          and transition.source_state = current_state.state_id

        -- we need to remember certain details of the source state we are exiting,
        -- for example, if it is final we need to generate a "done" event for it.
        join fsm.state source
          on  source.statechart_id = transition.statechart_id
          and source.id = current_state.state_id

        -- likewise, we remeber the details for the target state we need to activate.
        -- so that we can execute the `on_entry` callback.
        join fsm.state target
          on  target.statechart_id = transition.statechart_id
          and target.id = transition.target_state

        -- we need to get the entire sub-tree for the source state we are transitioning
        -- from, so that we can call all of the on_exit callbacks.
        join lateral (
          select array_agg(st::fsm.state)::fsm.state[] as states from
          ( select state_child.*
            from fsm.state state_child
            -- we only want child states that are currently activated in the state machine
            -- so, we filter by `exited_at is null` and correlate to the current
            -- state_child we are inspecting
            join fsm.state_machine_state as current_children_state
              on current_children_state.shard_id = shard
              and current_children_state.state_machine_id = machine_id
              and current_children_state.state_id = state_child.id
              and current_children_state.exited_at is null
            where state_child.statechart_id = current_state.statechart_id
              and state_child.parent_path <@ source.node_path
          ) st
        ) source_tree on true

        -- Similarly, we also need the tree for the target state, as we need to
        -- activate all the `is_initial` states and execute their `on_entry` callbacks
        join lateral (
          select array_agg(tt::fsm.state)::fsm.state[] as states from
           ( select state_child.*
             from fsm.state state_child
             where state_child.statechart_id = current_state.statechart_id
               and state_child.parent_path <@ target.node_path
               and state_child.is_initial
               -- We have selected so far all initial children recursively, but we have
               -- now to filter out those who have parents that are not initial as well
               -- Any node in the chain that is not active should break the chain of nodes
               -- that we are activating recursively.
               and not exists (
                   select *
                   from fsm.state bad_parent
                   where bad_parent.statechart_id = current_state.statechart_id
                      and target.node_path @> bad_parent.node_path
                      and bad_parent.node_path @> state_child.parent_path
                      and bad_parent.id <> target.id
                      and not bad_parent.is_initial
               )
          ) tt
        ) target_tree on true

        where current_state.shard_id = shard
          and current_state.state_machine_id = machine_id
          and current_state.exited_at is null
      -- transition-query}}}

      loop

        -- For all the active source states, we mark them as exited and execute their respective
        -- on_exit callback if any
        -- {{{source-exiting
        for on_exit_function_call in
          with

            target_states as (
              select *
              from
                unnest(state_transition.target_state || state_transition.children_target_states)
            )

          , source_states as (
              select *
              from
                unnest(state_transition.children_source_states || state_transition.source_state)
            )

          , updated_states as (
              update fsm.state_machine_state
              /* using clock_timestamp() instead of now(). now() uses
               * transaction time which can cause problem when another process
               * adds fsm.state_machine_state rows during the transaction. This
               * can cause the exited_at time to be earlier than the entered
               * time causing a constraint errors
               */
              set exited_at = clock_timestamp()
              where shard_id = shard
                and state_machine_id = machine_id
                and state_id in (select a.id from source_states a)
                -- if we are looping into the same state, we don't want to mark the current state as exited
                and state_id not in (select a.id from target_states a)
                and exited_at is null
            )

          select shard, machine_id, machine_id, id, unnest(on_exit) as on_exit from source_states
        loop
          execute format('select %I.%I(%L::fsm_event_payload)',
              coalesce((on_exit_function_call.on_exit).schema_name, 'public')
            , (on_exit_function_call.on_exit).function_name
            , ( shard
              , machine_id
              , handled.name
              , handled.data
              , on_exit_function_call.id
              , (state_transition.target_state).id
              , 'on_exit'
              )::fsm_event_payload
            );
         end loop;
        -- source-exiting}}}

        -- now we do the same for the target states, but in reverse order. We enter states from the
        -- outermost to the innermost and execute their on_exit callback if any.
        -- {{{target-entering
        for on_entry_function_call in
          with

            target_states as (
              select *
              from
                unnest(state_transition.target_state || state_transition.children_target_states)
            )

          , source_states as (
              select *
              from
                unnest(state_transition.children_source_states || state_transition.source_state)
            )

          , new_states as (
              insert into fsm.state_machine_state (shard_id, state_machine_id, statechart_id, state_id)
              select
                  shard as shard_id
                , machine_id as state_machine_id
                , a.statechart_id
                , a.id as state_id
              from target_states a
              -- We allow transitioning back to the same state (a loop)
              -- but for storage reasons, we prefer not to insert those rows again
              -- here, we exclude target states that are identical to the source state
              where a.id not in (
                select x.id from source_states x
              )
            )

          select shard, machine_id, machine_id, id, unnest(on_entry) as on_entry from target_states
        loop
          execute format('select %I.%I(%L::fsm_event_payload)',
              coalesce((on_entry_function_call.on_entry).schema_name, 'public')
            , (on_entry_function_call.on_entry).function_name
            , ( shard
              , machine_id
              , handled.name
              , handled.data
              , (state_transition.source_state).id
              , on_entry_function_call.id
              , 'on_entry'
              )::fsm_event_payload);
        end loop;
        -- target-entering}}}

        -- generate the "done" event for the target state if it is_final,
        -- including the parents, if needed
        -- {{{event-generation
        if state_transition.target_is_final
        then
          insert into fsm.state_machine_event (shard_id, state_machine_id, name, data) values
            ( shard
            , machine_id
            , format('done.state.%s', (state_transition.target_state).id)
            , handled.data
            );

          insert into fsm.state_machine_event (shard_id, state_machine_id, name, data)
            select shard as shard_id, machine_id as state_machine_id
                 , format('done.state.%s', f.id)
                 , handled.data as data
            from fsm.get_finalized_parents(
                shard
              , machine_id
              , (state_transition.target_state).parent_path
            ) f;
        end if;
        -- event-generation}}}

      end loop;

    end loop;

    return;
  end;
$$ language plpgsql volatile strict;

-- sql/function/is_state_active.sql
create or replace function fsm.is_state_active(shid bigint, smid bigint, state text)
  returns bool as
$$
  begin

    perform true
    from fsm.state_machine_state 
    where state_machine_id = smid 
      and shard_id = shid
      and state_id = state;

    if not found then
      return false;
    else
      return true;
    end if;
  end;
$$ language plpgsql stable strict;

-- sql/function/is_valid_transition.sql
create or replace function fsm.is_valid_transition(shard bigint, machine_id bigint, event_ text)
  returns bool as
$$
  begin
      perform true
      from fsm.state_machine_state current_state

      join fsm.state child_state
          on  child_state.statechart_id = current_state.statechart_id
          and child_state.id = current_state.state_id

      join fsm.state state
          on  state.statechart_id = current_state.statechart_id
          -- is state.node_path an ancestor of current_state.node_path (or equal)?
          -- this is used to get all of the current_state parents, including the current_state
          and state.node_path @> child_state.node_path

      -- check if the transition named "event_" is a valid one for
      -- the current_state. That is, we need to see if "current_state"
      -- appears as a "source_state" in the transition table and has
      -- an associated "event" name equals to event_
      join fsm.transition transition
          on transition.statechart_id = state.statechart_id
          and transition.source_state = state.id
          and transition.event = event_

      where   current_state.shard_id = shard
          and current_state.state_machine_id = machine_id
          and current_state.exited_at is null;

      if not found then
          return false;
      end if;

    return true;
  end;
$$ language plpgsql stable strict;

-- sql/function/notify_state_machine.sql
create or replace function fsm.notify_state_machine(shard bigint, machine bigint, event text, data jsonb default '{}')
    returns void as
$$
    insert into fsm.state_machine_event
        (shard_id, state_machine_id, name, data) values
        (shard, machine, event, data)
$$ language sql volatile security definer;

comment on function fsm.notify_state_machine is 'send an event to a specific state machine';

-- sql/function/start_machine.sql
create or replace function fsm.start_machine(shard bigint, machine_id bigint, initial_data jsonb default '{}')
  returns fsm.state_machine as
  $$
    declare
      initial fsm.state%rowtype;
      machine fsm.state_machine%rowtype;
      error_message text;
      error_state text;
      error_context text;
      error_detail text;
      on_entry_ fsm_callback_name;
    begin

      select * into machine from fsm.state_machine where shard_id = shard and id = machine_id;

      for initial in select * from fsm.get_initial_state(machine.statechart_id)
      loop

        insert into fsm.state_machine_state
          (shard_id, state_machine_id, statechart_id, state_id) values
          (shard, machine.id, machine.statechart_id, initial.id);

        foreach on_entry_ in array initial.on_entry
        loop
            -- This call will look like something like this
            -- select my_schema.my_function(
            --  (1, 199, '__initial__', '{...}', null, 233, 'on_entry')::fsm.event_payload
            -- )
            execute format('select %I.%I(%L::fsm_event_payload)',
                coalesce((on_entry_).schema_name::text, 'public')
              , (on_entry_).function_name
              , ( shard
                , machine.id
                , '__initial__'
                , initial_data
                , null
                , initial.id
                , 'on_entry'
                )::fsm_event_payload
            );
        end loop;

      end loop;

      return machine;

    exception when others then
      get stacked diagnostics
        error_message = message_text,
        error_context = pg_exception_context,
        error_detail = pg_exception_detail,
        error_state = returned_sqlstate;
      raise exception
        using errcode=error_state,
          message=error_message,
          detail = error_detail,
          hint=format('Error while handling state machine event: %s', error_context);
    end
  $$ language plpgsql volatile;

comment on function fsm.start_machine(bigint, bigint, jsonb) is $comment$
    Starts a given state machine by activating all of its initial states and
    executing the corresponding on_entry callbacks.
$comment$;

-- sql/function/start_machine_with_latest_statechart.sql
create or replace function fsm.start_machine_with_latest_statechart(shard_id bigint, named text, initial_data jsonb default '{}')
returns setof fsm.state_machine as
$$
    select m.*
    from fsm.create_state_machine_with_latest_statechart(shard_id, named) m
    join fsm.start_machine(shard_id, m.id, initial_data) on true

    limit 1
$$ language sql volatile strict
    rows 1;

comment on function fsm.start_machine_with_latest_statechart(bigint, text, jsonb) is $comment$
    Creates and starts a state machine with the latest statechart with the name passed.
$comment$;

-- sql/trigger/check_no_cross_boundary_transitions.sql
create or replace function fsm.trig_check_no_cross_boundary_transition() returns trigger as
$$
  declare
      bad_transitions jsonb;
  begin
    select jsonb_agg(c.*) into bad_transitions
    -- changed is the table of changes that where just modified
    from changed c
    join fsm.state source
      on  source.statechart_id = c.statechart_id
      and source.id = c.source_state
    join fsm.state target
      on  target.statechart_id = c.statechart_id
      and target.id = c.target_state
    where source.parent_id <> target.parent_id;

    if jsonb_array_length(bad_transitions) > 0
    then
      raise exception 'cannot add transitions between states with different parents: %', jsonb_pretty(bad_transitions);
    end if;

    return null;
  end;
$$ language plpgsql;

comment on function fsm.trig_check_no_cross_boundary_transition is $comment$
    This function checks that there are no transitions between states with
    different parents in the "fsm.transition" table.
$comment$;

set client_min_messages TO warning;
drop trigger if exists check_no_cross_boundary_transitions_insert on fsm.transition;
drop trigger if exists check_no_cross_boundary_transitions_update on fsm.transition;
reset client_min_messages;

create trigger check_no_cross_boundary_transitions_insert
after insert
on fsm.transition
referencing new table as changed
for each statement
execute function fsm.trig_check_no_cross_boundary_transition();

comment on trigger check_no_cross_boundary_transitions_insert on fsm.transition is $comment$
    Checks that no transitions in between states with different parents are
    inserted in the "fsm.transition" table.
$comment$;

create trigger check_no_cross_boundary_transitions_update
after update
on fsm.transition
referencing new table as changed
for each statement
execute function fsm.trig_check_no_cross_boundary_transition();

comment on trigger check_no_cross_boundary_transitions_update on fsm.transition is $comment$
    Checks that no transitions in between states with different parents are
    inserted in the "fsm.transition" table.
$comment$;

-- sql/trigger/check_no_duplicate_event_handler.sql
create or replace function fsm.trig_check_no_duplicate_event_handler() returns trigger as
$$
  declare
      duplicate_transitions jsonb;
  begin
    with changed_event as (
      select distinct statechart_id, event
      from changed
    )
    -- look at the entire tree to see if the same event name is used
    -- for a transition
    select jsonb_agg(t.*) into duplicate_transitions
    from fsm.transition t
    -- need to get the source state info for the transition
    -- specifically, we need to get its node_path
    join fsm.state s
      on  s.statechart_id = t.statechart_id
      and s.id = t.source_state
    -- get all children and parents on the source_state by using the node_path
    -- it is the count of this children nodes that will determine
    -- if the same event is used in another transition
    --
    -- The ltree operators carry an explicit schema. This trigger fires while
    -- pg_restore loads fsm.transition, and pg_restore runs with an empty
    -- search_path, where a bare <@ or @> cannot be resolved and the restore
    -- fails. ltree is installed into public; see set_state_parent_path.sql.
    join fsm.state relative
      on  relative.statechart_id = t.statechart_id
      and (relative.node_path operator(public.<@) s.node_path or relative.node_path operator(public.@>) s.node_path)
      and relative.id <> s.id
    join fsm.transition ct
      on  ct.statechart_id = relative.statechart_id
      and ct.source_state = relative.id
    join changed_event ce
      on  ce.statechart_id = ct.statechart_id
      and ce.event = ct.event
      and ce.statechart_id = t.statechart_id
      and ce.event = t.event;

    if jsonb_array_length(duplicate_transitions) > 0
    then
      raise exception $m$
      Cannot use the same event name for multiple transations in the same tree: %
      $m$, jsonb_pretty(duplicate_transitions);
    end if;

    return null;
  end;
$$ language plpgsql;

set client_min_messages TO warning;
drop trigger if exists check_no_duplicate_event_handler_insert on fsm.transition;
drop trigger if exists check_no_duplicate_event_handler_update on fsm.transition;
reset client_min_messages;

create trigger check_no_duplicate_event_handler_insert
after insert
on fsm.transition
referencing new table as changed
for each statement
execute function fsm.trig_check_no_duplicate_event_handler();

create trigger check_no_duplicate_event_handler_update
after update
on fsm.transition
referencing new table as changed
for each statement
execute function fsm.trig_check_no_duplicate_event_handler();

-- sql/trigger/check_no_state_loops.sql
create or replace function fsm.trig_check_no_state_loops()
returns trigger as
$$
declare the_cycle text[];
begin

  with recursive chart as (
    select distinct statechart_id
    from changed
  )
  , prev as (
    select cs.statechart_id, cs.id, array[id] as seen, false as cycle
    from fsm.state cs
    join chart
      on  chart.statechart_id = cs.statechart_id
    where parent_id is null

    union all

    select cs.statechart_id, cs.id, seen || cs.id as seen,
        cs.id = any(seen) as cycle
    from prev
    join fsm.state cs
      on  cs.statechart_id = prev.statechart_id
      and cs.parent_id = prev.id
      and prev.cycle = false
    join chart
      on  chart.statechart_id = cs.statechart_id
  )
  select seen into the_cycle
  from prev
  where prev.cycle
  limit 1;

  if the_cycle is not null
  then
    raise exception 'compound states should form a directed graph. Cycle detected: %', the_cycle;
  end if;

  return null;
end;
$$ language plpgsql;

comment on function fsm.trig_check_no_state_loops is $comment$
    Checks that the compound states do not form a cycle. Compound states
    should form a directed graph.
$comment$;

set client_min_messages TO warning;
drop trigger if exists check_no_state_loops_insert on fsm.state;
drop trigger if exists check_no_state_loops_update on fsm.state;
reset client_min_messages;

create trigger check_no_state_loops_insert
after insert
on fsm.state
referencing new table as changed
for each statement
execute function fsm.trig_check_no_state_loops();

comment on trigger check_no_state_loops_insert on fsm.state is $comment$
    Checks that the compound states do not form a cycle. Compound states
    should form a directed graph.
$comment$;

create trigger check_no_state_loops_update
after update
on fsm.state
referencing new table as changed
for each statement
execute function fsm.trig_check_no_state_loops();

comment on trigger check_no_state_loops_update on fsm.state is $comment$
    Checks that the compound states do not form a cycle. Compound states
    should form a directed graph.
$comment$;

-- sql/trigger/check_no_transition_for_final.sql
create or replace function fsm.trig_check_no_transition_for_final() returns trigger as
$$
  declare
      bad_transitions jsonb;
  begin
    select jsonb_agg(c.*) into bad_transitions
    from changed c
    join fsm.state s
      on  s.statechart_id = c.statechart_id
      and s.id = c.source_state
      and s.is_final;

    if jsonb_array_length(bad_transitions)
    then
      raise exception 'cannot add transitions from final states: %', jsonb_pretty(bad_transitions);
    end if;

    return null;
  end;
$$ language plpgsql;

comment on function fsm.trig_check_no_transition_for_final is $comment$
    Checks that there are no transitions added from final states.
$comment$;

-- create a similar function for states
create or replace function fsm.trig_check_no_final_state_with_transition() returns trigger as
$$
  declare
      bad_states jsonb;
  begin
    select jsonb_agg(c.*) into bad_states
    from changed c
    join fsm.transition t
      on  t.statechart_id = c.statechart_id
      and t.source_state = c.id
    where c.is_final;

    if jsonb_array_length(bad_states)
    then
      raise exception 'cannot add states with transitions from final states: %', jsonb_pretty(bad_states);
    end if;

    return null;
  end;
$$ language plpgsql;

comment on function fsm.trig_check_no_final_state_with_transition is $comment$
    Checks that there are no states added which have transitions from final states.
$comment$;

set client_min_messages TO warning;
drop trigger if exists check_no_transition_for_final_insert on fsm.transition;
drop trigger if exists check_no_transition_for_final_update on fsm.transition;
drop trigger if exists check_no_transition_for_final_update on fsm.state;
reset client_min_messages;

create trigger check_no_transition_for_final_insert
after insert
on fsm.transition
referencing new table as changed
for each statement
execute function fsm.trig_check_no_transition_for_final();

comment on trigger check_no_transition_for_final_insert on fsm.transition is $comment$
    Checks that there are no transitions inserted from final states.
$comment$;

create trigger check_no_transition_for_final_update
after update
on fsm.transition
referencing new table as changed
for each statement
execute function fsm.trig_check_no_transition_for_final();

comment on trigger check_no_transition_for_final_update on fsm.transition is $comment$
    Checks that there are no transitions added from final states.
$comment$;

create trigger check_no_transition_for_final_update
after update
on fsm.state
referencing new table as changed
for each statement
execute function fsm.trig_check_no_final_state_with_transition();

comment on trigger check_no_transition_for_final_update on fsm.transition is $comment$
    Checks that there are no states inserted with transitions from final states.
$comment$;

-- sql/trigger/check_valid_initial_state.sql
create or replace function fsm.trig_check_valid_initial_state() returns trigger as
$$
  declare
      chart bigint;
      total_initial bigint;
  begin
    for chart in
      select distinct statechart_id
      from changed
      where exists (select 1 from fsm.statechart where id = changed.statechart_id)
    loop
        select count(*) into total_initial
        from fsm.state
        where statechart_id = chart
          and is_initial
          and parent_id is null;

        if total_initial is distinct from 1
        then
          raise exception 'exactly one initial state is required per statechart';
        end if;

    end loop;

    return null;
  end;
$$ language plpgsql;

comment on function fsm.trig_check_valid_initial_state is $comment$
    Checks that there is only initial state per statechart. Only considers
    initial states whose parent_id is null.
$comment$;

set client_min_messages TO warning;
drop trigger if exists check_valid_initial_state_insert on fsm.state;
drop trigger if exists check_valid_initial_state_update on fsm.state;
drop trigger if exists check_valid_initial_state_delete on fsm.state;
reset client_min_messages;

create trigger check_valid_initial_state_insert
after insert
on fsm.state
referencing new table as changed
for each statement
execute function fsm.trig_check_valid_initial_state();

comment on trigger check_valid_initial_state_insert on fsm.state is $comment$
    Checks that there is only initial state per statechart. Only considers
    initial states whose parent_id is null.
$comment$;

create trigger check_valid_initial_state_update
after update
on fsm.state
referencing new table as changed
for each statement
execute function fsm.trig_check_valid_initial_state();

comment on trigger check_valid_initial_state_update on fsm.state is $comment$
    Checks that there is only initial state per statechart. Only considers
    initial states whose parent_id is null.
$comment$;

create trigger check_valid_initial_state_delete
after delete
on fsm.state
referencing old table as changed
for each statement
execute function fsm.trig_check_valid_initial_state();

comment on trigger check_valid_initial_state_delete on fsm.state is $comment$
    Checks that there is only initial state per statechart. Only considers
    initial states whose parent_id is null.
$comment$;

-- sql/trigger/notify_machine_event.sql
create or replace function fsm.trig_notify_machine_event() returns trigger as
$$
  declare
    event record;
  begin

    for event in select distinct shard_id, state_machine_id from new
    loop
      perform fsm.handle_machine_events(event.shard_id, event.state_machine_id);
    end loop;

    return null;
  end;
$$ language plpgsql;

comment on function fsm.trig_notify_machine_event is $comment$
  Handles all of the newly inserted events for all affected state machines.
$comment$;

set client_min_messages TO warning;
drop trigger if exists notify_machine_event on fsm.state_machine_event;
reset client_min_messages;

create trigger notify_machine_event
after insert
on fsm.state_machine_event
referencing new table as new
for each statement
execute function fsm.trig_notify_machine_event();

comment on trigger notify_machine_event on fsm.state_machine_event is $comment$
  Handles all of the newly inserted events for all affected state machines.
$comment$;

-- sql/trigger/set_state_parent_path.sql
-- The ltree type and its || operator are written with an explicit schema. This
-- trigger fires while pg_restore loads fsm.state, and pg_restore runs with an
-- empty search_path, where a bare "ltree" or "||" cannot be resolved and the
-- restore of the fsm data fails. Everything pg_statecharts owns lives in fsm
-- and is already qualified; ltree is installed into public. (ltree is
-- relocatable, so a database that keeps it in another schema has to change
-- these references, but the rest of the extension assumes it is on the
-- search_path anyway, which in practice means public.)
create or replace function fsm.trig_set_state_parent_path() returns trigger as
$$
    declare
        path public.ltree;
    begin

        if NEW.parent_id is null then
            NEW.parent_path = coalesce(NEW.statechart_id, OLD.statechart_id)::text::public.ltree;

        elseif TG_OP = 'INSERT' or OLD.parent_id is null or OLD.parent_id != NEW.parent_id then
            select parent_path operator(public.||) id
            from fsm.state
            where id = NEW.parent_id and statechart_id = NEW.statechart_id and not is_final
            into path;

            if path is null then
                raise exception 'Invalid parent_id. It should exist and not be final: %', NEW.parent_id;
            end if;

            new.parent_path = path;
        end if;

        new.node_path = new.parent_path operator(public.||) new.id;

        return new;
    end;
$$ language plpgsql;

create trigger set_state_parent_path
    before insert or update on fsm.state
    for each row execute procedure fsm.trig_set_state_parent_path();

-- sql/dump.sql
-- pg_dump leaves out the tables of an extension unless the extension registers
-- them as configuration tables. Without this, a backup of a database that uses
-- pg_statecharts holds every application row with its state_machine_id and
-- none of the machines those ids point at: after a restore the fsm tables are
-- empty, the identity sequences start over from 1, and the first new machines
-- collide with the ids the application tables still carry. 0.0.0 never
-- registered its tables, so backups taken under it do not contain the fsm
-- data; see "Backups" in the README.
--
-- The sequences are listed too, so that a restored database carries on
-- numbering where the dumped one left off. pg_dump orders the data by the
-- foreign keys between these tables, and the triggers on fsm.state and
-- fsm.transition qualify their ltree references so that they work under the
-- empty search_path that pg_restore loads data with.
--
-- fsm.state_machine_event and its sequence are deliberately left out. The
-- table is an inbox queue, not state: fsm.handle_machine_events consumes an
-- event in the same transaction that inserts it, so a committed row is always
-- one that has already been applied to fsm.state_machine_state, and the state
-- it produced is in the backup. What is left is a log kept for debugging,
-- which grows far too fast to be worth carrying in every dump. Restoring it
-- would also be a hazard rather than a help: the insert trigger fires while
-- pg_restore loads the rows, so any event that did somehow sit unhandled in
-- the dump would be handled again on the restored database, moving machines
-- that were dumped in a settled state and firing their on_entry and on_exit
-- callbacks a second time.
select pg_catalog.pg_extension_config_dump('fsm.statechart', '');
select pg_catalog.pg_extension_config_dump('fsm.state', '');
select pg_catalog.pg_extension_config_dump('fsm.transition', '');
select pg_catalog.pg_extension_config_dump('fsm.state_machine', '');
select pg_catalog.pg_extension_config_dump('fsm.state_machine_state', '');
select pg_catalog.pg_extension_config_dump('fsm.statechart_id_seq', '');
select pg_catalog.pg_extension_config_dump('fsm.state_machine_id_seq', '');