-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Build Systems à 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 à la Carte".
@package build
@version 1.1


-- | An abstract key/value store.
module Build.Store

-- | A <a>Hash</a> is used for efficient tracking and sharing of build
--   results. We use <tt>newtype Hash a = Hash a</tt> 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 <tt>i</tt>.
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 <tt>hash . getValue k</tt>.
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.Num.Integer.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 <a>Task</a> is used to compute a value of type <tt>v</tt>, by
--   finding the necessary dependencies using the provided <tt>fetch :: k
--   -&gt; f v</tt> callback.
type Task c k v = forall f. c f => (k -> f v) -> f v

-- | <a>Tasks</a> associates a <a>Task</a> with every non-input key.
--   <tt>Nothing</tt> 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

module Build.SelfTracking.Typed
type Fetch k f = forall v. k v -> f v
newtype TaskT c k v
TaskT :: (forall f. c f => Fetch k f -> f v) -> TaskT c k v
[runT] :: TaskT c k v -> forall f. c f => Fetch k f -> f v
type TasksT c k = forall v. k v -> Maybe (TaskT c k v)

-- | The type variable <tt>s</tt> stands for "scripts" written in some task
--   description language.
data Key k v s a
[Script] :: k -> Key k v s s
[Value] :: k -> Key k v s v
selfTracking :: forall k v s. (s -> Task Monad k v) -> Tasks Monad k s -> TasksT Monad (Key k v s)


-- | This module defines two different strategies of self-tracking, based
--   around the idea of storing task descriptions that can be parsed into a
--   <a>Task</a>.
--   
--   <ul>
--   <li>For <a>Monad</a> it works out beautifully. You just store the rule
--   on the disk, and depend on it.</li>
--   <li>For <a>Applicative</a>, we generate a fresh <a>Task</a> each time,
--   but have that <a>Task</a> depend on a fake version of the rules. This
--   is a change in the <a>Task</a>, 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.</li>
--   </ul>
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
--   <a>Build.Task.Typed</a>.
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 <a>Monad</a>, works beautifully and allows storing the key
--   on 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
--   <tt>f k == ks</tt>, then:
--   
--   <ul>
--   <li><pre>k in ks</pre></li>
--   <li><pre>forall i in ks . f i == ks</pre></li>
--   </ul>
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]


-- | The free description of tasks.
module Build.Task.Free
data Rule k v r
Rule :: [k] -> ([v] -> r) -> Rule k v r
toRule :: Task Applicative k v -> Rule k v v
fromRule :: Rule k v v -> Task Applicative k v
data Action k v a
Finished :: a -> Action k v a
Depends :: k -> (v -> Action k v a) -> Action k v a
toAction :: Task Monad k v -> Action k v v
fromAction :: Action k v v -> Task Monad k v
instance GHC.Base.Functor (Build.Task.Free.Rule k v)
instance GHC.Base.Functor (Build.Task.Free.Action k v)
instance GHC.Base.Applicative (Build.Task.Free.Action k v)
instance GHC.Base.Monad (Build.Task.Free.Action k v)
instance GHC.Base.Applicative (Build.Task.Free.Rule k v)


-- | 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 <tt>k -&gt; m
--   v</tt>, 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 <tt>k -&gt; v</tt>, 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 <tt>k -&gt; m v</tt> into
--   a task with a partial lookup function <tt>k -&gt; m (Maybe v)</tt>.
--   This essentially lifts the task from the type of values <tt>v</tt> to
--   <tt>Maybe v</tt>, where the result <tt>Nothing</tt> indicates that the
--   task failed because of a missing dependency.
liftMaybe :: Task Monad k v -> Task Monad k (Maybe v)

-- | Convert a task with a total lookup function <tt>k -&gt; m v</tt> into
--   a task with a lookup function that can throw exceptions <tt>k -&gt; m
--   (Either e v)</tt>. This essentially lifts the task from the type of
--   values <tt>v</tt> to <tt>Either e v</tt>, where the result <tt>Left
--   e</tt> indicates that the task failed because of a failed dependency
--   lookup, and <tt>Right v</tt> yeilds the value otherwise.
liftEither :: 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 <tt>tasks</tt>, an initial <tt>store</tt>, and
--   a <tt>result</tt> produced by running a build system on a target
--   <tt>key</tt>, this function returns <a>True</a> if the <tt>key</tt>'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


-- | Opaque monadic tasks, whose inputs and outputs can be dynamic.
module Build.Task.Opaque

-- | Environment variables are identified by names.
type Variable = String

-- | A collection of keys for accessing files, environment variables, and
--   contents of directories. Directories are somewhat magic, because their
--   values are derived from <a>File</a> keys, i.e. creating a new file in
--   a directory requires updating the the corresponding <a>Dir</a> key.
data Key a
[File] :: FilePath -> Key String
[Env] :: Variable -> Key String
[Dir] :: FilePath -> Key [FilePath]

-- | Read a key's value in a computation context <tt>f</tt>.
type Get k f = forall a. k a -> f a

-- | Write a key's value in a computation context <tt>f</tt>. Note: the
--   type can be changed to <tt>forall a. k a -&gt; f a -&gt; f a</tt> to
--   allow for static analysis of applicative and selective build tasks,
--   since we cannot have <tt>a</tt> in a static context <tt>f</tt>, e.g.
--   in <tt>Const</tt>. See more details in Section 5.3 of this paper:
--   <a>https://www.staff.ncl.ac.uk/andrey.mokhov/selective-functors.pdf</a>.
type Put k f = forall a. k a -> a -> f ()

-- | A build task is a stateful computation in a monadic context <tt>f</tt>
--   that is given two callbacks: for reading and writing values to a
--   key/value store.
type Task k a = forall f. Monad f => Get k f -> Put k f -> f a

-- | A unique task identifier, e.g. the path to the corresponding build
--   script.
type TaskName = String

-- | A task along with its unique identifier.
data NamedTask k
NamedTask :: TaskName -> Task k () -> NamedTask k
[taskName] :: NamedTask k -> TaskName
[task] :: NamedTask k -> Task k ()

-- | A collection of build tasks using the same read and write interface.
type Tasks k = [NamedTask k]

-- | An example type of "black box" build tasks: we can only find out what
--   they read and write by executing them in a monadic context.
type BlackBox = Task Key ()

-- | Multiple black boxes, e.g. a collection of build scripts lying around.
type BlackBoxes = Tasks Key

-- | An example collection of black boxes.
tasks :: BlackBoxes

-- | A typical build script that compiles a couple of C files, possibly
--   depending on some header files, and then links the resulting objects
--   into an executable.
build :: BlackBox

-- | A script for packaging the contents of the directory <tt>out</tt> in
--   an archive. Note that if called prematurely, it will miss some of the
--   release files and will <i>succeed</i>, yielding an incomplete archive.
--   The task will therefore need to be rerun whenever the key <tt>Dir
--   "out"</tt> is updated.
release :: BlackBox

-- | Compile a C source file, possibly including the <tt>lib.h</tt> header.
compile :: FilePath -> FilePath -> BlackBox

-- | Link object files in a given directory, producing an executable. Note
--   that this task can <i>fail</i> if run prematurely i.e. when some
--   object files have not yet been placed in the <tt>obj</tt> directory,
--   since some symbols will be undefined.
link :: FilePath -> FilePath -> BlackBox

-- | A task execution log entry, recording either a read from a key and the
--   obtained value, or a write to a key, along with the written value.
data LogEntry k
[GetEntry] :: k a -> a -> LogEntry k
[PutEntry] :: k a -> a -> LogEntry k

-- | A log is a sequence of log entries, in the execution order.
type Log k = [LogEntry k]

-- | Check if a log contains a <a>GetEntry</a> for a given <a>Key</a>.
--   Useful to detect if a task has a certain input dependency.
hasWrongGet :: Log Key -> Key a -> a -> Bool

-- | Execute a monadic task using given callbacks <a>Get</a> and
--   <a>Put</a>, logging all reads and writes.
execute :: forall m k. Monad m => Get k m -> Put k m -> Task k () -> m (Log k)

-- | An association of keys to values.
newtype Store
Store :: (forall a. Key a -> a) -> Store
[getValue] :: Store -> forall a. Key a -> a
putValue :: Key a -> a -> Store -> Store

-- | An example store with the following contents:
--   
--   File "src/a.c" -&gt; "a" File "src/b.c" -&gt; "b...#include
--   <a>lib.h</a>..." File "obj/main.o" -&gt; "...main..." File "lib/lib.h"
--   -&gt; "lib..." File "out/README" -&gt; "This is a README..." Env
--   <a>LIBDIR</a> -&gt; "lib" Dir "obj" -&gt; ["main.o"] Dir "out" -&gt;
--   [<a>README</a>]
exampleStore :: Store

-- | Known information about build task dependencies.
type Graph = TaskName -> Maybe (Log Key)

-- | A build system that builds a collection of black box tasks by
--   executing them blindly, and recording the resulting dependencies.
blindBuild :: BlackBoxes -> Store -> Graph -> (Store, Graph)

-- | A way to show the name of a key.
type ShowKey k = forall a. k a -> String

-- | A simple pretty-printer for the data type <a>Key</a>.
showKey :: ShowKey Key

-- | Show a value corresponding to a key, extracting an appropriate
--   <a>Show</a> instance from it.
showValue :: Key a -> a -> String

-- | A <a>Get</a> in <a>IO</a> for GHCi experiments.
getIO :: Get Key IO

-- | A <a>Put</a> in <a>IO</a> for GHCi experiments.
putIO :: Put Key IO
instance GHC.Show.Show (Build.Task.Opaque.LogEntry Build.Task.Opaque.Key)


-- | 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.
--   
--   A side observation: we could also rewrite the type of <a>Task</a> into
--   
--   type Task c k = forall f. c f =&gt; (forall a. k a -&gt; f a) -&gt;
--   (forall a. k a -&gt; Maybe (f a))
--   
--   ...which looks like a morphism between natural transformations. I'll
--   let category theory enthusiasts explain what this strange creature is
--   doing here.
type Task c k = forall f a. c f => Fetch k f -> k a -> Maybe (f a)

-- | Extract the names of dependencies.
dependencies :: ShowKey k -> Task Applicative k -> k a -> [String]
instance GHC.Classes.Ord Build.Task.Typed.Version
instance GHC.Classes.Eq Build.Task.Typed.Version


-- | Build traces that are used for recording information from previuos
--   builds.
module Build.Trace

-- | A trace is parameterised by the types of keys <tt>k</tt>, hashes
--   <tt>h</tt>, as well as the result <tt>r</tt>. For verifying traces,
--   <tt>r = h</tt>; for constructive traces, <tt>Hash r = h</tt>.
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
--   <a>recordVT</a>, <a>verifyVT</a> and a <a>Monoid</a> instance.
data VT k v

-- | Record a new trace for building a <tt>key</tt> with dependencies
--   <tt>deps</tt>, obtaining the hashes of up-to-date values by using
--   <tt>fetchHash</tt>.
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
--   <tt>key</tt>, and a set of verifying traces, return <a>True</a> if the
--   <tt>key</tt> 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
--   <a>recordCT</a>, <a>isDirtyCT</a>, <a>constructCT</a> and a
--   <a>Monoid</a> instance.
data CT k v

-- | Check if a given <tt>key</tt> is dirty w.r.t a <tt>store</tt>.
isDirtyCT :: (Eq k, Hashable v) => k -> Store (CT k v) k v -> Bool

-- | Record a new trace for building a <tt>key</tt> with dependencies
--   <tt>deps</tt>, obtaining the hashes of up-to-date values by using
--   <tt>fetchHash</tt>.
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
--   <tt>key</tt>, and a set of constructive traces, return <tt>Just
--   newValue</tt> 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 <a>CT</a>, but
--   requires an additional invariant: if a DCT contains a trace for a key
--   <tt>k</tt>, then it must also contain traces for each of its non-input
--   dependencies.
data DCT k v

-- | Record a new trace for building a <tt>key</tt> with dependencies
--   <tt>deps</tt>, obtaining the hashes of up-to-date values from the
--   given <tt>store</tt>.
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
--   <tt>key</tt>, and a set of deep constructive traces, return <tt>Just
--   newValue</tt> 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 <tt>key</tt> with dependencies
--   <tt>deps</tt>.
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
--   <tt>key</tt>, and a set of verifying traces, return <a>True</a> if the
--   <tt>key</tt> 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 r) => GHC.Show.Show (Build.Trace.Trace k v r)
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 (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.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 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 r) => GHC.Show.Show (Build.Trace.TraceST k r)
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.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

-- | Always rebuilds the key.
perpetualRebuilder :: Rebuilder Monad i 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 <a>Tasks</a>, 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 <tt>tasks</tt>, an initial <tt>store</tt>, and
--   a <tt>result</tt> produced by running a build system on a target
--   <tt>key</tt>, this function returns <a>True</a> if the <tt>result</tt>
--   is a correct build outcome. Specifically: * <tt>result</tt> and
--   <tt>store</tt> must agree on the values of all inputs. In other words,
--   no inputs were corrupted during the build. * <tt>result</tt> is
--   <i>consistent</i> with the <tt>tasks</tt>, i.e. for every non-input
--   key, the result of recomputing its task matches the value stored in
--   the <tt>result</tt>.
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
type Scheduler c i j k v = Rebuilder c j k v -> Build c 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.
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 <tt>calculation chain</tt>: 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 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 :: forall k v. (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 :: forall k v. (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 :: forall k v. (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 previous 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