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, 100 insertions, 20 deletions

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