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.
--- 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))