Mercurial > hg > config

annotate 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
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
149
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
1 #!/usr/bin/env python
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
2
153
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
3 def cycle_check(order, dependencies):
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
4 """ensure no cyclic dependencies"""
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
5 order_dict = dict([(j, i) for i, j in enumerate(order)])
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
6 for package, deps in dependencies.items():
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
7 index = order_dict[package]
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
8 for d in deps:
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
9 assert index > order_dict[d], "Cyclic dependencies detected"
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
10
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
11
149
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
12 def unroll_dependencies(dependencies):
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
13 """unroll dependencies"""
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
14 order = []
151
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
15
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
16 # unroll the dependencies
149
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
17 for package, deps in dependencies.items():
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
18 try:
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
19 index = order.index(package)
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
20 except ValueError:
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
21 order.append(package)
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
22 index = len(order) - 1
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
23 for dep in deps:
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
24 try:
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
25 dep_index = order.index(dep)
151
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
26 if dep_index > index:
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
27 order.insert(dep_index+1, package)
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
28 order.pop(index)
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
29 index = dep_index
149
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
30 except ValueError:
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
31 order.insert(index, dep)
151
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
32 except AssertionError:
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
33 print reverse_deps
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
34 raise
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
35
153
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
36 cycle_check(order, dependencies)
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
37 return order
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
38
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
39 def unroll_dependencies2(dependencies):
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
40 """a variation"""
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
41 order = []
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
42
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
43 # flatten all
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
44 packages = set(dependencies.keys())
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
45 for deps in dependencies.values():
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
46 packages.update(deps)
151
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
47
153
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
48 while len(order) != len(packages):
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
49
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
50 for package in packages.difference(order):
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
51 if dependencies.get(package, set()).issubset(order):
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
52 order.append(package)
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
53 break
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
54 else:
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
55 raise AssertionError("Cyclic dependencies detected")
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
56
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
57 cycle_check(order, dependencies)
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
58
149
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
59 return order
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
60
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
61 if __name__ == '__main__':
151
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
62 deps = {'packageA': set(['packageB', 'packageC', 'packageF']),
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
63 'packageB': set(['packageC', 'packageD', 'packageE', 'packageG']),
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
64 'packageC': set(['packageE']),
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
65 'packageE': set(['packageF', 'packageG']),
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
66 'packageF': set(['packageG']),
152
8d04ad79ef79 another test
Jeff Hammel <jhammel@mozilla.com>
parents: 151
diff changeset
67 'packageX': set(['packageA', 'packageG'])}
149
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
68 unrolled = unroll_dependencies(deps)
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
69 print unrolled
153
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
70
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
71 unrolled = unroll_dependencies2(deps)
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
72 print unrolled
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
73
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
74 # ensure cycle check works
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
75 deps['packageD'] = set(['packageX'])
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
76 try:
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
77 unroll_dependencies(deps)
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
78 raise AssertionError("Missed a cyclic dependency!")
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
79 except AssertionError:
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
80 pass
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
81
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
82 try:
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
83 unroll_dependencies2(deps)
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
84 raise AssertionError("Missed a cyclic dependency!")
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
85 except AssertionError:
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
86 pass