Simplify and optimize FindCycles

Simplify and optimize FindCycles

Finding cycles in a directed graph only requires a simple depth first
traversal, it does not require checking every path in the graph.

This is now fast enough to actually identify and print cycles between
targets.

Changes the error message slightly for file and target cycles,
and adds tests for both those cases.

Patch from cjhopman@chromium.org.

R=scottmg@chromium.org

Committed: https://code.google.com/p/gyp/source/detail?r=1992

[cjhopman, 2014-10-21 02:40:21]

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

[cjhopman, 2014-10-21 02:40:22]

scottmg: *

[scottmg, 2014-10-21 02:50:23]

https://codereview.chromium.org/664253005/diff/20001/pylib/gyp/input.py
File pylib/gyp/input.py (right):

https://codereview.chromium.org/664253005/diff/20001/pylib/gyp/input.py#newco...
pylib/gyp/input.py:1802: raise DependencyGraphNode.CircularException, \
Why not CircularException(...)?

https://codereview.chromium.org/664253005/diff/20001/pylib/gyp/input.py#newco...
pylib/gyp/input.py:1803: 'Cycles in dependency graph detected:\n' +
'\n'.join(cycles)
Could you add a test for this improved output format to input_test.py?

[scottmg, 2014-10-21 02:53:07]

https://codereview.chromium.org/664253005/diff/20001/pylib/gyp/input.py
File pylib/gyp/input.py (right):

https://codereview.chromium.org/664253005/diff/20001/pylib/gyp/input.py#newco...
pylib/gyp/input.py:1569: results.append(tuple([child] + path[:path.index(child)
+ 1]))
Does this have to make a tuple() out of the list? (The docstring appears to
imply not)

[scottmg, 2014-10-21 03:22:42]

https://codereview.chromium.org/664253005/diff/20001/pylib/gyp/input.py
File pylib/gyp/input.py (right):

https://codereview.chromium.org/664253005/diff/20001/pylib/gyp/input.py#newco...
pylib/gyp/input.py:1572: Visit(child, [child] + path)
I'm probably reading this wrong, but... given A->B->C->D->B

won't path be [D,C,B,A] so we'll print B->D-C->B as the cycle?

[cjhopman, 2014-10-21 18:22:23]

https://codereview.chromium.org/664253005/diff/20001/pylib/gyp/input.py
File pylib/gyp/input.py (right):

https://codereview.chromium.org/664253005/diff/20001/pylib/gyp/input.py#newco...
pylib/gyp/input.py:1569: results.append(tuple([child] + path[:path.index(child)
+ 1]))
On 2014/10/21 02:53:07, scottmg wrote:
> Does this have to make a tuple() out of the list? (The docstring appears to
> imply not)
Done.

This needed the tuple to convert results to a set below. This approach shouldn't
actually discover a particular cycle multiple times, so the uniqification isn't
needed anymore.

https://codereview.chromium.org/664253005/diff/20001/pylib/gyp/input.py#newco...
pylib/gyp/input.py:1572: Visit(child, [child] + path)
On 2014/10/21 03:22:42, scottmg wrote:
> I'm probably reading this wrong, but... given A->B->C->D->B
> 
> won't path be [D,C,B,A] so we'll print B->D-C->B as the cycle?

Ehh, I had the same problem. So the key is that this is actually traversing to
dependents, not dependencies. Maybe the name "child" doesn't help the mental
model.

https://codereview.chromium.org/664253005/diff/20001/pylib/gyp/input.py#newco...
pylib/gyp/input.py:1802: raise DependencyGraphNode.CircularException, \
On 2014/10/21 02:50:23, scottmg wrote:
> Why not CircularException(...)?
Done.

I just did what was used for raising this below. I've updated there to use (..)
also.

https://codereview.chromium.org/664253005/diff/20001/pylib/gyp/input.py#newco...
pylib/gyp/input.py:1803: 'Cycles in dependency graph detected:\n' +
'\n'.join(cycles)
On 2014/10/21 02:50:23, scottmg wrote:
> Could you add a test for this improved output format to input_test.py?

Done.

https://codereview.chromium.org/664253005/diff/20001/pylib/gyp/input.py#newco...
pylib/gyp/input.py:1856: bad_files.append(file)
bad_files was unused

https://codereview.chromium.org/664253005/diff/20001/pylib/gyp/input.py#newco...
pylib/gyp/input.py:1857: common_path_prefix =
os.path.commonprefix(dependency_nodes)
This doesn't really seem helpful since the prefix it strips sometimes doesn't
make sense (in the test it was getting 0.gyp->1.gyp->0.gyp instead of
file_cycle0.gyp->file_cycle1.gyp->file_cycle0.gyp)... maybe if it computed the
common prefix of the dirnames of all the nodes it would be better, but I don't
know if it is worth it or not.

[scottmg, 2014-10-21 18:31:47]

Thanks! lgtm

https://codereview.chromium.org/664253005/diff/80001/pylib/gyp/input.py
File pylib/gyp/input.py (right):

https://codereview.chromium.org/664253005/diff/80001/pylib/gyp/input.py#newco...
pylib/gyp/input.py:1808: raise DependencyGraphNode.CircularException, \
I meant this \ vs. (, mostly since that's what it was before

[cjhopman, 2014-10-21 19:52:54]

Do the gyp try bots not work?

Also, I'm not a gyp committer, could you land this for me?

https://codereview.chromium.org/664253005/diff/80001/pylib/gyp/input.py
File pylib/gyp/input.py (right):

https://codereview.chromium.org/664253005/diff/80001/pylib/gyp/input.py#newco...
pylib/gyp/input.py:1808: raise DependencyGraphNode.CircularException, \
On 2014/10/21 18:31:47, scottmg wrote:
> I meant this \ vs. (, mostly since that's what it was before

Ha, I really thought I fixed it here before.

[scottmg, 2014-10-21 20:01:42]

On 2014/10/21 19:52:54, cjhopman wrote:
> Do the gyp try bots not work?

It's "git try --no_search" (not "git cl try") but I think it only works if
you're a committer.

I started them. It looks like the tests are failing because of tuple->list. If
you could fix that up, I will land.

> Also, I'm not a gyp committer, could you land this for me?
> 
> https://codereview.chromium.org/664253005/diff/80001/pylib/gyp/input.py
> File pylib/gyp/input.py (right):
> 
>
https://codereview.chromium.org/664253005/diff/80001/pylib/gyp/input.py#newco...
> pylib/gyp/input.py:1808: raise DependencyGraphNode.CircularException, \
> On 2014/10/21 18:31:47, scottmg wrote:
> > I meant this \ vs. (, mostly since that's what it was before
> 
> Ha, I really thought I fixed it here before.

[cjhopman, 2014-10-22 23:43:21]

On 2014/10/21 20:01:42, scottmg wrote:
> On 2014/10/21 19:52:54, cjhopman wrote:
> > Do the gyp try bots not work?
> 
> It's "git try --no_search" (not "git cl try") but I think it only works if
> you're a committer.
> 
> I started them. It looks like the tests are failing because of tuple->list. If
> you could fix that up, I will land.

Fixed up. The remaining failures seem to be unrelated to this change.

> 
> > Also, I'm not a gyp committer, could you land this for me?
> > 
> > https://codereview.chromium.org/664253005/diff/80001/pylib/gyp/input.py
> > File pylib/gyp/input.py (right):
> > 
> >
>
https://codereview.chromium.org/664253005/diff/80001/pylib/gyp/input.py#newco...
> > pylib/gyp/input.py:1808: raise DependencyGraphNode.CircularException, \
> > On 2014/10/21 18:31:47, scottmg wrote:
> > > I meant this \ vs. (, mostly since that's what it was before
> > 
> > Ha, I really thought I fixed it here before.

[scottmg, 2014-10-22 23:57:51]

Committed patchset #8 (id:140001) manually as 1992 (presubmit successful).