Fix cycle cracking once and for all.

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 811 matching lines @@
 
       # 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):
+    def SanitizeTree():
       """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 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)
+      start = time.time()
+      cycles = FindCycles()
+      while cycles:
+        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)
+        cycles = FindCycles()
+      seconds = time.time() - start
+      if "--quiet" not in emerge.opts and seconds >= 0.1:
+        print "Tree sanitized in %dm%.1fs" % (seconds / 60, seconds % 60)
 
     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 258 matching lines @@
       if self.rebuild:
         local_pkgs = LocalPackageDatabase()
         remote_pkgs = RemotePackageDatabase(emerge.settings["PORTAGE_BINHOST"])
         AutoRebuildDeps(local_pkgs, remote_pkgs, cycles)
 
     # We need to remove installed packages so that we can use the dependency
     # ordering of the install process to show us what cycles to crack. Once
     # we've done that, we also need to recalculate our list of cycles so that
     # we don't include the installed packages in our cycles.
     RemoveInstalledPackages()
-    cycles = FindCycles()
-    SanitizeTree(cycles)
+    SanitizeTree()
     if deps_map:
       if "--usepkg" in emerge.opts:
         UsePrebuiltPackages()
       AddRemainingPackages()
     return deps_map
 
   def PrintInstallPlan(self, deps_map):
     """Print an emerge-style install plan.
 
     The install plan lists what packages we're installing, in order.
@@ skipping 540 matching lines @@
   # If we already upgraded portage, we don't need to do so again. But we do
   # need to upgrade the rest of the packages. So we'll go ahead and do that.
   if portage_upgrade:
     args = sys.argv[1:] + ["--nomerge=sys-apps/portage"]
     os.execvp(os.path.realpath(sys.argv[0]), args)
 
   print "Done"
 
 if __name__ == "__main__":
   main()