snowleopard / build Goto Github PK

Hello Andrey

Have you ever considered kind of a "dual" task?
I mean building the "strongly typed" local development environment with Infrastructure-as-Code approach.
It's correctness for a class of projects may be guaranteed by the build sources.

The practical need is that the build systems are normally working well in managed environments.
But individual developers have mutable environments in totally unknown state, for example with missing or misconfigured runtimes or build systems themselves.

I'm not sure how the recursive scheduler works. In particular, it's not clear to me how info is threaded through the recursive calls. As I understand it, the recursion happens on the last line on the snippet below via newFetch:

let newTask = rebuilder key value task
    newFetch = lift . fetch
    info <- gets (getInfo . fst)
    (newValue, newInfo) <- runStateT (run newTask newFetch) info

newTask has calls to get and put (for example, in vtRebuilder), and uses newFetch to recursively update its dependencies. However, each newFetch has it's own version of info and each StateT is run off by runStateT, so it would seem to me that when the code returns to vtRebuilder for the top level target key, it would still only have its original and unmodified version info. But this isn't the case: it correctly gets updated by its dependencies.

Are the nested get and put calls somehow updating the same state?

@Rotsor spotted today that the implementation of multi always returns Just in the second case:

https://github.com/snowleopard/build/blob/master/src/Build/Multi.hs#L20

But what if we ask the resulting Tasks to build a list that contains input keys? We'll fetch them! This will lead to a cyclic dependency, breaking the build system.

The fix doesn't seem to be difficult: presumably, we need to apply tasks to all keys and if any of them returns Nothing we should also return Nothing. It's a bit awkward, but I don't see a better fix.

@ndmitchell Thoughts?

P.S.: Actually the correct check should probably be isInput = any (isNothing . tasks . partition) keys.

The doc comment for shake talks about verifying traces while the implementation has moved to ST.

This is an issue to discuss how the restarting scheduler can be used to build tasks with dynamic inputs and outputs, as opposed to tasks with dynamic inputs that are covered by the Build Systems à la Carte paper.

I'll start by sketching a proof that the restarting scheduler works for tasks with dynamic outputs. First of all, we need to assume that all build tasks are finite, i.e. that they terminate and have a finite number of input dependencies, which in turn guarantees that the restarting scheduler terminates. Why? Because it always makes some progress by either removing a task from the working queue, or unblocking one of the blocked tasks, in which case the latter is one step closer to completion.

Let's run the restarting algorithm with a working queue containing all build tasks.

When it terminates, we have one of two cases:

• It succeeds and builds the target.
• It fails to build the target, our working queue is empty, and there is a set of blocked tasks T.

Now we can argue that in the second case the target key cannot be built due to one of the two reasons:

1. There is a dependency cycle reachable from it.
2. The target, or one of the keys it transitively depends on, is not an input and has no task to build it.

Let k denote the target key. All tasks that are not in T have completed and did not produce k (the build failed), hence we know that all tasks that could possibly build k must be in T. Let t denote one such task (if there is no such t, then this is the case (2) above). Since t ∈ T, it is blocked by some key b, and we can repeat our argument by taking b as the target key: by doing this we will eventually either hit the case (2), or will circle back to a key we already examined (since T is finite), which would indicate the case (1).

The proof in non-constructive in the sense that we don't know which t could actually produce k and hence lead to a cycle. All we can say is that either such t does not exist (2), or it does exist but it will inevitably either lead to a cycle (1) or hit a dead end (2).

Hi, the version bounds on Hackage are out-of-date. Could you please make a revision?