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. --- docs/GRAPH_VIEW.md | 83 +++++++++- docs/TRISKEL_EVAL.md | 187 ++++++++++++++++++++++ experiments/graph_compare.py | 158 ++++++++++++++++++ experiments/graph_shot.py | 7 +- experiments/graph_spike.py | 6 +- idatui/app.py | 31 +++- idatui/graph.py | 144 ++++++++++++++--- idatui/graph_triskel.py | 369 +++++++++++++++++++++++++++++++++++++++++++ pyproject.toml | 6 + tests/test_graph.py | 64 +++++--- tests/test_scenarios.py | 56 +++++++ 11 files changed, 1054 insertions(+), 57 deletions(-) create mode 100644 docs/TRISKEL_EVAL.md create mode 100644 experiments/graph_compare.py create mode 100644 idatui/graph_triskel.py 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 ``, 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 ``, 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 `_ 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 + # ), 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 -- cgit v1.3.1-sl0p