Mercurial > hg
changeset 24490:fb4639d5268e
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.
author | Matt Mackall <mpm@selenic.com> |
---|---|
date | Fri, 27 Mar 2015 23:52:23 -0500 |
parents | 0f6594b0a4e2 |
children | 784b278b349c |
files | contrib/import-checker.py |
diffstat | 1 files changed, 16 insertions(+), 17 deletions(-) [+] |
line wrap: on
line diff
--- 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))