From fc3f23c094795e6c889531c9706ec9b1153aac67 Mon Sep 17 00:00:00 2001 From: Chris McDonough Date: Fri, 3 Aug 2012 00:19:51 -0400 Subject: generalize TopologicalSorter out of Tweens class for use elsewhere --- pyramid/config/tweens.py | 114 ++------------ pyramid/config/util.py | 132 ++++++++++++++++ pyramid/tests/test_config/test_tweens.py | 46 +----- pyramid/tests/test_config/test_util.py | 249 +++++++++++++++++++++++++++++++ 4 files changed, 399 insertions(+), 142 deletions(-) diff --git a/pyramid/config/tweens.py b/pyramid/config/tweens.py index 1a83f0de9..1bc6dc95c 100644 --- a/pyramid/config/tweens.py +++ b/pyramid/config/tweens.py @@ -16,7 +16,10 @@ from pyramid.tweens import ( EXCVIEW, ) -from pyramid.config.util import action_method +from pyramid.config.util import ( + action_method, + TopologicalSorter, + ) class TweensConfiguratorMixin(object): def add_tween(self, tween_factory, under=None, over=None): @@ -177,119 +180,24 @@ class TweensConfiguratorMixin(object): introspectables.append(intr) self.action(discriminator, register, introspectables=introspectables) -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 over %r' % (dependent, dependees)) - msg = 'Implicit tween ordering cycle:' + '; '.join(L) - return msg - @implementer(ITweens) class Tweens(object): def __init__(self): + self.sorter = TopologicalSorter( + default_before=None, + default_after=INGRESS, + first=INGRESS, + last=MAIN) self.explicit = [] - self.names = [] - self.req_over = set() - self.req_under = set() - self.factories = {} - self.order = [] def add_explicit(self, name, factory): self.explicit.append((name, factory)) def add_implicit(self, name, factory, under=None, over=None): - self.names.append(name) - self.factories[name] = factory - if under is None and over is None: - under = INGRESS - if under is not None: - if not is_nonstr_iter(under): - under = (under,) - self.order += [(u, name) for u in under] - self.req_under.add(name) - if over is not None: - if not is_nonstr_iter(over): - over = (over,) - self.order += [(name, o) for o in over] - self.req_over.add(name) + self.sorter.add(name, factory, after=under, before=over) def implicit(self): - order = [(INGRESS, MAIN)] - roots = [] - graph = {} - names = [INGRESS, MAIN] - 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_over, has_under = set(), set() - for a, b in order: - if a in names and b in names: # deal with missing dependencies - add_arc(a, b) - has_over.add(a) - has_under.add(b) - - if not self.req_over.issubset(has_over): - raise ConfigurationError( - 'Detected tweens with no satisfied over dependencies: %s' - % (', '.join(sorted(self.req_over - has_over))) - ) - if not self.req_under.issubset(has_under): - raise ConfigurationError( - 'Detected tweens with no satisfied under dependencies: %s' - % (', '.join(sorted(self.req_under - has_under))) - ) - - 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.factories[name])) - - return result + return self.sorter.sorted() def __call__(self, handler, registry): if self.explicit: diff --git a/pyramid/config/util.py b/pyramid/config/util.py index 4e4c93be3..027060db3 100644 --- a/pyramid/config/util.py +++ b/pyramid/config/util.py @@ -300,3 +300,135 @@ def as_sorted_tuple(val): val = tuple(sorted(val)) return 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.name2val = {} + self.order = [] + self.default_before = default_before + self.default_after = default_after + self.first = first + self.last = last + + def add(self, name, val, after=None, before=None): + 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.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.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 diff --git a/pyramid/tests/test_config/test_tweens.py b/pyramid/tests/test_config/test_tweens.py index 0d96bf601..8853b6899 100644 --- a/pyramid/tests/test_config/test_tweens.py +++ b/pyramid/tests/test_config/test_tweens.py @@ -179,28 +179,12 @@ class TestTweens(unittest.TestCase): ('name2', 'factory2')]) def test_add_implicit(self): - from pyramid.tweens import INGRESS tweens = self._makeOne() tweens.add_implicit('name', 'factory') - self.assertEqual(tweens.names, ['name']) - self.assertEqual(tweens.factories, - {'name':'factory'}) - self.assertEqual(tweens.order, [(INGRESS, 'name')]) tweens.add_implicit('name2', 'factory2') - self.assertEqual(tweens.names, ['name', 'name2']) - self.assertEqual(tweens.factories, - {'name':'factory', 'name2':'factory2'}) - self.assertEqual(tweens.order, - [(INGRESS, 'name'), (INGRESS, 'name2')]) - tweens.add_implicit('name3', 'factory3', over='name2') - self.assertEqual(tweens.names, - ['name', 'name2', 'name3']) - self.assertEqual(tweens.factories, - {'name':'factory', 'name2':'factory2', - 'name3':'factory3'}) - self.assertEqual(tweens.order, - [(INGRESS, 'name'), (INGRESS, 'name2'), - ('name3', 'name2')]) + self.assertEqual(tweens.sorter.sorted(), + [('name2', 'factory2'), + ('name', 'factory')]) def test___call___explicit(self): tweens = self._makeOne() @@ -212,18 +196,13 @@ class TestTweens(unittest.TestCase): self.assertEqual(tweens(None, None), '123') def test___call___implicit(self): - from pyramid.tweens import INGRESS tweens = self._makeOne() def factory1(handler, registry): return handler def factory2(handler, registry): return '123' - tweens.names = ['name', 'name2'] - tweens.alias_to_name = {'name':'name', 'name2':'name2'} - tweens.name_to_alias = {'name':'name', 'name2':'name2'} - tweens.req_under = set(['name', 'name2']) - tweens.order = [(INGRESS, 'name'), (INGRESS, 'name2')] - tweens.factories = {'name':factory1, 'name2':factory2} + tweens.add_implicit('name2', factory2) + tweens.add_implicit('name1', factory1) self.assertEqual(tweens(None, None), '123') def test_implicit_ordering_1(self): @@ -413,7 +392,7 @@ class TestTweens(unittest.TestCase): self.assertRaises(ConfigurationError, tweens.implicit) def test_implicit_ordering_conflict_direct(self): - from pyramid.config.tweens import CyclicDependencyError + from pyramid.config.util import CyclicDependencyError tweens = self._makeOne() add = tweens.add_implicit add('browserid', 'browserid_factory') @@ -421,7 +400,7 @@ class TestTweens(unittest.TestCase): self.assertRaises(CyclicDependencyError, tweens.implicit) def test_implicit_ordering_conflict_indirect(self): - from pyramid.config.tweens import CyclicDependencyError + from pyramid.config.util import CyclicDependencyError tweens = self._makeOne() add = tweens.add_implicit add('browserid', 'browserid_factory') @@ -429,14 +408,3 @@ class TestTweens(unittest.TestCase): add('dbt', 'dbt_factory', under='browserid', over='auth') self.assertRaises(CyclicDependencyError, tweens.implicit) -class TestCyclicDependencyError(unittest.TestCase): - def _makeOne(self, cycles): - from pyramid.config.tweens import CyclicDependencyError - return CyclicDependencyError(cycles) - - def test___str__(self): - exc = self._makeOne({'a':['c', 'd'], 'c':['a']}) - result = str(exc) - self.assertTrue("'a' sorts over ['c', 'd']" in result) - self.assertTrue("'c' sorts over ['a']" in result) - diff --git a/pyramid/tests/test_config/test_util.py b/pyramid/tests/test_config/test_util.py index 1ad1fb3c1..06e63ca40 100644 --- a/pyramid/tests/test_config/test_util.py +++ b/pyramid/tests/test_config/test_util.py @@ -368,6 +368,255 @@ 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_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' -- cgit v1.2.3