mermaid

1import type { EngineInterface, Elements, Register, RenderElement, RenderInputOf, RenderNode } from 'claude-code'
2
3import { isSequence, kindOf, parseSequence } from './parse'
4import type { Sequence } from './parse'
5import { drawSequence } from './render'
6import type { Ink, Run } from './render'
7import { segmentsOf } from './segments'
8import type { Segment } from './segments'
9
10type AssistantRender = RenderInputOf<'AssistantMessage', 'terminal'>
11
12type Kit = Pick<Elements['terminal'], 'Box' | 'Text'>
13
14type Style = { dimColor?: boolean; bold?: boolean; italic?: boolean; backgroundColor?: string; color?: string }
15
16// six hues spread round the wheel, readable on dark and light themes; the n-th participant to send
17// a message takes PALETTE[n % length], and participants that never send stay uncoloured
18export const PALETTE = ['#5f87ff', '#ff8700', '#5fd75f', '#d75fd7', '#00d7d7', '#d7d700'] as const
19
20type Look = { colour: boolean; quiet: boolean; boxnote: boolean }
21
22// colour, quiet returns and boxed notes are on by default; MERMAID_STYLE=plain turns them all off
23async function readLook($: EngineInterface): Promise<Look> {
24  const value = (await $.env.get('MERMAID_STYLE').catch(() => undefined)) ?? ''
25  const isPlain = String(value).split(',').some(part => part.trim() === 'plain')
26  return { colour: !isPlain, quiet: !isPlain, boxnote: !isPlain }
27}
28
29const PAINTED: ReadonlySet<Ink> = new Set(['frame', 'name', 'line'])
30
31function runStyle(style: Styles, run: Run, chosen: Look): Style {
32  const base = { ...(run.shade ? style.shade : {}), ...(chosen.boxnote && run.ink === 'note' ? { italic: true } : style[run.ink]) }
33  const coloured = chosen.colour && run.lane !== undefined && run.lane >= 0 && PAINTED.has(run.ink) ? { color: PALETTE[run.lane % PALETTE.length] } : {}
34  const quiet = chosen.quiet && run.reply && run.ink === 'line' ? { dimColor: true } : {}
35  return { ...base, ...coloured, ...quiet }
36}
37
38export const TINT = { dark: '#303030', light: '#e4e4e4' } as const
39// `rect` blocks sit on a fainter background than notes, so a note inside one still stands out
40export const SHADE = { dark: '#262626', light: '#efefef' } as const
41
42const INDENT = 2
43
44type Styles = Record<Ink, Style> & { shade: Style }
45
46function styles(tint: string): Styles {
47  return {
48    shade: { backgroundColor: tint === TINT.light ? SHADE.light : SHADE.dark },
49    frame: { dimColor: true },
50    line: {},
51    name: { bold: true },
52    note: { italic: true, backgroundColor: tint },
53    block: { dimColor: true },
54    text: {},
55    number: { dimColor: true },
56  }
57}
58
59export const notDrawn = (kind: string) =>
60  kind === '' ? 'mermaid: no diagram type' : `mermaid: ${kind} not drawn yet, sequenceDiagram only`
61
62let tint: Promise<string> | undefined
63
64async function readTint($: EngineInterface): Promise<string> {
65  const rows = await $.config.list().catch(() => [])
66  const theme = rows.find(row => row.key === 'theme')?.value
67  return typeof theme === 'string' && /light/i.test(theme) ? TINT.light : TINT.dark
68}
69
70function row({ Box, Text }: Kit, style: Styles, chosen: Look, runs: Run[], key: string): RenderNode {
71  return (
72    <Box key={key} flexDirection="row">
73      {runs.map(run => (
74        <Text {...runStyle(style, run, chosen)}>
75          {run.text}
76        </Text>
77      ))}
78    </Box>
79  )
80}
81
82const isUnreadable = (sequence: Sequence) => sequence.participants.length === 0 || (sequence.unread ?? 0) > 0
83
84function problems({ Box, Text }: Kit, lines: string[], key: string): RenderNode {
85  return (
86    <Box key={key} flexDirection="column" paddingLeft={INDENT}>
87      {lines.map(line => (
88        <Text dimColor>{line}</Text>
89      ))}
90    </Box>
91  )
92}
93
94function diagram(kit: Kit, style: Styles, chosen: Look, sequence: Sequence, width: number, key: string): RenderNode {
95  const { Box, Text } = kit
96  const { rows, notes } = drawSequence(sequence, width, { boxedNotes: chosen.boxnote, labelsAbove: true })
97  return (
98    <Box key={key} flexDirection="column" paddingLeft={INDENT}>
99      {rows.map((runs, i) => row(kit, style, chosen, runs, `${key}-row-${i}`))}
100      {notes.length > 0 && <Text key={`${key}-gap`}> </Text>}
101      {notes.map(note => (
102        <Text dimColor>{note}</Text>
103      ))}
104      {sequence.problems.map(problem => (
105        <Text dimColor>{problem}</Text>
106      ))}
107    </Box>
108  )
109}
110
111function notice({ Box, Text }: Kit, kind: string, key: string): RenderNode {
112  return (
113    <Box key={key} paddingLeft={INDENT}>
114      <Text dimColor>{notDrawn(kind)}</Text>
115    </Box>
116  )
117}
118
119type Shown = { node: RenderNode; source?: undefined } | { source: string[] }
120
121function sequencePart($: EngineInterface, kit: Kit, style: Styles, chosen: Look, part: { source: string }, width: number, key: string): Shown {
122  try {
123    const sequence = parseSequence(part.source)
124    if (isUnreadable(sequence)) return { source: sequence.problems }
125    return { node: diagram(kit, style, chosen, sequence, width, key) }
126  } catch (error) {
127    const reason = error instanceof Error ? error.message : String(error)
128    $.ui.log(`mermaid could not draw a diagram: ${reason}`, { to: 'debug' })
129    return { source: [`mermaid: could not draw this diagram (${reason})`] }
130  }
131}
132
133async function drawParts($: EngineInterface, e: AssistantRender, next: (e: AssistantRender) => Promise<RenderElement>, parts: Segment[]): Promise<RenderElement> {
134  const kit = $.ui.resolve(e)
135  const style = styles(await (tint ??= readTint($)))
136  const chosen = await readLook($)
137  const width = (e.viewport?.columns ?? 80) - INDENT - 1
138  const drawn: RenderNode[] = []
139  let isFirst = e.props.isFirstOfReply
140  for (const [i, part] of parts.entries()) {
141    const key = `mermaid-part-${i}`
142    if (part.kind === 'text') {
143      const element = await next({ ...e, props: { ...e.props, text: part.text, isFirstOfReply: isFirst } })
144      isFirst = false
145      drawn.push(<kit.Box key={key}>{element}</kit.Box>)
146    } else if (part.kind === 'sequence') {
147      const shown = sequencePart($, kit, style, chosen, part, width, key)
148      if (shown.source) {
149        const source = await next({ ...e, props: { ...e.props, text: part.fence, isFirstOfReply: isFirst } })
150        isFirst = false
151        drawn.push(
152          <kit.Box key={key} flexDirection="column">
153            {source}
154            {problems(kit, shown.source, `${key}-problems`)}
155          </kit.Box>,
156        )
157      } else drawn.push(shown.node)
158    } else {
159      drawn.push(notice(kit, part.kind === 'other' ? part.type : '', key))
160    }
161  }
162  return (
163    <kit.Box flexDirection="column" rowGap={1}>
164      {drawn}
165    </kit.Box>
166  )
167}
168
169export const register: Register = on => {
170  on('ui.render', { component: 'AssistantMessage' }, async ($, e, next) => {
171    if (e.surface !== 'terminal' || e.props.isSummary) return next(e)
172    const parts = segmentsOf(e.props.text, source => (isSequence(source) ? 'sequence' : kindOf(source)))
173    if (!parts.some(part => part.kind === 'sequence' || part.kind === 'other')) return next(e)
174    try {
175      return await drawParts($, e as AssistantRender, next as (e: AssistantRender) => Promise<RenderElement>, parts)
176    } catch (error) {
177      $.ui.log(`mermaid could not draw a diagram: ${error instanceof Error ? error.message : String(error)}`, { to: 'debug' })
178      return next(e)
179    }
180  }).catch(($, e, next) => next(e))
181}
182

1import { fencesOf } from './segments'
2
3export type Arrow = 'filled' | 'open' | 'cross' | 'async' | 'both' | 'half'
4
5export type Participant = { id: string; label: string; kind: 'participant' | 'actor'; box?: number; shape?: string }
6
7export type Step =
8  | { kind: 'message'; from: string; to: string; text: string; isDashed: boolean; arrow: Arrow; number?: number }
9  | { kind: 'activate'; id: string; isOn: boolean }
10  | { kind: 'note'; over: string[]; side: 'left' | 'right' | 'over'; text: string }
11  | { kind: 'open'; keyword: string; text: string }
12  | { kind: 'branch'; keyword: string; text: string }
13  | { kind: 'close' }
14  | { kind: 'create'; id: string }
15  | { kind: 'destroy'; id: string }
16
17export type Sequence = {
18  title?: string
19  participants: Participant[]
20  steps: Step[]
21  problems: string[]
22  boxes: { label: string }[]
23  unread?: number
24}
25
26const ARROW = /<<-->>|<<->>|--\|\\|--\|\/|-\|\\|-\|\/|\/\|--|\\\|--|\/\|-|\\\|-|--\\\\|--\/\/|-\\\\|-\/\/|\/\/--|\\\\--|\/\/-|\\\\-|-->>|->>|--x|-x|--\)|-\)|-->|->/g
27const PARTICIPANT = /^(create\s+)?(participant|actor)\s+(.+?)(?:\s+as(?:\s+(.*))?)?$/i
28const NOTE = /^note\s+(left of|right of|over)\s+([^:]+?)\s*:\s*(.*)$/i
29const OPEN = /^(loop|alt|opt|par_over|par|critical|break|rect)\b\s*(.*)$/i
30const BRANCH = /^(else|and|option)\b\s*(.*)$/i
31const ACTIVATE = /^(activate|deactivate)\s+(.+)$/i
32const DESTROY = /^destroy\s+(.+)$/i
33const AUTONUMBER = /^autonumber\b\s*(.*)$/i
34const IGNORED = /^(links?\b|properties\b|details\b|acctitle\s*:|accdescr\s*:)/i
35const DESCRIPTION_BLOCK = /^accdescr\s*\{/i
36const WRAP = /^\s*(?:no)?wrap:/i
37const ENTITY = /#(\d+|[a-z][a-z0-9]*);/gi
38const ENTITY_MARK = '\u0000'
39const MAX_EXAMPLE = 30
40const BRANCH_OF: Record<string, string> = { else: 'alt', and: 'par', option: 'critical' }
41const BLOCK_LINE = /^(loop|alt|opt|par_over|par|critical|break|rect|else|and|option)\s/i
42// Mermaid's lexer reads these as keywords wherever an id could go; `title` and the acc* words only
43// at the start of a line, so they still work as a sender. Derived from the 11.16 parser.
44const SENDER_KEYWORDS = new Set(
45  (
46    'participant actor create destroy activate deactivate autonumber off over box loop alt opt par par_over critical ' +
47    'break rect else and option end note links link details properties sequencediagram'
48  ).split(' '),
49)
50const KEYWORDS = new Set([...SENDER_KEYWORDS, 'title', 'acctitle', 'accdescr'])
51const COLOUR_FUNCTION = /^\s*(rgba?|hsla?)\([^)]*\)\s*/i
52const COLOUR_HEX = /^\s*#[0-9a-f]{3,8}\b\s*/i
53const COLOURS = new Set(
54  (
55    'aliceblue antiquewhite aqua aquamarine azure beige bisque black blanchedalmond blue blueviolet brown burlywood cadetblue ' +
56    'chartreuse chocolate coral cornflowerblue cornsilk crimson cyan darkblue darkcyan darkgoldenrod darkgray darkgreen darkgrey ' +
57    'darkkhaki darkmagenta darkolivegreen darkorange darkorchid darkred darksalmon darkseagreen darkslateblue darkslategray ' +
58    'darkslategrey darkturquoise darkviolet deeppink deepskyblue dimgray dimgrey dodgerblue firebrick floralwhite forestgreen ' +
59    'fuchsia gainsboro ghostwhite gold goldenrod gray green greenyellow grey honeydew hotpink indianred indigo ivory khaki ' +
60    'lavender lavenderblush lawngreen lemonchiffon lightblue lightcoral lightcyan lightgoldenrodyellow lightgray lightgreen ' +
61    'lightgrey lightpink lightsalmon lightseagreen lightskyblue lightslategray lightslategrey lightsteelblue lightyellow lime ' +
62    'limegreen linen magenta maroon mediumaquamarine mediumblue mediumorchid mediumpurple mediumseagreen mediumslateblue ' +
63    'mediumspringgreen mediumturquoise mediumvioletred midnightblue mintcream mistyrose moccasin navajowhite navy oldlace olive ' +
64    'olivedrab orange orangered orchid palegoldenrod palegreen paleturquoise palevioletred papayawhip peachpuff peru pink plum ' +
65    'powderblue purple rebeccapurple red rosybrown royalblue saddlebrown salmon sandybrown seagreen seashell sienna silver skyblue ' +
66    'slateblue slategray slategrey snow springgreen steelblue tan teal thistle tomato turquoise violet wheat white whitesmoke ' +
67    'yellow yellowgreen transparent'
68  ).split(' '),
69)
70
71const SHAPES = new Set(['participant', 'actor', 'boundary', 'control', 'entity', 'database', 'collections', 'queue'])
72const METADATA = /@\{(.*)\}\s*$/
73
74const HALF = (isDashed: boolean, isReversed = false) => ({ isDashed, arrow: 'half' as const, ...(isReversed ? { isReversed } : {}) })
75
76const ARROWS: Record<string, { isDashed: boolean; arrow: Arrow; isReversed?: boolean }> = {
77  '-|\\': HALF(false),
78  '--|\\': HALF(true),
79  '-|/': HALF(false),
80  '--|/': HALF(true),
81  '-\\\\': HALF(false),
82  '--\\\\': HALF(true),
83  '-//': HALF(false),
84  '--//': HALF(true),
85  '/|-': HALF(false, true),
86  '/|--': HALF(true, true),
87  '\\|-': HALF(false, true),
88  '\\|--': HALF(true, true),
89  '//-': HALF(false, true),
90  '//--': HALF(true, true),
91  '\\\\-': HALF(false, true),
92  '\\\\--': HALF(true, true),
93  '->>': { isDashed: false, arrow: 'filled' },
94  '-->>': { isDashed: true, arrow: 'filled' },
95  '->': { isDashed: false, arrow: 'open' },
96  '-->': { isDashed: true, arrow: 'open' },
97  '-x': { isDashed: false, arrow: 'cross' },
98  '--x': { isDashed: true, arrow: 'cross' },
99  '-)': { isDashed: false, arrow: 'async' },
100  '--)': { isDashed: true, arrow: 'async' },
101  '<<->>': { isDashed: false, arrow: 'both' },
102  '<<-->>': { isDashed: true, arrow: 'both' },
103}
104
105const NAMED: Record<string, string> = {
106  quot: '"', amp: '&', lt: '<', gt: '>', nbsp: ' ', apos: "'", infin: '∞', rarr: '→', larr: '←', uarr: '↑',
107  darr: '↓', harr: '↔', rArr: '⇒', lArr: '⇐', hArr: '⇔', hellip: '…', mdash: '—', ndash: '–', copy: '©',
108  reg: '®', trade: '™', deg: '°', plusmn: '±', times: '×', divide: '÷', le: '≤', ge: '≥', ne: '≠',
109  middot: '·', bull: '•', laquo: '«', raquo: '»', euro: '€', pound: '£', check: '✓', cross: '✗',
110  colon: ':', semi: ';', num: '#', excl: '!', quest: '?', lpar: '(', rpar: ')', lsqb: '[', rsqb: ']', lbrack: '[',
111  rbrack: ']', lcub: '{', rcub: '}', lbrace: '{', rbrace: '}', ast: '*', plus: '+', comma: ',', period: '.', sol: '/',
112  bsol: '\\', verbar: '|', vert: '|', equals: '=', percnt: '%', dollar: '$', commat: '@', Hat: '^', lowbar: '_',
113  grave: '`', tilde: '~', sect: '§', para: '¶', micro: 'µ', cent: '¢', yen: '¥', frac12: '½', frac14: '¼', frac34: '¾',
114  sup1: '¹', sup2: '²', sup3: '³', iexcl: '¡', iquest: '¿', ensp: ' ', emsp: ' ', thinsp: ' ', lsquo: '‘', rsquo: '’',
115  ldquo: '“', rdquo: '”', dagger: '†', Dagger: '‡', permil: '‰', prime: '′', Prime: '″', larrhk: '↩', crarr: '↵',
116  alpha: 'α', beta: 'β', gamma: 'γ', delta: 'δ', epsilon: 'ε', lambda: 'λ', mu: 'μ', pi: 'π', sigma: 'σ', tau: 'τ',
117  phi: 'φ', omega: 'ω', Gamma: 'Γ', Delta: 'Δ', Lambda: 'Λ', Pi: 'Π', Sigma: 'Σ', Phi: 'Φ', Omega: 'Ω',
118  sum: '∑', prod: '∏', radic: '√', int: '∫', part: '∂', nabla: '∇', isin: '∈', notin: '∉', cap: '∩', cup: '∪',
119  sub: '⊂', sup: '⊃', and: '∧', or: '∨', not: '¬', forall: '∀', exist: '∃', empty: '∅', equiv: '≡', asymp: '≈',
120  prop: '∝', minus: '−', lowast: '∗', sdot: '⋅', loz: '◊', spades: '♠', clubs: '♣', hearts: '♥', diams: '♦',
121}
122
123const BREAK = /<br\s*\/?>/gi
124
125const REPLACEMENT = '�'
126
127const isDrawable = (point: number) =>
128  point <= 0x10ffff && !(point >= 0xd800 && point <= 0xdfff) && !(point < 0x20 || (point >= 0x7f && point < 0xa0))
129
130const codePoint = (code: string) => {
131  const point = Number(code)
132  return isDrawable(point) ? String.fromCodePoint(point) : REPLACEMENT
133}
134
135const decode = (text: string) =>
136  text.replace(/\u0000(\d+|[a-z][a-z0-9]*)\u0000/gi, (whole, code: string) =>
137    /^\d+$/.test(code) ? codePoint(code) : (NAMED[code] ?? NAMED[code.toLowerCase()] ?? `#${code};`),
138  )
139
140const clean = (text: string) => decode(text.replace(BREAK, ' ')).replace(/\s+/g, ' ').trim()
141
142const cleanLines = (text: string) =>
143  text
144    .split(BREAK)
145    .map(part => decode(part).replace(/\s+/g, ' ').trim())
146    .filter(part => part !== '')
147    .join('\n')
148
149const unquote = (text: string) => text.trim().replace(/^"(.*)"$/, '$1')
150
151const idOf = (text: string) => text.replace(/@\{.*\}$/, '').trim()
152
153const plural = (count: number, one: string, many = `${one}s`) => `${count} ${count === 1 ? one : many}`
154
155const lineList = (lines: number[]) => `${lines.length === 1 ? 'line' : 'lines'} ${lines.join(', ')}`
156
157function boxLabel(text: string): string {
158  const rest = text.replace(COLOUR_FUNCTION, '').replace(COLOUR_HEX, '')
159  if (rest !== text) return clean(rest)
160  const [first = '', ...others] = text.trim().split(/\s+/)
161  return COLOURS.has(first.toLowerCase()) ? clean(others.join(' ')) : clean(text)
162}
163
164export function mermaidBlocks(markdown: string): string[] {
165  return fencesOf(markdown).map(fence => fence.source)
166}
167
168export function isSequence(source: string): boolean {
169  return kindOf(source) === 'sequenceDiagram'
170}
171
172export function kindOf(source: string): string {
173  return body(source).header.split(/\s+/)[0] ?? ''
174}
175
176function isComment(line: string): boolean {
177  return line.startsWith('%%')
178}
179
180type Line = { text: string; line: number }
181
182function body(source: string): { title?: string; header: string; lines: Line[] } {
183  const lines = source.split('\n').map((text, i) => ({ text: text.trim(), line: i + 1 }))
184  let title: string | undefined
185  let at = lines.findIndex(line => line.text !== '')
186  if (lines[at]?.text === '---') {
187    const close = lines.findIndex((line, i) => i > at && line.text === '---')
188    if (close > at) {
189      for (const { text } of lines.slice(at + 1, close)) {
190        const found = /^title\s*:\s*(.+)$/.exec(text)
191        if (found) title = unquote(found[1]!)
192      }
193      at = close + 1
194    }
195  }
196  const rest = lines.slice(Math.max(0, at))
197  const start = rest.findIndex(line => line.text !== '' && !isComment(line.text))
198  const first = rest[start]
199  const inline = first && /^sequenceDiagram\s+(\S.*)$/.exec(first.text)
200  if (first && inline) return { title, header: 'sequenceDiagram', lines: [{ text: inline[1]!, line: first.line }, ...rest.slice(start + 1)] }
201
202  return { title, header: first?.text ?? '', lines: start < 0 ? [] : rest.slice(start + 1) }
203}
204
205function statements(lines: Line[]): Line[] {
206  return lines.flatMap(({ text, line }) => {
207    if (isComment(text)) return []
208    const marked = text.replace(ENTITY, (_, code: string) => `${ENTITY_MARK}${code}${ENTITY_MARK}`)
209    const uncommented = /^box\b/i.test(marked) ? marked : marked.replace(/#.*$/, '')
210    return uncommented
211      .split(';')
212      .map(part => part.trim())
213      .filter(part => part !== '' && !isComment(part))
214      .map(part => ({ text: part, line }))
215  })
216}
217
218type Found = { from: string; to: string; arrow: string; mark: string; text: string; hasColon: boolean; isInsideName: boolean; isCentral: boolean; isMalformed: boolean }
219
220function message(statement: string, known: Map<string, Participant>): Found | undefined {
221  const colon = statement.indexOf(':')
222  const head = colon < 0 ? statement : statement.slice(0, colon)
223  const text = colon < 0 ? '' : statement.slice(colon + 1)
224  const candidates = [...head.matchAll(ARROW)].flatMap(match => {
225    const from = head.slice(0, match.index).trim().replace(/\(\)$/, '').trim()
226    const tail = head.slice(match.index + match[0].length)
227    const mark = /^\s*(?:\(\))?\s*([+-])/.exec(tail)?.[1] ?? ''
228    const to = tail.replace(/^\s*(?:\(\))?\s*[+-]?\s*(?:\(\))?/, '').trim()
229    const isInsideName = match[0].endsWith('x') && /^\w/.test(tail) && /\w$/.test(from)
230    const isCentral = /\(\)\s*$/.test(head.slice(0, match.index)) || /^\s*[+-]?\s*\(\)/.test(tail)
231    const isMalformed = !isEndpoint(from, SENDER_KEYWORDS) || !isEndpoint(to)
232    return from !== '' && to !== '' ? [{ from, to, arrow: match[0], mark, text, hasColon: colon >= 0, isInsideName, isCentral, isMalformed }] : []
233  })
234  const wellFormed = candidates.filter(c => !c.isMalformed)
235  if (wellFormed.length === 0) return candidates[0]
236  const ranked = [...wellFormed.filter(c => !c.isInsideName), ...wellFormed.filter(c => c.isInsideName)]
237  return ranked.find(c => known.has(c.from) && known.has(c.to)) ?? ranked.find(c => known.has(c.from)) ?? ranked[0]
238}
239
240// Mermaid's actor token stops at these, so an endpoint holding one is a malformed arrow, not a name.
241const isName = (id: string) => !/[<>:,]/.test(idOf(id)) && !/^[-+]|[-+]$/.test(idOf(id))
242const isEndpoint = (id: string, keywords = KEYWORDS) => isName(id) && !keywords.has(idOf(id).toLowerCase())
243
244type Counter = { next: number; step: number; isVisible: boolean }
245
246// Mermaid counts every message from 1 whether or not numbers show; `autonumber` only moves the
247// counter when it names a start, and `off` hides numbers without stopping the count.
248function renumber(counter: Counter, args: string): void {
249  if (/^off\b/i.test(args)) {
250    counter.isVisible = false
251    return
252  }
253  const [start = NaN, step = NaN] = args === '' ? [] : args.split(/\s+/).map(Number)
254  if (Number.isFinite(start) && start !== 0) counter.next = start
255  if (Number.isFinite(step) && step !== 0) counter.step = step
256  counter.isVisible = true
257}
258
259const unwrapped = (text: string) => text.replace(WRAP, '')
260
261function metadataOf(declared: string, id: string, at: number, problems: string[]): { type?: string; alias?: string } {
262  const inner = METADATA.exec(declared)?.[1]
263  if (inner === undefined) return {}
264  const fields = fieldsOf(inner)
265  if (fields === undefined) {
266    problems.push(`line ${at}: metadata on ${id} not understood`)
267    return {}
268  }
269  const type = typeof fields.type === 'string' ? fields.type.toLowerCase() : undefined
270  if (type !== undefined && !SHAPES.has(type)) problems.push(`line ${at}: participant type "${fields.type}" not known`)
271  const alias = typeof fields.alias === 'string' ? fields.alias : undefined
272
273  return { ...(type === undefined ? {} : { type }), ...(alias === undefined ? {} : { alias }) }
274}
275
276function fieldsOf(inner: string): Record<string, unknown> | undefined {
277  try {
278    const parsed: unknown = JSON.parse(`{${inner}}`)
279    if (typeof parsed === 'object' && parsed !== null) return parsed as Record<string, unknown>
280  } catch {
281    // Mermaid reads the braces as a YAML flow mapping; fall through to that.
282  }
283
284  return flowMapping(inner)
285}
286
287const FLOW_ENTRY = /^\s*(?:"([^"]*)"|'([^']*)'|([^"':,][^:,]*?))\s*(?::(?:\s+|$)|(?<=["'])\s*:)(.*)$/
288
289// A YAML flow mapping: `key: value` pairs split on commas outside quotes. An unquoted key needs a
290// space after its colon, as in YAML, so `type:queue` is a key with no value.
291function flowMapping(inner: string): Record<string, unknown> | undefined {
292  const parts = inner.match(/(?:"[^"]*"|'[^']*'|[^,])+/g) ?? []
293  const fields: Record<string, unknown> = {}
294  for (const part of parts.filter(part => part.trim() !== '')) {
295    const entry = FLOW_ENTRY.exec(part)
296    if (!entry) return undefined
297    const key = (entry[1] ?? entry[2] ?? entry[3] ?? '').trim()
298    const value = entry[4]!.trim()
299    if (value !== '') fields[key] = unquote(value.replace(/^'(.*)'$/, '"$1"'))
300  }
301
302  return fields
303}
304
305export function parseSequence(source: string): Sequence {
306  const participants: Participant[] = []
307  const steps: Step[] = []
308  const boxes: { label: string }[] = []
309  const known = new Map<string, Participant>()
310  const blocks: { kind: 'box' | 'block'; keyword: string; line: number }[] = []
311  const unknown: string[] = []
312  let rejected = 0
313  const lineProblems: string[] = []
314  const links: number[] = []
315  const active = new Map<string, number>()
316  const doomed = new Map<string, number>()
317  const gone = new Set<string>()
318  const { title: frontTitle, header, lines } = body(source)
319  if (header !== '' && header !== 'sequenceDiagram') lineProblems.push(`not a sequenceDiagram: \`${header.slice(0, MAX_EXAMPLE)}\``)
320  let title = frontTitle
321  const counter: Counter = { next: 1, step: 1, isVisible: false }
322  let created: string | undefined
323  let isDescribing = false
324  let box: number | undefined
325  let extraEnds = 0
326
327  const meet = (id: string, label = id, kind: Participant['kind'] = 'participant') => {
328    const existing = known.get(id)
329    if (existing) return existing
330    const participant: Participant = { id, label: clean(label) || id, kind, ...(box === undefined ? {} : { box }) }
331    known.set(id, participant)
332    participants.push(participant)
333    return participant
334  }
335
336  const reject = (at: number, problem: string) => {
337    lineProblems.push(`line ${at}: ${problem} (mermaid.live rejects)`)
338    rejected++
339  }
340
341  // Mermaid tracks activation on any id and draws it once that id is a participant, even one first
342  // named by a later message; bars for ids that never become participants are dropped at the end.
343  const activate = (id: string, isOn: boolean, line: number) => {
344    const depth = active.get(id) ?? 0
345    if (!isOn && depth === 0) {
346      reject(line, `deactivate ${id} while inactive`)
347      return
348    }
349    active.set(id, depth + (isOn ? 1 : -1))
350    steps.push({ kind: 'activate', id, isOn })
351  }
352
353  const settleDoomed = (ids: string[], at: number) => {
354    for (const id of [...doomed.keys()]) {
355      doomed.delete(id)
356      if (!ids.includes(id)) {
357        reject(at, `the message after destroy ${id} must involve ${id}`)
358        continue
359      }
360      steps.push({ kind: 'destroy', id })
361      gone.add(id)
362    }
363  }
364
365  const sendMessage = (found: Found, at: number) => {
366    if (found.isMalformed) {
367      reject(at, `arrow \`${`${found.from}${found.arrow}${found.to}`.slice(0, MAX_EXAMPLE)}\` not understood`)
368      return
369    }
370    const bad = [found.from, found.to].map(idOf).find(id => /^[()]/.test(id))
371    if (bad !== undefined) {
372      reject(at, `participant \`${bad.slice(0, MAX_EXAMPLE)}\` cannot start with a parenthesis`)
373      return
374    }
375    if (box !== undefined) {
376      reject(at, 'only participants can be declared inside a box')
377      return
378    }
379    const written = { from: meet(idOf(found.from)).id, to: meet(idOf(found.to)).id }
380    const { isReversed = false, ...arrow } = ARROWS[found.arrow]!
381    const [from, to] = isReversed ? [written.to, written.from] : [written.from, written.to]
382    if (!found.hasColon) reject(at, "message without ':'")
383    if (created !== undefined && written.to !== created) reject(at, `the message after create ${created} must go to ${created}`)
384    created = undefined
385    if (found.isCentral) lineProblems.push(`line ${at}: central connection () not drawn`)
386    for (const id of [...new Set([from, to])].filter(id => gone.has(id))) {
387      lineProblems.push(`line ${at}: message touches ${id} after destroy`)
388    }
389    const number = counter.isVisible ? counter.next : undefined
390    counter.next = Math.round((counter.next + counter.step) * 100) / 100
391    steps.push({
392      kind: 'message',
393      from,
394      to,
395      text: cleanLines(unwrapped(found.text)),
396      ...arrow,
397      ...(number === undefined ? {} : { number }),
398    })
399    if (found.mark === '+') activate(written.to, true, at)
400    if (found.mark === '-') activate(written.from, false, at)
401    settleDoomed([from, to], at)
402  }
403
404  for (const { text: line, line: at } of statements(lines)) {
405    if (isDescribing) {
406      isDescribing = !line.includes('}')
407      continue
408    }
409    const beyond = [...line.matchAll(/\u0000(\d+)\u0000/g)].find(found => Number(found[1]) > 0x10ffff)
410    if (beyond) {
411      reject(at, `character code #${beyond[1]}; is out of range`)
412      continue
413    }
414    if (DESCRIPTION_BLOCK.test(line)) {
415      isDescribing = !line.includes('}')
416      continue
417    }
418    const declaration = PARTICIPANT.exec(line)
419    const isPlainDeclaration = declaration !== null && !new RegExp(ARROW.source).test(declaration[3]!)
420    const found = isPlainDeclaration || BLOCK_LINE.test(line) ? undefined : message(line, known)
421    if (found && !found.isInsideName) {
422      sendMessage(found, at)
423      continue
424    }
425    if (IGNORED.test(line)) {
426      if (/^links?\b/i.test(line)) links.push(at)
427      continue
428    }
429    const autonumber = AUTONUMBER.exec(line)
430    if (autonumber) {
431      renumber(counter, autonumber[1] ?? '')
432      continue
433    }
434    if (/^title\b/i.test(line)) {
435      title = clean(line.slice(5).replace(/^\s*:/, ''))
436      continue
437    }
438    if (line.toLowerCase() === 'end') {
439      const closed = blocks.pop()
440      if (closed === undefined) extraEnds++
441      else if (closed.kind === 'block') steps.push({ kind: 'close' })
442      else box = undefined
443      continue
444    }
445    const isDeclaration = PARTICIPANT.test(line)
446    if (box !== undefined && !isDeclaration && !/^box\b/i.test(line)) {
447      reject(at, 'only participants can be declared inside a box')
448      continue
449    }
450    if (/^box\b/i.test(line)) {
451      if (box !== undefined) {
452        reject(at, 'box inside a box')
453        continue
454      }
455      blocks.push({ kind: 'box', keyword: 'box', line: at })
456      box = boxes.push({ label: boxLabel(line.slice(3)) }) - 1
457      continue
458    }
459    const declared = PARTICIPANT.exec(line)
460    if (declared) {
461      const kind = declared[2]!.toLowerCase() === 'actor' ? 'actor' : 'participant'
462      // A quoted name takes the rest of the line in mermaid, `as` included.
463      const rest = line.replace(/^(?:create\s+)?(?:participant|actor)\s+/i, '')
464      const isQuoted = rest.startsWith('"')
465      const id = idOf(isQuoted ? rest : declared[3]!)
466      const written = isQuoted ? undefined : (declared[4] ?? (/\sas$/i.test(rest) ? '' : undefined))
467      if (!isName(id)) {
468        reject(at, `participant \`${id.slice(0, MAX_EXAMPLE)}\` not understood`)
469        continue
470      }
471      if (declared[1] && known.has(id)) {
472        reject(at, `create ${id} after ${id} was already used`)
473        continue
474      }
475      const metadata = metadataOf(isQuoted ? rest : declared[3]!, id, at, lineProblems)
476      const isNew = !known.has(id)
477      const participant = meet(id, written ?? id, kind)
478      if (isNew) {
479        participant.kind = metadata.type === 'actor' ? 'actor' : kind
480        if (metadata.type !== undefined && metadata.type !== 'actor' && metadata.type !== 'participant') participant.shape = metadata.type
481      }
482      const alias = written ?? metadata.alias
483      if (alias !== undefined) participant.label = cleanLines(alias)
484      if (declared[1]) {
485        steps.push({ kind: 'create', id })
486        created = id
487      }
488      continue
489    }
490    const destroyed = DESTROY.exec(line)
491    if (destroyed) {
492      doomed.set(meet(idOf(destroyed[1]!)).id, steps.length)
493      continue
494    }
495    const activation = ACTIVATE.exec(line)
496    if (activation) {
497      activate(idOf(activation[2]!), activation[1]!.toLowerCase() === 'activate', at)
498      continue
499    }
500    const note = NOTE.exec(line)
501    if (note) {
502      const where = note[1]!.toLowerCase()
503      const side = where.startsWith('left') ? 'left' : where.startsWith('right') ? 'right' : 'over'
504      const names = [...new Set(note[2]!.split(',').map(name => idOf(name.trim())))]
505      const keyword = names.find(name => !isEndpoint(name))
506      if (keyword !== undefined) {
507        reject(at, `note on \`${keyword.slice(0, MAX_EXAMPLE)}\` not understood`)
508        continue
509      }
510      if (names.length > 2) {
511        reject(at, 'note over takes at most two participants')
512        continue
513      }
514      const over = names.map(name => meet(name).id)
515      if (side !== 'over' && over.length > 1) {
516        reject(at, `note ${where} takes one participant`)
517        continue
518      }
519      steps.push({ kind: 'note', over, side, text: cleanLines(unwrapped(note[3] ?? '')) })
520      continue
521    }
522    const opened = OPEN.exec(line)
523    if (opened) {
524      const keyword = opened[1]!.toLowerCase()
525      blocks.push({ kind: 'block', keyword, line: at })
526      steps.push({ kind: 'open', keyword, text: keyword === 'rect' ? '' : clean(opened[2] ?? '') })
527      continue
528    }
529    const branch = BRANCH.exec(line)
530    if (branch) {
531      const keyword = branch[1]!.toLowerCase()
532      const parent = BRANCH_OF[keyword]
533      const inside = blocks.findLast(block => block.kind === 'block')?.keyword
534      if (inside !== parent && !(keyword === 'and' && inside === 'par_over')) {
535        reject(at, `${keyword} outside ${parent}`)
536        continue
537      }
538      steps.push({ kind: 'branch', keyword, text: clean(branch[2] ?? '') })
539      continue
540    }
541    if (found) {
542      sendMessage(found, at)
543      continue
544    }
545    unknown.push(decode(line))
546  }
547
548  for (const [id, index] of [...doomed].sort((a, b) => b[1] - a[1])) steps.splice(index, 0, { kind: 'destroy', id })
549  const shown = steps.filter(step => step.kind !== 'activate' || known.has(step.id))
550
551  const problems: string[] = []
552  if (header === '') problems.push('no diagram type (mermaid.live rejects)')
553  else if (participants.length === 0 && steps.length === 0 && rejected === 0 && unknown.length === 0) problems.push('empty diagram')
554  if (unknown.length > 0) {
555    const examples = unknown
556      .slice(0, 2)
557      .map(line => `\`${line.length > MAX_EXAMPLE ? `${line.slice(0, MAX_EXAMPLE - 1)}…` : line}\``)
558      .join(', ')
559    problems.push(`${plural(unknown.length, 'line')} not understood: ${examples}`)
560  }
561  problems.push(...lineProblems)
562  if (links.length > 0) problems.push(`links not shown (${lineList(links)})`)
563  const openedOn = (kind: 'box' | 'block') => blocks.filter(block => block.kind === kind).map(block => block.line)
564  const unclosed = openedOn('block').length
565  if (unclosed > 0) problems.push(`${plural(unclosed, 'block')} not closed, opened on ${lineList(openedOn('block'))} (mermaid.live rejects)`)
566  const unclosedBoxes = openedOn('box').length
567  if (unclosedBoxes > 0) {
568    problems.push(`${plural(unclosedBoxes, 'box', 'boxes')} not closed, opened on ${lineList(openedOn('box'))} (mermaid.live rejects)`)
569  }
570  if (extraEnds > 0) problems.push(`${plural(extraEnds, 'extra end')} (mermaid.live rejects)`)
571
572  const unread =
573    unknown.length + rejected + unclosed + unclosedBoxes + extraEnds + (header !== 'sequenceDiagram' ? 1 : 0)
574  return { title, participants, steps: shown, problems, boxes, ...(unread > 0 ? { unread } : {}) }
575}
576

1import type { Arrow, Participant, Sequence, Step } from './parse'
2import { cellWidth } from './width'
3
4export type Ink = 'frame' | 'name' | 'line' | 'text' | 'note' | 'block' | 'number'
5// `shade` marks cells inside a `rect` block, drawn on a faint background
6// `lane` is the participant a cell belongs to (its box, lifeline, or the sender of its message);
7// `reply` marks a dashed return, so a surface can colour or quieten them
8export type Run = { text: string; ink: Ink; shade?: boolean; lane?: number; reply?: boolean }
9
10type Message = Extract<Step, { kind: 'message' }>
11type Note = Extract<Step, { kind: 'note' }>
12type Opening = Extract<Step, { kind: 'open' | 'branch' }>
13type Cell = { char: string; ink: Ink; shade?: boolean; lane?: number; reply?: boolean }
14type Paint = { lane?: number; reply?: boolean }
15type Owner = Step | string
16type Span = { a: number; b: number; need: number; owners: Owner[] }
17type Wrapped = { lines: string[]; isCut: boolean }
18type Block = { open: Extract<Step, { kind: 'open' }>; branches: Opening[]; steps: Step[]; children: Block[] }
19
20type Item = {
21  step: Step
22  text: string
23  number?: string
24  fullWidth: number
25  maxCap: number
26  minCap: number
27  wordCap: number
28  pieceCap: number
29  canInline: boolean
30  isFrame: boolean
31}
32type State = { inline: boolean; tight?: boolean; cap: number; isHidden?: boolean }
33
34type Plan = {
35  lanes: Participant[]
36  lane: Map<string, number>
37  centre: number[]
38  width: number
39  states: Map<Step, State>
40  names: number[]
41  stacked: boolean[]
42  isBare: boolean
43  pads: Map<Block, { lo: number; hi: number; left: number; right: number }>
44  creates: Map<Message, string>
45  tight: Set<Owner>
46  rows: number
47  nested: Set<Step>
48}
49
50const HIDDEN_ROOM = 10
51const NAME_MIN = 5
52const NAME_KEEP = 6
53const SOFT_CAP = 12
54const HARD_CAP = 6
55const FRAME_CAP = 8
56const FRAME_ROOM = 6
57const NEST_GAP = 2
58const LOOSEN_TRIES = 12
59// Room left of the first lifeline for a footnoted left-of note's `[n] ` marker.
60const LEFT_MARK_ROOM = 4
61// Layout work (items measured, summed over passes) one fit may spend on optional improvements,
62// so a large diagram stays fast while a small one still gets every pass it can use.
63const WORK_BUDGET = 2000
64const SETTLE_RUNS = 60
65let work = 0
66const SELF_CAP = 24
67// The most columns one allocation step hands a gap; wider steps rarely beat several narrow ones.
68const STEP_MOST = 48
69// A dashed return needs enough dashes beside its label to read as dashed.
70const DASHES = 3
71const LEADER = 1
72// the fewest stroke cells an arrow keeps when a label shares its row
73const ARROW_MIN = 3
74const COLS_PER_ROW = 12
75const ACTOR = '☺ '
76const plain = (text: string) => text.replace(/\u00a0/g, ' ')
77const GLUE = '\u00a0'
78const segmenter = new Intl.Segmenter(undefined, { granularity: 'grapheme' })
79
80const HEADS: Record<Arrow, { right: string; left: string }> = {
81  filled: { right: '▶', left: '◀' },
82  open: { right: '', left: '' },
83  cross: { right: '×', left: '×' },
84  async: { right: '▷', left: '◁' },
85  both: { right: '▶', left: '◀' },
86  half: { right: '⇀', left: '↽' },
87}
88
89const SHAPES: Record<string, string> = { queue: '≋ ', database: '◫ ', entity: '◇ ', boundary: '⊢ ', control: '↻ ', collections: '▤ ' }
90
91const markerOf = (p: Participant) => (p.kind === 'actor' ? ACTOR : (p.shape && SHAPES[p.shape]) ?? '')
92
93const SIMPLE = /^[\x20-\x7e\u00a0\u2026\u2190-\u21ff\u2500-\u25fc]*$/
94const graphemes = (text: string) => (SIMPLE.test(text) ? [...text] : [...segmenter.segment(text)].map(s => s.segment))
95const odd = (n: number) => (n % 2 === 0 ? n + 1 : n)
96const half = (w: number) => (w - 1) / 2
97const leftOf = (w: number) => Math.floor(w / 2)
98const rightOf = (w: number) => w - 1 - Math.floor(w / 2)
99
100function cut(text: string, most: number): { text: string; isCut: boolean } {
101  if (cellWidth(text) <= most) return { text, isCut: false }
102  if (most <= 0) return { text: '', isCut: true }
103  let kept = ''
104  for (const g of graphemes(text)) {
105    if (cellWidth(kept + g) + 1 > most) break
106    kept += g
107  }
108  return { text: `${kept.trimEnd()}…`, isCut: true }
109}
110
111const GLUED = '\u0001'
112const BREAK_AFTER = /(?<=[/_,→])(?=[^\s/_,→])|(?<=::)(?=[^:\s])/u
113const HUMP = /(?<=\p{Ll})(?=\p{Lu})/u
114const BREAK_PREFERRED = /(?<=[/,→])(?=[^\s/,→])|(?<=[^\s(])(?=\()/u
115
116// A token wider than the line splits after `/ , →` or before `(` first, so an identifier like
117// `generate_offerset(req_identity,` wraps at its seams; `_` and `::` are used only when a part still
118// doesn't fit. A run of letters and digits is never split, except in a participant name
119// (`humps`), which may fold at a CamelCase hump rather than be cut.
120function seams(part: string, cap: number, rule: RegExp): string[] {
121  return cellWidth(part) > cap ? part.split(rule).filter(piece => piece !== '') : [part]
122}
123
124function pieces(token: string, cap: number, humps = false): string[] {
125  if (cellWidth(token) <= cap) return [token]
126  const parts = seams(token, cap, BREAK_PREFERRED)
127    .flatMap(part => seams(part, cap, BREAK_AFTER))
128    .flatMap(part => (humps ? seams(part, cap, HUMP) : [part]))
129  if (parts.length < 2) return [token]
130  const out: string[] = []
131  let current = ''
132  for (const part of parts) {
133    if (current !== '' && cellWidth(current + part) > cap) {
134      out.push(current)
135      current = part
136    } else current += part
137  }
138  if (current !== '') out.push(current)
139  return out.map((piece, i) => (i === 0 ? piece : GLUED + piece))
140}
141
142function greedy(tokens: string[], cap: number): string[] {
143  const lines: string[] = []
144  let current = ''
145  for (const raw of tokens) {
146    const isGlued = raw.startsWith(GLUED)
147    const token = isGlued ? raw.slice(1) : raw
148    if (current === '') current = token
149    else if (isGlued && cellWidth(current + token) <= cap) current += token
150    else if (!isGlued && cellWidth(`${current} ${token}`) <= cap) current = `${current} ${token}`
151    else {
152      lines.push(current)
153      current = token
154    }
155  }
156  if (current !== '') lines.push(current)
157  return lines
158}
159
160// Lines wrap split at a seam rejoin without the space a word break would need.
161const joinLines = (lines: string[]) => lines.reduce((all, line) => (all === '' ? line : /([/_,→]|::)$/.test(all) ? all + line : `${all} ${line}`), '')
162
163const wrapped = new Map<string, Wrapped>()
164
165export function wrap(text: string, cap: number, humps = false): Wrapped {
166  const key = `${cap}\u0000${humps ? 1 : 0}\u0000${text}`
167  const hit = wrapped.get(key)
168  if (hit) return hit
169  if (wrapped.size > 20000) wrapped.clear()
170  const result = wrapUncached(text, cap, humps)
171  wrapped.set(key, result)
172  return result
173}
174
175function wrapUncached(text: string, cap: number, humps: boolean): Wrapped {
176  let isCut = false
177  const lines = text.split('\n').flatMap(paragraph => {
178    // A free-standing arrow stays with the word before it, so no line starts with one; a slash or bar
179    // between alternatives stays with the word after it, so no line ends on one.
180    const kept = paragraph.replace(/ ([→⇢]) /gu, ' $1 ').replace(/ ([/|]) /gu, ' $1 ')
181    const tokens = kept.split(' ').filter(t => t !== '').flatMap(token => pieces(token, cap, humps)).map(token => {
182      const isGlued = token.startsWith(GLUED)
183      const shown = cut(isGlued ? token.slice(1) : token, cap)
184      isCut ||= shown.isCut
185      return isGlued ? GLUED + shown.text : shown.text
186    })
187    if (tokens.length === 0) return []
188    const lines = greedy(tokens, cap)
189    let tight = cap
190    const longest = Math.max(...tokens.map(token => cellWidth(token.replace(GLUED, ''))))
191    while (lines.length > 1 && tight - 1 >= longest && greedy(tokens, tight - 1).length === lines.length) tight--
192    return greedy(tokens, tight)
193  })
194  return { lines, isCut }
195}
196
197// A wrapped label whose last line leaves no room for the arrow costs a row of its own. A slightly
198// narrower wrap with the same line count often frees that room, so try it before giving up the row.
199const balancedCache = new Map<string, Map<number, Wrapped>>()
200
201function balanced(lines: Wrapped, text: string, most: number): Wrapped {
202  const fits = (line: string) => line !== '' && cellWidth(line) <= most
203  const last = lines.lines.at(-1) ?? ''
204  if (lines.isCut || lines.lines.length < 2 || fits(last)) return lines
205  const wide = widest(lines.lines)
206  const key = (most * 1024 + wide) * 1024 + lines.lines.length
207  if (balancedCache.size > 2000) balancedCache.clear()
208  const known = balancedCache.get(text) ?? new Map<number, Wrapped>()
209  balancedCache.set(text, known)
210  const hit = known.get(key)
211  if (hit) return hit
212  let found = lines
213  for (let cap = wide - 1; cap >= Math.max(1, wide - 16); cap--) {
214    const tried = wrap(text, cap)
215    if (tried.isCut || tried.lines.length > lines.lines.length) break
216    if (fits(tried.lines.at(-1) ?? '')) {
217      found = tried
218      break
219    }
220  }
221  known.set(key, found)
222  return found
223}
224
225const noteWidth = (step: Note, text: number) => (step.side === 'over' ? odd(text + 2) : text + 2)
226const widest = (lines: string[]) => Math.max(0, ...lines.map(cellWidth))
227
228export const canStack = (p: Participant) => !p.label.includes('\n') && p.label.trim().includes(' ')
229
230function stackedLabel(label: string): string[] {
231  const words = label.trim().split(/ +/)
232  let best = [label]
233  let bestWidth = Number.MAX_SAFE_INTEGER
234  for (let k = 1; k < words.length; k++) {
235    const lines = [words.slice(0, k).join(' '), words.slice(k).join(' ')]
236    const w = widest(lines)
237    if (w < bestWidth) {
238      best = lines
239      bestWidth = w
240    }
241  }
242  return best
243}
244
245// A box shows at most four lines of name; past that the fitter widens the lane, and only a lane
246// that can't widen loses the tail of its name to `…`.
247const HEADER_MOST = 4
248
249function fullHeader(p: Participant, cap: number, stacked = false, isBare = false): string[] {
250  const lines = stacked && canStack(p) ? stackedLabel(p.label) : p.label.split('\n')
251  const marker = isBare ? '' : markerOf(p)
252  return lines.flatMap((line, i) => {
253    const mark = i === 0 ? marker : ''
254    return wrap(line.trim(), Math.max(1, cap), true).lines.map((text, k) => `${k === 0 ? mark : ''}${text}`)
255  })
256}
257
258function headerLines(p: Participant, cap: number, stacked = false, isBare = false): string[] {
259  const all = fullHeader(p, cap, stacked, isBare)
260  if (all.length <= HEADER_MOST) return all
261  return [...all.slice(0, HEADER_MOST - 1), cut(joinLines(all.slice(HEADER_MOST - 1)), Math.max(1, cap)).text]
262}
263
264const boxWidths = new WeakMap<Participant, Map<string, number>>()
265
266function boxWidth(p: Participant, cap: number, isBare: boolean, stacked = false): number {
267  const known = boxWidths.get(p) ?? new Map<string, number>()
268  boxWidths.set(p, known)
269  const key = `${cap}:${isBare}:${stacked}`
270  const hit = known.get(key)
271  if (hit !== undefined) return hit
272  const width = widest(headerLines(p, cap, stacked, isBare)) + (isBare ? 2 : 4)
273  known.set(key, width)
274  return width
275}
276const boxHeight = (p: Participant, cap: number, stacked = false) => headerLines(p, cap, stacked).length + 2
277
278const createsCache = new WeakMap<Step[], Map<Message, string>>()
279
280function createsOf(steps: Step[]): Map<Message, string> {
281  const hit = createsCache.get(steps)
282  if (hit) return hit
283  const creates = new Map<Message, string>()
284  createsCache.set(steps, creates)
285  steps.forEach((step, k) => {
286    if (step.kind !== 'create') return
287    const next = steps.slice(k + 1).find((s): s is Message => s.kind === 'message' && s.from !== s.to && (s.from === step.id || s.to === step.id))
288    if (next && !creates.has(next)) creates.set(next, step.id)
289  })
290  return creates
291}
292
293const nestedCache = new WeakMap<Block[], Set<Step>>()
294
295// Steps inside a frame. A self message outside every frame may run its label over the lanes to
296// its right, since its rows belong to it alone; inside a frame the label stays within the frame.
297function nestedOf(tree: Block[]): Set<Step> {
298  const hit = nestedCache.get(tree)
299  if (hit) return hit
300  const nested = new Set<Step>()
301  const collect = (block: Block) => {
302    block.steps.forEach(step => nested.add(step))
303    block.children.forEach(collect)
304  }
305  tree.forEach(collect)
306  nestedCache.set(tree, nested)
307  return nested
308}
309
310const isSpilling = (step: Step, nested: Set<Step>) => step.kind === 'message' && step.from === step.to && !nested.has(step)
311
312// A call outside every frame owns its rows too, so a label that doesn't sit on its arrow may run
313// right over idle lanes instead of wrapping inside the gap between its two lifelines.
314const canSpill = (step: Step, nested: Set<Step>, creates: Map<Message, string>): step is Message =>
315  step.kind === 'message' && step.from !== step.to && !nested.has(step) && !creates.has(step)
316
317// A label sits on its arrow only while it fits on one line; a longer one spills over the rows
318// above, where its last line may still land on the arrow.
319function isSpill(step: Step, states: Map<Step, State>, items: Item[], nested: Set<Step>, creates: Map<Message, string>): boolean {
320  if (!canSpill(step, nested, creates)) return false
321  const state = states.get(step)
322  if (!state?.inline) return true
323  const item = itemIndex(items).get(step)
324  return item !== undefined && labelOf(item, state).lines.length > 1
325}
326
327const indexes = new WeakMap<Item[], Map<Step, Item>>()
328
329function itemIndex(items: Item[]): Map<Step, Item> {
330  const hit = indexes.get(items)
331  if (hit) return hit
332  const index = new Map(items.map(item => [item.step, item]))
333  indexes.set(items, index)
334  return index
335}
336
337function blocksOf(steps: Step[]): { top: Step[]; blocks: Block[] } {
338  const root: Block = { open: { kind: 'open', keyword: '', text: '' }, branches: [], steps: [], children: [] }
339  const stack = [root]
340  for (const step of steps) {
341    const current = stack.at(-1)!
342    if (step.kind === 'open') {
343      const block: Block = { open: step, branches: [], steps: [], children: [] }
344      current.children.push(block)
345      stack.push(block)
346    } else if (step.kind === 'close') {
347      if (stack.length > 1) stack.pop()
348    } else if (step.kind === 'branch' && stack.length > 1) current.branches.push(step)
349    else current.steps.push(step)
350  }
351  return { top: root.steps, blocks: root.children }
352}
353
354const WORD_KEEP = 14
355const wordKeep = (text: string) => Math.min(WORD_KEEP, widest(text.split(/[\s\n]+/)))
356const NAME_WORD_KEEP = 12
357const nameCut = (p: Participant, cap: number) => p.label.split('\n').some(line => wrap(line.trim(), cap, true).isCut) || fullHeader(p, cap).length > HEADER_MOST
358const floors = new WeakMap<Participant, number>()
359// The narrowest box a name fits in without cutting a word, counting the breaks wrap makes inside
360// identifiers (`Tarif::Rating` folds after `::`), capped so one long word can't hold a lane wide.
361function nameFloor(p: Participant): number {
362  const hit = floors.get(p)
363  if (hit !== undefined) return hit
364  const most = Math.max(NAME_MIN, Math.min(NAME_WORD_KEEP, widest(p.label.split(/[\s\n]+/))))
365  let floor = NAME_MIN
366  while (floor < most && nameCut(p, floor)) floor++
367  floors.set(p, floor)
368  return floor
369}
370
371const NAME_LINES = HEADER_MOST
372
373// The narrowest box a name fits in whole within four lines (or its explicit line count). Labels
374// need width more than boxes do: a wrapped name costs header rows once, a wrapped label on every
375// message, so boxes start here and only widen with width the labels leave.
376const folds = new WeakMap<Participant, number>()
377
378function nameFold(p: Participant): number {
379  const hit = folds.get(p)
380  if (hit !== undefined) return hit
381  const full = widest(p.label.split('\n').map(line => line.trim()))
382  const lines = Math.max(NAME_LINES, p.label.split('\n').length)
383  let fold = full
384  for (let cap = nameFloor(p); cap < full; cap++) {
385    if (!nameCut(p, cap) && headerLines(p, cap).length <= lines) {
386      fold = cap
387      break
388    }
389  }
390  folds.set(p, fold)
391  return fold
392}
393
394// mermaid writes a frame's condition in brackets; a frame too narrow for them shows the bare condition instead.
395const frameText = (step: Opening) => (step.kind === 'open' && step.keyword === 'rect' ? '' : step.text === '' ? step.keyword : `${step.keyword} [${step.text}]`)
396const bareText = (step: Opening) => `${step.keyword} ${step.text}`.trim()
397
398// The narrowest width a text wraps to without cutting a word, counting the breaks wrap makes
399// inside identifiers, so `generate_quote_set_for_new_business` counts as its pieces, not 35 columns.
400function uncut(text: string): number {
401  let lo = 1
402  let hi = Math.max(1, ...text.split(/[ \n\u00a0]+/).map(cellWidth))
403  while (lo < hi) {
404    const mid = Math.floor((lo + hi) / 2)
405    if (wrap(text, mid).isCut) lo = mid + 1
406    else hi = mid
407  }
408  return lo
409}
410
411function itemsOf(sequence: Sequence): { items: Item[]; numbers: Map<Message, string> } {
412  const items: Item[] = []
413  const numbers = new Map<Message, string>()
414  // with labels above, numbers right-align so 9 and 10 end in the same column
415  const digits = labelsAbove ? Math.max(0, ...sequence.steps.map(step => (step.kind === 'message' ? String(step.number ?? '').length : 0))) : 0
416  for (const step of sequence.steps) {
417    if (step.kind === 'message') {
418      const number = step.number === undefined ? undefined : String(step.number).padStart(digits, '\u2007')
419      if (number) numbers.set(step, number)
420      const text = number ? (step.text === '' ? number : `${number}${GLUE}${step.text}`) : step.text
421      const fullWidth = widest(wrap(text, Number.MAX_SAFE_INTEGER).lines)
422      const isSelf = step.from === step.to
423      items.push({ step, text, number, fullWidth, maxCap: fullWidth, minCap: HARD_CAP, wordCap: wordKeep(text), pieceCap: 0, canInline: !isSelf && !labelsAbove, isFrame: false })
424    } else if (step.kind === 'note') {
425      const fullWidth = widest(wrap(step.text, Number.MAX_SAFE_INTEGER).lines)
426      items.push({ step, text: step.text, fullWidth, maxCap: fullWidth, minCap: HARD_CAP, wordCap: wordKeep(step.text), pieceCap: 0, canInline: false, isFrame: false })
427    } else if (step.kind === 'open' || step.kind === 'branch') {
428      const text = frameText(step)
429      if (text === '') continue
430      const floor = Math.min(cellWidth(text), Math.max(cellWidth(step.keyword), FRAME_CAP))
431      items.push({ step, text, fullWidth: cellWidth(text), maxCap: cellWidth(text), minCap: floor, wordCap: 0, pieceCap: 0, canInline: false, isFrame: true })
432    }
433  }
434  for (const item of items) {
435    item.wordCap = Math.max(0, ...item.text.split(/[ \n\u00a0]+/).map(cellWidth))
436    item.pieceCap = uncut(item.text)
437  }
438  return { items, numbers }
439}
440
441function labelOf(item: Item, state: State): Wrapped {
442  const wrapped = wrap(item.text, state.cap)
443  if (!item.isFrame || wrapped.lines.length <= 2) return wrapped
444  return { lines: [wrapped.lines[0]!, cut(wrapped.lines.slice(1).join(' '), state.cap).text], isCut: true }
445}
446
447function solve(n: number, spans: Span[], left: number, right: number, base?: number[]): { centre: number[]; width: number; gaps: number[] } {
448  const gaps = Array.from({ length: Math.max(0, n - 1) }, (_, i) => base?.[i] ?? 0)
449  for (const { a, b, need } of [...spans].sort((x, y) => x.b - x.a - (y.b - y.a))) {
450    const k = b - a
451    if (k <= 0) continue
452    const have = gaps.slice(a, b).reduce((s, g) => s + g, 0)
453    const deficit = need - have
454    if (deficit <= 0) continue
455    for (let i = 0; i < k; i++) gaps[a + i]! += Math.floor(deficit / k) + (i < deficit % k ? 1 : 0)
456  }
457  const centre = [left]
458  for (const g of gaps) centre.push(centre.at(-1)! + g)
459  return { centre, width: centre.at(-1)! + right + 1, gaps }
460}
461
462function measure(sequence: Sequence, lanes: Participant[], items: Item[], states: Map<Step, State>, names: number[], stacked: boolean[], tree: Block[], isBare: boolean, base?: number[], limit?: number): Plan {
463  const n = lanes.length
464  const last = n - 1
465  const lane = new Map(lanes.map((p, i) => [p.id, i]))
466  const spans: Span[] = []
467  const edges: { side: 'left' | 'right'; value: number; owners: Owner[] }[] = []
468  let left = 0
469  let right = 0
470  let owners: Owner[] = []
471  const gap = (a: number, b: number, need: number) => spans.push({ a, b, need, owners })
472  const edge = (side: 'left' | 'right', value: number) => {
473    edges.push({ side, value, owners })
474    if (side === 'left') left = Math.max(left, value)
475    else right = Math.max(right, value)
476  }
477  const widths = lanes.map((p, i) => boxWidth(p, names[i]!, isBare, stacked[i]))
478  const creates = createsOf(sequence.steps)
479  widths.forEach((w, i) => {
480    owners = i === last ? [`lane:${i}`] : [`lane:${i}`, `lane:${i + 1}`]
481    if (i === 0) edge('left', leftOf(w))
482    if (i === last) edge('right', rightOf(w))
483    else gap(i, i + 1, rightOf(w) + leftOf(widths[i + 1]!) + 2)
484  })
485  owners = []
486  sequence.boxes.forEach((group, k) => {
487    const members = lanes.flatMap((p, i) => (p.box === k ? [i] : []))
488    if (members.length === 0 || group.label === '') return
489    const a = members[0]!
490    const b = members.at(-1)!
491    const extra = cellWidth(group.label) + 6 - (leftOf(widths[a]!) + rightOf(widths[b]!) + 1)
492    if (a < b) gap(a, b, extra)
493    else if (extra > 0 && a === last) edge('right', rightOf(widths[a]!) + extra)
494    else if (extra > 0) gap(a, a + 1, rightOf(widths[a]!) + extra + leftOf(widths[a + 1]!) + 2)
495  })
496  const byStep = new Map(items.map(item => [item.step, item]))
497  const itemOf = (step: Step) => byStep.get(step)!
498  const labelWidth = new Map<Step, number>()
499  for (const item of items) labelWidth.set(item.step, widest(labelOf(item, states.get(item.step)!).lines))
500  const isShown = (step: Step) => !states.get(step)?.isHidden
501  // a boxed note's border takes a column each side, so the layout reserves them too
502  const noteBox = (step: Note) => noteWidth(step, labelWidth.get(step) ?? 0) + (boxed ? 2 : 0)
503  const isHidden = (step: Message) => !lane.has(step.from) || !lane.has(step.to)
504  const nested = nestedOf(tree)
505  const spills = (step: Step) => limit !== undefined && isSpill(step, states, items, nested, creates)
506
507  const depth = lanes.map(() => 0)
508  const stops = new Map<Step, number>()
509  sequence.steps.forEach((step, k) => {
510    owners = [step]
511    if (step.kind === 'activate') {
512      const i = lane.get(step.id)
513      if (i !== undefined) depth[i] = Math.max(0, depth[i]! + (step.isOn ? 1 : -1))
514      return
515    }
516    if (step.kind === 'message') {
517      if (isHidden(step)) {
518        edge('right', HIDDEN_ROOM)
519        return
520      }
521      const from = lane.get(step.from)!
522      const to = lane.get(step.to)!
523      const w = labelWidth.get(step) ?? 0
524      const n = step.arrow === 'both' ? 1 : 0
525      if (from === to) {
526        const next = sequence.steps[k + 1]
527        const lit = next?.kind === 'activate' && next.isOn && next.id === step.to ? 1 : 0
528        const bar = depth[from]! + lit >= 2 ? 1 : 0
529        if (from === last) edge('right', w + 4 + bar)
530        else if (!isSpilling(step, nested)) gap(from, from + 1, w + 5 + bar)
531        else if (limit !== undefined) gap(from, from + 1, 6 + bar)
532        else {
533          gap(from, from + 1, 6 + bar)
534          gap(from, last, w + 5 + bar - rightOf(widths[last]!))
535        }
536        return
537      }
538      const lo = Math.min(from, to)
539      const hi = Math.max(from, to)
540      const born = creates.get(step)
541      if (born !== undefined) owners = [step, `lane:${lane.get(born)}`]
542      const boxSide = born === undefined ? 0 : lane.get(born) === hi ? leftOf(widths[hi]!) : lane.get(born) === lo ? rightOf(widths[lo]!) : 0
543      const state = states.get(step)
544      if (spills(step)) {
545        const busy = depth.findIndex((d, i) => i > lo && d > 0)
546        if (busy >= 0) stops.set(step, busy)
547        gap(lo, hi, 7 + n + (step.isDashed ? DASHES : 0))
548        return
549      }
550      if (state?.inline) {
551        const lines = labelOf(itemOf(step), state).lines
552        const tail = cellWidth(lines.at(-1) ?? '') + (state.tight ? 5 : LEADER + 5) + n + (step.isDashed ? DASHES : 0) + 1
553        gap(lo, hi, tail + boxSide)
554        if (lines.length > 1) gap(lo, hi, widest(lines.slice(0, -1)) + (to > from ? LEADER + 3 : 5) + boxSide)
555      } else gap(lo, hi, w + (to > from ? LEADER + 3 : 5) + boxSide)
556      return
557    }
558    if (step.kind === 'note' && !isShown(step) && step.side === 'left' && step.over.some(id => lane.get(id) === 0)) {
559      edge('left', LEFT_MARK_ROOM)
560      return
561    }
562    if (step.kind !== 'note' || !isShown(step)) return
563    const over = step.over.flatMap(id => lane.get(id) ?? []).sort((a, b) => a - b)
564    if (over.length === 0) return
565    const bw = noteBox(step)
566    const a = over[0]!
567    const b = over.at(-1)!
568    const side = step.side
569    if (side === 'left') {
570      if (a === 0) edge('left', bw + 1)
571      else gap(a - 1, a, bw + 3)
572    } else if (side === 'right') {
573      if (b === last) edge('right', bw + 2)
574      else gap(b, b + 1, bw + 4)
575    } else if (a === b) {
576      if (a === 0) edge('left', half(bw))
577      else gap(a - 1, a, half(bw) + 2)
578      if (a === last) edge('right', half(bw))
579      else gap(a, a + 1, half(bw) + 2)
580    } else {
581      // like mermaid, a note keeps each of its source lines whole when the terminal has room: its
582      // widest line is a floor on the span while it takes no more than a third of the width
583      const natural = widest(step.text.split('\n')) + 2
584      if (limit === undefined) gap(a, b, (labelWidth.get(step) ?? 0) - 1)
585      // the note may spread to the lifelines either side of its span, so its floor is shared
586      // across those gaps rather than forcing one gap wide
587      // placeNote leaves two cells inside each neighbouring lifeline, so the floor matches that room
588      else if (natural <= Math.floor(limit / 3)) gap(a > 0 ? a - 1 : a, b < last ? b + 1 : b, natural - 1 + (a > 0 ? 3 : 0) + (b < last ? 3 : 0))
589      if (a === 0) edge('left', 1)
590      if (b === last) edge('right', 1)
591    }
592  })
593  owners = []
594
595  const pads = new Map<Block, { lo: number; hi: number; left: number; right: number }>()
596  const touched = (step: Step): number[] => {
597    if (step.kind === 'message') {
598      const ends = [lane.get(step.from), lane.get(step.to)]
599      return ends.some(e => e === undefined) ? [...ends.flatMap(e => (e === undefined ? [] : [e])), last] : (ends as number[])
600    }
601    if (step.kind === 'note') return step.over.flatMap(id => lane.get(id) ?? [])
602    if (step.kind === 'create' || step.kind === 'destroy' || step.kind === 'activate') return lane.has(step.id) ? [lane.get(step.id)!] : []
603    return []
604  }
605  const ownersOf = (block: Block): Owner[] => [block.open, ...block.branches, ...block.steps, ...block.children.flatMap(ownersOf), ...block.steps.flatMap(touched).map(i => `lane:${i}`)]
606  const pad = (block: Block): { lo: number; hi: number; left: number; right: number } => {
607    const children = block.children.map(pad)
608    owners = ownersOf(block)
609    const all = [...block.steps.flatMap(touched), ...children.flatMap(c => [c.lo, c.hi])]
610    const lo = all.length > 0 ? Math.min(...all) : 0
611    const hi = all.length > 0 ? Math.max(...all) : last
612    let l = 2
613    let r = 2
614    const labelNeed = Math.max(0, ...[block.open, ...block.branches].map(opening => {
615      const w = labelWidth.get(opening) ?? 0
616      return w > 0 ? w + FRAME_ROOM : 0
617    }))
618    for (const step of block.steps) {
619      if (step.kind === 'note' && isShown(step)) {
620        const over = step.over.flatMap(id => lane.get(id) ?? [])
621        const bw = noteBox(step)
622        const side = step.side
623        if (over.length === 0) continue
624        if (side === 'left' && Math.min(...over) === lo) l = Math.max(l, bw + 3)
625        if (side === 'right' && Math.max(...over) === hi) r = Math.max(r, bw + 4)
626        if (side === 'over' && Math.min(...over) === Math.max(...over)) {
627          if (over[0] === lo) l = Math.max(l, half(bw) + 2)
628          if (over[0] === hi) r = Math.max(r, half(bw) + 2)
629        }
630        if (side === 'over' && Math.min(...over) !== Math.max(...over)) {
631          if (Math.min(...over) === lo) l = Math.max(l, 3)
632          if (Math.max(...over) === hi) r = Math.max(r, 3)
633        }
634      }
635      if (step.kind === 'message' && step.from === step.to && lane.get(step.from) === hi) r = Math.max(r, (labelWidth.get(step) ?? 0) + 5)
636      if (step.kind === 'message' && isHidden(step)) r = Math.max(r, HIDDEN_ROOM)
637      if (step.kind === 'create' && lane.has(step.id)) {
638        const i = lane.get(step.id)!
639        if (i === lo) l = Math.max(l, leftOf(widths[i]!) + 2)
640        if (i === hi) r = Math.max(r, rightOf(widths[i]!) + 2)
641      }
642    }
643    for (const child of children) {
644      if (child.lo === lo) l = Math.max(l, child.left + NEST_GAP)
645      if (child.hi === hi) r = Math.max(r, child.right + NEST_GAP)
646    }
647    if (lo === hi) r = Math.max(r, labelNeed - 1)
648    else if (labelNeed > 0) gap(lo, lo + 1, labelNeed - 1)
649    const result = { lo, hi, left: l, right: r }
650    pads.set(block, result)
651    if (lo > 0) gap(lo - 1, lo, l + 2)
652    else edge('left', l)
653    if (hi < last) gap(hi, hi + 1, r + 2)
654    else edge('right', r)
655    return result
656  }
657  tree.forEach(pad)
658
659  const { centre, width, gaps } = solve(n, spans, left, right, base)
660  const tight = new Set<Owner>()
661  for (const span of spans) {
662    if (span.b <= span.a || span.need <= 0) continue
663    let have = 0
664    for (let i = span.a; i < span.b; i++) have += gaps[i]!
665    if (have <= span.need) span.owners.forEach(o => tight.add(o))
666  }
667  for (const { side, value, owners: o } of edges) if (value >= (side === 'left' ? left : right)) o.forEach(x => tight.add(x))
668  let rows = Math.max(0, ...lanes.map((p, i) => boxHeight(p, names[i]!, stacked[i])))
669  for (const item of items) {
670    const state = states.get(item.step)!
671    const lines = state.isHidden ? 1 : labelOf(item, state).lines.length
672    const step = item.step
673    if (step.kind !== 'message' || state.isHidden) {
674      rows += Math.max(1, lines)
675      continue
676    }
677    if (isHidden(step)) {
678      rows += lines + 1
679      continue
680    }
681    const from = lane.get(step.from)!
682    const to = lane.get(step.to)!
683    if (from === to) {
684      const spills = limit !== undefined && from !== last && isSpilling(step, nested)
685      rows += Math.max(2, spills ? wrap(item.text, Math.max(1, limit - centre[from]! - 6)).lines.length : lines)
686      continue
687    }
688    if ((state.inline && !spills(step)) || creates.has(step)) {
689      rows += state.inline ? lines : lines + 1
690      continue
691    }
692    const isRight = to > from
693    const both = step.arrow === 'both' ? 1 : 0
694    const start = centre[Math.min(from, to)]! + 1
695    const end = centre[Math.max(from, to)]! - 1
696    const reach = isRight ? end - 2 : end - both
697    const tail = isRight ? start + both + 1 : start + 3
698    const fits = (line: string) => line !== '' && tail + cellWidth(line) + (step.isDashed ? DASHES : 0) <= reach
699    const spill = spills(step)
700    const busy = stops.get(step)
701    const stop = busy === undefined ? limit ?? 0 : centre[busy]! - 1
702    const label = spill ? wrap(item.text, Math.max(1, stop - (start + (isRight ? 1 : 3)) - 1)) : labelOf(item, state)
703    const shown = balanced(label, item.text, reach - tail - (step.isDashed ? DASHES : 0))
704    rows += fits(shown.lines.at(-1) ?? '') ? shown.lines.length : shown.lines.length + 1
705  }
706  return { lanes, lane, centre, width, states, names: [...names], stacked: [...stacked], isBare, pads, creates, tight, rows, nested }
707}
708
709type Move = { apply: () => void; undo: () => void; size: number; owner?: Owner }
710
711type Phase = 'soft' | 'wrap' | 'stack' | 'names' | 'pieces' | 'hard' | 'bare' | 'notes' | 'crush'
712
713const LADDERS: Phase[][] = [
714  ['soft', 'wrap', 'stack', 'bare', 'names', 'pieces', 'notes', 'hard', 'crush'],
715  ['soft', 'wrap', 'stack', 'bare', 'notes', 'names', 'pieces', 'hard', 'crush'],
716]
717
718const rowsOf = (item: Item, state: State) => {
719  if (state.isHidden) return 1
720  if (item.step.kind === 'message' && state.inline) return labelOf(item, state).lines.length - 1
721  return Math.max(1, labelOf(item, state).lines.length)
722}
723
724function fit(sequence: Sequence, lanes: Participant[], items: Item[], tree: Block[], width: number, ladder: Phase[]): Plan {
725  const isSelf = (item: Item) => item.step.kind === 'message' && item.step.from === item.step.to
726  const nested = nestedOf(tree)
727  const startCap = (item: Item) => (isSelf(item) && !isSpilling(item.step, nested) ? Math.min(item.maxCap, Math.max(SELF_CAP, item.wordCap)) : item.maxCap)
728  const states = new Map<Step, State>(items.map(item => [item.step, { inline: item.canInline, cap: startCap(item) }]))
729  const fullNames = lanes.map(p => widest(p.label.split('\n').map(line => line.trim())))
730  const names = lanes.map(nameFold)
731  const stacked = lanes.map(() => false)
732  let isBare = false
733  work = 0
734  const run = () => {
735    work += items.length + lanes.length
736    return measure(sequence, lanes, items, states, names, stacked, tree, isBare, undefined, width)
737  }
738  const isSpent = () => work > WORK_BUDGET
739  const shown = (item: Item) => widest(labelOf(item, states.get(item.step)!).lines)
740
741  let overshoot = 1
742  const tighten = (phase: Phase): Move[] => {
743    if (phase === 'bare') return isBare ? [] : [{ apply: () => (isBare = true), undo: () => (isBare = false), size: 0 }]
744    if (phase === 'stack') {
745      return lanes.flatMap<Move>((p, i) => (stacked[i] || !canStack(p) ? [] : [{ apply: () => (stacked[i] = true), undo: () => (stacked[i] = false), size: fullNames[i]!, owner: `lane:${i}` }]))
746    }
747    if (phase === 'notes') {
748      return items.flatMap<Move>(item => {
749        const state = states.get(item.step)!
750        if (item.step.kind !== 'note' || state.isHidden) return []
751        return [{ apply: () => (state.isHidden = true), undo: () => (state.isHidden = false), size: item.fullWidth, owner: item.step }]
752      })
753    }
754    const nameMoves = (isHard: boolean) =>
755      names.flatMap((cap, i) => {
756        const now = Math.min(cap, fullNames[i]!)
757        const floor = isHard ? NAME_MIN : nameFloor(lanes[i]!)
758        if (fullNames[i]! <= NAME_KEEP || now <= floor) return []
759        return [{ apply: () => (names[i] = Math.max(floor, now - overshoot)), undo: () => (names[i] = cap), size: now, owner: `lane:${i}` }]
760      })
761    if (phase === 'names') return nameMoves(false)
762    if (phase === 'crush') return nameMoves(true)
763    const floor = phase === 'soft' ? SOFT_CAP : phase === 'wrap' ? 1 : HARD_CAP
764    return [...items.flatMap<Move>(item => {
765      const state = states.get(item.step)!
766      if (state.isHidden) return []
767      if (state.inline && !state.tight) return [{ apply: () => (state.tight = true), undo: () => (state.tight = false), size: item.fullWidth + 3, owner: item.step }]
768      if (state.inline) return [{ apply: () => (state.inline = false), undo: () => (state.inline = true), size: item.fullWidth + 2, owner: item.step }]
769      const now = shown(item)
770      const keep = phase === 'hard' ? 0 : phase === 'pieces' ? item.pieceCap : item.wordCap
771      const target = Math.max(floor, item.minCap, keep)
772      if (now <= target) return []
773      const cap = state.cap
774      const next = Math.min(cap, Math.max(target, now - overshoot))
775      return [{ apply: () => (state.cap = next), undo: () => (state.cap = cap), size: now, owner: item.step }]
776    })]
777  }
778
779  let plan = run()
780  for (const phase of ladder) {
781    while (plan.width > width) {
782      overshoot = plan.width - width
783      const moves = tighten(phase)
784      if (moves.length === 0) break
785      const binding = moves.filter(move => move.owner === undefined || plan.tight.has(move.owner)).sort((x, y) => y.size - x.size)
786      if (binding.length === 0) break
787      const first = binding[0]!
788      first.apply()
789      const alone = run()
790      if (alone.width < plan.width || binding.length === 1) {
791        plan = alone
792        continue
793      }
794      binding.slice(1).forEach(move => move.apply())
795      plan = run()
796    }
797  }
798
799  // Spend the slack where it saves the most rows: restore lost information first, then
800  // the move with the largest row saving per column it costs.
801  type Loosen = { apply: () => void; undo: () => void; tier: number; saves: number }
802  const candidates = (): Loosen[] => {
803    const all: Loosen[] = []
804    for (const item of items) {
805      const state = states.get(item.step)!
806      if (state.isHidden) {
807        all.push({ apply: () => (state.isHidden = false), undo: () => (state.isHidden = true), tier: 0, saves: 0 })
808        continue
809      }
810      const before = rowsOf(item, state)
811      const { isCut } = labelOf(item, state)
812      if (item.canInline && !state.inline) {
813        const cap = state.cap
814        all.push({
815          apply: () => {
816            state.inline = true
817            state.tight = true
818            state.cap = item.maxCap
819          },
820          undo: () => {
821            state.inline = false
822            state.tight = false
823            state.cap = cap
824          },
825          tier: isCut ? 0 : 2,
826          saves: before,
827        })
828      }
829      if (state.cap < item.maxCap) {
830        const cap = state.cap
831        let target = item.maxCap
832        for (let c = cap + 1; c <= item.maxCap; c++) {
833          const tried = wrap(item.text, c)
834          if (tried.lines.length < labelOf(item, state).lines.length || tried.isCut !== isCut) {
835            target = c
836            break
837          }
838        }
839        const after = rowsOf(item, { ...state, cap: target })
840        all.push({ apply: () => (state.cap = target), undo: () => (state.cap = cap), tier: isCut ? 0 : 2, saves: before - after })
841      }
842    }
843    for (const item of items) {
844      const state = states.get(item.step)!
845      if (state.inline && state.tight) all.push({ apply: () => (state.tight = false), undo: () => (state.tight = true), tier: 3, saves: 0 })
846    }
847    const heights = lanes.map((p, i) => boxHeight(p, names[i]!, stacked[i]))
848    const tallest = Math.max(0, ...heights)
849    // One tall box is never the only tall one for long: widening names together is what shortens the header.
850    const widened = lanes.map((p, i) => Math.max(names[i]!, nameFold(p)))
851    const folded = Math.max(0, ...lanes.map((p, i) => boxHeight(p, widened[i]!, stacked[i])))
852    if (folded < tallest) {
853      const before = [...names]
854      all.push({ apply: () => names.splice(0, names.length, ...widened), undo: () => names.splice(0, names.length, ...before), tier: 2, saves: tallest - folded })
855    }
856    names.forEach((cap, i) => {
857      if (cap >= fullNames[i]!) return
858      if (nameCut(lanes[i]!, cap)) {
859        all.push({ apply: () => (names[i] = cap + 1), undo: () => (names[i] = cap), tier: 1, saves: 0 })
860        return
861      }
862      let target = cap + 1
863      while (target < fullNames[i]! && boxHeight(lanes[i]!, target, stacked[i]) >= heights[i]!) target++
864      const others = Math.max(0, ...heights.filter((_, k) => k !== i))
865      const saves = tallest - Math.max(others, boxHeight(lanes[i]!, target, stacked[i]))
866      all.push({ apply: () => (names[i] = target), undo: () => (names[i] = cap), tier: saves > 0 ? 2 : 3, saves })
867    })
868    stacked.forEach((isStacked, i) => {
869      if (isStacked) all.push({ apply: () => (stacked[i] = false), undo: () => (stacked[i] = true), tier: 2, saves: 1 })
870    })
871    if (isBare) all.push({ apply: () => (isBare = false), undo: () => (isBare = true), tier: 3, saves: 0 })
872    return all
873  }
874  // Restoring lost text one column or one note at a time costs a layout pass per step, so
875  // first try every move of the leading tier together, and widen cut names by bisection.
876  const widenNames = (): boolean => {
877    let isWidened = false
878    names.forEach((cap, i) => {
879      let lo = cap
880      let hi = fullNames[i]!
881      while (lo < hi) {
882        const mid = Math.ceil((lo + hi) / 2)
883        names[i] = mid
884        const tried = run()
885        if (tried.width <= width) {
886          lo = mid
887          plan = tried
888        } else hi = mid - 1
889      }
890      names[i] = lo
891      isWidened ||= lo > cap
892    })
893    return isWidened
894  }
895  const together = (moves: Loosen[]): boolean => {
896    if (moves.length < 2) return false
897    moves.forEach(move => move.apply())
898    const tried = run()
899    if (tried.width <= width) {
900      plan = tried
901      return true
902    }
903    moves.forEach(move => move.undo())
904    return false
905  }
906  const loosen = () => {
907    while (!isSpent()) {
908      let best: { move: Loosen; plan: Plan; score: number } | undefined
909      const hope = (move: Loosen) => move.tier * 1000 - move.saves * 100
910      const ranked = candidates().filter(move => !(move.tier === 2 && move.saves <= 0)).sort((x, y) => hope(x) - hope(y))
911      const lead = ranked[0]?.tier
912      if (lead === 0 && together(ranked.filter(move => move.tier === 0))) continue
913      if (lead === 1 && widenNames()) continue
914      let tries = 0
915      for (const move of ranked) {
916        if (tries >= LOOSEN_TRIES || (best && (hope(move) >= best.score || best.move.tier < 2))) break
917        tries++
918        move.apply()
919        const tried = run()
920        move.undo()
921        if (tried.width > width) continue
922        const cost = Math.max(0, tried.width - plan.width)
923        if (move.tier === 2 && cost > COLS_PER_ROW * move.saves) continue
924        const score = move.tier * 1000 - (move.saves * 100) / (1 + cost)
925        if (!best || score < best.score) best = { move, plan: tried, score }
926      }
927      if (!best) break
928      if (best.move.tier === 1 && widenNames()) continue
929      best.move.apply()
930      plan = best.plan
931    }
932  }
933  loosen()
934
935  const snapshot = () => {
936    const saved = { states: new Map([...states].map(([step, one]) => [step, { ...one }])), names: [...names], stacked: [...stacked], isBare, plan }
937    return () => {
938      for (const [step, one] of saved.states) Object.assign(states.get(step)!, { tight: undefined, isHidden: undefined }, one)
939      names.splice(0, names.length, ...saved.names)
940      stacked.splice(0, stacked.length, ...saved.stacked)
941      isBare = saved.isBare
942      plan = saved.plan
943    }
944  }
945
946  // A side note's margin is slack too: narrowing it is worth it when the width it frees
947  // lets other labels save more rows than the note costs.
948  const narrowMargins = () => {
949    for (const item of items) {
950      if (isSpent()) return
951      if (item.step.kind !== 'note' || item.step.side === 'over') continue
952      const state = states.get(item.step)!
953      const floor = Math.max(item.wordCap, item.minCap)
954      if (state.isHidden || state.cap <= floor) continue
955      const before = plan.rows
956      const restore = snapshot()
957      state.cap = floor
958      plan = run()
959      loosen()
960      if (plan.width <= width && plan.rows < before) continue
961      restore()
962    }
963  }
964  narrowMargins()
965
966  // Tightening from the full layout can strand width in the wrong gaps. Build the layout a
967  // second way, from every label at its narrowest, spending columns where they save the most
968  // rows, and keep whichever needs fewer rows.
969  const cost = () => {
970    const lost = names.filter((cap, i) => nameCut(lanes[i]!, cap)).length + items.filter(item => states.get(item.step)!.isHidden || labelOf(item, states.get(item.step)!).isCut).length
971    return lost * 1000 + plan.rows
972  }
973  if (isSpent()) return best(settle())
974  const fromTopCost = cost()
975  const fromTop = snapshot()
976  const narrowest = () => {
977    for (const item of items) {
978      const state = states.get(item.step)!
979      if (state.isHidden) continue
980      state.inline = false
981      state.tight = false
982      state.cap = Math.min(state.cap, Math.max(item.pieceCap, item.minCap))
983    }
984    plan = run()
985  }
986  names.splice(0, names.length, ...lanes.map(nameFold))
987  narrowest()
988  if (plan.width > width) {
989    fromTop()
990    narrowest()
991  }
992  if (plan.width <= width) {
993    loosen()
994    narrowMargins()
995  }
996  if (plan.width > width || cost() >= fromTopCost) fromTop()
997  return best(settle())
998
999  function best(found: Plan): Plan {
1000    const folded = lanes.map((p, i) => Math.max(found.names[i]!, nameFold(p)))
1001    const variants = [found.names, folded].filter((one, k, all) => all.findIndex(other => other.join() === one.join()) === k)
1002    const allocated = variants
1003      .map(one => allocate(sequence, lanes, items, tree, width, { ...found, names: one }))
1004      .reduce<Plan | undefined>((most, plan) => (plan && (!most || costOf(items, plan) < costOf(items, most)) ? plan : most), undefined)
1005    const chosen = allocated && costOf(items, allocated) < costOf(items, found) ? allocated : found
1006    return evenHeader(chosen)
1007  }
1008
1009  // Boxes of one height read as a row; a single wide box beside tall ones wastes both width and
1010  // rows. Fold every name to the same number of lines and keep the height that costs fewest rows.
1011  function evenHeader(found: Plan): Plan {
1012    let kept = found
1013    for (let height = 1; height <= HEADER_MOST; height++) {
1014      const folded = lanes.map((p, i) => {
1015        for (let cap = nameFloor(p); cap < fullNames[i]!; cap++) if (!nameCut(p, cap) && fullHeader(p, cap).length <= height) return cap
1016        return fullNames[i]!
1017      })
1018      const tried = measure(sequence, lanes, items, found.states, folded, found.stacked, tree, found.isBare, undefined, width)
1019      if (tried.width <= width && costOf(items, tried) < costOf(items, kept)) kept = tried
1020    }
1021    return kept
1022  }
1023
1024  // Whatever width is left after the search goes back to cut names, then to labels wrapped
1025  // narrower than their room, largest first. Each step is a bisection over one cap, so it
1026  // stays cheap even after the work budget is spent.
1027  function settle(): Plan {
1028    let runs = 0
1029    const widen = (get: () => number, set: (cap: number) => void, most: number, isWorse: (tried: Plan) => boolean) => {
1030      let lo = get()
1031      let hi = most
1032      while (lo < hi && runs < SETTLE_RUNS) {
1033        runs++
1034        const mid = Math.ceil((lo + hi) / 2)
1035        set(mid)
1036        const tried = measure(sequence, lanes, items, states, names, stacked, tree, isBare, undefined, width)
1037        if (tried.width <= width && !isWorse(tried)) {
1038          lo = mid
1039          plan = tried
1040        } else hi = mid - 1
1041      }
1042      set(lo)
1043    }
1044    names.forEach((_, i) => {
1045      if (nameCut(lanes[i]!, names[i]!)) widen(() => names[i]!, cap => (names[i] = cap), fullNames[i]!, tried => tried.rows > plan.rows)
1046    })
1047    // spare width also goes to a box whose name folds inside an identifier (`offerset_` /
1048    // `generation`), as long as no row is spent on it
1049    names.forEach((_, i) => {
1050      if (breaksInside(lanes[i]!, names[i]!)) widen(() => names[i]!, cap => (names[i] = cap), fullNames[i]!, tried => tried.rows > plan.rows)
1051    })
1052    const narrow = items
1053      .filter(item => !states.get(item.step)!.isHidden && !states.get(item.step)!.inline && states.get(item.step)!.cap < item.maxCap)
1054      .sort((x, y) => rowsOf(y, states.get(y.step)!) - rowsOf(x, states.get(x.step)!))
1055    for (const item of narrow) {
1056      const state = states.get(item.step)!
1057      widen(() => state.cap, cap => (state.cap = cap), Math.max(state.cap, startCap(item)), tried => tried.rows > plan.rows)
1058    }
1059    return measure(sequence, lanes, items, states, names, stacked, tree, isBare, undefined, width)
1060  }
1061}
1062
1063const costOf = (items: Item[], plan: Plan) =>
1064  (plan.lanes.filter((p, i) => nameCut(p, plan.names[i]!)).length +
1065    items.filter(item => {
1066      const state = plan.states.get(item.step)
1067      return state !== undefined && (state.isHidden || labelOf(item, state).isCut)
1068    }).length) *
1069    1000 +
1070  plan.rows
1071
1072// A claim's room grows with the gaps lo..hi-1; a self label spilling right instead loses room to every
1073// gap left of its lane (`against`), since it can only run to the right edge.
1074type Claim = { item: Item; lo: number; hi: number; against?: number; memo: Map<number, number> }
1075
1076// Width goes where it saves the most rows. Every label starts at the narrowest width it wraps to
1077// whole; then columns go one batch at a time to whichever gap buys the most rows per column, and
1078// a few columns at a time move between gaps while that saves rows. A label's room is the sum of
1079// the gaps its arrow spans, so a long arrow is paid for by every gap it crosses.
1080function allocate(sequence: Sequence, lanes: Participant[], items: Item[], tree: Block[], width: number, from: Plan): Plan | undefined {
1081  const n = lanes.length
1082  if (n < 2) return undefined
1083  const { lane, names, stacked, isBare, nested } = from
1084  const creates = createsOf(sequence.steps)
1085  const states = new Map([...from.states].map(([step, state]) => [step, { ...state }]))
1086  const isFree = (item: Item): boolean => {
1087    const step = item.step
1088    if (states.get(step)?.isHidden) return false
1089    if (step.kind === 'message') return lane.has(step.from) && lane.has(step.to) && !creates.has(step)
1090    return step.kind === 'note' && step.side === 'over' && new Set(step.over.filter(id => lane.has(id))).size > 1
1091  }
1092  const free = items.filter(isFree)
1093  if (free.length === 0) return undefined
1094  for (const item of free) Object.assign(states.get(item.step)!, { inline: false, tight: false, cap: Math.max(item.pieceCap, item.minCap, 1) })
1095  const floor = measure(sequence, lanes, items, states, names, stacked, tree, isBare, undefined, width)
1096  if (floor.width > width) return undefined
1097  const gaps = floor.centre.slice(1).map((c, i) => c - floor.centre[i]!)
1098  const lastWidth = boxWidth(lanes[n - 1]!, names[n - 1]!, isBare, stacked[n - 1])
1099  const right = floor.width - 1 - floor.centre[n - 1]!
1100  const budget = width - floor.width
1101  const attempt = (spend: number): Plan => {
1102  const resources = [...gaps, right]
1103  let slack = spend
1104  const most = width + 8
1105
1106  // rows a label needs given `room` columns between its ends (or to the right edge), and how the
1107  // room maps back to the label's cap
1108  const capOf = (item: Item, room: number): number => {
1109    const step = item.step
1110    if (step.kind === 'note') return room + 1
1111    if (step.kind !== 'message') return room
1112    const a = lane.get(step.from)!
1113    const b = lane.get(step.to)!
1114    if (a === b) return a === n - 1 ? room - 4 : isSpilling(step, nested) ? room : room - 5
1115    return room - (b > a ? 3 : 5)
1116  }
1117  // A label that spills wraps against the right edge, whatever its gap; its gap only decides
1118  // whether the last line can sit on the arrow.
1119  const spillRoom = (item: Item): number | undefined => {
1120    const step = item.step
1121    if (!canSpill(step, nested, creates)) return undefined
1122    const lo = Math.min(lane.get(step.from)!, lane.get(step.to)!)
1123    return Math.max(1, width - floor.centre[lo]! - (lane.get(step.to)! > lane.get(step.from)! ? 2 : 4) - 2)
1124  }
1125  const spilled = (item: Item, room: number): number => {
1126    const step = item.step as Message
1127    const wrapped = wrap(item.text, spillRoom(item)!)
1128    if (wrapped.isCut) return 1e6
1129    const extra = (step.arrow === 'both' ? 1 : 0) + (step.isDashed ? DASHES : 0) + 5
1130    const shown = balanced(wrapped, item.text, room - extra)
1131    const last = shown.lines.at(-1) ?? ''
1132    return last !== '' && cellWidth(last) + extra <= room ? shown.lines.length : shown.lines.length + 1
1133  }
1134  const rowsAt = (item: Item, room: number): number => {
1135    const step = item.step
1136    if (spillRoom(item) !== undefined) return spilled(item, room)
1137    const cap = capOf(item, room)
1138    if (cap < Math.max(item.pieceCap, 1)) return 1e6
1139    const wrapped = wrap(item.text, cap)
1140    if (wrapped.isCut) return 1e6
1141    if (step.kind !== 'message') return Math.max(1, wrapped.lines.length)
1142    if (step.from === step.to) return Math.max(2, wrapped.lines.length)
1143    const extra = (step.arrow === 'both' ? 1 : 0) + (step.isDashed ? DASHES : 0) + 5
1144    const fits = (line: string) => line !== '' && cellWidth(line) + extra <= room
1145    const shown = balanced(wrapped, item.text, room - extra)
1146    return fits(shown.lines.at(-1) ?? '') ? shown.lines.length : shown.lines.length + 1
1147  }
1148  const roomOf = (lo: number, hi: number) => {
1149    let room = 0
1150    for (let i = lo; i < hi; i++) room += resources[i]!
1151    return room
1152  }
1153  const left = floor.centre[0]!
1154  const claims: Claim[] = free.map(item => {
1155    const step = item.step
1156    let lo = 0
1157    let hi = 0
1158    let against: number | undefined
1159    if (step.kind === 'message') {
1160      const a = lane.get(step.from)!
1161      const b = lane.get(step.to)!
1162      if (a === b && a === n - 1) [lo, hi] = [n - 1, n]
1163      else if (a === b && isSpilling(step, nested)) against = a
1164      else if (a === b) [lo, hi] = [a, a + 1]
1165      else [lo, hi] = [Math.min(a, b), Math.max(a, b)]
1166    } else if (step.kind === 'note') {
1167      const over = step.over.flatMap(id => lane.get(id) ?? []).sort((x, y) => x - y)
1168      ;[lo, hi] = [over[0]!, over.at(-1)!]
1169    }
1170    return { item, lo, hi, against, memo: new Map() }
1171  })
1172  const sign = (claim: Claim, r: number) => (claim.against !== undefined ? (r < claim.against ? -1 : 0) : claim.lo <= r && r < claim.hi ? 1 : 0)
1173  const rowsFor = (claim: Claim, room: number) => {
1174    const hit = claim.memo.get(room)
1175    if (hit !== undefined) return hit
1176    const rows = rowsAt(claim.item, Math.min(room, most))
1177    claim.memo.set(room, rows)
1178    return rows
1179  }
1180  const current = claims.map(claim => (claim.against !== undefined ? width - left - roomOf(0, claim.against) - 6 : roomOf(claim.lo, claim.hi)))
1181  const touching = resources.map((_, r) => claims.flatMap((claim, k) => (sign(claim, r) !== 0 ? [k] : [])))
1182  while (slack > 0) {
1183    let pick: { r: number; k: number; score: number } | undefined
1184    for (let r = 0; r < resources.length; r++) {
1185      const touched = touching[r]!
1186      if (!touched.some(k => sign(claims[k]!, r) > 0)) continue
1187      const now = touched.reduce((sum, k) => sum + rowsFor(claims[k]!, current[k]!), 0)
1188      for (let k = 1; k <= Math.min(slack, STEP_MOST); k++) {
1189        const then = touched.reduce((sum, c) => sum + rowsFor(claims[c]!, current[c]! + sign(claims[c]!, r) * k), 0)
1190        const saved = now - then
1191        if (saved <= 0) continue
1192        const score = saved / k
1193        if (!pick || score > pick.score) pick = { r, k, score }
1194      }
1195    }
1196    if (!pick) break
1197    resources[pick.r]! += pick.k
1198    slack -= pick.k
1199    for (const k of touching[pick.r]!) current[k]! += sign(claims[k]!, pick.r) * pick.k
1200  }

1export type Segment = { kind: 'text'; text: string } | { kind: 'sequence'; source: string; fence: string } | { kind: 'other'; type: string }
2
3export type Fence = { from: number; to: number; source: string; indent: number; quotes: number }
4
5type Open = { char: string; length: number; indent: number; container: number; isMermaid: boolean; from: number; quotes: number; lead: number }
6
7const OPENER = /^( *)(`{3,}|~{3,})(.*)$/
8const LIST_ITEM = /^( *)(?:[-*+]|\d{1,9}[.)])( +|$)/
9const MERMAID_INFO = /^mermaid(?:[ \t]|$)/
10
11const QUOTE = /^ {0,3}> ?/
12const COMMENT_START = /^ {0,3}<!--/
13// CommonMark HTML blocks of type 6 run to the next blank line, and a fence inside one is raw HTML.
14const HTML_BLOCK =
15  /^ {0,3}<\/?(?:address|article|aside|base|basefont|blockquote|body|caption|center|col|colgroup|dd|details|dialog|dir|div|dl|dt|fieldset|figcaption|figure|footer|form|frame|frameset|h[1-6]|head|header|hr|html|iframe|legend|li|link|main|menu|menuitem|nav|noframes|ol|optgroup|option|p|param|search|section|summary|table|tbody|td|tfoot|th|thead|title|tr|track|ul)(?:[\s/>]|$)/i
16
17const quotesOf = (line: string) => {
18  let count = 0
19  let rest = line
20  for (let found = QUOTE.exec(rest); found; found = QUOTE.exec(rest)) {
21    rest = rest.slice(found[0].length)
22    count++
23  }
24  return count
25}
26
27function unquoted(line: string, levels: number, lead = 0): string | undefined {
28  if (lead > 0 && indentOf(line) < lead && line.trim() !== '') return undefined
29  let rest = dedent(line, lead)
30  for (let i = 0; i < levels; i++) {
31    const found = QUOTE.exec(rest)
32    if (!found) return undefined
33    rest = rest.slice(found[0].length)
34  }
35  return rest
36}
37
38const indentOf = (line: string) => line.length - line.trimStart().length
39
40const trimBlankLines = (text: string) => text.replace(/^(?:[ \t]*\n)+/, '').replace(/(?:\n[ \t]*)+$/, '')
41
42function dedent(line: string, by: number): string {
43  let cut = 0
44  while (cut < by && line[cut] === ' ') cut++
45  return line.slice(cut)
46}
47
48function opener(line: string, container: number): Open | undefined {
49  const found = OPENER.exec(line)
50  if (!found) return undefined
51  const indent = found[1]!.length
52  const [char, info] = [found[2]![0]!, found[3]!.trim()]
53  if (indent - container > 3 || indent < container) return undefined
54  if (char === '`' && info.includes('`')) return undefined
55  return { char, length: found[2]!.length, indent, container, isMermaid: MERMAID_INFO.test(info), from: 0, quotes: 0, lead: 0 }
56}
57
58function closes(line: string, open: Open): boolean {
59  const indent = indentOf(line)
60  const rest = line.trim()
61  if (indent - open.container > 3 || rest.length < open.length) return false
62  return [...rest].every(char => char === open.char)
63}
64
65export function fencesOf(markdown: string): Fence[] {
66  const lines = markdown.replace(/\r\n?/g, '\n').split('\n')
67  const fences: Fence[] = []
68  let open: Open | undefined
69  let list = 0
70  let isComment = false
71  let isHtml = false
72
73  const finish = (at: number, end: number) => {
74    if (open?.isMermaid) {
75      const { quotes: levels, indent, lead } = open
76      const body = lines.slice(open.from + 1, end).map(inner => dedent(unquoted(inner, levels, lead) ?? '', indent))
77      fences.push({ from: open.from, to: at, source: body.join('\n'), indent, quotes: levels })
78    }
79    open = undefined
80  }
81
82  for (const [at, raw] of lines.entries()) {
83    if (open) {
84      const line = unquoted(raw, open.quotes, open.lead)
85      if (line === undefined) {
86        finish(at - 1, at)
87      } else if (open.container > 0 && line.trim() !== '' && indentOf(line) < open.container) {
88        finish(at - 1, at)
89        list = 0
90      } else {
91        if (closes(line, open)) finish(at, at)
92        continue
93      }
94    }
95    if (isComment || COMMENT_START.test(raw)) {
96      const after: string = isComment ? raw : raw.slice(raw.indexOf('<!--') + 4)
97      isComment = !after.includes('-->')
98      continue
99    }
100    if (isHtml || HTML_BLOCK.test(raw)) {
101      isHtml = raw.trim() !== ''
102      continue
103    }
104    const quotes = quotesOf(raw)
105    const line = unquoted(raw, quotes)!
106    if (quotes > 0) {
107      const inner = LIST_ITEM.exec(line)
108      const width = inner ? inner[0].length : 0
109      const found = opener(inner ? ' '.repeat(width) + line.slice(width) : line, width)
110      if (found) open = { ...found, from: at, quotes }
111      continue
112    }
113    const item = LIST_ITEM.exec(line)
114    const quotedItem = item ? quotesOf(line.slice(item[0].length)) : 0
115    if (item && quotedItem > 0) {
116      list = item[0].length
117      const found = opener(unquoted(line.slice(list), quotedItem)!, 0)
118      if (found) open = { ...found, from: at, quotes: quotedItem, lead: list }
119      continue
120    }
121    if (item) list = item[0].length
122    else if (line.trim() !== '' && indentOf(line) < list) list = 0
123    const container = item || indentOf(line) >= list ? list : 0
124    const found = opener(item ? ' '.repeat(list) + line.slice(list) : line, container)
125    if (found) open = { ...found, from: at }
126  }
127
128  return fences
129}
130
131// Each piece is drawn by its own next(), so a diagram inside a list restarts the list after it.
132export function segmentsOf(markdown: string, typeOf: (source: string) => string): Segment[] {
133  const lines = markdown.replace(/\r\n?/g, '\n').split('\n')
134  const parts: Segment[] = []
135  let pending: string[] = []
136  let at = 0
137  const flush = () => {
138    const text = trimBlankLines(pending.join('\n'))
139    if (text.trim() !== '') parts.push({ kind: 'text', text })
140    pending = []
141  }
142  for (const fence of fencesOf(markdown)) {
143    const fenceLines = lines.slice(fence.from, fence.to + 1)
144    const raw = fence.quotes > 0 ? fenceLines : fenceLines.map(line => dedent(line, fence.indent))
145    pending.push(...lines.slice(at, fence.from))
146    at = fence.to + 1
147    const type = typeOf(fence.source)
148    if (type === 'sequence') {
149      flush()
150      parts.push({ kind: 'sequence', source: fence.source, fence: raw.join('\n') })
151    } else {
152      pending.push(...raw)
153      flush()
154      parts.push({ kind: 'other', type })
155    }
156  }
157  pending.push(...lines.slice(at))
158  flush()
159  return parts
160}
161

1const WIDE = /[ᄀ-ᅟ⌚⌛〈〉⏩-⏬⏰⏳◽◾☔☕♈-♓♿⚓⚡⚪⚫⚽⚾⛄⛅⛎⛔⛪⛲⛳⛵⛺⛽✅✊✋✨❌❎❓-❕❗➕-➗➰➿⬛⬜⭐⭕⺀-〾ぁ-㏿㐀-䶿一-鿿ꀀ-꓏ꥠ-꥿가-힣豈-﫿︐-︙︰-﹯＀-｠￠-￦]|[\u{1f000}-\u{1faff}\u{20000}-\u{3fffd}]/u
2
3const ZERO = /^(?:\p{Mn}|\p{Me}|\p{Cf}|\p{Cc})+$/u
4
5const segmenter = new Intl.Segmenter(undefined, { granularity: 'grapheme' })
6
7function graphemeWidth(grapheme: string): number {
8  if (ZERO.test(grapheme)) return 0
9  return WIDE.test(grapheme) || grapheme.includes('️') ? 2 : 1
10}
11
12const NARROW = /^[\x20-\x7e\u00a0\u2026\u2190-\u21ff\u2500-\u25fc]*$/
13
14const widths = new Map<string, number>()
15
16export function cellWidth(text: string): number {
17  if (NARROW.test(text)) return text.length
18  const hit = widths.get(text)
19  if (hit !== undefined) return hit
20  let width = 0
21  for (const { segment } of segmenter.segment(text)) width += graphemeWidth(segment)
22  if (widths.size > 20000) widths.clear()
23  widths.set(text, width)
24  return width
25}
26