1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
# 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 |
| minimap | click to jump the view there, drag to scrub |
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 operation, `flowchart(addr)` in
`idatui/codemode_client.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.
Clicking it **snaps to the nearest block** and takes the cursor with it;
dragging scrubs from block to block. It deliberately does not scroll to the
coordinate you clicked: blocks cover only a few percent of a laid-out graph
(4.6% on an 87-block function, under 1% on a 424-block one) and the rest is the
padding that keeps edges apart, so a coordinate-accurate jump parks you in empty
space with the cursor left behind. For the same reason, a drag-pan or a
`ctrl+d`/`pageup` that ends with **no block on screen at all** eases to the
nearest one — only when nothing is visible, so it never fights a deliberate pan. Because it floats over the canvas rather than living in it,
`on_click` has to test the minimap's hit-box **before** translating the click
into canvas coordinates — otherwise a click on the overview reads as a click on
whatever block happens to lie underneath it. `_minimap_rect()` is the single
source of truth for both the drawing and the hit-test.
## 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).
|
