From 127c48252edc2d431a10dbe5b3c3ae77d16ac479 Mon Sep 17 00:00:00 2001 From: Mike Bayer Date: Thu, 22 Sep 2011 19:21:39 -0400 Subject: [PATCH] - Fixed bug in unit of work whereby detection of "cycles" among classes in highly interlinked patterns would not produce a deterministic result; thereby sometimes missing some nodes that should be considered cycles and causing further issues down the road. Note this bug is in 0.6 also; not backported at the moment. [ticket:2282] --- CHANGES | 9 +++++++++ lib/sqlalchemy/orm/unitofwork.py | 7 ++++--- lib/sqlalchemy/util/topological.py | 15 ++++++++++++--- test/base/test_dependency.py | 30 ++++++++++++++++++++++++++++-- test/bootstrap/config.py | 2 +- 5 files changed, 54 insertions(+), 9 deletions(-) diff --git a/CHANGES b/CHANGES index dd10286576..598b8be672 100644 --- a/CHANGES +++ b/CHANGES @@ -31,6 +31,15 @@ CHANGES attribute, provided the name is the same as that of the entity mapped column. + - Fixed bug in unit of work whereby detection of + "cycles" among classes in highly interlinked patterns + would not produce a deterministic + result; thereby sometimes missing some nodes that + should be considered cycles and causing further + issues down the road. Note this bug is in 0.6 + also; not backported at the moment. + [ticket:2282] + - Fixed a variety of synonym()-related regressions from 0.6: - making a synonym against a synonym now works. diff --git a/lib/sqlalchemy/orm/unitofwork.py b/lib/sqlalchemy/orm/unitofwork.py index 5e0c939385..5c1f3b1a70 100644 --- a/lib/sqlalchemy/orm/unitofwork.py +++ b/lib/sqlalchemy/orm/unitofwork.py @@ -308,9 +308,10 @@ class UOWTransaction(object): #sort = topological.sort(self.dependencies, postsort_actions) #print "--------------" - #print self.dependencies - #print list(sort) - #print "COUNT OF POSTSORT ACTIONS", len(postsort_actions) + #print "\ndependencies:", self.dependencies + #print "\ncycles:", self.cycles + #print "\nsort:", list(sort) + #print "\nCOUNT OF POSTSORT ACTIONS", len(postsort_actions) # execute if self.cycles: diff --git a/lib/sqlalchemy/util/topological.py b/lib/sqlalchemy/util/topological.py index 8f34064722..ba68b71360 100644 --- a/lib/sqlalchemy/util/topological.py +++ b/lib/sqlalchemy/util/topological.py @@ -48,17 +48,26 @@ def sort(tuples, allitems): def find_cycles(tuples, allitems): # straight from gvr with some mods - todo = set(allitems) edges = util.defaultdict(set) for parent, child in tuples: edges[parent].add(child) + nodes_to_test = set(edges) output = set() - while todo: - node = todo.pop() + # we'd like to find all nodes that are + # involved in cycles, so we do the full + # pass through the whole thing for each + # node in the original list. + + # we can go just through parent edge nodes. + # if a node is only a child and never a parent, + # by definition it can't be part of a cycle. same + # if it's not in the edges at all. + for node in nodes_to_test: stack = [node] + todo = nodes_to_test.difference(stack) while stack: top = stack[-1] for node in edges[top]: diff --git a/test/base/test_dependency.py b/test/base/test_dependency.py index 85347ad913..4be3c83901 100644 --- a/test/base/test_dependency.py +++ b/test/base/test_dependency.py @@ -222,8 +222,11 @@ class DependencySortTest(fixtures.TestBase): node5, node6, ]) - eq_(topological.find_cycles(tuples, allnodes), set(['node1', - 'node2', 'node4'])) + # node6 only became present here once [ticket:2282] was addressed. + eq_( + topological.find_cycles(tuples, allnodes), + set(['node1','node2', 'node4', 'node6']) + ) def test_find_multiple_cycles_three(self): node1 = 'node1' @@ -252,3 +255,26 @@ class DependencySortTest(fixtures.TestBase): node6, ]) eq_(topological.find_cycles(tuples, allnodes), allnodes) + + def test_find_multiple_cycles_four(self): + tuples = [ + ('node6', 'node2'), + ('node15', 'node19'), + ('node19', 'node2'), ('node4', 'node10'), + ('node15', 'node13'), + ('node17', 'node11'), ('node1', 'node19'), ('node15', 'node8'), + ('node6', 'node20'), ('node14', 'node11'), ('node6', 'node14'), + ('node11', 'node2'), ('node10', 'node20'), ('node1', 'node11'), + ('node20', 'node19'), ('node4', 'node20'), ('node15', 'node20'), + ('node9', 'node19'), ('node11', 'node10'), ('node11', 'node19'), + ('node13', 'node6'), ('node3', 'node15'), ('node9', 'node11'), + ('node4', 'node17'), ('node2', 'node20'), ('node19', 'node10'), + ('node8', 'node4'), ('node11', 'node3'), ('node6', 'node1') + ] + allnodes = ['node%d' % i for i in xrange(1, 21)] + eq_( + topological.find_cycles(tuples, allnodes), + set(['node11', 'node10', 'node13', 'node15', 'node14', 'node17', + 'node19', 'node20', 'node8', 'node1', 'node3', + 'node2', 'node4', 'node6']) + ) diff --git a/test/bootstrap/config.py b/test/bootstrap/config.py index bdfc8189f5..edf94fae5f 100644 --- a/test/bootstrap/config.py +++ b/test/bootstrap/config.py @@ -168,7 +168,7 @@ post_configure.append(_set_table_options) def _reverse_topological(options, file_config): if options.reversetop: from sqlalchemy.orm import unitofwork, session, mapper, dependency - from sqlalchemy import topological + from sqlalchemy.util import topological from test.lib.util import RandomSet topological.set = unitofwork.set = session.set = mapper.set = dependency.set = RandomSet post_configure.append(_reverse_topological) -- 2.47.2