Проверка графа зависимостей iOS на облачном Mac

Локально набор задач обработки ресурсов выполняется в ожидаемом порядке, но после переноса в конвейер на облачном Mac иногда сначала создаётся индекс, а уже затем — ресурсы. Причина не обязательно в машине: если порядок задач определяется обходом словаря или постановка в очередь ошибочно считается завершением зависимости, ошибка может проявиться уже при следующем запуске процесса. Ниже проверим граф зависимостей отдельным скриптом Swift — запускать симулятор для этого не нужно.

Сначала определите направление рёбер и условия отказа

Заданный вручную порядок подходит для короткого и неизменного процесса. Граф зависимостей полезен, когда задачи добавляются и удаляются, а нескольким шагам нужны общие предварительные операции. Если вся работа изначально выполняется последовательно, граф лишь усложнит сопровождение.

В этой статье входные данные представлены как «имя задачи → множество задач-предшественников». Например, если index зависит от assets, то в результате 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 и лишь затем переходите к длительным шагам сборки. Сохраняйте ненулевой код завершения, чтобы ошибки в конфигурации зависимостей обнаруживались до запуска задач длительностью в несколько минут, а не после зависания исполнителя.

В этой реализации массив готовых задач сортируется заново на каждом шаге. Это подходит для графов задач приложения ограниченного размера. При росте числа узлов массив можно заменить минимальной кучей, сохранив тот же контракт лексикографического порядка и проверив совпадение результатов существующими тестами.

При реальном параллельном выполнении уменьшать счётчик незавершённых зависимостей последующих задач можно только после успешного завершения предшественника. Для ошибок, отмены и повторных попыток нужны отдельные состояния — их нельзя выводить из позиции в топологическом порядке. Итоговая проверка должна одновременно подтверждать три условия: ошибки входных данных объяснимы, порядок для корректного графа воспроизводим, а исполнитель не считает зависимости выполненными раньше времени. Тогда перенос на другой сборочный узел не внесёт случайный порядок в процесс выпуска.

Часто задаваемые вопросы