annotate python/unroll_deps.py @ 682:3fe1024377ca

STUB: python/unroll_deps.py
author Jeff Hammel <k0scist@gmail.com>
date Tue, 13 May 2014 13:02:45 -0700
parents bc1f4762027b
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
679
da62e6411ab7 STUB: python/unroll_deps.py
Jeff Hammel <k0scist@gmail.com>
parents: 155
diff changeset
1 #!/usr/bin/env python
149
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
2
682
3fe1024377ca STUB: python/unroll_deps.py
Jeff Hammel <k0scist@gmail.com>
parents: 681
diff changeset
3 """
3fe1024377ca STUB: python/unroll_deps.py
Jeff Hammel <k0scist@gmail.com>
parents: 681
diff changeset
4 unroll a set of dependencies
3fe1024377ca STUB: python/unroll_deps.py
Jeff Hammel <k0scist@gmail.com>
parents: 681
diff changeset
5 """
3fe1024377ca STUB: python/unroll_deps.py
Jeff Hammel <k0scist@gmail.com>
parents: 681
diff changeset
6
3fe1024377ca STUB: python/unroll_deps.py
Jeff Hammel <k0scist@gmail.com>
parents: 681
diff changeset
7 import sys
3fe1024377ca STUB: python/unroll_deps.py
Jeff Hammel <k0scist@gmail.com>
parents: 681
diff changeset
8
153
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
9 def cycle_check(order, dependencies):
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
10 """ensure no cyclic dependencies"""
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
11 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
12 for package, deps in dependencies.items():
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
13 index = order_dict[package]
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
14 for d in deps:
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
15 assert index > order_dict[d], "Cyclic dependencies detected"
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
16
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
17
149
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
18 def unroll_dependencies(dependencies):
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
19 """unroll dependencies"""
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
20 order = []
151
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
21
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
22 # unroll the dependencies
149
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
23 for package, deps in dependencies.items():
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 index = order.index(package)
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
26 except ValueError:
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
27 order.append(package)
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
28 index = len(order) - 1
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
29 for dep in deps:
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
30 try:
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
31 dep_index = order.index(dep)
151
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
32 if dep_index > index:
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
33 order.insert(dep_index+1, package)
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
34 order.pop(index)
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
35 index = dep_index
149
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
36 except ValueError:
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
37 order.insert(index, dep)
151
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
38
153
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
39 cycle_check(order, dependencies)
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
40 return order
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
41
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
42 def unroll_dependencies2(dependencies):
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
43 """a variation"""
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
44 order = []
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
45
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
46 # flatten all
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
47 packages = set(dependencies.keys())
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
48 for deps in dependencies.values():
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
49 packages.update(deps)
151
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
50
153
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
51 while len(order) != len(packages):
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
52
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
53 for package in packages.difference(order):
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
54 if dependencies.get(package, set()).issubset(order):
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
55 order.append(package)
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
56 break
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
57 else:
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
58 raise AssertionError("Cyclic dependencies detected")
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
59
679
da62e6411ab7 STUB: python/unroll_deps.py
Jeff Hammel <k0scist@gmail.com>
parents: 155
diff changeset
60 cycle_check(order, dependencies) # sanity
da62e6411ab7 STUB: python/unroll_deps.py
Jeff Hammel <k0scist@gmail.com>
parents: 155
diff changeset
61
149
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
62 return order
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
63
682
3fe1024377ca STUB: python/unroll_deps.py
Jeff Hammel <k0scist@gmail.com>
parents: 681
diff changeset
64
3fe1024377ca STUB: python/unroll_deps.py
Jeff Hammel <k0scist@gmail.com>
parents: 681
diff changeset
65 ### testing and CLI
3fe1024377ca STUB: python/unroll_deps.py
Jeff Hammel <k0scist@gmail.com>
parents: 681
diff changeset
66
3fe1024377ca STUB: python/unroll_deps.py
Jeff Hammel <k0scist@gmail.com>
parents: 681
diff changeset
67 def main(args=sys.argv[:1]):
681
bc1f4762027b STUB: python/unroll_deps.py
Jeff Hammel <k0scist@gmail.com>
parents: 679
diff changeset
68
bc1f4762027b STUB: python/unroll_deps.py
Jeff Hammel <k0scist@gmail.com>
parents: 679
diff changeset
69 # testing set of dependencies
151
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
70 deps = {'packageA': set(['packageB', 'packageC', 'packageF']),
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
71 'packageB': set(['packageC', 'packageD', 'packageE', 'packageG']),
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
72 'packageC': set(['packageE']),
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
73 'packageE': set(['packageF', 'packageG']),
f89c3615b414 this is how its done
Jeff Hammel <jhammel@mozilla.com>
parents: 150
diff changeset
74 'packageF': set(['packageG']),
152
8d04ad79ef79 another test
Jeff Hammel <jhammel@mozilla.com>
parents: 151
diff changeset
75 'packageX': set(['packageA', 'packageG'])}
149
05e461e4b409 add an unroll-deps example prog
Jeff Hammel <jhammel@mozilla.com>
parents:
diff changeset
76 unrolled = unroll_dependencies(deps)
681
bc1f4762027b STUB: python/unroll_deps.py
Jeff Hammel <k0scist@gmail.com>
parents: 679
diff changeset
77 print ('{}'.format(unrolled))
153
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 unrolled = unroll_dependencies2(deps)
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
80 print unrolled
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 # ensure cycle check works
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
83 deps['packageD'] = set(['packageX'])
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
84 try:
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
85 unroll_dependencies(deps)
155
f7cfd58eafe6 raise the correct exception
Jeff Hammel <jhammel@mozilla.com>
parents: 154
diff changeset
86 raise Exception("Missed a cyclic dependency!")
153
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
87 except AssertionError:
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
88 pass
682
3fe1024377ca STUB: python/unroll_deps.py
Jeff Hammel <k0scist@gmail.com>
parents: 681
diff changeset
89
153
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
90 try:
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
91 unroll_dependencies2(deps)
155
f7cfd58eafe6 raise the correct exception
Jeff Hammel <jhammel@mozilla.com>
parents: 154
diff changeset
92 raise Exception("Missed a cyclic dependency!")
153
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
93 except AssertionError:
17310d15ad26 alternate method + more tests
Jeff Hammel <jhammel@mozilla.com>
parents: 152
diff changeset
94 pass
682
3fe1024377ca STUB: python/unroll_deps.py
Jeff Hammel <k0scist@gmail.com>
parents: 681
diff changeset
95
3fe1024377ca STUB: python/unroll_deps.py
Jeff Hammel <k0scist@gmail.com>
parents: 681
diff changeset
96 if __name__ == '__main__':
3fe1024377ca STUB: python/unroll_deps.py
Jeff Hammel <k0scist@gmail.com>
parents: 681
diff changeset
97 main()