Simplify and optimize FindCycles

pylib/gyp/input.py

 # Copyright (c) 2012 Google Inc. All rights reserved.
 # Use of this source code is governed by a BSD-style license that can be
 # found in the LICENSE file.
 
 from compiler.ast import Const
 from compiler.ast import Dict
 from compiler.ast import Discard
 from compiler.ast import List
 from compiler.ast import Module
 from compiler.ast import Node
@@ skipping 1538 matching lines @@
             break
 
         if is_in_degree_zero:
           # All of the dependent's dependencies are already in flat_list.  Add
           # it to in_degree_zeros where it will be processed in a future
           # iteration of the outer loop.
           in_degree_zeros.add(node_dependent)
 
     return list(flat_list)
 
-  def FindCycles(self, path=None):
+  def FindCycles(self):
     """
     Returns a list of cycles in the graph, where each cycle is its own list.
     """
-    if path is None:
-      path = [self]
+    results = []
+    visited = set()
 
-    results = []
-    for node in self.dependents:
-      if node in path:
-        cycle = [node]
-        for part in path:
-          cycle.append(part)
-          if part == node:
-            break
-        results.append(tuple(cycle))
-      else:
-        results.extend(node.FindCycles([node] + path))
+    def Visit(node, path):
+      for child in node.dependents:
+        if child in path:
+          results.append(tuple([child] + path[:path.index(child) + 1]))

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

Does this have to make a tuple() out of the list? (The docstring appears to
imply not)

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

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.

+        elif not child in visited:
+          visited.add(child)
+          Visit(child, [child] + path)

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

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]

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.

+
+    visited.add(self)
+    Visit(self, [self])
 
     return list(set(results))
 
   def DirectDependencies(self, dependencies=None):
     """Returns a list of just direct dependencies."""
     if dependencies == None:
       dependencies = []
 
     for dependency in self.dependencies:
       # Check for None, corresponding to the root node.
@@ skipping 198 matching lines @@
         dependency_node = dependency_nodes.get(dependency)
         if not dependency_node:
           raise GypError("Dependency '%s' not found while "
                          "trying to load target %s" % (dependency, target))
         target_node.dependencies.append(dependency_node)
         dependency_node.dependents.append(target_node)
 
   flat_list = root_node.FlattenToList()
 
   # If there's anything left unvisited, there must be a circular dependency
-  # (cycle).  If you need to figure out what's wrong, look for elements of
-  # targets that are not in flat_list.
+  # (cycle).
   if len(flat_list) != len(targets):
-    raise DependencyGraphNode.CircularException(
-        'Some targets not reachable, cycle in dependency graph detected: ' +
-        ' '.join(set(flat_list) ^ set(targets)))
+    cycles = []
+    for cycle in root_node.FindCycles():
+      paths = []
+      for node in cycle:
+        paths.append(node.ref)
+      cycles.append('Cycle: %s' % ' -> '.join(paths))
+    raise DependencyGraphNode.CircularException, \

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

Why not CircularException(...)?

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

Done.

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

+        'Cycles in dependency graph detected:\n' + '\n'.join(cycles)

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

Could you add a test for this improved output format to input_test.py?

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

Done.

 
   return [dependency_nodes, flat_list]
 
 
 def VerifyNoGYPFileCircularDependencies(targets):
   # Create a DependencyGraphNode for each gyp file containing a target.  Put
   # it into a dict for easy access.
   dependency_nodes = {}
   for target in targets.iterkeys():
     build_file = gyp.common.BuildFile(target)
@@ skipping 32 matching lines @@
       root_node.dependents.append(build_file_node)
 
   flat_list = root_node.FlattenToList()
 
   # If there's anything left unvisited, there must be a circular dependency
   # (cycle).
   if len(flat_list) != len(dependency_nodes):
     bad_files = []
     for file in dependency_nodes.iterkeys():
       if not file in flat_list:
         bad_files.append(file)

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

bad_files was unused

     common_path_prefix = os.path.commonprefix(dependency_nodes)

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

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.

     cycles = []
     for cycle in root_node.FindCycles():
       simplified_paths = []
       for node in cycle:
         assert(node.ref.startswith(common_path_prefix))
         simplified_paths.append(node.ref[len(common_path_prefix):])
       cycles.append('Cycle: %s' % ' -> '.join(simplified_paths))
     raise DependencyGraphNode.CircularException, \
         'Cycles in .gyp file dependency graph detected:\n' + '\n'.join(cycles)
 
@@ skipping 999 matching lines @@
     ValidateRunAsInTarget(target, target_dict, build_file)
     ValidateActionsInTarget(target, target_dict, build_file)
 
   # Generators might not expect ints.  Turn them into strs.
   TurnIntIntoStrInDict(data)
 
   # TODO(mark): Return |data| for now because the generator needs a list of
   # build files that came in.  In the future, maybe it should just accept
   # a list, and not the whole data dict.
   return [flat_list, targets, data]