cs-mermaid

1// ABOUTME: cs-mermaid mod: draws each mermaid flowchart fence in a reply inline, as coloured blocks and line glyphs.
2// ABOUTME: One /config row (`cs-mermaid.drawDiagrams`, on by default) controls the drawing; CLAUDE.local.md carries the diagram instruction.
3import type { EngineInterface, Register } from 'claude-code'
4
5import { layout } from './layout'
6import type { Layout } from './layout'
7import { parse } from './parse'
8import type { Graph, GraphNode, ParseError } from './parse'
9import { cellWidth, padToWidth, truncateToWidth } from './text'
10
11// The /config row (`cs-mermaid.drawDiagrams`): off, fences stay source.
12export const OPTION = 'drawDiagrams'
13
14// A mermaid fence opens and closes on its own line with exactly three backticks. A line of four
15// or more backticks, or of three tildes, opens an outer block that quotes what it holds, closed by
16// a line of the same mark at least as long; a fence inside one is quoted source, not a chart.
17type Fence = { start: number; end: number; body: string }
18export function scanFences(text: string): Fence[] {
19  const fences: Fence[] = []
20  let outer: { mark: string; length: number } | undefined
21  let open: { start: number; bodyStart: number } | undefined
22  let at = 0
23  for (const line of text.split('\n')) {
24    const next = at + line.length + 1
25    const trimmed = line.trim()
26    const run = /^(`{3,}|~{3,})/.exec(trimmed)
27    if (run) {
28      const mark = run[1]!
29      if (outer) {
30        if (mark[0] === outer.mark && mark.length >= outer.length && trimmed === mark) outer = undefined
31      } else if (open) {
32        if (trimmed === '```') {
33          fences.push({ start: open.start, end: at + line.length, body: text.slice(open.bodyStart, Math.max(open.bodyStart, at - 1)) })
34          open = undefined
35        }
36      } else if (mark === '```' && trimmed.slice(3).trim() === 'mermaid') {
37        // The newline before the fence belongs to it, not to the prose above.
38        open = { start: Math.max(0, at - 1), bodyStart: next }
39      } else if (mark.length > 3 || mark[0] === '~') {
40        outer = { mark: mark[0]!, length: mark.length }
41      }
42    }
43    at = next
44  }
45  return fences
46}
47
48export function fencesOf(text: string): string[] {
49  return scanFences(text).map(fence => fence.body.trim()).filter(Boolean)
50}
51
52export type Fitted = { drawn: Layout; graph: Graph; turned: boolean } | { error: string }
53
54// A left-to-right chart wider than the transcript is turned top-down; a chart still too wide, or one
55// the engine refuses, is reported so the reply shows the source instead of a clipped drawing.
56export function fit(graph: Graph, columns: number): Fitted {
57  const first = layout(graph)
58  if ('error' in first) return first
59  if (first.width <= columns) return { drawn: first, graph, turned: false }
60  if (graph.dir === 'LR' || graph.dir === 'RL') {
61    const turned = layout({ ...graph, dir: graph.dir === 'LR' ? 'TD' : 'BT' })
62    if ('error' in turned) return turned
63    if (turned.width <= columns) return { drawn: turned, graph, turned: true }
64    return { error: `diagram is ${turned.width} columns wide, the transcript ${columns}` }
65  }
66  return { error: `diagram is ${first.width} columns wide, the transcript ${columns}` }
67}
68
69// Nodes are solid blocks: three rows of background colour with the label on the middle row.
70// Mermaid's default theme fills every node #ECECFF; here a node's role in the flow gives it a
71// hue, so a chart of plain `[ ]` boxes still reads as a flow: a decision (diamond or hexagon,
72// or any node that branches) amber, a start (a circle, or a node nothing leads to) green, an
73// end (a node that leads nowhere) grey. A `style` or `classDef` fill wins over all of it.
74type Palette = { fill: string; decision: string; start: string; end: string; text: string; line: string; good: string; bad: string }
75const LIGHT: Palette = { fill: '#ECECFF', decision: '#FFF3BF', start: '#D3F9D8', end: '#E9ECEF', text: '#1F1F1F', line: '#333333', good: '#2B8A3E', bad: '#C92A2A' }
76const DARK: Palette = { fill: '#3B3F6B', decision: '#6B5A1E', start: '#1F4D2B', end: '#3A3D42', text: '#F2F2F2', line: '#D3D3D3', good: '#69DB7C', bad: '#FF8787' }
77
78export function paletteFor(theme: unknown): Palette {
79  return typeof theme === 'string' && theme.startsWith('dark') ? DARK : LIGHT
80}
81
82export type Role = 'step' | 'decision' | 'start' | 'end'
83
84// A node's role, by its shape first and else by its place in the flow. A lone node is a step.
85export function roleOf(node: GraphNode, graph: Graph): Role {
86  if (node.shape === 'diamond' || node.shape === 'hexagon') return 'decision'
87  const outgoing = graph.edges.filter(edge => edge.from === node.id).length
88  const incoming = graph.edges.filter(edge => edge.to === node.id).length
89  // A circle is a terminal: the end when the flow only arrives at it, else the start.
90  if (node.shape === 'circle' || node.shape === 'doublecircle') return outgoing === 0 && incoming > 0 ? 'end' : 'start'
91  if (outgoing >= 2) return 'decision'
92  if (outgoing === 0 && incoming > 0) return 'end'
93  if (incoming === 0 && outgoing > 0) return 'start'
94  return 'step'
95}
96
97export function fillFor(role: Role, palette: Palette): string {
98  return role === 'step' ? palette.fill : palette[role]
99}
100
101// An edge label that answers a decision takes the answer's colour; any other label the line's.
102const GOOD = new Set(['yes', 'y', 'ok', 'pass', 'passed', 'true', 'healthy', 'success', 'done', 'valid'])
103const BAD = new Set(['no', 'n', 'fail', 'failed', 'false', 'error', 'degraded', 'invalid', 'timeout', 'reject', 'rejected'])
104export function labelColor(text: string, palette: Palette): string {
105  const word = text.trim().toLowerCase()
106  if (GOOD.has(word)) return palette.good
107  if (BAD.has(word)) return palette.bad
108  return palette.line
109}
110
111// The rows of a block `width` cells wide and `height` tall, the label centred on the middle row.
112export function blockRows(label: string, width: number, height: number): string[] {
113  const blank = ' '.repeat(width)
114  const inner = truncateToWidth(label, width)
115  const left = Math.floor((width - cellWidth(inner)) / 2)
116  const middle = padToWidth(' '.repeat(left) + inner, width)
117  return Array.from({ length: height }, (_, i) => (i === Math.floor(height / 2) ? middle : blank))
118}
119
120type Elements = ReturnType<EngineInterface['ui']['resolve']>
121
122// The diagram as coloured blocks and line glyphs.
123export function Drawing({ drawn, graph, palette, elements }: { drawn: Layout; graph: Graph; palette: Palette; elements: Elements }) {
124  const { Box, Text } = elements
125  return (
126    <Box width={drawn.width} height={drawn.height} position="relative">
127      {drawn.runs.map(run => (
128        <Box position="absolute" top={run.y} left={run.x}><Text color={palette.line}>{run.text}</Text></Box>
129      ))}
130      {drawn.boxes.map(box => {
131        const role = roleOf(box.node, graph)
132        const fill = box.node.style?.fill ?? fillFor(role, palette)
133        const text = box.node.style?.color ?? palette.text
134        return (
135          <Box position="absolute" top={box.y} left={box.x} width={box.width} height={box.height} flexDirection="column">
136            {blockRows(box.node.label, box.width, box.height).map(row => (
137              <Text color={text} backgroundColor={fill} bold={role === 'decision'}>{row}</Text>
138            ))}
139          </Box>
140        )
141      })}
142      {drawn.labels.map(label => (
143        <Box position="absolute" top={label.y} left={label.x}><Text italic color={labelColor(label.text, palette)}>{label.text}</Text></Box>
144      ))}
145    </Box>
146  )
147}
148
149// A fence the drawing cannot take: its source as it was written, the reason under it.
150export function drawFence(source: string, error: string, elements: Elements) {
151  const { Box, Text, Code } = elements
152  return (
153    <Box flexDirection="column">
154      <Code source={source} language="mermaid" />
155      <Text dimColor>mermaid: {error}</Text>
156    </Box>
157  )
158}
159
160// A reply's text split into prose and mermaid fences, in order.
161export function splitReply(text: string): { kind: 'text' | 'mermaid'; body: string }[] {
162  const parts: { kind: 'text' | 'mermaid'; body: string }[] = []
163  let last = 0
164  for (const fence of scanFences(text)) {
165    const before = text.slice(last, fence.start)
166    if (before.trim()) parts.push({ kind: 'text', body: before })
167    parts.push({ kind: 'mermaid', body: fence.body.trim() })
168    last = fence.end
169  }
170  const after = text.slice(last)
171  if (after.trim()) parts.push({ kind: 'text', body: after })
172  return parts
173}
174
175// A reply re-renders on every streaming flush and every width change, and a
176// chart near the limits takes over a second to lay out: keep the recent answers.
177const FITTED_KEPT = 32
178const fittedCache = new Map<string, Fitted | ParseError>()
179
180export function fitSource(source: string, columns: number): Fitted | ParseError {
181  const key = `${columns}\n${source}`
182  const known = fittedCache.get(key)
183  if (known) return known
184  const graph = parse(source)
185  const fitted = 'error' in graph ? graph : fit(graph, columns)
186  fittedCache.set(key, fitted)
187  if (fittedCache.size > FITTED_KEPT) fittedCache.delete(fittedCache.keys().next().value as string)
188  return fitted
189}
190
191export const register: Register = (on, options) => {
192  if (options[OPTION] === false) return
193
194  // The prose around a fence goes back to the engine, so the reply keeps its bullet.
195  on('ui.render', { component: 'AssistantMessage' }, async ($, e, next) => {
196    if (e.surface !== 'terminal') return next(e)
197    if (fencesOf(e.props.text).length === 0) return next(e)
198    // Draw each fence inline, in the room the terminal has; one that does not fit stays a fence.
199    const elements = $.ui.resolve(e)
200    const { Box } = elements
201    const theme = (await $.config.list()).find(row => row.key === 'theme')?.value
202    const palette = paletteFor(theme)
203    const columns = Math.max(20, (e.viewport?.columns ?? 80) - 6)
204    const parts = splitReply(e.props.text)
205    // The engine draws the prose, the opening bullet on the reply's first part only.
206    const prose = await Promise.all(parts.map((part, index) => part.kind === 'text'
207      ? next({ ...e, props: { ...e.props, text: part.body, isFirstOfReply: e.props.isFirstOfReply && index === 0 } })
208      : undefined))
209    return (
210      <Box flexDirection="column">
211        {parts.map((part, index) => {
212          if (part.kind === 'text') return prose[index]
213          const fitted = fitSource(part.body, columns)
214          if ('error' in fitted) return drawFence(part.body, fitted.error, elements)
215          return <Box marginY={1}><Drawing drawn={fitted.drawn} graph={fitted.graph} palette={palette} elements={elements} /></Box>
216        })}
217      </Box>
218    )
219  })
220}
221

1// ABOUTME: Layered layout of a parsed flowchart: back edges reversed, longest-path layers, crossing-reduction sweeps, per-edge ports.
2// ABOUTME: Answers placed blocks, line runs and edge labels in character cells, or the reason a chart cannot be drawn; toText renders one for tests.
3import type { Graph, GraphEdge, GraphNode, LineStyle } from './parse'
4import { cellWidth, truncateToWidth } from './text'
5
6export type Placed = { node: GraphNode; x: number; y: number; width: number; height: number }
7export type Run = { x: number; y: number; text: string }
8export type Label = { x: number; y: number; text: string }
9export type Layout = { width: number; height: number; boxes: Placed[]; runs: Run[]; labels: Label[] }
10export type LayoutError = { error: string }
11
12const MARGIN = 1
13const MAX_CELLS = 200_000
14
15// Items are real nodes or the dummy vertices a long edge is split into, one per layer it crosses.
16type Item = {
17  key: string
18  node?: GraphNode
19  layer: number
20  order: number
21  along: number // size on the layer axis (TD: height)
22  cross: number // size on the cross axis (TD: width)
23  a0: number
24  c0: number
25}
26// One edge piece between adjacent layers.
27type Segment = { edge: GraphEdge; from: Item; to: Item; exit: number; entry: number; first: boolean; last: boolean }
28
29export function layout(graph: Graph): Layout | LayoutError {
30  const flip = graph.dir === 'LR' || graph.dir === 'RL'
31  const items = new Map<string, Item>()
32  for (const node of graph.nodes) {
33    const [along, cross] = flip ? [cellWidth(node.label) + 4, 3] : [3, cellWidth(node.label) + 4]
34    items.set(node.id, { key: node.id, node, layer: 0, order: 0, along, cross, a0: 0, c0: 0 })
35  }
36
37  // Layering: back edges found by an iterative depth-first walk are reversed for layout.
38  const outgoing = new Map<string, GraphEdge[]>()
39  for (const edge of graph.edges) (outgoing.get(edge.from) ?? outgoing.set(edge.from, []).get(edge.from)!).push(edge)
40  const reversed = new Set<number>()
41  {
42    const state = new Map<string, 'open' | 'done'>()
43    for (const root of graph.nodes) {
44      if (state.has(root.id)) continue
45      const stack: { id: string; next: number }[] = [{ id: root.id, next: 0 }]
46      state.set(root.id, 'open')
47      while (stack.length > 0) {
48        const top = stack[stack.length - 1]!
49        const edges = outgoing.get(top.id) ?? []
50        if (top.next >= edges.length) {
51          state.set(top.id, 'done')
52          stack.pop()
53          continue
54        }
55        const edge = edges[top.next++]!
56        const seen = state.get(edge.to)
57        if (edge.to === edge.from || seen === 'open') reversed.add(edge.id)
58        else if (seen === undefined) {
59          state.set(edge.to, 'open')
60          stack.push({ id: edge.to, next: 0 })
61        }
62      }
63    }
64  }
65  const tailOf = (edge: GraphEdge) => (reversed.has(edge.id) ? edge.to : edge.from)
66  const headOf = (edge: GraphEdge) => (reversed.has(edge.id) ? edge.from : edge.to)
67  const forward = graph.edges.filter(edge => edge.from !== edge.to)
68  {
69    // Longest path from a source, in topological order (Kahn).
70    const indegree = new Map<string, number>()
71    const children = new Map<string, string[]>()
72    for (const node of graph.nodes) indegree.set(node.id, 0)
73    for (const edge of forward) {
74      indegree.set(headOf(edge), (indegree.get(headOf(edge)) ?? 0) + 1)
75      ;(children.get(tailOf(edge)) ?? children.set(tailOf(edge), []).get(tailOf(edge))!).push(headOf(edge))
76    }
77    const queue = graph.nodes.filter(node => indegree.get(node.id) === 0).map(node => node.id)
78    while (queue.length > 0) {
79      const id = queue.shift()!
80      const layer = items.get(id)!.layer
81      for (const child of children.get(id) ?? []) {
82        const item = items.get(child)!
83        item.layer = Math.max(item.layer, layer + 1)
84        indegree.set(child, (indegree.get(child) ?? 1) - 1)
85        if (indegree.get(child) === 0) queue.push(child)
86      }
87    }
88  }
89
90  // Dummy vertices: a long edge becomes a chain of segments between adjacent layers.
91  const segments: Segment[] = []
92  const chains = new Map<number, Segment[]>()
93  for (const edge of forward) {
94    const tail = items.get(tailOf(edge))!
95    const head = items.get(headOf(edge))!
96    const chain: Segment[] = []
97    let previous = tail
98    for (let layer = tail.layer + 1; layer < head.layer; layer++) {
99      const dummy: Item = { key: `#${edge.id}@${layer}`, layer, order: 0, along: 1, cross: 1, a0: 0, c0: 0 }
100      items.set(dummy.key, dummy)
101      chain.push({ edge, from: previous, to: dummy, exit: 0, entry: 0, first: false, last: false })
102      previous = dummy
103    }
104    chain.push({ edge, from: previous, to: head, exit: 0, entry: 0, first: false, last: false })
105    chain[0]!.first = true
106    chain[chain.length - 1]!.last = true
107    chains.set(edge.id, chain)
108    segments.push(...chain)
109  }
110
111  const layers: Item[][] = []
112  for (const item of items.values()) (layers[item.layer] ??= []).push(item)
113  for (let i = 0; i < layers.length; i++) layers[i] ??= []
114  orderLayers(layers, segments)
115
116  // Cross positions: real nodes widen for their ports, and in TD for the label that sits
117  // beside a straight exit; layers are centred on the widest.
118  const crossGap = flip ? 1 : 3
119  const labelOf = (s: Segment) => (s.first && s.edge.label ? cellWidth(s.edge.label) : 0)
120  // A labelled exit: the port, a gap, the label, and a cell of air before the next port's line.
121  const exitSpan = (s: Segment) => (!flip && labelOf(s) > 0 ? labelOf(s) + 4 : 2)
122  for (const item of items.values()) {
123    if (!item.node) continue
124    const exits = segments.filter(s => s.from === item)
125    const entries = segments.filter(s => s.to === item).length
126    // n ports two cells apart need 2n+1 cells; a labelled exit needs its label's room after it.
127    const exitRoom = exits.reduce((sum, s) => sum + exitSpan(s), 0) + 1
128    item.cross = Math.max(item.cross, entries * 2 + 1, exitRoom)
129  }
130  const totals = layers.map(layer => layer.reduce((sum, item) => sum + item.cross, 0) + crossGap * Math.max(0, layer.length - 1))
131  const maxTotal = Math.max(0, ...totals)
132  layers.forEach((layer, i) => {
133    let c = MARGIN + Math.floor((maxTotal - (totals[i] ?? 0)) / 2)
134    for (const item of layer) {
135      item.c0 = c
136      c += item.cross + crossGap
137    }
138  })
139
140  // Ports: each segment leaves and enters at its own column, spread across the node and
141  // ordered by the far end so segments do not cross on the way out.
142  for (const item of items.values()) {
143    const centre = (other: Item) => other.c0 + Math.floor(other.cross / 2)
144    const exits = segments.filter(s => s.from === item).sort((p, q) => centre(p.to) - centre(q.to))
145    const entries = segments.filter(s => s.to === item).sort((p, q) => centre(p.from) - centre(q.from))
146    entries.forEach((s, i) => (s.entry = portAt(item, i, entries.length)))
147    if (!item.node || exits.every(s => exitSpan(s) === 2)) {
148      exits.forEach((s, i) => (s.exit = portAt(item, i, exits.length)))
149      continue
150    }
151    // Labelled exits: each port is followed by the room its label needs.
152    const used = exits.reduce((sum, s) => sum + exitSpan(s), 0) - 2
153    let c = item.c0 + 1 + Math.floor((item.cross - 2 - used) / 2)
154    for (const s of exits) {
155      s.exit = c
156      c += exitSpan(s)
157    }
158  }
159  // Ends one cell apart run straight: rounding, not meaning, put them apart.
160  for (const s of segments) {
161    if (Math.abs(s.exit - s.entry) !== 1) continue
162    const siblings = segments.filter(o => o !== s && o.to.layer === s.to.layer)
163    // Never snap onto, or right beside, another line in the same gap.
164    const clear = (c: number) => !siblings.some(o => Math.abs(o.exit - c) <= 1 || Math.abs(o.entry - c) <= 1)
165    if (clear(s.entry) && s.entry > s.from.c0 && s.entry < s.from.c0 + s.from.cross - 1) s.exit = s.entry
166    else if (clear(s.exit) && s.exit > s.to.c0 && s.exit < s.to.c0 + s.to.cross - 1) s.entry = s.exit
167  }
168  // Two different segments sharing a column in one gap would overlap: nudge the entry.
169  for (let gap = 1; gap < layers.length; gap++) {
170    const inGap = segments.filter(s => s.to.layer === gap)
171    const used = new Set<number>()
172    for (const s of inGap) used.add(s.exit)
173    for (const s of inGap) {
174      if (s.from.node && s.to.node && s.exit === s.entry) continue
175      const taken = new Set([...used].filter(c => inGap.some(o => o !== s && (o.exit === c || o.entry === c))))
176      let entry = s.entry
177      // Whole steps of two first, so a moved entry stays clear of its neighbours.
178      for (const delta of [0, 2, -2, 1, -1]) {
179        const candidate = s.entry + delta
180        if (candidate > s.to.c0 && candidate < s.to.c0 + s.to.cross - 1 && !taken.has(candidate)) {
181          entry = candidate
182          break
183        }
184      }
185      s.entry = entry
186      used.add(entry)
187    }
188  }
189
190  // Bus rows per gap for segments that move across; overlapping spans take different rows.
191  const busOf = new Map<Segment, number>()
192  const busCount: number[] = []
193  for (let gap = 1; gap < layers.length; gap++) {
194    const movers = segments.filter(s => s.to.layer === gap && s.exit !== s.entry).sort((p, q) => Math.min(p.exit, p.entry) - Math.min(q.exit, q.entry))
195    const rowEnds: number[] = []
196    for (const s of movers) {
197      const lo = Math.min(s.exit, s.entry)
198      const hi = Math.max(s.exit, s.entry)
199      let row = rowEnds.findIndex(end => end + 2 <= lo)
200      if (row < 0) row = rowEnds.push(-Infinity) - 1
201      rowEnds[row] = hi
202      busOf.set(s, row)
203    }
204    busCount[gap] = rowEnds.length
205  }
206
207  // Along positions: every layer is as tall as its tallest item. A gap holds its buses at its
208  // far end and, in LR, room near its start for the labels that run along the edge.
209  const gapStart: number[] = []
210  const gapSize: number[] = []
211  let a = MARGIN
212  layers.forEach((layer, i) => {
213    gapStart[i] = a
214    if (i > 0) {
215      const labelRoom = flip ? Math.max(0, ...segments.filter(s => s.to.layer === i && labelOf(s) > 0).map(s => labelOf(s) + 2)) : 0
216      gapSize[i] = Math.max(2, 2 + (busCount[i] ?? 0), labelRoom + (busCount[i] ?? 0) + 1)
217      a += gapSize[i]!
218    }
219    const along = Math.max(1, ...layer.map(item => item.along))
220    for (const item of layer) {
221      item.a0 = a
222      item.along = along
223    }
224    a += along
225  })
226  const busRow = (s: Segment, bus: number) => (gapStart[s.to.layer] ?? 0) + (gapSize[s.to.layer] ?? 2) - 2 - bus
227
228  const grid = new Grid()
229  // A dummy vertex is the edge passing through its layer: draw it as a straight piece.
230  for (const item of items.values()) {
231    if (item.node) continue
232    const edgeId = Number(item.key.slice(1).split('@')[0])
233    const style = graph.edges[edgeId]?.style ?? 'solid'
234    grid.along(edgeId, item.c0, item.a0, item.a0 + item.along - 1, style)
235  }
236  for (const s of segments) {
237    const start = s.from.a0 + s.from.along
238    const end = s.to.a0 - 1
239    const bus = busOf.get(s)
240    if (bus === undefined) grid.along(s.edge.id, s.exit, start, end, s.edge.style)
241    else {
242      const row = busRow(s, bus)
243      grid.along(s.edge.id, s.exit, start, row, s.edge.style)
244      grid.cross(s.edge.id, row, s.exit, s.entry, s.edge.style)
245      grid.along(s.edge.id, s.entry, row, end, s.edge.style)
246    }
247    // Heads: the drawn direction of a reversed edge runs opposite to the written one.
248    const flipped = reversed.has(s.edge.id)
249    const headAtDrawnEnd = flipped ? s.edge.headAtFrom : s.edge.headAtTo
250    const headAtDrawnStart = flipped ? s.edge.headAtTo : s.edge.headAtFrom
251    if (s.last && headAtDrawnEnd) grid.arrow(s.edge.id, s.entry, end, 'end')
252    if (s.first && headAtDrawnStart) grid.arrow(s.edge.id, s.exit, start, 'start')
253  }
254
255  const width0 = Math.max(...[...items.values()].map(item => item.c0 + item.cross), 0) + 2
256  const boxes: Placed[] = []
257  const blocked = new Occupancy()
258  for (const item of items.values()) {
259    if (!item.node) continue
260    blocked.add(item.a0, item.c0, item.along, item.cross)
261    const { x, y } = point(flip, item.a0, item.c0)
262    boxes.push({ node: item.node, x, y, width: flip ? item.along : item.cross, height: flip ? item.cross : item.along })
263  }
264
265  // Labels: a rectangle beside the first segment that covers no node, no other edge and no
266  // other label; the edge's own cells beneath it are erased. Truncated when nothing fits.
267  const labels: Label[] = []
268  for (const edge of graph.edges) {
269    if (!edge.label) continue
270    const chain = chains.get(edge.id)
271    const s = chain?.[0]
272    if (!s) continue
273    const start = s.from.a0 + s.from.along
274    const bus = busOf.get(s)
275    const row = bus === undefined ? start : busRow(s, bus)
276    const text = edge.label
277    const placed = placeLabel(grid, blocked, labels, flip, edge.id, text, s, row, width0)
278    labels.push(placed)
279    blocked.add(flip ? placed.x : placed.y, flip ? placed.y : placed.x, flip ? cellWidth(placed.text) : 1, flip ? 1 : cellWidth(placed.text))
280  }
281
282  let runs = grid.runs(flip)
283  const width = Math.max(...boxes.map(b => b.x + b.width), ...runs.map(r => r.x + cellWidth(r.text)), ...labels.map(l => l.x + cellWidth(l.text)), 0) + MARGIN
284  const height = Math.max(...boxes.map(b => b.y + b.height), ...runs.map(r => r.y + 1), ...labels.map(l => l.y + 1), 0) + MARGIN
285  if (width * height > MAX_CELLS) return { error: `diagram would be ${width}x${height} cells` }
286
287  if (graph.dir === 'BT' || graph.dir === 'RL') {
288    const mirrorY = graph.dir === 'BT'
289    for (const box of boxes) {
290      if (mirrorY) box.y = height - box.y - box.height
291      else box.x = width - box.x - box.width
292    }
293    for (const label of labels) {
294      if (mirrorY) label.y = height - 1 - label.y
295      else label.x = width - label.x - cellWidth(label.text)
296    }
297    runs = runs.map(run => {
298      if (mirrorY) return { x: run.x, y: height - 1 - run.y, text: [...run.text].map(mirrorGlyphY).join('') }
299      return { x: width - run.x - run.text.length, y: run.y, text: [...run.text].reverse().map(mirrorGlyphX).join('') }
300    })
301  }
302  return { width, height, boxes, runs, labels }
303}
304
305function point(flip: boolean, along: number, cross: number): { x: number; y: number } {
306  return flip ? { x: along, y: cross } : { x: cross, y: along }
307}
308
309// The i-th of n ports across an item: dummies have one column; a node's ports sit two cells
310// apart, the group centred inside its edges.
311function portAt(item: Item, i: number, n: number): number {
312  if (!item.node) return item.c0
313  const inner = item.cross - 2
314  const start = item.c0 + 1 + Math.floor((inner - (2 * n - 1)) / 2)
315  return start + 2 * i
316}
317
318// Several starting orders, each refined by barycenter sweeps and transposes; fewest crossings wins.
319function orderLayers(layers: Item[][], segments: Segment[]): void {
320  const starts: Item[][][] = [
321    layers.map(layer => [...layer]),
322    layers.map(layer => [...layer].reverse()),
323    layers.map(layer => [...layer].sort((p, q) => segments.filter(s => s.from === q || s.to === q).length - segments.filter(s => s.from === p || s.to === p).length)),
324  ]
325  let best = Infinity
326  let bestOrder = starts[0]!
327  for (const start of starts) {
328    start.forEach((layer, i) => (layers[i] = layer))
329    const count = refineOrder(layers, segments)
330    if (count < best) {
331      best = count
332      bestOrder = layers.map(layer => [...layer])
333    }
334    if (best === 0) break
335  }
336  bestOrder.forEach((layer, i) => {
337    layers[i] = layer
338    layer.forEach((item, j) => (item.order = j))
339  })
340}
341
342// Crossing counts are the cost of ordering: each is a pass over every pair of segments in a
343// gap, and the transposes and permutations below ask for thousands. Past this many pairs the
344// order stands as it is, so a chart at the parser's limits draws in a second or two
345// instead of holding the render hook for tens of seconds; a small chart never reaches it.
346const ORDERING_BUDGET = 4_000_000
347
348function refineOrder(layers: Item[][], segments: Segment[]): number {
349  layers.forEach(layer => layer.forEach((item, i) => (item.order = i)))
350  let work = 0
351  const exhausted = () => work > ORDERING_BUDGET
352  const up = new Map<Item, Item[]>()
353  const down = new Map<Item, Item[]>()
354  for (const s of segments) {
355    ;(down.get(s.from) ?? down.set(s.from, []).get(s.from)!).push(s.to)
356    ;(up.get(s.to) ?? up.set(s.to, []).get(s.to)!).push(s.from)
357  }
358  const sweep = (layer: Item[], neighbours: Map<Item, Item[]>) => {
359    const score = new Map<Item, number>()
360    for (const item of layer) {
361      const near = neighbours.get(item) ?? []
362      score.set(item, near.length === 0 ? item.order : near.reduce((sum, n) => sum + n.order, 0) / near.length)
363    }
364    layer.sort((p, q) => (score.get(p) ?? 0) - (score.get(q) ?? 0) || p.order - q.order)
365    layer.forEach((item, i) => (item.order = i))
366  }
367  const crossings = () => {
368    let count = 0
369    for (let i = 1; i < layers.length; i++) {
370      const between = segments.filter(s => s.to.layer === i)
371      work += (between.length * (between.length - 1)) / 2
372      for (let p = 0; p < between.length; p++) for (let q = p + 1; q < between.length; q++) {
373        const a = between[p]!, b = between[q]!
374        if ((a.from.order - b.from.order) * (a.to.order - b.to.order) < 0) count++
375      }
376    }
377    return count
378  }
379  let best = crossings()
380  let bestOrder = layers.map(layer => [...layer])
381  for (let pass = 0; pass < 4 && best > 0 && !exhausted(); pass++) {
382    if (pass % 2 === 0) for (let i = 1; i < layers.length; i++) sweep(layers[i]!, up)
383    else for (let i = layers.length - 2; i >= 0; i--) sweep(layers[i]!, down)
384    const now = crossings()
385    if (now < best) {
386      best = now
387      bestOrder = layers.map(layer => [...layer])
388    }
389  }
390  bestOrder.forEach((layer, i) => {
391    layers[i] = layer
392    layer.forEach((item, j) => (item.order = j))
393  })
394  // Transpose: swap neighbours while that removes crossings.
395  for (let round = 0; round < 10 && best > 0 && !exhausted(); round++) {
396    let improved = false
397    for (const layer of layers) {
398      for (let i = 0; i + 1 < layer.length && !exhausted(); i++) {
399        const p = layer[i]!, q = layer[i + 1]!
400        ;[layer[i], layer[i + 1]] = [q, p]
401        p.order = i + 1
402        q.order = i
403        const now = crossings()
404        if (now < best) {
405          best = now
406          improved = true
407        } else {
408          ;[layer[i], layer[i + 1]] = [p, q]
409          p.order = i
410          q.order = i + 1
411        }
412      }
413    }
414    if (!improved) break
415  }
416  // A small chart: every combination of layer orders, since one layer at a time can stall.
417  const factorial = (n: number): number => (n <= 1 ? 1 : n * factorial(n - 1))
418  const combinations = layers.reduce((product, layer) => product * factorial(layer.length), 1)
419  if (best > 0 && combinations <= 5000 && !exhausted()) {
420    const search = (index: number) => {
421      if (index === layers.length) {
422        const now = crossings()
423        if (now < best) {
424          best = now
425          bestOrder = layers.map(layer => [...layer])
426        }
427        return
428      }
429      const layer = layers[index]!
430      for (const perm of permutations([...layer])) {
431        layer.splice(0, layer.length, ...perm)
432        layer.forEach((item, i) => (item.order = i))
433        search(index + 1)
434        if (best === 0) return
435      }
436    }
437    bestOrder = layers.map(layer => [...layer])
438    search(0)
439    bestOrder.forEach((layer, i) => {
440      layers[i] = layer
441      layer.forEach((item, j) => (item.order = j))
442    })
443    return best
444  }
445  // Small layers: try every order of one layer with the others fixed, until nothing improves.
446  for (let round = 0; round < 6 && best > 0 && !exhausted(); round++) {
447    let improved = false
448    for (const layer of layers) {
449      if (layer.length < 2 || layer.length > 6 || exhausted()) continue
450      const current = [...layer]
451      let bestPerm = current
452      for (const perm of permutations(current)) {
453        perm.forEach((item, i) => (item.order = i))
454        const now = crossings()
455        if (now < best) {
456          best = now
457          bestPerm = [...perm]
458          improved = true
459        }
460      }
461      layer.splice(0, layer.length, ...bestPerm)
462      layer.forEach((item, i) => (item.order = i))
463    }
464    if (!improved) break
465  }
466  return best
467}
468
469function* permutations<T>(list: T[]): Generator<T[]> {
470  if (list.length <= 1) {
471    yield [...list]
472    return
473  }
474  for (let i = 0; i < list.length; i++) {
475    const rest = [...list.slice(0, i), ...list.slice(i + 1)]
476    for (const tail of permutations(rest)) yield [list[i]!, ...tail]
477  }
478}
479
480class Occupancy {
481  private cells = new Set<string>()
482  add(a0: number, c0: number, along: number, cross: number) {
483    for (let a = a0; a < a0 + along; a++) for (let c = c0; c < c0 + cross; c++) this.cells.add(`${a},${c}`)
484  }
485  has(a: number, c: number): boolean {
486    return this.cells.has(`${a},${c}`)
487  }
488}
489
490function placeLabel(grid: Grid, blocked: Occupancy, labels: Label[], flip: boolean, edgeId: number, text: string, s: Segment, row: number, width: number): Label {
491  const free = (a: number, c: number, len: number) => {
492    for (let i = 0; i < len; i++) {
493      if (blocked.has(a, c + i)) return false
494      if (grid.ownedByOther(edgeId, a, c + i)) return false
495    }
496    return true
497  }
498  // In TD the label is a row of cells across the cross axis; in LR it must still read left to
499  // right, so it occupies one cross position and runs along the layer axis.
500  const len = cellWidth(text)
501  const start = s.from.a0 + s.from.along
502  const straight = s.exit === s.entry
503  const candidates: { a: number; c: number }[] = flip
504    ? [
505        { a: start, c: s.exit - 1 },
506        { a: start, c: s.exit + 1 },
507        { a: s.to.a0 - 1 - len, c: s.entry - 1 },
508      ]
509    : straight
510      ? [
511          { a: start, c: s.exit + 2 },
512          { a: start, c: s.exit - 1 - len },
513        ]
514      : [
515          // Beside the exit's own vertical run first: the corner and the head stay drawn.
516          { a: start, c: s.exit + 2 },
517          { a: start, c: s.exit - 1 - len },
518          { a: row, c: Math.min(s.exit, s.entry) + 2 },
519        ]
520  for (const at of candidates) {
521    if (flip) {
522      if (at.c < 0) continue
523      const ok = Array.from({ length: len }, (_, i) => !blocked.has(at.a + i, at.c) && !grid.ownedByOther(edgeId, at.a + i, at.c)).every(Boolean)
524      if (!ok) continue
525      for (let i = 0; i < len; i++) grid.erase(at.a + i, at.c)
526      const { x, y } = point(true, at.a, at.c)
527      return { x, y, text }
528    }
529    if (at.c < 1 || at.c + len > width + 20) continue
530    if (!free(at.a, at.c, len)) continue
531    if (labels.some(l => l.y === at.a && l.x < at.c + len && l.x + cellWidth(l.text) > at.c)) continue
532    for (let i = 0; i < len; i++) grid.erase(at.a, at.c + i)
533    return { x: at.c, y: at.a, text }
534  }
535  // Nothing fits whole: take the first candidate and cut the text to the room there.
536  const at = candidates[0]!
537  let room = 0
538  while (room < len && (flip ? !blocked.has(at.a + room, at.c) && !grid.ownedByOther(edgeId, at.a + room, at.c) : !blocked.has(at.a, at.c + room) && !grid.ownedByOther(edgeId, at.a, at.c + room))) room++
539  const cut = truncateToWidth(text, Math.max(1, room))
540  for (let i = 0; i < cellWidth(cut); i++) flip ? grid.erase(at.a + i, at.c) : grid.erase(at.a, at.c + i)
541  const { x, y } = point(flip, at.a, at.c)
542  return { x, y, text: cut }
543}
544
545const UP = 1, DOWN = 2, LEFT = 4, RIGHT = 8
546type Cell = { owner: number; mask: number; style: LineStyle; crossing: boolean; arrow?: 'end' | 'start' }
547
548class Grid {
549  private cells = new Map<string, Cell>()
550
551  private mark(owner: number, a: number, c: number, bit: number, style: LineStyle) {
552    const key = `${a},${c}`
553    const cell = this.cells.get(key)
554    if (!cell) {
555      this.cells.set(key, { owner, mask: bit, style, crossing: false })
556      return
557    }
558    if (cell.owner !== owner) cell.crossing = true
559    cell.mask |= bit
560  }
561
562  along(owner: number, c: number, a0: number, a1: number, style: LineStyle) {
563    const [lo, hi] = a0 <= a1 ? [a0, a1] : [a1, a0]
564    for (let a = lo; a <= hi; a++) {
565      if (a < hi) this.mark(owner, a, c, DOWN, style)
566      if (a > lo) this.mark(owner, a, c, UP, style)
567    }
568    if (lo === hi) this.mark(owner, lo, c, UP | DOWN, style)
569  }
570
571  cross(owner: number, a: number, c0: number, c1: number, style: LineStyle) {
572    const [lo, hi] = c0 <= c1 ? [c0, c1] : [c1, c0]
573    for (let c = lo; c <= hi; c++) {
574      if (c < hi) this.mark(owner, a, c, RIGHT, style)
575      if (c > lo) this.mark(owner, a, c, LEFT, style)
576    }
577  }
578
579  arrow(owner: number, c: number, a: number, at: 'end' | 'start') {
580    const key = `${a},${c}`
581    const cell = this.cells.get(key) ?? { owner, mask: UP | DOWN, style: 'solid' as const, crossing: false }
582    cell.arrow = at
583    this.cells.set(key, cell)
584  }
585
586  erase(a: number, c: number) {
587    this.cells.delete(`${a},${c}`)
588  }
589
590  ownedByOther(owner: number, a: number, c: number): boolean {
591    const cell = this.cells.get(`${a},${c}`)
592    return cell !== undefined && (cell.owner !== owner || cell.crossing)
593  }
594
595  runs(flip: boolean): Run[] {
596    const byRow = new Map<number, { x: number; glyph: string }[]>()
597    for (const [key, cell] of this.cells) {
598      const [a, c] = key.split(',').map(Number) as [number, number]
599      const x = flip ? a : c
600      const y = flip ? c : a
601      ;(byRow.get(y) ?? byRow.set(y, []).get(y)!).push({ x, glyph: glyphOf(cell, flip) })
602    }
603    const runs: Run[] = []
604    for (const [y, cells] of byRow) {
605      cells.sort((p, q) => p.x - q.x)
606      let run: Run | undefined
607      for (const cell of cells) {
608        if (run && run.x + run.text.length === cell.x) run.text += cell.glyph
609        else runs.push((run = { x: cell.x, y, text: cell.glyph }))
610      }
611    }
612    return runs.sort((p, q) => p.y - q.y || p.x - q.x)
613  }
614}
615
616function glyphOf(cell: Cell, flip: boolean): string {
617  if (cell.arrow === 'end') return flip ? '►' : '▼'
618  if (cell.arrow === 'start') return flip ? '◄' : '▲'
619  // Two edges through one cell: always a crossing, never a junction, since no two edges share a port.
620  if (cell.crossing) return '┼'
621  let mask = cell.mask
622  if (flip) mask = (cell.mask & UP ? LEFT : 0) | (cell.mask & DOWN ? RIGHT : 0) | (cell.mask & LEFT ? UP : 0) | (cell.mask & RIGHT ? DOWN : 0)
623  const vertical = (mask & (UP | DOWN)) !== 0 && (mask & (LEFT | RIGHT)) === 0
624  const horizontal = (mask & (LEFT | RIGHT)) !== 0 && (mask & (UP | DOWN)) === 0
625  if (vertical) return cell.style === 'dotted' ? '┆' : cell.style === 'thick' ? '┃' : '│'
626  if (horizontal) return cell.style === 'dotted' ? '┄' : cell.style === 'thick' ? '━' : '─'
627  const table: Record<number, string> = {
628    [DOWN | RIGHT]: '┌', [DOWN | LEFT]: '┐', [UP | RIGHT]: '└', [UP | LEFT]: '┘',
629    [UP | DOWN | RIGHT]: '├', [UP | DOWN | LEFT]: '┤', [LEFT | RIGHT | DOWN]: '┬', [LEFT | RIGHT | UP]: '┴',
630  }
631  return table[mask] ?? '┼'
632}
633
634const MIRROR_Y: Record<string, string> = { '┌': '└', '└': '┌', '┐': '┘', '┘': '┐', '┬': '┴', '┴': '┬', '▼': '▲', '▲': '▼' }
635const MIRROR_X: Record<string, string> = { '┌': '┐', '┐': '┌', '└': '┘', '┘': '└', '├': '┤', '┤': '├', '►': '◄', '◄': '►' }
636function mirrorGlyphY(glyph: string): string {
637  return MIRROR_Y[glyph] ?? glyph
638}
639function mirrorGlyphX(glyph: string): string {
640  return MIRROR_X[glyph] ?? glyph
641}
642
643// The drawing as lines of text: what a test or a preview compares against.
644export function toText(drawn: Layout): string {
645  const grid = Array.from({ length: drawn.height }, () => Array<string>(drawn.width).fill(' '))
646  const put = (x: number, y: number, text: string) => {
647    for (let i = 0; i < text.length; i++) if (grid[y] && x + i < drawn.width) grid[y]![x + i] = text[i]!
648  }
649  for (const run of drawn.runs) put(run.x, run.y, run.text)
650  for (const box of drawn.boxes) {
651    for (let y = box.y; y < box.y + box.height; y++) put(box.x, y, '█'.repeat(box.width))
652    const mid = box.y + Math.floor(box.height / 2)
653    const inner = truncateToWidth(box.node.label, box.width - 2)
654    put(box.x + 1 + Math.floor((box.width - 2 - cellWidth(inner)) / 2), mid, inner)
655  }
656  for (const label of drawn.labels) put(label.x, label.y, label.text)
657  return grid.map(row => row.join('').replace(/\s+$/, '')).join('\n')
658}
659

1// ABOUTME: Parses a mermaid flowchart (graph/flowchart TD TB BT LR RL) into nodes, edges and styles.
2// ABOUTME: Any statement outside the supported subset refuses the whole chart with the reason; there are no partial graphs.
3import { cellWidth } from './text'
4
5export type Dir = 'TD' | 'BT' | 'LR' | 'RL'
6export type Shape = 'rect' | 'round' | 'stadium' | 'subroutine' | 'cylinder' | 'circle' | 'doublecircle' | 'diamond' | 'hexagon' | 'flag' | 'parallelogram' | 'trapezoid'
7export type LineStyle = 'solid' | 'dotted' | 'thick'
8// Blocks have no border, so `stroke:` is accepted and ignored; `fill:` and `color:` are kept.
9export type NodeStyle = { fill?: string; color?: string }
10
11export type GraphNode = { id: string; label: string; shape: Shape; style?: NodeStyle }
12export type Arrow = { style: LineStyle; headAtTo: boolean; headAtFrom: boolean; label?: string }
13export type GraphEdge = { id: number; from: string; to: string } & Arrow
14export type Graph = { dir: Dir; nodes: GraphNode[]; edges: GraphEdge[] }
15export type ParseError = { error: string }
16
17export const LIMITS = { nodes: 200, edges: 400, label: 60 }
18
19// Each shape by its opening and closing delimiters, longest openers first so `([` wins over `(`.
20const SHAPES: { open: string; close: string; shape: Shape }[] = ([
21  { open: '([', close: '])', shape: 'stadium' },
22  { open: '[[', close: ']]', shape: 'subroutine' },
23  { open: '[(', close: ')]', shape: 'cylinder' },
24  { open: '((', close: '))', shape: 'circle' },
25  { open: '(((', close: ')))', shape: 'doublecircle' },
26  { open: '{{', close: '}}', shape: 'hexagon' },
27  { open: '[/', close: '/]', shape: 'parallelogram' },
28  { open: '[\\', close: '\\]', shape: 'parallelogram' },
29  { open: '[/', close: '\\]', shape: 'trapezoid' },
30  { open: '[\\', close: '/]', shape: 'trapezoid' },
31  { open: '[', close: ']', shape: 'rect' },
32  { open: '(', close: ')', shape: 'round' },
33  { open: '{', close: '}', shape: 'diamond' },
34  { open: '>', close: ']', shape: 'flag' },
35] as { open: string; close: string; shape: Shape }[]).sort((p, q) => q.open.length - p.open.length)
36
37// A node id; `-` and `.` join two word runs (`my-node`, `v1.2`) but never start an arrow (`A-->B`, `A-.->B`).
38const ID_SOURCE = '[A-Za-z0-9_]+(?:[.-][A-Za-z0-9_]+)*'
39const ID = new RegExp(`^${ID_SOURCE}`)
40const IDS_SOURCE = `${ID_SOURCE}(?:,${ID_SOURCE})*`
41// An arrow: optional head at the source, the shaft, optional head at the target.
42// With no head, the shaft must not run on into one (`--o`, `-->`); after a head the target may
43// begin with anything, `o` and `x` included.
44const ARROW = /^(<)?(-{2,}|={2,}|-\.+-)(?:(>|o|x)|(?![-=.>ox]))/
45
46export function parse(source: string): Graph | ParseError {
47  const statements = splitStatements(source)
48  const first = statements.shift()
49  if (first === undefined) return { error: 'empty diagram' }
50  // No direction is mermaid's default, top-down.
51  const header = /^(?:graph|flowchart)(?:\s+(TD|TB|BT|LR|RL))?$/.exec(first)
52  if (!header) return { error: `not a flowchart: "${first.slice(0, 40)}"` }
53  const dir: Dir = header[1] === undefined || header[1] === 'TB' ? 'TD' : (header[1] as Dir)
54
55  const nodes = new Map<string, GraphNode>()
56  const edges: GraphEdge[] = []
57  const classes = new Map<string, NodeStyle>()
58  const classOf = new Map<string, string>()
59  const styled = new Map<string, NodeStyle>()
60
61  for (const statement of statements) {
62    let match: RegExpExecArray | null
63    if (/^(subgraph\b|end$)/.test(statement)) return { error: 'subgraphs are not supported' }
64    if (/^(linkStyle|click|direction)\b/.test(statement)) continue
65    if ((match = new RegExp(`^classDef\\s+(${IDS_SOURCE})\\s+(.+)$`).exec(statement))) {
66      for (const name of (match[1] ?? '').split(',')) classes.set(name, readStyle(match[2] ?? ''))
67      continue
68    }
69    if ((match = new RegExp(`^class\\s+(${IDS_SOURCE})\\s+(${ID_SOURCE})$`).exec(statement))) {
70      for (const id of (match[1] ?? '').split(',')) classOf.set(id, match[2] ?? '')
71      continue
72    }
73    if ((match = new RegExp(`^style\\s+(${ID_SOURCE})\\s+(.+)$`).exec(statement))) {
74      styled.set(match[1] ?? '', readStyle(match[2] ?? ''))
75      continue
76    }
77    const failure = readChain(statement, nodes, edges, classOf)
78    if (failure) return { error: failure }
79    if (nodes.size > LIMITS.nodes) return { error: `more than ${LIMITS.nodes} nodes` }
80    if (edges.length > LIMITS.edges) return { error: `more than ${LIMITS.edges} edges` }
81  }
82  if (nodes.size === 0) return { error: 'no nodes' }
83
84  const fallback = classes.get('default')
85  for (const node of nodes.values()) {
86    const named = classOf.get(node.id)
87    const style = { ...(named ? classes.get(named) : fallback), ...styled.get(node.id) }
88    if (Object.keys(style).length > 0) node.style = style
89  }
90  return { dir, nodes: [...nodes.values()], edges }
91}
92
93// Statements end at a newline or a `;` outside quotes and brackets; `%%` comments are dropped.
94export function splitStatements(source: string): string[] {
95  const out: string[] = []
96  let current = ''
97  let quote = false
98  let depth = 0
99  const lines = source.split('\n')
100  for (const rawLine of lines) {
101    const line = rawLine.trim()
102    if (line.startsWith('%%')) continue
103    for (let i = 0; i < line.length; i++) {
104      const ch = line[i] ?? ''
105      if (!quote && ch === '%' && line[i + 1] === '%') break
106      if (ch === '"') quote = !quote
107      else if (!quote && (ch === '[' || ch === '(' || ch === '{')) depth++
108      else if (!quote && (ch === ']' || ch === ')' || ch === '}')) depth = Math.max(0, depth - 1)
109      if (ch === ';' && !quote && depth === 0) {
110        if (current.trim()) out.push(current.trim())
111        current = ''
112        continue
113      }
114      current += ch
115    }
116    if (current.trim()) out.push(current.trim())
117    current = ''
118    quote = false
119    depth = 0
120  }
121  return out
122}
123
124// `A & B -->|x| C --> D`: node groups joined by arrows. Anything left unread is an error.
125function readChain(statement: string, nodes: Map<string, GraphNode>, edges: GraphEdge[], classOf: Map<string, string>): string | undefined {
126  let rest = statement
127  let previous: string[] | undefined
128  let arrow: Arrow | undefined
129  for (;;) {
130    const group: string[] = []
131    for (;;) {
132      const read = readNode(rest, nodes, classOf)
133      if ('error' in read) return read.error
134      group.push(read.id)
135      rest = read.rest.trimStart()
136      if (!rest.startsWith('&')) break
137      rest = rest.slice(1).trimStart()
138    }
139    if (previous && arrow) {
140      for (const from of previous) {
141        for (const to of group) {
142          if (from === to) return `self-loops are not supported ("${from}")`
143          edges.push({ id: edges.length, from, to, ...arrow })
144        }
145      }
146    }
147    previous = group
148    if (rest === '') return undefined
149    const next = readArrow(rest)
150    if ('error' in next) return next.error
151    arrow = next.arrow
152    rest = next.rest.trimStart()
153    if (rest === '') return `dangling arrow in "${statement}"`
154  }
155}
156
157function readArrow(text: string): { arrow: Arrow; rest: string } | ParseError {
158  // `-- text -->`, `== text ==>`, `-. text .->`
159  const inline = /^(<)?(--|==|-\.)\s+([^-=.|][^|]*?)\s+(--|==|\.-)(?:(>|o|x)|(?![-=.>ox]))/.exec(text)
160  let head: RegExpExecArray | null = null
161  let label: string | undefined
162  let rest: string
163  let shaft: string
164  if (inline) {
165    label = unquote(inline[3] ?? '')
166    shaft = inline[2] ?? '--'
167    head = inline
168    rest = text.slice(inline[0].length)
169  } else {
170    const plain = ARROW.exec(text)
171    if (!plain) return { error: `expected an arrow at "${text.slice(0, 20)}"` }
172    shaft = plain[2] ?? '--'
173    head = plain
174    rest = text.slice(plain[0].length)
175    const piped = /^\s*\|("[^"]*"|[^|]*)\|/.exec(rest)
176    if (piped) {
177      label = unquote(piped[1] ?? '')
178      rest = rest.slice(piped[0].length)
179    }
180  }
181  const tail = inline ? inline[5] : head[3]
182  if (tail === 'o' || tail === 'x') return { error: `"${tail}" arrow ends are not supported` }
183  if (label !== undefined && cellWidth(label) > LIMITS.label) return { error: `edge label longer than ${LIMITS.label} cells` }
184  const style: LineStyle = shaft.startsWith('=') ? 'thick' : shaft.includes('.') ? 'dotted' : 'solid'
185  return { arrow: { style, headAtTo: tail === '>', headAtFrom: head[1] === '<', label: label || undefined }, rest }
186}
187
188function readNode(text: string, nodes: Map<string, GraphNode>, classOf: Map<string, string>): { id: string; rest: string } | ParseError {
189  const idMatch = ID.exec(text)
190  if (!idMatch) return { error: `expected a node at "${text.slice(0, 20)}"` }
191  const id = idMatch[0]
192  let rest = text.slice(id.length)
193  let label: string | undefined
194  let shape: Shape = 'rect'
195  const opener = SHAPES.find(one => rest.startsWith(one.open))
196  if (opener) {
197    const candidates = SHAPES.filter(one => one.open === opener.open)
198    const body = readDelimited(rest, opener.open, candidates.map(one => one.close))
199    if ('error' in body) return body
200    label = body.text
201    shape = candidates.find(one => one.close === body.close)?.shape ?? opener.shape
202    rest = body.rest
203  }
204  const inlineClass = new RegExp(`^:::(${ID_SOURCE})`).exec(rest)
205  if (inlineClass) {
206    classOf.set(id, inlineClass[1] ?? '')
207    rest = rest.slice(inlineClass[0].length)
208  }
209  if (label !== undefined) {
210    const clean = label.trim().replace(/^"(.*)"$/s, '$1').replace(/<br\s*\/?>/gi, ' ').trim()
211    if (cellWidth(clean) > LIMITS.label) return { error: `node label longer than ${LIMITS.label} cells` }
212    nodes.set(id, { id, label: clean || id, shape })
213  } else if (!nodes.has(id)) {
214    nodes.set(id, { id, label: id, shape: 'rect' })
215  }
216  return { id, rest }
217}
218
219// The text between `open` and the first matching closer, quotes respected, the shortest closer tried last.
220function readDelimited(text: string, open: string, closers: string[]): { text: string; close: string; rest: string } | ParseError {
221  let quote = false
222  const sorted = [...closers].sort((p, q) => q.length - p.length)
223  for (let i = open.length; i < text.length; i++) {
224    const ch = text[i]
225    if (ch === '"') {
226      quote = !quote
227      continue
228    }
229    if (quote) continue
230    for (const close of sorted) {
231      if (text.startsWith(close, i)) return { text: text.slice(open.length, i), close, rest: text.slice(i + close.length) }
232    }
233  }
234  return { error: `unclosed "${open}" in "${text.slice(0, 20)}"` }
235}
236
237// An edge label without the quotes that let it hold arrows or pipes.
238function unquote(label: string): string {
239  return label.trim().replace(/^"(.*)"$/s, '$1').trim()
240}
241
242// `fill:#f9f,color:rgb(1,2,3)`: pairs split on commas outside parentheses.
243function readStyle(text: string): NodeStyle {
244  const style: NodeStyle = {}
245  for (const part of text.split(/,(?![^()]*\))/)) {
246    const [key, value] = part.split(':').map(piece => piece.trim())
247    if (!value) continue
248    if (key === 'fill') style.fill = value
249    else if (key === 'color') style.color = value
250  }
251  return style
252}
253

1// ABOUTME: Terminal text measurement for the mermaid drawing: wide CJK and emoji count two cells, combining marks none.
2// ABOUTME: Pads and truncates strings to a cell width.
3// Terminal text measurement: a cell count, not a UTF-16 length.
4
5const WIDE = /[ᄀ-ᅟ⺀-〾ぁ-㏿㐀-䶿一-鿿ꀀ-꓏가-힣豈-﫿︰-﹏＀-｠￠-￦]|[\u{1F300}-\u{1F64F}]|[\u{1F900}-\u{1F9FF}]|[\u{20000}-\u{3FFFD}]/u
6const ZERO = /^[\p{M}​-‏️]+$/u
7
8export function graphemes(text: string): string[] {
9  const Segmenter = (Intl as { Segmenter?: new (locale: string, options: { granularity: 'grapheme' }) => { segment(input: string): Iterable<{ segment: string }> } }).Segmenter
10  if (!Segmenter) return Array.from(text)
11  return Array.from(new Segmenter('en', { granularity: 'grapheme' }).segment(text), piece => piece.segment)
12}
13
14function cellsOf(grapheme: string): number {
15  if (ZERO.test(grapheme)) return 0
16  const base = grapheme.replace(/[\p{M}​-‏️]/gu, '')
17  return WIDE.test(base) ? 2 : 1
18}
19
20export function cellWidth(text: string): number {
21  let width = 0
22  for (const grapheme of graphemes(text)) width += cellsOf(grapheme)
23  return width
24}
25
26// The longest prefix at most `width` cells wide, ending in `…` when anything was cut.
27export function truncateToWidth(text: string, width: number): string {
28  if (cellWidth(text) <= width) return text
29  if (width <= 0) return ''
30  let out = ''
31  let used = 0
32  for (const grapheme of graphemes(text)) {
33    const cells = cellsOf(grapheme)
34    if (used + cells > width - 1) break
35    out += grapheme
36    used += cells
37  }
38  return out + '…'
39}
40
41export function padToWidth(text: string, width: number): string {
42  return text + ' '.repeat(Math.max(0, width - cellWidth(text)))
43}
44