8f4569353e6f529ff097053f0fd6c68ee22ad359

Committed 26 Apr 2026 08:10PM UTC coverage: 92.503% (+0.2%) from 92.313%

Build # 8f4569353e6f529ff097053f0fd6c68ee22ad359

Build Type

push

github

Committed by

code-shoily

Commit Message

Update README and CHANGESET

Coverage Stats

1419 of 1534 relevant lines covered (92.5%)

20.04 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

94.29

/lib/choreo/fsm.ex

defmodule Choreo.FSM do
  @moduledoc """
  Finite-state machine builder on top of Yog.

  `Choreo.FSM` lets you define states, transitions, and render classic
  state-machine diagrams. It supports normal states, initial states, and
  final (accepting) states.

  ## When to use

  Use `Choreo.FSM` when modelling stateful behaviour — protocol handlers,
  UI flows, game states, or embedded-system controllers. It verifies
  determinism, finds dead states, and checks whether any input sequence
  leads to acceptance.

  ## Further reading

    * [Finite-state machine (Wikipedia)](https://en.wikipedia.org/wiki/Finite-state_machine)
    * [Automata Theory (Sipser)](https://math.mit.edu/~sipser/book.html)
    * [UML State Machine Diagrams](https://www.uml-diagrams.org/state-machine-diagrams.html)

  ## Quick Start

      fsm =
        Choreo.FSM.new()
        |> Choreo.FSM.add_initial_state(:idle, label: "Idle")
        |> Choreo.FSM.add_state(:running, label: "Running")
        |> Choreo.FSM.add_final_state(:done, label: "Done")
        |> Choreo.FSM.add_transition(:idle, :running, label: "start")
        |> Choreo.FSM.add_transition(:running, :done, label: "finish")
        |> Choreo.FSM.add_transition(:running, :idle, label: "pause")

      dot = Choreo.FSM.to_dot(fsm)

  ## Diagram

  <div class="graphviz">
    digraph G {
      graph [rankdir=LR, splines=spline, nodesep=0.5, ranksep=1.0];
      node [shape=circle, style=filled, fillcolor="#e2e8f0", fontname="Helvetica", fontsize=12, fontcolor="#1e293b"];
      edge [arrowhead=normal, color="#475569", style=solid, fontname="Helvetica", fontsize=10, penwidth=1.0];

      running [label="Running", fillcolor="#e2e8f0"];
      idle [label="Idle", fontcolor="white", fillcolor="#10b981"];
      done [label="Done", penwidth="2.0", fillcolor="#e2e8f0", shape="doublecircle"];

      running -> idle [label="pause"];
      running -> done [label="finish"];
      idle -> running [label="start"];

      __start_idle [shape=point, width=0.15, height=0.15, style=filled, fillcolor=black];
      __start_idle -> idle;
    }
  </div>

  ## Themes

  Use `:default`, `:dark`, or a custom `Choreo.Theme` struct:

      dot = Choreo.FSM.to_dot(fsm, theme: :dark)
  """

  @type t :: %__MODULE__{
          graph: Yog.Multi.Graph.t(),
          edge_meta: %{optional(Yog.Multi.Graph.edge_id()) => map()},
          meta: map()
        }

  defstruct graph: nil, edge_meta: %{}, meta: %{}

  @new_schema [
    directed: [
      type: :boolean,
      required: false,
      default: true
    ]
  ]

  @add_state_schema [
    label: [
      type: :string,
      required: false
    ],
    type: [
      type: {:in, [:normal, :initial, :final]},
      required: false
    ]
  ]

  @add_initial_state_schema [
    label: [
      type: :string,
      required: false
    ]
  ]

  @add_final_state_schema [
    label: [
      type: :string,
      required: false
    ]
  ]

  @add_transition_schema [
    label: [
      type: :string,
      required: false
    ],
    guard: [
      type: :string,
      required: false
    ]
  ]

  alias Choreo.FSM.Analysis

  # ============================================================================
  # Creation
  # ============================================================================

  @doc """
  Creates a new empty FSM.

  ## Options

    * `:directed` — whether the underlying graph is directed (default: `true`)

  ## Examples

      iex> fsm = Choreo.FSM.new()
      iex> fsm.graph.kind == :directed
      true
  """
  @spec new(keyword()) :: t()
  def new(opts \\ []) do
    opts = NimbleOptions.validate!(opts, @new_schema)
    kind = if opts[:directed], do: :directed, else: :undirected

    %__MODULE__{
      graph: Yog.Multi.new(kind),
      edge_meta: %{},
      meta: %{initial_state: nil, final_states: MapSet.new()}
    }
  end

  # ============================================================================
  # States
  # ============================================================================

  @doc """
  Adds a state to the FSM.

  ## Options

    * `:label` — display label (defaults to the state id)
    * `:type` — `:normal`, `:initial`, or `:final` (default: `:normal`)

  ## Examples

      iex> fsm = Choreo.FSM.new() |> Choreo.FSM.add_state(:idle, label: "Idle")
      iex> fsm.graph.nodes[:idle].label
      "Idle"

  ## Diagram

  <div class="graphviz">
    digraph G {
      graph [rankdir=LR, splines=spline, nodesep=0.5, ranksep=1.0];
      node [shape=circle, style=filled, fillcolor="#e2e8f0", fontname="Helvetica", fontsize=12, fontcolor="#1e293b"];
      edge [arrowhead=normal, color="#475569", style=solid, fontname="Helvetica", fontsize=10, penwidth=1.0];

      idle [label="Idle", fillcolor="#e2e8f0"];
    }
  </div>
  """
  @spec add_state(t(), Yog.node_id(), keyword()) :: t()
  def add_state(%__MODULE__{} = fsm, id, opts \\ []) do
    opts = NimbleOptions.validate!(opts, @add_state_schema)

    data = %{
      type: :state,
      label: Keyword.get(opts, :label, to_string(id))
    }

    fsm = %{fsm | graph: Yog.Multi.add_node(fsm.graph, id, data)}

    case Keyword.get(opts, :type) do
      :initial ->
        if fsm.meta.initial_state != nil do
          raise ArgumentError, "DFAs can only have one initial state"
        end

        put_in(fsm.meta.initial_state, id)

      :final ->
        put_in(fsm.meta.final_states, MapSet.put(fsm.meta.final_states, id))

      :normal ->
        fsm
        |> then(fn acc ->
          if acc.meta.initial_state == id, do: put_in(acc.meta.initial_state, nil), else: acc
        end)
        |> put_in([Access.key!(:meta), :final_states], MapSet.delete(fsm.meta.final_states, id))

      nil ->
        fsm
    end
  end

  @doc """
  Adds an initial state to the FSM.

  Initial states are rendered with a filled entry-point dot and an incoming
  arrow in DOT output.

  ## Options

    * `:label` — display label (defaults to the state id)

  ## Examples

      iex> fsm = Choreo.FSM.new() |> Choreo.FSM.add_initial_state(:idle)
      iex> :idle in Choreo.FSM.initial_states(fsm)
      true

  ## Diagram

  <div class="graphviz">
    digraph G {
      graph [rankdir=LR, splines=spline, nodesep=0.5, ranksep=1.0];
      node [shape=circle, style=filled, fillcolor="#e2e8f0", fontname="Helvetica", fontsize=12, fontcolor="#1e293b"];
      edge [arrowhead=normal, color="#475569", style=solid, fontname="Helvetica", fontsize=10, penwidth=1.0];

      idle [label="idle", fontcolor="white", fillcolor="#10b981"];

      __start_idle [shape=point, width=0.15, height=0.15, style=filled, fillcolor=black];
      __start_idle -> idle;
    }
  </div>
  """
  @spec add_initial_state(t(), Yog.node_id(), keyword()) :: t()
  def add_initial_state(%__MODULE__{} = fsm, id, opts \\ []) do
    opts = NimbleOptions.validate!(opts, @add_initial_state_schema)

    if fsm.meta.initial_state != nil do
      raise ArgumentError, "DFAs can only have one initial state"
    end

    fsm
    |> add_state(id, opts)
    |> put_in([Access.key!(:meta), :initial_state], id)
  end

  @doc """
  Adds a final (accepting) state to the FSM.

  Final states are rendered as double circles.

  ## Options

    * `:label` — display label (defaults to the state id)

  ## Examples

      iex> fsm = Choreo.FSM.new() |> Choreo.FSM.add_final_state(:done)
      iex> :done in Choreo.FSM.final_states(fsm)
      true

  ## Diagram

  <div class="graphviz">
    digraph G {
      graph [rankdir=LR, splines=spline, nodesep=0.5, ranksep=1.0];
      node [shape=circle, style=filled, fillcolor="#e2e8f0", fontname="Helvetica", fontsize=12, fontcolor="#1e293b"];
      edge [arrowhead=normal, color="#475569", style=solid, fontname="Helvetica", fontsize=10, penwidth=1.0];

      done [label="done", penwidth="2.0", fillcolor="#e2e8f0", shape="doublecircle"];
    }
  </div>
  """
  @spec add_final_state(t(), Yog.node_id(), keyword()) :: t()
  def add_final_state(%__MODULE__{} = fsm, id, opts \\ []) do
    opts = NimbleOptions.validate!(opts, @add_final_state_schema)

    fsm
    |> add_state(id, opts)
    |> put_in([Access.key!(:meta), :final_states], MapSet.put(fsm.meta.final_states, id))
  end

  @doc """
  Removes a state from the set of initial states.

  ## Examples

      iex> fsm = Choreo.FSM.new() |> Choreo.FSM.add_initial_state(:idle) |> Choreo.FSM.remove_initial_state(:idle)
      iex> :idle in Choreo.FSM.initial_states(fsm)
      false
  """
  @spec remove_initial_state(t(), Yog.node_id()) :: t()
  def remove_initial_state(%__MODULE__{} = fsm, id) do
    if fsm.meta.initial_state == id do
      put_in(fsm.meta.initial_state, nil)
    else
      fsm
    end
  end

  @doc """
  Removes a state from the set of final states.

  ## Examples

      iex> fsm = Choreo.FSM.new() |> Choreo.FSM.add_final_state(:done) |> Choreo.FSM.remove_final_state(:done)
      iex> :done in Choreo.FSM.final_states(fsm)
      false
  """
  @spec remove_final_state(t(), Yog.node_id()) :: t()
  def remove_final_state(%__MODULE__{} = fsm, id) do
    put_in(fsm.meta.final_states, MapSet.delete(fsm.meta.final_states, id))
  end

  # ============================================================================
  # Transitions
  # ============================================================================

  @doc """
  Adds a transition (directed edge) between two states.

  Multiple transitions are allowed per `(from, to)` pair (parallel edges),
  as long as they have unique labels from the source state.

  ## Options

    * `:label` — label shown on the transition arrow
    * `:guard` — guard condition (rendered alongside the label)

  ## Examples

      iex> fsm =
      ...>   Choreo.FSM.new()
      ...>   |> Choreo.FSM.add_state(:a)
      ...>   |> Choreo.FSM.add_state(:b)
      ...>   |> Choreo.FSM.add_transition(:a, :b, label: "go")
      iex> Yog.Multi.edges_between(fsm.graph, :a, :b) != []
      true

  ## Diagram

  <div class="graphviz">
    digraph G {
      graph [rankdir=LR, splines=spline, nodesep=0.5, ranksep=1.0];
      node [shape=circle, style=filled, fillcolor="#e2e8f0", fontname="Helvetica", fontsize=12, fontcolor="#1e293b"];
      edge [arrowhead=normal, color="#475569", style=solid, fontname="Helvetica", fontsize=10, penwidth=1.0];

      b [label="b", fillcolor="#e2e8f0"];
      a [label="a", fillcolor="#e2e8f0"];

      a -> b [label="go"];
    }
  </div>
  """
  @spec add_transition(t(), Yog.node_id(), Yog.node_id(), keyword()) :: t()
  def add_transition(%__MODULE__{} = fsm, from, to, opts \\ []) do
    opts = NimbleOptions.validate!(opts, @add_transition_schema)
    label = build_transition_label(opts)

    # DFAs do not support epsilon transitions
    if label == "" do
      raise ArgumentError,
            "epsilon transitions (empty labels) are not supported in DFAs"
    end

    existing = Yog.Multi.successors(fsm.graph, from)

    existing_labels = Enum.map(existing, fn {_dest, _eid, lbl} -> lbl end)

    if label in existing_labels do
      raise ArgumentError,
            "duplicate transition label #{inspect(label)} from state #{inspect(from)}"
    end

    {graph, edge_id} = Yog.Multi.add_edge(fsm.graph, from, to, label)
    edge_meta = Map.put(fsm.edge_meta, edge_id, %{label: label, guard: opts[:guard]})

    %{fsm | graph: graph, edge_meta: edge_meta}
  end

  defp build_transition_label(opts) do
    parts =
      []
      |> then(&if label = opts[:label], do: [label | &1], else: &1)
      |> then(&if guard = opts[:guard], do: ["[#{guard}]" | &1], else: &1)

    case parts do
      [] -> ""
      list -> Enum.reverse(list) |> Enum.join(" ")
    end
  end

  # ============================================================================
  # Queries
  # ============================================================================

  @doc """
  Returns all state IDs in the FSM.

  ## Examples

      iex> fsm = Choreo.FSM.new() |> Choreo.FSM.add_state(:a) |> Choreo.FSM.add_state(:b)
      iex> Enum.sort(Choreo.FSM.states(fsm))
      [:a, :b]
  """
  @spec states(t()) :: [Yog.node_id()]
  def states(%__MODULE__{graph: graph}) do
    Map.keys(graph.nodes)
  end

  @doc """
  Returns all transitions as `{from, to, label}` tuples.

  ## Examples

      iex> fsm =
      ...>   Choreo.FSM.new()
      ...>   |> Choreo.FSM.add_state(:a)
      ...>   |> Choreo.FSM.add_state(:b)
      ...>   |> Choreo.FSM.add_transition(:a, :b, label: "go")
      iex> Choreo.FSM.transitions(fsm)
      [{:a, :b, "go"}]
  """
  @spec transitions(t()) :: [{Yog.node_id(), Yog.node_id(), String.t()}]
  def transitions(%__MODULE__{graph: graph}) do
    Enum.map(graph.edges, fn {_edge_id, {from, to, label}} ->
      {from, to, label}
    end)
  end

  @doc """
  Returns the set of initial state IDs.

  ## Examples

      iex> fsm = Choreo.FSM.new() |> Choreo.FSM.add_initial_state(:idle)
      iex> :idle in Choreo.FSM.initial_states(fsm)
      true
  """
  @spec initial_states(t()) :: MapSet.t(Yog.node_id())
  def initial_states(%__MODULE__{meta: %{initial_state: nil}}), do: MapSet.new()
  def initial_states(%__MODULE__{meta: %{initial_state: state}}), do: MapSet.new([state])
  def initial_states(%__MODULE__{}), do: MapSet.new()

  @doc """
  Returns all final state IDs.

  ## Examples

      iex> fsm = Choreo.FSM.new() |> Choreo.FSM.add_final_state(:done)
      iex> :done in Choreo.FSM.final_states(fsm)
      true
  """
  @spec final_states(t()) :: [Yog.node_id()]
  def final_states(%__MODULE__{meta: %{final_states: set}}), do: MapSet.to_list(set)
  def final_states(%__MODULE__{}), do: []

  # ============================================================================
  # Transforms
  # ============================================================================

  @doc """
  Returns the complement FSM: final states become normal, and normal states
  become final. Initial states keep their `:initial` type.

  ## Examples

      iex> fsm =
      ...>   Choreo.FSM.new()
      ...>   |> Choreo.FSM.add_initial_state(:a)
      ...>   |> Choreo.FSM.add_final_state(:b)
      iex> comp = Choreo.FSM.complement(fsm)
      iex> :a in Choreo.FSM.final_states(comp)
      true
      iex> :b in Choreo.FSM.final_states(comp)
      false

  ## Diagram

  <div class="graphviz">
    digraph G {
      graph [rankdir=LR, splines=spline, nodesep=0.5, ranksep=1.0];
      node [shape=circle, style=filled, fillcolor="#e2e8f0", fontname="Helvetica", fontsize=12, fontcolor="#1e293b"];
      edge [arrowhead=normal, color="#475569", style=solid, fontname="Helvetica", fontsize=10, penwidth=1.0];

      b [label="b", fillcolor="#e2e8f0"];
      a [label="a", penwidth="2.0", fontcolor="white", fillcolor="#10b981", shape="doublecircle"];

      __start_a [shape=point, width=0.15, height=0.15, style=filled, fillcolor=black];
      __start_a -> a;
    }
  </div>
  """
  @spec complement(t()) :: t()
  def complement(%__MODULE__{} = fsm) do
    all_states = states(fsm) |> MapSet.new()
    old_finals = final_states(fsm) |> MapSet.new()
    new_finals = MapSet.difference(all_states, old_finals)

    put_in(fsm.meta.final_states, new_finals)
  end

  @doc """
  Prunes unreachable and dead states, returning a smaller equivalent FSM.

  * Unreachable states — no path from any initial state
  * Dead states — no path to any final state

  ## Examples

      iex> fsm =
      ...>   Choreo.FSM.new()
      ...>   |> Choreo.FSM.add_initial_state(:a)
      ...>   |> Choreo.FSM.add_state(:b)
      ...>   |> Choreo.FSM.add_state(:trap)
      ...>   |> Choreo.FSM.add_final_state(:c)
      ...>   |> Choreo.FSM.add_transition(:a, :c, label: "go")
      iex> pruned = Choreo.FSM.prune(fsm)
      iex> :a in Choreo.FSM.states(pruned)
      true
      iex> :b in Choreo.FSM.states(pruned)
      false
      iex> :trap in Choreo.FSM.states(pruned)
      false

  ## Diagram

  <div class="graphviz">
    digraph G {
      graph [rankdir=LR, splines=spline, nodesep=0.5, ranksep=1.0];
      node [shape=circle, style=filled, fillcolor="#e2e8f0", fontname="Helvetica", fontsize=12, fontcolor="#1e293b"];
      edge [arrowhead=normal, color="#475569", style=solid, fontname="Helvetica", fontsize=10, penwidth=1.0];

      c [label="c", penwidth="2.0", fillcolor="#e2e8f0", shape="doublecircle"];
      a [label="a", fontcolor="white", fillcolor="#10b981"];

      a -> c [label="go"];

      __start_a [shape=point, width=0.15, height=0.15, style=filled, fillcolor=black];
      __start_a -> a;
    }
  </div>
  """
  @spec prune(t()) :: t()
  def prune(%__MODULE__{} = fsm) do
    reachable = Analysis.reachable_states(fsm) |> MapSet.new()
    dead = Analysis.dead_states(fsm) |> MapSet.new()
    all = states(fsm) |> MapSet.new()

    to_remove = MapSet.union(dead, MapSet.difference(all, reachable))

    removed_edge_ids =
      fsm.graph.edges
      |> Enum.filter(fn {_eid, {from, to, _data}} ->
        from in to_remove or to in to_remove
      end)
      |> Enum.map(fn {eid, _} -> eid end)

    new_graph = Enum.reduce(to_remove, fsm.graph, &Yog.Multi.remove_node(&2, &1))

    new_edge_meta = Map.drop(fsm.edge_meta, removed_edge_ids)

    new_meta = %{
      fsm.meta
      | initial_state:
          if(fsm.meta.initial_state in to_remove, do: nil, else: fsm.meta.initial_state),
        final_states: MapSet.difference(fsm.meta.final_states, to_remove)
    }

    %__MODULE__{fsm | graph: new_graph, edge_meta: new_edge_meta, meta: new_meta}
  end

  # ============================================================================
  # Rendering
  # ============================================================================

  @doc """
  Renders the FSM to DOT format.

  ## Options

    * `:theme` — `:default`, `:dark`, or a `Choreo.Theme` struct

  ## Examples

      iex> fsm = Choreo.FSM.new() |> Choreo.FSM.add_state(:a)
      iex> dot = Choreo.FSM.to_dot(fsm)
      iex> String.contains?(dot, "digraph")
      true
      iex> String.contains?(dot, "a")
      true
  """
  @spec to_dot(t(), keyword()) :: String.t()
  def to_dot(%__MODULE__{} = fsm, opts \\ []) do
    Choreo.FSM.Render.DOT.to_dot(fsm, opts)
  end
end

1	defmodule Choreo.FSM do
2	@moduledoc """
3	Finite-state machine builder on top of Yog.
4
5	`Choreo.FSM` lets you define states, transitions, and render classic
6	state-machine diagrams. It supports normal states, initial states, and
7	final (accepting) states.
8
9	## When to use
10
11	Use `Choreo.FSM` when modelling stateful behaviour — protocol handlers,
12	UI flows, game states, or embedded-system controllers. It verifies
13	determinism, finds dead states, and checks whether any input sequence
14	leads to acceptance.
15
16	## Further reading
17
18	* [Finite-state machine (Wikipedia)](https://en.wikipedia.org/wiki/Finite-state_machine)
19	* [Automata Theory (Sipser)](https://math.mit.edu/~sipser/book.html)
20	* [UML State Machine Diagrams](https://www.uml-diagrams.org/state-machine-diagrams.html)
21
22	## Quick Start
23
24	fsm =
25	Choreo.FSM.new()
26	\|> Choreo.FSM.add_initial_state(:idle, label: "Idle")
27	\|> Choreo.FSM.add_state(:running, label: "Running")
28	\|> Choreo.FSM.add_final_state(:done, label: "Done")
29	\|> Choreo.FSM.add_transition(:idle, :running, label: "start")
30	\|> Choreo.FSM.add_transition(:running, :done, label: "finish")
31	\|> Choreo.FSM.add_transition(:running, :idle, label: "pause")
32
33	dot = Choreo.FSM.to_dot(fsm)
34
35	## Diagram
36
37	<div class="graphviz">
38	digraph G {
39	graph [rankdir=LR, splines=spline, nodesep=0.5, ranksep=1.0];
40	node [shape=circle, style=filled, fillcolor="#e2e8f0", fontname="Helvetica", fontsize=12, fontcolor="#1e293b"];
41	edge [arrowhead=normal, color="#475569", style=solid, fontname="Helvetica", fontsize=10, penwidth=1.0];
42
43	running [label="Running", fillcolor="#e2e8f0"];
44	idle [label="Idle", fontcolor="white", fillcolor="#10b981"];
45	done [label="Done", penwidth="2.0", fillcolor="#e2e8f0", shape="doublecircle"];
46
47	running -> idle [label="pause"];
48	running -> done [label="finish"];
49	idle -> running [label="start"];
50
51	__start_idle [shape=point, width=0.15, height=0.15, style=filled, fillcolor=black];
52	__start_idle -> idle;
53	}
54	</div>
55
56	## Themes
57
58	Use `:default`, `:dark`, or a custom `Choreo.Theme` struct:
59
60	dot = Choreo.FSM.to_dot(fsm, theme: :dark)
61	"""
62
63	@type t :: %__MODULE__{
64	graph: Yog.Multi.Graph.t(),
65	edge_meta: %{optional(Yog.Multi.Graph.edge_id()) => map()},
66	meta: map()
67	}
68
69	defstruct graph: nil, edge_meta: %{}, meta: %{}
70
71	@new_schema [
72	directed: [
73	type: :boolean,
74	required: false,
75	default: true
76	]
77	]
78
79	@add_state_schema [
80	label: [
81	type: :string,
82	required: false
83	],
84	type: [
85	type: {:in, [:normal, :initial, :final]},
86	required: false
87	]
88	]
89
90	@add_initial_state_schema [
91	label: [
92	type: :string,
93	required: false
94	]
95	]
96
97	@add_final_state_schema [
98	label: [
99	type: :string,
100	required: false
101	]
102	]
103
104	@add_transition_schema [
105	label: [
106	type: :string,
107	required: false
108	],
109	guard: [
110	type: :string,
111	required: false
112	]
113	]
114
115	alias Choreo.FSM.Analysis
116
117	# ============================================================================
118	# Creation
119	# ============================================================================
120
121	@doc """
122	Creates a new empty FSM.
123
124	## Options
125
126	* `:directed` — whether the underlying graph is directed (default: `true`)
127
128	## Examples
129
130	iex> fsm = Choreo.FSM.new()
131	iex> fsm.graph.kind == :directed
132	true
133	"""
134	@spec new(keyword()) :: t()
135	def new(opts \\ []) do
136	opts = NimbleOptions.validate!(opts, @new_schema)	95✔
137	kind = if opts[:directed], do: :directed, else: :undirected	94✔
138
139	%__MODULE__{	94✔
140	graph: Yog.Multi.new(kind),
141	edge_meta: %{},
142	meta: %{initial_state: nil, final_states: MapSet.new()}
143	}
144	end
145
146	# ============================================================================
147	# States
148	# ============================================================================
149
150	@doc """
151	Adds a state to the FSM.
152
153	## Options
154
155	* `:label` — display label (defaults to the state id)
156	* `:type` — `:normal`, `:initial`, or `:final` (default: `:normal`)
157
158	## Examples
159
160	iex> fsm = Choreo.FSM.new() \|> Choreo.FSM.add_state(:idle, label: "Idle")
161	iex> fsm.graph.nodes[:idle].label
162	"Idle"
163
164	## Diagram
165
166	<div class="graphviz">
167	digraph G {
168	graph [rankdir=LR, splines=spline, nodesep=0.5, ranksep=1.0];
169	node [shape=circle, style=filled, fillcolor="#e2e8f0", fontname="Helvetica", fontsize=12, fontcolor="#1e293b"];
170	edge [arrowhead=normal, color="#475569", style=solid, fontname="Helvetica", fontsize=10, penwidth=1.0];
171
172	idle [label="Idle", fillcolor="#e2e8f0"];
173	}
174	</div>
175	"""
176	@spec add_state(t(), Yog.node_id(), keyword()) :: t()
177	def add_state(%__MODULE__{} = fsm, id, opts \\ []) do
178	opts = NimbleOptions.validate!(opts, @add_state_schema)	175✔
179
180	data = %{	173✔
181	type: :state,
182	label: Keyword.get(opts, :label, to_string(id))	173✔
183	}
184
185	fsm = %{fsm \| graph: Yog.Multi.add_node(fsm.graph, id, data)}	173✔
186
187	case Keyword.get(opts, :type) do	173✔
188	:initial ->
189	if fsm.meta.initial_state != nil do	4✔
190	raise ArgumentError, "DFAs can only have one initial state"	1✔
191	end
192
193	put_in(fsm.meta.initial_state, id)	3✔
194
195	:final ->
196	put_in(fsm.meta.final_states, MapSet.put(fsm.meta.final_states, id))	2✔
197
198	:normal ->
199	fsm
200	\|> then(fn acc ->
201	if acc.meta.initial_state == id, do: put_in(acc.meta.initial_state, nil), else: acc	1✔
202	end)
203	\|> put_in([Access.key!(:meta), :final_states], MapSet.delete(fsm.meta.final_states, id))	1✔
204
205	nil ->
206	fsm	166✔
207	end
208	end
209
210	@doc """
211	Adds an initial state to the FSM.
212
213	Initial states are rendered with a filled entry-point dot and an incoming
214	arrow in DOT output.
215
216	## Options
217
218	* `:label` — display label (defaults to the state id)
219
220	## Examples
221
222	iex> fsm = Choreo.FSM.new() \|> Choreo.FSM.add_initial_state(:idle)
223	iex> :idle in Choreo.FSM.initial_states(fsm)
224	true
225
226	## Diagram
227
228	<div class="graphviz">
229	digraph G {
230	graph [rankdir=LR, splines=spline, nodesep=0.5, ranksep=1.0];
231	node [shape=circle, style=filled, fillcolor="#e2e8f0", fontname="Helvetica", fontsize=12, fontcolor="#1e293b"];
232	edge [arrowhead=normal, color="#475569", style=solid, fontname="Helvetica", fontsize=10, penwidth=1.0];
233
234	idle [label="idle", fontcolor="white", fillcolor="#10b981"];
235
236	__start_idle [shape=point, width=0.15, height=0.15, style=filled, fillcolor=black];
237	__start_idle -> idle;
238	}
239	</div>
240	"""
241	@spec add_initial_state(t(), Yog.node_id(), keyword()) :: t()
242	def add_initial_state(%__MODULE__{} = fsm, id, opts \\ []) do
243	opts = NimbleOptions.validate!(opts, @add_initial_state_schema)	44✔
244
245	if fsm.meta.initial_state != nil do	43✔
246	raise ArgumentError, "DFAs can only have one initial state"	1✔
247	end
248
249	fsm
250	\|> add_state(id, opts)
251	\|> put_in([Access.key!(:meta), :initial_state], id)	42✔
252	end
253
254	@doc """
255	Adds a final (accepting) state to the FSM.
256
257	Final states are rendered as double circles.
258
259	## Options
260
261	* `:label` — display label (defaults to the state id)
262
263	## Examples
264
265	iex> fsm = Choreo.FSM.new() \|> Choreo.FSM.add_final_state(:done)
266	iex> :done in Choreo.FSM.final_states(fsm)
267	true
268
269	## Diagram
270
271	<div class="graphviz">
272	digraph G {
273	graph [rankdir=LR, splines=spline, nodesep=0.5, ranksep=1.0];
274	node [shape=circle, style=filled, fillcolor="#e2e8f0", fontname="Helvetica", fontsize=12, fontcolor="#1e293b"];
275	edge [arrowhead=normal, color="#475569", style=solid, fontname="Helvetica", fontsize=10, penwidth=1.0];
276
277	done [label="done", penwidth="2.0", fillcolor="#e2e8f0", shape="doublecircle"];
278	}
279	</div>
280	"""
281	@spec add_final_state(t(), Yog.node_id(), keyword()) :: t()
282	def add_final_state(%__MODULE__{} = fsm, id, opts \\ []) do
283	opts = NimbleOptions.validate!(opts, @add_final_state_schema)	37✔
284
285	fsm
286	\|> add_state(id, opts)
287	\|> put_in([Access.key!(:meta), :final_states], MapSet.put(fsm.meta.final_states, id))	36✔
288	end
289
290	@doc """
291	Removes a state from the set of initial states.
292
293	## Examples
294
295	iex> fsm = Choreo.FSM.new() \|> Choreo.FSM.add_initial_state(:idle) \|> Choreo.FSM.remove_initial_state(:idle)
296	iex> :idle in Choreo.FSM.initial_states(fsm)
297	false
298	"""
299	@spec remove_initial_state(t(), Yog.node_id()) :: t()
300	def remove_initial_state(%__MODULE__{} = fsm, id) do
301	if fsm.meta.initial_state == id do	2✔
302	put_in(fsm.meta.initial_state, nil)	2✔
303	else
304	fsm	×
305	end
306	end
307
308	@doc """
309	Removes a state from the set of final states.
310
311	## Examples
312
313	iex> fsm = Choreo.FSM.new() \|> Choreo.FSM.add_final_state(:done) \|> Choreo.FSM.remove_final_state(:done)
314	iex> :done in Choreo.FSM.final_states(fsm)
315	false
316	"""
317	@spec remove_final_state(t(), Yog.node_id()) :: t()
318	def remove_final_state(%__MODULE__{} = fsm, id) do
319	put_in(fsm.meta.final_states, MapSet.delete(fsm.meta.final_states, id))	2✔
320	end
321
322	# ============================================================================
323	# Transitions
324	# ============================================================================
325
326	@doc """
327	Adds a transition (directed edge) between two states.
328
329	Multiple transitions are allowed per `(from, to)` pair (parallel edges),
330	as long as they have unique labels from the source state.
331
332	## Options
333
334	* `:label` — label shown on the transition arrow
335	* `:guard` — guard condition (rendered alongside the label)
336
337	## Examples
338
339	iex> fsm =
340	...> Choreo.FSM.new()
341	...> \|> Choreo.FSM.add_state(:a)
342	...> \|> Choreo.FSM.add_state(:b)
343	...> \|> Choreo.FSM.add_transition(:a, :b, label: "go")
344	iex> Yog.Multi.edges_between(fsm.graph, :a, :b) != []
345	true
346
347	## Diagram
348
349	<div class="graphviz">
350	digraph G {
351	graph [rankdir=LR, splines=spline, nodesep=0.5, ranksep=1.0];
352	node [shape=circle, style=filled, fillcolor="#e2e8f0", fontname="Helvetica", fontsize=12, fontcolor="#1e293b"];
353	edge [arrowhead=normal, color="#475569", style=solid, fontname="Helvetica", fontsize=10, penwidth=1.0];
354
355	b [label="b", fillcolor="#e2e8f0"];
356	a [label="a", fillcolor="#e2e8f0"];
357
358	a -> b [label="go"];
359	}
360	</div>
361	"""
362	@spec add_transition(t(), Yog.node_id(), Yog.node_id(), keyword()) :: t()
363	def add_transition(%__MODULE__{} = fsm, from, to, opts \\ []) do
364	opts = NimbleOptions.validate!(opts, @add_transition_schema)	83✔
365	label = build_transition_label(opts)	82✔
366
367	# DFAs do not support epsilon transitions
368	if label == "" do	82✔
369	raise ArgumentError,	2✔
370	"epsilon transitions (empty labels) are not supported in DFAs"
371	end
372
373	existing = Yog.Multi.successors(fsm.graph, from)	80✔
374
375	existing_labels = Enum.map(existing, fn {_dest, _eid, lbl} -> lbl end)	80✔
376
377	if label in existing_labels do	80✔
378	raise ArgumentError,	1✔
379	"duplicate transition label #{inspect(label)} from state #{inspect(from)}"
380	end
381
382	{graph, edge_id} = Yog.Multi.add_edge(fsm.graph, from, to, label)	79✔
383	edge_meta = Map.put(fsm.edge_meta, edge_id, %{label: label, guard: opts[:guard]})	79✔
384
385	%{fsm \| graph: graph, edge_meta: edge_meta}	79✔
386	end
387
388	defp build_transition_label(opts) do
389	parts =	82✔
390	[]
391	\|> then(&if label = opts[:label], do: [label \| &1], else: &1)	82✔
392	\|> then(&if guard = opts[:guard], do: ["[#{guard}]" \| &1], else: &1)	82✔
393
394	case parts do	82✔
395	[] -> ""	2✔
396	list -> Enum.reverse(list) \|> Enum.join(" ")	80✔
397	end
398	end
399
400	# ============================================================================
401	# Queries
402	# ============================================================================
403
404	@doc """
405	Returns all state IDs in the FSM.
406
407	## Examples
408
409	iex> fsm = Choreo.FSM.new() \|> Choreo.FSM.add_state(:a) \|> Choreo.FSM.add_state(:b)
410	iex> Enum.sort(Choreo.FSM.states(fsm))
411	[:a, :b]
412	"""
413	@spec states(t()) :: [Yog.node_id()]
414	def states(%__MODULE__{graph: graph}) do
415	Map.keys(graph.nodes)	51✔
416	end
417
418	@doc """
419	Returns all transitions as `{from, to, label}` tuples.
420
421	## Examples
422
423	iex> fsm =
424	...> Choreo.FSM.new()
425	...> \|> Choreo.FSM.add_state(:a)
426	...> \|> Choreo.FSM.add_state(:b)
427	...> \|> Choreo.FSM.add_transition(:a, :b, label: "go")
428	iex> Choreo.FSM.transitions(fsm)
429	[{:a, :b, "go"}]
430	"""
431	@spec transitions(t()) :: [{Yog.node_id(), Yog.node_id(), String.t()}]
432	def transitions(%__MODULE__{graph: graph}) do
433	Enum.map(graph.edges, fn {_edge_id, {from, to, label}} ->	4✔
434	{from, to, label}	5✔
435	end)
436	end
437
438	@doc """
439	Returns the set of initial state IDs.
440
441	## Examples
442
443	iex> fsm = Choreo.FSM.new() \|> Choreo.FSM.add_initial_state(:idle)
444	iex> :idle in Choreo.FSM.initial_states(fsm)
445	true
446	"""
447	@spec initial_states(t()) :: MapSet.t(Yog.node_id())
448	def initial_states(%__MODULE__{meta: %{initial_state: nil}}), do: MapSet.new()	29✔
449	def initial_states(%__MODULE__{meta: %{initial_state: state}}), do: MapSet.new([state])	43✔
450	def initial_states(%__MODULE__{}), do: MapSet.new()	×
451
452	@doc """
453	Returns all final state IDs.
454
455	## Examples
456
457	iex> fsm = Choreo.FSM.new() \|> Choreo.FSM.add_final_state(:done)
458	iex> :done in Choreo.FSM.final_states(fsm)
459	true
460	"""
461	@spec final_states(t()) :: [Yog.node_id()]
462	def final_states(%__MODULE__{meta: %{final_states: set}}), do: MapSet.to_list(set)	77✔
463	def final_states(%__MODULE__{}), do: []	×
464
465	# ============================================================================
466	# Transforms
467	# ============================================================================
468
469	@doc """
470	Returns the complement FSM: final states become normal, and normal states
471	become final. Initial states keep their `:initial` type.
472
473	## Examples
474
475	iex> fsm =
476	...> Choreo.FSM.new()
477	...> \|> Choreo.FSM.add_initial_state(:a)
478	...> \|> Choreo.FSM.add_final_state(:b)
479	iex> comp = Choreo.FSM.complement(fsm)
480	iex> :a in Choreo.FSM.final_states(comp)
481	true
482	iex> :b in Choreo.FSM.final_states(comp)
483	false
484
485	## Diagram
486
487	<div class="graphviz">
488	digraph G {
489	graph [rankdir=LR, splines=spline, nodesep=0.5, ranksep=1.0];
490	node [shape=circle, style=filled, fillcolor="#e2e8f0", fontname="Helvetica", fontsize=12, fontcolor="#1e293b"];
491	edge [arrowhead=normal, color="#475569", style=solid, fontname="Helvetica", fontsize=10, penwidth=1.0];
492
493	b [label="b", fillcolor="#e2e8f0"];
494	a [label="a", penwidth="2.0", fontcolor="white", fillcolor="#10b981", shape="doublecircle"];
495
496	__start_a [shape=point, width=0.15, height=0.15, style=filled, fillcolor=black];
497	__start_a -> a;
498	}
499	</div>
500	"""
501	@spec complement(t()) :: t()
502	def complement(%__MODULE__{} = fsm) do
503	all_states = states(fsm) \|> MapSet.new()	4✔
504	old_finals = final_states(fsm) \|> MapSet.new()	4✔
505	new_finals = MapSet.difference(all_states, old_finals)	4✔
506
507	put_in(fsm.meta.final_states, new_finals)	4✔
508	end
509
510	@doc """
511	Prunes unreachable and dead states, returning a smaller equivalent FSM.
512
513	* Unreachable states — no path from any initial state
514	* Dead states — no path to any final state
515
516	## Examples
517
518	iex> fsm =
519	...> Choreo.FSM.new()
520	...> \|> Choreo.FSM.add_initial_state(:a)
521	...> \|> Choreo.FSM.add_state(:b)
522	...> \|> Choreo.FSM.add_state(:trap)
523	...> \|> Choreo.FSM.add_final_state(:c)
524	...> \|> Choreo.FSM.add_transition(:a, :c, label: "go")
525	iex> pruned = Choreo.FSM.prune(fsm)
526	iex> :a in Choreo.FSM.states(pruned)
527	true
528	iex> :b in Choreo.FSM.states(pruned)
529	false
530	iex> :trap in Choreo.FSM.states(pruned)
531	false
532
533	## Diagram
534
535	<div class="graphviz">
536	digraph G {
537	graph [rankdir=LR, splines=spline, nodesep=0.5, ranksep=1.0];
538	node [shape=circle, style=filled, fillcolor="#e2e8f0", fontname="Helvetica", fontsize=12, fontcolor="#1e293b"];
539	edge [arrowhead=normal, color="#475569", style=solid, fontname="Helvetica", fontsize=10, penwidth=1.0];
540
541	c [label="c", penwidth="2.0", fillcolor="#e2e8f0", shape="doublecircle"];
542	a [label="a", fontcolor="white", fillcolor="#10b981"];
543
544	a -> c [label="go"];
545
546	__start_a [shape=point, width=0.15, height=0.15, style=filled, fillcolor=black];
547	__start_a -> a;
548	}
549	</div>
550	"""
551	@spec prune(t()) :: t()
552	def prune(%__MODULE__{} = fsm) do
553	reachable = Analysis.reachable_states(fsm) \|> MapSet.new()	4✔
554	dead = Analysis.dead_states(fsm) \|> MapSet.new()	4✔
555	all = states(fsm) \|> MapSet.new()	4✔
556
557	to_remove = MapSet.union(dead, MapSet.difference(all, reachable))	4✔
558
559	removed_edge_ids =	4✔
560	fsm.graph.edges	4✔
561	\|> Enum.filter(fn {_eid, {from, to, _data}} ->
562	from in to_remove or to in to_remove	4✔
563	end)
564	\|> Enum.map(fn {eid, _} -> eid end)	×
565
566	new_graph = Enum.reduce(to_remove, fsm.graph, &Yog.Multi.remove_node(&2, &1))	4✔
567
568	new_edge_meta = Map.drop(fsm.edge_meta, removed_edge_ids)	4✔
569
570	new_meta = %{	4✔
571	fsm.meta	4✔
572	\| initial_state:
573	if(fsm.meta.initial_state in to_remove, do: nil, else: fsm.meta.initial_state),	4✔
574	final_states: MapSet.difference(fsm.meta.final_states, to_remove)	4✔
575	}
576
577	%__MODULE__{fsm \| graph: new_graph, edge_meta: new_edge_meta, meta: new_meta}	4✔
578	end
579
580	# ============================================================================
581	# Rendering
582	# ============================================================================
583
584	@doc """
585	Renders the FSM to DOT format.
586
587	## Options
588
589	* `:theme` — `:default`, `:dark`, or a `Choreo.Theme` struct
590
591	## Examples
592
593	iex> fsm = Choreo.FSM.new() \|> Choreo.FSM.add_state(:a)
594	iex> dot = Choreo.FSM.to_dot(fsm)
595	iex> String.contains?(dot, "digraph")
596	true
597	iex> String.contains?(dot, "a")
598	true
599	"""
600	@spec to_dot(t(), keyword()) :: String.t()
601	def to_dot(%__MODULE__{} = fsm, opts \\ []) do
602	Choreo.FSM.Render.DOT.to_dot(fsm, opts)	8✔
603	end
604	end

code-shoily / choreo / 8f4569353e6f529ff097053f0fd6c68ee22ad359

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous