add toposort and tests

2 files changed, 143 insertions, 0 deletions

diff --git a/pyramid/tests/test_util.py b/pyramid/tests/test_util.py
index 247b61dad..8b6f47478 100644
--- a/pyramid/tests/test_util.py
+++ b/pyramid/tests/test_util.py
@@ -246,5 +246,71 @@ class Test_WeakOrderedSet(unittest.TestCase):
         self.assertEqual(list(wos), [])
         self.assertEqual(wos.last, None)
 
+class Test_topological_sort(unittest.TestCase):
+    def _callFUT(self, items, partial_order, ignore_missing_partials=True):
+        from pyramid.util import topological_sort
+        return topological_sort(items, partial_order, ignore_missing_partials)
+
+    def test_no_items_no_order(self):
+        result = self._callFUT([], [])
+        self.assertEqual(result, [])
+
+    def test_no_order(self):
+        result = self._callFUT(['a', 'b'], [])
+        self.assertEqual(result, ['a', 'b'])
+
+    def test_partial_order(self):
+        result = self._callFUT(['a', 'b', 'c'], [('b', 'c')])
+        self.assertEqual(result, ['a', 'b', 'c'])
+
+    def test_partial_order2(self):
+        result = self._callFUT(['a', 'b', 'c'], [('a', 'b'), ('b', 'c')])
+        self.assertEqual(result, ['a', 'b', 'c'])
+
+    def test_partial_order3(self):
+        result = self._callFUT(['a', 'b', 'c'], [('a', 'c'), ('b', 'a')])
+        self.assertEqual(result, ['b', 'a', 'c'])
+
+    def test_partial_order4(self):
+        result = self._callFUT(['a', 'b', 'c', 'd'], [('d', 'c')])
+        self.assertEqual(result, ['a', 'b', 'd', 'c'])
+
+    def test_partial_order_missing_partial_a(self):
+        result = self._callFUT(['a', 'b', 'c', 'd'], [('d', 'c'), ('f', 'c')])
+        self.assertEqual(result, ['a', 'b', 'd', 'f', 'c'])
+
+    def test_partial_order_missing_partial_b(self):
+        result = self._callFUT(['a', 'b', 'c', 'd'], [('d', 'c'), ('c', 'f')])
+        self.assertEqual(result, ['a', 'b', 'd', 'c', 'f'])
+
+    def test_cycle_direct(self):
+        from pyramid.util import CyclicDependencyError
+        self.assertRaises(
+            CyclicDependencyError,
+            self._callFUT,
+            ['a', 'b', 'c', 'd'], [('c', 'd'), ('d', 'c')])
+
+    def test_cycle_indirect(self):
+        from pyramid.util import CyclicDependencyError
+        self.assertRaises(
+            CyclicDependencyError,
+            self._callFUT,
+            ['a', 'b', 'c', 'd', 'e'],
+            [('c', 'd'), ('d', 'e'), ('e', 'c')])
+
+class TestCyclicDependencyError(unittest.TestCase):
+    def _makeOne(self, cycles):
+        from pyramid.util import CyclicDependencyError
+        return CyclicDependencyError(cycles)
+
+    def test___str__(self):
+        exc = self._makeOne({'a':['c', 'd'], 'c':['a']})
+        result = str(exc)
+        self.assertEqual(result,
+                         "'a' depends on ['c', 'd']; 'c' depends on ['a']")
+
+def reraise(exc):
+    raise exc
+
 class Dummy(object):
     pass
diff --git a/pyramid/util.py b/pyramid/util.py
index 7fd1b0dc6..fa885b81e 100644
--- a/pyramid/util.py
+++ b/pyramid/util.py
@@ -206,3 +206,80 @@ class WeakOrderedSet(object):
         if self._order:
             oid = self._order[-1]
             return self._items[oid]()
+
+def topological_sort(items, partial_order, ignore_missing_partials=True):
+    """
+    Stolen from http://www.bitinformation.com/art/python_topsort.html
+    (modified to sort initial roots in items order, and to ignore missing
+    partials).
+
+    Given the example list of items ['item2', 'item3', 'item1',
+    'item4'] and a 'partial order' list in the form [(item1, item2),
+    (item2, item3)], where the example tuples indicate that 'item1'
+    should precede 'item2' and 'item2' should precede 'item3', return
+    the sorted list of items ['item1', 'item2', 'item3', 'item4'].
+    Note that since 'item4' is not mentioned in the partial ordering
+    list, it will be at an arbitrary position in the returned list.
+    """
+    def add_node(graph, node, roots):
+        if not graph.has_key(node):
+            roots.append(node)
+            graph[node] = [0] # 0 = number of arcs coming into this node
+
+    def add_arc(graph, fromnode, tonode, roots):
+        graph[fromnode].append(tonode)
+        graph[tonode][0] = graph[tonode][0] + 1
+        if tonode in roots:
+            roots.remove(tonode)
+
+    graph = {}
+    roots = []
+
+    for v in items:
+        add_node(graph, v, roots)
+
+    for a, b in partial_order:
+        if ignore_missing_partials:
+            # don't fail if a value is present in the partial_order
+            # list but missing in items.  In this mode, we fake up a
+            # value instead of raising a KeyError when trying to use
+            # add_arc.  The result will contain the faked item.
+            if not graph.has_key(a):
+                add_node(graph, a, roots)
+            elif not graph.has_key(b):
+                add_node(graph, b, roots)
+        add_arc(graph, a, b, roots)
+
+    sorted = []
+
+    while roots:
+        root = roots.pop(0)
+        sorted.append(root)
+        for child in graph[root][1:]:
+            graph[child][0] = graph[child][0] - 1
+            if graph[child][0] == 0:
+                roots.insert(0, child)
+        del graph[root]
+
+    if graph:
+        # loop in input
+        cycledeps = {}
+        for k, v in graph.items():
+            cycledeps[k] = v[1:]
+        raise CyclicDependencyError(cycledeps)
+
+    return sorted
+
+class CyclicDependencyError(ConfigurationError):
+    def __init__(self, cycles):
+        self.cycles = cycles
+
+    def __str__(self):
+        L = []
+        cycles = self.cycles
+        for cycle in cycles:
+            dependent = cycle
+            dependees = cycles[cycle]
+            L.append('%r depends on %r' % (dependent, dependees))
+        msg = '; '.join(L)
+        return msg