# HG changeset patch
# User Jeff Hammel <jhammel@mozilla.com>
# Date 1310532580 25200
# Node ID 17310d15ad260c60764d2bd0c30688ea99c54847
# Parent  8d04ad79ef7926cbd53d0a24955dcdd79d521c28
alternate method + more tests

diff -r 8d04ad79ef79 -r 17310d15ad26 python/unroll_deps.py
--- a/python/unroll_deps.py	Tue Jul 12 20:17:10 2011 -0700
+++ b/python/unroll_deps.py	Tue Jul 12 21:49:40 2011 -0700
@@ -1,12 +1,20 @@
 #!/usr/bin/env python 
 
+def cycle_check(order, dependencies):
+    """ensure no cyclic dependencies"""
+    order_dict = dict([(j, i) for i, j in enumerate(order)])
+    for package, deps in dependencies.items():
+        index = order_dict[package]
+        for d in deps:
+            assert index > order_dict[d], "Cyclic dependencies detected"
+
+
 def unroll_dependencies(dependencies):
     """unroll dependencies"""
     order = []
 
     # unroll the dependencies
     for package, deps in dependencies.items():
-        print package, order
         try:
             index = order.index(package)
         except ValueError:
@@ -25,14 +33,29 @@
                 print reverse_deps
                 raise
 
-    # ensure no cyclic dependencies
-    # XXX should do this first
-    order_dict = dict([(j, i) for i, j in enumerate(order)])
-    for package, deps in dependencies.items():
-        index = order_dict[package]
-        for d in deps:
-            assert index > order_dict[d], "Cyclic dependencies detected"
+    cycle_check(order, dependencies)
+    return order
+
+def unroll_dependencies2(dependencies):
+    """a variation"""
+    order = []
+
+    # flatten all
+    packages = set(dependencies.keys())
+    for deps in dependencies.values():
+        packages.update(deps)
 
+    while len(order) != len(packages):
+
+        for package in packages.difference(order):
+            if dependencies.get(package, set()).issubset(order):
+                order.append(package)
+                break
+        else:
+            raise AssertionError("Cyclic dependencies detected")
+
+    cycle_check(order, dependencies)
+    
     return order
 
 if __name__ == '__main__':
@@ -44,3 +67,20 @@
             'packageX': set(['packageA', 'packageG'])}
     unrolled = unroll_dependencies(deps)
     print unrolled
+
+    unrolled = unroll_dependencies2(deps)
+    print unrolled
+
+    # ensure cycle check works
+    deps['packageD'] = set(['packageX'])
+    try:
+        unroll_dependencies(deps)
+        raise AssertionError("Missed a cyclic dependency!")
+    except AssertionError:
+        pass
+        
+    try:
+        unroll_dependencies2(deps)
+        raise AssertionError("Missed a cyclic dependency!")
+    except AssertionError:
+        pass