Improve the "gn path" command.

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.

Committed: https://crrev.com/8161ecd407152b4a07652b62dad8b2b273a55638
Cr-Commit-Position: refs/heads/master@{#398491}

[brettw, 2016-06-05 18:31:06]

The CQ bit was checked by brettw@chromium.org to run a CQ dry run

[brettw, 2016-06-05 18:31:07]

include

[commit-bot: I haz the power, 2016-06-05 18:31:17]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/2037303002/40001

[brettw, 2016-06-05 18:31:32]

brettw@chromium.org changed reviewers:
+ dpranke@chromium.org

[brettw, 2016-06-05 18:39:03]

Description was changed from

==========
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 shortet (or all of them if
requested).

Unfortunately, there are many hundred million unique paths between two targets
like //chrome and //base and it would take a llong 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 tarverse 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.
==========

to

==========
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.
==========

[commit-bot: I haz the power, 2016-06-05 19:26:01]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-06-05 19:26:02]

Dry run: This issue passed the CQ dry run.

[Dirk Pranke, 2016-06-07 02:01:28]

Sorry, I didn't have time to get to this today; I should be able to look at it
tomorrow morning, though.

[brettw, 2016-06-07 03:57:17]

No rush, this is obviously not blocking anything.

[Dirk Pranke, 2016-06-07 22:55:37]

lgtm

https://codereview.chromium.org/2037303002/diff/40001/tools/gn/command_path.cc
File tools/gn/command_path.cc (right):

https://codereview.chromium.org/2037303002/diff/40001/tools/gn/command_path.c...
tools/gn/command_path.cc:202: // doing depth-first search, we know that the
current path is the best
you mean breadth-first, right?

[brettw, 2016-06-08 05:11:28]

comment fix

[brettw, 2016-06-08 05:11:29]

The CQ bit was checked by brettw@chromium.org

[brettw, 2016-06-08 05:11:29]

The patchset sent to the CQ was uploaded after l-g-t-m from dpranke@chromium.org
Link to the patchset: https://codereview.chromium.org/2037303002/#ps60001
(title: "comment fix")

[commit-bot: I haz the power, 2016-06-08 05:11:41]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/2037303002/60001

[commit-bot: I haz the power, 2016-06-08 06:12:26]

Description was changed from

==========
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.
==========

to

==========
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.
==========

[commit-bot: I haz the power, 2016-06-08 06:12:27]

Committed patchset #4 (id:60001)

[commit-bot: I haz the power, 2016-06-08 06:14:00]

Description was changed from

==========
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.
==========

to

==========
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.

Committed: https://crrev.com/8161ecd407152b4a07652b62dad8b2b273a55638
Cr-Commit-Position: refs/heads/master@{#398491}
==========

[commit-bot: I haz the power, 2016-06-08 06:14:01]

Patchset 4 (id:??) landed as
https://crrev.com/8161ecd407152b4a07652b62dad8b2b273a55638
Cr-Commit-Position: refs/heads/master@{#398491}