- Move ``TopologicalSorter`` from ``pyramid.config.util`` to ``pyramid.util``,

  move ``CyclicDependencyError`` from ``pyramid.config.util`` to
  ``pyramid.exceptions``, rename ``Singleton`` to ``Sentinel`` and move from
  ``pyramid.config.util`` to ``pyramid.config.util``; this is in an effort to
  move that stuff that may be an API one day out of ``pyramid.config.util,
  because that package should never be imported from non-Pyramid code.
  TopologicalSorter is still not an API, but may become one.

8 files changed, 466 insertions, 421 deletions

diff --git a/CHANGES.txt b/CHANGES.txt
index 86a9e8b50..298bddf7a 100644
--- a/CHANGES.txt
+++ b/CHANGES.txt
@@ -38,6 +38,17 @@ Bug Fixes
   be unmolested on the way out.  See
   https://github.com/Pylons/pyramid/issues/709
 
+Internals
+---------
+
+- Move ``TopologicalSorter`` from ``pyramid.config.util`` to ``pyramid.util``,
+  move ``CyclicDependencyError`` from ``pyramid.config.util`` to
+  ``pyramid.exceptions``, rename ``Singleton`` to ``Sentinel`` and move from
+  ``pyramid.config.util`` to ``pyramid.config.util``; this is in an effort to
+  move that stuff that may be an API one day out of ``pyramid.config.util,
+  because that package should never be imported from non-Pyramid code.
+  TopologicalSorter is still not an API, but may become one.
+
 1.4a3 (2012-10-26)
 ==================
 
diff --git a/pyramid/config/util.py b/pyramid/config/util.py
index a4df44408..1c6e1ca15 100644
--- a/pyramid/config/util.py
+++ b/pyramid/config/util.py
@@ -12,8 +12,8 @@ from pyramid.compat import (
     )
 
 from pyramid.exceptions import ConfigurationError
-
 from pyramid.registry import predvalseq
+from pyramid.util import TopologicalSorter
 
 from hashlib import md5
 
@@ -72,156 +72,6 @@ def as_sorted_tuple(val):
 # under = after
 # over = before
 
-class Singleton(object):
-    def __init__(self, repr):
-        self.repr = repr
-
-    def __repr__(self):
-        return self.repr
-
-FIRST = Singleton('FIRST')
-LAST = Singleton('LAST')
-
-class TopologicalSorter(object):
-    def __init__(
-        self,
-        default_before=LAST,
-        default_after=None,
-        first=FIRST,
-        last=LAST,
-        ):
-        self.names = []
-        self.req_before = set()
-        self.req_after = set()
-        self.name2before = {}
-        self.name2after = {}
-        self.name2val = {}
-        self.order = []
-        self.default_before = default_before
-        self.default_after = default_after
-        self.first = first
-        self.last = last
-
-    def remove(self, name):
-        self.names.remove(name)
-        del self.name2val[name]
-        after = self.name2after.pop(name, [])
-        if after:
-            self.req_after.remove(name)
-            for u in after:
-                self.order.remove((u, name))
-        before = self.name2before.pop(name, [])
-        if before:
-            self.req_before.remove(name)
-            for u in before:
-                self.order.remove((name, u))
-                
-    def add(self, name, val, after=None, before=None):
-        if name in self.names:
-            self.remove(name)
-        self.names.append(name)
-        self.name2val[name] = val
-        if after is None and before is None:
-            before = self.default_before
-            after = self.default_after
-        if after is not None:
-            if not is_nonstr_iter(after):
-                after = (after,)
-            self.name2after[name] = after
-            self.order += [(u, name) for u in after]
-            self.req_after.add(name)
-        if before is not None:
-            if not is_nonstr_iter(before):
-                before = (before,)
-            self.name2before[name] = before
-            self.order += [(name, o) for o in before]
-            self.req_before.add(name)
-
-    def sorted(self):
-        order = [(self.first, self.last)]
-        roots = []
-        graph = {}
-        names = [self.first, self.last]
-        names.extend(self.names)
-
-        for a, b in self.order:
-            order.append((a, b))
-
-        def add_node(node):
-            if not node in graph:
-                roots.append(node)
-                graph[node] = [0] # 0 = number of arcs coming into this node
-
-        def add_arc(fromnode, tonode):
-            graph[fromnode].append(tonode)
-            graph[tonode][0] += 1
-            if tonode in roots:
-                roots.remove(tonode)
-
-        for name in names:
-            add_node(name)
-
-        has_before, has_after = set(), set()
-        for a, b in order:
-            if a in names and b in names: # deal with missing dependencies
-                add_arc(a, b)
-                has_before.add(a)
-                has_after.add(b)
-
-        if not self.req_before.issubset(has_before):
-            raise ConfigurationError(
-                'Unsatisfied before dependencies: %s'
-                % (', '.join(sorted(self.req_before - has_before)))
-            )
-        if not self.req_after.issubset(has_after):
-            raise ConfigurationError(
-                'Unsatisfied after dependencies: %s'
-                % (', '.join(sorted(self.req_after - has_after)))
-            )
-
-        sorted_names = []
-
-        while roots:
-            root = roots.pop(0)
-            sorted_names.append(root)
-            children = graph[root][1:]
-            for child in children:
-                arcs = graph[child][0]
-                arcs -= 1
-                graph[child][0] = arcs 
-                if arcs == 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)
-
-        result = []
-
-        for name in sorted_names:
-            if name in self.names:
-                result.append((name, self.name2val[name]))
-
-        return result
-
-class CyclicDependencyError(Exception):
-    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 sorts before %r' % (dependent, dependees))
-        msg = 'Implicit ordering cycle:' + '; '.join(L)
-        return msg
-
 class PredicateList(object):
     
     def __init__(self):
diff --git a/pyramid/exceptions.py b/pyramid/exceptions.py
index 04b6e20b7..1c8f99f62 100644
--- a/pyramid/exceptions.py
+++ b/pyramid/exceptions.py
@@ -60,3 +60,21 @@ class ConfigurationExecutionError(ConfigurationError):
 
     def __str__(self):
         return "%s: %s\n  in:\n  %s" % (self.etype, self.evalue, self.info)
+
+class CyclicDependencyError(Exception):
+    """ The exception raised when the Pyramid topological sorter detects a
+    cyclic dependency."""
+    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 sorts before %r' % (dependent, dependees))
+        msg = 'Implicit ordering cycle:' + '; '.join(L)
+        return msg
+
+
diff --git a/pyramid/tests/test_config/test_tweens.py b/pyramid/tests/test_config/test_tweens.py
index 8853b6899..9c3433468 100644
--- a/pyramid/tests/test_config/test_tweens.py
+++ b/pyramid/tests/test_config/test_tweens.py
@@ -392,7 +392,7 @@ class TestTweens(unittest.TestCase):
         self.assertRaises(ConfigurationError, tweens.implicit)
 
     def test_implicit_ordering_conflict_direct(self):
-        from pyramid.config.util import CyclicDependencyError
+        from pyramid.exceptions import CyclicDependencyError
         tweens = self._makeOne()
         add = tweens.add_implicit
         add('browserid', 'browserid_factory')
@@ -400,7 +400,7 @@ class TestTweens(unittest.TestCase):
         self.assertRaises(CyclicDependencyError, tweens.implicit)
 
     def test_implicit_ordering_conflict_indirect(self):
-        from pyramid.config.util import CyclicDependencyError
+        from pyramid.exceptions import CyclicDependencyError
         tweens = self._makeOne()
         add = tweens.add_implicit
         add('browserid', 'browserid_factory')
diff --git a/pyramid/tests/test_config/test_util.py b/pyramid/tests/test_config/test_util.py
index 13cb27526..8c3cd7455 100644
--- a/pyramid/tests/test_config/test_util.py
+++ b/pyramid/tests/test_config/test_util.py
@@ -396,274 +396,6 @@ class TestActionInfo(unittest.TestCase):
         self.assertEqual(str(inst),
                          "Line 0 of file filename:\n       linerepr  ")
 
-class TestTopologicalSorter(unittest.TestCase):
-    def _makeOne(self, *arg, **kw):
-        from pyramid.config.util import TopologicalSorter
-        return TopologicalSorter(*arg, **kw)
-
-    def test_remove(self):
-        inst = self._makeOne()
-        inst.names.append('name')
-        inst.name2val['name'] = 1
-        inst.req_after.add('name')
-        inst.req_before.add('name')
-        inst.name2after['name'] = ('bob',)
-        inst.name2before['name'] = ('fred',)
-        inst.order.append(('bob', 'name'))
-        inst.order.append(('name', 'fred'))
-        inst.remove('name')
-        self.assertFalse(inst.names)
-        self.assertFalse(inst.req_before)
-        self.assertFalse(inst.req_after)
-        self.assertFalse(inst.name2before)
-        self.assertFalse(inst.name2after)
-        self.assertFalse(inst.name2val)
-        self.assertFalse(inst.order)
-
-    def test_add(self):
-        from pyramid.config.util import LAST
-        sorter = self._makeOne()
-        sorter.add('name', 'factory')
-        self.assertEqual(sorter.names, ['name'])
-        self.assertEqual(sorter.name2val,
-                         {'name':'factory'})
-        self.assertEqual(sorter.order, [('name', LAST)])
-        sorter.add('name2', 'factory2')
-        self.assertEqual(sorter.names, ['name',  'name2'])
-        self.assertEqual(sorter.name2val,
-                         {'name':'factory', 'name2':'factory2'})
-        self.assertEqual(sorter.order,
-                         [('name', LAST), ('name2', LAST)])
-        sorter.add('name3', 'factory3', before='name2')
-        self.assertEqual(sorter.names,
-                         ['name',  'name2', 'name3'])
-        self.assertEqual(sorter.name2val,
-                         {'name':'factory', 'name2':'factory2',
-                          'name3':'factory3'})
-        self.assertEqual(sorter.order,
-                         [('name', LAST), ('name2', LAST),
-                          ('name3', 'name2')])
-
-    def test_sorted_ordering_1(self):
-        sorter = self._makeOne()
-        sorter.add('name1', 'factory1')
-        sorter.add('name2', 'factory2')
-        self.assertEqual(sorter.sorted(),
-                         [
-                             ('name1', 'factory1'),
-                             ('name2', 'factory2'),
-                             ])
-
-    def test_sorted_ordering_2(self):
-        from pyramid.config.util import FIRST
-        sorter = self._makeOne()
-        sorter.add('name1', 'factory1')
-        sorter.add('name2', 'factory2', after=FIRST)
-        self.assertEqual(sorter.sorted(),
-                         [
-                             ('name2', 'factory2'),
-                             ('name1', 'factory1'),
-                             ])
-
-    def test_sorted_ordering_3(self):
-        from pyramid.config.util import FIRST
-        sorter = self._makeOne()
-        add = sorter.add
-        add('auth', 'auth_factory', after='browserid')
-        add('dbt', 'dbt_factory') 
-        add('retry', 'retry_factory', before='txnmgr', after='exceptionview')
-        add('browserid', 'browserid_factory')
-        add('txnmgr', 'txnmgr_factory', after='exceptionview')
-        add('exceptionview', 'excview_factory', after=FIRST)
-        self.assertEqual(sorter.sorted(),
-                         [
-                             ('exceptionview', 'excview_factory'),
-                             ('retry', 'retry_factory'),
-                             ('txnmgr', 'txnmgr_factory'),
-                             ('dbt', 'dbt_factory'),
-                             ('browserid', 'browserid_factory'),
-                             ('auth', 'auth_factory'),
-                             ])
-
-    def test_sorted_ordering_4(self):
-        from pyramid.config.util import FIRST
-        sorter = self._makeOne()
-        add = sorter.add
-        add('exceptionview', 'excview_factory', after=FIRST)
-        add('auth', 'auth_factory', after='browserid')
-        add('retry', 'retry_factory', before='txnmgr', after='exceptionview')
-        add('browserid', 'browserid_factory')
-        add('txnmgr', 'txnmgr_factory', after='exceptionview')
-        add('dbt', 'dbt_factory') 
-        self.assertEqual(sorter.sorted(),
-                         [
-                             ('exceptionview', 'excview_factory'),
-                             ('retry', 'retry_factory'),
-                             ('txnmgr', 'txnmgr_factory'),
-                             ('browserid', 'browserid_factory'),
-                             ('auth', 'auth_factory'),
-                             ('dbt', 'dbt_factory'),
-                             ])
-
-    def test_sorted_ordering_5(self):
-        from pyramid.config.util import LAST, FIRST
-        sorter = self._makeOne()
-        add = sorter.add
-        add('exceptionview', 'excview_factory')
-        add('auth', 'auth_factory', after=FIRST)
-        add('retry', 'retry_factory', before='txnmgr', after='exceptionview')
-        add('browserid', 'browserid_factory', after=FIRST)
-        add('txnmgr', 'txnmgr_factory', after='exceptionview', before=LAST)
-        add('dbt', 'dbt_factory') 
-        self.assertEqual(sorter.sorted(),
-                         [
-                             ('browserid', 'browserid_factory'),
-                             ('auth', 'auth_factory'),
-                             ('exceptionview', 'excview_factory'),
-                             ('retry', 'retry_factory'),
-                             ('txnmgr', 'txnmgr_factory'), 
-                             ('dbt', 'dbt_factory'),
-                             ])
-
-    def test_sorted_ordering_missing_before_partial(self):
-        from pyramid.exceptions import ConfigurationError
-        sorter = self._makeOne()
-        add = sorter.add
-        add('dbt', 'dbt_factory')
-        add('auth', 'auth_factory', after='browserid')
-        add('retry', 'retry_factory', before='txnmgr', after='exceptionview')
-        add('browserid', 'browserid_factory')
-        self.assertRaises(ConfigurationError, sorter.sorted)
-
-    def test_sorted_ordering_missing_after_partial(self):
-        from pyramid.exceptions import ConfigurationError
-        sorter = self._makeOne()
-        add = sorter.add
-        add('dbt', 'dbt_factory')
-        add('auth', 'auth_factory', after='txnmgr')
-        add('retry', 'retry_factory', before='dbt', after='exceptionview')
-        add('browserid', 'browserid_factory')
-        self.assertRaises(ConfigurationError, sorter.sorted)
-
-    def test_sorted_ordering_missing_before_and_after_partials(self):
-        from pyramid.exceptions import ConfigurationError
-        sorter = self._makeOne()
-        add = sorter.add
-        add('dbt', 'dbt_factory')
-        add('auth', 'auth_factory', after='browserid')
-        add('retry', 'retry_factory', before='foo', after='txnmgr')
-        add('browserid', 'browserid_factory')
-        self.assertRaises(ConfigurationError, sorter.sorted)
-
-    def test_sorted_ordering_missing_before_partial_with_fallback(self):
-        from pyramid.config.util import LAST
-        sorter = self._makeOne()
-        add = sorter.add
-        add('exceptionview', 'excview_factory', before=LAST)
-        add('auth', 'auth_factory', after='browserid')
-        add('retry', 'retry_factory', before=('txnmgr', LAST),
-                                      after='exceptionview')
-        add('browserid', 'browserid_factory')
-        add('dbt', 'dbt_factory') 
-        self.assertEqual(sorter.sorted(),
-                         [
-                             ('exceptionview', 'excview_factory'),
-                             ('retry', 'retry_factory'),
-                             ('browserid', 'browserid_factory'),
-                             ('auth', 'auth_factory'),
-                             ('dbt', 'dbt_factory'),
-                             ])
-
-    def test_sorted_ordering_missing_after_partial_with_fallback(self):
-        from pyramid.config.util import FIRST
-        sorter = self._makeOne()
-        add = sorter.add
-        add('exceptionview', 'excview_factory', after=FIRST)
-        add('auth', 'auth_factory', after=('txnmgr','browserid'))
-        add('retry', 'retry_factory', after='exceptionview')
-        add('browserid', 'browserid_factory')
-        add('dbt', 'dbt_factory')
-        self.assertEqual(sorter.sorted(),
-                         [
-                             ('exceptionview', 'excview_factory'),
-                             ('retry', 'retry_factory'),
-                             ('browserid', 'browserid_factory'),
-                             ('auth', 'auth_factory'),
-                             ('dbt', 'dbt_factory'),
-                             ])
-
-    def test_sorted_ordering_with_partial_fallbacks(self):
-        from pyramid.config.util import LAST
-        sorter = self._makeOne()
-        add = sorter.add
-        add('exceptionview', 'excview_factory', before=('wontbethere', LAST))
-        add('retry', 'retry_factory', after='exceptionview')
-        add('browserid', 'browserid_factory', before=('wont2', 'exceptionview'))
-        self.assertEqual(sorter.sorted(),
-                         [
-                             ('browserid', 'browserid_factory'),
-                             ('exceptionview', 'excview_factory'),
-                             ('retry', 'retry_factory'),
-                             ])
-
-    def test_sorted_ordering_with_multiple_matching_fallbacks(self):
-        from pyramid.config.util import LAST
-        sorter = self._makeOne()
-        add = sorter.add
-        add('exceptionview', 'excview_factory', before=LAST)
-        add('retry', 'retry_factory', after='exceptionview')
-        add('browserid', 'browserid_factory', before=('retry', 'exceptionview'))
-        self.assertEqual(sorter.sorted(),
-                         [
-                             ('browserid', 'browserid_factory'),
-                             ('exceptionview', 'excview_factory'),
-                             ('retry', 'retry_factory'),
-                             ])
-
-    def test_sorted_ordering_with_missing_fallbacks(self):
-        from pyramid.exceptions import ConfigurationError
-        from pyramid.config.util import LAST
-        sorter = self._makeOne()
-        add = sorter.add
-        add('exceptionview', 'excview_factory', before=LAST)
-        add('retry', 'retry_factory', after='exceptionview')
-        add('browserid', 'browserid_factory', before=('txnmgr', 'auth'))
-        self.assertRaises(ConfigurationError, sorter.sorted)
-
-    def test_sorted_ordering_conflict_direct(self):
-        from pyramid.config.util import CyclicDependencyError
-        sorter = self._makeOne()
-        add = sorter.add
-        add('browserid', 'browserid_factory')
-        add('auth', 'auth_factory', before='browserid', after='browserid')
-        self.assertRaises(CyclicDependencyError, sorter.sorted)
-
-    def test_sorted_ordering_conflict_indirect(self):
-        from pyramid.config.util import CyclicDependencyError
-        sorter = self._makeOne()
-        add = sorter.add
-        add('browserid', 'browserid_factory')
-        add('auth', 'auth_factory', before='browserid')
-        add('dbt', 'dbt_factory', after='browserid', before='auth')
-        self.assertRaises(CyclicDependencyError, sorter.sorted)
-
-class TestSingleton(unittest.TestCase):
-    def test_repr(self):
-        from pyramid.config.util import Singleton
-        r = repr(Singleton('ABC'))
-        self.assertEqual(r, 'ABC')
-
-class TestCyclicDependencyError(unittest.TestCase):
-    def _makeOne(self, cycles):
-        from pyramid.config.util import CyclicDependencyError
-        return CyclicDependencyError(cycles)
-
-    def test___str__(self):
-        exc = self._makeOne({'a':['c', 'd'], 'c':['a']})
-        result = str(exc)
-        self.assertTrue("'a' sorts before ['c', 'd']" in result)
-        self.assertTrue("'c' sorts before ['a']" in result)
-
 class DummyCustomPredicate(object):
     def __init__(self):
         self.__text__ = 'custom predicate'
diff --git a/pyramid/tests/test_exceptions.py b/pyramid/tests/test_exceptions.py
index 773767d89..aa5ebb376 100644
--- a/pyramid/tests/test_exceptions.py
+++ b/pyramid/tests/test_exceptions.py
@@ -74,3 +74,15 @@ class TestConfigurationExecutionError(unittest.TestCase):
         exc = self._makeOne('etype', 'evalue', 'info')
         self.assertEqual(str(exc), 'etype: evalue\n  in:\n  info')
         
+class TestCyclicDependencyError(unittest.TestCase):
+    def _makeOne(self, cycles):
+        from pyramid.exceptions import CyclicDependencyError
+        return CyclicDependencyError(cycles)
+
+    def test___str__(self):
+        exc = self._makeOne({'a':['c', 'd'], 'c':['a']})
+        result = str(exc)
+        self.assertTrue("'a' sorts before ['c', 'd']" in result)
+        self.assertTrue("'c' sorts before ['a']" in result)
+
+
diff --git a/pyramid/tests/test_util.py b/pyramid/tests/test_util.py
index 3d85e18f5..785950230 100644
--- a/pyramid/tests/test_util.py
+++ b/pyramid/tests/test_util.py
@@ -288,6 +288,263 @@ class Test_object_description(unittest.TestCase):
             self._callFUT(inst),
             str(inst)[:100] + ' ... ]')
 
+class TestTopologicalSorter(unittest.TestCase):
+    def _makeOne(self, *arg, **kw):
+        from pyramid.util import TopologicalSorter
+        return TopologicalSorter(*arg, **kw)
+
+    def test_remove(self):
+        inst = self._makeOne()
+        inst.names.append('name')
+        inst.name2val['name'] = 1
+        inst.req_after.add('name')
+        inst.req_before.add('name')
+        inst.name2after['name'] = ('bob',)
+        inst.name2before['name'] = ('fred',)
+        inst.order.append(('bob', 'name'))
+        inst.order.append(('name', 'fred'))
+        inst.remove('name')
+        self.assertFalse(inst.names)
+        self.assertFalse(inst.req_before)
+        self.assertFalse(inst.req_after)
+        self.assertFalse(inst.name2before)
+        self.assertFalse(inst.name2after)
+        self.assertFalse(inst.name2val)
+        self.assertFalse(inst.order)
+
+    def test_add(self):
+        from pyramid.util import LAST
+        sorter = self._makeOne()
+        sorter.add('name', 'factory')
+        self.assertEqual(sorter.names, ['name'])
+        self.assertEqual(sorter.name2val,
+                         {'name':'factory'})
+        self.assertEqual(sorter.order, [('name', LAST)])
+        sorter.add('name2', 'factory2')
+        self.assertEqual(sorter.names, ['name',  'name2'])
+        self.assertEqual(sorter.name2val,
+                         {'name':'factory', 'name2':'factory2'})
+        self.assertEqual(sorter.order,
+                         [('name', LAST), ('name2', LAST)])
+        sorter.add('name3', 'factory3', before='name2')
+        self.assertEqual(sorter.names,
+                         ['name',  'name2', 'name3'])
+        self.assertEqual(sorter.name2val,
+                         {'name':'factory', 'name2':'factory2',
+                          'name3':'factory3'})
+        self.assertEqual(sorter.order,
+                         [('name', LAST), ('name2', LAST),
+                          ('name3', 'name2')])
+
+    def test_sorted_ordering_1(self):
+        sorter = self._makeOne()
+        sorter.add('name1', 'factory1')
+        sorter.add('name2', 'factory2')
+        self.assertEqual(sorter.sorted(),
+                         [
+                             ('name1', 'factory1'),
+                             ('name2', 'factory2'),
+                             ])
+
+    def test_sorted_ordering_2(self):
+        from pyramid.util import FIRST
+        sorter = self._makeOne()
+        sorter.add('name1', 'factory1')
+        sorter.add('name2', 'factory2', after=FIRST)
+        self.assertEqual(sorter.sorted(),
+                         [
+                             ('name2', 'factory2'),
+                             ('name1', 'factory1'),
+                             ])
+
+    def test_sorted_ordering_3(self):
+        from pyramid.util import FIRST
+        sorter = self._makeOne()
+        add = sorter.add
+        add('auth', 'auth_factory', after='browserid')
+        add('dbt', 'dbt_factory') 
+        add('retry', 'retry_factory', before='txnmgr', after='exceptionview')
+        add('browserid', 'browserid_factory')
+        add('txnmgr', 'txnmgr_factory', after='exceptionview')
+        add('exceptionview', 'excview_factory', after=FIRST)
+        self.assertEqual(sorter.sorted(),
+                         [
+                             ('exceptionview', 'excview_factory'),
+                             ('retry', 'retry_factory'),
+                             ('txnmgr', 'txnmgr_factory'),
+                             ('dbt', 'dbt_factory'),
+                             ('browserid', 'browserid_factory'),
+                             ('auth', 'auth_factory'),
+                             ])
+
+    def test_sorted_ordering_4(self):
+        from pyramid.util import FIRST
+        sorter = self._makeOne()
+        add = sorter.add
+        add('exceptionview', 'excview_factory', after=FIRST)
+        add('auth', 'auth_factory', after='browserid')
+        add('retry', 'retry_factory', before='txnmgr', after='exceptionview')
+        add('browserid', 'browserid_factory')
+        add('txnmgr', 'txnmgr_factory', after='exceptionview')
+        add('dbt', 'dbt_factory') 
+        self.assertEqual(sorter.sorted(),
+                         [
+                             ('exceptionview', 'excview_factory'),
+                             ('retry', 'retry_factory'),
+                             ('txnmgr', 'txnmgr_factory'),
+                             ('browserid', 'browserid_factory'),
+                             ('auth', 'auth_factory'),
+                             ('dbt', 'dbt_factory'),
+                             ])
+
+    def test_sorted_ordering_5(self):
+        from pyramid.util import LAST, FIRST
+        sorter = self._makeOne()
+        add = sorter.add
+        add('exceptionview', 'excview_factory')
+        add('auth', 'auth_factory', after=FIRST)
+        add('retry', 'retry_factory', before='txnmgr', after='exceptionview')
+        add('browserid', 'browserid_factory', after=FIRST)
+        add('txnmgr', 'txnmgr_factory', after='exceptionview', before=LAST)
+        add('dbt', 'dbt_factory') 
+        self.assertEqual(sorter.sorted(),
+                         [
+                             ('browserid', 'browserid_factory'),
+                             ('auth', 'auth_factory'),
+                             ('exceptionview', 'excview_factory'),
+                             ('retry', 'retry_factory'),
+                             ('txnmgr', 'txnmgr_factory'), 
+                             ('dbt', 'dbt_factory'),
+                             ])
+
+    def test_sorted_ordering_missing_before_partial(self):
+        from pyramid.exceptions import ConfigurationError
+        sorter = self._makeOne()
+        add = sorter.add
+        add('dbt', 'dbt_factory')
+        add('auth', 'auth_factory', after='browserid')
+        add('retry', 'retry_factory', before='txnmgr', after='exceptionview')
+        add('browserid', 'browserid_factory')
+        self.assertRaises(ConfigurationError, sorter.sorted)
+
+    def test_sorted_ordering_missing_after_partial(self):
+        from pyramid.exceptions import ConfigurationError
+        sorter = self._makeOne()
+        add = sorter.add
+        add('dbt', 'dbt_factory')
+        add('auth', 'auth_factory', after='txnmgr')
+        add('retry', 'retry_factory', before='dbt', after='exceptionview')
+        add('browserid', 'browserid_factory')
+        self.assertRaises(ConfigurationError, sorter.sorted)
+
+    def test_sorted_ordering_missing_before_and_after_partials(self):
+        from pyramid.exceptions import ConfigurationError
+        sorter = self._makeOne()
+        add = sorter.add
+        add('dbt', 'dbt_factory')
+        add('auth', 'auth_factory', after='browserid')
+        add('retry', 'retry_factory', before='foo', after='txnmgr')
+        add('browserid', 'browserid_factory')
+        self.assertRaises(ConfigurationError, sorter.sorted)
+
+    def test_sorted_ordering_missing_before_partial_with_fallback(self):
+        from pyramid.util import LAST
+        sorter = self._makeOne()
+        add = sorter.add
+        add('exceptionview', 'excview_factory', before=LAST)
+        add('auth', 'auth_factory', after='browserid')
+        add('retry', 'retry_factory', before=('txnmgr', LAST),
+                                      after='exceptionview')
+        add('browserid', 'browserid_factory')
+        add('dbt', 'dbt_factory') 
+        self.assertEqual(sorter.sorted(),
+                         [
+                             ('exceptionview', 'excview_factory'),
+                             ('retry', 'retry_factory'),
+                             ('browserid', 'browserid_factory'),
+                             ('auth', 'auth_factory'),
+                             ('dbt', 'dbt_factory'),
+                             ])
+
+    def test_sorted_ordering_missing_after_partial_with_fallback(self):
+        from pyramid.util import FIRST
+        sorter = self._makeOne()
+        add = sorter.add
+        add('exceptionview', 'excview_factory', after=FIRST)
+        add('auth', 'auth_factory', after=('txnmgr','browserid'))
+        add('retry', 'retry_factory', after='exceptionview')
+        add('browserid', 'browserid_factory')
+        add('dbt', 'dbt_factory')
+        self.assertEqual(sorter.sorted(),
+                         [
+                             ('exceptionview', 'excview_factory'),
+                             ('retry', 'retry_factory'),
+                             ('browserid', 'browserid_factory'),
+                             ('auth', 'auth_factory'),
+                             ('dbt', 'dbt_factory'),
+                             ])
+
+    def test_sorted_ordering_with_partial_fallbacks(self):
+        from pyramid.util import LAST
+        sorter = self._makeOne()
+        add = sorter.add
+        add('exceptionview', 'excview_factory', before=('wontbethere', LAST))
+        add('retry', 'retry_factory', after='exceptionview')
+        add('browserid', 'browserid_factory', before=('wont2', 'exceptionview'))
+        self.assertEqual(sorter.sorted(),
+                         [
+                             ('browserid', 'browserid_factory'),
+                             ('exceptionview', 'excview_factory'),
+                             ('retry', 'retry_factory'),
+                             ])
+
+    def test_sorted_ordering_with_multiple_matching_fallbacks(self):
+        from pyramid.util import LAST
+        sorter = self._makeOne()
+        add = sorter.add
+        add('exceptionview', 'excview_factory', before=LAST)
+        add('retry', 'retry_factory', after='exceptionview')
+        add('browserid', 'browserid_factory', before=('retry', 'exceptionview'))
+        self.assertEqual(sorter.sorted(),
+                         [
+                             ('browserid', 'browserid_factory'),
+                             ('exceptionview', 'excview_factory'),
+                             ('retry', 'retry_factory'),
+                             ])
+
+    def test_sorted_ordering_with_missing_fallbacks(self):
+        from pyramid.exceptions import ConfigurationError
+        from pyramid.util import LAST
+        sorter = self._makeOne()
+        add = sorter.add
+        add('exceptionview', 'excview_factory', before=LAST)
+        add('retry', 'retry_factory', after='exceptionview')
+        add('browserid', 'browserid_factory', before=('txnmgr', 'auth'))
+        self.assertRaises(ConfigurationError, sorter.sorted)
+
+    def test_sorted_ordering_conflict_direct(self):
+        from pyramid.exceptions import CyclicDependencyError
+        sorter = self._makeOne()
+        add = sorter.add
+        add('browserid', 'browserid_factory')
+        add('auth', 'auth_factory', before='browserid', after='browserid')
+        self.assertRaises(CyclicDependencyError, sorter.sorted)
+
+    def test_sorted_ordering_conflict_indirect(self):
+        from pyramid.exceptions import CyclicDependencyError
+        sorter = self._makeOne()
+        add = sorter.add
+        add('browserid', 'browserid_factory')
+        add('auth', 'auth_factory', before='browserid')
+        add('dbt', 'dbt_factory', after='browserid', before='auth')
+        self.assertRaises(CyclicDependencyError, sorter.sorted)
+
+class TestSentinel(unittest.TestCase):
+    def test_repr(self):
+        from pyramid.util import Sentinel
+        r = repr(Sentinel('ABC'))
+        self.assertEqual(r, 'ABC')
+
 def dummyfunc(): pass
 
 class Dummy(object):
diff --git a/pyramid/util.py b/pyramid/util.py
index 6190e8156..d83837322 100644
--- a/pyramid/util.py
+++ b/pyramid/util.py
@@ -1,8 +1,14 @@
 import inspect
 import weakref
 
+from pyramid.exceptions import (
+    ConfigurationError,
+    CyclicDependencyError,
+    )
+
 from pyramid.compat import (
     iteritems_,
+    is_nonstr_iter,
     integer_types,
     string_types,
     text_,
@@ -288,3 +294,162 @@ def shortrepr(object, closer):
         r = r[:100] + ' ... %s' % closer
     return r
 
+class Sentinel(object):
+    def __init__(self, repr):
+        self.repr = repr
+
+    def __repr__(self):
+        return self.repr
+
+FIRST = Sentinel('FIRST')
+LAST = Sentinel('LAST')
+
+class TopologicalSorter(object):
+    """ A utility class which can be used to perform topological sorts against
+    tuple-like data."""
+    def __init__(
+        self,
+        default_before=LAST,
+        default_after=None,
+        first=FIRST,
+        last=LAST,
+        ):
+        self.names = []
+        self.req_before = set()
+        self.req_after = set()
+        self.name2before = {}
+        self.name2after = {}
+        self.name2val = {}
+        self.order = []
+        self.default_before = default_before
+        self.default_after = default_after
+        self.first = first
+        self.last = last
+
+    def remove(self, name):
+        """ Remove a node from the sort input """
+        self.names.remove(name)
+        del self.name2val[name]
+        after = self.name2after.pop(name, [])
+        if after:
+            self.req_after.remove(name)
+            for u in after:
+                self.order.remove((u, name))
+        before = self.name2before.pop(name, [])
+        if before:
+            self.req_before.remove(name)
+            for u in before:
+                self.order.remove((name, u))
+                
+    def add(self, name, val, after=None, before=None):
+        """ Add a node to the sort input.  The ``name`` should be a string or
+        any other hashable object, the ``val`` should be the sortable (doesn't
+        need to be hashable).  ``after`` and ``before`` represents the name of
+        one of the other sortables (or a sequence of such named) or one of the
+        special sentinel values :attr:`pyramid.util.FIRST`` or
+        :attr:`pyramid.util.LAST` representing the first or last positions
+        respectively.  ``FIRST`` and ``LAST`` can also be part of a sequence
+        passed as ``before`` or ``after``.  A sortable should not be added
+        after LAST or before FIRST.  An example::
+
+           sorter = TopologicalSorter()
+           sorter.add('a', {'a':1}, before=LAST, after='b')
+           sorter.add('b', {'b':2}, before=LAST, after='c')
+           sorter.add('c', {'c':3})
+
+           sorter.sorted() # will be {'c':3}, {'b':2}, {'a':1}
+
+        """
+        if name in self.names:
+            self.remove(name)
+        self.names.append(name)
+        self.name2val[name] = val
+        if after is None and before is None:
+            before = self.default_before
+            after = self.default_after
+        if after is not None:
+            if not is_nonstr_iter(after):
+                after = (after,)
+            self.name2after[name] = after
+            self.order += [(u, name) for u in after]
+            self.req_after.add(name)
+        if before is not None:
+            if not is_nonstr_iter(before):
+                before = (before,)
+            self.name2before[name] = before
+            self.order += [(name, o) for o in before]
+            self.req_before.add(name)
+
+
+    def sorted(self):
+        """ Returns the sort input values in topologically sorted order"""
+        order = [(self.first, self.last)]
+        roots = []
+        graph = {}
+        names = [self.first, self.last]
+        names.extend(self.names)
+
+        for a, b in self.order:
+            order.append((a, b))
+
+        def add_node(node):
+            if not node in graph:
+                roots.append(node)
+                graph[node] = [0] # 0 = number of arcs coming into this node
+
+        def add_arc(fromnode, tonode):
+            graph[fromnode].append(tonode)
+            graph[tonode][0] += 1
+            if tonode in roots:
+                roots.remove(tonode)
+
+        for name in names:
+            add_node(name)
+
+        has_before, has_after = set(), set()
+        for a, b in order:
+            if a in names and b in names: # deal with missing dependencies
+                add_arc(a, b)
+                has_before.add(a)
+                has_after.add(b)
+
+        if not self.req_before.issubset(has_before):
+            raise ConfigurationError(
+                'Unsatisfied before dependencies: %s'
+                % (', '.join(sorted(self.req_before - has_before)))
+            )
+        if not self.req_after.issubset(has_after):
+            raise ConfigurationError(
+                'Unsatisfied after dependencies: %s'
+                % (', '.join(sorted(self.req_after - has_after)))
+            )
+
+        sorted_names = []
+
+        while roots:
+            root = roots.pop(0)
+            sorted_names.append(root)
+            children = graph[root][1:]
+            for child in children:
+                arcs = graph[child][0]
+                arcs -= 1
+                graph[child][0] = arcs 
+                if arcs == 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)
+
+        result = []
+
+        for name in sorted_names:
+            if name in self.names:
+                result.append((name, self.name2val[name]))
+
+        return result
+