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    lines.append("  classDef draft fill:#fff,stroke:#999,stroke-dasharray:3 3;")
128    lines.append("  classDef accepted fill:#eef,stroke:#36c;")
129    lines.append("  classDef implemented fill:#efe,stroke:#2a2;")
130    lines.append("  classDef rejected fill:#f8f8f8,stroke:#bbb,color:#999;")
131    for num in sorted(connected):
132        mip = mips[num]
133        # Bare "MIP-NNNN" only — the full title is already one line up in the index table, and a
134        # long label per node is exactly what made the graph unreadable before this rewrite.
135        lines.append(f'  {mip.node_id()}["MIP-{num:04d}"]:::{mip.status_class()}')
136    for a, b in edges:
137        lines.append(f"  {mips[a].node_id()} --> {mips[b].node_id()}")
138    lines.append("```")
139    orphans = sorted(set(mips) - connected)
140    if orphans:
141        orphan_list = ", ".join(f"MIP-{n:04d}" for n in orphans)
142        lines.append("")
143        lines.append(
144            f"_{len(orphans)} MIP(s) with no declared Blocked-by relationship, not graphed: "
145            f"{orphan_list}._"
146        )
147    return "\n".join(lines)
148
149
150def graph_block(mips):
151    return f"{START_MARK}\n{render_mermaid(mips)}\n{END_MARK}"
152
153
154def reachable(mips, start, blocked_direction=True):
155    """Every MIP transitively blocking (or blocked by, if blocked_direction=False) `start`."""
156    seen = set()
157    stack = [start]
158    while stack:
159        cur = stack.pop()
160        if cur not in mips:
161            continue
162        neighbors = (
163            mips[cur].blocked_by
164            if blocked_direction
165            else [m.num for m in mips.values() if cur in m.blocked_by]
166        )
167        for n in neighbors:
168            if n not in seen:
169                seen.add(n)
170                stack.append(n)
171    return seen
172
173
174def source_paths(mip_path):
175    """Backticked paths under a known top-level source dir, from a MIP's §5 Design section."""
176    text = mip_path.read_text(encoding="utf-8")
177    return set(
178        re.findall(
179            r"`((?:core|local|cli|site|scripts)/[A-Za-z0-9_./-]+)`",
180            text,
181        )
182    )
183
184
185def cmd_parallel(a, b):
186    mips = load_mips()
187    if a not in mips or b not in mips:
188        missing = [n for n in (a, b) if n not in mips]
189        print(f"mip_graph --parallel: MIP-{missing[0]:04d} not found")
190        return 1
191    blockers_of_a = reachable(mips, a)
192    blockers_of_b = reachable(mips, b)
193    dep_conflict = b in blockers_of_a or a in blockers_of_b
194    candidates_a = list(MIPS_DIR.glob(f"MIP-{a:04d}-*.md"))
195    candidates_b = list(MIPS_DIR.glob(f"MIP-{b:04d}-*.md"))
196    paths_a = source_paths(candidates_a[0]) if candidates_a else set()
197    paths_b = source_paths(candidates_b[0]) if candidates_b else set()
198    overlap = paths_a & paths_b
199
200    print(f"MIP-{a:04d} vs MIP-{b:04d}:")
201    print(f"  dependency conflict (Blocked by graph): {'yes' if dep_conflict else 'no'}")
202    if overlap:
203        print(f"  §5 source-path overlap: yes — {', '.join(sorted(overlap))}")
204    else:
205        print("  §5 source-path overlap: no (or no backticked source paths found in one/both)")
206    if not dep_conflict and not overlap:
207        print("  -> parallel-safe on both checks")
208        return 0
209    print("  -> NOT confirmed parallel-safe")
210    return 1
211
212
213def cmd_generate(check):
214    if not README.exists():
215        print(f"mip_graph: {README} not found", file=sys.stderr)
216        return 1
217    mips = load_mips()
218    new_block = graph_block(mips)
219    text = README.read_text(encoding="utf-8")
220    if START_MARK in text and END_MARK in text:
221        pre, rest = text.split(START_MARK, 1)
222        _, post = rest.split(END_MARK, 1)
223        new_text = pre + new_block + post
224    else:
225        sep = "" if text.endswith("\n") else "\n"
226        new_text = text + sep + "\n" + new_block + "\n"
227    if check:
228        if new_text != text:
229            print(
230                "mip_graph --check: docs/MIPs/README.md's graph block is stale or missing — "
231                "run `just mip-graph` and commit the result"
232            )
233            return 1
234        print("mip_graph --check: graph block is current")
235        return 0
236    if new_text != text:
237        README.write_text(new_text, encoding="utf-8")
238        print(f"mip_graph: wrote graph block to {README} ({len(mips)} MIPs)")
239    else:
240        print("mip_graph: graph block already current, nothing written")
241    return 0
242
243
244def self_test():
245    fails = 0
246
247    def ok(cond, label):
248        nonlocal fails
249        if cond:
250            print("  ok   " + label)
251        else:
252            print("  FAIL " + label)
253            fails += 1
254
255    sample = """# MIP-0099: A sample title
256
257| | |
258|---|---|
259| **Status** | Draft |
260| **Blocked by** | MIP-0010, MIP-0025 |
261"""
262    tmp = Path("/tmp/mip_graph_selftest_0099.md")
263    tmp.write_text(sample, encoding="utf-8")
264    mip = parse_mip_file(tmp)
265    ok(mip is not None, "parses a real MIP header")
266    ok(mip.num == 99, "extracts the MIP number")
267    ok(mip.title == "A sample title", "extracts the title")
268    ok(mip.blocked_by == [10, 25], "parses a comma-separated Blocked by list")
269    tmp.unlink()
270
271    none_sample = "# MIP-0098: Another\n\n| | |\n|---|---|\n| **Blocked by** | none |\n"
272    tmp2 = Path("/tmp/mip_graph_selftest_0098.md")
273    tmp2.write_text(none_sample, encoding="utf-8")
274    mip2 = parse_mip_file(tmp2)
275    ok(mip2.blocked_by == [], "'none' produces an empty blocker list, not a parsed '0'")
276    tmp2.unlink()
277
278    no_row = "# MIP-0097: No blocked-by row at all\n\n| | |\n|---|---|\n| **Status** | Draft |\n"
279    tmp3 = Path("/tmp/mip_graph_selftest_0097.md")
280    tmp3.write_text(no_row, encoding="utf-8")
281    mip3 = parse_mip_file(tmp3)
282    ok(mip3.blocked_by == [], "a MIP with no Blocked by row at all is unconnected, not an error")
283    tmp3.unlink()
284
285    mips = {
286        10: Mip(10, "Ledger", "Implemented", []),
287        32: Mip(32, "Benchmark", "Draft", [10]),
288    }
289    block = graph_block(mips)
290    ok(block.startswith(START_MARK) and block.endswith(END_MARK), "block is wrapped in markers")
291    ok("M0010 --> M0032" in block, "an edge renders blocker --> blocked")
292    ok(":::implemented" in block and ":::draft" in block, "status classes render per node")
293    ok('"MIP-0010"' in block, "a connected node's label is bare MIP-NNNN, not its title")
294    ok(
295        "Ledger" not in block and "Benchmark" not in block,
296        "a MIP's title never appears in the graph",
297    )
298
299    r = reachable(mips, 32)
300    ok(r == {10}, "reachable() walks the Blocked-by chain")
301
302    zero_edge_mips = {1: Mip(1, "A", "Draft", []), 2: Mip(2, "B", "Draft", [])}
303    zero_block = graph_block(zero_edge_mips)
304    ok("```mermaid" not in zero_block, "zero Blocked-by edges renders no mermaid block at all")
305    ok("nothing to graph yet" in zero_block, "zero edges renders the placeholder text instead")
306
307    orphan_mips = {
308        1: Mip(1, "Orphan", "Draft", []),
309        10: Mip(10, "Ledger", "Implemented", []),
310        32: Mip(32, "Benchmark", "Draft", [10]),
311    }
312    orphan_block = graph_block(orphan_mips)
313    ok("M0001" not in orphan_block, "a MIP with no edge in either direction is not drawn as a node")
314    ok("MIP-0001" in orphan_block, "an excluded orphan is still named in the not-graphed list")
315
316    stale_before = "before\n<!-- mip-graph:start -->\nold\n<!-- mip-graph:end -->\nafter\n"
317    tmp_readme = Path("/tmp/mip_graph_selftest_readme.md")
318    tmp_readme.write_text(stale_before, encoding="utf-8")
319    global README
320    real_readme = README
321    README = tmp_readme
322    try:
323        rc = cmd_generate(check=True)
324        ok(rc == 1, "--check reports stale when the block content differs")
325        cmd_generate(check=False)
326        rc2 = cmd_generate(check=True)
327        ok(rc2 == 0, "--check passes immediately after a regenerate")
328        ok(
329            "before\n" in tmp_readme.read_text() and "after\n" in tmp_readme.read_text(),
330            "content outside the markers is untouched",
331        )
332    finally:
333        README = real_readme
334        tmp_readme.unlink()
335
336    print(f"mip_graph self-test: {'ok' if fails == 0 else f'{fails} FAILED'}")
337    return 0 if fails == 0 else 1
338
339
340def main():
341    ap = argparse.ArgumentParser()
342    ap.add_argument("--check", action="store_true")
343    ap.add_argument("--parallel", nargs=2, type=int, metavar=("MIP_A", "MIP_B"))
344    ap.add_argument("--self-test", action="store_true")
345    args = ap.parse_args()
346
347    if args.self_test:
348        sys.exit(self_test())
349    if args.parallel:
350        sys.exit(cmd_parallel(*args.parallel))
351    sys.exit(cmd_generate(check=args.check))
352
353
354if __name__ == "__main__":
355    main()