e3cf872e

By: Tom Sydney Kerckhove <syd@cs-syd.eu>

Report each dependency edge as soon as it is known

Edges were worked out only once every job had been discovered, so a
consumer heard nothing about them until the run was nearly over. On this
repository's own flake the first edge arrived 22.4s in, after the last job
at 22.0s; it now arrives at 16.9s, four seconds before discovery finishes.

An edge is final the moment both of its ends are known, so waiting for the
rest of an output's closure only delayed reporting something that could not
change. The walk now runs in the coordinator's loop, in the time it spends
waiting on workers, and each edge goes out as it is found. Total run time is
unchanged.

The cost is that an attribute can now appear in several dependency lines,
each naming some of what it depends on, so a consumer takes their union
rather than the last line it saw. The union is identical to what a run used
to report in one line.

The traversal is a state machine that names the path whose references it
needs and is told the answer, so it is driven from the loop and tested
against a fixed graph without a store. The tests cover an output discovered
after the walks already passed through its derivation, which a design that
only looked forwards would silently lose.

Timeline