Feature request: build in mtime order

[prez]

See https://github.com/ninja-build/ninja/issues/1570. For example, with

rule cmd
    command = true
    description = $in

build ax: cmd a
build bx: cmd b
build cx: cmd c
build all: phony ax bx cx

and touch a c; sleep 1; touch b, samu would build b -> c -> a instead of c -> b -> a.

[markus-oberhumer]

This would indeed be a very welcome feature!

And given that this has been proposed for Ninja back in 2011 ( https://github.com/ninja-build/ninja/pull/60 ) without any further action it might even be a nice "selling point" for people to try samurai.

[michaelforney]

I think this should be easy to implement by using a priority queue for the pending work instead of a stack.

However, I'm not sure exactly how to decide which build actions should be run first. The example in the linked bug suggests that if a header and source file are changed, the unique object that depends on the source file should be built before the many objects that depend on the header. As far as ninja/samurai is concerned, both are inputs to the action.

If we simply used the metric that actions who have a newer input get built first, then if the header was modified later than the source file, we'd still build those 299 objects first. Perhaps we should prioritize first the actions with newest explicit dependencies (perhaps followed by newest implicit dependencies)?