Skip to content

armgit / bento

Public Imported from GitHub
0

Bento, the office suite that fits in a file

28.9 KB
Raw Blame
// SPDX-License-Identifier: MIT
// Copyright (c) 2026 The Bento authors
//
// A small layered (Sugiyama-style) layout for compound directed graphs.
// Written for mermaid.ts; pure, DOM-free and deterministic: the same input
// gives the same output byte for byte (no randomness, no Map-order surprises:
// every iteration order is the input order). A kernel candidate, with
// mermaid.ts: it imports nothing but the kernel's geometry TYPES.
//
// SUBGRAPHS, the way mermaid treats them:
//  · a subgraph none of whose members links outside it is laid out on its own
//    (in its own `direction`, or the parent's flipped: TB ⇄ LR, as mermaid
//    does) and then takes part in its parent as ONE node of its own size;
//  · a subgraph whose members DO link outside is a compound: its members take
//    part in the parent's layering and ordering, kept contiguous in every
//    layer, and its box is solved together with everything around it, so a
//    non-member never lands inside it. Edges between subgraphs get their bend
//    points in the space BETWEEN the boxes. (Mermaid ignores `direction` on
//    such a subgraph, and so do we.)
//
// The phases of one layered pass:
//  1. cycle breaking — depth-first from the sources; an edge that closes a
//     cycle is laid out reversed (it still draws its own way);
//  2. layer assignment — longest path, then sources pulled down next to their
//     first successor so a lone start node does not float at the top;
//  3. every rank is DOUBLED (dagre's trick): real nodes sit on even layers and
//     a labelled edge gets a dummy of its label's size on the odd layer in its
//     middle, so edge labels take up real space and never overlap a node;
//     longer edges get a chain of thin dummies, which become their bends. A
//     dummy belongs to the innermost subgraph holding both ends of its edge;
//  4. crossing reduction — barycentre sweeps down and up, keeping the best
//     ordering seen (crossings counted exactly with a Fenwick tree). The sort
//     key is hierarchical, so a subgraph's members stay contiguous, and a
//     subgraph's key is global, so sibling subgraphs keep one order in every
//     layer (otherwise their boxes could not both be rectangles);
//  5. coordinates — each layer, subgraph borders included, is placed at the
//     positions its neighbours' mean asks for, subject to the minimum
//     separations: isotonic regression, solved exactly by pool-adjacent-
//     violators, a few rounds. Then one longest-path pass over the separation
//     constraints, with each subgraph's left and right border as ONE variable
//     across all its layers, makes the result legal;
//  6. the direction (TB/BT/LR/RL) is a final transform of a TB layout.

import type { Box, Pt } from '../../../kernel/src/geom.ts'
export type { Box, Pt }

export type Dir = 'TB' | 'BT' | 'LR' | 'RL'

/** A node to place. `parent` is the id of the cluster it sits in (null = root). */
export interface LNode { id: string; w: number; h: number; parent: string | null }
/** A cluster (subgraph). `top` is the room its title needs above the content. */
export interface LCluster { id: string; parent: string | null; dir?: Dir; top: number; minW: number }
/** An edge between two node or cluster ids. `lw/lh` = the label's size (0 when none). */
export interface LEdge { from: string; to: string; minlen: number; lw: number; lh: number }

export interface LOpts { nodeGap: number; rankGap: number; pad: number; maxDummies: number }

export interface LResult {
  nodes: Map<string, Box>
  clusters: Map<string, Box>
  /** per input edge: the bend points between its two ends (absolute), and the
   *  label centre when it has a label. Endpoints are NOT included — they are
   *  derived on the node borders, the way slides' syncConnectors derives them. */
  edges: Array<{ bends: Pt[]; label?: Pt }>
  w: number
  h: number
  /** true when the dummy budget ran out and some long edges were left straight */
  capped: boolean
  /** subgraphs whose `direction` was ignored because their members link outside */
  ignoredDir: string[]
}

/** one entry of a layer. kind: 0 item, 1 bend, 2 label, 3 filler, 4 left border, 5 right border */
interface Ent { w: number; h: number; g: number; kind: number }
interface Sub { box: Box[]; groups: Box[]; bends: Map<number, Pt[]>; labels: Map<number, Pt>; w: number; h: number }
type LE = [number, number, number, number, number, number, number] // u v minlen lw lh edgeIndex group

const r2 = (v: number) => Math.round(v * 100) / 100

export function layout(nodes: LNode[], clusters: LCluster[], edges: LEdge[], dir: Dir, o: LOpts): LResult {
  const parentOf = new Map<string, string | null>()
  const cinfo = new Map<string, LCluster>()
  for (const c of clusters) { parentOf.set(c.id, c.parent); cinfo.set(c.id, c) }
  for (const n of nodes) parentOf.set(n.id, n.parent)
  const anc = (x: string): string[] => {
    const out: string[] = []
    for (let p = parentOf.get(x); p != null && out.length < 1000; p = parentOf.get(p)) out.push(p)
    return out
  }
  // a subgraph is COMPOUND when an edge has exactly one end strictly inside it
  // (an edge to the subgraph itself does not count)
  const compound = new Set<string>()
  for (const e of edges) {
    const A = anc(e.from), B = anc(e.to)
    for (const c of A) if (!B.includes(c) && c !== e.to) compound.add(c)
    for (const c of B) if (!A.includes(c) && c !== e.from) compound.add(c)
  }
  // the context an id is laid out in: its nearest non-compound ancestor (null = root)
  const ctxOf = (x: string): string | null => anc(x).find((c) => !compound.has(c)) ?? null
  const res: LResult = { nodes: new Map(), clusters: new Map(), edges: edges.map(() => ({ bends: [] })), w: 0, h: 0, capped: false, ignoredDir: [] }
  let budget = o.maxDummies
  const size = new Map<string, { w: number; h: number }>()
  for (const n of nodes) size.set(n.id, n)
  const cdir = new Map<string | null, Dir>([[null, dir]])
  // contexts, children before parents: deeper first, then input order
  const ctxs: Array<string | null> = clusters.filter((c) => !compound.has(c.id)).map((c) => c.id)
  ctxs.sort((a, b) => anc(b!).length - anc(a!).length)
  ctxs.push(null)
  for (const c of clusters) if (compound.has(c.id) && c.dir) res.ignoredDir.push(c.id)
  const dirOf = (k: string | null): Dir => {
    if (cdir.has(k)) return cdir.get(k)!
    const pd = dirOf(ctxOf(k!))
    const d = cinfo.get(k!)!.dir ?? (pd === 'TB' ? 'LR' : 'TB')
    cdir.set(k, d)
    return d
  }
  const subs = new Map<string | null, { sub: Sub; items: string[]; groups: string[] }>()
  for (const K of ctxs) {
    // items: nodes and non-compound subgraphs whose context is K; groups: compound subgraphs in K
    const items: string[] = [], groups: string[] = []
    for (const n of nodes) if (ctxOf(n.id) === K) items.push(n.id)
    for (const c of clusters) if (c.id !== K && ctxOf(c.id) === K) (compound.has(c.id) ? groups : items).push(c.id)
    const ii = new Map(items.map((id, i) => [id, i]))
    const gi = new Map(groups.map((id, i) => [id, i]))
    const grpOf = (id: string) => { const p = parentOf.get(id); return p != null && gi.has(p) ? gi.get(p)! : -1 }
    const gpar = groups.map(grpOf)
    // lift an endpoint into K: an item, or a compound group (drawn to its box)
    const lift = (x: string): { i?: number; g?: number } | null => {
      for (let cur: string | null | undefined = x; cur != null && cur !== K; cur = parentOf.get(cur)) {
        if (ii.has(cur)) return { i: ii.get(cur)! }
        if (gi.has(cur)) return cur === x ? { g: gi.get(cur)! } : null
      }
      return null
    }
    const inGroup = (i: number, g: number) => { for (let p = grpOf(items[i]); p >= 0; p = gpar[p]) if (p === g) return true; return false }
    const lifted: Array<[{ i?: number; g?: number }, { i?: number; g?: number }, number]> = []
    edges.forEach((e, k) => {
      const a = lift(e.from), b = lift(e.to)
      if (a && b) lifted.push([a, b, k])
    })
    // an edge to a compound subgraph's box is laid out against one of its
    // members: a source member for an edge coming in, a sink member going out
    const rep = (g: number, incoming: boolean): number => {
      let first = -1
      for (let i = 0; i < items.length; i++) {
        if (!inGroup(i, g)) continue
        if (first < 0) first = i
        if (!lifted.some(([a, b]) => a.i !== undefined && b.i !== undefined && inGroup(a.i, g) && inGroup(b.i, g) && (incoming ? b.i === i : a.i === i) && a.i !== b.i)) return i
      }
      return first
    }
    const chainG = (x: { i?: number; g?: number }): number[] => {
      const c: number[] = []
      for (let g = x.i !== undefined ? grpOf(items[x.i]) : gpar[x.g!]; g >= 0; g = gpar[g]) c.push(g)
      return c
    }
    const es: LE[] = []
    const toBox = new Set<number>()
    for (const [a, b, k] of lifted) {
      if (a.g !== undefined || b.g !== undefined) toBox.add(k)
      const u = a.i ?? rep(a.g!, false), v = b.i ?? rep(b.g!, true)
      if (u < 0 || v < 0 || u === v) continue
      const cb = chainG(b)
      const lca = chainG(a).find((g) => cb.includes(g)) ?? -1
      es.push([u, v, edges[k].minlen, edges[k].lw, edges[k].lh, k, lca])
    }
    const its = items.map((id) => ({ ...size.get(id)!, group: grpOf(id) }))
    const gs = groups.map((id, i) => ({ parent: gpar[i], top: cinfo.get(id)!.top, minW: cinfo.get(id)!.minW }))
    const sub = layered(its, gs, es, dirOf(K), o, () => budget, (n) => { budget -= n })
    if (sub.capped) res.capped = true
    // an edge drawn to a compound box was laid out against one of its members:
    // its bends belong to that member, not the box, so it is drawn straight
    for (const k of toBox) { sub.bends.delete(k); sub.labels.delete(k) }
    if (K !== null) {
      const c = cinfo.get(K)!
      size.set(K, { w: Math.max(sub.w + 2 * o.pad, c.minW + 2 * o.pad), h: sub.h + 2 * o.pad + c.top })
    }
    subs.set(K, { sub: { ...sub, w: sub.w, h: sub.h }, items, groups })
  }
  // top-down: absolute positions
  const place = (K: string | null, ox: number, oy: number) => {
    const { sub, items, groups } = subs.get(K)!
    let cx = ox, cy = oy
    if (K !== null) {
      const c = cinfo.get(K)!, sz = size.get(K)!
      cx = ox + o.pad + (sz.w - 2 * o.pad - sub.w) / 2
      cy = oy + o.pad + c.top
    }
    const abs = (b: Box): Box => ({ x: r2(cx + b.x), y: r2(cy + b.y), w: r2(b.w), h: r2(b.h) })
    groups.forEach((id, g) => res.clusters.set(id, abs(sub.groups[g])))
    items.forEach((id, i) => {
      const b = abs(sub.box[i])
      if (cinfo.has(id)) { res.clusters.set(id, b); place(id, b.x, b.y) } else res.nodes.set(id, b)
    })
    for (const [i, pts] of sub.bends) res.edges[i].bends = pts.map((p) => ({ x: r2(cx + p.x), y: r2(cy + p.y) }))
    for (const [i, p] of sub.labels) res.edges[i].label = { x: r2(cx + p.x), y: r2(cy + p.y) }
  }
  place(null, 0, 0)
  const root = subs.get(null)!.sub
  res.w = r2(root.w)
  res.h = r2(root.h)
  return res
}

/** Layered layout of one context: items, compound groups, edges. TB-space inside. */
function layered(
  items: Array<{ w: number; h: number; group: number }>,
  groups: Array<{ parent: number; top: number; minW: number }>,
  es: LE[],
  dir: Dir,
  o: LOpts,
  budget: () => number,
  spend: (n: number) => void,
): Sub & { capped: boolean } {
  const horiz = dir === 'LR' || dir === 'RL'
  const N = items.length, G = groups.length
  const gpar = groups.map((g) => g.parent)
  // a group's padding in TB-space: the title sits on whichever side becomes the top
  const padTop = (g: number) => o.pad + (dir === 'TB' ? groups[g].top : 0)
  const padBot = (g: number) => o.pad + (dir === 'BT' ? groups[g].top : 0)
  const padLeft = (g: number) => o.pad + (horiz ? groups[g].top : 0)
  const out: number[][] = items.map(() => [])
  es.forEach(([u, v], k) => { if (u !== v) out[u].push(k) })
  // 1. cycle breaking: depth-first from the sources, in input order (a
  // flowchart's "reject → back to start" edge is the one reversed, as in
  // mermaid). A graph with no source — every node on a cycle — is entered at
  // the node with the most (out − in) edges, parallel edges counted.
  const deg = new Float64Array(N)
  const hasIn = new Uint8Array(N)
  es.forEach(([u, v]) => { if (u !== v) { deg[u]++; deg[v]--; hasIn[v] = 1 } })
  const roots = [...items.keys()].sort((a, b) => hasIn[a] - hasIn[b] || (hasIn[a] ? deg[b] - deg[a] : 0) || a - b)
  const rev = new Set<number>()
  const state = new Uint8Array(N) // 0 new, 1 on stack, 2 done
  for (const s of roots) {
    if (state[s]) continue
    const st: Array<[number, number]> = [[s, 0]]
    state[s] = 1
    while (st.length) {
      const top = st[st.length - 1]
      const [n, i] = top
      if (i < out[n].length) {
        top[1]++
        const k = out[n][i]
        const v = es[k][1]
        if (state[v] === 1) rev.add(k)
        else if (!state[v]) { state[v] = 1; st.push([v, 0]) }
      } else { state[n] = 2; st.pop() }
    }
  }
  const dag = es.map(([u, v, m], k): [number, number, number] => (rev.has(k) ? [v, u, m] : [u, v, m]))
  // 2. longest-path layering (Kahn, input order), minlen doubled
  const indeg = new Int32Array(N)
  const succ: number[][] = items.map(() => [])
  const dagIn = new Uint8Array(N)
  dag.forEach(([u, v], k) => { if (u !== v) { indeg[v]++; succ[u].push(k); dagIn[v] = 1 } })
  const layer = new Int32Array(N)
  const topo: number[] = []
  for (let i = 0; i < N; i++) if (!indeg[i]) topo.push(i)
  for (let q = 0; q < topo.length; q++) {
    const u = topo[q]
    for (const k of succ[u]) {
      const [, v, m] = dag[k]
      layer[v] = Math.max(layer[v], layer[u] + 2 * Math.max(1, m))
      if (!--indeg[v]) topo.push(v)
    }
  }
  // pull each source down to just above its nearest successor
  for (let q = topo.length - 1; q >= 0; q--) {
    const u = topo[q]
    if (dagIn[u] || !succ[u].length) continue
    let best = Infinity
    for (const k of succ[u]) best = Math.min(best, layer[dag[k][1]] - 2 * Math.max(1, dag[k][2]))
    if (best > layer[u] && best < Infinity) layer[u] = best
  }
  // 3. dummies: a chain per long edge; a labelled edge's middle dummy has the label's size
  const all: Ent[] = items.map((it) => ({ w: horiz ? it.h : it.w, h: horiz ? it.w : it.h, g: it.group, kind: 0 }))
  const lay: number[] = Array.from(layer)
  const chains = new Map<number, number[]>() // es index → dummy entry indices
  const adjUp: number[][] = all.map(() => [])
  const adjDn: number[][] = all.map(() => [])
  const add = (e: Ent, l: number) => { all.push(e); lay.push(l); adjUp.push([]); adjDn.push([]); return all.length - 1 }
  const link = (a: number, b: number) => { adjDn[a].push(b); adjUp[b].push(a) }
  let capped = false
  dag.forEach(([u, v], k) => {
    if (u === v) return
    const span = lay[v] - lay[u]
    const [, , , lw, lh, , grp] = es[k]
    if (span - 1 > budget()) { capped = true; link(u, v); return }
    spend(span - 1)
    const mid = lay[u] + (span >> 1) - ((span >> 1) % 2 === 0 ? 1 : 0)
    const chain: number[] = []
    let prev = u
    for (let l = lay[u] + 1; l < lay[v]; l++) {
      const lab = lw > 0 && l === mid
      const id = add(lab ? { w: horiz ? lh : lw, h: horiz ? lw : lh, g: grp, kind: 2 } : { w: 2, h: 0, g: grp, kind: 1 }, l)
      chain.push(id)
      link(prev, id)
      prev = id
    }
    link(prev, v)
    chains.set(k, rev.has(k) ? chain.reverse() : chain)
  })
  // groups: root-first ancestor chains, layer spans, and a filler wherever a
  // group spans a layer it has nothing in (else a stranger could sit inside its box)
  const up = (g: number) => { const c: number[] = []; for (; g >= 0; g = gpar[g]) c.unshift(g); return c }
  const gchain = groups.map((_, g) => up(g))
  const lo = new Array<number>(G).fill(Infinity), hi = new Array<number>(G).fill(-Infinity)
  const has = new Set<number>() // g * Lmax + l
  let Lmax = 0
  for (const l of lay) Lmax = Math.max(Lmax, l + 1)
  const mark = (g: number, l: number) => { for (const x of gchain[g]) { lo[x] = Math.min(lo[x], l); hi[x] = Math.max(hi[x], l); has.add(x * Lmax + l) } }
  all.forEach((e, n) => { if (e.g >= 0) mark(e.g, lay[n]) })
  for (let g = G - 1; g >= 0; g--) for (let l = lo[g]; l <= hi[g]; l++) if (!has.has(g * Lmax + l)) { add({ w: 0, h: 0, g, kind: 3 }, l); mark(g, l) }
  const chainOf = (n: number) => (all[n].g >= 0 ? gchain[all[n].g] : [])
  // 4. ordering: layers in DFS discovery order, then hierarchical barycentre sweeps
  const L = Lmax || 1
  const layers: number[][] = Array.from({ length: L }, () => [])
  const seen = new Uint8Array(all.length)
  for (let s = 0; s < N; s++) {
    if (seen[s] || dagIn[s]) continue
    const st = [s]
    while (st.length) {
      const n = st.pop()!
      if (seen[n]) continue
      seen[n] = 1
      layers[lay[n]].push(n)
      for (let i = adjDn[n].length - 1; i >= 0; i--) if (!seen[adjDn[n][i]]) st.push(adjDn[n][i])
    }
  }
  for (let s = 0; s < all.length; s++) if (!seen[s]) { seen[s] = 1; layers[lay[s]].push(s) }
  const pos = new Float64Array(all.length)
  const setPos = () => layers.forEach((ly) => ly.forEach((n, i) => { pos[n] = i }))
  setPos()
  const rel = (n: number) => (pos[n] + 0.5) / layers[lay[n]].length
  const nkey = new Float64Array(all.length)
  const gkey = new Float64Array(G)
  const sortLayer = (l: number) => {
    layers[l].sort((a, b) => {
      const ca = chainOf(a), cb = chainOf(b)
      let i = 0
      while (i < ca.length && i < cb.length && ca[i] === cb[i]) i++
      const ka = i < ca.length ? gkey[ca[i]] : nkey[a], kb = i < cb.length ? gkey[cb[i]] : nkey[b]
      return ka - kb || (i < ca.length ? ca[i] : G + pos[a]) - (i < cb.length ? cb[i] : G + pos[b])
    })
    layers[l].forEach((n, i) => { pos[n] = i })
  }
  const groupKeys = () => {
    const sum = new Float64Array(G), cnt = new Float64Array(G)
    all.forEach((_, n) => { for (const g of chainOf(n)) { sum[g] += rel(n); cnt[g]++ } })
    for (let g = 0; g < G; g++) gkey[g] = cnt[g] ? sum[g] / cnt[g] : 0
  }
  const crossings = () => {
    let c = 0
    for (let l = 0; l < L - 1; l++) {
      const pairs: Array<[number, number]> = []
      for (const n of layers[l]) for (const m of adjDn[n]) pairs.push([pos[n], pos[m]])
      pairs.sort((a, b) => a[0] - b[0] || a[1] - b[1])
      const size = layers[l + 1].length + 1
      const bit = new Int32Array(size + 1)
      for (let i = 0; i < pairs.length; i++) {
        // count earlier pairs whose lower end is to the right of this one's
        let s = 0
        for (let j = size; j > 0; j -= j & -j) s += bit[j]
        let le = 0
        for (let j = pairs[i][1] + 1; j > 0; j -= j & -j) le += bit[j]
        c += s - le
        for (let j = pairs[i][1] + 1; j <= size; j += j & -j) bit[j]++
      }
    }
    return c
  }
  // the first pass only makes groups contiguous and consistently ordered
  groupKeys()
  for (let n = 0; n < all.length; n++) nkey[n] = rel(n)
  for (let l = 0; l < L; l++) sortLayer(l)
  let best = layers.map((l) => l.slice())
  let bestC = crossings()
  for (let it = 0; it < 8 && bestC > 0; it++) {
    const down = it % 2 === 0
    groupKeys()
    for (let k = 1; k < L; k++) {
      const l = down ? k : L - 1 - k
      const nb = down ? adjUp : adjDn
      for (const n of layers[l]) {
        const ns = nb[n]
        nkey[n] = ns.length ? ns.reduce((s, m) => s + rel(m), 0) / ns.length : rel(n)
      }
      sortLayer(l)
    }
    const c = crossings()
    if (c < bestC) { bestC = c; best = layers.map((l) => l.slice()) }
  }
  for (let l = 0; l < L; l++) layers[l] = best[l]
  setPos()
  // 5. coordinates. Each layer becomes a token list with each group's left and
  // right borders as zero-width tokens around its members.
  const E0 = all.length
  const side = new Map<number, number>() // (g * L + l) * 2 + right → token entry
  const tokens: number[][] = layers.map((ly, l) => {
    const t: number[] = [], open: number[] = []
    const close = (keep: number) => { while (open.length > keep) { const g = open.pop()!; const id = add({ w: 0, h: 0, g, kind: 5 }, l); side.set((g * L + l) * 2 + 1, id); t.push(id) } }
    for (const n of ly) {
      const c = chainOf(n)
      let i = 0
      while (i < open.length && i < c.length && open[i] === c[i]) i++
      close(i)
      for (; i < c.length; i++) { const id = add({ w: 0, h: 0, g: c[i], kind: 4 }, l); side.set((c[i] * L + l) * 2, id); t.push(id); open.push(c[i]) }
      t.push(n)
    }
    close(0)
    return t
  })
  const half = (n: number) => (all[n].kind < 4 ? all[n].w / 2 : 0)
  const light = (n: number) => all[n].kind === 1 || all[n].kind === 2 || all[n].kind === 3
  const gap = (a: number, b: number) => {
    const A = all[a], B = all[b]
    if (A.kind === 4) return padLeft(A.g)
    if (B.kind === 5) return o.pad
    return light(a) && light(b) ? o.nodeGap / 4 : light(a) || light(b) ? o.nodeGap / 2 : o.nodeGap
  }
  const sep = (a: number, b: number) => half(a) + gap(a, b) + half(b)
  const x = new Float64Array(all.length)
  for (const t of tokens) {
    let cx = 0
    t.forEach((n, i) => { if (i) cx += sep(t[i - 1], n); x[n] = cx })
  }
  const place = (t: number[], want: (n: number) => number | null) => {
    if (!t.length) return
    // target_i = desired_i − offset_i must be non-decreasing: PAVA
    const off: number[] = [0]
    for (let i = 1; i < t.length; i++) off.push(off[i - 1] + sep(t[i - 1], t[i]))
    const blocks: Array<{ v: number; wt: number; n: number }> = []
    t.forEach((n, i) => {
      const w = want(n)
      const wt = all[n].kind >= 4 ? 4 : all[n].kind ? 2 : 1
      blocks.push({ v: (w ?? x[n]) - off[i], wt: w === null ? 0.01 : wt, n: 1 })
      while (blocks.length > 1 && blocks[blocks.length - 2].v >= blocks[blocks.length - 1].v) {
        const b = blocks.pop()!, a = blocks[blocks.length - 1]
        a.v = (a.v * a.wt + b.v * b.wt) / (a.wt + b.wt)
        a.wt += b.wt
        a.n += b.n
      }
    })
    let i = 0
    for (const b of blocks) for (let j = 0; j < b.n; j++, i++) x[t[i]] = b.v + off[i]
  }
  const mean = (ns: number[]) => (ns.length ? ns.reduce((s, m) => s + x[m], 0) / ns.length : null)
  // a border wants to line up with the same border one layer up and down
  const border = (n: number, l: number, dirs: number[]) => {
    const e = all[n], ns: number[] = []
    for (const d of dirs) { const m = side.get((e.g * L + l + d) * 2 + (e.kind - 4)); if (m !== undefined && l + d >= 0 && l + d < L) ns.push(m) }
    return mean(ns)
  }
  for (let round = 0; round < 6; round++) {
    const down = round % 2 === 0
    for (let k = 0; k < L; k++) {
      const l = down ? k : L - 1 - k
      const d = round === 5 ? [-1, 1] : [down ? -1 : 1]
      place(tokens[l], (n) => (all[n].kind >= 4 ? border(n, l, d) : all[n].kind === 3 ? null : mean(round === 5 ? adjUp[n].concat(adjDn[n]) : down ? adjUp[n] : adjDn[n])))
    }
  }
  // legalise: longest path over the separation constraints, a group's left
  // (and right) border being ONE variable in every layer it spans
  const V = E0 + 2 * G
  const vOf = (n: number) => (all[n].kind === 4 ? E0 + 2 * all[n].g : all[n].kind === 5 ? E0 + 2 * all[n].g + 1 : n)
  const val = new Float64Array(V).fill(-Infinity)
  for (let n = 0; n < E0; n++) val[n] = x[n]
  const outs: Array<Array<[number, number]>> = Array.from({ length: V }, () => [])
  const indg = new Int32Array(V)
  const need = (a: number, b: number, d: number) => { outs[a].push([b, d]); indg[b]++ }
  for (let n = E0; n < all.length; n++) if (all[n].kind === 4) val[vOf(n)] = Math.min(val[vOf(n)] === -Infinity ? Infinity : val[vOf(n)], x[n])
  for (let g = 0; g < G; g++) if (!horiz) need(E0 + 2 * g, E0 + 2 * g + 1, groups[g].minW + 2 * o.pad)
  for (const t of tokens) for (let i = 1; i < t.length; i++) need(vOf(t[i - 1]), vOf(t[i]), sep(t[i - 1], t[i]))
  const q: number[] = []
  for (let v = 0; v < V; v++) if (!indg[v]) q.push(v)
  const done = new Uint8Array(V)
  const relax = (v: number) => { done[v] = 1; for (const [w, d] of outs[v]) { if (val[v] + d > val[w]) val[w] = val[v] + d; if (!--indg[w]) q.push(w) } }
  for (let i = 0; i < q.length; i++) relax(q[i])
  for (let v = 0; v < V; v++) if (!done[v]) relax(v) // a cycle (should not happen): best effort
  // pull each left border in as far as its contents allow, innermost first
  for (const g of [...groups.keys()].sort((a, b) => gchain[b].length - gchain[a].length)) {
    const Lv = E0 + 2 * g
    let m = val[Lv + 1] - (horiz ? 0 : groups[g].minW) - 2 * o.pad
    for (const [w, d] of outs[Lv]) if (w !== Lv + 1) m = Math.min(m, val[w] - d)
    if (m > val[Lv]) val[Lv] = m
  }
  // then improve without ever breaking a constraint: shift each group whole
  // (members, nested groups and borders together) toward where its members
  // want to be, as far as its slack allows; then each entry alone, within its
  // neighbours; then pull the borders tight again
  const ins: Array<Array<[number, number]>> = Array.from({ length: V }, () => [])
  outs.forEach((os, v) => { for (const [w, d] of os) ins[w].push([v, d]) })
  const vch = (v: number) => (v < E0 ? chainOf(v) : gchain[(v - E0) >> 1])
  const mem: number[][] = groups.map(() => [])
  for (let v = 0; v < V; v++) for (const g of vch(v)) mem[g].push(v)
  const want = (v: number) => {
    const ns = all[v].kind < 3 ? adjUp[v].concat(adjDn[v]) : []
    return ns.length ? ns.reduce((s, m) => s + val[m], 0) / ns.length : null
  }
  const lower = (v: number, skip?: number) => ins[v].reduce((m, [u, d]) => (skip !== undefined && vch(u).includes(skip) ? m : Math.max(m, val[u] + d)), -Infinity)
  const upper = (v: number, skip?: number) => outs[v].reduce((m, [w, d]) => (skip !== undefined && vch(w).includes(skip) ? m : Math.min(m, val[w] - d)), Infinity)
  const outer = [...groups.keys()].sort((a, b) => gchain[a].length - gchain[b].length)
  for (let round = 0; round < 8; round++) {
    for (const g of outer) {
      let sum = 0, cnt = 0, lo = -Infinity, hi = Infinity
      for (const v of mem[g]) {
        const w = v < E0 ? want(v) : null
        if (w !== null) { sum += w - val[v]; cnt++ }
        lo = Math.max(lo, lower(v, g) - val[v])
        hi = Math.min(hi, upper(v, g) - val[v])
      }
      const d = cnt ? Math.max(lo, Math.min(hi, sum / cnt)) : 0
      if (d) for (const v of mem[g]) val[v] += d
    }
    for (let v = 0; v < E0; v++) {
      const w = want(v)
      if (w !== null) val[v] = Math.max(lower(v), Math.min(upper(v), w))
    }
    for (const g of [...outer].reverse()) {
      const Lv = E0 + 2 * g
      val[Lv] = Math.max(lower(Lv), upper(Lv))
      val[Lv + 1] = Math.min(upper(Lv + 1), lower(Lv + 1))
    }
  }
  for (let n = 0; n < E0; n++) x[n] = val[n]
  // y: layer thickness, plus room above and below for the groups that start or end there
  const extT = new Float64Array(G), extB = new Float64Array(G)
  for (const g of [...groups.keys()].sort((a, b) => gchain[b].length - gchain[a].length)) {
    extT[g] += padTop(g); extB[g] += padBot(g)
    const p = gpar[g]
    if (p >= 0) { if (lo[p] === lo[g]) extT[p] = Math.max(extT[p], extT[g]); if (hi[p] === hi[g]) extB[p] = Math.max(extB[p], extB[g]) }
  }
  const gapT = new Float64Array(L), gapB = new Float64Array(L)
  for (let g = 0; g < G; g++) if (lo[g] <= hi[g]) { gapT[lo[g]] = Math.max(gapT[lo[g]], extT[g]); gapB[hi[g]] = Math.max(gapB[hi[g]], extB[g]) }
  const ly = new Float64Array(L)
  let cy = 0
  for (let l = 0; l < L; l++) {
    const th = layers[l].reduce((m, n) => Math.max(m, all[n].h), 0)
    cy += (l ? o.rankGap / 2 + gapB[l - 1] : 0) + gapT[l]
    ly[l] = cy + th / 2
    cy += th
  }
  cy += L ? gapB[L - 1] : 0
  // group boxes in TB-space, innermost first
  const gb: Box[] = groups.map(() => ({ x: 0, y: Infinity, w: 0, h: -Infinity }))
  for (let n = 0; n < E0; n++) {
    const g = all[n].g
    if (g < 0) continue
    const b = gb[g]
    b.y = Math.min(b.y, ly[lay[n]] - all[n].h / 2)
    b.h = Math.max(b.h, ly[lay[n]] + all[n].h / 2)
  }
  for (const g of [...groups.keys()].sort((a, b) => gchain[b].length - gchain[a].length)) {
    const b = gb[g]
    b.y -= padTop(g); b.h += padBot(g)
    b.x = val[E0 + 2 * g]
    b.w = val[E0 + 2 * g + 1] - b.x
    const p = gpar[g]
    if (p >= 0) { gb[p].y = Math.min(gb[p].y, b.y); gb[p].h = Math.max(gb[p].h, b.h) }
    b.h -= b.y
  }
  let minX = Infinity, maxX = -Infinity
  for (let n = 0; n < E0; n++) { minX = Math.min(minX, x[n] - all[n].w / 2); maxX = Math.max(maxX, x[n] + all[n].w / 2) }
  for (const b of gb) { minX = Math.min(minX, b.x); maxX = Math.max(maxX, b.x + b.w) }
  if (!E0) minX = maxX = 0
  const TW = maxX - minX, TH = cy
  // 6. direction transform, of boxes (TB-space → final)
  const tr = (b: Box): Box => {
    const bx = b.x - minX
    if (dir === 'TB') return { x: bx, y: b.y, w: b.w, h: b.h }
    if (dir === 'BT') return { x: bx, y: TH - b.y - b.h, w: b.w, h: b.h }
    if (dir === 'LR') return { x: b.y, y: bx, w: b.h, h: b.w }
    return { x: TH - b.y - b.h, y: bx, w: b.h, h: b.w }
  }
  const at = (n: number): Pt => { const b = tr({ x: x[n], y: ly[lay[n]], w: 0, h: 0 }); return { x: b.x, y: b.y } }
  const box = items.map((_, n) => tr({ x: x[n] - all[n].w / 2, y: ly[lay[n]] - all[n].h / 2, w: all[n].w, h: all[n].h }))
  const bends = new Map<number, Pt[]>()
  const labels = new Map<number, Pt>()
  for (const [k, chain] of chains) {
    const k0 = es[k][5]
    bends.set(k0, chain.map(at))
    const lab = chain.find((n) => all[n].kind === 2)
    if (lab !== undefined) labels.set(k0, at(lab))
  }
  return { box, groups: gb.map(tr), bends, labels, w: horiz ? TH : TW, h: horiz ? TW : TH, capped }
}