diff options
| -rw-r--r-- | docs/GRAPH_VIEW.md | 83 | ||||
| -rw-r--r-- | docs/TRISKEL_EVAL.md | 187 | ||||
| -rw-r--r-- | experiments/graph_compare.py | 158 | ||||
| -rw-r--r-- | experiments/graph_shot.py | 7 | ||||
| -rw-r--r-- | experiments/graph_spike.py | 6 | ||||
| -rw-r--r-- | idatui/app.py | 31 | ||||
| -rw-r--r-- | idatui/graph.py | 144 | ||||
| -rw-r--r-- | idatui/graph_triskel.py | 369 | ||||
| -rw-r--r-- | pyproject.toml | 6 | ||||
| -rw-r--r-- | tests/test_graph.py | 64 | ||||
| -rw-r--r-- | tests/test_scenarios.py | 56 |
11 files changed, 1054 insertions, 57 deletions
diff --git a/docs/GRAPH_VIEW.md b/docs/GRAPH_VIEW.md index 29b280e..ea1f84d 100644 --- a/docs/GRAPH_VIEW.md +++ b/docs/GRAPH_VIEW.md @@ -32,6 +32,7 @@ extra work. | `0` | jump to the entry block | | `z` | zoom: full → compact → collapsed | | `m` | show / hide the minimap | +| `e` | layout engine: auto → native → triskel | | `f` | centre on the current block | | `Enter` | follow — stays in the graph when the target is a block of this function | | `x` `n` `y` `;` | xrefs / rename / retype / comment, exactly as in the listing | @@ -56,7 +57,51 @@ The backend adds exactly one operation, `flowchart(addr)` in `idatui/codemode_client.py`, which returns block ranges and typed edges — **not** text. -## Layout (`idatui/graph.py`) +## Two layout engines + +`graph.layout(blocks, sizer, engine=...)` takes `auto` (the default, also +`$IDATUI_GRAPH_ENGINE`), `native` or `triskel`, and `e` cycles them in the view. +`auto` prefers **triskel** where it is installed and the function is at most 250 +blocks, and falls back to **native** otherwise — including if triskel raises, +which is never fatal. + +| | native | triskel | +|---|---|---| +| algorithm | layered Sugiyama, below | SESE decomposition ([paper](https://hal.science/hal-04996939)) | +| ships with | always, pure python | needs `pytriskel` (our fork) | +| shape | wide and short | narrow and tall | +| crossings | more | far fewer | +| 87-block `main` | 15 ms, 1202×444 | 37 ms, 845×789 | +| 424-block `sub_3720` | 145 ms | 1.5 s (so `auto` won't) | + +On the 128-function corpus with realistic box sizes, triskel draws fewer +crossings on 12 functions, the same on 9, more on 3 — and the wins are where it +matters: `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, instead of straight +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 +small: triskel's routes are already orthogonal (0 diagonal segments in 2471), its +ports already land spread along the box border, and — because our fork made the +spacing settable — **we hand it cell counts rather than pixels**, so nothing is +ever rounded and two edge lanes can never land on the same row. + +What it does not do is trust the library with degenerate input, all of which is +handled before the call: self-loops (drawn as `↺`, and they make triskel throw), +disconnected components (laid out separately and stacked; IDA flowcharts do have +unreachable blocks), and the one edge in the corpus that triskel routes *through* +a block, which is detoured and then re-verified — if the detour fails the whole +layout falls back to native rather than draw an edge through the disassembly. + +## Layout (`idatui/graph.py`, the native engine) Pure python: no IDA, no Textual, no I/O, so it is unit-tested offline in milliseconds (`tests/test_graph.py`, which needs no worker). Textbook Sugiyama, @@ -130,9 +175,16 @@ listing. A CFG that size is not a picture anyone can read — IDA's own is a hairball there too (1853 crossings on the worst function in `targets/echo`). This is a feature, not a shortcoming. -Known cosmetic gap: a back edge leaves its tail's *top* border (`┴`) and arrows -up into the head's *bottom* (`▲`). Correct and readable, but IDA runs loop edges -around the side of the graph. +Known cosmetic gap **of the native engine**: a back edge leaves its tail's *top* +border (`┴`) and arrows up into the head's *bottom* (`▲`). Correct and readable, +but IDA runs loop edges around the side of the graph — which is exactly what the +triskel engine does, so `e` is the workaround. + +That difference is why an edge's arrowhead is decided by `Route.flipped` and not +by geometry. The native engine reverses back edges to get a DAG, so its polyline +runs *against* control flow and the arrow belongs at the start; triskel keeps the +real direction. Reading the direction off the drawing would silently reverse +every loop edge on one of the two engines. ## Driving it @@ -151,8 +203,25 @@ drive raw graph action=zoom - `experiments/cfg_dump.py` — freeze real CFGs from a binary to JSON. - `experiments/graph_spike.py` — lay out and render a corpus function to stdout, - or `--stats` the whole corpus. Uses `idatui.graph`, so it exercises the - shipping engine with no worker in the loop. + 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). + (the pane you are in is usually too narrow to judge it); takes an engine as + its fifth argument. + +## Installing the triskel engine + +It is optional; without it everything works and `auto` means `native`. + +```bash +uv pip install ~/dev/triskel/bindings/python # needs cmake, ninja, a C++23 compiler +``` + +That is **our fork**, not PyPI. Upstream's wheels stop at cp313 with no sdist +(so there is nothing to install on 3.14), and on any version their +`get_waypoints()` raises, which means no edge routes at all. `~/dev/triskel/PATCHES.md` +lists every change. `$IDATUI_TRISKEL_PATH` can point at a build tree instead. diff --git a/docs/TRISKEL_EVAL.md b/docs/TRISKEL_EVAL.md new file mode 100644 index 0000000..ea57515 --- /dev/null +++ b/docs/TRISKEL_EVAL.md @@ -0,0 +1,187 @@ +# 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 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) diff --git a/idatui/app.py b/idatui/app.py index 8baff74..76aff62 100644 --- a/idatui/app.py +++ b/idatui/app.py @@ -2356,6 +2356,7 @@ class GraphView(NavMixin, ScrollView, can_focus=True): Binding("0", "goto_entry", "Entry", show=False), Binding("z", "zoom", "Zoom"), Binding("m", "minimap", "Minimap", show=False), + Binding("e", "engine", "Engine", show=False), Binding("f", "center", "Centre", show=False), Binding("ctrl+d", "pan(12)", "½↓", show=False), Binding("ctrl+u", "pan(-12)", "½↑", show=False), @@ -2388,6 +2389,9 @@ class GraphView(NavMixin, ScrollView, can_focus=True): self._blocks: dict[int, object] = {} self._zoom = 0 self._show_minimap = True + #: layout backend; "auto" prefers triskel where it is installed and the + #: function is small enough for it. Cycled with `e`. + self._engine = "auto" self._mini_cache: tuple | None = None self._drag: tuple[int, int, float, float] | None = None self._drag_map = False # the drag started on the minimap @@ -2423,7 +2427,8 @@ class GraphView(NavMixin, ScrollView, can_focus=True): return blocks = [graph.Block(id=b.id, start=b.start, end=b.end, succs=list(b.succs)) for b in self.fc.blocks] - self.lay = graph.layout(blocks, self._sizer, entry=self.fc.entry) + self.lay = graph.layout(blocks, self._sizer, entry=self.fc.entry, + engine=self._engine) self.virtual_size = Size(self.lay.width + 2, self.lay.height + 1) def _rows(self, nid: int): @@ -2657,6 +2662,26 @@ class GraphView(NavMixin, ScrollView, can_focus=True): self.refresh() self.app._status(f"graph: minimap {'on' if self._show_minimap else 'off'}") + def action_engine(self) -> None: + """Cycle the layout engine and redraw the same function with it. + + The two engines disagree about shape more than about correctness -- + native draws wide and short, triskel narrow and tall with far fewer + crossings -- and which one reads better genuinely depends on the + function. Cheaper to look than to argue. + """ + from . import graph_triskel + choices = ["auto", "native"] + (["triskel"] if graph_triskel.available() + else []) + self._engine = choices[(choices.index(self._engine) + 1) % len(choices)] + self._relayout() + self._clamp_cursor() + self._center_cursor() + self.refresh(layout=True) + got = self.lay.stats["engine"] if self.lay else "?" + note = "" if graph_triskel.available() else " (pytriskel not installed)" + self.app._status(f"graph: engine {self._engine} \u2192 {got}{note}") + def action_center(self) -> None: self._center_cursor() self.refresh() @@ -3664,6 +3689,7 @@ _HELP = ( ("0", "jump to the entry block"), ("z", "zoom: full \u2192 compact \u2192 collapsed"), ("m", "show/hide the minimap"), + ("e", "layout engine: auto \u2192 native \u2192 triskel"), ("f", "centre on the current block"), ("Enter", "follow (stays in the graph if it lands here)"), ("drag / click", "pan / put the cursor in a block"), @@ -6502,9 +6528,10 @@ class IdaTui(App): return s = gv.lay.stats loops = f", {s['back']} loop{'s' if s['back'] != 1 else ''}" if s["back"] else "" + eng = "" if s.get("engine") == "native" else f", {s.get('engine')}" self._status( f"{gv.fc.name} @ {gv.fc.func_ea:#x} [graph: {s['blocks']} blocks, " - f"{s['edges']} edges{loops}] " + f"{s['edges']} edges{loops}{eng}] " f"z=zoom({gv.ZOOMS[gv._zoom]}) m=map J/K=edge space=text") def on_graph_view_cursor_moved(self, msg: "GraphView.CursorMoved") -> None: diff --git a/idatui/graph.py b/idatui/graph.py index baee597..fbaf87f 100644 --- a/idatui/graph.py +++ b/idatui/graph.py @@ -28,9 +28,13 @@ row at a time (``cells_at_row``), exactly like the listing's ``render_line``. """ from __future__ import annotations +import logging +import os import time from dataclasses import dataclass, field +_LOG = logging.getLogger(__name__) + # Terminal cells are about twice as tall as they are wide, so horizontal gaps # need roughly 2x the cell count of vertical gaps to look square. HGAP = 3 # min columns between two boxes in a layer @@ -100,6 +104,12 @@ class Edge: kind: str = E_UNCOND back: bool = False chain: list[int] = field(default_factory=list) + #: ``src``/``dst`` are swapped relative to control flow. The native engine + #: reverses back edges so layering sees a DAG; the triskel engine handles + #: cycles itself and leaves them alone. Everything downstream that has to + #: recover the real direction (succ/pred, arrowheads) reads THIS, not + #: ``back`` -- which is now purely a style bit. + flipped: bool = False @property def style(self) -> str: @@ -151,6 +161,7 @@ def _break_cycles(g: _Graph, root: int) -> None: for e in g.edges: if e.back: e.src, e.dst = e.dst, e.src + e.flipped = True # --------------------------------------------------------- 2. layering @@ -461,6 +472,9 @@ class Route: pts: list[tuple[int, int]] head: bool = True # arrowhead (target is a real block) tail: bool = True # port tee (source is a real block) + #: the polyline is drawn against control flow (a reversed back edge), so the + #: arrowhead belongs at ``pts[0]`` and the port tee at ``pts[-1]``. + flipped: bool = False def _route(g: _Graph, layers: list[list[int]]) -> list[Route]: @@ -521,8 +535,8 @@ def _route(g: _Graph, layers: list[list[int]]) -> list[Route]: else: ych = chan_y[na.rank] + lanes.get((a, b, id(e)), 0) pts = [(y0, x0), (ych, x0), (ych, x1), (y1, x1)] - routes.append(Route(edge=e, pts=pts, - head=not nb.dummy, tail=not na.dummy)) + routes.append(Route(edge=e, pts=pts, head=not nb.dummy, + tail=not na.dummy, flipped=e.flipped)) return routes @@ -646,20 +660,25 @@ class Layout: return None -def layout(blocks: list[Block], sizer, entry: int | None = None) -> Layout: - """Lay out ``blocks``. ``sizer(block) -> (width, height)`` in cells.""" - t0 = time.perf_counter() +def _build(blocks: list[Block], sizer, entry: int | None) -> tuple[_Graph, int]: + """The block list as a layout graph, plus the entry node id. + + Shared by both engines, and re-run from scratch if one of them has to fall + back, because an engine positions nodes in place. + """ g = _Graph() for b in blocks: w, h = sizer(b) + b.selfloop = False g.add(Node(id=b.id, block=b, label=f"loc_{b.start:X}", w=max(int(w), 4), h=max(int(h), 3))) for b in blocks: outs = [(d, k) for d, k in b.succs if d in g.nodes] for dst, kind in outs: if dst == b.id: - # A self-loop constrains nothing and would deadlock the Kahn - # ranking (its own in-degree never drains). Drawn as a marker. + # A self-loop constrains nothing, deadlocks the Kahn ranking + # (its own in-degree never drains) and makes triskel throw + # "EMPTY BL" from its bracket lists. Drawn as a marker instead. b.selfloop = True continue if len(outs) == 1: @@ -667,15 +686,70 @@ def layout(blocks: list[Block], sizer, entry: int | None = None) -> Layout: g.edges.append(Edge(src=b.id, dst=dst, kind=kind)) root = entry if entry in g.nodes else (min(g.nodes) if g.nodes else 0) - if g.nodes: - _break_cycles(g, root) - _assign_ranks(g, root) - _add_dummies(g) - layers = _order_layers(g, root) - _assign_x(g, layers) - routes = _route(g, layers) + return g, root + + +def _native_engine(g: _Graph, root: int) -> tuple[list[Route], int]: + """Layered Sugiyama in cells: the pipeline documented at the top.""" + _break_cycles(g, root) + _assign_ranks(g, root) + _add_dummies(g) + layers = _order_layers(g, root) + _assign_x(g, layers) + return _route(g, layers), len(layers) + + +#: Engine names accepted by ``layout(engine=...)`` and ``IDATUI_GRAPH_ENGINE``. +ENGINES = ("auto", "native", "triskel") + +#: Above this many blocks ``auto`` stays native: triskel's SESE decomposition +#: costs ~10x at 424 blocks (1.5s vs 145ms), and a layout that blocks the UI for +#: a second is worse than a layout with more crossings. Measured, see +#: docs/TRISKEL_EVAL.md. +AUTO_TRISKEL_MAX_BLOCKS = 250 + + +def _pick_engine(engine: str | None, nblocks: int) -> str: + want = (engine or os.environ.get("IDATUI_GRAPH_ENGINE") or "auto").lower() + if want not in ENGINES: + want = "auto" + if want == "auto": + from . import graph_triskel + if nblocks <= AUTO_TRISKEL_MAX_BLOCKS and graph_triskel.available(): + return "triskel" + return "native" + return want + + +def layout(blocks: list[Block], sizer, entry: int | None = None, + engine: str | None = None) -> Layout: + """Lay out ``blocks``. ``sizer(block) -> (width, height)`` in cells. + + ``engine`` picks the layout backend: ``native`` (pure python, always + available), ``triskel`` (SESE decomposition via the C++ library, far fewer + crossings) or ``auto``. Defaults to ``$IDATUI_GRAPH_ENGINE`` or ``auto``. + A triskel failure is never fatal: it falls back to native. + """ + t0 = time.perf_counter() + name = _pick_engine(engine, len(blocks)) + g, root = _build(blocks, sizer, entry) + + layers = 0 + if not g.nodes: + routes = [] + elif name == "triskel": + from . import graph_triskel + try: + routes, layers = graph_triskel.run(g, root) + except Exception as exc: # noqa: BLE001 + # Native code with a history of throwing on degenerate CFGs. The + # graph view is a convenience; losing it beats losing the session. + _LOG.warning("triskel layout failed (%s), falling back", exc) + name = "native+triskel-failed" + g, root = _build(blocks, sizer, entry) + routes, layers = _native_engine(g, root) else: - layers, routes = [], [] + routes, layers = _native_engine(g, root) # ---- paint into the index ----------------------------------------- p = Painting() @@ -708,40 +782,60 @@ def layout(blocks: list[Block], sizer, entry: int | None = None) -> Layout: ch = CORNER.get((_dir(a, b), _dir(b, c))) if ch and not blocked(*b): p.add_mark(b[0], b[1], ch, style, eid) - # A back edge was reversed for layering, so its polyline runs from the - # loop HEAD down to the tail: the arrow belongs at the start, pointing - # up into the block control returns to. + # Where the arrowhead goes is a question about CONTROL FLOW, not about + # geometry. The native engine reverses back edges for layering, so their + # polyline runs from the loop HEAD down to the tail and the arrow + # belongs at the start, pointing up into the block control returns to. + # The triskel engine keeps the real direction and routes the loop around + # the side of the graph, so the arrow is at the end like any other edge. + # ``rt.flipped`` is the only thing that distinguishes the two. first, last = rt.pts[0], rt.pts[-1] - if e.back: + down_first = rt.pts[1][0] > first[0] if len(rt.pts) > 1 else True + down_last = last[0] > rt.pts[-2][0] if len(rt.pts) > 1 else True + if rt.flipped: if rt.tail: - p.add_mark(first[0], first[1], "\u25b2", style, eid) + p.add_mark(first[0], first[1], + "\u25b2" if down_first else "\u25bc", style, eid) if rt.head: - p.add_mark(last[0], last[1], "\u2534", style, eid) + p.add_mark(last[0], last[1], + "\u2534" if down_last else "\u252c", style, eid) else: if rt.tail: - p.add_mark(first[0], first[1], "\u252c", style, eid) + p.add_mark(first[0], first[1], + "\u252c" if down_first else "\u2534", style, eid) if rt.head: - p.add_mark(last[0], last[1], "\u25bc", style, eid) + p.add_mark(last[0], last[1], + "\u25bc" if down_last else "\u25b2", style, eid) succ: dict[int, list[tuple[int, str]]] = {n.id: [] for n in real} pred: dict[int, list[tuple[int, str]]] = {n.id: [] for n in real} for e in g.edges: - a, b = (e.dst, e.src) if e.back else (e.src, e.dst) # undo reversal + a, b = (e.dst, e.src) if e.flipped else (e.src, e.dst) # undo reversal if a in succ: succ[a].append((b, e.style)) if b in pred: pred[b].append((a, e.style)) + # The canvas has to cover the EDGES too, not just the boxes. Under the + # native engine that is the same thing -- dummy nodes reserve space, so no + # edge is ever outside the boxes' bounding box. Triskel routes a loop around + # the side of the graph, past every node, and sizing on boxes alone clipped + # exactly the edges that make its layouts worth having. width = max((n.right + 1 for n in real), default=1) height = max((n.y + n.h for n in real), default=1) + for rt in routes: + for r, c in rt.pts: + width = max(width, c + 1) + height = max(height, r + 1) order = sorted(real, key=lambda n: (n.rank, n.order)) stats = { "blocks": len(blocks), "nodes": len(g.nodes), "dummies": len(g.nodes) - len(real), - "layers": len(layers), + "layers": layers, "edges": len(g.edges), "back": sum(1 for e in g.edges if e.back), + "engine": name, "ms": (time.perf_counter() - t0) * 1000, } return Layout(nodes=order, by_id={n.id: n for n in g.nodes.values()}, diff --git a/idatui/graph_triskel.py b/idatui/graph_triskel.py new file mode 100644 index 0000000..e5b662e --- /dev/null +++ b/idatui/graph_triskel.py @@ -0,0 +1,369 @@ +"""Triskel-backed layout: SESE decomposition, in character cells. + +`triskel <https://github.com/triskellib/triskel>`_ lays a CFG out by splitting it +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. + +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: + +1. **We work in cells, not pixels.** Our fork exposes ``set_spacing()``, so the + gutters and the edge-lane pitch are set in cells (3 / 1 / 1) and node sizes + are handed over in cells. Upstream's constants are pixels (50 / 40 / 30); + feeding those a 32px-tall cell rounds two adjacent edge lanes onto the same + row, which in a terminal means two differently-coloured edges fighting over + one cell. In cell units the output is integral and lanes never collide. +2. **Triskel's routes are already orthogonal.** Zero diagonal segments out of + 2471 on the corpus, so every segment is a run of ``─`` or ``│``. +3. **Ports already land on the box border**, spread along it by degree, which is + exactly what our own ``_ports`` does. + +What it does NOT do is trust the library with degenerate input. Self-loops and +disconnected graphs make it throw, an empty graph used to segfault, and a +segfault takes the TUI down with it. Both are handled here, before the call. +""" +from __future__ import annotations + +import os + +from . import graph as G + +# Spacing, in cells. X_GUTTER is the gap between boxes in a layer, Y_GUTTER the +# gap between a box and the first edge lane, EDGE_HEIGHT the pitch between +# stacked horizontal edge runs -- so EDGE_HEIGHT >= 1 is what guarantees two +# lanes never share a row. +HGAP = 3 +VGAP = 1 +LANE = 1 + +#: Columns between two weakly-connected components laid out side by side. +COMPONENT_GAP = 4 + +_mod: object | None = None +_tried = False + + +def module(): + """The ``pytriskel`` extension, or None. Imported lazily and cached. + + ``$IDATUI_TRISKEL_PATH`` points at a build tree (our fork's + ``build/bindings/python``) for development installs. + """ + global _mod, _tried + if _tried: + return _mod + _tried = True + path = os.environ.get("IDATUI_TRISKEL_PATH") + if path: + import sys + if path not in sys.path: + sys.path.insert(0, path) + try: + import pytriskel # noqa: PLC0415 + except ImportError: + return None + # Upstream ships wheels whose get_waypoints() always throws (a missing + # <pybind11/stl.h>), and without waypoints there are no edges to draw. Fail + # the availability check rather than dying mid-layout. + if not hasattr(pytriskel, "set_spacing"): + return None + _mod = pytriskel + return _mod + + +def available() -> bool: + return module() is not None + + +def _components(g: G._Graph) -> list[list[int]]: + """Weakly-connected components, entry's component first. + + Triskel raises ``EMPTY BL`` on a disconnected graph (its cycle-equivalence + bracket lists run dry), and IDA flowcharts do contain unreachable blocks -- + ``tests/test_graph.py:t_unreachable`` is exactly that shape. So we split the + work ourselves and stack the pieces side by side, which is also what the + native engine effectively does. + """ + adj: dict[int, set[int]] = {i: set() for i in g.nodes} + for e in g.edges: + adj[e.src].add(e.dst) + adj[e.dst].add(e.src) + seen: set[int] = set() + comps: list[list[int]] = [] + for start in g.nodes: + if start in seen: + continue + stack, comp = [start], [] + seen.add(start) + while stack: + i = stack.pop() + comp.append(i) + for j in adj[i]: + if j not in seen: + seen.add(j) + stack.append(j) + comps.append(sorted(comp)) + return comps + + +def _edge_type(pt, kind: str): + if kind == G.E_TRUE: + return pt.EdgeType.T + if kind == G.E_FALSE: + return pt.EdgeType.F + return pt.EdgeType.Default + + +def _clean(pts: list[tuple[int, int]]) -> list[tuple[int, int]]: + """Drop duplicate and collinear waypoints. + + Triskel emits doubled points where it stitches region layouts together (a + back edge came back with 20 waypoints, 6 of them duplicates). A doubled + point is a zero-length segment, which would make the corner-glyph pass read + a direction of "nowhere". + """ + out: list[tuple[int, int]] = [] + for p in pts: + if out and out[-1] == p: + continue + out.append(p) + i = 1 + while i < len(out) - 1: + a, b, c = out[i - 1], out[i], out[i + 1] + if (a[0] == b[0] == c[0]) or (a[1] == b[1] == c[1]): + del out[i] + else: + i += 1 + return out + + +def run(g: G._Graph, root: int) -> tuple[list[G.Route], int]: + """Position every node in ``g`` and return (routes, layer count). + + Mirrors the contract of ``graph._native_engine``: nodes come back with + ``x``/``y``/``rank``/``order`` set, edges keep their real direction (triskel + handles cycles internally, so nothing is flipped), and routes are cell + polylines. + """ + pt = module() + if pt is None: + raise RuntimeError("pytriskel is not available") + pt.set_spacing(x_gutter=float(HGAP), y_gutter=float(VGAP), + edge_height=float(LANE)) + + by_src: dict[int, list[G.Edge]] = {} + for e in g.edges: + by_src.setdefault(e.src, []).append(e) + + routes: list[G.Route] = [] + x_off = 0 + for comp in _components(g): + members = set(comp) + edges = [e for i in comp for e in by_src.get(i, []) if e.dst in members] + x_off = _layout_component(pt, g, comp, edges, routes, x_off) + + # The native engine learns which edges are back edges from its DFS, because + # it has to reverse them to get a DAG. Triskel handles cycles internally and + # tells us nothing, so recover it from the drawing: an edge that does not + # descend is one control flow comes back along. This is style only (purple, + # and the `loop:` reading in the RPC surface) -- the direction is untouched, + # which is why ``flipped`` stays False on every triskel route. + for e in g.edges: + e.back = g.nodes[e.dst].y <= g.nodes[e.src].y + + # Ranks are a layout concept the rest of the app navigates by (`w`/`b`, the + # RPC surface). Triskel doesn't expose them -- it has regions, not layers -- + # so recover bands from the y coordinates the boxes actually landed on. + real = [n for n in g.nodes.values() if not n.dummy] + bands = sorted({n.y for n in real}) + rank_of = {y: r for r, y in enumerate(bands)} + for n in real: + n.rank = rank_of[n.y] + for y in bands: + row = sorted((n for n in real if n.y == y), key=lambda n: n.x) + for k, n in enumerate(row): + n.order = k + + _repair_boxes(g, routes) + _verify(g, routes) + return routes, len(bands) + + +def _layout_component(pt, g: G._Graph, comp: list[int], edges: list[G.Edge], + routes: list[G.Route], x_off: int) -> int: + """Lay one component out, shifted right by ``x_off``. Returns the next x.""" + builder = pt.make_layout_builder() + tid = {} + for nid in comp: + n = g.nodes[nid] + # NOTE the argument order: make_node(height, width). Upstream's Python + # docstring says "width and height", which is the other way round; our + # fork makes them keyword arguments so it cannot be got wrong silently. + tid[nid] = builder.make_node(height=float(n.h), width=float(n.w)) + teid = [(builder.make_edge(tid[e.src], tid[e.dst], _edge_type(pt, e.kind)), e) + for e in edges] + lay = builder.build() + + polys: list[tuple[G.Edge, list[tuple[float, float]]]] = [] + for eid, e in teid: + polys.append((e, [(p.x, p.y) for p in lay.get_waypoints(eid)])) + + # Triskel's origin is not its bounding box: a loop edge routed around the + # side runs to y = -1, above every node. Normalise on everything drawn, not + # just the boxes, or the canvas clips its own edges. + xs = [lay.get_coords(tid[i]).x for i in comp] + ys = [lay.get_coords(tid[i]).y for i in comp] + xs += [x for _, wps in polys for x, _ in wps] + ys += [y for _, wps in polys for _, y in wps] + min_x, min_y = min(xs, default=0.0), min(ys, default=0.0) + + def cell(x: float, y: float) -> tuple[int, int]: + return int(round(y - min_y)), int(round(x - min_x)) + x_off + + for nid in comp: + n = g.nodes[nid] + p = lay.get_coords(tid[nid]) + n.y, n.x = cell(p.x, p.y) + + right = max((g.nodes[i].x + g.nodes[i].w for i in comp), default=x_off) + for e, wps in polys: + pts = _clean([cell(x, y) for x, y in wps]) + if len(pts) < 2: + continue + _snap_ports(g, e, pts) + pts = _clean(pts) + routes.append(G.Route(edge=e, pts=pts, head=True, tail=True, + flipped=False)) + right = max(right, max(c for _, c in pts) + 1) + return right + COMPONENT_GAP + + +def _box_index(g: G._Graph) -> tuple[dict[int, list[G.Node]], dict[int, list[G.Node]]]: + """(boxes strictly covering each column, boxes strictly covering each row). + + "Strictly" because a cell ON the border is where ports, arrowheads and tees + legitimately live; only the interior is off limits. + """ + by_col: dict[int, list[G.Node]] = {} + by_row: dict[int, list[G.Node]] = {} + for n in g.nodes.values(): + if n.dummy: + continue + for c in range(n.x + 1, n.right): + by_col.setdefault(c, []).append(n) + for r in range(n.y + 1, n.bottom): + by_row.setdefault(r, []).append(n) + return by_col, by_row + + +def _hits(by_col, by_row, p: tuple[int, int], q: tuple[int, int]) -> list[G.Node]: + """Boxes whose interior a straight segment from ``p`` to ``q`` runs into.""" + (r0, c0), (r1, c1) = p, q + if c0 == c1: + lo, hi = (r0, r1) if r0 <= r1 else (r1, r0) + return [n for n in by_col.get(c0, ()) + if n.y < hi and lo < n.bottom] + lo, hi = (c0, c1) if c0 <= c1 else (c1, c0) + return [n for n in by_row.get(r0, ()) + if n.x < hi and lo < n.right] + + +def _repair_boxes(g: G._Graph, routes: list[G.Route]) -> int: + """Detour any segment that runs through a box. Returns the number moved. + + Triskel does not actually guarantee this. On the corpus one edge in 128 + functions comes back drawn through a block (``sub_69C0``: a vertical at + x=235 crossing a box spanning x=222.5..236.5, in float space -- so it is the + library's own layout, not our rounding). Two cells is nothing in a PNG, + where the box is opaque and painted last. In a terminal the box is mostly + holes: the edge appears *inside* the disassembly text, and ``edge_at`` + happily reports an edge under a cell the user reads as code. + + ``docs/GRAPH_VIEW.md`` states that no edge ever crosses a box and + ``tests/test_graph.py`` counts it across the corpus, so rather than weaken + the claim we push the offending run out to the nearest side of the box it + hits. Only interior segments are moved -- the first and last carry the port + and the arrowhead, and those belong on the border. + """ + by_col, by_row = _box_index(g) + moved = 0 + for rt in routes: + for i in range(1, len(rt.pts) - 2): + p, q = rt.pts[i], rt.pts[i + 1] + for _ in range(4): + hit = _hits(by_col, by_row, p, q) + if not hit: + break + n = hit[0] + if p[1] == q[1]: # vertical: shift column + col = p[1] + near, far = n.x - 1, n.right + 1 + if col - n.x > n.right - col or near < 0: + near, far = far, near # never detour off-canvas + p, q = (p[0], near), (q[0], near) + else: # horizontal: shift row + row = p[0] + near, far = n.y - 1, n.bottom + 1 + if row - n.y > n.bottom - row or near < 0: + near, far = far, near + p, q = (near, p[1]), (near, q[1]) + rt.pts[i], rt.pts[i + 1] = p, q + moved += 1 + return moved + + +def _verify(g: G._Graph, routes: list[G.Route]) -> None: + """Raise if any segment still crosses a box, so ``layout()`` falls back. + + The invariant is worth more than the engine: a layout with more crossings + beats one that draws edges through the code. + """ + by_col, by_row = _box_index(g) + for rt in routes: + for p, q in zip(rt.pts, rt.pts[1:]): + hit = _hits(by_col, by_row, p, q) + if hit: + raise RuntimeError( + f"edge {rt.edge.src}->{rt.edge.dst} crosses block " + f"{hit[0].id} at {p}-{q} and could not be detoured") + + +def _snap_ports(g: G._Graph, e: G.Edge, pts: list[tuple[int, int]]) -> None: + """Pull the polyline's ends onto the box borders, in place. + + Triskel leaves a node at ``y + height`` -- the first row *below* the box, + because it thinks in half-open pixel rectangles while our boxes own rows + ``y .. y+h-1`` inclusive and draw a border on the last one. Landing the end + points on the border row is what lets the arrowhead and the port tee replace + a border character instead of floating one cell off it. + """ + src, dst = g.nodes[e.src], g.nodes[e.dst] + + def clamp(n: G.Node, col: int) -> int: + return max(n.x + 1, min(col, n.x + n.w - 2)) + + if len(pts) == 2: + # A straight drop between two boxes: one column has to satisfy both, or + # the "line" acquires a kink with no corner glyph to explain it. + col = clamp(dst, clamp(src, pts[0][1])) + down = pts[1][0] >= pts[0][0] + pts[0] = (src.bottom if down else src.y, col) + pts[1] = (dst.y if down else dst.bottom, col) + return + + # tail: src's bottom border if the edge leaves downward, its top if not + old_r, old_c = pts[0] + col = clamp(src, old_c) + pts[0] = (src.bottom if pts[1][0] >= old_r else src.y, col) + if pts[1][1] == old_c: # the first segment was vertical: keep it + pts[1] = (pts[1][0], col) + + # head: dst's top border if the edge arrives downward, its bottom if not + old_r, old_c = pts[-1] + col = clamp(dst, old_c) + pts[-1] = (dst.y if pts[-2][0] <= old_r else dst.bottom, col) + if pts[-2][1] == old_c: + pts[-2] = (pts[-2][0], col) diff --git a/pyproject.toml b/pyproject.toml index 1171107..80c28bf 100644 --- a/pyproject.toml +++ b/pyproject.toml @@ -13,6 +13,12 @@ dependencies = [ [project.optional-dependencies] dev = ["pytest>=8"] +# The graph view's SESE layout engine (`e` in graph mode) is optional: without +# it, layout falls back to the pure-python engine. It is deliberately NOT listed +# 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" diff --git a/tests/test_graph.py b/tests/test_graph.py index 146092d..d882f94 100644 --- a/tests/test_graph.py +++ b/tests/test_graph.py @@ -41,6 +41,16 @@ def sizer(b: G.Block) -> tuple[int, int]: return (len(f"loc_{b.start:X}") + 6, 4) +#: Which layout engine the current pass is exercising. Every invariant here is +#: a claim about the DRAWING, not about how it was arrived at, so the whole +#: suite runs once per available engine (see main()). +ENGINE = "native" + + +def layout(blocks, sz=None, entry=None) -> G.Layout: + return G.layout(blocks, sz or sizer, entry=entry, engine=ENGINE) + + def mk(edges: dict[int, list[tuple[int, str]]], n: int | None = None) -> list[G.Block]: ids = set(edges) | {d for v in edges.values() for d, _ in v} if n: @@ -95,7 +105,7 @@ def invariants(lay: G.Layout, name: str) -> None: # ---------------------------------------------------------------- cases def t_linear() -> None: - lay = G.layout(mk({0: [(1, "uncond")], 1: [(2, "uncond")]}), sizer) + lay = layout(mk({0: [(1, "uncond")], 1: [(2, "uncond")]}), sizer) invariants(lay, "linear") ranks = [lay.by_id[i].rank for i in (0, 1, 2)] check(ranks == [0, 1, 2], f"linear: ranks stack ({ranks})") @@ -103,7 +113,7 @@ def t_linear() -> None: def t_diamond() -> None: - lay = G.layout(mk({0: [(1, "jump"), (2, "fall")], + lay = layout(mk({0: [(1, "jump"), (2, "fall")], 1: [(3, "uncond")], 2: [(3, "uncond")]}), sizer) invariants(lay, "diamond") check(lay.by_id[3].rank == 2, "diamond: join sits below both arms") @@ -115,7 +125,7 @@ def t_diamond() -> None: def t_selfloop() -> None: """A self-loop must not stall the ranking — the bug that collapsed a whole function into three layers and made the graph 280 columns wide.""" - lay = G.layout(mk({0: [(1, "uncond")], 1: [(1, "jump"), (2, "fall")], + lay = layout(mk({0: [(1, "uncond")], 1: [(1, "jump"), (2, "fall")], 2: [(3, "uncond")]}), sizer) invariants(lay, "selfloop") ranks = [lay.by_id[i].rank for i in (0, 1, 2, 3)] @@ -124,7 +134,7 @@ def t_selfloop() -> None: def t_loop() -> None: - lay = G.layout(mk({0: [(1, "uncond")], 1: [(2, "jump"), (3, "fall")], + lay = layout(mk({0: [(1, "uncond")], 1: [(2, "jump"), (3, "fall")], 2: [(1, "uncond")]}), sizer) invariants(lay, "loop") check(any(e.back for e in lay.edges), "loop: a back edge is detected") @@ -136,7 +146,7 @@ def t_loop() -> None: def t_switch() -> None: - lay = G.layout(mk({0: [(i, "switch") for i in range(1, 9)], + lay = layout(mk({0: [(i, "switch") for i in range(1, 9)], **{i: [(9, "uncond")] for i in range(1, 9)}}), sizer) invariants(lay, "switch") check(len({lay.by_id[i].rank for i in range(1, 9)}) == 1, @@ -146,7 +156,7 @@ def t_switch() -> None: def t_unreachable() -> None: """A block reachable only through a reversed edge must still get a rank.""" - lay = G.layout(mk({0: [(1, "uncond")], 2: [(2, "jump")]}, n=3), sizer) + lay = layout(mk({0: [(1, "uncond")], 2: [(2, "jump")]}, n=3), sizer) invariants(lay, "unreachable") check(len(lay.nodes) == 3, "unreachable: every block is placed") @@ -155,15 +165,19 @@ def t_long_edge() -> None: """An edge spanning many layers gets dummies, so it reserves real space.""" chain = {i: [(i + 1, "uncond")] for i in range(6)} chain[0] = [(1, "fall"), (6, "jump")] - lay = G.layout(mk(chain), sizer) + lay = layout(mk(chain), sizer) invariants(lay, "long_edge") - check(lay.stats["dummies"] >= 4, - f"long_edge: the skip edge is padded ({lay.stats['dummies']} dummies)") + # Dummy nodes are how the NATIVE engine reserves horizontal space for a + # long edge. Triskel reaches the same end -- an edge that crosses no box, + # checked by invariants() above -- without them, so this is engine-specific. + if ENGINE == "native": + check(lay.stats["dummies"] >= 4, + f"long_edge: the skip edge is padded ({lay.stats['dummies']} dummies)") check(all_edges_drawn(lay), "long_edge: the long edge is drawn") def t_empty() -> None: - lay = G.layout([], sizer) + lay = layout([], sizer) check(lay.nodes == [], "empty: no nodes") check(lay.width >= 1 and lay.height >= 1, "empty: canvas is still sane") @@ -171,7 +185,7 @@ def t_empty() -> None: def t_row_query() -> None: """cells_at_row must be windowed: asking for a slice returns only that slice, which is what keeps a 13M-cell graph renderable.""" - lay = G.layout(mk({0: [(1, "jump"), (2, "fall")], + lay = layout(mk({0: [(1, "jump"), (2, "fall")], 1: [(3, "uncond")], 2: [(3, "uncond")]}), sizer) for row in range(lay.height): full = lay.painting.cells_at_row(row, 0, lay.width) @@ -182,7 +196,7 @@ def t_row_query() -> None: def t_hit_test() -> None: - lay = G.layout(mk({0: [(1, "jump"), (2, "fall")]}), sizer) + lay = layout(mk({0: [(1, "jump"), (2, "fall")]}), sizer) n = lay.nodes[0] check(lay.node_at(n.y, n.x) is n, "hit: top-left corner hits the node") check(lay.node_at(n.y + 1, n.x + 1) is n, "hit: interior hits the node") @@ -202,7 +216,7 @@ def t_corpus(path: str) -> None: 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"]] - lay = G.layout(blocks, sizer) + lay = layout(blocks, sizer) if lay.stats["ms"] > worst_ms: worst_ms, worst_name = lay.stats["ms"], rec["name"] check(no_box_overlap(lay), f"corpus {rec['name']}: boxes must not overlap") @@ -220,14 +234,24 @@ def t_corpus(path: str) -> None: def main() -> int: + global ENGINE print("idatui.graph layout tests") - for fn in (t_linear, t_diamond, t_selfloop, t_loop, t_switch, - t_unreachable, t_long_edge, t_empty, t_row_query, t_hit_test): - print(f" {fn.__name__}") - fn() - for path in sys.argv[1:]: - if os.path.exists(path): - t_corpus(path) + from idatui import graph_triskel + engines = ["native"] + if graph_triskel.available(): + engines.append("triskel") + else: + print(" (pytriskel not importable: skipping the triskel engine)") + for engine in engines: + ENGINE = engine + print(f"\nengine: {engine}") + for fn in (t_linear, t_diamond, t_selfloop, t_loop, t_switch, + t_unreachable, t_long_edge, t_empty, t_row_query, t_hit_test): + print(f" {fn.__name__}") + fn() + for path in sys.argv[1:]: + if os.path.exists(path): + t_corpus(path) print(f"\n{CHECKS} checks, {len(FAILED)} failed") for f in FAILED: print(f" - {f}") diff --git a/tests/test_scenarios.py b/tests/test_scenarios.py index 5297f0c..d5090e0 100644 --- a/tests/test_scenarios.py +++ b/tests/test_scenarios.py @@ -3479,6 +3479,62 @@ async def s_graph_zoom(c: Ctx): f"{gv.lay.height} vs {full_h}") +@scenario("graph_engine") +async def s_graph_engine(c: Ctx): + """`e` swaps the layout backend under a live view. + + The interesting part is not that triskel draws a different picture, it is + that everything anchored to the old one survives: the cursor keeps its + address, the canvas is resized to the new extent (triskel routes loop edges + OUTSIDE the boxes' bounding box, which is what made the first version clip + them), and a missing pytriskel degrades to native instead of raising. + """ + from idatui import graph_triskel + app = c.app + fn, gv = await _open_graph(c) + if gv.lay is None: + c.check("graph loaded", False) + return + ea = gv._cursor_ea() + first = gv.lay.stats["engine"] + c.check("auto picks triskel when it is installed", + first == ("triskel" if graph_triskel.available() else "native"), + f"engine={first} available={graph_triskel.available()}") + + seen = [first] + for _ in range(3): + await c.press("e") + await c.pause(0.2) + seen.append(gv.lay.stats["engine"]) + c.check(f"the view survives engine={gv._engine}", + gv.lay is not None and gv.lay.width > 0 and gv.lay.height > 0, + f"{gv.lay.width}x{gv.lay.height}") + c.check(f"the cursor keeps an address on engine={gv._engine}", + gv._cursor_ea() is not None) + c.check(f"the canvas covers every edge on engine={gv._engine}", + all(0 <= col < gv.lay.width and 0 <= row < gv.lay.height + for rt in _routes_of(gv.lay) for row, col in rt), + f"canvas {gv.lay.width}x{gv.lay.height}") + c.check("e cycles back round", seen[0] == seen[-1], str(seen)) + c.check("native was one of them", "native" in seen, str(seen)) + c.check("the status names the engine", "graph:" in c.status() or + gv.fc.name in c.status(), c.status()) + if ea is not None: + c.check("the cursor address is unchanged by relayout", + gv._cursor_ea() is not None) + + +def _routes_of(lay): + """Every painted point, as (row, col) pairs, straight out of the index.""" + out = [] + for row, runs in lay.painting.hruns.items(): + out.append([(row, lo) for lo, _hi, _s, _e in runs] + + [(row, hi) for _lo, hi, _s, _e in runs]) + for lo, hi, col, _s, _e in lay.painting.vruns: + out.append([(lo, col), (hi, col)]) + return out + + @scenario("graph_render") async def s_graph_render(c: Ctx): """The drawing itself: boxes, instruction text and edge glyphs must actually |