1
/**
2
 * State machine analyzer: a completeness check for a state machine. Every state against every event, which cells nobody
3
 * decided, which states can't be reached or left, and where two rules disagree.
4
 *
5
 * A state machine is usually drawn as its happy path. Written as a table, most of its cells are an event arriving in
6
 * a state that wasn't waiting for it, and each needs a decision. The input is written the way a person sketches one:
7
 *
8
 *     gather:                              a state; the first one is the start
9
 *       slots_complete -> search           a move
10
 *       slots_missing -> stay              an outcome: stay, defer, reject, ignore, or back
11
 *     search:
12
 *       slot_free -> confirm   # a reason  shown in the gaps and the tests
13
 *     every state except search:           a block for several states; also "a, b:" and "every state:"
14
 *       model_unavailable -> degraded
15
 *       anything else -> reject            every event this state has no other rule for
16
 *     events: model_back                   an event no rule uses yet
17
 *
18
 * A target with no header of its own, `done` say, is where the machine ends: it is not a row, because nothing
19
 * happens after it. The narrower rule wins: a state's own header beats a block of three, which beats `every state`
20
 * (and a block that names its states beats an `every state` block as large), and any named event beats
21
 * `anything else`. Two rules equally narrow that say different things about one cell are a
22
 * conflict, and the cell is left undecided until someone picks.
23
 */
24
import type { Cell, Field, GraphEdge, GraphNode, Output, Tool } from "@toolbench/sdk";
25

26
type Input = { machine: string; also: string[] };
27

28
class InputError extends Error {
29
  readonly at?: number;
30
  readonly len?: number;
31
  constructor(message: string, at?: number, len?: number) {
32
    super(message);
33
    if (at !== undefined) this.at = at;
34
    if (len !== undefined) this.len = len;
35
  }
36
}
37

38
export type Kind = "move" | "back" | "stay" | "defer" | "reject" | "ignore";
39
export type Outcome = { kind: Kind; to: string; line: number; reason: string };
40

41
const OUTCOMES = new Set(["stay", "defer", "reject", "ignore", "back"]);
42
const RESERVED = new Set([...OUTCOMES, "every", "events", "anything"]);
43
const NAME = /^\w[\w.-]*$/;
44

45
/**
46
 * How a cell reads in the grid. Words and a symbol, so a cell never has to be decoded from a colour. Only the cells
47
 * that need someone's attention carry a warning tone: an undecided or disputed cell is bad, and defer, which holds an
48
 * event for later, is warn. Reject is a bare ✕ in the muted tone, on purpose: in a finished machine most cells are
49
 * rejects, and writing or painting each one as loudly as a gap would hide the moves and the gaps. The legend says
50
 * what ✕ means.
51
 */
52
export function mark(o: Outcome | null, rules = 0): { text: string; tone?: "good" | "warn" | "bad" | "muted" } {
53
  if (rules > 1) return { text: `${rules} rules`, tone: "bad" };
54
  if (!o) return { text: "?", tone: "bad" };
55
  if (o.kind === "move") return { text: `→ ${o.to}`, tone: "good" };
56
  if (o.kind === "back") return { text: "↩ back", tone: "good" };
57
  if (o.kind === "reject") return { text: "✕", tone: "muted" };
58
  if (o.kind === "defer") return { text: "defer", tone: "warn" };
59
  return { text: o.kind };
60
}
61
export const LEGEND =
62
  "→ moves to that state, ↩ back returns to the state before, ✕ reject drops the event, ? undecided, 2 rules is a conflict.";
63

64
type Where = { line: number; at: number; len: number };
65
type Block = (Where & { names: string[] }) | (Where & { except: string[] });
66
type Rule = { block: Block; events: string[] | "else"; outcome: Outcome };
67

68
export type Machine = {
69
  states: string[];
70
  events: string[];
71
  ends: string[];
72
  start: string;
73
  /** One entry per state and event; null where nobody decided or two rules disagree. */
74
  cells: Map<string, Outcome | null>;
75
  /** The cells two equally narrow rules disagree about, with every rule that claims them. */
76
  conflicts: { state: string; event: string; rules: Outcome[] }[];
77
};
78

79
export const key = (s: string, e: string) => `${s}\u0000${e}`;
80
const split = (raw: string) =>
81
  raw
82
    .split(",")
83
    .map((x) => x.trim())
84
    .filter(Boolean);
85
const quote = (s: string) => `"${s}"`;
86
const and = (xs: string[]) => (xs.length < 2 ? (xs[0] ?? "") : `${xs.slice(0, -1).join(", ")} and ${xs.at(-1)}`);
87

88
/** Read the text and resolve every cell. Throws InputError on a line it can't read, naming the line. */
89
export function parse(text: string): Machine {
90
  const states: string[] = [];
91
  const events: string[] = [];
92
  const blocks: Block[] = [];
93
  const rules: Rule[] = [];
94
  const addState = (s: string) => {
95
    if (!states.includes(s)) states.push(s);
96
  };
97
  const addEvent = (e: string) => {
98
    if (!events.includes(e)) events.push(e);
99
  };
100
  let block: Block | null = null;
101
  let offset = 0;
102

103
  for (const [n, raw] of text.split("\n").entries()) {
104
    const at = offset;
105
    const len = raw.length;
106
    offset += raw.length + 1;
107
    const line = n + 1;
108
    const hash = raw.indexOf("#");
109
    const body = (hash < 0 ? raw : raw.slice(0, hash)).trim();
110
    const reason = hash < 0 ? "" : raw.slice(hash + 1).trim();
111
    if (!body) continue;
112
    const fail = (msg: string): never => {
113
      throw new InputError(`Line ${line}: ${msg}`, at, len);
114
    };
115
    const name = (x: string, what: string) => {
116
      if (!NAME.test(x)) fail(`${quote(x)} isn't a ${what} name. Use letters, digits, _ . and -, with no spaces.`);
117
      return x;
118
    };
119

120
    const declared = /^events\s*:(.*)$/i.exec(body);
121
    if (declared) {
122
      for (const e of split(declared[1] ?? "")) addEvent(name(e, "event"));
123
      continue;
124
    }
125

126
    const arrow = /->|→|=>/.exec(body);
127
    if (arrow) {
128
      if (!block) fail(`${quote(body)} has no state above it. Start with a state and a colon, like "search:".`);
129
      const lhs = body.slice(0, arrow.index).trim();
130
      const rhs = body.slice(arrow.index + arrow[0].length).trim();
131
      if (!lhs) fail("there is no event before the arrow.");
132
      if (!rhs) fail("there is nothing after the arrow. Write a state, or stay, defer, reject, ignore or back.");
133
      if (/\s/.test(rhs))
134
        fail(`after the arrow comes one state, or stay, defer, reject, ignore or back, not ${quote(rhs)}.`);
135
      const word = rhs.toLowerCase();
136
      const outcome: Outcome = OUTCOMES.has(word)
137
        ? { kind: word as Kind, to: "", line, reason }
138
        : { kind: "move", to: name(rhs, "state"), line, reason };
139
      let evs: string[] | "else";
140
      if (/^(anything\s+else|\*)$/i.test(lhs)) evs = "else";
141
      else {
142
        evs = split(lhs).map((e) => name(e, "event"));
143
        evs.forEach(addEvent);
144
      }
145
      rules.push({ block: block as Block, events: evs, outcome });
146
      continue;
147
    }
148

149
    if (body.endsWith(":")) {
150
      const head = body.slice(0, -1).trim();
151
      const every = /^every\s+states?(?:\s+except\s+(.*))?$/i.exec(head);
152
      if (every) {
153
        const except = every[1] === undefined ? [] : split(every[1]);
154
        if (every[1] !== undefined && !except.length) fail('"except" needs the states to leave out.');
155
        for (const s of except) name(s, "state");
156
        block = { line, at, len, except };
157
      } else {
158
        const names = split(head);
159
        if (!names.length) fail("there is a colon with no state before it.");
160
        for (const s of names) {
161
          name(s, "state");
162
          if (RESERVED.has(s.toLowerCase())) fail(`${quote(s)} is a word this tool reads, so it can't be a state.`);
163
          addState(s);
164
        }
165
        block = { line, at, len, names };
166
      }
167
      blocks.push(block);
168
      continue;
169
    }
170

171
    fail(
172
      `${quote(body)} is neither a state nor a rule. A state ends with a colon, like "search:", and a rule has an arrow, like "slot_free -> confirm".`,
173
    );
174
  }
175

176
  if (!states.length)
177
    throw new InputError(
178
      "There are no states. Write one with a colon, then its rules beneath it:\ngather:\n  slots_complete -> search",
179
    );
180
  if (!events.length)
181
    throw new InputError('There are no events. Write a rule under a state, like "slots_complete -> search".');
182
  for (const b of blocks)
183
    if ("except" in b)
184
      for (const s of b.except)
185
        if (!states.includes(s))
186
          throw new InputError(`Line ${b.line}: ${quote(s)} isn't one of the states, ${and(states)}.`, b.at, b.len);
187

188
  const members = (b: Block) => ("names" in b ? b.names : states.filter((s) => !b.except.includes(s)));
189
  const ends: string[] = [];
190
  for (const r of rules) {
191
    const o = r.outcome;
192
    if (o.kind === "move" && !states.includes(o.to) && !ends.includes(o.to)) ends.push(o.to);
193
  }
194

195
  // Narrower wins: a named event beats "anything else", then the block covering fewer states, and a block that
196
  // names its states beats an "every state" block of the same size, because naming them is the narrower intent.
197
  const rank = (r: Rule) => (r.events === "else" ? 1e6 : 0) + members(r.block).length + ("names" in r.block ? 0 : 0.5);
198
  const effect = (o: Outcome, s: string) => (o.kind === "move" && o.to === s ? "stay" : `${o.kind} ${o.to}`);
199
  const cells = new Map<string, Outcome | null>();
200
  const conflicts: Machine["conflicts"] = [];
201
  for (const s of states) {
202
    for (const e of events) {
203
      const claim = rules.filter((r) => members(r.block).includes(s) && (r.events === "else" || r.events.includes(e)));
204
      if (!claim.length) {
205
        cells.set(key(s, e), null);
206
        continue;
207
      }
208
      const best = Math.min(...claim.map(rank));
209
      const top = claim.filter((r) => rank(r) === best).map((r) => r.outcome);
210
      if (new Set(top.map((o) => effect(o, s))).size > 1) {
211
        conflicts.push({ state: s, event: e, rules: top });
212
        cells.set(key(s, e), null);
213
        continue;
214
      }
215
      const o = top[0] as Outcome;
216
      cells.set(key(s, e), o.kind === "move" && o.to === s ? { ...o, kind: "stay", to: "" } : o);
217
    }
218
  }
219
  return { states, events, ends, start: states[0] as string, cells, conflicts };
220
}
221

222
/** States a run from the start can arrive in. `back` returns somewhere already reached, so it adds nothing. */
223
export function reachable(m: Machine): Set<string> {
224
  const seen = new Set([m.start]);
225
  const todo = [m.start];
226
  for (let s = todo.pop(); s !== undefined; s = todo.pop()) {
227
    for (const e of m.events) {
228
      const o = m.cells.get(key(s, e));
229
      if (o?.kind === "move" && m.states.includes(o.to) && !seen.has(o.to)) {
230
        seen.add(o.to);
231
        todo.push(o.to);
232
      }
233
    }
234
  }
235
  return seen;
236
}
237

238
/** States no event moves anywhere else: once in, the machine stays. */
239
export function stuck(m: Machine): string[] {
240
  const leaves = (o: Outcome | null | undefined) => o?.kind === "move" || o?.kind === "back";
241
  return m.states.filter((s) => !m.events.some((e) => leaves(m.cells.get(key(s, e)))));
242
}
243

244
export const say = (o: Outcome) => (o.kind === "move" ? `-> ${o.to}` : o.kind);
245
const py = (s: string) => JSON.stringify(s);
246

247
export function skeleton(m: Machine): string {
248
  const disputed = new Map(m.conflicts.map((c) => [key(c.state, c.event), c]));
249
  const rows: string[] = [];
250
  for (const s of m.states) {
251
    for (const e of m.events) {
252
      const o = m.cells.get(key(s, e));
253
      const c = disputed.get(key(s, e));
254
      const expected = o ? py(o.kind === "move" ? o.to : o.kind) : "None";
255
      const note = c ? `two answers, lines ${and(c.rules.map((r) => String(r.line)))}` : o ? o.reason : "undecided";
256
      rows.push(`    (${py(s)}, ${py(e)}, ${expected}),${note ? `  # ${note}` : ""}`);
257
    }
258
  }
259
  return [
260
    "import pytest",
261
    "",
262
    "# One case per cell: (state, event, what should happen). A state's name is a move; stay, defer,",
263
    "# reject and ignore keep the machine where it is; back returns to the state it came from.",
264
    "# None is a cell with no rule yet, so its test fails until one is written.",
265
    "CELLS = [",
266
    ...rows,
267
    "]",
268
    "",
269
    "",
270
    "def deliver(state, event):",
271
    '    """Put your machine in `state`, deliver `event`, and return the new state or the outcome word."""',
272
    "    raise NotImplementedError",
273
    "",
274
    "",
275
    '@pytest.mark.parametrize("state, event, expected", CELLS, ids=[f"{s}-{e}" for s, e, _ in CELLS])',
276
    "def test_cell(state, event, expected):",
277
    "    if expected is None:",
278
    '        pytest.fail(f"no rule says what {event} does in {state}")',
279
    "    assert deliver(state, event) == expected",
280
    "",
281
  ].join("\n");
282
}
283

284
const plural = (n: number, one: string, many = `${one}s`) => `${n} ${n === 1 ? one : many}`;
285

286
/**
287
 * The shape, in one value: a conflict first, because it is a bug, then the states that can't be reached or left.
288
 * Null when there is nothing to say, so the coverage line does not gain a "None" field.
289
 */
290
function shape(m: Machine, unreachable: string[], noExit: string[]): Field | null {
291
  const c0 = m.conflicts[0];
292
  if (c0)
293
    return {
294
      label: "Conflicts",
295
      value: `${plural(m.conflicts.length, "cell")} with two answers`,
296
      note: `${c0.state} on ${c0.event}: lines ${and(c0.rules.map((r) => String(r.line)))} say different things.`,
297
      tone: "bad",
298
    };
299
  if (unreachable.length || noExit.length) {
300
    const same = unreachable.length === noExit.length && unreachable.every((s) => noExit.includes(s));
301
    const value = same
302
      ? `${and(unreachable)} can't be reached or left`
303
      : [
304
          ...(unreachable.length ? [`${and(unreachable)} can't be reached`] : []),
305
          ...(noExit.length ? [`${and(noExit)} can't be left`] : []),
306
        ].join(", and ");
307
    return { label: "Shape", value, mono: false };
308
  }
309
  return null;
310
}
311

312
/**
313
 * The happy path, as the author wrote it: from the start, take each state's first-written move to somewhere not yet
314
 * visited, until an end or a state with nowhere new to go. First-written rather than shortest, because a shortcut
315
 * such as `committed -> report` is an exception path, and the drawing a person starts from lists the happy path first.
316
 */
317
export function mainPath(m: Machine): string[] {
318
  const path = [m.start];
319
  for (let s: string | undefined = m.start; s && m.states.includes(s); ) {
320
    const here: string = s;
321
    const next = m.events
322
      .map((e) => m.cells.get(key(here, e)))
323
      .filter((o): o is Outcome => o?.kind === "move" && !path.includes(o.to))
324
      .sort((a, b) => a.line - b.line)[0];
325
    s = next?.to;
326
    if (s) path.push(s);
327
  }
328
  return path;
329
}
330

331
/** Up to three event names, then a count, so a label stays one short line. */
332
const few = (es: string[]) => (es.length > 3 ? `${es.slice(0, 2).join(", ")} and ${es.length - 2} more` : and(es));
333

334
/**
335
 * The machine as states and arrows, one arrow per pair of states, labelled with the events that take it.
336
 *
337
 * Only moves are drawn. A `stay` (and defer, reject, ignore) leaves the state where it is, so as a self-loop it would
338
 * put a loop on almost every node of a finished machine, 22 of them in the booking, and say nothing the grid doesn't.
339
 * A `back` is dashed, to each state that moves into it, because that is where it can return to.
340
 */
341
export function graph(m: Machine, unreachable: string[], noExit: string[]): Output {
342
  const path = mainPath(m);
343
  const nodes: GraphNode[] = [
344
    ...m.states.map((s): GraphNode => {
345
      const lost = unreachable.includes(s);
346
      const stuckHere = noExit.includes(s);
347
      const note =
348
        lost && stuckHere ? "can't be reached or left" : lost ? "can't be reached" : stuckHere ? "no way out" : "";
349
      return {
350
        id: s,
351
        ...(note ? { note, tone: "warn" as const } : {}),
352
        ...(s === m.start ? { badge: "start" } : {}),
353
        ...(path.includes(s) ? { rank: path.indexOf(s) } : {}),
354
      };
355
    }),
356
    ...m.ends.map(
357
      (s): GraphNode => ({
358
        id: s,
359
        shape: "pill",
360
        note: "end",
361
        ...(path.includes(s) ? { rank: path.indexOf(s) } : {}),
362
      }),
363
    ),
364
  ];
365
  const moves = new Map<string, { from: string; to: string; events: string[]; back: boolean }>();
366
  const add = (from: string, to: string, e: string, back: boolean) => {
367
    const k = `${key(from, to)}\u0000${back}`;
368
    const edge = moves.get(k) ?? { from, to, events: [], back };
369
    edge.events.push(e);
370
    moves.set(k, edge);
371
  };
372
  for (const s of m.states)
373
    for (const e of m.events) {
374
      const o = m.cells.get(key(s, e));
375
      if (o?.kind === "move") add(s, o.to, e, false);
376
    }
377
  for (const s of m.states)
378
    for (const e of m.events) {
379
      if (m.cells.get(key(s, e))?.kind !== "back") continue;
380
      const from = m.states.filter((p) => p !== s && m.events.some((x) => m.cells.get(key(p, x))?.to === s));
381
      for (const p of from) add(s, p, e, true);
382
    }
383
  const edges = [...moves.values()].map(
384
    (x): GraphEdge => ({
385
      from: x.from,
386
      to: x.to,
387
      label: x.back ? `${few(x.events)}, back` : few(x.events),
388
      ...(x.back ? { line: "dashed" as const } : {}),
389
    }),
390
  );
391
  return {
392
    kind: "graph",
393
    graph: {
394
      label: `The machine's moves, from ${m.start}`,
395
      layout: "layered",
396
      direction: "LR",
397
      nodes,
398
      edges,
399
      ...(path.length > 1 ? { highlight: path } : {}),
400
    },
401
  };
402
}
403

404
export default {
405
  run(input: Input) {
406
    try {
407
      const m = parse(String(input.machine ?? ""));
408
      const all = [...m.cells.values()];
409
      const decided = all.filter((o): o is Outcome => o !== null);
410
      const open = all.length - decided.length;
411
      const reach = reachable(m);
412
      const unreachable = m.states.filter((s) => !reach.has(s));
413
      const noExit = stuck(m);
414

415
      const count = (k: Kind) => decided.filter((o) => o.kind === k || (k === "move" && o.kind === "back")).length;
416
      const kinds = (["move", "stay", "defer", "ignore", "reject"] as const)
417
        .map((k) => [k, count(k)] as const)
418
        .filter(([, n]) => n > 0)
419
        .map(([k, n]) => plural(n, k));
420
      /*
421
       * ⚠️ One coverage line comes first, and it is what a card shows. It replaced a "Biggest gap" headline that
422
       * forced four tied event names into one sentence, and three tiles that were one fraction.
423
       */
424
      const gap = shape(m, unreachable, noExit);
425
      const coverage: Output = {
426
        kind: "fields",
427
        role: "answer",
428
        fields: [
429
          {
430
            label: "Decided",
431
            value: `${decided.length} of ${all.length} pairs`,
432
            note: `${plural(m.states.length, "state")} x ${plural(m.events.length, "event")}${kinds.length ? `: ${and(kinds)}` : ""}. It starts at ${m.start}${m.ends.length ? ` and ends at ${and(m.ends)}` : ""}.`,
433
          },
434
          {
435
            label: "Undecided",
436
            value: String(open),
437
            note: open ? "Marked ? in the table, most open events first." : "Every pair has an answer.",
438
          },
439
          ...(gap ? [gap] : []),
440
        ],
441
      };
442

443
      const disputed = new Map(m.conflicts.map((c) => [key(c.state, c.event), c.rules.length]));
444
      const cell = (s: string, e: string) => mark(m.cells.get(key(s, e)) ?? null, disputed.get(key(s, e)));
445
      // A pasted table loses the grid's legend-at-a-glance and often its caption, so a reject keeps its word there.
446
      const word = (s: string, e: string) => (m.cells.get(key(s, e))?.kind === "reject" ? "✕ reject" : cell(s, e).text);
447
      /*
448
       * The least-decided events on top, ties in the order written, so the rows to work on are the first a reader
449
       * sees, and a finished machine keeps its written order. `matrix` so it scrolls on a phone rather than
450
       * stacking into one card per event.
451
       */
452
      const openIn = (e: string) => m.states.filter((s) => !m.cells.get(key(s, e))).length;
453
      const byOpen = m.events
454
        .map((e, i) => ({ e, i, n: openIn(e) }))
455
        .sort((x, y) => y.n - x.n || x.i - y.i)
456
        .map((x) => x.e);
457
      const grid: Output = {
458
        kind: "table",
459
        role: "matrix",
460
        caption: LEGEND,
461
        columns: [
462
          { label: "Event", wrap: "none", rowHeader: true },
463
          ...m.states.map((s) => ({ label: s, mono: true, wrap: "none" as const })),
464
        ],
465
        rows: byOpen.map((e): Cell[] => [{ text: e, mono: true }, ...m.states.map((s) => cell(s, e))]),
466
      };
467

468
      const said = (o: Outcome) => `line ${o.line} says ${say(o)}${o.reason ? ` (${o.reason})` : ""}`;
469
      const gaps = [
470
        ...m.conflicts.map((c) => ({
471
          gap: "Two answers",
472
          tone: "bad" as const,
473
          where: `${c.state} on ${c.event}`,
474
          why: `${c.rules.map(said).join("; ").replace(/^l/, "L")}.`,
475
        })),
476
        ...unreachable.map((s) => ({
477
          gap: "Can't be reached",
478
          tone: "warn" as const,
479
          where: s,
480
          why: `Nothing leads here from ${m.start}, the start.`,
481
        })),
482
        ...noExit.map((s) => ({
483
          gap: "No way out",
484
          tone: "warn" as const,
485
          where: s,
486
          why: "No event moves it to another state.",
487
        })),
488
      ];
489
      const parts: Output[] = [coverage, grid, graph(m, unreachable, noExit)];
490
      if (gaps.length)
491
        parts.push({
492
          kind: "table",
493
          caption: "Gaps",
494
          columns: [
495
            { label: "Gap", wrap: "none" },
496
            { label: "Where", mono: true, wrap: "none" },
497
            { label: "Why", wrap: "prose" },
498
          ],
499
          rows: gaps.map((g): Cell[] => [{ text: g.gap, tone: g.tone }, { text: g.where, mono: true }, g.why]),
500
        });
501
      if (input.also.includes("markdown")) {
502
        const row = (cells: string[]) => `| ${cells.join(" | ")} |`;
503
        const md = [
504
          `${all.length} cells: ${decided.length} decided, ${open} undecided.`,
505
          "",
506
          row(["Event", ...m.states]),
507
          row(["---", ...m.states.map(() => "---")]),
508
          ...byOpen.map((e) => row([e, ...m.states.map((s) => word(s, e))])),
509
          "",
510
          LEGEND,
511
          ...(gaps.length ? ["", "Gaps:", "", ...gaps.map((g) => `- ${g.gap}: ${g.where}. ${g.why}`)] : []),
512
          "",
513
        ];
514
        parts.push({ kind: "code", lang: "markdown", source: md.join("\n") });
515
      }
516
      if (input.also.includes("pytest")) parts.push({ kind: "code", lang: "python", source: skeleton(m) });
517
      return { kind: "group", parts };
518
    } catch (error) {
519
      if (error instanceof InputError)
520
        return {
521
          kind: "error",
522
          message: error.message,
523
          input: "machine",
524
          ...(error.at !== undefined ? { at: error.at } : {}),
525
          ...(error.len !== undefined ? { len: error.len } : {}),
526
        };
527
      throw error;
528
    }
529
  },
530
} satisfies Tool<Input>;