Build.Scheduler

Build schedulers execute task rebuilders in the right order.

Documentation

topological :: Ord k => Rebuilder Applicative i k v -> Build Applicative i k v

This scheduler constructs the dependency graph of the target key by extracting all (static) dependencies upfront, and then traversing the graph in the topological order, rebuilding keys using the supplied rebuilder.

reordering :: forall i k v. Ord k => Rebuilder Monad i k v -> Build Monad (i, Chain k) k v

A model of the scheduler used by Excel, which builds keys in the order used in the previous build. If a key cannot be build because its dependencies have changed and a new dependency is still dirty, the corresponding build task is abandoned and the key is moved at the end of the calculation chain, so it can be restarted when all its dependencies are up to date.

type Chain k = [k]

The so-called calculation chain: the order in which keys were built during the previous build, which is used as the best guess for the current build by Excel and other similar build systems.

restarting :: forall i k v. Eq k => IsDirty i k v -> Rebuilder Monad i k v -> Build Monad i k v

A model of the scheduler used by Bazel. We extract a key K from the queue and try to build it. There are now two cases: 1. The build fails because one of the dependencies of K is dirty. In this case we add the dirty dependency to the queue, listing K as blocked by it. 2. The build succeeds, in which case we add all keys that were previously blocked by K to the queue.

recursive :: forall i k v. Ord k => Rebuilder Monad i k v -> Build Monad i k v

This scheduler builds keys recursively: to build a key it first makes sure that all its dependencies are up to date and then executes the key's task. It stores the set of keys that have already been built as part of the state to avoid executing the same task twice.

independent :: forall i k v. Eq k => Rebuilder Monad i k v -> Build Monad i k v

An incorrect scheduler that builds the target key without respecting its dependencies. It produces the correct result only if all dependencies of the target key are up to date.