Create a debug tool to print all dependency chains between two nodes
aosp/825820 prints a single dependency chain between two nodes using a
BFS based approach. The current CL will print all dependency chains.
This has been implemented using a DFS based approach.
1. DFS makes it easy to send a "path prefix"
2. I have not memoized this algorithm yet. I ran it for a couple of
examples against redin's ninja file and found it to benchmark OK (more
details in Test section)
3. Since this is DFS, it is sensitive to the depth of the search. For my
hardware, a search exceeding a depth>50,000 would cause a segmentation fault
Bug: 193147539
Test: ./ninja ninja_test && ./ninja_test
Benchmark:
path
time ./ninja -C ~/code/aosp -f out/combined-aosp_redfin.ninja -t path
all bionic/apex/com.android.runtime.pk8
takes ~26s and returns 1 path
paths
time ./ninja -C ~/code/aosp -f out/combined-aosp_redfin.ninja -t paths
all bionic/apex/com.android.runtime.pk8
takes ~28s and returns 48 paths
Change-Id: Ia5ea029dd0f9c410a1151310d205792b93ed702c
4 files changed
