Valider un graphe de dépendances iOS sur un Mac distant

Un même traitement de ressources s’exécute dans le bon ordre en local, mais, une fois intégré au pipeline d’un Mac distant, il produit parfois l’index avant les ressources. La machine n’est pas forcément en cause : si l’ordre des tâches dépend du parcours d’un dictionnaire, ou si « déjà mise en file » est confondu avec « dépendance terminée », il suffit de relancer le traitement dans un autre processus pour révéler le défaut. Voici comment valider le graphe de dépendances avec un script Swift autonome, sans démarrer le simulateur.

Définir le sens des arcs et les conditions d’échec

Un ordre défini à la main convient à un enchaînement court et fixe. Un graphe de dépendances est plus adapté lorsque des tâches sont ajoutées ou supprimées, ou lorsque plusieurs étapes partagent des prérequis. Si tout le travail est déjà strictement séquentiel, introduire un graphe ne fait qu’alourdir la maintenance.

Dans cet article, l’entrée prend la forme « nom de la tâche → ensemble des tâches prérequises ». Par exemple, si index dépend de assets, cette dernière doit apparaître en premier dans le résultat. Les noms de tâches sont des identifiants stables, indépendants de la langue d’affichage. Les tâches sans dépendance entre elles sont sélectionnées selon l’ordre lexicographique de leur identifiant.

Le contrat d’entrée doit aussi préciser trois règles : les arcs en double sont fusionnés, une dépendance inconnue provoque un échec immédiat et une tâche qui dépend d’elle-même constitue un cycle. Un graphe vide est valide et renvoie un tableau vide. Ne créez pas implicitement les nœuds inconnus : une faute de frappe dans un nom serait alors acceptée comme une entrée valide.

Le tri prouve uniquement que les dépendances peuvent être organisées en une séquence valide. Il ne prouve ni que les tâches sont terminées ni que leurs résultats sont corrects. L’état d’exécution et la structure du graphe doivent être validés séparément.

Implémenter un tri stable et exécutable

Enregistrez le contenu suivant dans graph-check.swift, dans le répertoire de travail du nœud. Le code ne dépend que de la bibliothèque standard Swift et s’exécute avec la chaîne d’outils actuellement sélectionnée, sans paquet supplémentaire. L’algorithme suit le nombre de dépendances encore non satisfaites pour chaque tâche et sélectionne, à chaque tour, la tâche prête dont le nom vient en premier dans l’ordre lexicographique.

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

Si la validation réussit, le script n’affiche rien. En cas d’échec, le processus renvoie un code de sortie non nul. N’exécutez pas ce script de validation avec un mode d’optimisation qui désactive les vérifications de précondition. Après intégration au projet, vous pouvez déplacer les mêmes assertions dans une cible de test dédiée, afin que les réglages de compilation du code applicatif n’influencent pas les vérifications.

Compléter les exemples par des assertions de propriétés

Un résultat attendu fixe permet de repérer une dérive de l’ordre, mais il peut aussi entériner une implémentation erronée. Le code vérifie donc également le nombre d’éléments en sortie, l’ensemble des nœuds et l’ordre imposé par chaque arc. Ces trois catégories de contrôles servent respectivement à empêcher les omissions, les doublons et les inversions de dépendances.

Ajoutez ensuite un graphe en losange : deux tâches dépendent d’une même racine, puis une dernière tâche dépend de ces deux tâches. La racine ne doit apparaître qu’une fois dans le résultat, et la tâche de convergence doit être la dernière. Ajoutez aussi des entrées comprenant plusieurs sous-graphes indépendants, un seul nœud, une dépendance à soi-même et un graphe dont tous les nœuds appartiennent à des cycles.

Pour un même graphe, insérez les entrées du dictionnaire dans des ordres différents, puis inversez chaque tableau de dépendances : le résultat doit rester strictement identique. Le déterminisme vient ici du tri explicite, pas du fait que des exécutions répétées « semblent toujours donner la même chose ». Un parcours de dictionnaire qui produit par hasard le bon ordre ne constitue pas une garantie de l’interface.

Ne pas confondre tâches bloquées et membres d’un cycle

Dans l’exemple, a et b dépendent l’une de l’autre. report dépend seulement de b, mais ne peut pas non plus être débloquée. L’erreur s’appelle donc blocked, sans prétendre que toutes les tâches restantes appartiennent à un cycle.

Quelles preuves conserver pour le diagnostic ?

Le rapport d’échec doit simplement conserver le graphe d’origine, l’ensemble des tâches bloquées trié de manière stable, l’identifiant du commit et la version de la chaîne d’outils. Si l’interface doit mettre précisément en rouge les membres des cycles, ajoutez une analyse des composantes fortement connexes. Ne tracez pas un « chemin cyclique » au seul motif que certains nœuds ont encore un degré entrant supérieur à zéro.

En présence d’un cycle, la planification entière doit échouer, même si certaines tâches indépendantes ont déjà été ordonnées. Sauf si le produit prend explicitement en charge une exécution partielle, le début du résultat ne doit pas être transmis à l’exécuteur comme s’il s’agissait d’un plan complet.

Respecter la frontière entre planification et exécution dans le pipeline

Exécutez d’abord la vérification du graphe sur le Mac distant, avant de lancer les étapes de compilation coûteuses. Préservez le code de sortie non nul afin de détecter une erreur de configuration des dépendances avant le démarrage de tâches qui durent plusieurs minutes, plutôt qu’une fois l’exécuteur bloqué.

Cette implémentation trie à nouveau le tableau des tâches prêtes à chaque tour. Elle convient aux graphes de tâches applicatives de taille limitée. Lorsque le nombre de nœuds augmente, vous pouvez remplacer ce tableau par un tas min, à condition de conserver le même contrat d’ordre lexicographique et de réutiliser les tests existants pour comparer les résultats.

Lors d’une véritable exécution parallèle, le compteur de dépendances non satisfaites d’une tâche suivante ne doit diminuer qu’après la réussite d’une tâche prérequise. Les échecs, les annulations et les nouvelles tentatives exigent des états distincts : ils ne peuvent pas être déduits de l’indice dans l’ordre topologique. La validation finale doit réunir trois garanties : les entrées invalides produisent des erreurs explicables, les graphes valides donnent un ordre stable et l’exécuteur ne considère pas les dépendances comme satisfaites trop tôt. Ainsi, un changement de nœud de compilation ne fera pas entrer un ordre accidentel dans le processus de livraison.

Questions fréquentes