From 1cf127f5c1cc5d7862385df14b5c49ba028ade7c Mon Sep 17 00:00:00 2001 From: user Date: Sun, 9 Aug 2026 12:59:18 +0200 Subject: Graph: a second layout engine, triskel's SESE decomposition `e` in graph mode cycles auto -> native -> triskel, and `auto` prefers triskel where it is installed and the function is at most 250 blocks. Why: our layered engine draws wide-and-short pictures with a lot of crossings on anything branchy. Triskel splits the CFG into Single-Entry Single-Exit regions first and lays each out on its own, which on the 128-function corpus means fewer crossings on 12 functions, equal on 9, worse on 3 -- and the wins are the hairballs (sub_5CA0 41 -> 6, sub_2C90 32 -> 7, sub_2C00 12 -> 0). It also routes loop edges around the side of the graph the way IDA does, which was a known gap here. It is not free: ~2x slower at 87 blocks, 10x at 424, hence the cap. The library needed a fork (~/dev/triskel, branch idatui) before it could be used from Python at all -- its get_waypoints() threw on every published version, an empty graph segfaulted the interpreter, and its spacing constants were pixels baked in at compile time. Making those settable is what makes this integration cheap: we hand it CELLS, so its output is integral and two edge lanes can never round onto the same row. The feared quantisation problem measured out backwards -- cells claimed by more than one edge: native 131, triskel 35. Not trusted with degenerate input, all handled before the call: self-loops and disconnected components make it throw, and one corpus edge comes back routed through a block, which we detour and re-verify. A triskel failure is never fatal; it falls back to native. Two things the second engine flushed out of the existing code: - the canvas was sized from boxes alone, which is exact only because native's dummy nodes reserve the space. Triskel routes outside that bounding box and the edges were being clipped. - arrowhead placement read e.back, conflating "this is a loop edge" (style) with "this polyline runs against control flow" (geometry). Now Edge.flipped, which is also a latent fix for residual-cycle edges whose succ/pred were being reported backwards. tests/test_graph.py runs its whole suite once per available engine (943 checks); new graph_engine scenario covers the live toggle. --- experiments/graph_compare.py | 158 +++++++++++++++++++++++++++++++++++++++++++ experiments/graph_shot.py | 7 +- experiments/graph_spike.py | 6 +- 3 files changed, 168 insertions(+), 3 deletions(-) create mode 100644 experiments/graph_compare.py (limited to 'experiments') diff --git a/experiments/graph_compare.py b/experiments/graph_compare.py new file mode 100644 index 0000000..0714554 --- /dev/null +++ b/experiments/graph_compare.py @@ -0,0 +1,158 @@ +#!/usr/bin/env python3 +"""Compare the layout engines on a corpus: crossings, canvas, ambiguity, cost. + + python3 experiments/graph_compare.py .auto/cfg-corpus.json + python3 experiments/graph_compare.py .auto/cfg-corpus.json --max-blocks 40 + +Every number comes out of the shipping pipeline (``idatui.graph``), not out of a +side channel, so it measures what the view will actually draw. + +The columns that matter: + +``X`` proper segment crossings -- what the SESE decomposition is for. +``amb`` cells claimed by more than one edge. In a pixel renderer overlapping + lines are invisible; in a terminal one cell holds one character, so an + ambiguous cell is an edge the user cannot follow and ``edge_at`` gets + wrong under the cursor. +""" +from __future__ import annotations + +import argparse +import json +import os +import sys +import time +from collections import defaultdict + +sys.path.insert(0, os.path.dirname(os.path.dirname(os.path.abspath(__file__)))) + +from idatui import graph as G # noqa: E402 + + +def sizer(b: G.Block) -> tuple[int, int]: + return (len(f"loc_{b.start:X}") + 6, 4) + + +def real_sizer(rec: dict, max_lines: int): + """Box sizes from the actual disassembly text, like the view's own sizer. + + Box shape is not a detail here: it decides how much horizontal room a layer + needs, and therefore how far edges travel sideways. Comparing engines on + uniform 20-column stubs measures the wrong graph. + """ + texts = {} + for b in rec["blocks"]: + lines = list(b["lines"]) + if max_lines and len(lines) > max_lines: + lines = lines[:max_lines - 1] + [f"... {len(b['lines']) - max_lines + 1} more"] + texts[b["id"]] = lines + + def size(b: G.Block) -> tuple[int, int]: + lines = texts[b.id] + return max((len(line) for line in lines), default=8) + 4, len(lines) + 2 + return size + + +def segments(lay: G.Layout) -> dict[int, list[tuple[int, int, int, int]]]: + """Per-edge segments as (x0, y0, x1, y1), rebuilt from the painting.""" + segs: dict[int, list] = defaultdict(list) + for row, runs in lay.painting.hruns.items(): + for lo, hi, _style, eid in runs: + segs[eid].append((lo, row, hi, row)) + for lo, hi, col, _style, eid in lay.painting.vruns: + segs[eid].append((col, lo, col, hi)) + return segs + + +def crossings(segs: dict[int, list], cap: int = 400_000) -> int | None: + def orient(px, py, qx, qy, rx, ry): + v = (qx - px) * (ry - py) - (qy - py) * (rx - px) + return (v > 0) - (v < 0) + + keys = list(segs) + n = pairs = 0 + for i, a in enumerate(keys): + for b in keys[i + 1:]: + for ax, ay, bx, by in segs[a]: + for cx, cy, dx, dy in segs[b]: + pairs += 1 + if pairs > cap: + return None + o1 = orient(ax, ay, bx, by, cx, cy) + o2 = orient(ax, ay, bx, by, dx, dy) + o3 = orient(cx, cy, dx, dy, ax, ay) + o4 = orient(cx, cy, dx, dy, bx, by) + if o1 != o2 and o3 != o4: + n += 1 + return n + + +def ambiguous(lay: G.Layout) -> tuple[int, int]: + """(cells claimed by >1 edge, total edge cells).""" + owners: dict[tuple[int, int], set[int]] = defaultdict(set) + for row, runs in lay.painting.hruns.items(): + for lo, hi, _s, eid in runs: + for c in range(lo, hi + 1): + owners[(row, c)].add(eid) + for lo, hi, col, _s, eid in lay.painting.vruns: + for r in range(lo, hi + 1): + owners[(r, col)].add(eid) + return sum(1 for v in owners.values() if len(v) > 1), len(owners) + + +def main() -> int: + ap = argparse.ArgumentParser() + ap.add_argument("corpus") + ap.add_argument("--max-blocks", type=int, default=10 ** 9) + ap.add_argument("--min-blocks", type=int, default=6) + ap.add_argument("--real-sizer", action="store_true", + help="size boxes from the disassembly text, as the view does") + ap.add_argument("--max-lines", type=int, default=8) + args = ap.parse_args() + + from idatui import graph_triskel + if not graph_triskel.available(): + print("pytriskel not importable; set IDATUI_TRISKEL_PATH", file=sys.stderr) + return 2 + + recs = json.load(open(args.corpus)) + recs = [r for r in recs + if args.min_blocks <= len(r["blocks"]) <= args.max_blocks] + recs.sort(key=lambda r: len(r["blocks"])) + + print(f"{'blk':>4} | {'native ms':>9} {'canvas':>11} {'X':>5} {'amb':>5} | " + f"{'tk ms':>7} {'canvas':>11} {'X':>5} {'amb':>5} | name") + tot = {"native": 0.0, "triskel": 0.0} + won = tied = lost = 0 + amb_tot = {"native": 0, "triskel": 0} + for rec in recs: + row = {} + for engine in ("native", "triskel"): + blocks = [G.Block(id=b["id"], start=b["start"], end=b["end"], + succs=[(d, k) for d, k in b["succs"]]) + for b in rec["blocks"]] + size = real_sizer(rec, args.max_lines) if args.real_sizer else sizer + t0 = time.perf_counter() + lay = G.layout(blocks, size, engine=engine) + ms = (time.perf_counter() - t0) * 1000 + tot[engine] += ms + amb, _cells = ambiguous(lay) + amb_tot[engine] += amb + row[engine] = (ms, lay.width, lay.height, crossings(segments(lay)), amb) + (nm, nw, nh, nx, na) = row["native"] + (tm, tw, th, tx, ta) = row["triskel"] + if nx is not None and tx is not None: + won += tx < nx + tied += tx == nx + lost += tx > nx + print(f"{len(rec['blocks']):>4} | {nm:>9.1f} {f'{nw}x{nh}':>11} " + f"{str(nx):>5} {na:>5} | {tm:>7.1f} {f'{tw}x{th}':>11} " + f"{str(tx):>5} {ta:>5} | {rec['name']}") + print(f"\ntotal: native {tot['native']:.0f} ms, triskel {tot['triskel']:.0f} ms") + print(f"crossings: triskel better on {won}, equal on {tied}, worse on {lost}") + print(f"ambiguous cells: native {amb_tot['native']}, triskel {amb_tot['triskel']}") + return 0 + + +if __name__ == "__main__": + sys.exit(main()) diff --git a/experiments/graph_shot.py b/experiments/graph_shot.py index 5f0d45a..e024809 100644 --- a/experiments/graph_shot.py +++ b/experiments/graph_shot.py @@ -1,6 +1,6 @@ """Render the graph view headless at a chosen size and print it. - ~/ida-venv/bin/python experiments/graph_shot.py [func] [cols] [rows] [zoom] + ~/ida-venv/bin/python experiments/graph_shot.py [func] [cols] [rows] [zoom] [engine] The pane a person runs this in is usually too small to judge the layout, and the pilot lays out synchronously at whatever size you ask for -- so this is the way @@ -19,6 +19,7 @@ func = sys.argv[1] if len(sys.argv) > 1 else "sub_2297" cols = int(sys.argv[2]) if len(sys.argv) > 2 else 170 rows = int(sys.argv[3]) if len(sys.argv) > 3 else 55 zoom = int(sys.argv[4]) if len(sys.argv) > 4 else 0 +engine = sys.argv[5] if len(sys.argv) > 5 else None src, tmp = f"{REPO}/targets/echo", "/tmp/echo_shot" shutil.copy(src, tmp) @@ -46,6 +47,10 @@ async def main() -> None: await pilot.pause(0.2) await pilot.press("space") gv = app.query_one(GraphView) + if engine: + gv._engine = engine + gv._relayout() + app._graph_status() ok = await wait_for(lambda: app._active == "graph" and gv.lay is not None, pilot.pause, 90) if not ok: diff --git a/experiments/graph_spike.py b/experiments/graph_spike.py index 547c829..e8cf3b8 100644 --- a/experiments/graph_spike.py +++ b/experiments/graph_spike.py @@ -110,6 +110,8 @@ def main() -> int: ap.add_argument("--max-lines", type=int, default=8, help="collapse blocks longer than this (0 = never)") ap.add_argument("--no-color", action="store_true") + ap.add_argument("--engine", choices=G.ENGINES, default=None, + help="layout backend (default: $IDATUI_GRAPH_ENGINE or auto)") args = ap.parse_args() recs = json.load(open(args.corpus)) @@ -119,7 +121,7 @@ def main() -> int: tot = 0.0 for r in sorted(recs, key=lambda r: len(r["blocks"])): blocks, sizer, _ = build(r, args.max_lines) - lay = G.layout(blocks, sizer) + lay = G.layout(blocks, sizer, engine=args.engine) s = lay.stats tot += s["ms"] print(f"{s['blocks']:>7} {s['nodes']:>6} {s['dummies']:>6} " @@ -138,7 +140,7 @@ def main() -> int: rec = min(recs, key=lambda r: len(r["blocks"])) blocks, sizer, texts = build(rec, args.max_lines) - lay = G.layout(blocks, sizer) + lay = G.layout(blocks, sizer, engine=args.engine) print(render(lay, texts, color=not args.no_color)) print(f"\n{rec['name']}: {lay.stats} canvas {lay.width}x{lay.height}", file=sys.stderr) -- cgit v1.3.1-sl0p