Doing Things in a Possible Order

Last timeWhen Some Links Cost More

An order that respects every dependency comes out of either walk, no such order exists exactly when there is a cycle, and the same question is answered by every build tool.

The question every build tool asks

Twelve things have to be done. Some cannot start until others have finished.

Produce an order in which all of them can be done.

That is a build, a database migration sequence, a course prerequisite list, a

deployment with services that depend on each other, and the resolution of a

package's dependencies. In every case the dependencies form a directed graph,

a link from the thing depended on to the thing depending on it, and the

question is an order of the points in which every link points forwards.

The requirement is weaker than it first sounds. Nothing says which valid order

to produce, and nothing says that two unrelated things must be in any

particular order. All that is required is that each item comes after

everything it depends upon.

FIG 1A valid order, and what it does and does not fix

The first span is forced by the dependencies and the second is not. An order that swapped the library and the tool would be just as valid. That freedom is not a defect in the answer; the final section is about what it is worth.

Peeling off what is ready

Here is the method. For each item, count how many things it is still waiting

for. Anything whose count is zero is ready now. Take any ready item, put it

next in the order, and reduce the count of everything that was waiting on it,

since it has now been done. Anything whose count falls to zero joins the ready

set. Repeat until nothing is ready.

No searching happens anywhere in that. The counts are built in one pass over

the links, and after that every step is an addition and a comparison.

FIG 2Peeling a small build apart

step	step	ready now	taken	counts reduced	the order so far
1	1	fetch	fetch	library 0, tool 0	fetch
2	2	library, tool	library	tests 1, package 1	fetch, library
3	3	tool	tool	tests 0, package 1	fetch, library, tool
4	4	tests	tests	package 0	fetch, library, tool, tests
5	5	package	package	nothing	all five, in a valid order

5 steps

At step two there were two ready items and either could have been taken, which is where the alternative orders come from. The counts do all the work: nothing is ever searched for, and an item becomes ready the instant its last dependency is removed.

Why a cycle is the only thing that can go wrong

Suppose the method stops with items left over. Every remaining item has a

count above zero, meaning each is waiting on something that is also still

remaining. Follow that: from any leftover item, step to something it is

waiting on, and again, and again. There are finitely many items, so eventually

a repeat occurs, and a repeat is a cycle.

So the method cannot stall for any reason other than a loop. That gives a

clean statement: a valid order exists exactly when the graph has no cycle, and

the peeling method both produces the order and demonstrates the loop,

depending on which happens.

The lesson stops here

2 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents