Make DependencyGraph.DeepDependencies() depth-first.

Make DependencyGraph.DeepDependencies() depth-first.

Previously dependencies were processed in-order, this changes to pre-order.

This makes 'all_dependent_settings' processing order topological.

R=thakis@chromium.org
BUG=393873
Committed: https://chromium.googlesource.com/external/gyp/+/ae276266d580a10b87661ca50c4574a03625c033

[Dan Beam, 2015-06-18 21:47:27]

Patchset #2 (id:20001) has been deleted

[Dan Beam, 2015-06-18 21:48:06]

Patchset #2 (id:40001) has been deleted

[Nico, 2015-06-18 21:51:58]

lgtm if yes

https://codereview.chromium.org/1182323007/diff/60001/test/dependencies/adso/...
File test/dependencies/adso/all_dependent_settings_order.gyp (right):

https://codereview.chromium.org/1182323007/diff/60001/test/dependencies/adso/...
test/dependencies/adso/all_dependent_settings_order.gyp:7:
'all_dependent_settings': {'sources': ['a.cc']},
Do direct_dependent_settings work correctly already?

[Dan Beam, 2015-06-18 21:56:27]

https://codereview.chromium.org/1182323007/diff/60001/test/dependencies/adso/...
File test/dependencies/adso/all_dependent_settings_order.gyp (right):

https://codereview.chromium.org/1182323007/diff/60001/test/dependencies/adso/...
test/dependencies/adso/all_dependent_settings_order.gyp:7:
'all_dependent_settings': {'sources': ['a.cc']},
On 2015/06/18 21:51:58, Nico wrote:
> Do direct_dependent_settings work correctly already?

unless I'm misunderstanding something: they might but they don't use
DeepDependencies() nor recursion[1].  I can write another test for them if you'd
like, but it seems like a separate issue.

[1]
https://code.google.com/p/chromium/codesearch#chromium/src/tools/gyp/pylib/gy...

[Dan Beam, 2015-06-18 22:54:44]

The CQ bit was checked by dbeam@chromium.org

[Dan Beam, 2015-06-18 22:54:53]

The CQ bit was unchecked by dbeam@chromium.org

[Dan Beam, 2015-06-18 22:56:09]

The CQ bit was checked by dbeam@chromium.org

[commit-bot: I haz the power, 2015-06-18 23:01:06]

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

[commit-bot: I haz the power, 2015-06-18 23:01:08]

Commit queue rejected this change because it did not recognize the base URL.
Please commit your change manually.

[Nico, 2015-06-18 23:35:31]

Committed patchset #3 (id:80001) manually as
ae276266d580a10b87661ca50c4574a03625c033 (presubmit successful).

[cjhopman, 2015-06-19 20:50:01]

cjhopman@chromium.org changed reviewers:
+ cjhopman@chromium.org

[cjhopman, 2015-06-19 20:50:02]

This description confused me. DeepDependencies was already doing a depth-first
search. in-order/pre-order terms usually apply to traversing a tree, but we are
traversing a graph. Also if it were a tree, wouldn't this actually be changing
from pre-order to post-order? In a tree, both pre-order and post-order provide a
topological sort (well, depends on if edges are directed toward children or
parents).

The change itself looks correct, though.