Recursive StateT?

[reckbo]

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?

[snowleopard]

@reckbo Thank you very much for your question. The code is indeed tricky -- just as any code involving mutable state! And in fact, you've discovered a bug in our recursive scheduler.

Indeed, due to the confusion of two different versions of info, we lose some traces. I printed the resulting traces for our spreadsheet example and got the following:

[Trace {key = F4, depends = [(F3,Hash 2),(F2,Hash 1)], result = Hash 3}
,Trace {key = F1, depends = [], result = Hash 1}
,Trace {key = F0, depends = [], result = Hash 0}
,Trace {key = C2, depends = [(B3,Hash 6),(C1,Hash 1000)], result = Hash 1000}
,Trace {key = C1, depends = [(B3,Hash 6)], result = Hash 1000}
,Trace {key = B3, depends = [(A3,Hash 3),(B2,Hash 2)], result = Hash 6}
,Trace {key = B2, depends = [(B1,Hash 1)], result = Hash 2}
,Trace {key = B1, depends = [], result = Hash 1}]

We have F4 in the trace, but its dependencies F3 and F2 are missing!

Therefore, although the build result is correct, we will need to rebuild some keys unnecessarily during the next build, because we are missing information on their expected values.

/cc @ndmitchell

[snowleopard]

The following revision of newFetch seems to fix the issue:

newFetch k = do v <- lift (fetch k); put =<< lift (gets $ getInfo . fst); return v

It's not pretty though. I'll see if we can refactor it.

[snowleopard]

By the way, this is related to #6, where we were looking for a safer approach to manipulating traces.

[reckbo]

Thanks for looking into this and clarifying for me (although I'm still baffled that the trace got updated at all, I'll have to look at it again).

[snowleopard]

@reckbo Thanks for opening this issue! And don't hesitate to ask for further clarifications.