云端 Mac 上的 iOS 依赖图验收：稳定拓扑排序与环检测

同一批资源处理任务，在本地按预期执行，搬到云端 Mac 的流水线后却偶尔先生成索引、再生成资源。问题未必出在机器：如果任务顺序来自字典遍历，或者把“已经排进队列”误当成“依赖已经完成”，换一次进程就可能暴露错误。下面用独立 Swift 脚本验收依赖图，不需要先启动模拟器。

先定义边的方向与失败语义

手写顺序适合固定且很短的流程；依赖图适合任务会增删、多个步骤共享前置条件的流程。若所有工作原本就是线性执行，引入图只会增加维护成本。

本文用“任务名 → 前置任务集合”表示输入。例如 index 依赖 assets，输出必须先出现后者。任务名作为稳定标识，不随显示语言变化；互不依赖的任务按标识的字典序选择。

输入还要约定三件事：重复边合并，未知依赖立即失败，自依赖视为环。空图合法，返回空数组。不要悄悄创建未知节点，否则拼错名称也会被当成成功。

排序只证明依赖关系能否排成合法序列，不证明任务已经完成，更不证明产物正确。执行状态与图结构应分开验收。

写一个可运行的稳定排序器

在节点工作目录保存下面内容为 graph-check.swift。代码只依赖 Swift 标准库；使用当前已选定工具链运行，不需要安装额外包。算法维护每个任务尚未满足的依赖数，每轮选择名字最小的就绪任务。

enum GraphError: Error, Equatable {
    case unknown(task: String, dependency: String)
    case blocked([String])
}

func ordered(_ graph: [String: [String]]) throws -> [String] {
    let names = graph.keys.sorted()
    let known = Set(names)
    var remaining: [String: Int] = [:]
    var successors: [String: [String]] = [:]

    for task in names {
        let dependencies = Set(graph[task]!)
        for dependency in dependencies.sorted() {
            guard known.contains(dependency) else {
                throw GraphError.unknown(
                    task: task, dependency: dependency
                )
            }
            successors[dependency, default: []].append(task)
        }
        remaining[task] = dependencies.count
    }

    var ready = names.filter { remaining[$0] == 0 }
    var result: [String] = []

    while !ready.isEmpty {
        let task = ready.removeFirst()
        result.append(task)
        for next in successors[task, default: []] {
            remaining[next]! -= 1
            if remaining[next] == 0 {
                ready.append(next)
            }
        }
        ready.sort()
    }

    guard result.count == names.count else {
        throw GraphError.blocked(
            names.filter { remaining[$0]! > 0 }
        )
    }
    return result
}

func check() throws {
    let graph = [
        "assets": ["fetch", "fetch"],
        "fetch": [],
        "index": ["assets"],
        "lint": []
    ]
    let result = try ordered(graph)
    precondition(result == ["fetch", "assets", "index", "lint"])

    let position = Dictionary(
        uniqueKeysWithValues: result.enumerated().map {
            ($0.element, $0.offset)
        }
    )
    precondition(result.count == graph.count)
    precondition(Set(result) == Set(graph.keys))
    for (task, dependencies) in graph {
        for dependency in dependencies {
            precondition(position[dependency]! < position[task]!)
        }
    }

    let empty = try ordered([:])
    precondition(empty.isEmpty)

    do {
        _ = try ordered(["export": ["missing"]])
        preconditionFailure("Unknown dependency was accepted")
    } catch let error as GraphError {
        precondition(error == .unknown(
            task: "export", dependency: "missing"
        ))
    }

    do {
        _ = try ordered([
            "a": ["b"], "b": ["a"], "report": ["b"]
        ])
        preconditionFailure("Cycle was accepted")
    } catch let error as GraphError {
        precondition(error == .blocked(["a", "b", "report"]))
    }
}

try check()

xcrun swift graph-check.swift

通过时没有输出，失败时进程返回非零退出码。不要用禁用前置条件检查的优化模式执行这份验收脚本。接入项目后，可把相同断言移到正式测试目标，避免业务构建设置影响检查行为。

用性质断言补齐样本盲区

固定结果能发现顺序漂移，但也可能把错误实现一起固定下来。因此代码同时验证输出数量、节点集合，以及每条边的先后关系。这三类检查分别阻止遗漏、重复和依赖倒置。

接着增加菱形图：两个任务依赖同一个根，最后一个任务依赖这两个任务。根只能输出一次，汇合任务必须最后出现。再加入多个独立子图、单节点、自依赖，以及全部节点都在环内的输入。

对同一张图，用不同顺序插入字典，再反转各依赖数组，结果应完全一致。这里的确定性来自显式排序，而不是反复运行后“看起来一直一样”。不要把一次恰巧正确的字典遍历当成接口保证。

不要把阻塞集合误报为环成员

示例里的 a 与 b 相互依赖，report 只是依赖 b，却同样无法被释放。因此错误名称使用 blocked，而不是宣称所有残留任务都在环内。

排障时保留哪些证据

失败报告保留原始图、稳定排序后的阻塞集合、提交标识与工具链版本即可。若需要在界面精确标红环成员，再增加强连通分量分析；不要仅凭入度仍大于零就画出“循环路径”。

有环时，即使部分独立任务已经排出顺序，整个规划仍应失败。除非产品明确支持部分执行，否则不能把前半段结果当成完整计划交给执行器。

接进流水线时守住调度边界

先在云端 Mac 上执行图检查，再进入耗时的构建步骤。保留非零退出码，让依赖配置错误在分钟级任务启动前暴露，而不是等执行器挂起后才发现。

这份实现每轮重新排序就绪数组，适合规模有限的应用任务图；节点数量增长后，可换成最小堆，但要保持同样的字典序契约，并复用现有测试比较结果。

真正并行执行时，只有前置任务成功完成才能减少后继任务的未完成计数。失败、取消与重试需要单独状态，不能靠拓扑序下标推导。最终验收应同时满足：输入异常可解释、合法图顺序稳定、执行器不提前释放依赖。这样换到另一台构建节点，也不会把偶然顺序带进发布流程。

常见问题