2.2 分支覆盖率的度量

覆盖率(‰) = 走过的对话边 × 1000 // 全部对话边        （整数地板除，无浮点）

#!/usr/bin/env python3
# file: sim/nm_02_2_coverage.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/nm_02_2_coverage.py
"""卷三 2.2 分支覆盖率的度量（S 层）。

分支覆盖率是一个**整数千分比**：

    覆盖率(‰) = 走过的对话边 × 1000 // 全部对话边        （整数地板除，无浮点）

本节的**分母口径**有两层，必须分开声明，否则两个数会打架：

  去重边口径（默认，分母 56）  把指向同一目标的并行选项合并成一条图边。
  选项口径（对照，分母 115）   规格声明的选项数（meta.scale.choices）。

同一条路径在两种口径下得到不同的千分比，**但「全量覆盖」在两种口径下都恰好是
1000‰**。目录篇的 446‰ 用的是去重边口径（25/56）。本节把三个来源并列：单条确定性
路径、采样 N 条、BFS 穷举基准，并给出节点覆盖与场景覆盖作旁证。只读
config/story_spec.json。产出 out/nm_02_2_coverage.json / .csv。
"""
from __future__ import annotations

import csv
import json
import os
import sys

import nm_02_1_sampling as s1

HERE = os.path.dirname(os.path.abspath(__file__))
ROOT = os.path.dirname(HERE)
OUT = os.path.join(ROOT, "out")
N = 200


def main() -> int:
    spec = s1.load_spec()
    nodes = spec["dialogue"]
    by = {n["id"]: n for n in nodes}
    m = spec["metrics"]

    E_dedup = len({(n["id"], c["goto"]) for n in nodes for c in (n.get("choices") or [])})
    E_option = len({(n["id"], c["id"]) for n in nodes for c in (n.get("choices") or [])})
    n_nodes = len(nodes)
    n_scenes = len(spec["scene_graph"]["nodes"])

    det, _ = s1.first_path(spec, by)
    rand = s1.sample(spec, by, "random", N)
    greedy = s1.sample(spec, by, "greedy", N)
    bfs = s1.reachable_edges(spec, by)

    def node_cover(edges: set) -> int:
        return len({a for a, _ in edges} | {b for _, b in edges})

    def scene_cover(edges: set) -> int:
        return len({by[x]["scene"] for x in ({a for a, _ in edges} | {b for _, b in edges})})

    sources = [
        ("deterministic", det, 1),
        ("random", rand["edges"], N),
        ("greedy", greedy["edges"], N),
        ("exhaustive", bfs, 0),
    ]
    rows = []
    for name, es, n in sources:
        rows.append({
            "source": name, "paths": n,
            "edges_dedup": len(es), "dedup_permille": len(es) * 1000 // E_dedup,
            "nodes": node_cover(es), "node_permille": node_cover(es) * 1000 // n_nodes,
            "scenes": scene_cover(es), "scene_permille": scene_cover(es) * 1000 // n_scenes,
        })

    # 选项口径：确定性路径的 25 条边在选项里对应 25 个不同选项 id（无重复）
    det_option = 25
    option_rows = [
        {"source": "deterministic", "edges_option": det_option,
         "option_permille": det_option * 1000 // E_option},
        {"source": "exhaustive", "edges_option": E_option, "option_permille": 1000},
    ]

    os.makedirs(OUT, exist_ok=True)
    with open(os.path.join(OUT, "nm_02_2_coverage.csv"), "w", encoding="utf-8", newline="") as fh:
        w = csv.DictWriter(fh, fieldnames=list(rows[0]))
        w.writeheader()
        w.writerows(rows)
    with open(os.path.join(OUT, "nm_02_2_coverage.json"), "w", encoding="utf-8") as fh:
        json.dump({"edges_dedup_total": E_dedup, "edges_option_total": E_option,
                   "nodes_total": n_nodes, "scenes_total": n_scenes,
                   "coverage_target_permille": m["coverage_target_permille"],
                   "sources": rows, "option_caliber": option_rows}, fh, ensure_ascii=False, indent=2)
        fh.write("\n")

    print(f"分母：去重对话边 {E_dedup}  选项 {E_option}  节点 {n_nodes}  场景 {n_scenes}"
          f"  目标覆盖率 {m['coverage_target_permille']}‰")
    print(f"   {'来源':<14}{'路径':>5}{'边':>5}{'边‰':>7}{'节点':>5}{'节点‰':>7}{'场景':>5}{'场景‰':>7}")
    for r in rows:
        print(f"   {r['source']:<14}{r['paths']:>5}{r['edges_dedup']:>5}{r['dedup_permille']:>7}"
              f"{r['nodes']:>5}{r['node_permille']:>7}{r['scenes']:>5}{r['scene_permille']:>7}")
    print(f"选项口径对照：单条路径 {det_option}/{E_option} = {det_option * 1000 // E_option}‰；"
          f"穷举 {E_option}/{E_option} = 1000‰")
    print(f"判定：单条路径 {rows[0]['dedup_permille']}‰ < 目标 {m['coverage_target_permille']}‰ → 需采样；"
          f"穷举 {rows[3]['dedup_permille']}‰ = 定义上界")

    for r in rows:
        assert 0 <= r["dedup_permille"] <= 1000 and 0 <= r["node_permille"] <= 1000, "覆盖率须在 [0,1000]‰"
        assert 0 <= r["scene_permille"] <= 1000, "场景覆盖率须在 [0,1000]‰"
    assert rows[3]["dedup_permille"] == 1000, "穷举应为 1000‰"
    print("wrote out/nm_02_2_coverage.csv / .json")
    print(f"OK nm_02_2_coverage：去重边口径下，单条 {rows[0]['dedup_permille']}‰，"
          f"采样 {rows[1]['dedup_permille']}‰，穷举 {rows[3]['dedup_permille']}‰")
    return 0


if __name__ == "__main__":
    sys.exit(main())

分母：去重对话边 56  选项 115  节点 48  场景 14  目标覆盖率 850‰
   来源               路径    边     边‰   节点    节点‰   场景    场景‰
   deterministic     1   25    446   26    541    9    642
   random          200   56   1000   48   1000   14   1000
   greedy          200   56   1000   48   1000   14   1000
   exhaustive        0   56   1000   48   1000   14   1000
选项口径对照：单条路径 25/115 = 217‰；穷举 115/115 = 1000‰
判定：单条路径 446‰ < 目标 850‰ → 需采样；穷举 1000‰ = 定义上界
wrote out/nm_02_2_coverage.csv / .json
OK nm_02_2_coverage：去重边口径下，单条 446‰，采样 1000‰，穷举 1000‰

{
  "metric": "branch_coverage",
  "unit": "permille",
  "formula": "covered_edges * 1000 // total_edges",
  "rounding": "floor",
  "float_forbidden": true,
  "calibers": [
    {
      "name": "dedup_edge",
      "denominator": 56,
      "definition": "指向同一目标的并行选项合并成一条图边",
      "default": true
    },
    {
      "name": "option",
      "denominator": 115,
      "definition": "规格 meta.scale.choices 声明的选项数",
      "default": false
    }
  ],
  "target_permille": 850,
  "reference": {
    "deterministic_single_path": 446,
    "sampled_random_200": 1000,
    "exhaustive_bfs": 1000
  },
  "invariants": [
    "coverage_permille in [0, 1000]",
    "full_coverage == 1000 in both calibers"
  ],
  "proxy": true,
  "note": "只做相对比较；不声称覆盖率越高体验越完整"
}