-- 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 0.0.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.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 the value of a key, 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 = forall f. c f => k -> Maybe ((k -> f v) -> f 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.
--   
--   <ul>
--   <li>For Monad it works out beautifully. You just store the rule on the
--   disk, and depend on it.</li>
--   <li>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.</li>
--   </ul>
module Build.SelfTracking
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 using Monad, works beautifully and allows storing the key on
--   the disk.
selfTrackingM :: (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)


-- | Given a build system that can work with single keys, generalise that
--   to one that deals with multiple keys at a time.
module Build.Multi

-- | Given a build rule where you can build some combinations of multiple
--   rules, use a partition to enable building lots of multiple rule
--   subsets.
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" structures for dependencies, providing either an
--   applicative interface (for <a>Depend</a>) or a monadic interface (for
--   <a>Depends</a>). By passing them to a suitable <a>Task</a> you can
--   reconstruct all necessary dependencies.
module Build.Task.Depend
toDepend :: Task Applicative k v -> Depend k v v

-- | A list of dependencies, and a function that when applied to those
--   dependencies produces the result.
data Depend k v r
Depend :: [k] -> ([v] -> r) -> Depend k v r
toDepends :: Task Monad k v -> Depends k v v

-- | A list of dependencies, and a function that when applied to those
--   dependencies either the result or more dependencies.
data Depends k v r
Depends :: [k] -> ([v] -> Depends k v r) -> Depends k v r
Done :: r -> Depends k v r
instance GHC.Base.Functor (Build.Task.Depend.Depends k v)
instance GHC.Base.Functor (Build.Task.Depend.Depend k v)
instance GHC.Base.Applicative (Build.Task.Depend.Depends k v)
instance GHC.Base.Monad (Build.Task.Depend.Depends k v)
instance GHC.Base.Applicative (Build.Task.Depend.Depend 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 on a pure store <tt>k -&gt; v</tt>, tracking
--   the dependencies.
track :: Task Monad k v -> (k -> v) -> (v, [k])

-- | Execute a monadic task using an effectful fetch function <tt>k -&gt; m
--   v</tt>, tracking the dependencies.
trackM :: forall m k v. Monad m => Task Monad k v -> (k -> m v) -> m (v, [k])

-- | Given a description of tasks, check if a key is input.
isInput :: forall k v. Tasks Monad k v -> k -> Bool

-- | Run a task with a pure lookup function.
compute :: Task Monad k v -> (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.
partial :: 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.
exceptional :: Task Monad k v -> Task Monad k (Either e v)


-- | A Typed version of dependencies 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)


-- | This whole module is just a tiresome workaround for the lack of
--   impredicative polymorphism. If GHC adds impredicative polymorphism, we
--   can drop it entirely and simplify the rest of the code by removing
--   unnecessary task unwrapping.
module Build.Task.Wrapped

-- | GTask is a generalised Task wrapped in a newtype. It is generalised in
--   the sense that it computes a value of type <tt>a</tt> given a fetch of
--   type <tt>k -&gt; f v</tt>.
newtype GTask c k v a
GTask :: (forall f. c f => (k -> f v) -> f a) -> GTask c k v a
[runGTask] :: GTask c k v a -> forall f. c f => (k -> f v) -> f a
type Wrapped c k v = (k -> GTask c k v v) -> GTask c k v v
unwrap :: forall c k v. Wrapped c k v -> Task c k v
instance GHC.Base.Functor (Build.Task.Wrapped.GTask GHC.Base.Functor k v)
instance GHC.Base.Functor (Build.Task.Wrapped.GTask GHC.Base.Applicative k v)
instance GHC.Base.Functor (Build.Task.Wrapped.GTask GHC.Base.Alternative k v)
instance GHC.Base.Functor (Build.Task.Wrapped.GTask GHC.Base.Monad k v)
instance GHC.Base.Functor (Build.Task.Wrapped.GTask GHC.Base.MonadPlus k v)
instance GHC.Base.Applicative (Build.Task.Wrapped.GTask GHC.Base.Applicative k v)
instance GHC.Base.Applicative (Build.Task.Wrapped.GTask GHC.Base.Alternative k v)
instance GHC.Base.Applicative (Build.Task.Wrapped.GTask GHC.Base.Monad k v)
instance GHC.Base.Applicative (Build.Task.Wrapped.GTask GHC.Base.MonadPlus k v)
instance GHC.Base.Monad (Build.Task.Wrapped.GTask GHC.Base.Monad k v)
instance GHC.Base.Monad (Build.Task.Wrapped.GTask GHC.Base.MonadPlus k v)
instance GHC.Base.Alternative (Build.Task.Wrapped.GTask GHC.Base.Alternative k v)
instance GHC.Base.Alternative (Build.Task.Wrapped.GTask GHC.Base.MonadPlus k v)
instance GHC.Base.MonadPlus (Build.Task.Wrapped.GTask GHC.Base.MonadPlus k 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 non-deterministic task with a pure lookup function, listing all
--   possible results.
computeND :: Task MonadPlus k v -> (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


-- | 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 h r
Trace :: k -> [(k, h)] -> r -> Trace k h r
[key] :: Trace k h r -> k
[depends] :: Trace k h r -> [(k, h)]
[result] :: Trace k h 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 :: (Hashable v, Monad m) => k -> v -> [k] -> (k -> m (Hash v)) -> VT k v -> m (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, Hashable v) => k -> 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 :: Monad m => k -> v -> [k] -> (k -> m (Hash v)) -> CT k v -> m (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 -> v -> (k -> m (Hash v)) -> CT k v -> m (Maybe v)

-- | 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. Input
--   keys cannot appear in a DCT because they are never built.
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. (Hashable 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 deterministic constructive traces, return
--   <tt>Just newValue</tt> if it is possible to reconstruct it from the
--   traces.
constructDCT :: forall k v m. (Hashable k, Hashable v, Monad m) => k -> (k -> m (Hash v)) -> DCT k v -> m (Maybe 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, Monad m) => Step -> k -> v -> [k] -> ST k v -> m (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 (Build.Trace.ST k v)
instance Data.Semigroup.Semigroup (Build.Trace.ST k v)
instance GHC.Base.Monoid (Build.Trace.ST 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 Data.Semigroup.Semigroup (Build.Trace.DCT k v)
instance GHC.Base.Monoid (Build.Trace.DCT k v)
instance Data.Traversable.Traversable Build.Trace.Tree
instance GHC.Show.Show a => GHC.Show.Show (Build.Trace.Tree a)
instance GHC.Classes.Ord a => GHC.Classes.Ord (Build.Trace.Tree a)
instance GHC.Base.Functor Build.Trace.Tree
instance Data.Foldable.Foldable Build.Trace.Tree
instance GHC.Classes.Eq a => GHC.Classes.Eq (Build.Trace.Tree a)
instance (GHC.Show.Show k, GHC.Show.Show v) => GHC.Show.Show (Build.Trace.CT k v)
instance Data.Semigroup.Semigroup (Build.Trace.CT k v)
instance GHC.Base.Monoid (Build.Trace.CT k v)
instance Data.Semigroup.Semigroup (Build.Trace.VT k v)
instance GHC.Base.Monoid (Build.Trace.VT k v)
instance (GHC.Show.Show r, GHC.Show.Show h, GHC.Show.Show k) => GHC.Show.Show (Build.Trace.Trace k h r)
instance Data.Semigroup.Semigroup Build.Trace.Step
instance GHC.Base.Monoid Build.Trace.Step
instance Build.Store.Hashable a => Build.Store.Hashable (Build.Trace.Tree a)


-- | 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 () 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 = (Map k Time, Time)

-- | This rebuilders uses approximate dependencies to decide whether a key
--   needs to be rebuilt. Used by Excel.
approximationRebuilder :: Ord k => Rebuilder Monad (ApproximationInfo k) k v
data DependencyApproximation k
SubsetOf :: [k] -> DependencyApproximation k
Unknown :: DependencyApproximation k
type ApproximationInfo k = (k -> Bool, k -> DependencyApproximation 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 deterministic constructive traces.
dctRebuilder :: (Hashable 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 <tt>build</tt> and <tt>tasks</tt>, check that <tt>build</tt>
--   produces a correct result for any initial store and a target key.
correct :: (Ord k, Eq v) => Build Monad i k v -> Tasks Monad k v -> Bool

-- | 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

-- | Check that a build system is <i>idempotent</i>, i.e. running it once
--   or twice in a row leads to the same resulting <a>Store</a>.
idempotent :: Eq v => Build Monad i k v -> Tasks Monad k v -> 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 :: Ord k => Rebuilder Applicative i k v -> Build Applicative 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.
reordering :: forall i k v. Ord k => Rebuilder Monad i k v -> Build Monad (i, Chain k) 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.
restarting :: forall i k v. Eq k => IsDirty i k v -> 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.
recursive :: forall i k v. Ord 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.
independent :: forall i k v. Eq k => Rebuilder Monad i k v -> Build Monad i 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 :: forall k v. 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 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 Buck: an applicative build system that uses deterministic
--   constructive traces to check if a key is up to date as well as for
--   caching build results.
buck :: (Hashable 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 (Step, ST 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 Nix: a monadic build system that uses deterministic
--   constructive traces to check if a key is up to date as well as for
--   caching build results.
nix :: (Hashable k, Hashable v) => Build Monad (DCT k v) k v