summaryrefslogtreecommitdiff
path: root/design/mock/graph.py
diff options
context:
space:
mode:
authorGabriel Schneider <[email protected]>2026-11-11 10:38:37 -0300
committerGabriel Schneider <[email protected]>2026-11-11 10:40:03 -0300
commit6142fa676731e158622ca7956c150c58bc57f1f2 (patch)
tree7413e5740a83c07caa769ee35c57cb770875e0dc /design/mock/graph.py
parent6a7a87b8ecb7902de5640cad00028997825024d2 (diff)
downloadcomputeranim-6142fa676731e158622ca7956c150c58bc57f1f2.tar.gz
computeranim-6142fa676731e158622ca7956c150c58bc57f1f2.zip
design: the graph of a function's blocks; two runs as a pair
From the user. The disassembly's alternate form at a larger scale is the graph of its basic blocks: a block a box of rows with its offset, lines and visit count; execution flows down and a back edge is the one thing that climbs, in its loop's lane with the turn count; what the run never reached folds away. On the map it takes the disassembly's place; in the working frame a blocks lens draws its shape and the rows are its view. Verbs leave and turn carry the mark along an edge. Two runs of one program share a frame as a pair: the seam is the gutter, the source shared above, rows only one run has and values that differ marked at the seam. The scene it is made for sets a plain build against an ASan one in a stack overflow: the frame beside its shadow bytes, the store beside its check, and the step where they part. Co-Authored-By: Claude Fable 5.2 <[email protected]> Claude-Session: https://claude.ai/code/session_016Y9MNCKgYCGiANnEwcEQxa
Diffstat (limited to 'design/mock/graph.py')
-rw-r--r--design/mock/graph.py583
1 files changed, 583 insertions, 0 deletions
diff --git a/design/mock/graph.py b/design/mock/graph.py
new file mode 100644
index 0000000..e9b8f2b
--- /dev/null
+++ b/design/mock/graph.py
@@ -0,0 +1,583 @@
+#!/usr/bin/env python3
+"""The disassembly's other form: a function as a graph of its basic blocks, with what the run did on it.
+
+ python3 -B graph.py # 22-graph-sort, 23-graph-open, 24-graph-strip, 25-blocks-lens (.svg)
+
+Data: sort and reverse from anim/tools/sort.c and list.c (cc -O0 -g -no-pie), their disassembly in
+sort-O0.dis and reverse-O0.dis (objdump -dl), the paths their runs took from `ztrace dbg` stepped by instruction;
+libc's `open` from objdump of /usr/lib/libc.so.6 (libc-open.dis), its path the one mock 16's run took.
+"""
+import re
+from collections import Counter
+
+import gen
+import dense as D
+import context as C
+from context import (PAGE, RAISED, RULE, VELLUM, BRIGHT, DIM, FAINT, GOLD, KW, CODE, HEAP, STACK, DATA, A, S, ROW, TAG,
+ PAD, MONO, BOLD, b, ph, mix, Svg)
+
+HERE = __file__.rsplit("/", 1)[0]
+NORETURN = {"__stack_chk_fail", "__syscall_do_cancel"}
+TRAIL = gen.TRAIL
+
+
+def read_dis(name, lines=True):
+ """(address, line, mnemonic, operands, target) from objdump -d[l] -M intel."""
+ out, line = [], None
+ for l in open(f"{HERE}/{name}"):
+ m = re.search(r"\.c:(\d+)", l)
+ if m and not re.match(r"^\s+[0-9a-f]+:", l):
+ line = int(m.group(1))
+ continue
+ m = re.match(r"^\s+([0-9a-f]+):\s+(\S+)\s*(.*)$", l)
+ if not m:
+ continue
+ mnem, ops = m.group(2), m.group(3)
+ if mnem in ("addr32", "bnd", "notrack") and ops: # a prefix: the instruction is what follows it
+ mnem, _, ops = ops.partition(" ")
+ ops = ops.strip()
+ tgt = re.match(r"([0-9a-f]+) <([^>]+)>", ops)
+ callee = tgt.group(2) if tgt else None
+ ops = re.sub(r"\s*<[^>]+>", "", re.sub(r"\s+#.*", "", ops)).strip()
+ mn, ops = D.conv(mnem, ops)
+ out.append((int(m.group(1), 16), line if lines else None, mn, ops, int(tgt.group(1), 16) if tgt else None, callee))
+ return out
+
+
+class Block:
+ def __init__(self, name, rows):
+ self.name, self.rows = name, rows
+ self.a = rows[0][0]
+ self.out = [] # (target name, kind): taken, fall, jmp
+ self.ret = rows[-1][2] == "ret"
+
+
+def blocks(insns, base):
+ """Basic blocks: a leader at the entry, at every jump's target and after every jump, ret or call that does not
+ return. Padding (nops after a jump) is left out. Names are offsets: +5f."""
+ lo, hi = insns[0][0], insns[-1][0]
+ lead = {lo}
+ for i, (a, ln, mn, ops, t, callee) in enumerate(insns):
+ ends = mn.startswith("j") or mn == "ret" or (mn == "call" and callee in NORETURN)
+ if ends and i + 1 < len(insns):
+ lead.add(insns[i + 1][0])
+ if mn.startswith("j") and t and lo <= t <= hi:
+ lead.add(t)
+ out, cur = {}, []
+ for r in insns:
+ if r[0] in lead and cur:
+ out[cur[0][0]] = cur
+ cur = []
+ cur.append(r)
+ out[cur[0][0]] = cur
+ bl = {}
+ for a, rows in out.items():
+ if all(r[2] in ("nop", "xchg") for r in rows):
+ continue # padding between functions' paths: not a block
+ bl[a] = Block("+%x" % (a - base), rows)
+ order = sorted(bl)
+ for i, a in enumerate(order):
+ last = bl[a].rows[-1]
+ nxt = bl[a].rows[-1][0] + 1
+ nxt = next((x for x in order if x > a), None)
+ mn, t, callee = last[2], last[4], last[5]
+ if mn == "jmp":
+ bl[a].out = [(t, "jmp")]
+ elif mn.startswith("j"):
+ bl[a].out = [(t, "taken"), (nxt, "fall")]
+ elif mn == "ret" or (mn == "call" and callee in NORETURN):
+ bl[a].out = []
+ else:
+ bl[a].out = [(nxt, "fall")]
+ bl[a].out = [(x, k) for x, k in bl[a].out if x in bl]
+ return bl
+
+
+def layers(bl, entry):
+ """Back edges by a depth-first walk from the entry; layers by the longest path over the rest; a block that
+ returns in the last layer."""
+ back, state = set(), {}
+
+ def walk(a):
+ state[a] = 1
+ for t, k in bl[a].out:
+ if state.get(t) == 1:
+ back.add((a, t))
+ elif t not in state:
+ walk(t)
+ state[a] = 2
+ walk(entry)
+ lay = {a: 0 for a in bl}
+ for _ in bl:
+ for a in bl:
+ for t, k in bl[a].out:
+ if (a, t) not in back:
+ lay[t] = max(lay[t], lay[a] + 1)
+ last = max(lay.values())
+ for a in bl:
+ if bl[a].ret:
+ lay[a] = last + (0 if all(lay[x] < last or bl[x].ret for x in bl) else 1)
+ return lay, back
+
+
+# ---- a block, at the map's size: a head and insn rows --------------------------------------------------------
+X_OFF, X_LINE, X_MN, X_OPS = 72, 116, 128, 212
+
+
+def block_w(blk, base, note_w=0):
+ return max(300, X_OPS + max(len(r[3]) for r in blk.rows) * A + 24 + note_w)
+
+
+def fold_rows(rows, keep):
+ """A block longer than 16 rows: its first four and last four, the middle one `more` row."""
+ if len(rows) <= 16 or keep:
+ return rows
+ return rows[:4] + [None] + rows[-4:]
+
+
+def draw_block(g, x, y, w, blk, base, st):
+ """st: count (visits), cur (the pc's address in it), trail (ran rows), notes {address: note}, cur_line."""
+ if hasattr(blk, "folded"): # blocks the whole recording never reached: one dashed box, no rows
+ h = TAG + ROW + PAD
+ g.rect(x, y, w, h, PAGE)
+ g.frame(x, y, w, h, RULE, 2, "12 8")
+ g.t(x + 12, b(y), "+%x to +%x" % (blk.rows[0][0] - base, blk.rows[-1][0] - base), S, FAINT, MONO)
+ g.t(x + w - 12, b(y), "%d blocks never reached" % len(blk.folded) if len(blk.folded) > 1 else "never reached",
+ 18, FAINT, "sans", "end")
+ g.t(x + 12, b(y + TAG), blk.name, 18, DIM, "sans")
+ return h, {}
+ rows = fold_rows(blk.rows, st.get("cur"))
+ h = TAG + len(rows) * ROW + PAD
+ reached = st.get("count", 0) > 0
+ g.rect(x, y, w, h, PAGE)
+ g.rect(x, y, w, TAG, RAISED if reached else PAGE)
+ g.frame(x, y, w, h, GOLD if st.get("cur") else RULE, 2) # not reached yet: plain, no count
+ ink = CODE
+ C.addr(g, x + 12, y, blk.a, ink)
+ lines = sorted({r[1] for r in blk.rows if r[1]})
+ if lines:
+ g.t(x + 12 + len("%x" % blk.a) * A + 16, b(y), "line %d" % lines[0] if len(lines) == 1 else
+ "lines %d to %d" % (lines[0], lines[-1]), 18, FAINT, "sans")
+ if reached:
+ g.t(x + w - 12, b(y), "×%d" % st["count"], S, VELLUM, MONO, "end")
+ yy, last_line, at = y + TAG, None, {}
+ for r in rows:
+ if r is None:
+ C.more(g, x + X_OFF - 36, yy)
+ g.t(x + X_MN, b(yy), "%d rows" % (len(blk.rows) - 8), S, FAINT, MONO)
+ yy += ROW
+ continue
+ a, ln, mn, ops, t, callee = r
+ at[a] = yy
+ dim_ = False
+ if a == st.get("cur"):
+ g.path(f"M{x + 20},{yy + 12} l-10,-6 v12 Z", fill=C.current_row(g, x + 2, yy, w - 4, 24))
+ elif a in st.get("trail", []):
+ g.rect(x + 2, yy + 1, 4, ROW - 2, TRAIL[st["trail"].index(a)])
+ g.t(x + X_OFF, b(yy), "+%x" % (a - base), S, FAINT if not dim_ else mix(FAINT, PAGE, 0.4), MONO, "end")
+ if ln and ln != last_line:
+ on = ln == st.get("cur_line") and st.get("cur")
+ g.t(x + X_LINE, b(yy), str(ln), S, GOLD if on else FAINT, BOLD if on else MONO, "end")
+ last_line = ln
+ fade = (lambda c: mix(c, PAGE, 0.55)) if dim_ else (lambda c: c)
+ g.t(x + X_MN, b(yy), mn, S, fade(FAINT if mn in ("nop", "endbr64") else KW),
+ MONO if mn in ("nop", "endbr64") else BOLD)
+ if t and (mn.startswith("j") or mn == "call"):
+ ex = C.addr(g, x + X_OPS, yy, t, fade(CODE))
+ else:
+ ex = C.operands(g, x + X_OPS, yy, mn, ops, fade(VELLUM))
+ note = st.get("notes", {}).get(a)
+ if note:
+ nx = max(ex + 2 * A, x + X_OPS + 20 * A)
+ for s_, ink_ in note:
+ if ink_ == "chip":
+ g.rect(nx, yy + 2, 32, 20, RAISED)
+ g.t(nx + 16, b(yy), s_, S, BRIGHT, BOLD, "middle")
+ nx += 38
+ else:
+ g.t(nx, b(yy), s_, S, ink_, MONO)
+ nx += len(s_) * A
+ if mn == "call" and callee: # a call that comes back: out of the block's side and in again a row down
+ hx = x + w
+ g.path(f"M{hx},{yy + 12} h14 q6,0 6,6 v12 q0,6 -6,6 h-8", fade(DIM) if reached else RULE, 2)
+ g.path(f"M{hx},{yy + 36} l8,-4 v8 Z", fill=fade(DIM) if reached else RULE)
+ g.t(hx + 28, b(yy) + 12, callee, S, fade(VELLUM), MONO)
+ yy += ROW
+ if blk.ret: # the way out: a stub and a bar under the block
+ cx = x + w / 2
+ g.rect(cx - 1, y + h, 2, 14, DIM if reached else RULE)
+ g.rect(cx - 14, y + h + 14, 28, 3, DIM if reached else RULE)
+ return h, at
+
+
+# ---- the graph: placement and edges -----------------------------------------------------------------------
+def arrow(g, pts, *a, **k):
+ """gen.arrow, its repeated and straight-through points dropped."""
+ q = []
+ for p in pts:
+ if q and abs(p[0] - q[-1][0]) < 0.5 and abs(p[1] - q[-1][1]) < 0.5:
+ continue
+ if len(q) >= 2 and (abs(q[-2][0] - q[-1][0]) < 0.5 and abs(q[-1][0] - p[0]) < 0.5 or
+ abs(q[-2][1] - q[-1][1]) < 0.5 and abs(q[-1][1] - p[1]) < 0.5):
+ q[-1] = p
+ continue
+ q.append(p)
+ gen.arrow(g, q, *a, **k)
+
+def place(bl, lay, cols, widths, heights, x0, y0, pitch, gap):
+ """Each block at its column (a scene's layout, by the rule in the catalogue) and its layer."""
+ nl = max(lay.values()) + 1
+ lh = [max([heights[a] for a in bl if lay[a] == k] or [0]) for k in range(nl)]
+ ly = [y0]
+ for k in range(1, nl):
+ ly.append(ly[-1] + lh[k - 1] + gap)
+ pos = {a: (x0 + cols[a] * pitch, ly[lay[a]]) for a in bl}
+ return pos, lh, ly
+
+
+def edges(g, bl, lay, back, pos, widths, heights, lh, ly, gap, st, base, lane_x0, channel_x, small=False):
+ """Every edge: forward ones down from the bottom by the side their target lies on, along the gap's middle, down
+ into the target's top; one that would cross a block runs in the right channel; a back edge leaves the bottom,
+ goes out to its loop's lane on the left, climbs it and enters its header's head from the side: the one thing
+ that climbs. Ink: never taken `rule`; taken in the run `dim`; the last three taken the trail's golds."""
+ sw0 = 2
+ trail = st.get("edge_trail", [])
+ counts = st.get("edge_counts", {})
+ backs = sorted([(a, t) for a, t in back], key=lambda e: -(lay[e[0]] - lay[e[1]]))
+ lane = {e: lane_x0 + i * (10 if small else 16) for i, e in enumerate(backs)}
+ inc = {}
+ for a in bl:
+ for t, k in bl[a].out:
+ if (a, t) not in back:
+ inc.setdefault(t, []).append(a)
+ track = {}
+ for a in sorted(bl, key=lambda a: (lay[a], pos[a][0])):
+ x, y = pos[a]
+ w, h = widths[a], heights[a]
+ outs = bl[a].out
+ for t, kind in outs:
+ e = (a, t)
+ n = counts.get(e, 0)
+ ink = TRAIL[trail.index(e)] if e in trail else DIM if n else RULE
+ sw = 3 if trail and e == trail[0] else sw0
+ tx, ty = pos[t]
+ tw_ = widths[t]
+ if e in back:
+ lx = lane[e]
+ k = track.get(lay[a], 0)
+ track[lay[a]] = k + 1
+ by = ly[lay[a]] + lh[lay[a]] + (8 if small else 14) + k * 8
+ sx = x + (16 if small else 40)
+ hy = ty + (12 if not small else 12)
+ pts = [(sx, y + h), (sx, by), (lx, by), (lx, hy), (tx - 1, hy)]
+ st.setdefault("paths", {})[e] = pts
+ arrow(g, pts, ink, sw, r=4 if small else 8, hl=7 if small else 10, hw=8 if small else 10)
+ if n: # the loop's turns, on the lane under its turn into the header
+ if st.get("struck_count") == e: # the count is a value: written, it is struck
+ g.rect(lx + 1, hy + 8, 10 + len(str(n)) * 11, 20, C.SOFT)
+ g.t(lx + 5, hy + 22, "×%d" % n, 18, BRIGHT, "sansb")
+ else:
+ g.t(lx + 5, hy + 22, "×%d" % n, 18, FAINT, "sans")
+ continue
+ # the side the target lies on picks the port
+ srcs = sorted(inc.get(t, []), key=lambda s_: pos[s_][0])
+ slot = srcs.index(a)
+ tx_ = tx + tw_ / 2 + (slot - (len(srcs) - 1) / 2) * (16 if small else 48)
+ crosses = any(lay[a] < lay[o] < lay[t] and pos[o][0] - 8 < tx_ < pos[o][0] + widths[o] + 8 for o in bl)
+ side = 1 if crosses else (tx + tw_ / 2) - (x + w / 2) # the channel is on the right
+ sx = x + w / 2 if abs(side) < w / 2 - 40 and not crosses else (
+ x + w - (16 if small else 40) if side > 0 else x + (16 if small else 40))
+ gy = ly[lay[a]] + lh[lay[a]] + gap / 2 + track.get(("f", lay[a]), 0) * 6
+ track[("f", lay[a])] = track.get(("f", lay[a]), 0) + 1
+ between = [o for o in bl if lay[a] < lay[o] < lay[t] and pos[o][0] - 8 < tx_ < pos[o][0] + widths[o] + 8]
+ if between: # it would cross a block: the right channel
+ gy2 = ly[lay[t]] - gap / 2
+ pts = [(sx, y + h), (sx, gy), (channel_x, gy), (channel_x, gy2), (tx_, gy2), (tx_, ty)]
+ else:
+ pts = [(sx, y + h), (sx, gy), (tx_, gy), (tx_, ty)]
+ st.setdefault("paths", {})[e] = pts
+ arrow(g, pts, ink, sw, r=4 if small else 8, hl=7 if small else 10, hw=8 if small else 10)
+ if n and kind != "jmp" and not small and len(outs) > 1:
+ g.t(sx + 8, y + h + 20, str(n), S, FAINT, MONO)
+
+
+def graph(g, x, y, w, title, note, bl, entry, base, cols, st, pitch=None, gap=48, notes_w=0):
+ """The panel: its tag, the blocks at the map's size, the edges. Returns the blocks' row positions."""
+ lay, back = layers(bl, entry)
+ widths = {a: 520 if hasattr(bl[a], "folded") else block_w(bl[a], base, notes_w if st["blocks"].get(a, {}).get("notes")
+ else 0) for a in bl}
+ heights = {a: TAG + (ROW if hasattr(bl[a], "folded") else
+ len(fold_rows(bl[a].rows, st["blocks"].get(a, {}).get("cur"))) * ROW) + PAD for a in bl}
+ nb = len([e for e in back])
+ lane_x0 = x + 24
+ x0 = x + 24 + nb * 16 + 24
+ pitch = pitch or max(widths.values()) + 56
+ pos, lh, ly = place(bl, lay, cols, widths, heights, x0, y + TAG + 36, pitch, gap)
+ channel_x = max(pos[a][0] + widths[a] for a in bl) + 32
+ hgt = max(pos[a][1] + heights[a] for a in bl) - y + 48
+ C.tag(g, x, y, w, hgt, title, focus=True, note=note)
+ edges(g, bl, lay, back, pos, widths, heights, lh, ly, gap, st, base, lane_x0, channel_x)
+ ats = {}
+ for a in bl:
+ s_ = st["blocks"].get(a, {})
+ _, at = draw_block(g, pos[a][0], pos[a][1], widths[a], bl[a], base, s_)
+ ats.update(at)
+ return pos, ats, hgt
+
+
+def run_state(bl, path, upto, base):
+ """Visits and edge counts over the path's first `upto` blocks; the last three edges taken."""
+ p = path[:upto]
+ cnt = Counter(p)
+ ec = Counter(zip(p, p[1:]))
+ trail = list(reversed(list(zip(p, p[1:]))[-3:]))
+ return cnt, ec, trail
+
+
+# ---- the data ---------------------------------------------------------------------------------------------
+SORT = read_dis("sort-O0.dis")
+SORT_BASE = 0x401143
+SORT_BL = blocks(SORT, SORT_BASE)
+SB = sorted(SORT_BL) # B0 .. B7 by address
+NAMES = dict(zip("B0 B1 B2 B3 B4 B5 B6 B7".split(), SB))
+SORT_PATH = [NAMES[n] for n in ("B0 B6 B1 B3 B4 B5 B6 B1 B3 B4 B5 B6 B1 B3 B4 B5 B6 B1 B3 B4 B2 B3 B4 B2 B3 B4 B5 B6 B1 "
+ "B3 B4 B2 B3 B4 B5 B6 B1 B3 B4 B2 B3 B4 B2 B3 B4 B2 B3 B4 B2 B3 B4 B2 B3 B4 B5 B6 B1 "
+ "B3 B4 B2 B3 B4 B2 B3 B4 B5 B6 B7").split()]
+SORT_COLS = {NAMES["B0"]: 0, NAMES["B6"]: 0, NAMES["B1"]: 0, NAMES["B3"]: 0, NAMES["B4"]: 0, NAMES["B2"]: 0,
+ NAMES["B5"]: 1, NAMES["B7"]: 1}
+
+
+def sort_state(upto, cur, trail_rows, notes=None, cur_line=12):
+ cnt, ec, trail = run_state(SORT_BL, SORT_PATH, upto, SORT_BASE)
+ blk = {a: {"count": cnt.get(a, 0)} for a in SORT_BL}
+ ca = max(a for a in SORT_BL if a <= cur)
+ blk[ca].update(cur=cur, trail=trail_rows, notes=notes or {}, cur_line=cur_line)
+ return {"blocks": blk, "edge_counts": ec, "edge_trail": trail}
+
+
+# the 11th time through the compare: i = 6, j = 4, a[3] = 17 against a[4] = 5 (moment 370 of the stepped run)
+UPTO = [i for i, a in enumerate(SORT_PATH) if a == NAMES["B4"]][10] + 1
+NOTES_370 = {0x4011bf: [("404030 ", HEAP), ("◂ ", FAINT), ("17", VELLUM)],
+ 0x4011d6: [("404034 ", HEAP), ("◂ ", FAINT), ("5", VELLUM)],
+ 0x4011d9: [("17", VELLUM), (" : ", FAINT), ("5", VELLUM), (" ", FAINT), ("zf", DIM), (" sf", DIM), (" of", DIM)],
+ 0x4011db: [("taken", VELLUM), (" · reads zf sf of", FAINT)]}
+
+
+def frame_sort_map(name):
+ """Mock 22: on the map, the disassembly column as sort's graph, two columns wide, beside the source whole."""
+ gen.W, gen.H = 2900, 1800
+ g = Svg()
+ D.put(112)
+ src = open(HERE + "/../../anim/tools/sort.c").read().split("\n")
+ C.LX = 112
+ C.source(g, 96, 22, src, 1, 12, [13, 14], "sort.c", 22)
+ C.LX = 64
+ g.t(112, 60, "the map: sort's disassembly as its graph, two columns wide (1024 to 2816), at moment 370 of 465 in sort",
+ 22, DIM, "sans")
+ st = sort_state(UPTO, 0x4011db, [0x4011d9, 0x4011d6, 0x4011cf], NOTES_370)
+ graph(g, 1024, 96, 1792, "disassembly · sort", "its blocks · visits so far · the edges the run took",
+ SORT_BL, SB[0], SORT_BASE, SORT_COLS, st, pitch=560, notes_w=30 * A)
+ g.save(name)
+
+
+# ---- libc's open: unreached blocks folded -----------------------------------------------------------------
+OPEN = read_dis("libc-open.dis", lines=False)
+OPEN_BASE = 0x110ec0
+L = 0x7ffff7c00000
+
+
+def rebase(rows):
+ return [(a + L, ln, mn, ops, (t + L) if t else None, callee) for a, ln, mn, ops, t, callee in rows]
+
+
+OPEN_BL = blocks(rebase(OPEN), OPEN_BASE + L)
+OPEN_PATH = [a + L for a in (0x110ec0, 0x110ee9, 0x110efb, 0x110fb0, 0x110fca, 0x110fd2, 0x110fd4, 0x110fe3)]
+
+
+def fold_unreached(bl, path, groups):
+ """Blocks the run never reached, a connected run of them one box: `5 blocks not reached`."""
+ out = {a: bl[a] for a in bl if a in path}
+ for name, members in groups:
+ rows = [r for m in members for r in bl[m].rows]
+ fb = Block(name, rows)
+ fb.folded = members
+ out[members[0]] = fb
+ rep = {m: ms[0] for _, ms in groups for m in ms}
+ for a, blk in list(out.items()):
+ seen = []
+ for t, k in (blk.out if not hasattr(blk, "folded") else [o for m in blk.folded for o in bl[m].out]):
+ t2 = rep.get(t, t)
+ if t2 != a and t2 in out and (t2, k) not in seen and t2 not in [s_ for s_, _ in seen]:
+ seen.append((t2, k))
+ blk.out = seen
+ blk.ret = blk.ret if not hasattr(blk, "folded") else False
+ return out
+
+
+def frame_open_map(name):
+ """Mock 23: libc's open, 19 blocks, of which the run reached 8; the 11 it did not are folded into three boxes.
+ The pc is at the `syscall` (mock 16's moment 4)."""
+ gen.W, gen.H = 2000, 2000
+ g = Svg()
+ o = lambda x: x + L
+ groups = [("the O_CREAT path: the mode from the varargs", [o(0x110f90)]),
+ ("multi-threaded: a cancellable call", [o(0x110f1b), o(0x110f23), o(0x110f2b), o(0x110f6d)]),
+ ("an error: errno set, -1 returned", [o(0x110fe8), o(0x110f79), o(0x110f7e)]),
+ ("cancelled", [o(0x110ff6), o(0x111009)]),
+ ("the canary broken", [o(0x110fec), o(0x110ff0)])]
+ groups = [(n, [m for m in ms if m in OPEN_BL]) for n, ms in groups]
+ bl = fold_unreached(OPEN_BL, OPEN_PATH, groups)
+ cols = {a: 0 for a in bl}
+ for n, ms in groups:
+ cols[ms[0]] = 1
+ st = {"blocks": {a: {"count": 1} for a in OPEN_PATH}, "edge_counts": Counter(zip(OPEN_PATH, OPEN_PATH[1:])),
+ "edge_trail": list(reversed(list(zip(OPEN_PATH, OPEN_PATH[1:]))[1:4]))}
+ st["blocks"][o(0x110fb0)].update(cur=o(0x110fc5), trail=[o(0x110fc0), o(0x110fb9), o(0x110fb6)],
+ notes={o(0x110fc5): [("openat", BRIGHT), (" nr 257", FAINT)]})
+ st["edge_counts"] = Counter(zip(OPEN_PATH[:4], OPEN_PATH[1:4]))
+ st["edge_trail"] = list(reversed(list(zip(OPEN_PATH[:4], OPEN_PATH[1:4]))))
+ for a in OPEN_PATH[4:]:
+ st["blocks"][a]["count"] = 0 # not yet: the run is at the syscall
+ for _, ms in groups:
+ st["blocks"][ms[0]] = {"count": 0}
+ g.t(64, 60, "the map: libc's open as its graph · 19 blocks, the run reached 8 so far; the 11 it never reached are "
+ "folded into five boxes", 22, DIM, "sans")
+ graph(g, 64, 96, 1872, "disassembly · open · libc.so.6", "no source · 19 blocks · folded: 11 never reached",
+ bl, OPEN_PATH[0], OPEN_BASE + L, cols, st, pitch=880, gap=40, notes_w=18 * A)
+ g.save(name)
+
+
+# ---- reverse: a loop's turn, as a strip -------------------------------------------------------------------
+REV = read_dis("reverse-O0.dis")
+REV_BASE = 0x401188
+REV_BL = blocks(REV, REV_BASE)
+RB = sorted(REV_BL)
+R0, R1, R2, R3 = RB
+REV_PATH = [R0, R2, R1, R2, R1, R2, R1, R2, R3]
+
+
+def frame_strip(name):
+ """Mock 24: reverse's loop, four instants: the condition about to be decided; its edge taken, the mark
+ travelling it; the back edge's turn, the count going up; the way out."""
+ gen.W, gen.H = 3840, 1120
+ g = Svg()
+ cols = {R0: 0, R1: 0, R2: 0, R3: 0}
+ inst = [
+ ("1", "the condition", "cur at jne, the compare's chips framed; the second turn", 4, 0x4011ce,
+ {0x4011c9: [("1004070", HEAP), (" : ", FAINT), ("0", VELLUM), (" ", FAINT), ("zf", DIM)],
+ 0x4011ce: [("taken", VELLUM), (" · reads zf", FAINT)]}, None),
+ ("2", "the edge taken", "the edge lit gold, the mark on it, halfway", 5, None, {}, (R2, R1)),
+ ("3", "the loop's turn", "the back edge climbs, the mark on it; its count struck: the second turn", 6, None, {}, (R1, R2)),
+ ("4", "the way out", "not taken: down to the exit, landed", 9, 0x4011d0, {}, None),
+ ]
+ for k, (num, title, sub, upto, cur, notes, moving) in enumerate(inst):
+ dx = 64 + k * 940
+ g.o.append(f'<g transform="translate({dx - 64},0)">')
+ g.t(64, 40, num, 28, GOLD, "sansb")
+ g.t(92, 40, title, 28, VELLUM, "sansm")
+ g.t(64, 70, sub, 20, FAINT, "sans")
+ cnt, ec, trail = run_state(REV_BL, REV_PATH, upto, REV_BASE)
+ st = {"blocks": {a: {"count": cnt.get(a, 0)} for a in REV_BL}, "edge_counts": ec, "edge_trail": trail}
+ if cur:
+ ca = max(a for a in REV_BL if a <= cur)
+ st["blocks"][ca].update(cur=cur, notes=notes, cur_line=20 if ca == R2 else 21 if ca == R1 else 26)
+ if moving == (R1, R2):
+ st["struck_count"] = moving
+ pos, ats, hgt = graph(g, 64, 96, 900, "disassembly · reverse", "", REV_BL, R0, REV_BASE, cols, st, pitch=470,
+ gap=48, notes_w=18 * A)
+ if moving: # the mark between blocks: the gold plaque halfway along the edge it takes
+ pts = st["paths"][moving]
+ seg = [(p, q, abs(q[0] - p[0]) + abs(q[1] - p[1])) for p, q in zip(pts, pts[1:])]
+ half, run = sum(l for _, _, l in seg) / 2, 0
+ for p, q, l in seg:
+ if run + l >= half:
+ f = (half - run) / l
+ mx, my = p[0] + (q[0] - p[0]) * f, p[1] + (q[1] - p[1]) * f
+ break
+ run += l
+ g.rect(mx - 12, my - 12, 24, 24, GOLD)
+ up = q[1] < p[1]
+ g.path(f"M{mx},{my + (-6 if up else 6)} l-6,{8 if up else -8} h12 Z", fill=gen.INK)
+ g.o.append("</g>")
+ g.save(name)
+
+
+# ---- the working frame: a `blocks` lens, the graph as shapes, its view the disassembly -----------------------
+def silhouette(g, x, y, w, h, bl, entry, base, cols, st, title):
+ """The graph without its text: a block a box 24 high, as wide as its rows (8 a row, 72 at least), its offset
+ and visits; the pc's gold; edges and lanes as on the map, small."""
+ lay, back = layers(bl, entry)
+ widths = {a: max(132, 60 + len(bl[a].rows) * 10) for a in bl}
+ heights = {a: 24 for a in bl}
+ nb = len(back)
+ x0 = x + 24 + nb * 10 + 16
+ pos, lh, ly = place(bl, lay, cols, widths, heights, x0 + 60, y + TAG + 14, 300, 12)
+ C.tag(g, x, y, w, h, title, focus=True, note="its blocks · the visits · the path")
+ edges(g, bl, lay, back, pos, widths, heights, lh, ly, 12, st, base, x + 24, max(pos[a][0] + widths[a] for a in bl) + 20,
+ small=True)
+ for a in bl:
+ s_ = st["blocks"].get(a, {})
+ bx, by = pos[a]
+ cur = s_.get("cur")
+ g.rect(bx, by, widths[a], 24, RAISED if s_.get("count") else PAGE)
+ g.frame(bx, by, widths[a], 24, GOLD if cur else RULE, 2 if not cur else 3)
+ g.t(bx + 8, b(by), "+%x" % (a - base), S, VELLUM if s_.get("count") else FAINT, MONO)
+ if s_.get("count"):
+ g.t(bx + widths[a] - 8, b(by), "×%d" % s_["count"], S, DIM, MONO, "end")
+ return pos
+
+
+def frame_lens(name):
+ """Mock 25: sort at moment 370 in the working frame with the `blocks` lens: its drawing the graph as shapes,
+ its view the disassembly round the pc (moved from the program column, which is the source's alone)."""
+ gen.W, gen.H = 1920, 1080
+ g = Svg()
+ st = sort_state(UPTO, 0x4011db, [0x4011d9, 0x4011d6, 0x4011cf], NOTES_370)
+ pos = silhouette(g, 64, 48, 880, 296, SORT_BL, SB[0], SORT_BASE, {a: c for a, c in SORT_COLS.items()}, st,
+ "the blocks of sort")
+ # its view: the disassembly, seven rows round the pc, the block's rows bracketed as the drawing's gold box
+ C.LX, C.CW = 976, 880
+ rows = [(a, ln, mn, [(t, CODE)] if t and mn.startswith("j") else [(ops, VELLUM)],
+ "cur" if a == 0x4011db else {0x4011d9: "trail0", 0x4011d6: "trail1", 0x4011cf: "trail2"}.get(a),
+ ("runs", NOTES_370[a]) if a in NOTES_370 else None)
+ for a, ln, mn, ops, t, callee in SORT if 0x4011c7 <= a <= 0x4011e1] # seven rows: the view's
+ C.disasm(g, 48, rows, "sort · +84 to +a1", 12)
+ C.LX, C.CW = 64, 880
+ # the program column: the source alone
+ src = open(HERE + "/../../anim/tools/sort.c").read().split("\n")
+ C.source(g, 356, 21, src, 1, 12, [14, 13], "sort.c", 22)
+ # registers and the stack, moment 370
+ S_, H_ = STACK, HEAP
+ E = [(0x7fffffffed00, S_), (0x7fffffffedb0, S_), (0x7fffffffee10, S_)]
+ regs = [("rax", [], ("int", 5)), ("rbx", [], ("int", 0)), ("rcx", [], ("int", 0x10)), ("rdx", [], ("int", 0x11)),
+ ("rsi", [(0x404034, DATA)], ("int", 0x1f0000001a)), ("rdi", [(0x404030, DATA)], ("int", 0x1a00000005)),
+ ("rbp", [(0x7fffffffecf0, S_)] + E, ("int", 0)), ("rsp", [(0x7fffffffecd8, S_)], ("int", 0x800000000)),
+ ("r8", [(0x7ffff7e19680, DATA)], None), ("r9", [(0x7ffff7e1afa0, DATA)], None),
+ ("r10", [(0x7fffffffea60, S_)], ("int", 0)), ("r11", [(0x7ffff7ffca90, DATA)], ("int", 0x786843bb9f54c5c1)),
+ ("r12", [(0x7fffffffee38, S_), (0x7fffffffefea, S_)], ("str", "./sort")), ("r13", [], ("int", 1)),
+ ("r14", [(0x7ffff7ffd000, DATA), (0x7ffff7ffe3c0, DATA)], ("int", 0)),
+ ("r15", [(0x403e10, DATA), (0x4010e0, CODE, "__do_global_dtors_aux")], None),
+ ("rip", [(0x4011db, CODE, "sort+152")], None)]
+ flags = [("CF", 0, 0), ("PF", 1, 0), ("AF", 1, 0), ("ZF", 0, 0), ("SF", 0, 0), ("IF", 1, 0), ("DF", 0, 0), ("OF", 0, 0)]
+ C.RX = 976
+ C.registers(g, 260, regs, flags, {"rax": {0: "tick"}, "rdx": {0: "tick"}})
+ C.stack(g, 712, [(0x7fffffffecd8, ["rsp"], [], ("int", 0x800000000)), (0x7fffffffece0, [], [], ("int", 0)),
+ (0x7fffffffece8, [], [], ("int", 0x400000006)), (0x7fffffffecf0, ["rbp"], E, ("int", 0)),
+ (0x7fffffffecf8, [], [(0x4011ff, CODE, "main+14")], None),
+ (0x7fffffffed00, [], E[1:], ("int", 0))],
+ [("sort(8)", 0, 4)], rsp=0x7fffffffecd8,
+ roles={2: ("i, j", VELLUM), 3: ("saved rbp", DIM)})
+ C.clock(g, 370, 465)
+ gen.caption(g, [[("The sixth pass, its third compare: ",), ("17 : 5", "mono"), (", so ",), ("jg", "mono"),
+ (" goes back to the swap.",)],
+ [("The swap has run 5 times so far; the outer loop has turned 5.",)]])
+ g.save(name)
+
+
+if __name__ == "__main__":
+ assert len(SORT_BL) == 8 and len(REV_BL) == 4, (len(SORT_BL), len(REV_BL))
+ assert Counter(SORT_PATH)[NAMES["B4"]] == 17 and Counter(SORT_PATH)[NAMES["B2"]] == 10
+ frame_sort_map("22-graph-sort")
+ frame_open_map("23-graph-open")
+ frame_strip("24-graph-strip")
+ frame_lens("25-blocks-lens")