Enable early cutoff optimization

[zombiezen]

Build systems à la carte describes the early cutoff optimization as:

When [a build system] executes a task and the result is unchanged from the previous build, it is unnecessary to execute the dependent tasks, and hence [a build system] can stop a build earlier [...]

Nix's experimental content addressability feature achieves this by "resolving" a derivation into only depending on the built sources. While this has the intended effect, it loses the dependency information in the process and is IMO confusing to describe to users.

For zb, I want to key realizations on this "resolved" hash. I'm not exactly sure how to reconcile this with Nix Intensional Model. I believe this may just be a matter of redefining hashDrv to use the derivation's inputs' realized content addresses.

[Ericson2314]

Hash derivations based on their realized inputs.

As it turns out, this simplifies the process even more because we can find realizations as we walk up the tree.

I added hooks for using realizations that aren't in the store yet, which is useful once substituters are in play, but aren't necessary for the introducing the early cutoff optimization.

Does this mean you don't need to hash derivations until the content-addresses of their inputs are already known?

[zombiezen]

Correct, code for that is here: https://github.com/256lights/zb/blob/af1a43b55217b2021660aa4779aa1d9ef09ff77d/internal/backend/equivalence_class.go#L49-L65

I do use a "pseudo-hash" as a heuristic early on to identify potential multi-output derivations that are used within the build graph, but other than that, hashes are computed lazily. It's pretty similar: https://github.com/256lights/zb/blob/af1a43b55217b2021660aa4779aa1d9ef09ff77d/internal/backend/equivalence_class.go#L67-L109