diff options
| -rw-r--r-- | docs/GRAPH_VIEW.md | 7 | ||||
| -rw-r--r-- | docs/TRISKEL_EVAL.md | 187 | ||||
| -rw-r--r-- | experiments/graph_compare.py | 158 | ||||
| -rw-r--r-- | idatui/graph_triskel.py | 2 | ||||
| -rw-r--r-- | pyproject.toml | 1 |
5 files changed, 1 insertions, 354 deletions
diff --git a/docs/GRAPH_VIEW.md b/docs/GRAPH_VIEW.md index b656179..a3d2645 100644 --- a/docs/GRAPH_VIEW.md +++ b/docs/GRAPH_VIEW.md @@ -86,10 +86,6 @@ back up the middle. It is not a clean sweep: on `sub_69C0` (109 blocks) its narrower canvas packs edges tighter and it ends up with *more* cells shared between edges than native (1280 vs 935). -`experiments/graph_compare.py` regenerates all of those numbers, and -`docs/TRISKEL_EVAL.md` is the full evaluation, including what had to be fixed in -triskel to make it usable at all. - ### The triskel path (`idatui/graph_triskel.py`) The whole impedance mismatch lives in that one module. Three things keep it @@ -219,9 +215,6 @@ drive raw graph action=zoom - `experiments/graph_spike.py` — lay out and render a corpus function to stdout, or `--stats` the whole corpus; `--engine` picks the backend. Uses `idatui.graph`, so it exercises the shipping engine with no worker in the loop. -- `experiments/graph_compare.py` — both engines over a corpus: crossings, canvas, - ambiguous cells, cost. `--real-sizer` sizes boxes from the disassembly text, - which is the only comparison worth reading. - `experiments/graph_smoke.py` — end-to-end: tool → domain → layout. - `experiments/graph_shot.py` — render the real view headless at a chosen size (the pane you are in is usually too narrow to judge it); takes an engine as diff --git a/docs/TRISKEL_EVAL.md b/docs/TRISKEL_EVAL.md deleted file mode 100644 index ea57515..0000000 --- a/docs/TRISKEL_EVAL.md +++ /dev/null @@ -1,187 +0,0 @@ -# Triskel for graph layout — evaluated, forked, integrated - -> **Outcome.** Shipped as the `triskel` engine behind `graph.layout(engine=...)`, -> preferred by `auto` up to 250 blocks, off a local fork -> (`~/dev/triskel`, branch `idatui`, see its `PATCHES.md`). The library needed -> six fixes before it could be used from Python at all — including a segfault -> and a binding bug that made edge routes unreachable. Everything below is the -> evaluation that led there; `docs/GRAPH_VIEW.md` documents what shipped. - - -[triskel](https://github.com/triskellib/triskel) (MPL-2.0, C++23, 126★) is a CFG -layout engine from Inria, the implementation of *[Towards better CFG -layouts](https://hal.science/hal-04996939)*. Its idea is genuinely better than -ours: before running Sugiyama, split the CFG into **Single-Entry Single-Exit -(SESE) regions**, lay each region out on its own, then paste the region layouts -back in as single super-nodes. Divide and conquer, so crossings stay local. - -This is what happened when we actually ran it against `idatui.graph` on the -128-function corpus in `.auto/cfg-corpus.json`. - -**Verdict as first written: don't link the library, port the idea.** That was -reversed after the blockers turned out to be six small, independent patches -rather than algorithm work — and one of them (settable spacing) removed the -quantisation problem entirely instead of managing it. Reimplementing 350 lines -of cycle-equivalence C++ in Python to avoid a `#include` would have been a poor -trade. The licensing note at the end is why the fork stays a fork: MPL-2.0 is -file-level copyleft, so linking it costs us nothing, and our changes to *their* -files stay in *their* repo. - -## The quality gap is real - -Both engines fed identical blocks and identical cell sizes (triskel gets them as -"pixels" at 16×32 per cell). Crossings are proper segment intersections counted -on each engine's own edge polylines; `X` is that count, `None` = above the -counting cap. - -``` - blk edge | ours ms ours WxH X | tk ms tk WxH(cells) X | name - 9 14 | 0.5 89x62 5 | 0.3 81x71 1 | sub_61D0 - 10 41 | 1.3 99x80 10 | 0.5 86x105 0 | sub_3500 - 17 44 | 1.4 213x144 6 | 0.6 159x171 0 | sub_2FF0 - 21 33 | 1.2 724x105 41 | 0.5 782x119 0 | sub_5CA0 - 38 150 | 4.7 325x305 32 | 2.8 202x392 1 | sub_2C90 - 87 428 | 14.8 1202x444 None | 30.3 850x775 None | main - 109 647 | 25.9 793x476 None | 53.6 363x970 None | sub_69C0 - 424 3340 | 145.7 9222x1386 None | 1534.3 1872x3883 None | sub_3720 -total ours 207 ms triskel 1626 ms (full corpus in /tmp/tk_cmp.py) -``` - -Two things to take from that table: - -- **Crossings collapse to ~0.** Every function under 40 blocks lays out with 0 - or 1 crossing, where ours has up to 41. That is the SESE decomposition doing - exactly what the paper claims. -- **Canvases get narrow and tall.** `sub_69C0`: 793×476 → 363×970. `sub_3720`: - 9222×1386 → 1872×3883. For a terminal that is the right trade — vertical - scrolling is free, horizontal panning is the thing that makes our graph view - feel like peering through a letterbox. - -And it costs us on speed above ~40 blocks: 2× slower at 87–109 blocks, **10× -slower at 424** (1.5 s vs 145 ms). So it would not let us raise the 400-block -cap; it would argue for lowering it. - -## The output *is* renderable in character cells - -This was the thing that could have killed the idea outright, and it doesn't: - -- **Every segment is axis-aligned.** 0 diagonal segments out of 1708 (`main`) - and 2471 (`sub_69C0`). Box-drawing characters map straight onto it. -- **No edge is routed through a box.** The "edge cells inside a box" count comes - out at exactly ~1 per edge — that is the polyline's first waypoint, which sits - at the source node's *centre*. Clip the first and last segment to the border - and it is clean. -- **Quantisation is a knob, not a wall.** Triskel packs edges in continuous - space, so rounding to cells can drop two edges into one column. How often - depends entirely on the px-per-cell we feed it (`main`, 140 edges): - - | px/cell | edge cells | cells shared by >1 edge | - |---|---|---| - | 8×16 | 50418 | 73 (0.1%) | - | 12×24 | 41536 | 69 (0.2%) | - | 16×32 | 36071 | 1026 (2.8%) | - | 24×48 | 28113 | 4525 (16.1%) | - - The gutters are hardcoded constants (`X_GUTTER=50`, `Y_GUTTER=40`, - `EDGE_HEIGHT=30`), so px-per-cell is really "how many cells of gutter do I - buy". Cheap cells → wider canvas, unambiguous edges. This matters more for us - than for a pixel renderer: an ambiguous cell isn't just ugly, it breaks - click-to-select-edge and the incident-edge highlight, which assume a cell - belongs to one edge. Our lane-packed channels exist to make that impossible. - -## Why we can't just `pip install pytriskel` (all fixed in the fork) - -1. **No wheel we can use.** All ten releases ship `manylinux_2_34_x86_64` wheels - for cp37–cp313 and **no sdist**. Our venv is Python 3.14 → `pip install` - finds nothing. It is also x86_64-Linux only: no macOS, no arm64, no Windows. -2. **The Python bindings can't return edge routes at all.** `pytriskel.cpp` - never includes `<pybind11/stl.h>`, so `get_waypoints()` raises - `Unable to convert function return value to a Python type` on every published - version. The `.pyi` stub gives it away: `get_waypoints(self, arg0: int) -> ...`. - From the shipped wheel you can get node coordinates and save a PNG — that is - it. A one-line patch fixes it (verified locally). -3. **Building from source works but is heavy.** Verified here: clone, `cmake - -DENABLE_CAIRO=ON -DBUILD_BINDINGS=ON`, ~2 minutes, produces a working - `pytriskel.cpython-314-*.so`. But `BUILD_BINDINGS` is gated on - `ENABLE_CAIRO`, so a user installing a *TUI* would need cmake, a C++23 - compiler, fmt and cairo dev headers to draw boxes made of `─`. -4. **It crashes the process on degenerate input.** - - empty graph → **segfault** (not an exception — it takes the interpreter with - it, and with it your session) - - disconnected graph → `RuntimeError: EMPTY BL`, an internal bracket-list - assertion leaking out. IDA flowcharts do contain unreachable blocks. - - Self-loops, parallel edges and 2-cycles are all handled fine. -5. **Rough edges in the API.** `make_node(float height, float width)` is - documented in the Python stub as "with a width and height" — the arguments - are the other way round (this cost us a benchmark run). `get_height` is bound - twice, once over `get_width`, so graph width is unreachable from Python. - Node sizes can't be read back, and the SESE tree isn't exposed. - -## What we'd also lose - -`graph.py` doesn't just return coordinates. It returns ranks and per-layer -order, which `w`/`b` navigation, the minimap and the RPC `graph show` verb all -read. Triskel exposes neither — we'd re-derive ordering from y coordinates. -And the whole engine is currently pure Python with no I/O, which is why -`tests/test_graph.py` runs offline in milliseconds against a 128-function -corpus. Linking a native layout engine costs us that property. - -## What integration actually cost - -Six patches to the fork (`~/dev/triskel/PATCHES.md`) and one new module, -`idatui/graph_triskel.py`. The patch that mattered most was making `X_GUTTER` / -`Y_GUTTER` / `EDGE_HEIGHT` settable: feeding the engine **cells instead of -pixels** (3 / 1 / 1) makes its output integral, so the whole quantisation -section above stops applying. Measured after the fact on the real pipeline, the -fear was backwards — cells claimed by more than one edge across the small-corpus -functions: **native 131, triskel 35**. - -Three things stayed on our side of the boundary because they are the caller's -job, not the library's: self-loops (never passed — they throw), disconnected -components (laid out separately and stacked — they throw), and the one corpus -edge triskel routes through a block (detoured, then re-verified, else the whole -layout falls back to native). - -The canvas also had to learn that edges can live outside the boxes' bounding -box: triskel routes a loop around the side of the graph, and sizing the canvas -on nodes alone — which is exact for the native engine, since its dummy nodes -reserve the space — clipped exactly the edges that make its layouts worth having. - -## The road not taken: port the idea, not the code - -The win is the SESE decomposition, and that is ~350 lines of C++ -(`lib/src/analysis/sese.cpp`, cycle equivalence / program structure tree, plus -`udfs.cpp`) and the region orchestration in `layout.cpp`. In Python, on top of -the pipeline we already have, that is roughly: - -1. undirected DFS + cycle equivalence → the program structure tree (~200 lines) -2. per-region layout: run our existing steps 2–5 on the region subgraph -3. collapse each region into a super-node in its parent, then translate - -Steps 2 and 3 reuse `_assign_ranks` / `_order_layers` / `_assign_x` unchanged, -and — this is the point — **our cell-native router and lane packing survive**, so -we keep the 0-edge-cells-inside-a-box guarantee and unambiguous edge ownership -instead of inheriting a quantisation problem. - -On licensing: MPL-2.0 is file-level copyleft. Linking the library unmodified -imposes nothing on our code; copying their source into `graph.py` would arguably -make that file MPL. Implementing from the paper and citing it keeps this clean. - -Worth doing regardless, as upstream is friendly and we may want the library -later: file the missing `<pybind11/stl.h>`, the empty-graph segfault, and the -`make_node` docstring order. - -## Reproducing - -The throwaway scripts that produced the tables above (`/tmp/tk_*.py`, driving -pytriskel directly) have been replaced by one that drives the shipping pipeline: - -```bash -python3 experiments/graph_compare.py .auto/cfg-corpus.json --real-sizer -``` - -and the engines are exercised side by side, on every invariant, by -`tests/test_graph.py` — which runs its whole suite once per available engine, so -"triskel draws no edge through a box" is checked on 128 real functions rather -than asserted here. diff --git a/experiments/graph_compare.py b/experiments/graph_compare.py deleted file mode 100644 index 0714554..0000000 --- a/experiments/graph_compare.py +++ /dev/null @@ -1,158 +0,0 @@ -#!/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/idatui/graph_triskel.py b/idatui/graph_triskel.py index 479c39b..2bf92bf 100644 --- a/idatui/graph_triskel.py +++ b/idatui/graph_triskel.py @@ -5,7 +5,7 @@ into Single-Entry Single-Exit regions first, laying each region out on its own, and pasting the results back as super-nodes. On our corpus that takes functions that our own layered engine draws with up to 41 edge crossings down to 0 or 1, and it routes loop edges around the side of the graph the way IDA does instead -of straight back up the middle. ``docs/TRISKEL_EVAL.md`` has the measurements. +of straight back up the middle. This module owns the whole impedance mismatch between a float/pixel layout engine and a grid of character cells. Three things make that mismatch small: diff --git a/pyproject.toml b/pyproject.toml index 2420329..f8e75e6 100644 --- a/pyproject.toml +++ b/pyproject.toml @@ -18,7 +18,6 @@ dev = ["pytest>=8"] # as a dependency -- PyPI's pytriskel has no wheel for current Pythons, no sdist, # and a binding bug that makes edge routes unreachable. Install our fork: # uv pip install ~/dev/triskel/bindings/python -# See docs/TRISKEL_EVAL.md and ~/dev/triskel/PATCHES.md. [project.scripts] idatui = "idatui.launch:main" |