summaryrefslogtreecommitdiff
path: root/design/mock/graph.py
diff options
context:
space:
mode:
Diffstat (limited to 'design/mock/graph.py')
-rw-r--r--design/mock/graph.py1023
1 files changed, 403 insertions, 620 deletions
diff --git a/design/mock/graph.py b/design/mock/graph.py
index 6062fa9..083842e 100644
--- a/design/mock/graph.py
+++ b/design/mock/graph.py
@@ -1,19 +1,20 @@
#!/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.
+"""The disassembly's other form: a function as a graph of its basic blocks, with what the run has done on it by
+the moment shown, and nothing after.
- python3 -B graph.py # 22-graph-sort, 23-graph-open, 24-graph-strip, 43-graph-forms (.svg)
+ python3 -B graph.py # 22-graph-sort, 24-graph-strip, 43-graph-forms (.svg)
# (25, the `blocks` lens in the working frame, is frame.py's)
-The form is the track: the blocks in a line in the order they run, each loop closing over the line as an arch
-whose blocks sit on its floor, a forward jump that skips blocks dipping under them. Across in the lens's band,
-down on the map, where the blocks are cards that carry their rows. The layered form it replaced (`silhouette`,
-with `place` and `edges`) is kept for the comparison sheet, 43.
+Two forms. `rings`, the first: each loop a ring its blocks sit on, clockwise from its header at the ring's left,
+an inner loop a smaller ring touching its parent at its header, a loop's way out leaving along the ring's tangent;
+what is outside every loop laid in layers. `layers`, the second, for a function that is a tree of branches: the
+blocks in layers, pills and round corners. A block a pill either way (its offset, its visits so far).
Data: sort as the scene builds it (clang -O0, anim/build.zig, less the instrumentation's calls): sort-clang.dis
(objdump -dl), its path from `ztrace record --by insn --from sort` (the block leaders it hit), its stop in
sort-dbg.txt. reverse from anim/tools/list.c (cc -O0), reverse-O0.dis, its path 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.
+instruction. libc's `open` from objdump of /usr/lib/libc.so.6 (libc-open.dis), its path the one mock 16's run
+took. Every count is the path's up to the moment shown.
"""
import math
import re
@@ -129,102 +130,6 @@ def layers(bl, entry):
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):
- """As wide as its widest row as drawn (the size words gone, a width's cells in their place), 300 at least."""
- ops = [len(re.sub(r"\b\w+ ptr ", "", r[3])) + (3 if " ptr " in r[3] else 0) for r in blk.rows]
- return max(300, X_OPS + max(ops) * 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)
- if st.get("split") and r is rows[-1] and not st.get("cur"): # a conditional's two ways, counted, in words
- tk, nt = st["split"]
- g.t(max(ex + 2 * A, x + X_OPS + 10 * A), b(yy), "taken %d · not %d" % (tk, nt), S, FAINT, 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 = []
@@ -253,7 +158,7 @@ def edges(g, bl, lay, back, pos, widths, heights, lh, ly, gap, st, base, lane_x0
"""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."""
+ that climbs. Ink by the moment shown: not taken yet `rule`; taken `dim`; the last three the trail's golds."""
sw0 = 2
trail = st.get("edge_trail", [])
counts = st.get("edge_counts", {})
@@ -324,243 +229,6 @@ def run_state(bl, path, upto, base):
return cnt, ec, trail
-# ---- the data: sort as the scene builds it ------------------------------------------------------------------
-SORTC = [r for r in read_dis("sort-clang.dis") if 0x401150 <= r[0] < 0x401200]
-SORT_BASE = 0x401150
-SORT_BL = blocks(SORTC, SORT_BASE)
-SB = sorted(SORT_BL)
-# the block leaders the run hit, from sort's entry to its return: ztrace record --by insn --from sort, clang -O0
-SORT_PATH = [SORT_BASE + int(o, 16) for o in (
- "0 12 1e 24 2f 56 5d 97 99 12 1e 24 2f 56 5d 97 99 12 1e 24 2f 56 5d 97 99 12 1e 24 2f 56 5f 24 2f 56 5f 24 2f "
- "56 5d 97 99 12 1e 24 2f 56 5f 24 2f 56 5d 97 99 12 1e 24 2f 56 5f 24 2f 56 5f 24 2f 56 5f 24 2f 56 5f 24 2f 56 "
- "5f 24 2f 56 5d 97 99 12 1e 24 2f 56 5f 24 2f 56 5f 24 2f 56 5d 97 99 12 a7").split()]
-O = lambda off: SORT_BASE + off
-NEVER = {(a, t) for a in SORT_BL for t, _ in SORT_BL[a].out} - set(zip(SORT_PATH, SORT_PATH[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}
- if cur:
- 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, "never": NEVER}
-
-
-# the 11th time through the compare: i = 6, j = 4, a[3] = 17 against a[4] = 5; the stop is the jne after it
-# (sort-dbg.txt). Five swaps so far, five turns of each loop.
-UPTO = [i for i, a in enumerate(SORT_PATH) if a == O(0x56)][10] + 1
-PC = 0x4011ab
-TRAIL_ROWS = [0x4011a9, 0x4011a6, 0x4011a3]
-NOTES = {0x4011a6: [("7fffffffecd3 ", STACK), ("◂ ", FAINT), ("1", VELLUM)],
- 0x4011a9: [("1", VELLUM), (" : ", FAINT), ("1", VELLUM), (" ", FAINT), ("zf", DIM)],
- 0x4011ab: [("taken", VELLUM), (" · reads zf", FAINT)]}
-
-
-def frame_sort_map(name):
- """Mock 22: on the map, the disassembly column as sort's track, one column wide (1024 to 1904), beside the
- source whole: the cards on their spine, the loops' lanes on the left, the jumps past cards on the right."""
- gen.W, gen.H = 1980, 1860
- g = Svg()
- src = open(HERE + "/../../anim/tools/sort.c").read().split("\n")
- C.LX = 112
- C.source(g, 96, 22, src, 1, 12, [14, 13], "sort.c", 22)
- C.LX = 64
- g.t(112, 60, "the map: sort's disassembly as its track, in the second column (1024 to 1904), at the 11th compare",
- 22, DIM, "sans")
- st = sort_state(UPTO, PC, TRAIL_ROWS, NOTES)
- hgt, ats, _ = track_map(g, 1024, 96, 880, SORT_BL, SB[0], SORT_BASE, st, "disassembly · sort",
- "its blocks · visits · the edges taken · the loops' turns", notes_w=17 * A)
- print("22: the track on the map is %d high; the map's stage holds %d" % (hgt, 1688))
- g.rect(112, 1784, 1792, 2, RULE)
- g.t(112, 1808, "the map's stage ends at 1784", 18, FAINT, "sans")
- 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 five cards by
- what they are. The pc is at the `syscall` (mock 16's moment 4): the blocks after it are reached later."""
- gen.W, gen.H = 1008, 1640
- 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)
- st = {"blocks": {a: {"count": 1} for a in OPEN_PATH}}
- 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 track · 19 blocks, the run reached 8; the 11 never reached folded", 22,
- DIM, "sans")
- hgt, _, _ = track_map(g, 64, 96, 880, bl, OPEN_PATH[0], OPEN_BASE + L, st, "disassembly · open · libc.so.6",
- "no source · 19 blocks · folded: 11 never reached", notes_w=18 * A)
- print("23: %d high" % hgt)
- 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 in the lens, four instants: the condition about to be decided; the edge taken, the
- mark on it; the turn, the mark on the arch over the loop's blocks, its count struck; the way out, under."""
- gen.W, gen.H = 1920, 600
- g = Svg()
- inst = [
- ("1", "the condition", "the pc on jne in the test's block, the second time; its two ways out", 4, 0x4011ce, None),
- ("2", "the edge taken", "taken: along the line to the body, the mark on the edge, landing", 4, None,
- ((R2, R1), 0.55)),
- ("3", "the loop's turn", "back over the arch to the test, the mark coming round; the count struck as it lands", 5,
- None, ((R1, R2), 0.6)),
- ("4", "the way out", "not taken, the fourth time: under the body to the exit, landed", 9, 0x4011d0, None),
- ]
- for k, (num, title, sub, upto, cur, moving) in enumerate(inst):
- x, y = 64 + (k % 2) * 912, 40 + (k // 2) * 280
- g.t(x, y + 24, num, 28, GOLD, "sansb")
- g.t(x + 28, y + 24, title, 28, VELLUM, "sansm")
- g.t(x, y + 52, sub, 18, FAINT, "sans")
- path = REV_PATH[:upto] + ([moving[0][1]] if moving else [])
- cnt, ec, trail = run_state(REV_BL, path, len(path), REV_BASE)
- if moving: # the mark is on its edge: the target not yet entered, the edge lit
- cnt[moving[0][1]] -= 1
- 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)
- track_lens(g, x, y + 72, 880, 200, REV_BL, R0, REV_BASE, st, "the blocks of reverse", moving=moving,
- struck=moving[0] if moving and moving[0] == (R1, R2) else None)
- g.save(name)
-
-
-# ---- the layered form, as the lens drew it before the track (the comparison sheet) -------------------------
-def silhouette(g, x, y, w, h, bl, entry, base, cols, st, title, rounded=False, pitch=300):
- """The layered form without its text (the lens before the track): a block a box 24 high, as wide as its rows
- (10 a row, 132 at least), its offset and visits; the pc's gold; edges and lanes as on the map, small.
- rounded: the same layers with pills and round corners (the comparison sheet's second form)."""
- 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, pitch, 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, radius=12 if rounded else None)
- for a in bl:
- s_ = st["blocks"].get(a, {})
- bx, by = pos[a]
- cur = s_.get("cur")
- if rounded:
- pill(g, bx, by, widths[a], RAISED if s_.get("count") else PAGE, GOLD if cur else RULE, 3 if cur else 2)
- else:
- 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 + (12 if rounded else 8), b(by), "+%x" % (a - base), S, VELLUM if s_.get("count") else FAINT, MONO)
- if s_.get("count"):
- g.t(bx + widths[a] - (12 if rounded else 8), b(by), "×%d" % s_["count"], S, DIM, MONO, "end")
- return pos, max(by for _, by in pos.values()) + 24 - y
-
-
-# ---- the track ----------------------------------------------------------------------------------------------
-def loops_of(bl, entry):
- """Layers and back edges as `layers` finds them, and each loop's blocks: a back edge's natural loop (its
- header, and every block that reaches its latch without passing the header), loops of one header merged."""
- lay, back = layers(bl, entry)
- preds = {a: [] for a in bl}
- for a in bl:
- for t, _ in bl[a].out:
- preds[t].append(a)
- loops = {}
- for a, h in back:
- body, todo = {h, a}, [a]
- while todo:
- n = todo.pop()
- if n == h:
- continue
- for p in preds[n]:
- if p not in body:
- body.add(p)
- todo.append(p)
- loops.setdefault(h, set()).update(body)
- return lay, back, loops
-
-
-def track_order(bl, lay, loops):
- """The line's order: as they run (by layer, then address), each loop's blocks together from its header, so
- that a block outside a loop never sits on its floor; the blocks that return last."""
- def emit(nodes, header=None):
- out, done = [], set()
- for a in sorted(nodes, key=lambda a: (lay[a], a)):
- if a in done:
- continue
- if a in loops and a != header and loops[a] <= nodes:
- inner = emit(loops[a], a)
- out += inner
- done |= set(inner)
- else:
- out.append(a)
- done.add(a)
- return out
- return emit(set(bl))
-
-
-def spans_levels(spans):
- """Arches (or dips) by nesting: one that holds another is a level higher, so that none crosses another."""
- lv = {}
- for s in sorted(spans, key=lambda s: s[1] - s[0]):
- inner = [lv[o[2]] for o in spans if o[2] in lv and s[0] <= o[0] and o[1] <= s[1] and o[2] != s[2]]
- lv[s[2]] = 1 + max(inner, default=0)
- return lv
-
class Path:
"""An edge as drawn: straight runs and quarter circles, one family. Kept as points too, to measure it and to
@@ -619,13 +287,6 @@ def draw_path(g, p, ink, sw, dash=None, hl=8, hw=8):
gen.head_tri(g, x2, y2, ux, uy, ink, hl, hw)
-def pill(g, x, y, w, fill, stroke, sw=2, dash=None):
- """A block in the lens: a pill 24 high, its ends half circles."""
- a = (f'<rect x="{x + sw / 2:.1f}" y="{y + sw / 2:.1f}" width="{w - sw:.1f}" height="{24 - sw:.1f}" '
- f'rx="{12 - sw / 2:.1f}" fill="{fill}" stroke="{stroke}" stroke-width="{sw}"')
- g.o.append(a + (f' stroke-dasharray="{dash}"' if dash else "") + "/>")
-
-
def mark(g, p, f, ink=GOLD):
"""The current mark travelling an edge: the gold plaque, its point the way it goes."""
(mx, my), (ux, uy) = p.at(f)
@@ -634,260 +295,183 @@ def mark(g, p, f, ink=GOLD):
def edge_ink(e, st):
- """Never taken in the whole recording: rule, dashed. Not yet: rule. Taken: dim. The last three: the trail's
- golds, the newest 3 units."""
+ """By the moment shown: not taken yet, `rule`; taken, `dim`; the last three taken, the trail's golds, the newest
+ 3 units. Nothing that needs the rest of the run."""
trail = st.get("edge_trail", [])
if e in trail:
return TRAIL[trail.index(e)], 3 if trail.index(e) == 0 else 2, None
if st.get("edge_counts", {}).get(e, 0):
return DIM, 2, None
- return RULE, 2, "12 8" if e in st.get("never", ()) else None
+ return RULE, 2, None
-TRACK = dict(gap=40, arch=52, arch_step=36, dip=44, dip_step=16, stub=10, port=16)
+def pill(g, x, y, w, fill, stroke, sw=2, dash=None):
+ """A block: a pill 24 high, its ends half circles."""
+ a = (f'<rect x="{x + sw / 2:.1f}" y="{y + sw / 2:.1f}" width="{w - sw:.1f}" height="{24 - sw:.1f}" '
+ f'rx="{12 - sw / 2:.1f}" fill="{fill}" stroke="{stroke}" stroke-width="{sw}"')
+ g.o.append(a + (f' stroke-dasharray="{dash}"' if dash else "") + "/>")
-def track_lens(g, x, y, w, h, bl, entry, base, st, title, note="its blocks · the visits · the path · the loops' turns",
- tag=True, moving=None, struck=None):
- """The `blocks` lens: the function as a track across the band. A block a pill 24 high (its offset, its
- visits; as long as its rows at 10 a row, the text's length at least) on one line, in the order they run;
- an edge to the next block a straight run along the line; a loop's back edge an arch over its blocks, out of
- its latch's top and down into its header's (the loop is the closed shape the arch and its floor make, its
- turns at its centre); a forward jump past blocks a dip under them. Arches nest by level, 32 apart; dips 16.
- moving: (edge, fraction): the mark on that edge. struck: an arch whose count is being struck.
- Returns the edges' paths, and the line's y."""
- lay, back, loops = loops_of(bl, entry)
- order = track_order(bl, lay, loops)
- idx = {a: i for i, a in enumerate(order)}
+def calls_of(blk):
+ """The functions a block calls and that come back: named in its pill, after its offset."""
+ if hasattr(blk, "folded"):
+ return ""
+ names = [r[5] for r in blk.rows if r[2] == "call" and r[5] and r[5] not in NORETURN]
+ return " ".join(names[:2]) + (" …" if len(names) > 2 else "")
- def text_of(a):
- n = st["blocks"].get(a, {}).get("count", 0)
- return "+%x" % (a - base), ("×%d" % n) if n else ""
- pw = {a: max(24 + (len(text_of(a)[0]) + len(text_of(a)[1]) + 1) * A + 8, 10 * len(bl[a].rows) + 24) for a in order}
- gap = TRACK["gap"]
- total = sum(pw.values()) + gap * (len(order) - 1)
- xs, xx = {}, x + (w - total) / 2
- for a in order:
- xs[a] = xx
- xx += pw[a] + gap
- arches = [(idx[t], idx[a], (a, t)) for a, t in back]
- dips = [(idx[a], idx[t], (a, t)) for a in order for t, _ in bl[a].out
- if (a, t) not in back and idx[t] > idx[a] + 1]
- al, dl = spans_levels(arches), spans_levels(dips)
- H = lambda k: TRACK["arch"] + TRACK["arch_step"] * (k - 1)
- D = lambda k: TRACK["dip"] + TRACK["dip_step"] * (k - 1)
- top, foot = H(max(al.values(), default=1)), D(max(dl.values(), default=1))
- y0 = y + TAG + (h - TAG - top - foot) / 2 + top
- if tag:
- C.tag(g, x, y, w, h, title, focus=True, note=note)
- paths = {}
- s_, P = TRACK["stub"], TRACK["port"]
- for a in order:
- for t, kind in bl[a].out:
- e = (a, t)
- if e in back: # out of the latch's top, over, down into the header's
- k, r = H(al[e]), H(al[e]) - 12 - s_
- xa, xt = xs[a] + pw[a] - P, xs[t] + P
- p = (Path(xa, y0 - 12).to(xa, y0 - 12 - s_).arc(xa - r, y0 - k, r, False).to(xt + r, y0 - k)
- .arc(xt, y0 - 12 - s_, r, False).to(xt, y0 - 12))
- elif idx[t] == idx[a] + 1: # to the next block: along the line
- p = Path(xs[a] + pw[a], y0).to(xs[t], y0)
- else: # past blocks: under them
- k, r = D(dl[e]), D(dl[e]) - 12 - s_
- xa, xt = xs[a] + pw[a] - P, xs[t] + P
- p = (Path(xa, y0 + 12).to(xa, y0 + 12 + s_).arc(xa + r, y0 + k, r, False).to(xt - r, y0 + k)
- .arc(xt, y0 + 12 + s_, r, False).to(xt, y0 + 12))
- paths[e] = p
- for e, p in sorted(paths.items(), key=lambda kv: kv[0] in st.get("edge_trail", ())): # the trail on top
- ink, sw, dash = edge_ink(e, st)
- draw_path(g, p, ink, sw, dash)
- for a, t in back: # each loop's turns, at its centre: under its arch, over what it holds
- e = (a, t)
- n = st.get("edge_counts", {}).get(e, 0)
- inner = max([H(al[o]) for o in al if al[o] < al[e]] + [12])
- cx, cy = (xs[t] + xs[a] + pw[a]) / 2, y0 - inner - (H(al[e]) - inner) * 0.4 # clear of the mark on the arch
- s = "×%d" % n
- if struck == e:
- g.rect(cx - len(s) * A / 2 - 5, cy - 11, len(s) * A + 10, 22, C.SOFT)
- g.t(cx, cy + 7, s, S, BRIGHT, BOLD, "middle")
- elif n:
- g.t(cx, cy + 7, s, S, DIM, MONO, "middle")
- for a in order:
- s0 = st["blocks"].get(a, {})
- n, cur = s0.get("count", 0), s0.get("cur") and not moving
- pill(g, xs[a], y0 - 12, pw[a], RAISED if n else PAGE, GOLD if cur else RULE, 3 if cur else 2)
- off, cnt = text_of(a)
- g.t(xs[a] + 12, b(y0 - 12), off, S, VELLUM if n else FAINT, MONO)
- if cnt:
- g.t(xs[a] + pw[a] - 12, b(y0 - 12), cnt, S, DIM, MONO, "end")
- for i, r_ in enumerate(bl[a].rows): # a call that comes back: a hook under the pill, out and in again
- if r_[2] == "call" and r_[5] and r_[5] not in NORETURN:
- cx = xs[a] + 16 + (pw[a] - 48) * i / max(len(bl[a].rows) - 1, 1)
- g.path(f"M{cx:.1f},{y0 + 12:.1f} v6 a5,5 0 0 0 10,0 v-6", DIM if n else RULE, 2)
- g.t(cx + 16, y0 + 34, r_[5], S, VELLUM if n else FAINT, MONO)
- if moving:
- mark(g, paths[moving[0]], moving[1])
- return paths, y0, xs, pw
+def pill_text(bl, a, base, st):
+ """A block's words: its offset, the functions it calls, and its visits so far (none before its first)."""
+ if hasattr(bl[a], "folded"):
+ return "+%x …" % (bl[a].folded[0] - base), "· %d" % len(bl[a].folded)
+ n = st["blocks"].get(a, {}).get("count", 0)
+ return "+%x" % (a - base), ("×%d" % n) if n else ""
+
+
+def pill_w(bl, a, base, st):
+ off, cnt = pill_text(bl, a, base, st)
+ c = calls_of(bl[a])
+ return 24 + (len(off) + len(cnt) + 1 + (len(c) + 1 if c else 0)) * A + 8
+
+
+def draw_pill(g, x, y, bl, a, base, st, w=None):
+ """Reached so far: on `raised`, its offset primary, its visits. Not yet: on the page, its offset faint, no count.
+ A fold of blocks not reached yet: dashed, its span and how many. The pc's: framed gold, 3."""
+ w = w or pill_w(bl, a, base, st)
+ s0 = st["blocks"].get(a, {})
+ n, cur, fold = s0.get("count", 0), s0.get("cur"), hasattr(bl[a], "folded")
+ pill(g, x, y, w, RAISED if n else PAGE, GOLD if cur else RULE, 3 if cur else 2, "12 8" if fold else None)
+ off, cnt = pill_text(bl, a, base, st)
+ g.t(x + 12, b(y), off, S, VELLUM if n else FAINT, MONO)
+ c = calls_of(bl[a])
+ if c: # a call is not an edge: the callee named in the pill, faint
+ g.t(x + 12 + (len(off) + 1) * A, b(y), c, S, FAINT, MONO)
+ if cnt:
+ g.t(x + w - 12, b(y), cnt, S, DIM if n else FAINT, MONO, "end")
+ return w
-def track_map(g, x, y, w, bl, entry, base, st, title, note, notes_w=0):
- """The map's graph: the same track run down, a block a card that carries its rows (`draw_block`), the cards
- in the line's order on one spine 40 in from their left; a back edge leaves its latch's left side and climbs
- a lane on the left, 48 apart, into its header's head; a forward jump past cards leaves the source's right
- side and goes down a channel on the right into its target's head. Every bend a quarter circle of 16; cards 10
- apart. The turns in the lobe between a lane and what it holds; a conditional's two ways counted in words in
- its jump's row (`taken 5 · not 6`), where the pc's block has the jump's own annotation.
- Returns the panel's height and each card's rows' y."""
- lay, back, loops = loops_of(bl, entry)
- order = track_order(bl, lay, loops)
- idx = {a: i for i, a in enumerate(order)}
- fold = lambda a: hasattr(bl[a], "folded")
- split_w = lambda a: (X_OPS + max(len("%x" % (bl[a].rows[-1][4] or 0)) + 2, 10) * A + 17 * A
- if len(bl[a].out) == 2 and st["blocks"].get(a, {}).get("count")
- and not st["blocks"].get(a, {}).get("cur") else 0)
- widths = {a: 520 if fold(a) else max(block_w(bl[a], base, notes_w if st["blocks"].get(a, {}).get("notes") else 0),
- split_w(a)) for a in order}
- heights = {a: TAG + (ROW if fold(a) else len(fold_rows(bl[a].rows, st["blocks"].get(a, {}).get("cur"))) * ROW) + PAD
- for a in order}
- arches = [(idx[t], idx[a], (a, t)) for a, t in back]
- dips = [(idx[a], idx[t], (a, t)) for a in order for t, _ in bl[a].out
- if (a, t) not in back and idx[t] > idx[a] + 1]
- al, dl = spans_levels(arches), spans_levels(dips)
- cx0 = x + 24 + 48 * max(al.values(), default=0) + 12
- ys, yy = {}, y + TAG + 8
- for a in order:
- ys[a] = yy
- yy += heights[a] + 10
- yy += 10 # room under the last card for the way out's bar
- hook = lambda a: max([28 + len(r[5]) * A for r in bl[a].rows if r[2] == "call" and r[5]] + [0]) if not fold(a) else 0
- chan = max(cx0 + widths[a] + hook(a) for a in order) + 24
- hgt = yy - y
- C.tag(g, x, y, w, hgt, title, focus=True, note=note)
- R, spine = 16, cx0 + 40
- paths = {}
- for a in order:
- for t, kind in bl[a].out:
- e = (a, t)
- ya, yt = ys[a] + heights[a] - 14, ys[t] + 12
- if e in back:
- L = cx0 - 48 * al[e]
- p = (Path(cx0, ya).to(L + R, ya).arc(L, ya - R, R, True).to(L, yt + R).arc(L + R, yt, R, True)
- .to(cx0, yt))
- elif idx[t] == idx[a] + 1:
- p = Path(spine, ys[a] + heights[a]).to(spine, ys[t])
- else:
- Cx = chan + 32 * (dl[e] - 1)
- p = (Path(cx0 + widths[a], ya).to(Cx - R, ya).arc(Cx, ya + R, R, True).to(Cx, yt - R)
- .arc(Cx - R, yt, R, True).to(cx0 + widths[t], yt))
- paths[e] = p
- for e, p in sorted(paths.items(), key=lambda kv: kv[0] in st.get("edge_trail", ())):
- ink, sw, dash = edge_ink(e, st)
- draw_path(g, p, ink, sw, dash, hl=10, hw=10)
- counts = st.get("edge_counts", {})
- for a, t in back: # the turns, in the lobe
- e = (a, t)
- n = counts.get(e, 0)
- if n:
- L = cx0 - 48 * al[e]
- g.t(L + 24, (ys[t] + ys[a] + heights[a]) / 2 + 7, "×%d" % n, S, DIM, MONO, "middle")
- ats = {}
- for a in order:
- s0 = dict(st["blocks"].get(a, {}))
- if len(bl[a].out) == 2 and not fold(a) and s0.get("count"): # a conditional reached: its two ways counted
- (t1, k1), (t2, k2) = bl[a].out
- tk, nt = (t1, t2) if k1 == "taken" else (t2, t1)
- s0["split"] = (counts.get((a, tk), 0), counts.get((a, nt), 0))
- _, at = draw_block(g, cx0, ys[a], widths[a], bl[a], base, s0)
- ats.update(at)
- return hgt, ats, paths
+# ---- the second form: layers ------------------------------------------------------------------------------------
+def layered(g, x, y, w, h, bl, entry, base, cols, st, title, pitch=300, tag=True):
+ """`layers`: the blocks in layers by the longest path from the entry (from the code, not from the run), each
+ under its fall-through predecessor and a taken target to its right; a block a pill; edges down from the foot,
+ a back edge up its lane on the left; every corner round (12). Returns the pills' places and the height used."""
+ lay, back = layers(bl, entry)
+ widths = {a: pill_w(bl, a, base, st) for a in bl}
+ heights = {a: 24 for a in bl}
+ x0 = x + 24 + len(back) * 10 + 16
+ pos, lh, ly = place(bl, lay, cols, widths, heights, x0 + 60, y + TAG + 14, pitch, 12)
+ if tag:
+ C.tag(g, x, y, w, h, title, focus=True, note="its blocks · the visits so far · 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, radius=12)
+ for a in bl:
+ draw_pill(g, *pos[a], bl, a, base, st, widths[a])
+ return pos, max(by for _, by in pos.values()) + 24 - y
-# ---- rings: the comparison sheet's third form, each loop a circle its blocks sit on ----------------------------
-RING_AT = {0x12: ("o", 180), 0x1e: ("o", 235), 0x24: ("o", 300), 0x5d: ("o", 25), 0x97: ("o", 80), 0x99: ("o", 130),
- 0x2f: ("i", 15), 0x56: ("i", 95), 0x5f: ("i", 185)}
+def fold_not_yet(bl, reached, groups):
+ """The blocks the run has not reached by the moment shown, folded: each group (the code beyond one way the run
+ has not taken yet, as far as it leads, cut so that no fold leads back into another) one dashed pill in the
+ place of its first block; an edge into or out of a member is the fold's."""
+ out = {a: bl[a] for a in bl if a in reached or not any(a in ms for ms in groups)}
+ rep = {}
+ for ms in groups:
+ fb = Block("+%x" % ms[0], [r for m in ms for r in bl[m].rows])
+ fb.folded = ms
+ out[ms[0]] = fb
+ rep.update({m: ms[0] 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 not in [s_ for s_, _ in seen]:
+ seen.append((t2, k))
+ blk.out = seen
+ if hasattr(blk, "folded"):
+ blk.ret = False
+ return out
-def rings(g, x, y, w, h, st, title):
- """sort as rings: the outer loop a circle of 170, its blocks round it clockwise; the inner loop a circle of 92
- inside it, touching it at its header; the way in and the way out as short tracks at the left; a loop's exit a
- chord between the rings. Every edge an arc of its ring or a straight chord."""
- C.tag(g, x, y, w, h, title, focus=True, note="its blocks · the visits · the path · the loops' turns")
- R, r = 170, 92
- ox, oy = x + w / 2 + 120, y + TAG + 24 + R
- t0 = math.radians(300)
- ix, iy = ox + (R - r) * math.cos(t0), oy + (R - r) * math.sin(t0)
- ring = {"o": (ox, oy, R), "i": (ix, iy, r)}
+
+# ---- the first form: rings ----------------------------------------------------------------------------------
+def rings(g, x, y, w, h, bl, base, st, spec, title, moving=None, struck=None, tag=True):
+ """`rings`: each loop a circle its blocks sit on, upright, clockwise from its header at the ring's left (9
+ o'clock), where the way in arrives; an inner loop a smaller ring outside its parent, touching it at its header,
+ which is the parent's block at 3 o'clock. An edge from a block to the next on its ring, and a loop's back edge,
+ are arcs of the ring; an edge inside a loop that passes blocks of it is an arc 30 inside the ring; a way out
+ leaves along the ring's tangent, out of the pill's foot, and every bend after is a quarter circle of 16.
+ Outside every loop the blocks lie as `layers` lays them. The loop's turns so far at its centre.
+ spec: rings {name: (dx, dy, r)} from the origin; at {offset: (ring, degrees)}; free {offset: (dx, dy)};
+ the origin (dx, dy) from the panel's corner; edges {(from, to): kind}, kind "line", ("arc", ring),
+ ("skip", ring) or a function of the places giving a Path; hook {offset: (dx, side)}."""
+ if tag:
+ C.tag(g, x, y, w, h, title, focus=True, note="its blocks · the visits so far · the path · the loops' turns")
+ ox, oy = x + spec["origin"][0], y + spec["origin"][1]
+ ring = {k: (ox + dx, oy + dy, r) for k, (dx, dy, r) in spec["rings"].items()}
pos = {}
- for off, (k, deg) in RING_AT.items():
- cx, cy, rr = ring[k]
- pos[O(off)] = (cx + rr * math.cos(math.radians(deg)), cy + rr * math.sin(math.radians(deg)))
- pos[O(0x0)] = (ox - R - 170, oy)
- pos[O(0xa7)] = (ox - R - 170, oy + 96)
- texts = {a: ("+%x" % (a - SORT_BASE), "×%d" % st["blocks"][a]["count"] if st["blocks"][a]["count"] else "")
- for a in SORT_BL}
- pw = {a: 24 + (len(texts[a][0]) + len(texts[a][1]) + 1) * A + 8 for a in SORT_BL}
+ for off, (k, deg) in spec["at"].items():
+ cx, cy, r = ring[k]
+ pos[base + off] = (cx + r * math.cos(math.radians(deg)), cy + r * math.sin(math.radians(deg)))
+ for off, (dx, dy) in spec["free"].items():
+ pos[base + off] = (ox + dx, oy + dy)
+ pw = {a: pill_w(bl, a, base, st) for a in pos}
inside = lambda a, px, py: abs(px - pos[a][0]) < pw[a] / 2 + 4 and abs(py - pos[a][1]) < 16
- def on_ring(a, t, k):
- """The arc of ring k from a's pill to t's, clockwise, cut where each pill ends."""
- cx, cy, rr = ring[k]
+ def arc(a, t, k, inset=0):
+ cx, cy, r = ring[k]
+ r -= inset
a0 = math.atan2(pos[a][1] - cy, pos[a][0] - cx)
a1 = math.atan2(pos[t][1] - cy, pos[t][0] - cx)
while a1 <= a0:
a1 += 2 * math.pi
- pt = lambda th: (cx + rr * math.cos(th), cy + rr * math.sin(th))
+ pt = lambda th: (cx + r * math.cos(th), cy + r * math.sin(th))
s, e = a0, a1
while inside(a, *pt(s)):
- s += 0.005
+ s += 0.004
while inside(t, *pt(e)):
- e -= 0.005
+ e -= 0.004
p = Path(*pt(s))
- p.arc(*pt(e), rr, True)
+ steps = max(1, int((e - s) / (math.pi / 2)) + 1) # an arc a quarter or less at a time
+ for k_ in range(1, steps + 1):
+ p.arc(*pt(s + (e - s) * k_ / steps), r, True)
return p
paths = {}
- for a in SORT_BL:
- for t, kind in SORT_BL[a].out:
- ka, kt = RING_AT.get(a - SORT_BASE, (None,))[0], RING_AT.get(t - SORT_BASE, (None,))[0]
- if (a, t) == (O(0x0), O(0x12)):
- p = Path(pos[a][0] + pw[a] / 2, oy).to(pos[t][0] - pw[t] / 2, oy)
- elif (a, t) == (O(0x12), O(0xa7)):
- sx = pos[a][0] - 20
- p = (Path(sx, oy + 12).to(sx, oy + 40).arc(sx - 56, oy + 96, 56, True)
- .to(pos[t][0] + pw[t] / 2, oy + 96))
- elif ka and kt and ka == kt or (a - SORT_BASE, t - SORT_BASE) in ((0x24, 0x2f), (0x5f, 0x24)):
- p = on_ring(a, t, "i" if (a - SORT_BASE, t - SORT_BASE) in ((0x24, 0x2f), (0x5f, 0x24)) else ka)
- else: # between the rings, or across one: a chord
- (ax, ay), (tx, ty) = pos[a], pos[t]
- d = math.hypot(tx - ax, ty - ay)
- ux, uy = (tx - ax) / d, (ty - ay) / d
- s, e = 0, d
- while inside(a, ax + ux * s, ay + uy * s):
- s += 1
- while inside(t, ax + ux * e, ay + uy * e):
- e -= 1
- p = Path(ax + ux * s, ay + uy * s).to(ax + ux * e, ay + uy * e)
- paths[(a, t)] = p
+ for (fo, to), kind in spec["edges"].items():
+ a, t = base + fo, base + to
+ if callable(kind):
+ p = kind(pos, pw, base)
+ elif kind == "line":
+ p = Path(pos[a][0] + pw[a] / 2, pos[a][1]).to(pos[t][0] - pw[t] / 2, pos[t][1])
+ elif kind[0] == "arc":
+ p = arc(a, t, kind[1])
+ else:
+ p = arc(a, t, kind[1], 30)
+ paths[(a, t)] = p
for e, p in sorted(paths.items(), key=lambda kv: kv[0] in st.get("edge_trail", ())):
ink, sw, dash = edge_ink(e, st)
- if len(p.pts) > 2: # an arc: its head on the tangent at its end
- draw_arc_head(g, p, ink, sw, dash)
- else:
- draw_path(g, p, ink, sw, dash)
- for (cx, cy, rr), e in ((ring["o"], (O(0x99), O(0x12))), (ring["i"], (O(0x5f), O(0x24)))):
- n = st["edge_counts"].get(e, 0)
- tx, ty = (cx, cy) if rr < R else (cx - 80, cy + 60)
- g.t(tx, ty + 7, "×%d" % n, S, DIM, MONO, "middle")
- for a in SORT_BL:
- s0 = st["blocks"][a]
- n, cur = s0.get("count", 0), s0.get("cur")
- px, py = pos[a][0] - pw[a] / 2, pos[a][1] - 12
- pill(g, px, py, pw[a], RAISED if n else PAGE, GOLD if cur else RULE, 3 if cur else 2)
- g.t(px + 12, b(py), texts[a][0], S, VELLUM if n else FAINT, MONO)
- if texts[a][1]:
- g.t(px + pw[a] - 12, b(py), texts[a][1], S, DIM, MONO, "end")
- sx, sy = pos[O(0x5f)][0] + 26, pos[O(0x5f)][1] - 12
- g.path(f"M{sx:.1f},{sy:.1f} v-6 a5,5 0 0 1 10,0 v6", DIM, 2)
- g.t(sx + 16, sy - 6, "swap", S, VELLUM, MONO)
+ (draw_arc_head if len(p.pts) > 2 and abs(p.pts[-1][0] - p.pts[-2][0]) > 0.5 and
+ abs(p.pts[-1][1] - p.pts[-2][1]) > 0.5 else draw_path)(g, p, ink, sw, dash)
+ for k, e in spec["turns"].items(): # each loop's turns so far, at its centre, under the line its pills are on
+ cx, cy, _ = ring[k]
+ cy += spec.get("turns_dy", 30)
+ e = (base + e[0], base + e[1])
+ n = st.get("edge_counts", {}).get(e, 0)
+ if not n:
+ continue
+ s, word = str(n), " turn" if n == 1 else " turns"
+ x0 = cx - (len(s) * A + gen.tw(word, 18, "sans")) / 2
+ if struck == e:
+ g.rect(x0 - 5, cy - 11, len(s) * A + 10, 22, C.SOFT)
+ g.t(x0, cy + 7, s, S, BRIGHT if struck == e else VELLUM, BOLD if struck == e else MONO)
+ g.t(x0 + len(s) * A, cy + 6, word, 18, DIM, "sans")
+ for a in pos:
+ s0 = dict(st["blocks"].get(a, {}))
+ if moving:
+ s0.pop("cur", None)
+ draw_pill(g, pos[a][0] - pw[a] / 2, pos[a][1] - 12, bl, a, base, {"blocks": {a: s0}}, pw[a])
+ if moving:
+ mark(g, paths[moving[0]], moving[1])
+ return paths, pos
def draw_arc_head(g, p, ink, sw, dash):
@@ -904,72 +488,271 @@ def draw_arc_head(g, p, ink, sw, dash):
gen.head_tri(g, x2, y2, (x2 - x1) / l_, (y2 - y1) / l_, ink, 8, 8)
-def frame_forms(name):
- """Mock 43: sort's graph four ways, at the same moment and at the lens's scale: the present form, its layers
- rounded, rings, and the track (recommended), each in the box it is given and at the size it needs."""
- gen.W, gen.H = 1920, 1600
+# ---- the data: sort as the scene builds it ------------------------------------------------------------------
+SORTC = [r for r in read_dis("sort-clang.dis") if 0x401150 <= r[0] < 0x401200]
+SORT_BASE = 0x401150
+SORT_BL = blocks(SORTC, SORT_BASE)
+SB = sorted(SORT_BL)
+# the block leaders the run hit, from sort's entry to its return: ztrace record --by insn --from sort, clang -O0
+SORT_PATH = [SORT_BASE + int(o, 16) for o in (
+ "0 12 1e 24 2f 56 5d 97 99 12 1e 24 2f 56 5d 97 99 12 1e 24 2f 56 5d 97 99 12 1e 24 2f 56 5f 24 2f 56 5f 24 2f "
+ "56 5d 97 99 12 1e 24 2f 56 5f 24 2f 56 5d 97 99 12 1e 24 2f 56 5f 24 2f 56 5f 24 2f 56 5f 24 2f 56 5f 24 2f 56 "
+ "5f 24 2f 56 5d 97 99 12 1e 24 2f 56 5f 24 2f 56 5f 24 2f 56 5d 97 99 12 a7").split()]
+O = lambda off: SORT_BASE + off
+
+
+def sort_state(upto, cur, trail_rows, notes=None, cur_line=12):
+ """The run's facts by the moment shown: the path's first `upto` blocks, and nothing after."""
+ cnt, ec, trail = run_state(SORT_BL, SORT_PATH, upto, SORT_BASE)
+ blk = {a: {"count": cnt.get(a, 0)} for a in SORT_BL}
+ if cur:
+ 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; the stop is the jne after it
+# (sort-dbg.txt). Five swaps so far, five turns of each loop; the function's way out not taken yet.
+UPTO = [i for i, a in enumerate(SORT_PATH) if a == O(0x56)][10] + 1
+PC = 0x4011ab
+TRAIL_ROWS = [0x4011a9, 0x4011a6, 0x4011a3]
+NOTES = {0x4011a6: [("7fffffffecd3 ", STACK), ("◂ ", FAINT), ("1", VELLUM)],
+ 0x4011a9: [("1", VELLUM), (" : ", FAINT), ("1", VELLUM), (" ", FAINT), ("zf", DIM)],
+ 0x4011ab: [("taken", VELLUM), (" · reads zf", FAINT)]}
+
+
+def down_round(sx, sy, ty, tx, ey, r=16):
+ """A way out: straight down from (sx, sy) to ty, round a quarter, across to tx, round a quarter, and straight
+ to (tx, ey), up or down."""
+ left = tx < sx
+ p = Path(sx, sy).to(sx, ty - r)
+ p.arc(sx + (-r if left else r), ty, r, left)
+ up = ey < ty
+ p.to(tx + (r if left else -r), ty)
+ p.arc(tx, ty + (-r if up else r), r, left if up else not left)
+ return p.to(tx, ey)
+
+
+SORT_RINGS = {
+ "origin": (434, TAG + 14 + 144),
+ "rings": {"o": (0, 0, 140), "i": (224, 0, 84)},
+ "at": {0x12: ("o", 180), 0x1e: ("o", 225), 0x24: ("o", 0), 0x5d: ("o", 60), 0x97: ("o", 110), 0x99: ("o", 145),
+ 0x2f: ("i", 270), 0x56: ("i", 0), 0x5f: ("i", 75)},
+ "free": {0x0: (-320, 0), 0xa7: (-180, 124)},
+ "edges": {(0x0, 0x12): "line", (0x12, 0x1e): ("arc", "o"), (0x1e, 0x24): ("arc", "o"), (0x24, 0x2f): ("arc", "i"),
+ (0x2f, 0x56): ("arc", "i"), (0x56, 0x5f): ("arc", "i"), (0x5f, 0x24): ("arc", "i"),
+ (0x24, 0x56): ("skip", "i"), (0x5d, 0x97): ("arc", "o"), (0x97, 0x99): ("arc", "o"),
+ (0x99, 0x12): ("arc", "o"),
+ # the inner loop's way out: down out of +56's foot, along its ring's tangent, under +5f, into +5d's end
+ (0x56, 0x5d): lambda pos, pw, base: (Path(pos[base + 0x56][0] + 30, pos[base + 0x56][1] + 12)
+ .to(pos[base + 0x56][0] + 30, pos[base + 0x5d][1] - 16)
+ .arc(pos[base + 0x56][0] + 14, pos[base + 0x5d][1], 16, True)
+ .to(pos[base + 0x5d][0] + pw[base + 0x5d] / 2, pos[base + 0x5d][1])),
+ # the function's way out: down out of +12's foot, outside the ring, into +a7
+ (0x12, 0xa7): lambda pos, pw, base: Path(pos[base + 0x12][0] - 40, pos[base + 0x12][1] + 12)
+ .to(pos[base + 0xa7][0], pos[base + 0xa7][1] - 12)},
+ "turns": {"o": (0x99, 0x12), "i": (0x5f, 0x24)},
+}
+
+
+# ---- libc's open, at its syscall: a tree of branches, what is not reached yet 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)] # by the syscall (mock 16's moment 4)
+
+
+# ---- reverse: a loop's turn ------------------------------------------------------------------------------------
+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]
+REV_RINGS = {
+ "origin": (441, TAG + 14 + 82),
+ "rings": {"o": (0, 0, 70)},
+ "at": {R2 - REV_BASE: ("o", 180), R1 - REV_BASE: ("o", 0)},
+ "free": {R0 - REV_BASE: (-230, 0), R3 - REV_BASE: (-100, 100)},
+ "edges": {(R0 - REV_BASE, R2 - REV_BASE): "line", (R2 - REV_BASE, R1 - REV_BASE): ("arc", "o"),
+ (R1 - REV_BASE, R2 - REV_BASE): ("arc", "o"),
+ (R2 - REV_BASE, R3 - REV_BASE): lambda pos, pw, base: Path(pos[R2][0] - 30, pos[R2][1] + 12)
+ .to(pos[R3][0], pos[R3][1] - 12)},
+ "turns": {"o": (R1 - REV_BASE, R2 - REV_BASE)},
+}
+
+
+# ---- the disassembly beside the graph, linear, its blocks ruled ---------------------------------------------------
+TEXT = read_dis("sort-clang.dis") # the program's text: swap, sort, main
+FUNC = lambda a: "swap" if a < 0x401150 else "sort" if a < 0x401200 else "main"
+
+
+def sort_disasm(g, y, n, line=12):
+ """n rows round the pc; each block's first row under a rule, its visits so far ranged right in the annotation's
+ room; the trail's three rows and the pc's with what they did; another function's rows `outside`."""
+ i = [r[0] for r in TEXT].index(PC)
+ lo = max(0, min(i - n // 2, len(TEXT) - n))
+ st = sort_state(UPTO, PC, TRAIL_ROWS)
+ notes = dict(NOTES)
+ notes[0x4011a3] = [("7fffffffecd3 ", STACK), ("◂ ", FAINT), ("1", VELLUM)]
+ rows, last = [], None
+ for a, ln, mn, ops, t, callee in TEXT[lo:lo + n]:
+ f = FUNC(a)
+ state = "cur" if a == PC else {0x4011a9: "trail0", 0x4011a6: "trail1", 0x4011a3: "trail2"}.get(a)
+ note = ("runs", notes[a]) if a in notes else ("text", callee, VELLUM) if mn == "call" else None
+ if f != "sort":
+ state = "other_first" if f != last else "other"
+ note = ("text", f, DIM) if f != last else note
+ rows.append((a, ln if f == "sort" else None, mn,
+ [(t, CODE)] if t and (mn.startswith("j") or mn == "call") else [(ops, VELLUM)], state, note))
+ last = f
+ at = C.disasm(g, y, rows, "sort", line)
+ for a in at:
+ if a in SORT_BL: # a block's first row: the rule over it, its pill's count in digits
+ yy = at[a]
+ g.rect(C.LX + 2, yy, C.CW - 4, 2, RULE)
+ n_ = st["blocks"][a]["count"]
+ if n_:
+ g.t(C.LX + C.CW - 12, b(yy), "×%d" % n_, S, FAINT, MONO, "end")
+ line12 = [at[r[0]] for r in rows if r[1] == 12 and r[0] < 0x4011af]
+ return at, (min(line12), max(line12) + ROW), lo
+
+
+# ---- the mocks ------------------------------------------------------------------------------------------------
+def frame_sort_map(name):
+ """Mock 22: the map's first two columns at the 11th compare: the drawing (rings, at its size in the frame) over
+ the source whole, and the disassembly column linear, 69 rows round the pc, each block ruled with its visits so
+ far; the thread across the gutter; the working frame's windows outlined."""
+ gen.W, gen.H = 2000, 1860
g = Svg()
st = sort_state(UPTO, PC, TRAIL_ROWS, NOTES)
- g.t(64, 56, "sort's graph, four ways", 36, BRIGHT, "sansm")
- g.t(64, 90, "The same moment in each (the 11th compare: 17 > 5, jne about to take the swap); the lens's scale, "
- "mono 20. Veiled: what falls outside the box the frame gives the lens.", 20, DIM, "sans")
+ g.t(112, 60, "the map: sort's rings over the source, the disassembly linear beside them, at the 11th compare", 22,
+ DIM, "sans")
+ rings(g, 112, 96, 880, 344, SORT_BL, SORT_BASE, st, SORT_RINGS, "the blocks of sort")
+ src = open(HERE + "/../../anim/tools/sort.c").read().split("\n")
+ C.LX = 112
+ ys = C.source(g, 452, 22, src, 1, 12, [14, 13], "sort.c", 22)
+ C.LX = 1024
+ at, run, lo = sort_disasm(g, 96, 69)
+ C.LX = 64
+ D.thread_across(g, ys, [run])
+ g.frame(112 - 4, 96 - 4, 888, 352, DIM, 2) # the frame's windows (25): the drawing whole
+ for bx, by, bw, bh in ((112, 452 + TAG + PAD + 8 * ROW, 880, 6 * ROW), (1024, at[0x4011ab] - 5 * ROW, 880, 11 * ROW)):
+ g.frame(bx - 1, by - 1, bw + 2, bh + 2, DIM, 2) # on the rows' edges, never through a line's letters
+ g.rect(112, 1798, 1792, 2, RULE)
+ g.t(112, 1824, "the map's stage ends at 1784; the other columns (memory, the registers whole, the stack) as in 19",
+ 18, FAINT, "sans")
+ g.save(name)
- def veil(x, y, w, h):
- g.o.append(f'<rect x="{x}" y="{y}" width="{w}" height="{h}" fill="{PAGE}" opacity="0.6"/>')
+
+def frame_strip(name):
+ """Mock 24: reverse's loop as a ring, four instants: the condition; the edge taken, the mark on the ring's top;
+ the turn, the mark coming round under it, the count at the centre struck; the way out, down the tangent."""
+ gen.W, gen.H = 1920, 712
+ g = Svg()
+ inst = [
+ ("1", "the condition", "the pc on jne in the test's block, the second time; its two ways out", 4, 0x4011ce, None),
+ ("2", "the edge taken", "taken: round the top of the ring to the body, the mark on it", 4, None,
+ ((R2, R1), 0.5)),
+ ("3", "the loop's turn", "back round the foot of the ring to the test; the count at its centre struck as it lands",
+ 5, None, ((R1, R2), 0.5)),
+ ("4", "the way out", "not taken, the fourth time: down the tangent, out of the ring, landed", 9, 0x4011d0, None),
+ ]
+ for k, (num, title, sub, upto, cur, moving) in enumerate(inst):
+ x, y = 64 + (k % 2) * 912, 40 + (k // 2) * 320
+ g.t(x, y + 24, num, 28, GOLD, "sansb")
+ g.t(x + 28, y + 24, title, 28, VELLUM, "sansm")
+ g.t(x, y + 52, sub, 18, FAINT, "sans")
+ path = REV_PATH[:upto] + ([moving[0][1]] if moving else [])
+ cnt, ec, trail = run_state(REV_BL, path, len(path), REV_BASE)
+ if moving: # the mark is on its edge: the target not yet entered, the edge lit
+ cnt[moving[0][1]] -= 1
+ 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)
+ rings(g, x, y + 72, 880, 248, REV_BL, REV_BASE, st, REV_RINGS, "the blocks of reverse", moving=moving,
+ struck=moving[0] if moving and moving[0] == (R1, R2) else None)
+ g.save(name)
+
+
+def frame_forms(name):
+ """Mock 43: the graph's two forms at the lens's scale, every count as of the moment shown: rings (the first), on
+ sort in the pane the frame gives it; layers (the second), on sort, and on libc's open at its syscall, a tree of
+ branches, what the run has not reached yet folded."""
+ gen.W, gen.H = 1920, 1260
+ g = Svg()
+ st = sort_state(UPTO, PC, TRAIL_ROWS, NOTES)
+ g.t(64, 56, "the graph's two forms", 36, BRIGHT, "sansm")
+ g.t(64, 90, "At the lens's scale, mono 20; each in the pane the `blocks` split gives it, 880 by 344. Every number is "
+ "the run's by the moment shown; veiled: what a pane must pan to.", 20, DIM, "sans")
def label(x, y, key, title, sub):
- g.t(x, y, key, 28, GOLD if key == "4" else BRIGHT, "sansb")
+ g.t(x, y, key, 28, GOLD if key == "1" else BRIGHT, "sansb")
g.t(x + 30, y, title, 28, VELLUM, "sansm")
g.t(x, y + 28, sub, 18, FAINT, "sans")
+
+ def veil(x, y, w, h):
+ g.o.append(f'<rect x="{x}" y="{y}" width="{w}" height="{h}" fill="{PAGE}" opacity="0.6"/>')
+ label(64, 152, "1", "rings: sort at the 11th compare", "each loop a ring, the inner touching the outer at its "
+ "header; ways out down the tangent; whole in 880 by 344")
+ rings(g, 64, 212, 880, 344, SORT_BL, SORT_BASE, st, SORT_RINGS, "the blocks of sort")
cols = {a: 0 for a in SORT_BL}
cols[O(0xa7)] = 1
cols[O(0x5f)] = 1
- for k, (key, title, sub, rounded) in enumerate((
- ("1", "present: layers, boxes, square lanes", "ten layers, 400 high: past the lens's 296 (veiled), so it "
- "pans; a third of its width", False),
- ("2", "the same layers, rounded", "pills and round corners: smoother, and just as tall", True))):
- x = 64 + k * 912
- label(x, 152, key, title, sub)
- _, hh = silhouette(Svg(), x, 212, 880, 999, SORT_BL, SB[0], SORT_BASE, cols, st, "", rounded, pitch=330)
- silhouette(g, x, 212, 880, hh + 16, SORT_BL, SB[0], SORT_BASE, cols, st, "the blocks of sort", rounded, pitch=330)
- veil(x - 2, 212 + 296, 884, hh + 16 - 296 + 2)
- label(64, 704, "3", "rings", "each loop a circle its blocks sit on, the inner inside the outer: 420 high, "
- "past the band's 200 (veiled)")
- rings(g, 64, 764, 880, 420, st, "the blocks of sort")
- veil(62, 764 + 200, 884, 222)
+ label(976, 152, "2", "layers: the same moment", "the loops as lanes; 400 high, so it pans in 344 (veiled): "
+ "for loops, rings")
+ _, hh = layered(Svg(), 976, 212, 880, 999, SORT_BL, SB[0], SORT_BASE, cols, st, "", pitch=330)
+ layered(g, 976, 212, 880, hh + 16, SORT_BL, SB[0], SORT_BASE, cols, st, "the blocks of sort", pitch=330)
+ veil(974, 212 + 344, 884, hh + 16 - 344 + 2)
+ # libc's open at its syscall: the branches it has taken, and a fold for each run of what it has not reached yet
+ o = lambda off: OPEN_BASE + L + off
+ bl = fold_not_yet(OPEN_BL, set(OPEN_PATH), [[o(x) for x in (0x5b, 0x63, 0x6b, 0xad, 0xb9, 0x136, 0x149)],
+ [o(x) for x in (0xbe, 0x10a, 0x112, 0x114, 0x123, 0x128, 0x12c, 0x130)]])
+ ost = {"blocks": {a: {"count": 1 if a in OPEN_PATH else 0} for a in bl},
+ "edge_counts": Counter(zip(OPEN_PATH, OPEN_PATH[1:])),
+ "edge_trail": list(reversed(list(zip(OPEN_PATH, OPEN_PATH[1:]))))}
+ ost["blocks"][OPEN_PATH[-1]]["cur"] = True
+ ocols = {a: (0 if a in OPEN_PATH else 1) for a in bl}
+ label(64, 670, "2", "layers: libc's open at its syscall", "a tree of branches and no loop (rings has none to "
+ "draw, and is this); what is not reached yet folded, dashed")
+ layered(g, 64, 730, 880, 344, bl, OPEN_PATH[0], OPEN_BASE + L, ocols, ost, "the blocks of open · libc.so.6",
+ pitch=380)
nx = 976
for i, (s, ink) in enumerate((
- ("What each costs", VELLUM),
- ("1 The tools' picture. Tall by nature: a layer a block,", DIM),
- (" so it pans in a short pane, and leaves the width.", DIM),
- ("2 Rounding the corners does not change the shape.", DIM),
- ("3 The most circular, and a loop is a ring; but rings", DIM),
- (" want a square pane, a loop's way out is a chord", DIM),
- (" across them, and pills on its sides sit across it.", DIM),
- ("4 The track. A line of blocks as they run, each loop", VELLUM),
- (" an arch over its own blocks: a closed shape, its", VELLUM),
- (" turns at its centre; a jump past blocks a dip", VELLUM),
- (" under them. Wide and short: 11 blocks in 1622", VELLUM),
- (" by 150, whole. Its order is the disassembly's,", VELLUM),
- (" which is under the source; run down, it is the", VELLUM),
- (" map's column with its rows.", VELLUM))):
- g.t(nx, 730 + i * 30, s, 22 if i == 0 else 20, ink, "sansm" if i == 0 else "sans")
- label(64, 1220, "4", "the track: recommended", "the band across the frame, 1792 by 200: the whole graph, no pan")
- paths, y0, xs, pw = track_lens(g, 64, 1280, 1792, 200, SORT_BL, SB[0], SORT_BASE, st, "the blocks of sort")
- print("43: the track is %d wide" % (max(xs[a] + pw[a] for a in xs) - min(xs.values())))
- g.t(64, 1530, "Ink in 3 and 4: never taken in the whole run, dashed rule (j > 0 failing); not yet, rule (the "
- "way out); taken, dim; the last three, the trail's golds. 1 and 2 keep the layers' ink: never taken, rule.",
- 18, DIM, "sans")
+ ("Which, and why", VELLUM),
+ ("1 Rings, the first form. A loop is a ring and the mark going", VELLUM),
+ (" round it is the picture of iteration; its turns at its", VELLUM),
+ (" centre. Nested loops: rings touching at the header.", VELLUM),
+ ("2 Layers, the second, for a function of branches: the path", DIM),
+ (" reads down, and a fork is two columns. Rings with no", DIM),
+ (" loop is this. For loops it is tall and pans.", DIM),
+ (" The track is withdrawn: a ring says a loop, a layer a", DIM),
+ (" branch; a line of blocks said neither, and its arches", DIM),
+ (" were rings flattened to fit a band.", DIM),
+ ("Nothing from after the moment: counts so far; an edge or", VELLUM),
+ ("a block not reached yet is quiet (rule, page, no count);", VELLUM),
+ ("open's folds are what it has not reached yet, and open", VELLUM),
+ ("as the run gets there.", VELLUM))):
+ g.t(nx, 690 + i * 30, s, 22 if i == 0 else 20, ink, "sansm" if i == 0 else "sans")
+ g.t(64, 1120, "Ink: not reached so far, rule; taken so far, dim; the last three, the trail's golds, the newest 3. "
+ "A fold, dashed. No count before a block's first visit.", 18, DIM, "sans")
g.save(name)
if __name__ == "__main__":
assert len(SORT_BL) == 11 and len(REV_BL) == 4, (len(SORT_BL), len(REV_BL))
assert Counter(SORT_PATH)[O(0x56)] == 17 and Counter(SORT_PATH)[O(0x5f)] == 10
- lay_, back_, loops_ = loops_of(SORT_BL, SB[0])
- assert [a - SORT_BASE for a in track_order(SORT_BL, lay_, loops_)] == \
- [0x0, 0x12, 0x1e, 0x24, 0x2f, 0x56, 0x5f, 0x5d, 0x97, 0x99, 0xa7]
+ st_ = sort_state(UPTO, PC, TRAIL_ROWS) # nothing from after the moment: the way out not taken yet
+ assert st_["blocks"][O(0xa7)]["count"] == 0 and st_["edge_counts"][(O(0x12), O(0xa7))] == 0
+ assert st_["blocks"][O(0x5f)]["count"] == 5 and st_["edge_counts"][(O(0x99), O(0x12))] == 5
frame_sort_map("22-graph-sort")
- frame_open_map("23-graph-open")
frame_strip("24-graph-strip")
frame_forms("43-graph-forms")