Pipeline Stage Ordering
20 min
A CI/CD pipeline is a set of stages (build, test, lint, deploy...) with
dependencies between them — deploy can't run until both test and
lint pass, and neither of those can run until build produces
something to test. This is exactly the same shape as Algorithms'
graph-algorithms topological sort: given a directed acyclic graph of
"must come before" constraints, find a valid linear order.
def topological_order(stages):
visited = set()
order = []
def visit(stage):
if stage in visited:
return
visited.add(stage)
for dep in stages.get(stage, []):
visit(dep)
order.append(stage)
for stage in stages:
visit(stage)
return order
This recurses into a stage's DEPENDENCIES before appending the stage itself to order -- a dependency can never be appended after something that needs it, because by the time a stage gets appended, every one of its dependencies has already fully recursed and appended first.
Write `topological_order(stages)`: `stages` maps each stage name to a list of stages it depends on. Return a valid execution order where every stage appears AFTER all of its dependencies.
Why is a CI/CD pipeline's stage-dependency graph fundamentally the same problem as Algorithms' topological-sort module?
You can compute a valid pipeline execution order from a stage-dependency graph via topological sort — the same algorithm behind git bisect-style dependency resolution and build systems generally.