Cleanup cycle cracking in parallel_emerge.

parallel_emerge

 #!/usr/bin/python2.6
 # Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
 # Use of this source code is governed by a BSD-style license that can be
 # found in the LICENSE file.
 
 """Program to run emerge in parallel, for significant speedup.
 
 Usage:
  ./parallel_emerge [--board=BOARD] [--workon=PKGS] [--no-workon-deps]
                    [emerge args] package"
@@ skipping 624 matching lines @@
       # If this package is installed, or will get installed, add it to
       # final_pkgs
       for pkg in deps_map:
         for match in final_db.match_pkgs(pkg):
           final_pkgs.add(str(match.cpv))
 
     def FindCycles():
       """Find cycles in the dependency tree.
 
       Returns:
-        Dict of packages involved in cyclic dependencies, mapping each package
-        to a list of the cycles the package is involved in.
+        A dict mapping cyclic packages to a dict of the deps that cause
+        cycles. For each dep that causes cycles, it returns an example
+        traversal of the graph that shows the cycle.
       """
 
-      def FindCyclesAtNode(pkg, cycles, unresolved):
+      def FindCyclesAtNode(pkg, cycles, unresolved, resolved):
         """Find cycles in cyclic dependencies starting at specified package.
 
         Args:
           pkg: Package identifier.
-          cycles: Set of cycles so far.
+          cycles: A dict mapping cyclic packages to a dict of the deps that
+                  cause cycles. For each dep that causes cycles, it returns an
+                  example traversal of the graph that shows the cycle.
           unresolved: Nodes that have been visited but are not fully processed.
+          resolved: Nodes that have been visited and are fully processed.
         """
+        pkg_cycles = cycles.get(pkg)
+        if pkg in resolved and not pkg_cycles:
+          # If we already looked at this package, and found no cyclic
+          # dependencies, we can stop now.
+          return
         unresolved.append(pkg)
-        mycycles = cycles.get(pkg)
-        if mycycles:
-          mycycles = mycycles.get("pkgs")
         for dep in deps_map[pkg]["needs"]:
-          if mycycles and dep in mycycles:
-            continue
-          elif dep in unresolved:
+          if dep in unresolved:
             idx = unresolved.index(dep)
             mycycle = unresolved[idx:] + [dep]
-            for cycle_pkg in mycycle:
-              info = cycles.setdefault(cycle_pkg, {})
-              info.setdefault("pkgs", set()).update(mycycle)
-              info.setdefault("cycles", []).append(mycycle)
-          else:
-            FindCyclesAtNode(dep, cycles, unresolved)
+            for i in range(len(mycycle) - 1):
+              pkg1, pkg2 = mycycle[i], mycycle[i+1]
+              cycles.setdefault(pkg1, {}).setdefault(pkg2, mycycle)
+          elif not pkg_cycles or dep not in pkg_cycles:
+            # Looks like we haven't seen this edge before.
+            FindCyclesAtNode(dep, cycles, unresolved, resolved)
         unresolved.pop()
+        resolved.add(pkg)
 
-      cycles, unresolved = {}, []
+      cycles, unresolved, resolved = {}, [], set()
       for pkg in deps_map:
-        FindCyclesAtNode(pkg, cycles, unresolved)
+        FindCyclesAtNode(pkg, cycles, unresolved, resolved)
       return cycles
 
     def RemoveInstalledPackages():
       """Remove installed packages, propagating dependencies."""
 
       # If we're in non-selective mode, the packages specified on the command
       # line are generally mandatory.
       #
       # There are a few exceptions to this rule:
       #  1. If the package isn't getting installed because it's in
@@ skipping 41 matching lines @@
           dep_provides.update(provides)
           dep_provides.discard(pkg)
           dep_provides.discard(dep)
         for target in provides:
           target_needs = deps_map[target]["needs"]
           target_needs.update(needs)
           target_needs.pop(pkg, None)
           target_needs.pop(target, None)
         del deps_map[pkg]
 
+    def PrintCycleBreak(basedep, dep, mycycle):
+      """Print details about a cycle that we are planning on breaking.
+
+         We are breaking a cycle where dep needs basedep. mycycle is an
+         example cycle which contains dep -> basedep."""
+
+      # If it's an optional dependency, there's no need to spam the user with
+      # warning messages.
+      needs = deps_map[dep]["needs"]
+      depinfo = needs.get(basedep, "deleted")
+      if depinfo == "optional":
+        return
+
+      # Notify the user that we're breaking a cycle.
+      print "Breaking %s -> %s (%s)" % (dep, basedep, depinfo)
+
+      # Show cycle.
+      for i in range(len(mycycle) - 1):
+        pkg1, pkg2 = mycycle[i], mycycle[i+1]
+        needs = deps_map[pkg1]["needs"]
+        depinfo = needs.get(pkg2, "deleted")
+        if pkg1 == dep and pkg2 == basedep:
+          depinfo = depinfo + ", deleting"
+        print "  %s -> %s (%s)" % (pkg1, pkg2, depinfo)
+
     def SanitizeTree(cycles):
       """Remove circular dependencies.
 
       We prune all dependencies involved in cycles that go against the emerge
       ordering. This has a nice property: we're guaranteed to merge
       dependencies in the same order that portage does.
 
       Because we don't treat any dependencies as "soft" unless they're killed
       by a cycle, we pay attention to a larger number of dependencies when
       merging. This hurts performance a bit, but helps reliability.
 
       Args:
         cycles: Dict of packages involved in cyclic dependencies, mapping each
         package to a list of the cycles the package is involved in. Produced
         by FindCycles().
       """
-      for basedep, cycle_info in cycles.iteritems():
-        for mycycle in cycle_info["cycles"]:
-          info = []
-          broken = False
-          for i in range(len(mycycle) - 1):
-            pkg1, pkg2 = mycycle[i], mycycle[i+1]
-            needs = deps_map[pkg1]["needs"]
-            depinfo = needs.get(pkg2, "deleted")
-            bad = False
-            if (deps_info[pkg1]["idx"] >= deps_info[pkg2]["idx"] and
-                depinfo != "deleted"):
-              depinfo = depinfo + ", deleting"
-              broken = True
-              del deps_map[pkg1]["needs"][pkg2]
-              deps_map[pkg2]["provides"].remove(pkg1)
-            info.append("  %s -> %s (%s)" % (pkg1, pkg2, depinfo))
-          if broken:
-            print "Breaking cycle:"
-            print "\n".join(info)
+      for dep, mycycles in cycles.iteritems():
+        for basedep, mycycle in mycycles.iteritems():
+          if deps_info[basedep]["idx"] >= deps_info[dep]["idx"]:
+            PrintCycleBreak(basedep, dep, mycycle)
+            del deps_map[dep]["needs"][basedep]
+            deps_map[basedep]["provides"].remove(dep)
 
     def AddSecretDeps():
       """Find these tagged packages and add extra dependencies.
 
       For debugging dependency problems.
       """
       for bad in secret_deps:
         needed = secret_deps[bad]
         bad_pkg = None
         needed_pkg = None
@@ skipping 782 matching lines @@
       world_set.update(new_world_pkgs)
 
   # Update environment (library cache, symlinks, etc.)
   if deps.board and "--pretend" not in emerge.opts:
     portage.env_update()
 
   print "Done"
 
 if __name__ == "__main__":
   main()