Function dfsSort

packages/runtime-core/src/utils/DependencyUtils.ts:253–302

* @zh 使用 DFS 进行拓扑排序 * @en Topological sort using DFS * * @zh DFS 算法特点： * - 实现简单 * - 递归方式，栈溢出风险（极端情况）

(
    items: T[],
    resolveId: (id: string) => string
)

 * - 递归方式，栈溢出风险（极端情况）
 */
function dfsSort<T extends IDependable>(
    items: T[],
    resolveId: (id: string) => string
): TopologicalSortResult<T> {
    const itemMap = new Map<string, T>();
    for (const item of items) {
        itemMap.set(item.id, item);
    }

    const sorted: T[] = [];
    const visited = new Set<string>();
    const visiting = new Set<string>(); // 用于检测循环
    const cycleIds: string[] = [];

    const visit = (item: T): boolean => {
        if (visited.has(item.id)) return true;
        if (visiting.has(item.id)) {
            cycleIds.push(item.id);
            return false; // 发现循环
        }

        visiting.add(item.id);

        for (const dep of item.dependencies || []) {
            const depId = resolveId(dep);
            const depItem = itemMap.get(depId);
            if (depItem && !visit(depItem)) {
                cycleIds.push(item.id);
                return false;
            }
        }

        visiting.delete(item.id);
        visited.add(item.id);
        sorted.push(item);
        return true;
    };

    for (const item of items) {
        if (!visited.has(item.id)) {
            visit(item);
        }
    }

    return {
        sorted,
        hasCycles: cycleIds.length > 0,
        cycleIds: cycleIds.length > 0 ? [...new Set(cycleIds)] : undefined
    };
}

/**
 * @zh 拓扑排序（统一入口）