Regarding the non-ordering of dependencies I wonder if it would help to have some sort of shuffle flag. I know that redo has implemented a --shuffle flag to tease out missing dependencies.

https://github.com/apenwarr/redo/blob/master/Documentation/r...