mip_graph

  1#!/usr/bin/env python3
  2"""mip_graph — generate a Mermaid dependency graph from every MIP's metadata table and write it
  3into docs/MIPs/README.md between two HTML-comment markers. Reads only a machine-readable
  4**Blocked by** row (comma-separated MIP numbers, or the literal `none`) — the human-readable
  5**Depends on** field stays prose-only and is never parsed, because it legitimately carries four
  6different relations (blocking, blocked-by, co-delivery, negation) in one cell that a regex cannot
  7tell apart (verified against all 28 real MIPs in this repo before this script was written; see
  8docs/MIPs/README.md's own history for the specific mis-parses that ruled it out).
  9
 10    scripts/mip_graph.py                    # regenerate the graph block in docs/MIPs/README.md
 11    scripts/mip_graph.py --check             # exit 1 if the checked-in block is stale or missing
 12    scripts/mip_graph.py --parallel 30 31    # can these two MIPs be worked in parallel?
 13    scripts/mip_graph.py --self-test
 14
 15A MIP with no **Blocked by** row (most of them, today — this is a new, opt-in field) is drawn as
 16an unconnected node. Nothing here invents an edge from prose.
 17"""
 18
 19import argparse
 20import re
 21import sys
 22from pathlib import Path
 23
 24ROOT = Path(__file__).resolve().parent.parent
 25MIPS_DIR = ROOT / "docs" / "MIPs"
 26README = MIPS_DIR / "README.md"
 27
 28START_MARK = "<!-- mip-graph:start -->"
 29END_MARK = "<!-- mip-graph:end -->"
 30
 31TITLE_RE = re.compile(r"^#\s*MIP-(\d{4}):\s*(.+?)\s*$")
 32ROW_RE = re.compile(r"^\|\s*\*\*(?P<key>[^*]+)\*\*\s*\|\s*(?P<val>.*?)\s*\|\s*$")
 33MIP_NUM_RE = re.compile(r"\b(\d{4})\b")
 34
 35STATUS_CLASS = {
 36    "draft": "draft",
 37    "accepted": "accepted",
 38    "implemented": "implemented",
 39    "rejected": "rejected",
 40    "superseded": "rejected",
 41}
 42
 43
 44class Mip:
 45    def __init__(self, num, title, status, blocked_by):
 46        self.num = num
 47        self.title = title
 48        self.status = status
 49        self.blocked_by = blocked_by  # list[int]
 50
 51    def node_id(self):
 52        return f"M{self.num:04d}"
 53
 54    def status_class(self):
 55        s = self.status.lower()
 56        for key, cls in STATUS_CLASS.items():
 57            if s.startswith(key):
 58                return cls
 59        return "draft"
 60
 61
 62def parse_mip_file(path):
 63    lines = path.read_text(encoding="utf-8").splitlines()
 64    num = None
 65    title = path.stem
 66    status = "Draft"
 67    blocked_by = []
 68    for line in lines[:3]:
 69        m = TITLE_RE.match(line)
 70        if m:
 71            num = int(m.group(1))
 72            title = m.group(2)
 73            break
 74    if num is None:
 75        return None
 76    for line in lines:
 77        m = ROW_RE.match(line)
 78        if not m:
 79            continue
 80        key = m.group("key").strip().lower()
 81        val = m.group("val").strip()
 82        if key == "status":
 83            # first word/clause only — "Implemented, ultrareview-verified..." -> "Implemented"
 84            status = re.split(r"[,(]", val, maxsplit=1)[0].strip() or "Draft"
 85        elif key == "blocked by":
 86            if val.lower() != "none":
 87                blocked_by = [int(n) for n in MIP_NUM_RE.findall(val)]
 88    return Mip(num, title, status, blocked_by)
 89
 90
 91def load_mips():
 92    mips = {}
 93    for path in sorted(MIPS_DIR.glob("MIP-*.md")):
 94        if path.name.endswith(".tasks.md"):
 95            continue
 96        mip = parse_mip_file(path)
 97        if mip:
 98            mips[mip.num] = mip
 99    return mips
100
101
102NO_EDGES_PLACEHOLDER = (
103    "_No MIP currently declares a **Blocked by** relationship, so there is nothing to graph yet "
104    "— add that field to a MIP's metadata table and run `just mip-graph` again._"
105)
106
107
108def render_mermaid(mips):
109    edges = []
110    for num in sorted(mips):
111        mip = mips[num]
112        for blocker in mip.blocked_by:
113            if blocker in mips:
114                edges.append((blocker, num))
115    edges = sorted(set(edges))
116    if not edges:
117        return NO_EDGES_PLACEHOLDER
118
119    # Only the MIPs that actually participate in an edge get drawn — an orphan MIP (no declared
120    # Blocked-by relationship in either direction) adds a disconnected box that tells the reader
121    # nothing the index table above doesn't already say, and 20+ of them turned the graph into an
122    # unreadable wall (verified against a real run: 29 MIPs, 0 edges, every node carrying its full
123    # title — the exact complaint that got this rewritten).
124    connected = {a for a, _ in edges} | {b for _, b in edges}
125
126    lines = ["```mermaid", "flowchart TD"]
127    # Dark fills: the site is slate only and injects white label text (MIP-0068 §5.2).
128    lines.append("  classDef draft fill:#1e2129,stroke:#8fa3b0,stroke-dasharray:3 3;")
129    lines.append("  classDef accepted fill:#0b4261,stroke:#1ac5da;")
130    lines.append("  classDef implemented fill:#0f4a2e,stroke:#3ecf6e;")
131    lines.append("  classDef rejected fill:#2a2d35,stroke:#666,color:#999;")
132    for num in sorted(connected):
133        mip = mips[num]
134        # Bare "MIP-NNNN" only — the full title is already one line up in the index table, and a
135        # long label per node is exactly what made the graph unreadable before this rewrite.
136        lines.append(f'  {mip.node_id()}["MIP-{num:04d}"]:::{mip.status_class()}')
137    for a, b in edges:
138        lines.append(f"  {mips[a].node_id()} --> {mips[b].node_id()}")
139    lines.append("```")
140    orphans = sorted(set(mips) - connected)
141    if orphans:
142        orphan_list = ", ".join(f"MIP-{n:04d}" for n in orphans)
143        lines.append("")
144        lines.append(
145            f"_{len(orphans)} MIP(s) with no declared Blocked-by relationship, not graphed: "
146            f"{orphan_list}._"
147        )
148    return "\n".join(lines)
149
150
151def graph_block(mips):
152    return f"{START_MARK}\n{render_mermaid(mips)}\n{END_MARK}"
153
154
155def reachable(mips, start, blocked_direction=True):
156    """Every MIP transitively blocking (or blocked by, if blocked_direction=False) `start`."""
157    seen = set()
158    stack = [start]
159    while stack:
160        cur = stack.pop()
161        if cur not in mips:
162            continue
163        neighbors = (
164            mips[cur].blocked_by
165            if blocked_direction
166            else [m.num for m in mips.values() if cur in m.blocked_by]
167        )
168        for n in neighbors:
169            if n not in seen:
170                seen.add(n)
171                stack.append(n)
172    return seen
173
174
175def source_paths(mip_path):
176    """Backticked paths under a known top-level source dir, from a MIP's §5 Design section."""
177    text = mip_path.read_text(encoding="utf-8")
178    return set(
179        re.findall(
180            r"`((?:core|local|cli|site|scripts)/[A-Za-z0-9_./-]+)`",
181            text,
182        )
183    )
184
185
186def cmd_parallel(a, b):
187    mips = load_mips()
188    if a not in mips or b not in mips:
189        missing = [n for n in (a, b) if n not in mips]
190        print(f"mip_graph --parallel: MIP-{missing[0]:04d} not found")
191        return 1
192    blockers_of_a = reachable(mips, a)
193    blockers_of_b = reachable(mips, b)
194    dep_conflict = b in blockers_of_a or a in blockers_of_b
195    candidates_a = list(MIPS_DIR.glob(f"MIP-{a:04d}-*.md"))
196    candidates_b = list(MIPS_DIR.glob(f"MIP-{b:04d}-*.md"))
197    paths_a = source_paths(candidates_a[0]) if candidates_a else set()
198    paths_b = source_paths(candidates_b[0]) if candidates_b else set()
199    overlap = paths_a & paths_b
200
201    print(f"MIP-{a:04d} vs MIP-{b:04d}:")
202    print(f"  dependency conflict (Blocked by graph): {'yes' if dep_conflict else 'no'}")
203    if overlap:
204        print(f"  §5 source-path overlap: yes — {', '.join(sorted(overlap))}")
205    else:
206        print("  §5 source-path overlap: no (or no backticked source paths found in one/both)")
207    if not dep_conflict and not overlap:
208        print("  -> parallel-safe on both checks")
209        return 0
210    print("  -> NOT confirmed parallel-safe")
211    return 1
212
213
214def cmd_generate(check):
215    if not README.exists():
216        print(f"mip_graph: {README} not found", file=sys.stderr)
217        return 1
218    mips = load_mips()
219    new_block = graph_block(mips)
220    text = README.read_text(encoding="utf-8")
221    if START_MARK in text and END_MARK in text:
222        pre, rest = text.split(START_MARK, 1)
223        _, post = rest.split(END_MARK, 1)
224        new_text = pre + new_block + post
225    else:
226        sep = "" if text.endswith("\n") else "\n"
227        new_text = text + sep + "\n" + new_block + "\n"
228    if check:
229        if new_text != text:
230            print(
231                "mip_graph --check: docs/MIPs/README.md's graph block is stale or missing — "
232                "run `just mip-graph` and commit the result"
233            )
234            return 1
235        print("mip_graph --check: graph block is current")
236        return 0
237    if new_text != text:
238        README.write_text(new_text, encoding="utf-8")
239        print(f"mip_graph: wrote graph block to {README} ({len(mips)} MIPs)")
240    else:
241        print("mip_graph: graph block already current, nothing written")
242    return 0
243
244
245def self_test():
246    fails = 0
247
248    def ok(cond, label):
249        nonlocal fails
250        if cond:
251            print("  ok   " + label)
252        else:
253            print("  FAIL " + label)
254            fails += 1
255
256    sample = """# MIP-0099: A sample title
257
258| | |
259|---|---|
260| **Status** | Draft |
261| **Blocked by** | MIP-0010, MIP-0025 |
262"""
263    tmp = Path("/tmp/mip_graph_selftest_0099.md")
264    tmp.write_text(sample, encoding="utf-8")
265    mip = parse_mip_file(tmp)
266    ok(mip is not None, "parses a real MIP header")
267    ok(mip.num == 99, "extracts the MIP number")
268    ok(mip.title == "A sample title", "extracts the title")
269    ok(mip.blocked_by == [10, 25], "parses a comma-separated Blocked by list")
270    tmp.unlink()
271
272    none_sample = "# MIP-0098: Another\n\n| | |\n|---|---|\n| **Blocked by** | none |\n"
273    tmp2 = Path("/tmp/mip_graph_selftest_0098.md")
274    tmp2.write_text(none_sample, encoding="utf-8")
275    mip2 = parse_mip_file(tmp2)
276    ok(mip2.blocked_by == [], "'none' produces an empty blocker list, not a parsed '0'")
277    tmp2.unlink()
278
279    no_row = "# MIP-0097: No blocked-by row at all\n\n| | |\n|---|---|\n| **Status** | Draft |\n"
280    tmp3 = Path("/tmp/mip_graph_selftest_0097.md")
281    tmp3.write_text(no_row, encoding="utf-8")
282    mip3 = parse_mip_file(tmp3)
283    ok(mip3.blocked_by == [], "a MIP with no Blocked by row at all is unconnected, not an error")
284    tmp3.unlink()
285
286    mips = {
287        10: Mip(10, "Ledger", "Implemented", []),
288        32: Mip(32, "Benchmark", "Draft", [10]),
289    }
290    block = graph_block(mips)
291    ok(block.startswith(START_MARK) and block.endswith(END_MARK), "block is wrapped in markers")
292    ok("M0010 --> M0032" in block, "an edge renders blocker --> blocked")
293    ok(":::implemented" in block and ":::draft" in block, "status classes render per node")
294    ok('"MIP-0010"' in block, "a connected node's label is bare MIP-NNNN, not its title")
295    ok(
296        "Ledger" not in block and "Benchmark" not in block,
297        "a MIP's title never appears in the graph",
298    )
299
300    r = reachable(mips, 32)
301    ok(r == {10}, "reachable() walks the Blocked-by chain")
302
303    zero_edge_mips = {1: Mip(1, "A", "Draft", []), 2: Mip(2, "B", "Draft", [])}
304    zero_block = graph_block(zero_edge_mips)
305    ok("```mermaid" not in zero_block, "zero Blocked-by edges renders no mermaid block at all")
306    ok("nothing to graph yet" in zero_block, "zero edges renders the placeholder text instead")
307
308    orphan_mips = {
309        1: Mip(1, "Orphan", "Draft", []),
310        10: Mip(10, "Ledger", "Implemented", []),
311        32: Mip(32, "Benchmark", "Draft", [10]),
312    }
313    orphan_block = graph_block(orphan_mips)
314    ok("M0001" not in orphan_block, "a MIP with no edge in either direction is not drawn as a node")
315    ok("MIP-0001" in orphan_block, "an excluded orphan is still named in the not-graphed list")
316
317    stale_before = "before\n<!-- mip-graph:start -->\nold\n<!-- mip-graph:end -->\nafter\n"
318    tmp_readme = Path("/tmp/mip_graph_selftest_readme.md")
319    tmp_readme.write_text(stale_before, encoding="utf-8")
320    global README
321    real_readme = README
322    README = tmp_readme
323    try:
324        rc = cmd_generate(check=True)
325        ok(rc == 1, "--check reports stale when the block content differs")
326        cmd_generate(check=False)
327        rc2 = cmd_generate(check=True)
328        ok(rc2 == 0, "--check passes immediately after a regenerate")
329        ok(
330            "before\n" in tmp_readme.read_text() and "after\n" in tmp_readme.read_text(),
331            "content outside the markers is untouched",
332        )
333    finally:
334        README = real_readme
335        tmp_readme.unlink()
336
337    print(f"mip_graph self-test: {'ok' if fails == 0 else f'{fails} FAILED'}")
338    return 0 if fails == 0 else 1
339
340
341def main():
342    ap = argparse.ArgumentParser()
343    ap.add_argument("--check", action="store_true")
344    ap.add_argument("--parallel", nargs=2, type=int, metavar=("MIP_A", "MIP_B"))
345    ap.add_argument("--self-test", action="store_true")
346    args = ap.parse_args()
347
348    if args.self_test:
349        sys.exit(self_test())
350    if args.parallel:
351        sys.exit(cmd_parallel(*args.parallel))
352    sys.exit(cmd_generate(check=args.check))
353
354
355if __name__ == "__main__":
356    main()