Chapter 1: Introduction

Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>

1 files changed, 436 insertions, 0 deletions

diff --git a/graph/web/layout.js b/graph/web/layout.js
new file mode 100644
index 00000000..bd164854
--- /dev/null
+++ b/graph/web/layout.js
@@ -0,0 +1,436 @@
+// Convert a snapshot to ELK geometry. The compiler's graph stays untouched.
+class GraphLayout {
+  constructor() {
+    this.elk = new ELK({workerUrl: "vendor/elk-worker.min.js"});
+    this.ctx = document.createElement("canvas").getContext("2d");
+    this.ctx.font = "12px sans-serif";
+  }
+
+  clip(text) {
+    const chars = Array.from((text || "").replace(/\s+/g, " "));
+    return chars.length > 44 ? chars.slice(0, 43).join("") + "…" : chars.join("");
+  }
+
+  async run(snap, evt, folded = new Set()) {
+    const view = GraphGroups.view(snap, folded);
+    snap = view.snap;
+    const raw = new Map(snap.nodes.map(n => [n.id, n]));
+    const outs = new Map();
+    for (const n of snap.nodes) for (const e of n.edges) if (!e.jump && raw.get(e.def)?.fold) {
+      if (!outs.has(e.def)) outs.set(e.def, new Set());
+      outs.get(e.def).add(n.id);
+    }
+    // The whole-program SCCP cycle is not source control flow.
+    const hidden = (n, e) => ["START", "UNIT"].includes(n.kind) && raw.get(e.def)?.kind === "STOP";
+    const nodes = snap.nodes.map(n => {
+      const label = `${this.clip(n.label)} #${n.id}${n.proj ? "/" + n.proj.idx : ""}`, type = this.clip(n.type);
+      // Detached control projections need only a small, single-line anchor.
+      const compact = ["START", "UNIT", "STOP"].includes(n.kind) ||
+        (n.kind === "CTRL" && n.proj && !raw.has(n.proj.par) && !n.type);
+      let w = Math.ceil(Math.max(120, this.ctx.measureText(label).width + 24 + (n.folding ? 60 : 0),
+        this.ctx.measureText(type).width + 24, (n.edges.length + 1) * 18));
+      const scope = n.kind === "SCOPE";
+      const cols = scope ? n.edges.map(e => Math.ceil(Math.max(48,
+        this.ctx.measureText(e.label || "[" + e.idx + "]").width + 24))) : [];
+      if (scope) w = Math.ceil(Math.max(120, this.ctx.measureText(label).width + 24,
+        cols.reduce((sum, w) => sum + w, 0)));
+      if (compact) w = Math.ceil(Math.max(72, this.ctx.measureText(label).width + 24,
+        (n.edges.filter(e => !hidden(n, e)).length + 1) * 18));
+      if (n.fold) {
+        w = Math.ceil(Math.max(160, w + 32, ((outs.get(n.id)?.size || 0) + 1) * 18));
+      }
+      return {id: "n" + n.id, width: w, height: compact ? 26 : scope ? 56 : 44,
+        ports: [], n, label, type, scope, cols, compact, stop: n.kind === "STOP", ox: 0, oy: 0};
+    });
+    const byId = new Map(nodes.map(n => [n.n.id, n]));
+    const parsing = evt?.phase === "Parse" && evt.kind !== "PHASE";
+    const roots = new Set(snap.roots);
+    const scopes = nodes.filter(n => n.scope);
+    const active = parsing ? byId.get(snap.scope) : null;
+    // Scope bindings count as users too. Scope ownership comes from parser
+    // roots; unfinished expression values are inferred from absent uses.
+    const used = new Set();
+    for (const n of snap.nodes) for (const e of n.edges) if (e.def) used.add(e.def);
+    const temps = new Set(evt?.temps);
+    const held = parsing ? nodes.filter(n =>
+      (n.n.proj || ["DATA", "MEM", "PHI"].includes(n.n.kind)) && !used.has(n.n.id) && !temps.has(n.n.id)) : [];
+    for (const n of held) n.held = true;
+    const owned = [...held, ...scopes.filter(n => parsing && roots.has(n.n.id))];
+    const projs = new Map();
+    for (const n of nodes) {
+      const par = byId.get(n.n.proj?.par);
+      // A projection without its parent still gets a standalone box.
+      if (!par || par.n.proj || par.n.fold || n.n.fold) continue;
+      if (!projs.has(par)) projs.set(par, []);
+      projs.get(par).push(n);
+      n.par = par;
+    }
+    const phis = new Map();
+    for (const n of nodes) {
+      if (n.n.kind !== "PHI" || n.n.fold) continue;
+      const reg = byId.get(n.n.edges.find(e => e.idx === 0)?.def);
+      if (!reg || reg.n.fold || !["REGION", "LOOP", "FUN"].includes(reg.n.kind)) continue;
+      if (!phis.has(reg)) phis.set(reg, []);
+      phis.get(reg).push(n);
+      n.reg = reg;
+    }
+    const jumps = [];
+    const groups = nodes.filter(n => !n.par && !n.reg).map(n => {
+      const slots = (projs.get(n) || []).sort((a, b) => a.n.proj.idx - b.n.proj.idx || a.n.id - b.n.id);
+      const parts = [n, ...slots];
+      if (slots.length) {
+        const w = slots.reduce((sum, p) => sum + p.width, 0);
+        n.width = Math.max(n.width, w);
+        const extra = (n.width - w) / slots.length;
+        let x = 0;
+        for (const p of slots) {
+          p.width += extra;
+          p.ox = x;
+          p.oy = n.height;
+          x += p.width;
+        }
+      }
+      // ELK sees one row; the renderer keeps each Region/Phi as a separate box.
+      let width = n.width;
+      for (const p of phis.get(n) || []) {
+        p.ox = width + 32;
+        width = p.ox + p.width;
+        parts.push(p);
+      }
+      // Shortcuts occupy a small local strip of this box. They never connect
+      // ELK to the remote function or Return and thus cannot order functions.
+      const links = [];
+      for (const p of parts) for (const e of p.n.edges) if (e.jump) {
+        const label = `↗ ${this.clip(view.raw.get(e.jump).label)} #${e.jump}`;
+        links.push({id: `j${p.n.id}f${e.jump}`, box: n.id, use: p.n.id, target: e.jump,
+          slot: e.idx, refs: e.refs, role: e.role, label,
+          x: width + 24, y: links.length * 28, height: 22,
+          width: Math.ceil(this.ctx.measureText(label).width + 20)});
+      }
+      jumps.push(...links);
+      const ports = [];
+      for (const p of parts) {
+        p.cell = slots.length > 0 && !p.reg;
+        const extra = p.scope && p.cols.length ?
+          (p.width - p.cols.reduce((sum, w) => sum + w, 0)) / p.cols.length : 0;
+        let x = 0;
+        for (const [idx, e] of p.n.edges.entries()) {
+          if (hidden(p.n, e)) continue;
+          // The parent/projection link is represented by the shared box.
+          if (p.par && e.idx === 0 && e.def === p.par.n.id) continue;
+          // Phi's Region input is a local left-facing marker, not a routed edge.
+          if (p.reg && e.idx === 0) continue;
+          if (p.scope) {
+            const span = p.cols[idx] + extra;
+            ports.push({id: p.id + "i" + e.idx, x: x + span / 2 - 3, y: -3, span,
+              width: 6, height: 6, layoutOptions: {"elk.port.side": "NORTH"}});
+            x += span;
+            continue;
+          }
+          const off = p.n.kind === "PHI" ? 0 : 1;
+          const slot = p.n.fold ? e.idx : e.refs.reduce((sum, r) => sum + r.idx, 0) / e.refs.length;
+          ports.push({id: p.id + "i" + e.idx, x: p.ox + p.width * (slot + off) / ((p.n.fold ? p.n.edges.length : p.n.slots) + off) - 3,
+            y: p.oy - 3, width: 6, height: 6, layoutOptions: {"elk.port.side": "NORTH"}});
+        }
+        // Direct uses of the MultiNode attach to its header, projections below.
+        const side = p === n && slots.length ? "EAST" : "SOUTH";
+        ports.push({id: p.id + "o", x: p.ox + (side === "EAST" ? p.width : p.width / 2) - 3,
+          y: p.oy + (side === "EAST" ? p.height / 2 : p.height) - 3,
+          width: 6, height: 6, layoutOptions: {"elk.port.side": side}});
+        const defs = [...(outs.get(p.n.id) || [])];
+        for (const [i, id] of defs.entries()) ports.push({id: p.id + "o" + id,
+          x: p.width * (i + 1) / (defs.length + 1) - 3, y: p.height - 3,
+          width: 6, height: 6, layoutOptions: {"elk.port.side": "SOUTH"}});
+      }
+      const height = n.height + (slots.length ? Math.max(...slots.map(p => p.height)) : 0);
+      return {id: n.id, width: links.length ? width + 24 + Math.max(...links.map(j => j.width)) : width,
+        height: Math.max(height, links.length * 28), ports, parts};
+    });
+    const edges = [], backs = new Map();
+    for (const use of snap.nodes) {
+      for (const e of use.edges) {
+        if (!e.def || e.jump || hidden(use, e)) continue;
+        if (byId.get(use.id).reg && e.idx === 0) continue;
+        if (byId.get(use.id).par && e.idx === 0 && e.def === use.proj.par) continue;
+        const bundle = e.refs.length > 1;
+        const id = bundle ? `b${use.id}d${e.def}` : "e" + e.orig.use + "i" + e.orig.idx;
+        const reg = byId.get(use.edges[0]?.def)?.n;
+        // Focused documentation can omit the Loop but retain its backedge cue.
+        const back = !use.fold && (e.backedge === true || (e.idx === 2 &&
+          (use.kind === "LOOP" || (use.kind === "PHI" && reg?.kind === "LOOP"))));
+        const loop = back ? (use.kind === "LOOP" ? use.id : (reg?.kind === "LOOP" ? reg.id : 0)) : 0;
+        const wrap = loop && view.groups.has(loop) && !raw.get(loop).fold ? loop : 0;
+        if (wrap) backs.set(wrap, (backs.get(wrap) || 0) + 1);
+        edges.push({id, use: use.id, def: e.def, idx: e.orig.idx, orig: e.orig, refs: e.refs, bundle, role: e.role, label: e.label,
+          bind: use.kind === "SCOPE", wrap,
+          // Layout follows value/control flow downward. SVG arrows point back
+          // from use to def, matching Simple's actual edge direction.
+          sources: ["n" + e.def + "o" + (byId.get(e.def).n.fold ? use.id : "")], targets: ["n" + use.id + "i" + e.idx],
+          layoutOptions: {"elk.layered.priority.direction": back ? 0 : e.role === "CTRL" ? 10 : 1,
+            "elk.layered.priority.straightness": !back && e.role === "CTRL" ? 100 : 0}});
+      }
+    }
+    const opts = {
+      "elk.algorithm": "layered", "elk.direction": "DOWN", "elk.edgeRouting": "ORTHOGONAL",
+      "elk.hierarchyHandling": "INCLUDE_CHILDREN",
+      "elk.layered.nodePlacement.strategy": "NETWORK_SIMPLEX",
+      "elk.spacing.nodeNode": 32, "elk.layered.spacing.nodeNodeBetweenLayers": 48,
+      "elk.padding": "[top=24,left=24,bottom=24,right=24]",
+      "elk.separateConnectedComponents": held.length === 0,
+      // ELK 0.12's model-order presort fails on nested hierarchy edge dummies.
+      "elk.layered.considerModelOrder.strategy": view.open.length ? "NONE" : "NODES_AND_EDGES",
+      "elk.randomSeed": 1
+    };
+    const containers = new Map(view.open.map(g => [g.id, {id: "g" + g.id, children: [],
+      layoutOptions: {...opts, "elk.padding": `[top=${34 + (backs.get(g.id) || 0) * 8},left=12,bottom=12,right=${backs.has(g.id) ? 24 + backs.get(g.id) * 10 : 12}]`}}]));
+    const children = [];
+    const add = (par, box) => (containers.get(par)?.children || children).push(box);
+    for (const g of view.open) add(g.par, containers.get(g.id));
+    for (const {parts, ...box} of groups) {
+      const n = parts[0];
+      if (n.scope || n.stop) continue;
+      // The folded header replaces its own container inside the parent group.
+      const par = n.n.fold ? n.n.fold.par : view.home.get(n.n.id);
+      add(par, {...box, layoutOptions: {"elk.portConstraints": "FIXED_POS",
+        // LAST_SEPARATE conflicts with ELK's hierarchical boundary ports.
+        "elk.layered.layering.layerConstraint": parts.length === 1 && n.held ?
+          (view.open.length ? "LAST" : "LAST_SEPARATE") : "NONE"}});
+    }
+    const input = {
+      id: "root", children,
+      // Scope bindings and lifetime associations must not impose CFG ranks.
+      edges: edges.filter(e => e.role !== "ASSOC" && !e.bind && !byId.get(e.def).scope &&
+        !byId.get(e.use).stop && !byId.get(e.def).stop).map(e => ({
+        id: e.id, sources: e.sources, targets: e.targets, layoutOptions: e.layoutOptions
+      })),
+      layoutOptions: opts
+    };
+    // ELK expects an edge on the lowest container containing both endpoints.
+    const portBox = new Map(), parents = new Map();
+    const index = box => {
+      for (const p of box.ports || []) portBox.set(p.id, box);
+      for (const child of box.children || []) { parents.set(child, box); index(child); }
+    };
+    index(input);
+    const flow = input.edges;
+    input.edges = [];
+    for (const e of flow) {
+      const ancestors = new Set();
+      for (let p = parents.get(portBox.get(e.sources[0])); p; p = parents.get(p)) ancestors.add(p);
+      let p = parents.get(portBox.get(e.targets[0]));
+      while (!ancestors.has(p)) p = parents.get(p);
+      (p.edges ||= []).push(e);
+    }
+    const graph = await this.elk.layout(input);
+    // Place scopes and Stops after the flow graph; their ports stay local.
+    for (const g of groups.filter(g => g.parts[0].scope || g.parts[0].stop))
+      graph.children.push({...g, x: 0, y: 0});
+    const boxes = new Map(), routes = new Map();
+    const collect = (box, x, y) => {
+      box.x = (box.x || 0) + x; box.y = (box.y || 0) + y;
+      boxes.set(box.id, box);
+      for (const e of box.edges || []) routes.set(e.id, {e, box});
+      for (const child of box.children || []) collect(child, box.x, box.y);
+    };
+    collect(graph, 0, 0);
+    for (const group of groups) {
+      const box = boxes.get(group.id);
+      const ports = new Map(box.ports.map(p => [p.id, p]));
+      for (const n of group.parts) {
+        n.x = box.x + n.ox; n.y = box.y + n.oy;
+        // Keep semantic nodes/slots intact for selection and neighborhood marks.
+        n.ports = n.n.edges.map(e => {
+          if (n.reg && e.idx === 0)
+            return {id: n.id + "i0", x: -6, y: n.height / 2 - 3, width: 6, height: 6, reg: true, edge: e};
+          const p = ports.get(n.id + "i" + e.idx);
+          return p && {...p, x: p.x - n.ox, y: p.y - n.oy, edge: e};
+        }).filter(Boolean);
+        const out = ports.get(n.id + "o");
+        n.ports.push({...out, x: out.x - n.ox, y: out.y - n.oy});
+        for (const id of outs.get(n.n.id) || []) n.ports.push(ports.get(n.id + "o" + id));
+      }
+    }
+    // Saved scopes describe suspended parser states at their control points.
+    // Keep a common column, nudging down only when two name tables overlap.
+    const ctrlY = n => {
+      const ctrl = byId.get(n.n.edges.find(e => e.label === "$ctrl" || e.idx === 0)?.def);
+      return ctrl ? ctrl.y + ctrl.height + 24 : 24;
+    };
+    const saved = scopes.filter(n => n !== active).sort((a, b) => ctrlY(a) - ctrlY(b) || a.n.id - b.n.id);
+    if (saved.length) {
+      const x = graph.width + 48;
+      let y = 24;
+      for (const n of saved) {
+        n.x = x;
+        n.y = Math.max(y, ctrlY(n));
+        y = n.y + n.height + 24;
+      }
+      graph.width = x + Math.max(...saved.map(n => n.width)) + 24;
+      graph.height = Math.max(graph.height, y);
+    }
+    // The active scope moves with the parser, below the current graph.
+    if (active) {
+      graph.width = Math.max(graph.width, active.width + 48);
+      active.x = (graph.width - active.width) / 2;
+      active.y = graph.height + 24;
+      graph.height = active.y + active.height + 24;
+    }
+    // Parser ownership is an overlay, never an IR node or an ELK flow edge.
+    const parser = owned.length ? {width: Math.max(180, (owned.length + 1) * 18), height: 36} : null;
+    // Stack Stop inputs before their collector: StopCUs above the outer Stop.
+    // Peers share a row, so adding CUs costs width rather than another level.
+    const pending = new Set(nodes.filter(n => n.stop)), rows = [];
+    while (pending.size) {
+      const row = [...pending].filter(n => !n.n.edges.some(e => pending.has(byId.get(e.def))));
+      // A malformed cycle should still be drawable.
+      if (!row.length) row.push(...pending);
+      for (const n of row) pending.delete(n);
+      rows.push({nodes: row, width: row.reduce((sum, n) => sum + n.width, 0) + (row.length - 1) * 32,
+        height: Math.max(...row.map(n => n.height))});
+    }
+    const stops = rows.length ? {width: Math.max(...rows.map(r => r.width)),
+      height: rows.reduce((sum, r) => sum + r.height, 0) + (rows.length - 1) * 32} : null;
+    // The whole Stop stack stays below the flow graph, beside the Parser.
+    const foot = [...(stops ? [stops] : []), ...(parser ? [parser] : [])];
+    if (foot.length) {
+      const width = foot.reduce((sum, n) => sum + n.width, 0) + (foot.length - 1) * 32;
+      const height = Math.max(...foot.map(n => n.height));
+      graph.width = Math.max(graph.width, width + 48);
+      let x = (graph.width - width) / 2;
+      for (const n of foot) {
+        n.x = x;
+        n.y = graph.height + 24 + height - n.height;
+        x += n.width + 32;
+      }
+      graph.height += height + 48;
+    }
+    if (stops) {
+      let y = stops.y;
+      for (const row of rows) {
+        let x = stops.x + (stops.width - row.width) / 2;
+        for (const n of row.nodes) {
+          n.x = x;
+          n.y = y;
+          x += n.width + 32;
+        }
+        y += row.height + 32;
+      }
+    }
+    if (parser) {
+      owned.sort((a, b) => a.x - b.x || a.n.id - b.n.id);
+      parser.ports = owned.map((n, i) => ({id: "parser-i" + n.n.id,
+        x: parser.width * (i + 1) / (owned.length + 1) - 3, y: -3}));
+      for (const n of owned) edges.push({id: "parser-hold-" + n.n.id, scope: n.scope, active: n === active,
+        use: 0, def: n.n.id, role: "PARSER", sources: [n.id + "o"], targets: ["parser-i" + n.n.id]});
+    }
+    // Each expanded loop reserves a clear gutter on its right. Route the
+    // endpoint leads around node boxes, then join them along that gutter.
+    const obstacles = groups.filter(g => !g.parts[0].scope && !g.parts[0].stop).map(g => boxes.get(g.id));
+    const lanes = new Map();
+    for (const e of edges) {
+      if (e.role === "ASSOC" || e.role === "PARSER" || e.bind || byId.get(e.def).scope ||
+          byId.get(e.use)?.stop || byId.get(e.def).stop) {
+        const def = byId.get(e.def), use = e.role === "PARSER" ? parser : byId.get(e.use);
+        const a = def.ports.find(p => p.id === e.sources[0]);
+        const b = use.ports.find(p => p.id === e.targets[0]);
+        const x = def.x + a.x + 3, y = def.y + a.y + 3;
+        const u = use.x + b.x + 3, v = use.y + b.y + 3;
+        e.path = `M${x},${y} C${x},${y + 24} ${u},${v - 24} ${u},${v}`;
+      } else {
+        const route = routes.get(e.id), origin = boxes.get(route.e.container) || route.box;
+        e.path = route.e.sections.map(s => this.roundedPath(
+          [s.startPoint, ...(s.bendPoints || []), s.endPoint]
+            .map(p => ({x: p.x + origin.x, y: p.y + origin.y})))).join(" ");
+      }
+      if (e.wrap) {
+        const box = boxes.get("g" + e.wrap), i = lanes.get(e.wrap) || 0;
+        lanes.set(e.wrap, i + 1);
+        const def = byId.get(e.def), use = byId.get(e.use);
+        const a = def.ports.find(p => p.id === e.sources[0]), b = use.ports.find(p => p.id === e.targets[0]);
+        const start = {x: def.x + a.x + 3, y: def.y + a.y + 3};
+        const end = {x: use.x + b.x + 3, y: use.y + b.y + 3};
+        const east = a.layoutOptions["elk.port.side"] === "EAST";
+        const from = {x: start.x + (east ? 10 : 0), y: start.y + (east ? 0 : 10)};
+        const to = {x: end.x, y: end.y - 12 - (backs.get(e.wrap) - i - 1) * 8};
+        const right = box.x + box.width - 12 - i * 10;
+        const head = this.toRight(from, right, obstacles), tail = this.toRight(to, right, obstacles);
+        const pts = [start, ...head, ...tail.reverse(), end];
+        e.path = this.roundedPath(pts);
+        e.lane = right;
+      }
+    }
+    for (const j of jumps) {
+      const box = boxes.get(j.box), use = byId.get(j.use);
+      j.x += box.x; j.y += box.y;
+      const p = use.ports.find(p => p.id === use.id + "i" + j.slot);
+      const x = use.x + p.x + 3, y = use.y + p.y + 3;
+      j.path = this.roundedPath([{x: j.x, y: j.y + j.height / 2},
+        {x: j.x - 12, y: j.y + j.height / 2}, {x: j.x - 12, y: box.y - 18},
+        {x, y: box.y - 18}, {x, y}]);
+    }
+    return {width: graph.width, height: graph.height, nodes, edges, jumps, raw: view.raw, cover: view.cover,
+      groups: view.open.map(g => ({...g, ...boxes.get("g" + g.id), gid: g.id, n: view.raw.get(g.id)})),
+      parser, scope: active?.n.id || 0, scopes: new Set(owned.filter(n => n.scope).map(n => n.n.id)),
+      held: new Set(held.map(n => n.n.id))};
+  }
+
+  // Keep the orthogonal route, easing each bend without moving its endpoints.
+  // Half-segment limits prevent neighboring corners from overlapping on short
+  // routes. The radius fits inside the routing gutters' eight-pixel clearance.
+  roundedPath(points, radius = 8) {
+    const ps = points.filter((p, i) => !i || p.x !== points[i-1].x || p.y !== points[i-1].y);
+    if (!ps.length) return "";
+    let path = `M${ps[0].x},${ps[0].y}`;
+    for (let i = 1; i < ps.length - 1; i++) {
+      const a = ps[i-1], b = ps[i], c = ps[i+1];
+      const ux = b.x-a.x, uy = b.y-a.y, vx = c.x-b.x, vy = c.y-b.y;
+      if (ux*vy === uy*vx) { path += ` L${b.x},${b.y}`; continue; }
+      const before = Math.hypot(ux,uy), after = Math.hypot(vx,vy);
+      const r = Math.min(radius, before/2, after/2);
+      path += ` L${b.x-ux*r/before},${b.y-uy*r/before}` +
+        ` Q${b.x},${b.y} ${b.x+vx*r/after},${b.y+vy*r/after}`;
+    }
+    if (ps.length > 1) path += ` L${ps.at(-1).x},${ps.at(-1).y}`;
+    return path;
+  }
+
+  // An orthogonal lead to a right-side gutter. Search only the channels
+  // between boxes; this is routing geometry, not a second node layout.
+  toRight(start, right, boxes) {
+    const pad = 8;
+    const left = Math.min(start.x, right), end = Math.max(start.x, right);
+    const rects = boxes.map(b => ({l: b.x - pad, r: b.x + b.width + pad,
+      t: b.y - pad, b: b.y + b.height + pad})).filter(b => b.r > left && b.l < end);
+    const xs = [...new Set([start.x, right, ...rects.flatMap(b => [b.l, b.r])])]
+      .filter(x => x >= left && x <= end).sort((a,b) => a-b);
+    const ys = [...new Set([start.y, ...rects.flatMap(b => [b.t, b.b])])].sort((a,b) => a-b);
+    const w = xs.length, size = w * ys.length, first = ys.indexOf(start.y) * w + xs.indexOf(start.x);
+    const goal = xs.indexOf(right), dir = right >= start.x ? 1 : -1;
+    const prev = new Int32Array(size).fill(-1), todo = new Int32Array(size);
+    let read = 0, len = 1, last = -1;
+    todo[0] = first; prev[first] = first;
+    const clear = (x, y, u, v) => !rects.some(b => x === u ?
+      x > b.l && x < b.r && Math.max(y,v) > b.t && Math.min(y,v) < b.b :
+      y > b.t && y < b.b && Math.max(x,u) > b.l && Math.min(x,u) < b.r);
+    while (read < len) {
+      const at = todo[read++], x = at % w, y = Math.floor(at / w);
+      if (x === goal) { last = at; break; }
+      for (const [u,v] of [[x+dir,y], [x,y-1], [x,y+1]]) {
+        if (u < 0 || u >= w || v < 0 || v >= ys.length) continue;
+        const next = v*w+u;
+        if (prev[next] !== -1 || !clear(xs[x],ys[y],xs[u],ys[v])) continue;
+        prev[next] = at; todo[len++] = next;
+      }
+    }
+    // A transient overlapping box during parsing can close all channels.
+    if (last === -1) return [start, {x: right, y: start.y}];
+    const pts = [];
+    for (let at = last;; at = prev[at]) {
+      pts.push({x: xs[at % w], y: ys[Math.floor(at / w)]});
+      if (at === first) break;
+    }
+    pts.reverse();
+    return pts.filter((p,i) => !i || i === pts.length-1 ||
+      !((pts[i-1].x === p.x && p.x === pts[i+1].x) || (pts[i-1].y === p.y && p.y === pts[i+1].y)));
+  }
+}