diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/GRAPH_VIEW.md | 83 | ||||
| -rw-r--r-- | docs/TRISKEL_EVAL.md | 187 |
2 files changed, 263 insertions, 7 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. |