commit 1e0dbda9b0b9b8ad3e2243b68f35d340341a37ba
author brettw <brettw@chromium.org> Tue Jun 07 23:12:12 2016 -0700
committer Commit bot <commit-bot@chromium.org> Wed Jun 08 06:13:55 2016 +0000
tree 2e8ae27a2c412fef9995db6fd00c472778bc4596
parent 9f6fb17ebe0275fdb1faefd7d4b731af2f11eaf7

Improve the "gn path" command.

Previously, GN path would find all paths between the two targets, count them for statistical purposes, sort them, and print the shortest (or all of them if requested).

Unfortunately, there are many hundred millions of unique paths between two targets like //chrome and //base and it would take a long time and eventually run out of address space counting them all.

This patch changes the algorithm from depth-first to breadth-first search, and doesn't traverse or count a target if that target was already found to have a path to the destination. The result is the path from //chrome to //base finds 65 paths which makes the algorithm run instantly and the output with --all is much more useful.

Review-Url: https://codereview.chromium.org/2037303002
Cr-Original-Commit-Position: refs/heads/master@{#398491}
Cr-Mirrored-From: https://chromium.googlesource.com/chromium/src
Cr-Mirrored-Commit: 8161ecd407152b4a07652b62dad8b2b273a55638