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