Планировщик сборки на топологической сортировке

До любой сортировки реши, что такое граф задач и какие операции он должен поддерживать. Граф сборки — это направленный ациклический граф (DAG): узлы — задачи, рёбра кодируют «A должна завершиться до B» (a→b означает, что A — предусловие B). Представление важно: список смежности по набору узлов масштабируется лучше матрицы для разреженных графов сборки (большинство задач зависят от нескольких других, а не от каждой). Смоделируй две вспомогательные структуры, которые тебе понадобятся в каждом последующем этапе: карту in-degree (сколько предусловий у каждой задачи ещё не выполнено?) и список смежности (для завершённой задачи, какие задачи она разблокирует?). Обе должны вычисляться за O(V+E). Изолированные узлы — задачи без зависимостей и без зависимых — валидны и не должны молча отбрасываться. Предоставь чистый конструктор, принимающий узлы как массив строк и рёбра как пары [предшественник, преемник], валидирующий, что каждый конец ребра — объявленный узел, и бросающий при неизвестных концах.

Реализуй алгоритм Кана: засей очередь всеми узлами с нулевым in-degree, многократно извлекай узел в результат и уменьшай in-degree его преемников — если преемник достигает нуля, добавь его в очередь. Это O(V+E) и итеративно, без риска переполнения стека рекурсии. Ключевой момент: этот алгоритм по сути недетерминирован, когда несколько узлов одновременно подходят (нулевой in-degree): в реальной системе сборки недетерминизм означает, что повторные сборки дают разный порядок, кэширование ломается, а CI не воспроизводим. Исправь это, используя min-heap или лексикографически сортируя кандидатов с нулевым in-degree перед обработкой — порядок стабилен, дёшев (дополнительно O(k log k) за шаг, где k — количество ничьих) и делает вывод чистой функцией от графа. Результат должен содержать каждый узел ровно один раз, включая изолированные.

Алгоритм Кана даёт обнаружение циклов бесплатно: если результат после обработки всех узлов с нулевым in-degree содержит меньше узлов, чем ввод, существует хотя бы один цикл — узлы, отсутствующие в результате, — это именно те, что застряли в цикле (все их предшественники тоже были в циклах, поэтому их in-degree никогда не достигал нуля). Это существенное преимущество перед обнаружением на основе DFS: ты получаешь узлы цикла без дополнительных затрат. Но «цикл обнаружен» — это не полезная ошибка. Система сборки должна сообщать оператору, какие задачи взаимно блокируют друг друга, поэтому CycleError должен раскрывать набор узлов, участвующих в цикле, а не просто булево значение. Для самопетли (a→a) сообщение должно называть этот узел; для двухузлового цикла (a→b→a) должны присутствовать оба. Сделай CycleError типизированным классом, расширяющим Error, с полем cycleNodes, экспортируй его, чтобы вызывающие могли проверить instanceof и извлечь цикл для отображения.

Детерминизм — это не свойство, которое ты предполагаешь, а свойство, которое ты доказываешь тестом, утверждающим точный вывод для известного графа. Выбери нетривиальный граф (не менее 6 узлов, не менее 2 ситуаций разрешения ничьей), вычисли ожидаемый топологический порядок вручную с использованием твоего правила лексикографической ничьей и напиши тест, жёстко кодирующий этот ожидаемый массив. Если вывод меняется — тест падает. Это дисциплинирует будущие рефакторы: если ты меняешь правило ничьей, ты должен обновить ожидаемый вывод, что заставляет тебя думать, не нарушает ли изменение воспроизводимость. Также протестируй грань самого правила ничьей: для узлов ['c','a','b'] без рёбер сортировка должна вернуть ['a','b','c'], а не порядок вставки. Задокументируй правило ничьей в комментарии рядом с реализацией, чтобы намерение было явным и не потерялось при следующем рефакторе.

Линейный порядок — это минимум, который должен предоставлять планировщик, но реальная система сборки запускает столько задач параллельно, сколько позволяет граф. Расширение батчей алгоритма Кана даёт тебе это бесплатно: вместо того чтобы добавлять в очередь узлы с нулевым in-degree по одному, собирай все узлы, у которых in-degree достигает нуля в одном раунде, в один батч — этот батч и есть набор задач, которые можно запускать параллельно на этом уровне. Обрабатывай каждый батч как единицу, затем уменьшай in-degree, собирай следующий батч и повторяй. Результат — список батчей (массивов строк), где задачи внутри батча не зависят друг от друга, а каждая задача в батче k+1 зависит хотя бы от одной задачи в батчах 1…k. Это волновая / уровневая синхронная модель, используемая make -j и большинством CI-движков. Докажи это: две задачи без пути между ними должны попасть в один батч; задача, зависящая от одной из них, должна попасть в строго более поздний батч.

Алгоритм доказан; теперь сделай его полезным инструментом. Собери тонкий раннер, принимающий манифест задач (JSON, отображающий имена задач на массивы команд и имена зависимостей), разрешающий порядок выполнения через topoSort, диспетчеризирующий каждый батч конкурентно (Promise.all по батчу) и стримящий структурированный JSON-вывод на задачу (name, status, stdout, durationMs). Раннер должен отклонять манифест и показывать читаемую ошибку, если topoSort бросает CycleError — называя цикл, чтобы оператор мог исправить манифест без чтения стек-трейсов. Он также должен валидировать, что каждое имя зависимости в манифесте ссылается на объявленную задачу (неизвестная зависимость = завершить сразу при загрузке, а не во время выполнения). Сделай раннер тестируемым, инжектируя функцию-исполнитель (то, что реально запускает shell-команду), чтобы тесты могли проверять поведение планировщика без порождения реальных процессов. Замерь выигрыш по wall-clock времени батчевого раннера против последовательного на синтетическом алмазном графе из 20 задач.