Mercurial > hg > config

comparison python/unroll_deps.py @ 153:17310d15ad26

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
alternate method + more tests
author Jeff Hammel <jhammel@mozilla.com>
date Tue, 12 Jul 2011 21:49:40 -0700
parents 8d04ad79ef79
children b86b070fbdd1
comparison
equal deleted inserted replaced
152:8d04ad79ef79 153:17310d15ad26
1 #!/usr/bin/env python 1 #!/usr/bin/env python
2
3 def cycle_check(order, dependencies):
4 """ensure no cyclic dependencies"""
5 order_dict = dict([(j, i) for i, j in enumerate(order)])
6 for package, deps in dependencies.items():
7 index = order_dict[package]
8 for d in deps:
9 assert index > order_dict[d], "Cyclic dependencies detected"
10
2 11
3 def unroll_dependencies(dependencies): 12 def unroll_dependencies(dependencies):
4 """unroll dependencies""" 13 """unroll dependencies"""
5 order = [] 14 order = []
6 15
7 # unroll the dependencies 16 # unroll the dependencies
8 for package, deps in dependencies.items(): 17 for package, deps in dependencies.items():
9 print package, order
10 try: 18 try:
11 index = order.index(package) 19 index = order.index(package)
12 except ValueError: 20 except ValueError:
13 order.append(package) 21 order.append(package)
14 index = len(order) - 1 22 index = len(order) - 1
23 order.insert(index, dep) 31 order.insert(index, dep)
24 except AssertionError: 32 except AssertionError:
25 print reverse_deps 33 print reverse_deps
26 raise 34 raise
27 35
28 # ensure no cyclic dependencies 36 cycle_check(order, dependencies)
29 # XXX should do this first 37 return order
30 order_dict = dict([(j, i) for i, j in enumerate(order)])
31 for package, deps in dependencies.items():
32 index = order_dict[package]
33 for d in deps:
34 assert index > order_dict[d], "Cyclic dependencies detected"
35 38
39 def unroll_dependencies2(dependencies):
40 """a variation"""
41 order = []
42
43 # flatten all
44 packages = set(dependencies.keys())
45 for deps in dependencies.values():
46 packages.update(deps)
47
48 while len(order) != len(packages):
49
50 for package in packages.difference(order):
51 if dependencies.get(package, set()).issubset(order):
52 order.append(package)
53 break
54 else:
55 raise AssertionError("Cyclic dependencies detected")
56
57 cycle_check(order, dependencies)
58
36 return order 59 return order
37 60
38 if __name__ == '__main__': 61 if __name__ == '__main__':
39 deps = {'packageA': set(['packageB', 'packageC', 'packageF']), 62 deps = {'packageA': set(['packageB', 'packageC', 'packageF']),
40 'packageB': set(['packageC', 'packageD', 'packageE', 'packageG']), 63 'packageB': set(['packageC', 'packageD', 'packageE', 'packageG']),
42 'packageE': set(['packageF', 'packageG']), 65 'packageE': set(['packageF', 'packageG']),
43 'packageF': set(['packageG']), 66 'packageF': set(['packageG']),
44 'packageX': set(['packageA', 'packageG'])} 67 'packageX': set(['packageA', 'packageG'])}
45 unrolled = unroll_dependencies(deps) 68 unrolled = unroll_dependencies(deps)
46 print unrolled 69 print unrolled
70
71 unrolled = unroll_dependencies2(deps)
72 print unrolled
73
74 # ensure cycle check works
75 deps['packageD'] = set(['packageX'])
76 try:
77 unroll_dependencies(deps)
78 raise AssertionError("Missed a cyclic dependency!")
79 except AssertionError:
80 pass
81
82 try:
83 unroll_dependencies2(deps)
84 raise AssertionError("Missed a cyclic dependency!")
85 except AssertionError:
86 pass