# HG changeset patch
# User Matt Mackall <mpm@selenic.com>
# Date 1427518343 18000
# Node ID fb4639d5268ed1f00c0878afa6dfa1b8eca21fa1
# Parent  0f6594b0a4e290185d549fe43fbc654da33343c6
import-checker: make search algorithm non-recursive breadth-first

Breadth-first allows finding the shortest cycle including the starting
module. This lets us terminate our search early when we've discovered
shorter paths already. This gives a tremendous speed-up to the
cycle-finding portion of the test, dropping total runtime from 39s to
3s.

diff -r 0f6594b0a4e2 -r fb4639d5268e contrib/import-checker.py
--- a/contrib/import-checker.py	Fri Mar 27 19:27:19 2015 -0500
+++ b/contrib/import-checker.py	Fri Mar 27 23:52:23 2015 -0500
@@ -166,22 +166,21 @@
 def cyclekey(names):
     return tuple(sorted(names))
 
-def check_one_mod(mod, imports, path=None, ignore=None):
-    if path is None:
-        path = []
-    if ignore is None:
-        ignore = []
-    path = path + [mod]
-    for i in sorted(imports.get(mod, [])):
-        if i not in stdlib_modules and not i.startswith('mercurial.'):
-            i = mod.rsplit('.', 1)[0] + '.' + i
-        if i in path:
-            firstspot = path.index(i)
-            cycle = path[firstspot:]
-            if cyclekey(cycle) not in ignore:
-                raise CircularImport(cycle)
-            continue
-        check_one_mod(i, imports, path=path, ignore=ignore)
+def checkmod(mod, imports):
+    shortest = {}
+    visit = [[mod]]
+    while visit:
+        path = visit.pop(0)
+        for i in sorted(imports.get(path[-1], [])):
+            if i not in stdlib_modules and not i.startswith('mercurial.'):
+                i = mod.rsplit('.', 1)[0] + '.' + i
+            if len(path) < shortest.get(i, 1000):
+                shortest[i] = len(path)
+                if i in path:
+                    if i == path[0]:
+                        raise CircularImport(path)
+                    continue
+                visit.append(path + [i])
 
 def rotatecycle(cycle):
     """arrange a cycle so that the lexicographically first module listed first
@@ -207,7 +206,7 @@
     cycles = {}
     for mod in sorted(imports.iterkeys()):
         try:
-            check_one_mod(mod, imports, ignore=cycles)
+            checkmod(mod, imports)
         except CircularImport, e:
             cycle = e.args[0]
             cycles[cyclekey(cycle)] = ' -> '.join(rotatecycle(cycle))