Mercurial > hg > config

annotate python/unroll_deps.py @ 585:1e3b778be7e4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
STUB: .emacs
author Jeff Hammel <k0scist@gmail.com>
date Thu, 23 Jan 2014 11:27:02 -0800
parents f7cfd58eafe6
children da62e6411ab7
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
153
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
33 cycle_check(order, dependencies)
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
34 return order
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
35
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
36 def unroll_dependencies2(dependencies):
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
37 """a variation"""
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
38 order = []
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
39
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
40 # flatten all
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
41 packages = set(dependencies.keys())
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
42 for deps in dependencies.values():
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
43 packages.update(deps)
151
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
44
153
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
45 while len(order) != len(packages):
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
46
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
47 for package in packages.difference(order):
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
48 if dependencies.get(package, set()).issubset(order):
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
49 order.append(package)
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
50 break
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
51 else:
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
52 raise AssertionError("Cyclic dependencies detected")
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
53
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
54 cycle_check(order, dependencies)
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
55
149
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
56 return order
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
57
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
58 if __name__ == '__main__':
151
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
59 deps = {'packageA': set(['packageB', 'packageC', 'packageF']),
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
60 'packageB': set(['packageC', 'packageD', 'packageE', 'packageG']),
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
61 'packageC': set(['packageE']),
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
62 'packageE': set(['packageF', 'packageG']),
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
63 'packageF': set(['packageG']),
152
8d04ad79ef79 another test
Jeff Hammel <jhammel@mozilla.com>
parents: 151
diff changeset
64 'packageX': set(['packageA', 'packageG'])}
149
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
65 unrolled = unroll_dependencies(deps)
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
66 print unrolled
153
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
67
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
68 unrolled = unroll_dependencies2(deps)
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
69 print unrolled
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 # ensure cycle check works
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
72 deps['packageD'] = set(['packageX'])
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
73 try:
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
74 unroll_dependencies(deps)
155
f7cfd58eafe6 raise the correct exception
Jeff Hammel <jhammel@mozilla.com>
parents: 154
diff changeset
75 raise Exception("Missed a cyclic dependency!")
153
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
76 except AssertionError:
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
77 pass
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
78
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
79 try:
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
80 unroll_dependencies2(deps)
155
f7cfd58eafe6 raise the correct exception
Jeff Hammel <jhammel@mozilla.com>
parents: 154
diff changeset
81 raise Exception("Missed a cyclic dependency!")
153
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
82 except AssertionError:
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
83 pass