diff options
| -rw-r--r-- | docs/GRAPH_VIEW.md | 8 | ||||
| -rw-r--r-- | idatui/app.py | 3 | ||||
| -rw-r--r-- | idatui/graph.py | 23 | ||||
| -rw-r--r-- | idatui/graph_triskel.py | 141 | ||||
| -rw-r--r-- | tests/test_graph.py | 38 |
5 files changed, 181 insertions, 32 deletions
diff --git a/docs/GRAPH_VIEW.md b/docs/GRAPH_VIEW.md index d588b3d..d4f0180 100644 --- a/docs/GRAPH_VIEW.md +++ b/docs/GRAPH_VIEW.md @@ -61,9 +61,13 @@ text. `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 +`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. +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 | |---|---|---| diff --git a/idatui/app.py b/idatui/app.py index b2b1722..4b3d5fb 100644 --- a/idatui/app.py +++ b/idatui/app.py @@ -2685,6 +2685,9 @@ class GraphView(NavMixin, ScrollView, can_focus=True): # installed" on its own sends people to check the wrong python. note = ("" if graph_triskel.available() else f" (no pytriskel in {sys.executable})") + # A fallback with no reason is a bug report nobody can file. + if self.lay and self.lay.stats.get("engine_error"): + note = f" \u2014 {self.lay.stats['engine_error']}" self.app._status(f"graph: engine {self._engine} \u2192 {got}{note}") def action_center(self) -> None: diff --git a/idatui/graph.py b/idatui/graph.py index fbaf87f..f40de07 100644 --- a/idatui/graph.py +++ b/idatui/graph.py @@ -702,11 +702,18 @@ def _native_engine(g: _Graph, root: int) -> tuple[list[Route], int]: #: 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 +#: Above this many blocks ``auto`` stays native. Layout runs on every open and +#: every zoom keypress, so this is an interactivity budget, not a correctness +#: one. Triskel's cost knees hard (measured on `ls`, 400 functions): +#: +#: blocks 174 233 256 329 424 495 +#: native 25 72 23 93 144 203 ms +#: triskel 66 489 266 555 1501 1968 ms +#: +#: 180 keeps the worst auto-triskel layout in the tens of milliseconds. Raising +#: it buys prettier pictures of graphs nobody can read anyway -- the view +#: refuses to draw past 400 blocks at all. +AUTO_TRISKEL_MAX_BLOCKS = 180 def _pick_engine(engine: str | None, nblocks: int) -> str: @@ -735,6 +742,7 @@ def layout(blocks: list[Block], sizer, entry: int | None = None, g, root = _build(blocks, sizer, entry) layers = 0 + err = None if not g.nodes: routes = [] elif name == "triskel": @@ -744,8 +752,10 @@ def layout(blocks: list[Block], sizer, entry: int | None = None, 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. + # Keep the REASON: a fallback the user can see but not explain is + # only marginally better than a crash. _LOG.warning("triskel layout failed (%s), falling back", exc) - name = "native+triskel-failed" + name, err = "native (triskel failed)", f"{type(exc).__name__}: {exc}" g, root = _build(blocks, sizer, entry) routes, layers = _native_engine(g, root) else: @@ -836,6 +846,7 @@ def layout(blocks: list[Block], sizer, entry: int | None = None, "edges": len(g.edges), "back": sum(1 for e in g.edges if e.back), "engine": name, + "engine_error": err, "ms": (time.perf_counter() - t0) * 1000, } return Layout(nodes=order, by_id={n.id: n for n in g.nodes.values()}, diff --git a/idatui/graph_triskel.py b/idatui/graph_triskel.py index 343e6f5..1741f17 100644 --- a/idatui/graph_triskel.py +++ b/idatui/graph_triskel.py @@ -271,6 +271,56 @@ def _hits(by_col, by_row, p: tuple[int, int], q: tuple[int, int]) -> list[G.Node if n.x < hi and lo < n.right] +def _free_line(blocked: list[tuple[int, int]], want: int, + allow: tuple[int, int] | None = None) -> int | None: + """The coordinate nearest ``want`` that is in none of ``blocked``. + + ``blocked`` is a list of inclusive intervals. Jumping to the near side of + the *first* box in the way is not enough in a dense layout -- that column is + very often inside the next box along -- so consider every box the run + passes and step out of each interval in turn. + + ``allow`` constrains the result to an inclusive range, which is how a port + stays on its own box's border: everything outside becomes blocked. + """ + if allow is not None: + lo, hi = allow + if lo > hi: + return None + blocked = list(blocked) + [(hi + 1, hi + 1 + 10 ** 6)] + if lo > 0: + blocked.append((0, lo - 1)) + if not blocked: + return want + merged: list[list[int]] = [] + for lo, hi in sorted(blocked): + if merged and lo <= merged[-1][1] + 1: + merged[-1][1] = max(merged[-1][1], hi) + else: + merged.append([lo, hi]) + + def inside(v: int) -> list[int] | None: + for iv in merged: + if iv[0] <= v <= iv[1]: + return iv + return None + + if inside(want) is None: + return want + low = want + while (iv := inside(low)) is not None: + low = iv[0] - 1 + if low < 0: + low = None + break + high = want + while (iv := inside(high)) is not None: + high = iv[1] + 1 + if low is None: + return high + return low if want - low <= high - want else high + + def _repair_boxes(g: G._Graph, routes: list[G.Route]) -> int: """Detour any segment that runs through a box. Returns the number moved. @@ -289,38 +339,85 @@ def _repair_boxes(g: G._Graph, routes: list[G.Route]) -> int: and the arrowhead, and those belong on the border. """ by_col, by_row = _box_index(g) + real = [n for n in g.nodes.values() if not n.dummy] moved = 0 for rt in routes: - for i in range(1, len(rt.pts) - 2): - p, q = rt.pts[i], rt.pts[i + 1] - for _ in range(4): - hit = _hits(by_col, by_row, p, q) - if not hit: - break - n = hit[0] + # Moving one segment stretches the two beside it, which can push THEM + # into a box, so sweep until the route stops changing. Three passes is + # plenty in practice and bounds the work on a pathological route. + for _ in range(3): + dirty = False + last = len(rt.pts) - 2 + for i in range(0, len(rt.pts) - 1): + p, q = rt.pts[i], rt.pts[i + 1] + if not _hits(by_col, by_row, p, q): + continue if p[1] == q[1]: # vertical: shift column - col = p[1] - out = n.x - 1 # nearest side of the box - if col - n.x > n.right - col or out < 0: - out = n.right + 1 # never detour off-canvas - p, q = (p[0], out), (q[0], out) - else: # horizontal: shift row - row = p[0] - out = n.y - 1 - if row - n.y > n.bottom - row or out < 0: - out = n.bottom + 1 - p, q = (out, p[1]), (out, q[1]) - rt.pts[i], rt.pts[i + 1] = p, q + lo, hi = sorted((p[0], q[0])) + blocked = [(n.x + 1, n.right - 1) for n in real + if n.y < hi and lo < n.bottom] + # The first and last segments carry the port and the + # arrowhead, so they may only move ALONG their own box's + # border -- but move they must: triskel is happy to park a + # block directly above its successor and drive the final + # approach straight through it. Another port on the same + # border is almost always free. + allow = None + if i == 0 or i == last: + ends = [] + if i == 0: + ends.append(g.nodes[rt.edge.src]) + if i == last: + ends.append(g.nodes[rt.edge.dst]) + allow = (max(n.x + 1 for n in ends), + min(n.right - 1 for n in ends)) + col = _free_line(blocked, p[1], allow) + if col is None: + continue + rt.pts[i], rt.pts[i + 1] = (p[0], col), (q[0], col) + elif i not in (0, last): # horizontal: shift row + lo, hi = sorted((p[1], q[1])) + blocked = [(n.y + 1, n.bottom - 1) for n in real + if n.x < hi and lo < n.right] + row = _free_line(blocked, p[0]) + if row is None: + continue + rt.pts[i], rt.pts[i + 1] = (row, p[1]), (row, q[1]) + else: + continue moved += 1 + dirty = True + if not dirty: + break return moved def _verify(g: G._Graph, routes: list[G.Route]) -> None: - """Raise if any segment still crosses a box, so ``layout()`` falls back. + """Raise if the drawing breaks an invariant, so ``layout()`` falls back. - The invariant is worth more than the engine: a layout with more crossings - beats one that draws edges through the code. + The invariants are worth more than the engine: a layout with more crossings + beats one that draws edges through the code, or one block over another. + + Overlapping boxes are triskel's, not ours -- it superimposes independently + laid out SESE regions, and on 2 of `ls`'s 400 functions two blocks end up a + couple of columns into each other in float space, before any rounding. In a + PNG that is a cosmetic nick on a border. Here the boxes are made of text, so + one block's disassembly overwrites another's. """ + rows: dict[int, list[G.Node]] = {} + for n in g.nodes.values(): + if n.dummy: + continue + for r in range(n.y, n.y + n.h): + rows.setdefault(r, []).append(n) + for r, boxes in rows.items(): + boxes.sort(key=lambda n: n.x) + for a, b in zip(boxes, boxes[1:]): + if b.x <= a.right: + raise RuntimeError( + f"blocks {a.id} and {b.id} overlap on row {r} " + f"(x[{a.x},{a.right}] vs x[{b.x},{b.right}])") + by_col, by_row = _box_index(g) for rt in routes: for p, q in zip(rt.pts, rt.pts[1:]): diff --git a/tests/test_graph.py b/tests/test_graph.py index d882f94..96d4f85 100644 --- a/tests/test_graph.py +++ b/tests/test_graph.py @@ -211,14 +211,38 @@ def t_corpus(path: str) -> None: print(f"\ncorpus: {len(recs)} functions from {path}") worst_ms = 0.0 worst_name = "" + fellback: list[tuple[str, str | None]] = [] + worst_any_ms = 0.0 + worst_any_name = "" t0 = time.perf_counter() for rec in recs: 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 = layout(blocks, sizer) - if lay.stats["ms"] > worst_ms: + # A SILENT fallback is the failure mode that matters here: the engine + # under test quietly stops being the engine under test, and every + # invariant below then passes for the wrong reason. `ls` main (329 + # blocks) used to fall back on all three zoom levels because a final + # approach was routed through the block above its target. + # + # Falling back is legitimate -- it is how an upstream layout defect is + # kept off the screen -- so this asserts it is rare and explained, + # not that it never happens. + if ENGINE != "auto" and lay.stats["engine"] != ENGINE: + fellback.append((rec["name"], lay.stats.get("engine_error"))) + check(bool(lay.stats.get("engine_error")), + f"corpus {rec['name']}: a fallback must record its reason") + # Time the engine only on the functions it would actually be ASKED for. + # `auto` hands anything over AUTO_TRISKEL_MAX_BLOCKS to native, and the + # view refuses to draw past 400 blocks at all, so a forced triskel run + # on a 495-block monster times a call the app cannot make. + reachable = (ENGINE != "triskel" + or len(blocks) <= G.AUTO_TRISKEL_MAX_BLOCKS) + if reachable and lay.stats["ms"] > worst_ms: worst_ms, worst_name = lay.stats["ms"], rec["name"] + if lay.stats["ms"] > worst_any_ms: + worst_any_ms, worst_any_name = lay.stats["ms"], rec["name"] check(no_box_overlap(lay), f"corpus {rec['name']}: boxes must not overlap") check(len(lay.nodes) == len(blocks), f"corpus {rec['name']}: every block is placed") @@ -230,7 +254,17 @@ def t_corpus(path: str) -> None: total = (time.perf_counter() - t0) * 1000 print(f" laid out {len(recs)} functions in {total:.0f} ms " f"(worst {worst_ms:.0f} ms: {worst_name})") - check(worst_ms < 2000, f"corpus: worst layout under 2s ({worst_ms:.0f} ms)") + if fellback: + print(f" {len(fellback)} fell back to native:") + for name, why in fellback: + print(f" {name}: {why}") + check(len(fellback) <= max(2, len(recs) // 20), + f"corpus: {ENGINE} fell back on {len(fellback)}/{len(recs)} functions") + check(worst_ms < 2000, f"corpus: worst REACHABLE layout under 2s " + f"({worst_ms:.0f} ms: {worst_name})") + # Nothing may blow up quadratically even when forced past its own limits. + check(worst_any_ms < 5000, f"corpus: worst layout at any size under 5s " + f"({worst_any_ms:.0f} ms: {worst_any_name})") def main() -> int: |