iOS-Abhängigkeitsgraphen auf dem Cloud-Mac prüfen

Dieselben Verarbeitungsschritte für Ressourcen laufen lokal wie erwartet. Nach dem Umzug in die Pipeline auf einem Cloud-Mac wird jedoch gelegentlich zuerst der Index und erst danach werden die Ressourcen erzeugt. Das muss nicht an der Maschine liegen: Wenn die Aufgabenreihenfolge von der Iteration über ein Dictionary abhängt oder „bereits eingereiht“ mit „Abhängigkeit bereits abgeschlossen“ verwechselt wird, kann schon ein neuer Prozess den Fehler sichtbar machen. Im Folgenden prüfen wir den Abhängigkeitsgraphen mit einem eigenständigen Swift-Skript, ohne vorher einen Simulator starten zu müssen.

Kantenrichtung und Fehlerverhalten zuerst festlegen

Eine von Hand festgelegte Reihenfolge eignet sich für kurze, unveränderliche Abläufe. Ein Abhängigkeitsgraph ist sinnvoll, wenn Aufgaben hinzukommen oder wegfallen und mehrere Schritte gemeinsame Voraussetzungen haben. Läuft ohnehin alles linear ab, erhöht ein Graph nur den Wartungsaufwand.

Als Eingabe verwenden wir hier „Aufgabenname → Menge der vorausgesetzten Aufgaben“. Hängt beispielsweise index von assets ab, muss assets in der Ausgabe zuerst erscheinen. Aufgabennamen dienen als stabile Kennungen und ändern sich nicht mit der Anzeigesprache. Unter voneinander unabhängigen Aufgaben wird anhand dieser Kennungen lexikografisch ausgewählt.

Für die Eingabe gelten außerdem drei Regeln: Doppelte Kanten werden zusammengeführt, unbekannte Abhängigkeiten führen sofort zum Fehler, und eine Abhängigkeit von sich selbst gilt als Zyklus. Ein leerer Graph ist zulässig und liefert ein leeres Array. Unbekannte Knoten dürfen nicht stillschweigend angelegt werden, sonst würden auch Tippfehler in Namen als gültige Eingabe durchgehen.

Die Sortierung zeigt lediglich, ob sich die Abhängigkeiten in eine gültige Reihenfolge bringen lassen. Sie belegt weder, dass Aufgaben abgeschlossen sind, noch, dass ihre Ergebnisse stimmen. Ausführungszustand und Graphstruktur müssen getrennt geprüft werden.

Einen ausführbaren, deterministischen Sortierer implementieren

Speichern Sie den folgenden Inhalt im Arbeitsverzeichnis des Knotens als graph-check.swift. Der Code benötigt nur die Swift-Standardbibliothek und lässt sich mit der aktuell ausgewählten Toolchain ausführen. Zusätzliche Pakete sind nicht erforderlich. Der Algorithmus verwaltet für jede Aufgabe die Anzahl noch nicht erfüllter Abhängigkeiten und wählt in jedem Durchlauf die bereite Aufgabe mit dem lexikografisch kleinsten Namen.

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

Bei erfolgreicher Prüfung gibt es keine Ausgabe; bei einem Fehler beendet sich der Prozess mit einem Exitcode ungleich null. Führen Sie dieses Prüfskript nicht in einem Optimierungsmodus aus, der die Prüfungen mit precondition deaktiviert. Nach der Einbindung ins Projekt können dieselben Zusicherungen in ein reguläres Test-Target übernommen werden, damit die Build-Einstellungen der Anwendung das Prüfverhalten nicht beeinflussen.

Lücken der Testbeispiele durch Eigenschaftsprüfungen schließen

Ein fest vorgegebenes Ergebnis erkennt Änderungen der Reihenfolge, kann aber auch das Ergebnis einer fehlerhaften Implementierung als Sollzustand festschreiben. Deshalb prüft der Code zusätzlich die Anzahl der ausgegebenen Knoten, die Knotenmenge und die Reihenfolge an jeder Kante. Diese drei Prüfungen verhindern fehlende oder doppelte Knoten sowie umgekehrte Abhängigkeiten.

Ergänzen Sie als Nächstes einen rautenförmigen Graphen: Zwei Aufgaben hängen von derselben Wurzel ab, eine abschließende Aufgabe wiederum von diesen beiden Aufgaben. Die Wurzel darf nur einmal ausgegeben werden, und die zusammenführende Aufgabe muss zuletzt erscheinen. Nehmen Sie außerdem mehrere unabhängige Teilgraphen, einen einzelnen Knoten, eine Selbstabhängigkeit und eine Eingabe auf, bei der alle Knoten in Zyklen liegen.

Fügen Sie denselben Graphen in unterschiedlicher Reihenfolge in das Dictionary ein und kehren Sie anschließend auch die Reihenfolge in allen Abhängigkeitsarrays um. Das Ergebnis muss exakt gleich bleiben. Die Deterministik entsteht hier durch explizites Sortieren, nicht dadurch, dass es nach mehreren Durchläufen „immer gleich aussieht“. Eine zufällig passende Dictionary-Iteration ist keine Schnittstellengarantie.

Blockierte Knoten nicht fälschlich als Zyklusknoten melden

Im Beispiel hängen a und b voneinander ab. report hängt lediglich von b ab, kann aber ebenfalls nicht freigegeben werden. Deshalb heißt der Fehler blocked, statt zu behaupten, alle verbleibenden Aufgaben seien Teil eines Zyklus.

Welche Nachweise zur Fehleranalyse aufbewahrt werden sollten

Für den Fehlerbericht genügen der ursprüngliche Graph, die lexikografisch sortierte Menge der blockierten Knoten, die Commit-Kennung und die Toolchain-Version. Sollen in einer Oberfläche genau die Zyklusknoten rot markiert werden, ergänzen Sie eine Analyse der starken Zusammenhangskomponenten. Zeichnen Sie keinen „Zykluspfad“ allein deshalb ein, weil der Eingangsgrad noch größer als null ist.

Enthält der Graph einen Zyklus, muss die gesamte Planung fehlschlagen, selbst wenn einige unabhängige Aufgaben bereits einsortiert wurden. Sofern das Produkt eine teilweise Ausführung nicht ausdrücklich unterstützt, darf dieses Teilergebnis nicht als vollständiger Plan an die Ausführungskomponente übergeben werden.

Bei der Pipeline-Integration die Grenze zur Ausführungssteuerung wahren

Führen Sie auf dem Cloud-Mac zuerst die Graphprüfung aus und starten Sie erst danach die zeitaufwendigen Build-Schritte. Reichen Sie den Exitcode ungleich null unverändert weiter. So werden Fehler in der Abhängigkeitskonfiguration sichtbar, bevor minutenlange Aufgaben anlaufen, statt erst dann, wenn die Ausführung feststeckt.

Diese Implementierung sortiert das Array der bereiten Aufgaben in jedem Durchlauf neu und eignet sich für überschaubare Aufgabengraphen einer Anwendung. Wächst die Knotenzahl, kann ein Min-Heap das Array ersetzen. Dabei muss dieselbe lexikografische Auswahlregel erhalten bleiben; die vorhandenen Tests sollten zum Ergebnisvergleich weiterverwendet werden.

Bei tatsächlich paralleler Ausführung darf die Anzahl offener Abhängigkeiten einer nachfolgenden Aufgabe erst sinken, wenn die vorausgesetzte Aufgabe erfolgreich abgeschlossen wurde. Fehler, Abbrüche und Wiederholungsversuche benötigen eigene Zustände; sie lassen sich nicht aus dem Index in der topologischen Reihenfolge ableiten. Die abschließende Prüfung muss alle drei Anforderungen erfüllen: Ungültige Eingaben sind nachvollziehbar, gültige Graphen liefern eine deterministische Reihenfolge, und die Ausführungskomponente gibt nachfolgende Aufgaben nicht vorzeitig frei. So gelangt auch beim Wechsel auf einen anderen Build-Knoten keine zufällige Reihenfolge in den Release-Prozess.

Häufig gestellte Fragen