-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Build systems a la carte
--
-- A library for experimenting with build systems and incremental
-- computation frameworks, based on the ideas presented in the ICFP 2018
-- paper "Build Systems a la Carte".
@package build
@version 1.0
-- | An abstract key/value store.
module Build.Store
-- | A Hash is used for efficient tracking and sharing of build
-- results. We use newtype Hash a = Hash a for prototyping.
data Hash a
class Ord a => Hashable a
-- | Compute the hash of a given value. We typically assume cryptographic
-- hashing, e.g. SHA256.
hash :: Hashable a => a -> Hash a
-- | An abstract datatype for a key/value store with build information of
-- type i.
data Store i k v
-- | Read the value of a key.
getValue :: k -> Store i k v -> v
-- | Update the value of a key.
putValue :: Eq k => k -> v -> Store i k v -> Store i k v
-- | Read the hash of a key's value. In some cases may be implemented more
-- efficiently than hash . getValue k.
getHash :: Hashable v => k -> Store i k v -> Hash v
-- | Read the build information.
getInfo :: Store i k v -> i
-- | Write the build information.
putInfo :: i -> Store i k v -> Store i k v
-- | Modify the build information.
mapInfo :: (i -> j) -> Store i k v -> Store j k v
-- | Initialise the store.
initialise :: i -> (k -> v) -> Store i k v
instance GHC.Show.Show a => GHC.Show.Show (Build.Store.Hash a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Build.Store.Hash a)
instance GHC.Classes.Eq a => GHC.Classes.Eq (Build.Store.Hash a)
instance Build.Store.Hashable GHC.Types.Int
instance Build.Store.Hashable GHC.Integer.Type.Integer
instance Build.Store.Hashable a => Build.Store.Hashable [a]
instance Build.Store.Hashable a => Build.Store.Hashable (Build.Store.Hash a)
instance (Build.Store.Hashable a, Build.Store.Hashable b) => Build.Store.Hashable (a, b)
instance GHC.Base.Functor Build.Store.Hash
instance GHC.Base.Applicative Build.Store.Hash
-- | The Task abstractions.
module Build.Task
-- | A Task is used to compute a value of type v, by
-- finding the necessary dependencies using the provided fetch :: k
-- -> f v callback.
newtype Task c k v
Task :: forall f. c f => (k -> f v) -> f v -> Task c k v
[run] :: Task c k v -> forall f. c f => (k -> f v) -> f v
-- | Tasks associates a Task with every non-input key.
-- Nothing indicates that the key is an input.
type Tasks c k v = k -> Maybe (Task c k v)
-- | Compose two task descriptions, preferring the first one in case there
-- are two tasks corresponding to the same key.
compose :: Tasks Monad k v -> Tasks Monad k v -> Tasks Monad k v
-- | Lift an applicative task to Task Monad. Use this function
-- when applying monadic task combinators to applicative tasks.
liftTask :: Task Applicative k v -> Task Monad k v
-- | Lift a collection of applicative tasks to Tasks Monad. Use
-- this function when building applicative tasks with a monadic build
-- system.
liftTasks :: Tasks Applicative k v -> Tasks Monad k v
-- | This module defines two different strategies of self-tracking, based
-- around the idea of storing task descriptions that can be parsed into a
-- Task.
--
--
--
For Monad it works out beautifully. You just store the rule
-- on the disk, and depend on it.
--
For Applicative, we generate a fresh Task each time,
-- but have that Task depend on a fake version of the rules. This
-- is a change in the Task, but it's one for which the standard
-- implementations tend to cope with just fine. Most applicative systems
-- with self-tracking probably do it this way.
--
module Build.SelfTracking
-- | We assume that the fetch passed to a Task is consistent and returns
-- values matching the keys. It is possible to switch to typed tasks to
-- check this assumption at compile time, e.g. see
-- Build.Task.Typed.
data Key k
Key :: k -> Key k
KeyTask :: k -> Key k
data Value v t
Value :: v -> Value v t
ValueTask :: t -> Value v t
-- | A model for Monad, works beautifully and allows storing the key
-- on the disk.
selfTrackingM :: forall k v t. (t -> Task Monad k v) -> Tasks Monad k t -> Tasks Monad (Key k) (Value v t)
-- | The applicative model requires every key to be able to associate with
-- its environment (e.g. a reader somewhere). Does not support cutoff if
-- a key changes.
selfTrackingA :: (t -> Task Applicative k v) -> (k -> t) -> Tasks Applicative (Key k) (Value v t)
-- | Support for multiple-output tasks.
module Build.Multi
-- | Defines a set partition. For a function to be a valid partition, if
-- f k == ks, then:
--
--
--
k in ks
--
forall i in ks . f i == ks
--
type Partition k = k -> [k]
-- | Given a task description with individual multiple-output keys, compute
-- its "closure" supporting all possible combinations of keys.
multi :: Eq k => Partition k -> Tasks Applicative [k] [v] -> Tasks Applicative [k] [v]
-- | Applicative tasks, as used by Make, Ninja and other applicative build
-- systems. Dependencies of applicative tasks are known statically,
-- before their execution.
module Build.Task.Applicative
-- | Find the dependencies of an applicative task.
dependencies :: Task Applicative k v -> [k]
-- | Functorial tasks, which have exactly one statically known dependency.
-- Docker is an example of a functorial build system: Docker containers
-- are organised in layers, where each layer makes changes to the
-- previous one.
module Build.Task.Functor
-- | Find the dependency of a functorial task.
dependency :: Task Functor k v -> k
-- | Monadic tasks, as used by Excel, Shake and other build systems.
-- Dependencies of monadic tasks can only be discovered dynamically, i.e.
-- during their execution.
module Build.Task.Monad
-- | Execute a monadic task using an effectful fetch function k -> m
-- v, tracking the dependencies.
track :: forall m k v. Monad m => Task Monad k v -> (k -> m v) -> m (v, [(k, v)])
-- | Execute a monadic task on a pure store k -> v, tracking
-- the dependencies.
trackPure :: Task Monad k v -> (k -> v) -> (v, [k])
-- | Given a description of tasks, check if a key is input.
isInput :: Tasks Monad k v -> k -> Bool
-- | Run a task with a pure lookup function.
computePure :: Task Monad k v -> (k -> v) -> v
-- | Run a task in a given store.
compute :: Task Monad k v -> Store i k v -> v
-- | Convert a task with a total lookup function k -> m v into
-- a task with a partial lookup function k -> m (Maybe v).
-- This essentially lifts the task from the type of values v to
-- Maybe v, where the result Nothing indicates that the
-- task failed because of a missing dependency.
partial :: Task Monad k v -> Task Monad k (Maybe v)
-- | Convert a task with a total lookup function k -> m v into
-- a task with a lookup function that can throw exceptions k -> m
-- (Either e v). This essentially lifts the task from the type of
-- values v to Either e v, where the result Left
-- e indicates that the task failed because of a failed dependency
-- lookup, and Right v yeilds the value otherwise.
exceptional :: Task Monad k v -> Task Monad k (Either e v)
-- | A version of monadic tasks with some support for non-determinism.
module Build.Task.MonadPlus
-- | An example of a non-deterministic task: generate a random number from
-- a specified interval.
random :: (Int, Int) -> Task MonadPlus k Int
-- | Run a task in a given store.
computeND :: Task MonadPlus k v -> Store i k v -> [v]
-- | Given a description of tasks, an initial store, and
-- a result produced by running a build system on a target
-- key, this function returns True if the key's
-- value is a possible result of running the associated task.
correctBuildValue :: Eq v => Tasks MonadPlus k v -> Store i k v -> Store i k v -> k -> Bool
-- | A model of polymorphic tasks, where the value type depends on the key.
-- See the source for an example.
module Build.Task.Typed
-- | A typed build task.
type Task c k = forall f. c f => (forall k. Key k => k -> f (Value k)) -> k -> Maybe (f (Value k))
-- | A type class for keys, equipped with an associated type family that
-- can be used to determine the type of value corresponding to the key.
class Key k where {
type family Value k :: *;
}
-- | The name of the key. Useful for avoiding heterogeneous lists of keys.
showKey :: Key k => k -> String
-- | Extract the names of dependencies.
showDependencies :: Task Applicative k -> k -> [String]
instance GHC.Show.Show (Build.Task.Typed.ExampleKey a)
instance Build.Task.Typed.Key (Build.Task.Typed.ExampleKey a)
-- | Build traces that are used for recording information from previuos
-- builds.
module Build.Trace
-- | A trace is parameterised by the types of keys k, hashes
-- h, as well as the result r. For verifying traces,
-- r = h; for constructive traces, Hash r = h.
data Trace k v r
Trace :: k -> [(k, Hash v)] -> r -> Trace k v r
[key] :: Trace k v r -> k
[depends] :: Trace k v r -> [(k, Hash v)]
[result] :: Trace k v r -> r
-- | An abstract data type for a set of verifying traces equipped with
-- recordVT, verifyVT and a Monoid instance.
data VT k v
-- | Record a new trace for building a key with dependencies
-- deps, obtaining the hashes of up-to-date values by using
-- fetchHash.
recordVT :: k -> Hash v -> [(k, Hash v)] -> VT k v -> VT k v
-- | Given a function to compute the hash of a key's current value, a
-- key, and a set of verifying traces, return True if the
-- key is up-to-date.
verifyVT :: (Monad m, Eq k, Eq v) => k -> Hash v -> (k -> m (Hash v)) -> VT k v -> m Bool
-- | An abstract data type for a set of constructive traces equipped with
-- recordCT, isDirtyCT, constructCT and a
-- Monoid instance.
data CT k v
-- | Check if a given key is dirty w.r.t a store.
isDirtyCT :: (Eq k, Hashable v) => k -> Store (CT k v) k v -> Bool
-- | Record a new trace for building a key with dependencies
-- deps, obtaining the hashes of up-to-date values by using
-- fetchHash.
recordCT :: k -> v -> [(k, Hash v)] -> CT k v -> CT k v
-- | Given a function to compute the hash of a key's current value, a
-- key, and a set of constructive traces, return Just
-- newValue if it is possible to reconstruct it from the traces.
-- Prefer reconstructing the currenct value, if it matches one of the
-- traces.
constructCT :: (Monad m, Eq k, Eq v) => k -> (k -> m (Hash v)) -> CT k v -> m [v]
-- | Our current model has the same representation as CT, but
-- requires an additional invariant: if a DCT contains a trace for a key
-- k, then it must also contain traces for each of its non-input
-- dependencies.
data DCT k v
-- | Record a new trace for building a key with dependencies
-- deps, obtaining the hashes of up-to-date values from the
-- given store.
recordDCT :: forall k v m. (Eq k, Hashable v, Monad m) => k -> v -> [k] -> (k -> m (Hash v)) -> DCT k v -> m (DCT k v)
-- | Given a function to compute the hash of a key's current value, a
-- key, and a set of deep constructive traces, return Just
-- newValue if it is possible to reconstruct it from the traces.
constructDCT :: forall k v m. (Eq k, Hashable v, Monad m) => k -> (k -> m (Hash v)) -> DCT k v -> m [v]
data Step
-- | A step trace, records the resulting value, the step it last build, the
-- step where it changed.
data ST k v
-- | Record a new trace for building a key with dependencies
-- deps.
recordST :: (Hashable v, Eq k) => Step -> k -> v -> [k] -> ST k v -> ST k v
-- | Given a function to compute the hash of a key's current value, a
-- key, and a set of verifying traces, return True if the
-- key is up-to-date.
verifyST :: (Monad m, Eq k, Hashable v) => k -> v -> (k -> m ()) -> m (ST k v) -> m Bool
instance (GHC.Show.Show k, GHC.Show.Show v) => GHC.Show.Show (Build.Trace.ST k v)
instance GHC.Base.Semigroup (Build.Trace.ST k v)
instance GHC.Base.Monoid (Build.Trace.ST k v)
instance (GHC.Show.Show k, GHC.Show.Show r) => GHC.Show.Show (Build.Trace.TraceST k r)
instance GHC.Show.Show Build.Trace.Step
instance GHC.Classes.Ord Build.Trace.Step
instance GHC.Classes.Eq Build.Trace.Step
instance GHC.Enum.Enum Build.Trace.Step
instance (GHC.Show.Show k, GHC.Show.Show v) => GHC.Show.Show (Build.Trace.DCT k v)
instance GHC.Base.Semigroup (Build.Trace.DCT k v)
instance GHC.Base.Monoid (Build.Trace.DCT k v)
instance (GHC.Show.Show k, GHC.Show.Show v) => GHC.Show.Show (Build.Trace.CT k v)
instance GHC.Base.Semigroup (Build.Trace.CT k v)
instance GHC.Base.Monoid (Build.Trace.CT k v)
instance (GHC.Show.Show k, GHC.Show.Show v) => GHC.Show.Show (Build.Trace.VT k v)
instance GHC.Base.Semigroup (Build.Trace.VT k v)
instance GHC.Base.Monoid (Build.Trace.VT k v)
instance (GHC.Show.Show k, GHC.Show.Show v, GHC.Show.Show r) => GHC.Show.Show (Build.Trace.Trace k v r)
instance GHC.Base.Semigroup Build.Trace.Step
instance GHC.Base.Monoid Build.Trace.Step
-- | Rebuilders take care of deciding whether a key needs to be rebuild and
-- running the corresponding task if need be.
module Build.Rebuilder
-- | Given a key-value pair and the corresponding task, a rebuilder returns
-- a new task that has access to the build information and can use it to
-- skip rebuilding a key if it is up to date.
type Rebuilder c i k v = k -> v -> Task c k v -> Task (MonadState i) k v
-- | Get an applicative rebuilder out of a monadic one.
adaptRebuilder :: Rebuilder Monad i k v -> Rebuilder Applicative i k v
-- | Always rebuilds the key.
perpetualRebuilder :: Rebuilder Monad () k v
-- | This rebuilder uses modification time to decide whether a key is dirty
-- and needs to be rebuilt. Used by Make.
modTimeRebuilder :: Ord k => Rebuilder Applicative (MakeInfo k) k v
type Time = Integer
type MakeInfo k = (Time, Map k Time)
-- | If the key is dirty, rebuild it. Used by Excel.
dirtyBitRebuilder :: Rebuilder Monad (k -> Bool) k v
-- | If the key is dirty, rebuild it and clear the dirty bit. Used by
-- Excel.
dirtyBitRebuilderWithCleanUp :: Ord k => Rebuilder Monad (Set k) k v
-- | This rebuilders uses approximate dependencies to decide whether a key
-- needs to be rebuilt.
approximateRebuilder :: (Ord k, Eq v) => Rebuilder Monad (ApproximationInfo k) k v
-- | If there is an entry for a key, it is an conservative approximation of
-- its dependencies. Otherwise, we have no reasonable approximation and
-- assume the key is always dirty (e.g. it uses an INDIRECT reference).
type ApproximateDependencies k = Map k [k]
-- | A set of dirty keys and information about dependencies.
type ApproximationInfo k = (Set k, ApproximateDependencies k)
-- | This rebuilder relies on verifying traces.
vtRebuilder :: (Eq k, Hashable v) => Rebuilder Monad (VT k v) k v
-- | This rebuilder relies on version/step traces.
stRebuilder :: (Eq k, Hashable v) => Rebuilder Monad (Step, ST k v) k v
-- | This rebuilder relies on constructive traces.
ctRebuilder :: (Eq k, Hashable v) => Rebuilder Monad (CT k v) k v
-- | This rebuilder relies on deep constructive traces.
dctRebuilder :: (Eq k, Hashable v) => Rebuilder Monad (DCT k v) k v
-- | Build systems and the properties they should ensure.
module Build
-- | A build system takes a description of Tasks, a target key, and
-- a store, and computes a new store, where the key and its dependencies
-- are up to date.
type Build c i k v = Tasks c k v -> k -> Store i k v -> Store i k v
-- | Given a description of tasks, an initial store, and
-- a result produced by running a build system on a target
-- key, this function returns True if the result
-- is a correct build outcome. Specifically: * result and
-- store must agree on the values of all inputs. In other words,
-- no inputs were corrupted during the build. * result is
-- consistent with the tasks, i.e. for every non-input
-- key, the result of recomputing its task matches the value stored in
-- the result.
correctBuild :: (Ord k, Eq v) => Tasks Monad k v -> Store i k v -> Store i k v -> k -> Bool
-- | Build schedulers execute task rebuilders in the right order.
module Build.Scheduler
-- | 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.
topological :: forall i k v. Ord k => Scheduler Applicative i i 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.
restarting :: forall ir k v. Ord k => Scheduler Monad (ir, Chain k) ir k v
-- | 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.
type Chain k = [k]
-- | 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.
restarting2 :: forall k v. (Hashable v, Eq k) => Scheduler Monad (CT k v) (CT k v) k v
-- | This scheduler builds keys recursively: to build a key it executes the
-- associated task, discovering its dependencies on the fly, and if one
-- of the dependencies is dirty, the task is suspended until the
-- dependency is rebuilt. It stores the set of keys that have already
-- been built as part of the state to avoid executing the same task
-- twice.
suspending :: forall i k v. Ord k => Scheduler Monad i 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.
independent :: forall i k v. Eq k => Scheduler Monad i i k v
instance GHC.Base.Monad (Build.Scheduler.Wrap i extra k v)
instance GHC.Base.Applicative (Build.Scheduler.Wrap i extra k v)
instance GHC.Base.Functor (Build.Scheduler.Wrap i extra k v)
instance Control.Monad.State.Class.MonadState i (Build.Scheduler.Wrap i extra k v)
-- | Models of several build systems.
module Build.System
-- | This is not a correct build system: given a target key, it simply
-- rebuilds it, without rebuilding any of its dependencies.
dumb :: Eq k => Build Monad () k v
-- | This is a correct but non-minimal build system: given a target key it
-- recursively rebuilds its dependencies, even if they are already up to
-- date. There is no memoisation, therefore the a key may be built
-- multiple times.
busy :: forall k v. Eq k => Build Monad () k v
-- | This is a correct but non-minimal build system: it will rebuild keys
-- even if they are up to date. However, it performs memoization,
-- therefore it never builds a key twice.
memo :: Ord k => Build Monad () k v
-- | A model of Make: an applicative build system that uses file
-- modification times to check if a key is up to date.
make :: Ord k => Build Applicative (MakeInfo k) k v
-- | A model of Ninja: an applicative build system that uses verifying
-- traces to check if a key is up to date.
ninja :: (Ord k, Hashable v) => Build Applicative (VT k v) k v
-- | A model of CloudBuild: an applicative build system that uses
-- constructive traces to check if a key is up to date as well as for
-- caching build results.
cloudBuild :: (Ord k, Hashable v) => Build Applicative (CT k v) k v
-- | A model of Buck: an applicative build system that uses deep
-- constructive traces to check if a key is up to date as well as for
-- caching build results.
buck :: (Ord k, Hashable v) => Build Applicative (DCT k v) k v
-- | A model of Excel: a monadic build system that stores the calculation
-- chain from the previuos build and approximate dependencies.
excel :: Ord k => Build Monad (ExcelInfo k) k v
-- | A model of Shake: a monadic build system that uses verifying traces to
-- check if a key is up to date.
shake :: (Ord k, Hashable v) => Build Monad (VT k v) k v
-- | A model of Cloud Shake: a monadic build system that uses constructive
-- traces to check if a key is up to date as well as for caching build
-- results.
cloudShake :: (Ord k, Hashable v) => Build Monad (CT k v) k v
-- | A model of Bazel: a monadic build system that uses constructive traces
-- to check if a key is up to date as well as for caching build results.
-- Note that Bazel currently does not allow users to write monadic build
-- rules: only built-in rules have access to dynamic dependencies.
bazel :: (Ord k, Hashable v) => Build Monad (CT k v) k v
-- | A model of Nix: a monadic build system that uses deep constructive
-- traces to check if a key is up to date as well as for caching build
-- results.
nix :: (Ord k, Hashable v) => Build Monad (DCT k v) k v