diff options
Diffstat (limited to '')
| -rw-r--r-- | docs/GRAPH_VIEW.md | 106 |
1 files changed, 98 insertions, 8 deletions
diff --git a/docs/GRAPH_VIEW.md b/docs/GRAPH_VIEW.md index 29b280e..0b24aa5 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 | @@ -53,10 +54,64 @@ Growing a second disassembly renderer for graph mode would have been the real cost. The backend adds exactly one operation, `flowchart(addr)` in -`idatui/codemode_client.py`, which returns block ranges and typed edges — **not** +`idatui/nexus_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 180 +blocks, and falls back to **native** otherwise — including if triskel raises, +which is never fatal, and the status line then says why. + +The 180 is an interactivity budget: layout runs on every open and every zoom +keypress, and triskel's cost knees hard just past it (174 blocks: 66 ms; +233 blocks: 489 ms; 329: 555 ms; 424: 1.5 s, against native's 25/72/93/144). + +| | native | triskel | +|---|---|---| +| algorithm | layered Sugiyama, below | SESE decomposition ([paper](https://hal.science/hal-04996939)) | +| ships with | always, pure python | needs `pytriskel` (patched fork, unpublished) | +| 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). + +### 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. Triskel's graph +root is **whichever node was created first**, and every one of its analyses walks +out from there, so anything the root cannot reach is undefined behaviour — it +throws `EMPTY BL` from its SESE bracket lists, or, when the entry block has no +successors at all, segfaults. That is not survivable: a crash in a C extension +takes the TUI with it, with no chance to fall back. So the entry is created +first, orphan blocks are attached to it with **phantom edges** that steer the +layout but are never drawn, and reachability is *asserted in python* before +crossing into C++. + +The rest is handled before the call too: self-loops (drawn as `↺`; they make +triskel throw), and edges routed through a block, which are detoured and +re-verified. Whatever is left over falls back to native rather than reach the +screen wrong — currently 8 layouts in 1200 (`ls`, three zoom levels each), all +of them triskel leaving two boxes a few columns into each other, which in a +terminal means one block's disassembly overwriting another's. + +## 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 +185,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 +213,36 @@ 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_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`. + +It needs `pytriskel`, and specifically a **patched build that is not published +anywhere yet**. 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. Until that fork is released you will get the +native engine — which is the default, ships with the repo, and is fully +supported. The rest of this section only applies if you already have a patched +build tree. + +**Install it into the interpreter the launcher actually runs**, which is +`$IDATUI_PYTHON` and defaults to `~/ida-venv/bin/python` — *not* the repo's +`.venv`, which is only what the tests use. Getting this wrong is the one way to +see `no pytriskel in ...` in the status bar while `tests/test_graph.py` happily +exercises both engines; the message names the interpreter for that reason. + +```bash +"$IDATUI_PYTHON" -m pip install /path/to/triskel/bindings/python +.venv/bin/python -m pip install /path/to/triskel/bindings/python # for the tests +``` + +Needs cmake, ninja and a C++23 compiler at install time; the wheel is built from +source for whichever interpreter runs pip. `$IDATUI_TRISKEL_PATH` can point at a +build tree instead of installing. |