// 用 Tarjan SCC 求真实循环依赖,对比插件算法
const fs = require(‘fs’);
const path = require(‘path’);
const ROOT = ‘/Users/dhf/Documents/git/cocos/blast/assets’;
const EXTS = [’.ts’, ‘.tsx’, ‘.js’, ‘.jsx’];
function* walkFiles(dir) {
for (const e of fs.readdirSync(dir, { withFileTypes: true })) {
const p = path.join(dir, e.name);
if (e.isDirectory()) { if (e.name === ‘node_modules’ || e.name.startsWith(’.’)) continue; yield* walkFiles§; }
else if (EXTS.includes(path.extname(e.name).toLowerCase())) yield p;
}
}
const files = […walkFiles(ROOT)];
const fileSet = new Set(files.map(f => path.resolve(f)));
const importRe = /(?:import|export)[^’"]from\s’"[’"]|import\s*’"[’"]/g;
function resolveImport(fromFile, spec) {
if (!spec.startsWith(’.’)) return null;
const base = path.resolve(path.dirname(fromFile), spec);
for (const ext of EXTS) if (fileSet.has(base + ext)) return base + ext;
for (const ext of EXTS) if (fileSet.has(path.join(base, ‘index’ + ext))) return path.join(base, ‘index’ + ext);
return null;
}
const graph = new Map();
for (const f of files) {
const rf = path.resolve(f);
let src; try { src = fs.readFileSync(f, ‘utf8’); } catch { continue; }
let m; importRe.lastIndex = 0;
while ((m = importRe.exec(src))) {
const t = resolveImport(rf, m[1] || m[2]);
if (t && t !== rf) { if (!graph.has(rf)) graph.set(rf, new Set()); graph.get(rf).add(t); }
}
}
// Tarjan SCC (迭代版,避免栈溢出)
const t0 = Date.now();
const index = new Map(), low = new Map(), onStack = new Set(), stack = [];
let idx = 0;
const sccs = [];
for (const start of graph.keys()) {
if (index.has(start)) continue;
const callStack = [[start, 0]];
while (callStack.length) {
const frame = callStack[callStack.length - 1];
const v = frame[0];
if (frame[1] === 0) { index.set(v, idx); low.set(v, idx); idx++; stack.push(v); onStack.add(v); }
let recurse = false;
const targets = graph.get(v) ? […graph.get(v)] : [];
for (let i = frame[1]; i < targets.length; i++) {
const w = targets[i];
if (!index.has(w)) { frame[1] = i + 1; callStack.push([w, 0]); recurse = true; break; }
else if (onStack.has(w)) low.set(v, Math.min(low.get(v), index.get(w)));
}
if (recurse) continue;
if (low.get(v) === index.get(v)) {
const scc = [];
let w;
do { w = stack.pop(); onStack.delete(w); scc.push(w); } while (w !== v);
if (scc.length > 1) sccs.push(scc);
}
callStack.pop();
if (callStack.length) { const p = callStack[callStack.length - 1][0]; low.set(p, Math.min(low.get§, low.get(v))); }
}
}
console.log(‘Tarjan SCC 耗时(ms):’, Date.now() - t0);
console.log(‘真实循环依赖组数(强连通分量>1):’, sccs.length);
sccs.slice(0, 10).forEach((scc, i) => {
console.log(\n环 #${i + 1} (${scc.length} 个文件):);
scc.slice(0, 6).forEach(f => console.log(’ ‘, path.relative(ROOT, f)));
if (scc.length > 6) console.log(’ … 等’, scc.length, ‘个’);
});