h*WeR      !"#$%&'()*+,-./0123456789:; < = > ? @ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l m n o p q r s t u v w x y z { | } ~                          1.1 Safe-Inferred& buildAn abstract datatype for a key/value store with build information of type i.buildCompute the hash of a given value. We typically assume cryptographic hashing, e.g. SHA256.buildA  is used for efficient tracking and sharing of build results. We use newtype Hash a = Hash a for prototyping.buildRead the build information.buildRead the value of a key.buildRead the hash of a key's value. In some cases may be implemented more efficiently than hash . getValue k.buildWrite the build information.buildModify the build information. buildUpdate the value of a key. buildInitialise the store.      Safe-Inferred/build associates a  with every non-input key. Nothing% indicates that the key is an input.buildA $ is used to compute a value of type v<, by finding the necessary dependencies using the provided fetch :: k -> f v callback.buildCompose two task descriptions, preferring the first one in case there are two tasks corresponding to the same key. Safe-Inferred)*/buildThe type variable s stands for "scripts" written in some task description language.    Safe-Inferred $buildWe 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.buildFetch a value.buildFetch a task description.'build A model for 7, works beautifully and allows storing the key on disk.(buildThe 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.$%&!"#'($%&!"#'( Safe-Inferred Z)buildDefines 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*buildGiven a task description with individual multiple-output keys, compute its "closure" supporting all possible combinations of keys.)*)* Safe-Inferred +build-Find the dependencies of an applicative task.++ Safe-Inferred9 /012,-.34 /012,-.34 Safe-Inferred f:build)Find the dependency of a functorial task.::  Safe-Inferred;build'Execute a monadic task on a pure store k -> v, tracking the dependencies.<build9Execute a monadic task using an effectful fetch function k -> m v, tracking the dependencies.=build6Given a description of tasks, check if a key is input.>build'Run a task with a pure lookup function.?buildRun a task in a given store.@build,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.Abuild,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.<;=>?@A<;=>?@A  Safe-Inferred BbuildAn example of a non-deterministic task: generate a random number from a specified interval.buildRun a non-deterministic task with a pure lookup function, listing all possible results.CbuildRun a task in a given store.DbuildGiven a description of tasks , an initial store, and a result1 produced by running a build system on a target key, this function returns  if the key='s value is a possible result of running the associated task.BCDBCD  Safe-Inferred )*/"Ebuild A way to show the name of a key.Fbuild0Known information about build task dependencies.Gbuild!An association of keys to values.Jbuild;A log is a sequence of log entries, in the execution order.KbuildA 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.NbuildMultiple black boxes, e.g. a collection of build scripts lying around.ObuildAn example type of "black box" build tasks: we can only find out what they read and write by executing them in a monadic context.PbuildA collection of build tasks using the same read and write interface.Qbuild(A task along with its unique identifier.UbuildA unique task identifier, e.g. the path to the corresponding build script.Vbuild f a -> f a to allow for static analysis of applicative and selective build tasks, since we cannot have a in a static context f , e.g. in Const2. See more details in Section 5.3 of this paper:  https://www.staff.ncl.ac.uk/andrey.mokhov/selective-functors.pdf.Xbuild,Read a key's value in a computation context f.YbuildA collection of keys for accessing files, environment variables, and contents of directories. Directories are somewhat magic, because their values are derived from Z keys, i.e. creating a new file in a directory requires updating the the corresponding \ key.]build.Environment variables are identified by names.^build%An example collection of black boxes._buildA 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.`build5A script for packaging the contents of the directory out in an archive. Note that if called prematurely, it will miss some of the release files and will succeed, yielding an incomplete archive. The task will therefore need to be rerun whenever the key  Dir "out" is updated.abuild0Compile a C source file, possibly including the lib.h header.bbuildLink object files in a given directory, producing an executable. Note that this task can fail if run prematurely i.e. when some object files have not yet been placed in the obj1 directory, since some symbols will be undefined.cbuildCheck if a log contains a L for a given Y=. Useful to detect if a task has a certain input dependency.dbuild-Execute a monadic task using given callbacks X and W , logging all reads and writes.fbuild-An example store with the following contents:=File "src/a.c" -> "a" File "src/b.c" -> "b...#include  lib.h..." File "obj/main.o" -> "...main..." File "lib/lib.h" -> "lib..." File "out/README" -> "This is a README..." Env LIBDIR -> "lib" Dir "obj" -> ["main.o"] Dir "out" -> [README]gbuildA build system that builds a collection of black box tasks by executing them blindly, and recording the resulting dependencies.hbuild*A simple pretty-printer for the data type Y.ibuild?Show a value corresponding to a key, extracting an appropriate  instance from it.jbuildA X in  for GHCi experiments.kbuildA W in  for GHCi experiments.ZbuildFile contents.[buildEnvironment variable.\buildDirectory contents.'EFGIHJKMLNOPQSTRUVWXY\[Z]^_`abcdefghijk']Y\[ZXWVUQSTRPON^_`abKMLJcdGIHefFgEhijk  Safe-Inferred)*/'build A way to show the name of a key.mbuildA typed build task.6A side observation: we could also rewrite the type of m intotype Task c k = forall f. c f => (forall a. k a -> f a) -> (forall a. k a -> 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.buildThe fetch; callback whose result type depends on the type of the key.nbuild"Extract the names of dependencies.buildA build task for some simple typed numeric calculations. We can perform static analysis of this task using the function n. For example: dependencies showKey task Base == [] dependencies showKey task SplitDigit == [Number,Base] build7An example key/value mapping consistent with the build .buildShow the name of a key.mnmn  Safe-Inferred0RqbuildA step trace, records the resulting value, the step it last build, the step where it changed.sbuild1Our current model has the same representation as t, 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.tbuildAn abstract data type for a set of constructive traces equipped with ~, },  and a  instance.ubuildAn abstract data type for a set of verifying traces equipped with {, | and a  instance.vbuild.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.{build"Record a new trace for building a key with dependencies deps6, obtaining the hashes of up-to-date values by using  fetchHash.|buildGiven a function to compute the hash of a key's current value, a key(, and a set of verifying traces, return  if the key is up-to-date.}buildCheck if a given key is dirty w.r.t a store.~build"Record a new trace for building a key with dependencies deps6, obtaining the hashes of up-to-date values by using  fetchHash.buildGiven 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.build6Extract the tree of input dependencies of a given key.build"Record a new trace for building a key with dependencies deps<, obtaining the hashes of up-to-date values from the given store.buildGiven a function to compute the hash of a key's current value, a key1, and a set of deep constructive traces, return  Just newValue5 if it is possible to reconstruct it from the traces.build"Record a new trace for building a key with dependencies deps.buildGiven a function to compute the hash of a key's current value, a key(, and a set of verifying traces, return  if the key is up-to-date.vwxzyu{|t}~srqvwxzyu{|t}~srq Safe-Inferred/5! build7A set of dirty keys and information about dependencies.buildIf 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).buildGiven 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.buildAlways rebuilds the key.buildThis rebuilder uses modification time to decide whether a key is dirty and needs to be rebuilt. Used by Make.build/If the key is dirty, rebuild it. Used by Excel.buildIf the key is dirty, rebuild it and clear the dirty bit. Used by Excel.buildThis rebuilders uses approximate dependencies to decide whether a key needs to be rebuilt.build*This rebuilder relies on verifying traces.build-This rebuilder relies on constructive traces.build2This rebuilder relies on deep constructive traces.build-This rebuilder relies on version/step traces. Safe-Inferred9buildBuild a dependency graph given a function for computing dependencies of a key and a target key.build=Compute all keys reachable via dependecies from a target key.build2Compute the topological sort of a graph or return Nothing if the graph has cycles.buildGiven a function to compute successors of a vertex, apply it recursively starting from a given vertex. Returns Nothing if this process does not terminate because of cycles. Note that the current implementation is very inefficient: it trades efficiency for simplicity. The resulting list is likely to contain an exponential number of duplicates.buildGiven a monadic function to compute successors of a vertex, apply it recursively starting from a given vertex. Returns Nothing if this process does not terminate because of cycles. Note that the current implementation is very inefficient: it trades efficiency for simplicity. The resulting list is likely to contain an exponential number of duplicates. Safe-Inferred/<build&A build system takes a description of , a target key, and a store, and computes a new store, where the key and its dependencies are up to date.buildGiven a description of tasks , an initial store, and a result1 produced by running a build system on a target key, this function returns  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. Safe-Inferred /J/buildAn item in the queue comprises a key that needs to be built and a list of keys that are blocked on it. More efficient implementations are possible, e.g. storing blocked keys in a  Map k [k]" would allow faster queue updates.buildThe 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.build Lift a computation operating on i to  Store i k v.build Lift a computation operating on  Store i k v to Store (i, j) k v.buildUpdate the value of a key in the store. The function takes both the current value (the first argument of type v2) and the new value (the second argument of type v), and can potentially avoid touching the store if the value is unchanged. The current implementation simply ignores the current value, but in future this may be optimised, e.g. by comparing their hashes.buildThis 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.build,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, e.g. because of a failed dependency lookup, and Right v yields the value otherwise.buildA 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.buildAdd a key with a list of blocked keys to the queue. If the key is already in the queue, extend its list of blocked keys.buildExtract a key and a list of blocked keys from the queue, or return Nothing if the queue is empty.buildA 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.buildThis 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.buildRun a Task (MonadState i) using a fetch callback operating on a larger state that contains a  Store i k v plus some extra information.buildAn 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. Safe-InferredR build2Excel stores a dirty bit per key and a calc chain.buildThis is not a correct build system: given a target key, it simply rebuilds it, without rebuilding any of its dependencies.buildThis 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.buildThis 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.buildA model of Make: an applicative build system that uses file modification times to check if a key is up to date.buildA model of Ninja: an applicative build system that uses verifying traces to check if a key is up to date.buildA model of Excel: a monadic build system that stores the calculation chain from the previous build and approximate dependencies.buildA model of Shake: a monadic build system that uses verifying traces to check if a key is up to date.buildA 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.buildA 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.buildA 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.buildA 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.buildA 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.   !"#$%&'()*+,-./00123..4,,56789:;<=>>?@ABCDEFGH I J K L M N O P Q R S T    U V W X Y Z ) [ [ \ ] ^ * _ ` , a b c d e  f g h i j  k l m n o p q * : r s t u v w x y y z { | } ~                             S 2 ]  m  build-1.1-Ay2MQF4UxDF2FysfGj38PW Build.Store Build.TaskBuild.SelfTracking.TypedBuild.SelfTracking Build.MultiBuild.Task.ApplicativeBuild.Task.FreeBuild.Task.FunctorBuild.Task.MonadBuild.Task.MonadPlusBuild.Task.OpaqueBuild.Task.Typed Build.TraceBuild.RebuilderBuildBuild.Scheduler Build.SystembuildBuild.UtilitiesStoreHashablehashHashgetInfogetValuegetHashputInfomapInfoputValue initialise$fApplicativeHash $fFunctorHash $fHashable(,)$fHashableHash$fHashableList$fHashableInteger $fHashableInt$fEqHash $fOrdHash $fShowHashTasksTaskcomposeKeyScriptValueTasksTTaskTrunTFetch selfTracking ValueTaskKeyTask selfTrackingM selfTrackingA Partitionmulti dependenciesActionFinishedDependsRuletoRulefromRuletoAction fromAction$fApplicativeRule $fMonadAction$fApplicativeAction$fFunctorAction $fFunctorRule dependency trackPuretrackisInput computePurecompute liftMaybe liftEitherrandom computeNDcorrectBuildValueShowKeyGraphLogLogEntryGetEntryPutEntry BlackBoxesBlackBox NamedTasktaskNametaskTaskNamePutGetFileEnvDirVariabletasksreleasecompilelink hasWrongGetexecute exampleStore blindBuildshowKey showValuegetIOputIO$fShowLogEntry $fEqVersion $fOrdVersionSTStepDCTCTVTTracekeydependsresultrecordVTverifyVT isDirtyCTrecordCT constructCT recordDCT constructDCTrecordSTverifyST $fMonoidStep$fSemigroupStep $fMonoidST $fSemigroupST$fShowST $fShowTraceST $fEnumStep$fEqStep $fOrdStep $fShowStep $fMonoidDCT$fSemigroupDCT $fShowDCT $fMonoidCT $fSemigroupCT$fShowCT $fMonoidVT $fSemigroupVT$fShowVT $fShowTraceApproximationInfoApproximateDependenciesMakeInfoTime RebuilderperpetualRebuildermodTimeRebuilderdirtyBitRebuilderdirtyBitRebuilderWithCleanUpapproximateRebuilder vtRebuilder ctRebuilder dctRebuilder stRebuilder correctBuildChain Scheduler topological restarting restarting2 suspending independent$fMonadStateiWrap $fFunctorWrap$fApplicativeWrap $fMonadWrapdumbbusymemomakeninjaexcelshakebazel cloudShake cloudBuildbucknix fetchValuefetchValueTaskbaseGHC.BaseMonad computePureNDghc-prim GHC.TypesTrueGHC.ShowShowIOfetchMonoiddeepDependenciesgraph reachabletopSortreachreachMQueue liftStoreliftInfo updateValuetryenqueuedequeueliftRun ExcelInfo