#!/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, 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.
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.
"""
import math
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):
"""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 = []
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, radius=None):
"""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=radius or (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=radius or (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 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 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
put the travelling mark on it."""
def __init__(self, x, y):
self.d, self.pts = f"M{x:.1f},{y:.1f}", [(x, y)]
def to(self, x, y):
self.d += f" L{x:.1f},{y:.1f}"
self.pts.append((x, y))
return self
def arc(self, x, y, r, cw):
"""A circular arc of radius r to (x, y), clockwise on the screen when cw."""
x0, y0 = self.pts[-1]
self.d += f" A{r:.1f},{r:.1f} 0 0 {1 if cw else 0} {x:.1f},{y:.1f}"
cl = math.hypot(x - x0, y - y0)
ux, uy = (x - x0) / cl, (y - y0) / cl
hh = math.sqrt(max(r * r - cl * cl / 4, 0))
nx, ny = (-uy, ux) if cw else (uy, -ux)
cx, cy = (x0 + x) / 2 + nx * hh, (y0 + y) / 2 + ny * hh
a0, a1 = math.atan2(y0 - cy, x0 - cx), math.atan2(y - cy, x - cx)
if cw and a1 < a0:
a1 += 2 * math.pi
if not cw and a1 > a0:
a1 -= 2 * math.pi
for k in range(1, 17):
a = a0 + (a1 - a0) * k / 16
self.pts.append((cx + r * math.cos(a), cy + r * math.sin(a)))
return self
def length(self):
return sum(math.hypot(q[0] - p[0], q[1] - p[1]) for p, q in zip(self.pts, self.pts[1:]))
def at(self, f):
"""The point a fraction f along, and the unit direction there."""
goal, run = self.length() * f, 0
for p, q in zip(self.pts, self.pts[1:]):
l_ = math.hypot(q[0] - p[0], q[1] - p[1])
if l_ and run + l_ >= goal:
k = (goal - run) / l_
return (p[0] + (q[0] - p[0]) * k, p[1] + (q[1] - p[1]) * k), ((q[0] - p[0]) / l_, (q[1] - p[1]) / l_)
run += l_
p, q = self.pts[-2], self.pts[-1]
l_ = math.hypot(q[0] - p[0], q[1] - p[1])
return q, ((q[0] - p[0]) / l_, (q[1] - p[1]) / l_)
def draw_path(g, p, ink, sw, dash=None, hl=8, hw=8):
"""The edge and its head on its last point; the stroke stops at the head's base (its last leg is straight)."""
(x1, y1), (x2, y2) = p.pts[-2], p.pts[-1]
l_ = math.hypot(x2 - x1, y2 - y1)
ux, uy = (x2 - x1) / l_, (y2 - y1) / l_
d = p.d[:p.d.rfind(" L")] + f" L{x2 - ux * (hl - 1):.1f},{y2 - uy * (hl - 1):.1f}"
g.path(d, ink, sw, dash=dash, join="round", cap="butt")
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'")
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)
g.rect(mx - 11, my - 11, 22, 22, ink)
gen.head_tri(g, mx + ux * 6, my + uy * 6, ux, uy, gen.INK, 12, 10)
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."""
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
TRACK = dict(gap=40, arch=52, arch_step=36, dip=44, dip_step=16, stub=10, port=16)
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 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 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
# ---- 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 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)}
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}
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]
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))
s, e = a0, a1
while inside(a, *pt(s)):
s += 0.005
while inside(t, *pt(e)):
e -= 0.005
p = Path(*pt(s))
p.arc(*pt(e), rr, 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 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)
def draw_arc_head(g, p, ink, sw, dash):
"""An arc, its stroke ending where its head begins, the head on the arc's tangent."""
pts, run, cut = p.pts, 0, 7
k = len(pts) - 1
while k > 0 and run < cut:
run += math.hypot(pts[k][0] - pts[k - 1][0], pts[k][1] - pts[k - 1][1])
k -= 1
d = "M%.1f,%.1f " % pts[0] + " ".join("L%.1f,%.1f" % q for q in pts[1:k + 1])
g.path(d, ink, sw, dash=dash, join="round")
(x1, y1), (x2, y2) = pts[-2], pts[-1]
l_ = math.hypot(x2 - x1, y2 - y1)
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
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")
def veil(x, y, w, h):
g.o.append(f'')
def label(x, y, key, title, sub):
g.t(x, y, key, 28, GOLD if key == "4" else BRIGHT, "sansb")
g.t(x + 30, y, title, 28, VELLUM, "sansm")
g.t(x, y + 28, sub, 18, FAINT, "sans")
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)
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")
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]
frame_sort_map("22-graph-sort")
frame_open_map("23-graph-open")
frame_strip("24-graph-strip")
frame_forms("43-graph-forms")