Let us consider following dependency graph (O is the source file):
Let us assume that source file O changed, and we asked to redo "D". To figure
out what needs to be done, check_deps function is used, which reads deps file
of "D", discover that it depends on "B" and "C", their hashes still intact, so
it recurses into both of them, until it figures out that "O" changed.
Problem is that check_deps does not cache its results, so it checks A and O
twice. In general case, every node of every path from D to O is checked,
amplification can be arbitrary large. This issue can be solved by caching,
although it would complicate source code with implementation of hash map.
After redo figured that "D" needs to be re-done, it invokes D.do that calls
"redo-ifchange B", which repeats checking whether "B" needs to be re-done. But
we already know the answer -- it was intermediate result in parent invokation
of "redo-ifchange". It means that we do amount of work quadratic on depth of
the graph, where linear would be enough.
This problem is harder to solve, since we need to share information between all
related calls to "redo-ifchange". Having common ancestor to setup environment
variable with path or file descriptor to common database is probably the
simplest solution, but it would pull dependency on "dbm" at minimum:
implementation of mutable key-value in-file map is unlikely to be trivial.
Thoughts?
Let us consider following dependency graph (O is the source file):
Let us assume that source file O changed, and we asked to redo "D". To figure
out what needs to be done,
check_depsfunction is used, which reads deps fileof "D", discover that it depends on "B" and "C", their hashes still intact, so
it recurses into both of them, until it figures out that "O" changed.
Problem is that
check_depsdoes not cache its results, so it checks A and Otwice. In general case, every node of every path from D to O is checked,
amplification can be arbitrary large. This issue can be solved by caching,
although it would complicate source code with implementation of hash map.
After redo figured that "D" needs to be re-done, it invokes D.do that calls
"redo-ifchange B", which repeats checking whether "B" needs to be re-done. But
we already know the answer -- it was intermediate result in parent invokation
of "redo-ifchange". It means that we do amount of work quadratic on depth of
the graph, where linear would be enough.
This problem is harder to solve, since we need to share information between all
related calls to "redo-ifchange". Having common ancestor to setup environment
variable with path or file descriptor to common database is probably the
simplest solution, but it would pull dependency on "dbm" at minimum:
implementation of mutable key-value in-file map is unlikely to be trivial.
Thoughts?