From 7279862d57c97063eb46997804b5efb6c0b07189 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Thu, 24 Sep 2026 10:47:39 -0700 Subject: Bunch better layout options --- graph/web/groups.js | 22 ++++++++++++-- graph/web/index.html | 9 +++++- graph/web/layout.js | 56 +++++++++++++++++++++++++---------- graph/web/render.js | 84 ++++++++++++++++++++++++++++++++++++++++------------ 4 files changed, 132 insertions(+), 39 deletions(-) (limited to 'graph/web') diff --git a/graph/web/groups.js b/graph/web/groups.js index 6ee4e091..da14405f 100644 --- a/graph/web/groups.js +++ b/graph/web/groups.js @@ -19,20 +19,36 @@ class GraphGroups { for (const n of snap.nodes) { if (cover.get(n.id) !== n.id) continue; const fold = groups.has(n.id) && folded.has(n.id); - const v = {...n, edges: [], fold: fold ? groups.get(n.id) : null}; + const v = {...n, slots: n.edges.length, edges: [], fold: fold ? groups.get(n.id) : null}; if (fold) { v.proj = null; v.type = `${v.fold.members.size} nodes folded`; } nodes.push(v); byId.set(n.id, v); } + const bundles = new Map(), rank = {ASSOC: 0, DATA: 1, MEM: 2, CTRL: 3}; for (const n of snap.nodes) for (const e of n.edges) { const use = byId.get(cover.get(n.id)), def = cover.get(e.def) || 0; if (use.fold && (!def || def === use.id)) continue; - use.edges.push({...e, idx: use.fold ? use.edges.length : e.idx, def, - orig: {use: n.id, def: e.def, idx: e.idx}}); + const orig = {use: n.id, def: e.def, idx: e.idx, role: e.role, label: e.label}; + // During inlining the old function may disappear. Keep ordinary edges + // then; a shortcut needs a real, selectable function in this snapshot. + const jump = raw.get(e.jump)?.kind === "FUN" ? e.jump : 0; + const key = jump ? `j${use.id}:${jump}` : def && (use.fold || byId.get(def).fold) ? `${use.id}:${def}` : null; + const old = bundles.get(key); + if (old) { + old.refs.push(orig); + if (rank[e.role] > rank[old.role]) old.role = e.role; + old.label = null; + } else { + const edge = {...e, idx: use.fold ? use.edges.length : e.idx, def, jump, orig, refs: [orig]}; + use.edges.push(edge); + if (key) bundles.set(key, edge); + } } // Expanded groups only; a folded group is represented by its header box. + for (const n of nodes) if (n.kind === "SCOPE") for (const e of n.edges) + e.label = e.refs.map(r => r.label || `[${r.idx}]`).join(", "); const open = [...groups.values()].filter(g => !folded.has(g.id) && cover.get(g.id) === g.id); const depth = g => { let n = 0; diff --git a/graph/web/index.html b/graph/web/index.html index 909f7b1d..198db3ad 100644 --- a/graph/web/index.html +++ b/graph/web/index.html @@ -22,6 +22,8 @@ .edge.PARSER { stroke-dasharray:5 4; } .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; } .edge.selected { stroke-width:3.5; } + .edge.bundle { stroke-width:4; } + .edge.bundle.selected { stroke-width:6; } .node { cursor:pointer; } .box { stroke:#758191; stroke-width:1; } .node.held .box { stroke-dasharray:5 3; } @@ -34,8 +36,13 @@ .fold-btn rect { fill:white; stroke:#596674; } .fold-btn text { font-size:14px; fill:#152330; } .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; } - .head { font-size:10px; fill:#596674; } + .shortcut { cursor:pointer; } + .shortcut path { fill:none; stroke-width:1.5; } + .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; } + .shortcut text { font-size:11px; fill:#783030; } + .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; } .label { font-size:12px; fill:#152330; font-weight:600; } + .node-id { font-size:10px; fill:#596674; font-weight:400; } .type { font-size:11px; fill:#455768; } .port { stroke:#536477; stroke-width:1; } .row { stroke:#b6afcf; stroke-width:1; } diff --git a/graph/web/layout.js b/graph/web/layout.js index 53e26f53..68445a3b 100644 --- a/graph/web/layout.js +++ b/graph/web/layout.js @@ -16,14 +16,14 @@ class GraphLayout { 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 (raw.get(e.def)?.fold) { + 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(e.orig.def); + 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), type = this.clip(n.type); + const label = `#${n.id}${n.proj ? "/" + n.proj.idx : ""} ${this.clip(n.label)}`, type = this.clip(n.type); const compact = ["START", "UNIT", "STOP"].includes(n.kind); let w = Math.ceil(Math.max(120, this.ctx.measureText(label).width + 24, this.ctx.measureText(type).width + 24, (n.edges.length + 1) * 18)); @@ -32,13 +32,12 @@ class GraphLayout { 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(`#${n.id} ${label}`).width + 24, + 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) { - const slot = Math.max(18, ...n.edges.map(e => this.ctx.measureText(`${e.orig.use}:${e.orig.idx}`).width + 12)); - w = Math.ceil(Math.max(200, w + 32, (n.edges.length + 1) * slot, ((outs.get(n.id)?.size || 0) + 1) * 18)); + 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 : 62, + 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])); @@ -72,6 +71,7 @@ class GraphLayout { 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]; @@ -94,6 +94,17 @@ class GraphLayout { 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 = `↗ #${e.jump} ${this.clip(view.raw.get(e.jump).label)}`; + 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; @@ -114,7 +125,8 @@ class GraphLayout { continue; } const off = p.n.kind === "PHI" ? 0 : 1; - ports.push({id: p.id + "i" + e.idx, x: p.ox + p.width * (e.idx + off) / (p.n.edges.length + off) - 3, + 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. @@ -127,29 +139,34 @@ class GraphLayout { x: p.width * (i + 1) / (defs.length + 1) - 3, y: p.height - 3, width: 6, height: 6, layoutOptions: {"elk.port.side": "SOUTH"}}); } - return {id: n.id, width, height: n.height + (slots.length ? Math.max(...slots.map(p => p.height)) : 0), ports, parts}; + 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 = []; for (const use of snap.nodes) { for (const e of use.edges) { - if (!e.def || hidden(use, e)) continue; + 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 id = "e" + e.orig.use + "i" + e.orig.idx; + 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; const back = !use.fold && e.idx === 2 && (use.kind === "LOOP" || (use.kind === "PHI" && reg?.kind === "LOOP")); - edges.push({id, use: use.id, def: e.def, idx: e.orig.idx, orig: e.orig, role: e.role, label: e.label, + 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", // 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 ? e.orig.def : "")], targets: ["n" + use.id + "i" + e.idx], - layoutOptions: {"elk.layered.priority.direction": back ? 0 : e.role === "CTRL" ? 10 : 1}}); + 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, @@ -158,7 +175,7 @@ class GraphLayout { "elk.randomSeed": 1 }; const containers = new Map(view.open.map(g => [g.id, {id: "g" + g.id, children: [], - layoutOptions: {...opts, "elk.padding": "[top=58,left=28,bottom=28,right=28]"}}])); + layoutOptions: {...opts, "elk.padding": "[top=34,left=12,bottom=12,right=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)); @@ -315,7 +332,14 @@ class GraphLayout { .map((p, i) => `${i ? "L" : "M"}${p.x + origin.x},${p.y + origin.y}`).join(" ")).join(" "); } } - return {width: graph.width, height: graph.height, nodes, edges, raw: view.raw, cover: view.cover, + 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 = `M${j.x},${j.y + j.height / 2}H${j.x - 12}V${box.y - 18}H${x}V${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))}; diff --git a/graph/web/render.js b/graph/web/render.js index f0b622db..b1a294ec 100644 --- a/graph/web/render.js +++ b/graph/web/render.js @@ -20,6 +20,9 @@ class GraphView { this.links = this.world.append("g").attr("class", "edges"); this.parser = this.world.append("g").attr("class", "parser"); this.nodes = this.world.append("g").attr("class", "nodes"); + // Titles/buttons stay above crossing edges, even with narrow group margins. + this.heads = this.world.append("g").attr("class", "region-heads"); + this.shortcuts = this.world.append("g").attr("class", "shortcuts"); this.zoom = d3.zoom().scaleExtent([.02, 4]).on("zoom", event => { if (event.sourceEvent) this.auto = false; this.world.attr("transform", event.transform); @@ -45,24 +48,31 @@ class GraphView { const regions = this.regions.selectAll("g.region").data(scene.groups || [], g => g.gid).join(enter => { const g = enter.append("g").attr("class", "region"); g.append("rect").attr("class", "region-box").attr("rx", 8); - g.append("text").attr("class", "label").attr("x", 34).attr("y", 22); - g.append("title"); return g; }).attr("transform", g => `translate(${g.x},${g.y})`); regions.select("rect.region-box").attr("width", g => g.width).attr("height", g => g.height) - .attr("fill", g => g.n.kind === "LOOP" ? "#f1f6fc" : "#fff8ec"); - regions.select("text.label").text(g => (`#${g.gid} ${g.n.label}`).slice(0, Math.max(12, Math.floor((g.width-48)/7)))); - regions.select("title").text(g => `${g.n.label} · ${g.members.size} nodes`); - regions.each((g, i, items) => this.foldButton(d3.select(items[i]), g.gid, false, 8, 8)); + .attr("fill", g => g.n.kind === "LOOP" ? "#f1f6fc" : g.n.kind === "FUN" ? "#fff8ec" : "#f2f7ef"); + const heads = this.heads.selectAll("g.region-head").data(scene.groups || [], g => g.gid).join(enter => { + const g = enter.append("g").attr("class", "region-head"); + g.append("text").attr("class", "label").attr("x", 26).attr("y", 17); + g.append("title"); + return g; + }).attr("transform", g => `translate(${g.x},${g.y})`); + heads.select("text.label").each((g, i, items) => this.label(d3.select(items[i]), + (`#${g.gid} ${g.n.label}`).slice(0, Math.max(12, Math.floor((g.width-48)/7))))); + heads.select("title").text(g => `${g.n.label} · ${g.members.size} nodes`); + heads.each((g, i, items) => this.foldButton(d3.select(items[i]), g.gid, false, 4, 4)); this.links.selectAll("path.edge").data(scene.edges, e => e.id).join("path") .attr("class", e => "edge " + e.role).attr("id", e => e.id) - .attr("d", e => e.path).attr("stroke", e => this.colors[e.role]) - .attr("marker-start", e => "url(#arrow-" + e.role + ")") + .classed("bundle", e => e.bundle) + .attr("d", e => e.path).attr("stroke", e => this.colors[e.bundle && e.role === "ASSOC" ? "DATA" : e.role]) + .attr("marker-start", e => "url(#arrow-" + (e.bundle && e.role === "ASSOC" ? "DATA" : e.role) + ")") .each(function(e) { d3.select(this).selectAll("title").data([e]).join("title") .text(e.role === "PARSER" ? (e.scope ? `Parser holds ${e.active ? "active" : "saved"} scope #${e.def}` : `Parser holds #${e.def}; no graph users yet`) : - `#${e.orig?.use ?? e.use}[${e.idx}] → #${e.orig?.def ?? e.def} · ${e.role}${e.label ? " · " + e.label : ""}`); + (e.bundle ? `${e.refs.length} edges bundled\n` : "") + e.refs.map(r => + `#${r.use}[${r.idx}] → #${r.def} · ${r.role}${r.label ? " · " + r.label : ""}`).join("\n")); }); this.parser.selectAll("g").data(scene.parser ? [scene.parser] : []).join(enter => { const g = enter.append("g"); @@ -78,9 +88,8 @@ class GraphView { const boxes = this.nodes.selectAll("g.node").data(scene.nodes, n => n.id).join(enter => { const g = enter.append("g").attr("class", "node"); g.append("path").attr("class", "box"); - g.append("text").attr("class", "head").attr("x", 8).attr("y", 15); - g.append("text").attr("class", "label").attr("text-anchor", "middle").attr("y", 33); - g.append("text").attr("class", "type").attr("text-anchor", "middle").attr("y", 51); + g.append("text").attr("class", "label").attr("text-anchor", "middle"); + g.append("text").attr("class", "type").attr("text-anchor", "middle").attr("y", 35); g.append("title"); return g; }); @@ -92,10 +101,9 @@ class GraphView { boxes.select("path.box").attr("d", n => this.shape(n)) .attr("fill", n => ({CTRL: "#fff1c4", REGION: "#fff1c4", LOOP: "#ffe0ab", FUN: "#ffe0ab", UNIT: "#ffe0ab", START: "#fff1c4", STOP: "#fff1c4", MEM: "#dcecff", PHI: "#f5e4fa", SCOPE: "#e5e0ff", DATA: "#edf3f7"})[n.n.kind]); - boxes.select("text.head").attr("y", n => n.scope ? 47 : 15) - .text(n => n.compact ? "" : `#${n.n.id}${n.n.proj ? " · p" + n.n.proj.idx : ""}`); - boxes.select("text.label").attr("x", n => n.width / 2).attr("y", n => n.compact ? 17 : n.scope ? 51 : 33) - .text(n => n.compact ? `#${n.n.id} ${n.label}` : n.label); + boxes.select("text.label").attr("x", n => (n.width - (n.n.fold ? 24 : 0)) / 2) + .attr("y", n => n.compact ? 17 : n.scope ? 48 : 18) + .each((n, i, items) => this.label(d3.select(items[i]), n.label)); boxes.select("text.type").attr("x", n => n.width / 2).text(n => n.scope || n.compact ? "" : n.type); boxes.select("title").text(n => this.info(n.n)); boxes.each((n, i, groups) => { @@ -121,14 +129,41 @@ class GraphView { }); group.selectAll("text.slot").data(ports, p => p.id).join("text") .attr("class", "slot").attr("x", p => p.reg ? -10 : p.x + 3).attr("y", p => p.y - 4) - .attr("text-anchor", "middle").text(p => n.n.fold ? `${p.edge.orig.use}:${p.edge.orig.idx}` : p.edge.idx); + .attr("text-anchor", "middle").text(p => n.n.fold ? "" : p.edge.refs.map(r => r.idx).join(",")); }); + const jumps = this.shortcuts.selectAll("g.shortcut").data(scene.jumps || [], j => j.id).join(enter => { + const g = enter.append("g").attr("class", "shortcut").attr("role", "button").attr("tabindex", 0); + g.append("path"); + g.append("rect").attr("rx", 4); + g.append("text"); + g.append("title"); + return g; + }).attr("aria-label", j => "Go to function " + j.label) + .on("click", (event, j) => { event.stopPropagation(); this.center(j.target); }) + .on("keydown", (event, j) => { + if (event.key === "Enter" || event.key === " ") { + event.preventDefault(); event.stopPropagation(); this.center(j.target); + } + }); + jumps.select("path").attr("d", j => j.path).attr("stroke", j => this.colors[j.role]) + .attr("marker-start", j => `url(#arrow-${j.role})`); + jumps.select("rect").attr("x", j => j.x).attr("y", j => j.y) + .attr("width", j => j.width).attr("height", j => j.height); + jumps.select("text").attr("x", j => j.x + 10).attr("y", j => j.y + 15).text(j => j.label); + jumps.select("title").text(j => `Center function #${j.target}\n` + + j.refs.map(r => `#${r.use}[${r.idx}] → #${r.def} · ${r.role}`).join("\n")); this.assocs(document.getElementById("assocs").checked); this.mark(); this.select(this.pick); if (this.auto) this.fit(); } + label(host, text) { + const split = text.indexOf(" "); + host.selectAll("tspan").data([text.slice(0, split), text.slice(split)]).join("tspan") + .attr("class", (_, i) => i ? null : "node-id").text(s => s); + } + foldButton(host, id, folded, x, y) { const btn = host.selectAll("g.fold-btn").data(id ? [id] : []).join(enter => { const g = enter.append("g").attr("class", "fold-btn").attr("role", "button").attr("tabindex", 0); @@ -156,7 +191,7 @@ class GraphView { if (n.n.kind === "PHI") return `M12,0H${w - 12}L${w},${h / 2}L${w - 12},${h}H12L0,${h / 2}Z`; if (n.n.kind === "MEM" || n.n.kind === "FUN") return `M10,0H${w - 10}L${w},10V${h - 10}L${w - 10},${h}H10L0,${h - 10}V10Z`; - const r = n.n.kind === "LOOP" ? 24 : n.n.kind === "SCOPE" ? 4 : 14; + const r = n.n.kind === "LOOP" ? 20 : n.n.kind === "SCOPE" ? 4 : 14; return `M${r},0H${w - r}Q${w},0 ${w},${r}V${h - r}Q${w},${h} ${w - r},${h}` + `H${r}Q0,${h} 0,${h - r}V${r}Q0,0 ${r},0Z`; } @@ -177,7 +212,9 @@ class GraphView { const node = this.scene?.raw?.get(id) || this.scene?.nodes.find(n => n.n.id === id)?.n; this.nodes.selectAll("g.node").classed("selected", n => n.n.id === (this.scene.cover?.get(id) || id)); this.links.selectAll("path.edge").classed("selected", e => id !== 0 && - ((e.orig?.use ?? e.use) === id || (e.orig?.def ?? e.def) === id || e.use === id || e.def === id)); + (e.refs?.some(r => r.use === id || r.def === id) || e.use === id || e.def === id)); + this.shortcuts.selectAll("g.shortcut").classed("selected", j => id !== 0 && + (j.target === id || j.use === id || j.refs.some(r => r.use === id || r.def === id))); const detail = document.getElementById("detail"); detail.hidden = !id; const box = this.scene?.cover?.get(id); @@ -186,6 +223,15 @@ class GraphView { assocs(show) { this.links.selectAll(".ASSOC").style("display", e => show || e.bind ? null : "none"); } + center(id) { + const dst = this.scene.cover?.get(id) || id; + const n = this.scene.nodes.find(n => n.n.id === dst); + if (!n) return; + this.auto = false; + this.select(id); + this.svg.call(this.zoom.translateTo, n.x + n.width / 2, n.y + n.height / 2); + } + mark() { const evt = this.evt; const show = document.getElementById("near").checked; -- cgit v1.2.3