| Commit message (Collapse) | Author | Age | Files | Lines |
|---|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
"EMPTY BL" in the status bar is triskel's own bracket-list assertion from
its SESE pass, and it turned out to be the mild version of the problem.
Triskel's graph root is whichever node was created FIRST, and every
analysis walks out from it. Anything unreachable from that node is
undefined behaviour. We were:
- creating nodes in id order, so the root was the lowest-numbered
block rather than the entry, and
- splitting only WEAKLY connected components, which says nothing about
reachability.
A 7-block CFG whose entry has no successors -- IDA hands those out for
thunks and for dead code it could not resolve -- SEGFAULTS the
interpreter. That is unsurvivable: it takes the session down and there
is no exception to fall back from.
Now the entry is created first, orphan blocks are attached to it with
phantom edges that steer placement but are never drawn (one edge usually
adopts a whole orphan subgraph, attached at a node no other orphan
reaches), and reachability is asserted in python BEFORE crossing into
C++. This replaces the component splitting entirely: one layout instead
of N stacked side by side, and triskel gets to place the orphans.
The reproducer is now a test (t_unreachable_entry). Remaining fallbacks
on the ls corpus are 8/1200 layouts, all the upstream box-overlap
defect, all but one on 300-500 block functions.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
"engine triskel -> native+triskel-failed" was unreadable and, worse,
gave no reason: the cause went to a logger a TUI user never sees.
Dumped all 400 functions of bin/ls (echo's 128 were not enough) and swept
them at three zoom levels: 6 of 1200 layouts fell back, all of them my
own _verify tripping over a detour that could not be placed.
- the detour jumped to the nearest side of the FIRST box in the way,
which in a dense layout is usually inside the next box along. It now
collects every box the run passes and picks the nearest genuinely
free line.
- it skipped the first and last segments because they carry the port
and the arrowhead. But that is exactly where the failures were:
triskel is happy to park a block directly above its successor and
drive the final approach straight through it. Those segments may now
move ALONG their own box's border, which is free almost every time.
- repairs are swept to a fixed point: moving one segment stretches its
neighbours, which can push those into a box.
0/1200 fallbacks after that. Then the bigger corpus turned up a second,
genuinely upstream defect: superimposing SESE regions can leave two
blocks a couple of columns into each other (2 of ls's 400 functions,
in float space, before rounding). Cosmetic in a PNG; here the boxes are
made of text, so one block's disassembly overwrites another's. _verify
now checks it and falls back, which is the right trade.
Reporting, so this is never mute again:
- stats["engine_error"] carries the reason, the status line shows it,
and the label is "native (triskel failed)".
- the corpus test asserts fallbacks are rare AND explained, rather
than asserting they never happen.
Also lowered AUTO_TRISKEL_MAX_BLOCKS 250 -> 180. Layout runs on every
zoom keypress and triskel knees hard past ~175 blocks (174: 66ms,
233: 489ms, 329: 555ms). The old cap allowed a 489ms stall. The corpus
timing check now measures only sizes `auto` can actually reach, plus a
5s ceiling so nothing blows up quadratically when forced.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
`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.
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
Fourteen test files, each its own __main__, and no way to run them but from
memory -- so in practice you ran the one you were working on and hoped. Worse,
nothing said which files need a licensed IDA and a real worker (minutes) and
which are pure stdlib (milliseconds), so the cheap ones nobody ran either.
tests/run.py runs the lot and prints one table. --fast selects only the suites
that need nothing, which is 257 checks in half a second under any python3 --
that's the one you run between edits.
The classification lives in the test files, not in a table here that would rot
the first time someone adds a test: each declares NEEDS_IDA at module scope and
run.py reads it with ast (it can't import them -- they run their suite at
import). A file without the marker is a hard error rather than a silent guess.
|
|
|
Textbook Sugiyama, the same shape IDA's own graph uses: break cycles,
longest-path layering, dummy nodes, median/transposition ordering,
priority x-coords, then port-and-channel edge routing. Pure python -- no
IDA, no Textual, no I/O -- so it is tested offline in milliseconds with no
worker, which is the whole reason the hard part is kept out of the UI.
Dummy nodes are what make routing tractable: a long edge occupies real
horizontal space, so no edge ever has to cross a box. The tests assert
exactly that over a 128-function corpus, and it holds at 0.
Two things cost real time to find. A self-loop never drains its own
in-degree, so it deadlocks the ranking and collapses the graph into three
layers, 280 columns wide -- they are dropped from the layout and drawn as
a marker. And crossing minimisation is the entire runtime: recounting
globally per candidate swap is O(n^3) and took 20.4s on a 424-block
function, against 152ms for Fenwick inversion counting plus a local
O(deg*deg) swap delta.
The result is not a painted canvas -- that function is ~13M cells. It is
an index: per-row runs, bucketed vertical intervals, and point marks,
queried one row at a time.
|
