diff options
Diffstat (limited to 'docs')
| -rw-r--r-- | docs/GRAPH_VIEW.md | 145 |
1 files changed, 145 insertions, 0 deletions
diff --git a/docs/GRAPH_VIEW.md b/docs/GRAPH_VIEW.md new file mode 100644 index 0000000..ccddfe7 --- /dev/null +++ b/docs/GRAPH_VIEW.md @@ -0,0 +1,145 @@ +# Graph view — the function's control flow, in character cells + +**Space** swaps the code view for an IDA-style basic-block graph of the current +function. Space again returns to the text. It is opt-in, off by default, and +lives in its own module: with graph mode off nothing else in the app does any +extra work. + +``` + ┌─ sub_61D0 ──────────────────────┐ + │ 000061D0 sub_61D0 endbr64 │ ┌─ 9 blocks ──────┐ + │ 000061D4 push rbp │ │ █████████ │ + │ ... │ │ ·███████████ │ + │ 00006200 jmp short loc_622C │ │ ████·███████ │ + └─────────────────┬───────────────┘ └─────────────────┘ + │ + ┌─ loc_622C ───────▼─────────────────┐ + │ 0000622C loc_622C mov eax, [rcx] │ + │ 00006231 jbe short loc_6208 │ + └──────────┬─────────────┬───────────┘ + ╭─────────╯ ╰──────────╮ +``` + +## Keys + +| key | | +|---|---| +| `Space` | graph ⇄ text | +| `j` `k` | line up/down, crossing into the next/previous block | +| `h` `l` | column left / right | +| `J` `K` | follow an edge to a successor / predecessor block | +| `w` `b` | next / previous block in layout order | +| `0` | jump to the entry block | +| `z` | zoom: full → compact → collapsed | +| `m` | show / hide the minimap | +| `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 | +| `Tab` | leave for the pseudocode of the block you're on | +| mouse | drag to pan, click to place the cursor, double-click to follow | + +Graph mode is **sticky**: following a call from the graph lands in the callee's +graph rather than dumping you back in the listing. + +## Why the boxes are cheap + +A node's body is **the same `Head` rows the listing renders** — fetched with the +same `heads` tool, carrying IDA's own colour tags, names and operand text. That +is the whole reason this feature is a few hundred lines instead of a rewrite: +syntax highlighting, the word-under-cursor highlight, the execution trail and +every editing verb work inside a box because they are working on listing rows. +Growing a second disassembly renderer for graph mode would have been the real +cost. + +The backend adds exactly one tool, `flowchart(addr)` in +`server/patch_server.py`, which returns block ranges and typed edges — **not** +text. + +## Layout (`idatui/graph.py`) + +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, +the same shape IDA's own graph uses: + +| step | what | notes | +|---|---|---| +| 1 | break cycles | DFS gray-set; back edges reversed for layout only | +| 2 | layer | longest-path ranking | +| 3 | dummies | a k-layer edge becomes k−1 dummy nodes | +| 4 | order | median sweeps + adjacent transposition | +| 5 | x-coords | priority/median sweeps, variable node widths | +| 6 | route | ports per border, one lane-packed channel per layer gap | + +Step 3 is what makes step 6 tractable: because every long edge occupies real +horizontal space as dummy nodes, **no edge ever has to cross a box**. That is +measured, not hoped — `tests/test_graph.py` counts edge cells landing inside a +box across a 128-function corpus and requires 0. + +Edges are coloured by IDA's convention: green = branch taken, red = falls +through, blue = the block's only successor, purple = loops back, amber = one arm +of an n-way switch. The edges touching the block under the cursor are brightened. +A self-loop is a `↺` on the block's top border rather than an edge. + +### Two traps worth remembering + +- **Self-loops deadlock the Kahn ranking.** A block that jumps to itself never + drains its own in-degree, so ranking stalls and every downstream block stays at + rank 0 — the graph collapses into three layers and comes out 280 columns wide. + They are dropped from the layout graph and drawn as a marker. `_assign_ranks` + also force-releases the most-constrained survivor if the queue ever drains + early, so a residual cycle degrades instead of exploding. +- **Crossing minimisation is where the time goes.** The naive transposition pass + recounts crossings globally per candidate swap: O(n³), which made a 424-block + function take **20.4 seconds**. Counting inversions with a Fenwick tree and + computing only the local `O(deg(a)·deg(b))` delta per swap took the same + function to **152 ms**, and the whole 128-function corpus from 21 s to 224 ms. + +## Rendering + +Nothing is pre-painted. A 424-block function lays out to ~13M cells, so +`graph.Painting` is an *index* — per-row horizontal runs, a bucketed interval +index of vertical runs, and point marks — and `GraphView.render_line(y)` asks it +for one row at a time, exactly like `ListingView`. Cost per frame is proportional +to the viewport, not the graph. + +Three zoom levels (`z`) trade detail for shape: **full** (address gutter + +instructions), **compact** (instructions only), **collapsed** (one summary row +per block). On `main` (87 blocks) that is a 1378×518 canvas down to 545×289. + +The **minimap** (`m`) is a coarse occupancy grid of the whole graph with the +viewport marked, drawn top-right and inset two columns — a `ScrollView` paints +its scrollbar over the last column, which otherwise eats the minimap's border. + +## Limits + +Above **400 blocks** the graph is refused with a message and you stay in the +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. + +## Driving it + +`graph` is an RPC verb (see `docs/RPC.md`), and it reports **structure**, not box +drawing characters — a driver wants blocks and edges, not glyphs: + +```bash +drive raw graph action=open # Space +drive raw graph action=show # blocks, edges, ranks, cursor +drive raw graph action=block target=0x6250 +drive raw graph action=succ # J +drive raw graph action=zoom +``` + +## Offline tools + +- `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. +- `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). |