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.

1 files changed, 119 insertions, 25 deletions

diff --git a/idatui/graph.py b/idatui/graph.py
index baee597..fbaf87f 100644
--- a/idatui/graph.py
+++ b/idatui/graph.py
@@ -28,9 +28,13 @@ row at a time (``cells_at_row``), exactly like the listing's ``render_line``.
 """
 from __future__ import annotations
 
+import logging
+import os
 import time
 from dataclasses import dataclass, field
 
+_LOG = logging.getLogger(__name__)
+
 # Terminal cells are about twice as tall as they are wide, so horizontal gaps
 # need roughly 2x the cell count of vertical gaps to look square.
 HGAP = 3           # min columns between two boxes in a layer
@@ -100,6 +104,12 @@ class Edge:
     kind: str = E_UNCOND
     back: bool = False
     chain: list[int] = field(default_factory=list)
+    #: ``src``/``dst`` are swapped relative to control flow. The native engine
+    #: reverses back edges so layering sees a DAG; the triskel engine handles
+    #: cycles itself and leaves them alone. Everything downstream that has to
+    #: recover the real direction (succ/pred, arrowheads) reads THIS, not
+    #: ``back`` -- which is now purely a style bit.
+    flipped: bool = False
 
     @property
     def style(self) -> str:
@@ -151,6 +161,7 @@ def _break_cycles(g: _Graph, root: int) -> None:
     for e in g.edges:
         if e.back:
             e.src, e.dst = e.dst, e.src
+            e.flipped = True
 
 
 # --------------------------------------------------------- 2. layering
@@ -461,6 +472,9 @@ class Route:
     pts: list[tuple[int, int]]
     head: bool = True      # arrowhead (target is a real block)
     tail: bool = True      # port tee (source is a real block)
+    #: the polyline is drawn against control flow (a reversed back edge), so the
+    #: arrowhead belongs at ``pts[0]`` and the port tee at ``pts[-1]``.
+    flipped: bool = False
 
 
 def _route(g: _Graph, layers: list[list[int]]) -> list[Route]:
@@ -521,8 +535,8 @@ def _route(g: _Graph, layers: list[list[int]]) -> list[Route]:
         else:
             ych = chan_y[na.rank] + lanes.get((a, b, id(e)), 0)
             pts = [(y0, x0), (ych, x0), (ych, x1), (y1, x1)]
-        routes.append(Route(edge=e, pts=pts,
-                            head=not nb.dummy, tail=not na.dummy))
+        routes.append(Route(edge=e, pts=pts, head=not nb.dummy,
+                            tail=not na.dummy, flipped=e.flipped))
     return routes
 
 
@@ -646,20 +660,25 @@ class Layout:
         return None
 
 
-def layout(blocks: list[Block], sizer, entry: int | None = None) -> Layout:
-    """Lay out ``blocks``. ``sizer(block) -> (width, height)`` in cells."""
-    t0 = time.perf_counter()
+def _build(blocks: list[Block], sizer, entry: int | None) -> tuple[_Graph, int]:
+    """The block list as a layout graph, plus the entry node id.
+
+    Shared by both engines, and re-run from scratch if one of them has to fall
+    back, because an engine positions nodes in place.
+    """
     g = _Graph()
     for b in blocks:
         w, h = sizer(b)
+        b.selfloop = False
         g.add(Node(id=b.id, block=b, label=f"loc_{b.start:X}",
                    w=max(int(w), 4), h=max(int(h), 3)))
     for b in blocks:
         outs = [(d, k) for d, k in b.succs if d in g.nodes]
         for dst, kind in outs:
             if dst == b.id:
-                # A self-loop constrains nothing and would deadlock the Kahn
-                # ranking (its own in-degree never drains). Drawn as a marker.
+                # A self-loop constrains nothing, deadlocks the Kahn ranking
+                # (its own in-degree never drains) and makes triskel throw
+                # "EMPTY BL" from its bracket lists. Drawn as a marker instead.
                 b.selfloop = True
                 continue
             if len(outs) == 1:
@@ -667,15 +686,70 @@ def layout(blocks: list[Block], sizer, entry: int | None = None) -> Layout:
             g.edges.append(Edge(src=b.id, dst=dst, kind=kind))
 
     root = entry if entry in g.nodes else (min(g.nodes) if g.nodes else 0)
-    if g.nodes:
-        _break_cycles(g, root)
-        _assign_ranks(g, root)
-        _add_dummies(g)
-        layers = _order_layers(g, root)
-        _assign_x(g, layers)
-        routes = _route(g, layers)
+    return g, root
+
+
+def _native_engine(g: _Graph, root: int) -> tuple[list[Route], int]:
+    """Layered Sugiyama in cells: the pipeline documented at the top."""
+    _break_cycles(g, root)
+    _assign_ranks(g, root)
+    _add_dummies(g)
+    layers = _order_layers(g, root)
+    _assign_x(g, layers)
+    return _route(g, layers), len(layers)
+
+
+#: Engine names accepted by ``layout(engine=...)`` and ``IDATUI_GRAPH_ENGINE``.
+ENGINES = ("auto", "native", "triskel")
+
+#: Above this many blocks ``auto`` stays native: triskel's SESE decomposition
+#: costs ~10x at 424 blocks (1.5s vs 145ms), and a layout that blocks the UI for
+#: a second is worse than a layout with more crossings. Measured, see
+#: docs/TRISKEL_EVAL.md.
+AUTO_TRISKEL_MAX_BLOCKS = 250
+
+
+def _pick_engine(engine: str | None, nblocks: int) -> str:
+    want = (engine or os.environ.get("IDATUI_GRAPH_ENGINE") or "auto").lower()
+    if want not in ENGINES:
+        want = "auto"
+    if want == "auto":
+        from . import graph_triskel
+        if nblocks <= AUTO_TRISKEL_MAX_BLOCKS and graph_triskel.available():
+            return "triskel"
+        return "native"
+    return want
+
+
+def layout(blocks: list[Block], sizer, entry: int | None = None,
+           engine: str | None = None) -> Layout:
+    """Lay out ``blocks``. ``sizer(block) -> (width, height)`` in cells.
+
+    ``engine`` picks the layout backend: ``native`` (pure python, always
+    available), ``triskel`` (SESE decomposition via the C++ library, far fewer
+    crossings) or ``auto``. Defaults to ``$IDATUI_GRAPH_ENGINE`` or ``auto``.
+    A triskel failure is never fatal: it falls back to native.
+    """
+    t0 = time.perf_counter()
+    name = _pick_engine(engine, len(blocks))
+    g, root = _build(blocks, sizer, entry)
+
+    layers = 0
+    if not g.nodes:
+        routes = []
+    elif name == "triskel":
+        from . import graph_triskel
+        try:
+            routes, layers = graph_triskel.run(g, root)
+        except Exception as exc:                      # noqa: BLE001
+            # Native code with a history of throwing on degenerate CFGs. The
+            # graph view is a convenience; losing it beats losing the session.
+            _LOG.warning("triskel layout failed (%s), falling back", exc)
+            name = "native+triskel-failed"
+            g, root = _build(blocks, sizer, entry)
+            routes, layers = _native_engine(g, root)
     else:
-        layers, routes = [], []
+        routes, layers = _native_engine(g, root)
 
     # ---- paint into the index -----------------------------------------
     p = Painting()
@@ -708,40 +782,60 @@ def layout(blocks: list[Block], sizer, entry: int | None = None) -> Layout:
             ch = CORNER.get((_dir(a, b), _dir(b, c)))
             if ch and not blocked(*b):
                 p.add_mark(b[0], b[1], ch, style, eid)
-        # A back edge was reversed for layering, so its polyline runs from the
-        # loop HEAD down to the tail: the arrow belongs at the start, pointing
-        # up into the block control returns to.
+        # Where the arrowhead goes is a question about CONTROL FLOW, not about
+        # geometry. The native engine reverses back edges for layering, so their
+        # polyline runs from the loop HEAD down to the tail and the arrow
+        # belongs at the start, pointing up into the block control returns to.
+        # The triskel engine keeps the real direction and routes the loop around
+        # the side of the graph, so the arrow is at the end like any other edge.
+        # ``rt.flipped`` is the only thing that distinguishes the two.
         first, last = rt.pts[0], rt.pts[-1]
-        if e.back:
+        down_first = rt.pts[1][0] > first[0] if len(rt.pts) > 1 else True
+        down_last = last[0] > rt.pts[-2][0] if len(rt.pts) > 1 else True
+        if rt.flipped:
             if rt.tail:
-                p.add_mark(first[0], first[1], "\u25b2", style, eid)
+                p.add_mark(first[0], first[1],
+                           "\u25b2" if down_first else "\u25bc", style, eid)
             if rt.head:
-                p.add_mark(last[0], last[1], "\u2534", style, eid)
+                p.add_mark(last[0], last[1],
+                           "\u2534" if down_last else "\u252c", style, eid)
         else:
             if rt.tail:
-                p.add_mark(first[0], first[1], "\u252c", style, eid)
+                p.add_mark(first[0], first[1],
+                           "\u252c" if down_first else "\u2534", style, eid)
             if rt.head:
-                p.add_mark(last[0], last[1], "\u25bc", style, eid)
+                p.add_mark(last[0], last[1],
+                           "\u25bc" if down_last else "\u25b2", style, eid)
 
     succ: dict[int, list[tuple[int, str]]] = {n.id: [] for n in real}
     pred: dict[int, list[tuple[int, str]]] = {n.id: [] for n in real}
     for e in g.edges:
-        a, b = (e.dst, e.src) if e.back else (e.src, e.dst)   # undo reversal
+        a, b = (e.dst, e.src) if e.flipped else (e.src, e.dst)   # undo reversal
         if a in succ:
             succ[a].append((b, e.style))
         if b in pred:
             pred[b].append((a, e.style))
 
+    # The canvas has to cover the EDGES too, not just the boxes. Under the
+    # native engine that is the same thing -- dummy nodes reserve space, so no
+    # edge is ever outside the boxes' bounding box. Triskel routes a loop around
+    # the side of the graph, past every node, and sizing on boxes alone clipped
+    # exactly the edges that make its layouts worth having.
     width = max((n.right + 1 for n in real), default=1)
     height = max((n.y + n.h for n in real), default=1)
+    for rt in routes:
+        for r, c in rt.pts:
+            width = max(width, c + 1)
+            height = max(height, r + 1)
     order = sorted(real, key=lambda n: (n.rank, n.order))
     stats = {
         "blocks": len(blocks),
         "nodes": len(g.nodes),
         "dummies": len(g.nodes) - len(real),
-        "layers": len(layers),
+        "layers": layers,
         "edges": len(g.edges),
         "back": sum(1 for e in g.edges if e.back),
+        "engine": name,
         "ms": (time.perf_counter() - t0) * 1000,
     }
     return Layout(nodes=order, by_id={n.id: n for n in g.nodes.values()},