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.

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.