5.3 图集变更的传播与回归
4.1 依赖图显式与隐式 把「谁引用谁」建成了有向图，4.3 资源清理与不可达资产 用它在图上做前向可达。本节换一个方向：从一次变更出发，问「谁会被它碰到」。5.1 已经保证了装箱的确定性——同一批输入产出同一张布局；但「可复现」不等于「无影响」：只要图集重打包，坐标变了，UV 就变，引用它的资产就必须重跑。卷一 10.3 图集与批次的耦合 讲了这件事在批次上的后果，本节把它算成一份可执行的回归清单。
先立一条判据：「受影响」的定义是「沿反向引用边可达」，与文件系统、打包器、引擎都无关——因此 Python 与 TypeScript 能各自独立算一遍再逐位对照。
5.3.1 三层引用图与回归套件映射
《星屑旅店》的图集引用是三层：rect（图集区域）→ sprite（引用若干 rect）→ material（引用若干 sprite）→ screen（引用若干 material）。箭头指向上层，也就是说「被引用者变了，引用者就要重跑」。把每条边反向存一份（ref → 引用它的节点），一次变更就变成一次 BFS：从变更的 rect 出发，逐层向上走，走到的每个节点都进受影响集合。
这套引用关系落在 config/ta05_propagation.json：17 个节点（9 sprite / 4 material / 4 screen）、23 个被引用的 rect、两张变更单——rect_repack（三块图标位置变化）与 atlas_resize（图集升档，全部 UV 变化）。每个节点按 kind 映射到一个回归套件：sprite → uv-binding、material → drawcall-batch、screen → golden-screenshot。于是「传播」的输出不只是一串 id，而是该跑哪几套回归、各跑多少项。
5.3.2 S 层：反向索引 + BFS 传播
下面这段是 S 层脚本，建反向索引后从变更 rect 做 BFS，输出受影响资产清单、按 kind 的分布、爆炸半径千分比 affectedCount*1000 // nodeCount，以及需要重跑的回归项与套件分布：
#!/usr/bin/env python3
# file: sim/ta05_propagation.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/ta05_propagation.py
"""图集变更的传播与回归（S 层，卷二 5.3）。
图集重打包后，位置/UV 变了的 rect 会牵动所有引用它的资产：rect → sprite → material →
screen 三层引用构成有向图。本脚本建反向索引（ref → 引用者），从变更的 rect 出发做 BFS，
输出**受影响资产清单**与**需要重跑的回归项**（按 kind 映射到回归套件）。
指标全整数：``permille = affectedCount * 1000 // nodeCount``（爆炸半径千分比）。所有输出按 id
排序 → 与 TS 逐位一致。落盘 out/ta05_propagation.json。
"""
import json
import os
import sys
from collections import deque
ROOT = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
CFG = os.path.join(ROOT, "config/ta05_propagation.json")
OUT = os.path.join(ROOT, "out")
def reverse_index(nodes):
"""ref → 引用它的节点 id 列表（排序后确定）。"""
rev = {}
for n in nodes:
for r in n["refs"]:
rev.setdefault(r, []).append(n["id"])
for k in rev:
rev[k].sort()
return rev
def propagate(nodes, rev, seeds):
"""从种子出发沿反向边 BFS，返回排序后的受影响节点 id 列表。"""
seen, queue, affected = set(), deque(seeds), []
while queue:
cur = queue.popleft()
for parent in rev.get(cur, []):
if parent in seen:
continue
seen.add(parent)
affected.append(parent)
queue.append(parent)
return sorted(affected)
def main() -> int:
cfg = json.load(open(CFG, encoding="utf-8"))
os.makedirs(OUT, exist_ok=True)
nodes, suites = cfg["nodes"], cfg["suites"]
kind_of = {n["id"]: n["kind"] for n in nodes}
rev = reverse_index(nodes)
all_rects = sorted({r for n in nodes for r in n["refs"]})
changes = []
for ch in cfg["changes"]:
seeds = all_rects if ch.get("allRects") else ch["rects"]
affected = propagate(nodes, rev, seeds)
by_kind = {}
for nid in affected:
k = kind_of[nid]
by_kind[k] = by_kind.get(k, 0) + 1
regression = [{"id": f"reg_{nid}", "suite": suites[kind_of[nid]]} for nid in affected]
reg_by_suite = {}
for r in regression:
reg_by_suite[r["suite"]] = reg_by_suite.get(r["suite"], 0) + 1
changes.append({
"id": ch["id"], "reason": ch["reason"], "seedCount": len(seeds),
"affected": affected, "affectedCount": len(affected), "byKind": by_kind,
"permille": len(affected) * 1000 // len(nodes),
"regression": regression, "regressionBySuite": reg_by_suite,
})
report = {"project": cfg["project"], "nodeCount": len(nodes),
"rectCount": len(all_rects), "suites": suites, "changes": changes}
with open(os.path.join(OUT, "ta05_propagation.json"), "w", encoding="utf-8") as fh:
json.dump(report, fh, ensure_ascii=False, indent=2, sort_keys=True)
fh.write("\n")
print(f"nodeCount={len(nodes)} rectCount={len(all_rects)}")
for c in changes:
print(f" {c['id']:<12} seeds={c['seedCount']} affected={c['affectedCount']} "
f"permille={c['permille']} byKind={c['byKind']} regression={c['regressionBySuite']}")
print("wrote out/ta05_propagation.json")
return 0
if __name__ == "__main__":
sys.exit(main())
实跑输出（/opt/homebrew/bin/python3 sim/ta05_propagation.py）：
nodeCount=17 rectCount=23
rect_repack seeds=3 affected=8 permille=470 byKind={'material': 2, 'screen': 3, 'sprite': 3} regression={'drawcall-batch': 2, 'golden-screenshot': 3, 'uv-binding': 3}
atlas_resize seeds=23 affected=17 permille=1000 byKind={'material': 4, 'screen': 4, 'sprite': 9} regression={'drawcall-batch': 4, 'golden-screenshot': 4, 'uv-binding': 9}
wrote out/ta05_propagation.json
读出来的结论：改三块图标，牵动 8 个资产（470‰），要重跑 8 个回归项——这就是「变更的长腿」。注意 screen 层 3 个里包含 screen_inn_room 与 screen_title，它们并没有直接引用那三块图标，而是经 mat_ui_common 间接够到的：传播必须走到不动点，只看一跳会漏掉一半。极端情形是 atlas_resize：全部 UV 变化，17 个节点全中，爆炸半径 1000‰，此时全量回归比挑拣更便宜。
5.3.3 P 层：TS 内核
下面这段是 P 层内核，把同一套反向索引与 BFS 用 TypeScript 重写。所有输出按 id 排序、无随机，因此与 Python 逐位一致：
// file: core/src/ta05/propagation.ts
// tier: P
// verify: node --test 'core/test/ta05_*.test.ts'
// 卷二 5.3：图集变更传播的 TS 侧实现。建反向索引（ref → 引用者），从变更 rect 做 BFS，
// 输出受影响节点与回归项。全整数、无随机、输出按 id 排序 → 与 sim/ta05_propagation.py 逐位一致。
export type Node = { id: string; kind: string; refs: string[] };
export function reverseIndex(nodes: Node[]): Map<string, string[]> {
const rev = new Map<string, string[]>();
for (const n of nodes) {
for (const r of n.refs) {
const a = rev.get(r) ?? [];
a.push(n.id);
rev.set(r, a);
}
}
for (const [, a] of rev) a.sort();
return rev;
}
export function propagate(nodes: Node[], rev: Map<string, string[]>, seeds: string[]): string[] {
const seen = new Set<string>();
const queue = [...seeds];
const affected: string[] = [];
while (queue.length > 0) {
const cur = queue.shift() as string;
for (const parent of rev.get(cur) ?? []) {
if (seen.has(parent)) continue;
seen.add(parent);
affected.push(parent);
queue.push(parent);
}
}
return affected.sort();
}
export function byKind(nodes: Node[], affected: string[]): Record<string, number> {
const kindOf = new Map(nodes.map((n) => [n.id, n.kind]));
const out: Record<string, number> = {};
for (const id of affected) {
const k = kindOf.get(id) as string;
out[k] = (out[k] ?? 0) + 1;
}
return out;
}
export function regressions(suites: Record<string, string>, nodes: Node[], affected: string[]): {
id: string; suite: string;
}[] {
const kindOf = new Map(nodes.map((n) => [n.id, n.kind]));
return affected.map((id) => ({ id: `reg_${id}`, suite: suites[kindOf.get(id) as string] }));
}
5.3.4 P 层测试：跨语言对照与负例
下面这段是 P 层测试，读的是 S 层落盘的 out/ta05_propagation.json（不是同一份源码），对两张变更单逐项断言 affected / byKind / 爆炸半径 / 回归项与 Python 相等，并带两个负例——改一个无人引用的 rect 时受影响集合必须为空，改全部 rect 时爆炸半径必须到 1000‰：
// file: core/test/ta05_propagation.test.ts
// tier: P
// verify: node --test 'core/test/ta05_*.test.ts'
// 卷二 5.3 跨语言对照：读 sim/ta05_propagation.py 落盘的 out/ta05_propagation.json，断言 TS
// 侧传播出的 affected / byKind / permille / regression 与 Python 逐位一致。带负例：改一个
// 无人引用的 rect，受影响集合必须为空；改全部 rect 则爆炸半径必须到 1000‰。
import test from "node:test";
import assert from "node:assert/strict";
import { readFileSync } from "node:fs";
import { createHash } from "node:crypto";
import { dirname, resolve } from "node:path";
import { fileURLToPath } from "node:url";
import { reverseIndex, propagate, byKind, regressions, type Node } from "../src/ta05/propagation.ts";
const ROOT = resolve(dirname(fileURLToPath(import.meta.url)), "../..");
const cfg = JSON.parse(readFileSync(resolve(ROOT, "config/ta05_propagation.json"), "utf8"));
const py = JSON.parse(readFileSync(resolve(ROOT, "out/ta05_propagation.json"), "utf8"));
test("跨语言：两次变更的 affected / byKind / permille / regression 逐位一致", () => {
const nodes = cfg.nodes as Node[];
const rev = reverseIndex(nodes);
const allRects = [...new Set(nodes.flatMap((n) => n.refs))].sort();
const seedsById = new Map<string, string[]>(
(cfg.changes as { id: string; rects?: string[]; allRects?: boolean }[])
.map((c) => [c.id, c.allRects ? allRects : (c.rects as string[])]));
const lines: string[] = [];
for (const c of py.changes as { id: string; affected: string[]; byKind: Record<string, number>; permille: number; regression: { id: string; suite: string }[] }[]) {
const seeds = seedsById.get(c.id) as string[];
const affected = propagate(nodes, rev, seeds);
assert.deepEqual(affected, c.affected, `${c.id} affected`);
assert.deepEqual(byKind(nodes, affected), c.byKind, `${c.id} byKind`);
assert.equal(Math.floor((affected.length * 1000) / nodes.length), c.permille, `${c.id} permille`);
assert.deepEqual(regressions(cfg.suites, nodes, affected), c.regression, `${c.id} regression`);
lines.push(`${c.id}:${affected.length}:${c.permille}`);
}
console.log(`propagation digest = ${createHash("sha256").update(lines.join("\n")).digest("hex").slice(0, 16)}`);
});
test("负例：无人引用的 rect 变更 → 受影响集合为空", () => {
const nodes = cfg.nodes as Node[];
const rev = reverseIndex(nodes);
const affected = propagate(nodes, rev, ["scene_sky-strip_v01"]);
assert.deepEqual(affected, []);
assert.equal(Math.floor((affected.length * 1000) / nodes.length), 0);
// 全量变更必须命中每一个节点（爆炸半径 1000‰）
const allRects = [...new Set(nodes.flatMap((n) => n.refs))].sort();
const all = propagate(nodes, rev, allRects);
assert.equal(all.length, nodes.length);
assert.equal(Math.floor((all.length * 1000) / nodes.length), 1000);
});
实跑输出（node --test core/test/ta05_propagation.test.ts）：
propagation digest = 415244df0a41a495
✔ 跨语言：两次变更的 affected / byKind / permille / regression 逐位一致
✔ 负例：无人引用的 rect 变更 → 受影响集合为空
ℹ tests 2
ℹ pass 2
ℹ fail 0
propagation digest = 415244df0a41a495 是测试按 变更 id : 受影响数 : 爆炸半径 拼起来算的跨语言摘要——任一层的传播结果变一位它都会变。两个负例才是真正锁住语义的部分：**「改没人用的东西，谁也不受影响」排除了传播写反（把引用者当成被引用者），「全改就是 1000‰」**排除了漏层（只走一跳）。
5.3.5 结果对照与三条边界
两张变更单的结果并排看，就能读出「变更代价」的量级：
| 变更单 | 种子 rect | 受影响资产 | 爆炸半径 | sprite / material / screen | uv-binding / drawcall-batch / golden-screenshot |
|---|---|---|---|---|---|
rect_repack | 3 | 8 | 470‰ | 3 / 2 / 3 | 3 / 2 / 3 |
atlas_resize | 23 | 17 | 1000‰ | 9 / 4 / 4 | 9 / 4 / 4 |
- 反向 BFS 给出的是「受影响」，不是「已损坏」。位置变了不等于渲染错了——很多情况下 UV 是运行时按 sprite 元数据算的，资产只需重跑回归，不需要人工改。清单的作用是把重跑范围从「全量」缩到「必要」。
golden-screenshot这一类回归需要真实渲染环境：真截图回归要在真实引擎里跑出画面再比对，需真实环境（引擎 / 渲染器），命令行不可复现。本节只算该跑哪些套件、各多少项，不产生真实截图比对结果。- 图必须无环。传播假定引用图是 DAG（4.2 环检测与悬空引用
已用负例锁住）；若图里有环，BFS 靠
seen仍会终止，但「谁该先重跑」的拓扑顺序就失去意义了。
一句话总结：变更的代价不在变更本身，而在它的长腿。 把引用关系反过来存一份，一次 BFS 就能把「改三块图标要重跑 8 个资产」从经验判断变成可执行清单。
阅读导航：上一节：5.2 mip 链与压缩格式字节账 · 下一节：6.1 材质参数表与默认值 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。