4.2 环检测与悬空引用
4.1 建好的图有两种「病」会让管线停摆：环与悬空引用。环意味着没有任何一个资产可以「先」打包——拓扑排序无解，增量构建会死循环；悬空引用意味着边指向一个不存在的节点——打包时找不到源文件，只能报错或静默丢引用。引擎侧怎么在加载期兜底属于实现，本节外链 《渲染引擎》的范围划分 ，只做建图之后的图算法。
两类问题的判据完全不同：环是图的结构属性（节点之间互相可达），悬空是边对节点的存在性检查。所以它们用两个独立函数，输出两套前缀（CYCLE: / DANGLING:），谁都不会把对方掩盖掉。
4.2.1 三色标记：白 / 灰 / 黑
找环最稳的办法是 DFS 三色标记。给每个节点一个颜色：
| 颜色 | 含义 |
|---|---|
| 白 | 还没访问过 |
| 灰 | 在当前 DFS 递归栈上（正在展开，还没收口） |
| 黑 | 已完成（子树全部走完） |
DFS 时若遇到一条指向灰节点的边，那就是回边——它连回当前栈上的祖先，说明存在环。环路径就是栈上从那个灰节点到当前节点的一段。灰→黑 的转换保证了「同一个环只会在收口前被发现一次」。
与强连通分量法（Tarjan）相比，三色标记多出来的是环路径本身：Tarjan 只告诉你「这几个节点在一个分量里」，三色标记直接给出 furn_lamp_01 -> furn_lamp_01_v2 -> furn_lamp_01 这条边走顺序——修复时你需要的正是它。
4.2.2 S 层：DFS 三色标记找环 + 悬空检测
下面这段是 S 层脚本，读 4.1 的配置，用三色标记找环、逐边判悬空。环路径旋转到字典序最小节点开头再拼字符串，故与遍历起点、与语言都无关：
#!/usr/bin/env python3
# file: sim/ta04_cycle.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/ta04_cycle.py
"""4.2 环检测与悬空引用：读 config/ta04_graph.json，用 **DFS 三色标记**（白/灰/黑）找环，
逐边判悬空引用。
三色标记：白=未访问，灰=在当前递归栈上，黑=已完成。DFS 中若遇到一条指向**灰**节点的边，
就是回边，说明存在环——环路径即当前栈上从该灰节点到当前节点的一段。
环用「沿环方向旋转到字典序最小节点开头，再以 ``->`` 连接」规范化，故与遍历起点、
与语言都无关。落 out/ta04_cycle.json 供 P 层逐位对照。
"""
import hashlib
import json
import os
import sys
from ta04_graph import build_graph
ROOT = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
WHITE, GRAY, BLACK = 0, 1, 2
def adjacency(ids, edges):
adj = {n: [] for n in ids}
for s, t, _ in edges:
if s in adj and t in adj:
adj[s].append(t)
for n in adj:
adj[n] = sorted(set(adj[n]))
return adj
def canon(cycle):
"""把环路径旋转到字典序最小节点开头（保持方向），拼成稳定字符串。"""
k = cycle.index(min(cycle))
rot = cycle[k:] + cycle[:k]
return "CYCLE:" + "->".join(rot)
def find_cycles(ids, edges):
adj = adjacency(ids, edges)
color = {n: WHITE for n in ids}
path = []
cycles = set()
def dfs(v):
color[v] = GRAY
path.append(v)
for w in adj[v]:
if color[w] == WHITE:
dfs(w)
elif color[w] == GRAY:
cycles.add(canon(path[path.index(w):]))
path.pop()
color[v] = BLACK
for v in sorted(ids):
if color[v] == WHITE:
dfs(v)
return sorted(cycles)
def dangling(ids, edges):
idset = set(ids)
return sorted(f"DANGLING:{s}->{t}" for s, t, _ in edges if t not in idset)
def main():
spec = json.load(open(os.path.join(ROOT, "config/ta04_graph.json"), encoding="utf-8"))
ids, edges = build_graph(spec)
cyc = find_cycles(ids, edges)
dang = dangling(ids, edges)
findings = cyc + dang
digest = hashlib.sha256("\n".join(findings).encode("utf-8")).hexdigest()[:16]
rep = {
"nodeCount": len(ids),
"edgeCount": len(edges),
"cycles": cyc,
"cycleCount": len(cyc),
"dangling": dang,
"danglingCount": len(dang),
"findings": findings,
"digest": digest,
}
with open(os.path.join(ROOT, "out/ta04_cycle.json"), "w", encoding="utf-8") as f:
json.dump(rep, f, ensure_ascii=False, indent=2)
f.write("\n")
print(f"nodes={rep['nodeCount']} edges={rep['edgeCount']} "
f"cycles={rep['cycleCount']} dangling={rep['danglingCount']}")
for x in findings:
print(f" {x}")
print(f"digest={digest}")
print("wrote out/ta04_cycle.json")
return 0
if __name__ == "__main__":
sys.exit(main())
实跑 /opt/homebrew/bin/python3 sim/ta04_cycle.py：
nodes=17 edges=18 cycles=1 dangling=1
CYCLE:furn_lamp_01->furn_lamp_01_v2
DANGLING:mat_counter_wood->tex_missing_wood
digest=8987fc63064670ba
wrote out/ta04_cycle.json
4.1 埋的两个问题资产都被抓出来了：furn_lamp_01 显式引用变体 furn_lamp_01_v2，而变体又经命名约定隐式依赖基础 furn_lamp_01——这个环有一条边是隐式的，只读 dependsOn 的检查器根本看不见它。悬空那条则是 mat_counter_wood 的槽位指向不存在的贴图。
4.2.3 P 层：三色标记的 TS 内核
下面这段是 P 层 TS 内核 core/src/ta04/cycle.ts，与上面的 Python 逐条对应：同一个 WHITE/GRAY/BLACK、同一套 canon 旋转规则、同一套排序：
// file: core/src/ta04/cycle.ts
// tier: P
// verify: node --test 'core/test/ta04_*.test.ts'
// 4.2 环检测与悬空引用。与 sim/ta04_cycle.py 同一套规则：DFS 三色标记（白/灰/黑）找回边，
// 环旋转到字典序最小节点开头做规范化；悬空引用逐边判定。只允许可擦除 TS 语法。
import type { Edge } from "./graph.ts";
const WHITE = 0;
const GRAY = 1;
const BLACK = 2;
export function adjacency(ids: string[], edges: Edge[]): Record<string, string[]> {
const adj: Record<string, string[]> = {};
for (const n of ids) adj[n] = [];
for (const [s, t] of edges) if (s in adj && t in adj) adj[s].push(t);
for (const n of Object.keys(adj)) adj[n] = [...new Set(adj[n])].sort();
return adj;
}
export function canon(cycle: string[]): string {
let k = 0;
for (let i = 1; i < cycle.length; i += 1) if (cycle[i] < cycle[k]) k = i;
const rot = cycle.slice(k).concat(cycle.slice(0, k));
return `CYCLE:${rot.join("->")}`;
}
export function findCycles(ids: string[], edges: Edge[]): string[] {
const adj = adjacency(ids, edges);
const color: Record<string, number> = {};
for (const n of ids) color[n] = WHITE;
const path: string[] = [];
const cycles = new Set<string>();
const dfs = (v: string): void => {
color[v] = GRAY;
path.push(v);
for (const w of adj[v]) {
if (color[w] === WHITE) dfs(w);
else if (color[w] === GRAY) cycles.add(canon(path.slice(path.indexOf(w))));
}
path.pop();
color[v] = BLACK;
};
for (const v of [...ids].sort()) if (color[v] === WHITE) dfs(v);
return [...cycles].sort();
}
export function danglingRefs(ids: string[], edges: Edge[]): string[] {
const idset = new Set(ids);
return edges
.filter(([, t]) => !idset.has(t))
.map(([s, t]) => `DANGLING:${s}->${t}`)
.sort();
}
4.2.4 负例：人为造环，必须 fail
本节最重要的不是「干净图报 0」，而是「有环必须报出来」。 测试一边读 Python 产物做跨语言对照，一边在内存里造环，验证检测器真的会失败：
// file: core/test/ta04_cycle.test.ts
// tier: P
// verify: node --test 'core/test/ta04_*.test.ts'
// 4.2 环检测。跨语言对照读 out/ta04_cycle.json；**负例是本节核心**：人为造环，检测器必须报出来。
import test from "node:test";
import assert from "node:assert/strict";
import { readFileSync } from "node:fs";
import { dirname, resolve } from "node:path";
import { fileURLToPath } from "node:url";
import { createHash } from "node:crypto";
import { buildGraph, type Edge } from "../src/ta04/graph.ts";
import { danglingRefs, findCycles } from "../src/ta04/cycle.ts";
const HERE = dirname(fileURLToPath(import.meta.url));
const ROOT = resolve(HERE, "../..");
const spec = JSON.parse(readFileSync(resolve(ROOT, "config/ta04_graph.json"), "utf8"));
const py = JSON.parse(readFileSync(resolve(ROOT, "out/ta04_cycle.json"), "utf8"));
const digest16 = (ls: string[]): string =>
createHash("sha256").update(ls.join("\n"), "utf8").digest("hex").slice(0, 16);
test("环与悬空：TS 复算与 Python 产物逐位一致", () => {
const { ids, edges } = buildGraph(spec);
assert.deepEqual(findCycles(ids, edges), py.cycles);
assert.deepEqual(danglingRefs(ids, edges), py.dangling);
assert.equal(digest16([...py.cycles, ...py.dangling]), py.digest);
});
test("负例：人为造一个环，环检测必须报出来（干净图不报）", () => {
const cyc: Edge[] = [["a", "b", "x"], ["b", "a", "x"], ["c", "a", "x"]];
assert.deepEqual(findCycles(["a", "b", "c"], cyc), ["CYCLE:a->b"]);
const clean: Edge[] = [["a", "b", "x"]];
assert.deepEqual(findCycles(["a", "b"], clean), []);
});
test("负例：自环与三节点环都规范成稳定字符串", () => {
assert.deepEqual(findCycles(["solo"], [["solo", "solo", "x"]]), ["CYCLE:solo"]);
const tri: Edge[] = [["x", "y", "x"], ["y", "z", "x"], ["z", "x", "x"]];
assert.deepEqual(findCycles(["x", "y", "z"], tri), ["CYCLE:x->y->z"]);
});
test("负例：悬空引用必须被检出，指向存在的 id 不算悬空", () => {
const e: Edge[] = [["a", "b", "x"], ["a", "ghost", "x"]];
assert.deepEqual(danglingRefs(["a", "b"], e), ["DANGLING:a->ghost"]);
});
test("真实样本：混合环（一条显式边 + 一条隐式变体边）只有建模隐式边才看得见", () => {
const { ids, edges } = buildGraph(spec);
assert.deepEqual(findCycles(ids, edges), ["CYCLE:furn_lamp_01->furn_lamp_01_v2"]);
const explicitOnly = edges.filter(([, , k]) => k === "explicit");
assert.deepEqual(findCycles(ids, explicitOnly), []);
});
实跑 node --test 'core/test/ta04_cycle.test.ts'：
✔ 环与悬空：TS 复算与 Python 产物逐位一致
✔ 负例：人为造一个环，环检测必须报出来（干净图不报）
✔ 负例：自环与三节点环都规范成稳定字符串
✔ 负例：悬空引用必须被检出，指向存在的 id 不算悬空
✔ 真实样本：混合环（一条显式边 + 一条隐式变体边）只有建模隐式边才看得见
ℹ tests 5
ℹ pass 5
ℹ fail 0
「负例」要证明的不是「测试通过了」，而是「断言是活的、不是空转」。用一个一次性脚本反证：把「有环图」硬断言成「干净」必须抛错，把「干净图」断言成「干净」必须通过：
有环图 findCycles = ["CYCLE:a->b"]
干净图 findCycles = []
EXPECTED FAIL: Expected values to be strictly deep-equal:
干净图断言通过（负例非空转）
第 3 行正是造环负例确实 fail 的证明：assert.deepEqual(["CYCLE:a->b"], []) 抛出了断言错误。换句话说，如果环检测器坏了、恒返回空，这条负例会立刻把 CI 门禁打红——它不是一个永远为真的摆设。
4.2.5 环为什么必须规范化
环是一个有向环，同一张图里可以从任意节点开始遍历，碰到的第一条回边也依赖邻接表的顺序。如果直接报「DFS 碰到的第一条环」，两语言、两次运行的输出都可能不同，跨语言对照就做不了，人也没法拿它去和上一次的告警 diff。
规范化只做一件事：把环路径沿环方向旋转到字典序最小的节点开头。furn_lamp_01 -> furn_lamp_01_v2 -> furn_lamp_01 与 furn_lamp_01_v2 -> furn_lamp_01 -> furn_lamp_01_v2 是两个起点、同一个环，旋转后都变成 CYCLE:furn_lamp_01->furn_lamp_01_v2。自环 solo -> solo 规范化成 CYCLE:solo。规范化之后，环集合是字符串数组，逐位一致——P 层测试里 findCycles 与 Python 产物 assert.deepEqual 过的正是这个。
真 DCC 内部的引用图（材质 → 采样器 → 贴图节点）由 DCC 自己维护，本机无 DCC、不可复现，标 X；本节只管导出清单这一层。
阅读导航：上一节：4.1 依赖图：显式引用与隐式引用 · 下一节：4.3 资源清理与不可达资产 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。