From 29640f52d14eb8ca932c628eda5f9dde9ba48d92 Mon Sep 17 00:00:00 2001
From: Philip Jenvey <pjenvey@underboss.org>
Date: Sun, 3 May 2009 00:05:28 +0000
Subject: [PATCH] fix _sort not always using the node's id as its key fixes
 #1380

---
 lib/sqlalchemy/topological.py | 14 ++++++++------
 test/base/dependency.py       |  8 +++++---
 2 files changed, 13 insertions(+), 9 deletions(-)

diff --git a/lib/sqlalchemy/topological.py b/lib/sqlalchemy/topological.py
index 306cdfc900..77945b173c 100644
--- a/lib/sqlalchemy/topological.py
+++ b/lib/sqlalchemy/topological.py
@@ -164,20 +164,22 @@ def _sort(tuples, allitems, allow_cycles=False, ignore_self_cycles=False):
     edges = _EdgeCollection()
 
     for item in list(allitems) + [t[0] for t in tuples] + [t[1] for t in tuples]:
-        if id(item) not in nodes:
+        item_id = id(item)
+        if item_id not in nodes:
             node = _Node(item)
-            nodes[item] = node
+            nodes[item_id] = node
 
     for t in tuples:
+        id0 = id(t[0])
         if t[0] is t[1]:
             if allow_cycles:
-                n = nodes[t[0]]
+                n = nodes[id0]
                 n.cycles = set([n])
             elif not ignore_self_cycles:
                 raise CircularDependencyError("Self-referential dependency detected " + repr(t))
             continue
-        childnode = nodes[t[1]]
-        parentnode = nodes[t[0]]
+        childnode = nodes[id(t[1])]
+        parentnode = nodes[id0]
         edges.add((parentnode, childnode))
 
     queue = []
@@ -213,7 +215,7 @@ def _sort(tuples, allitems, allow_cycles=False, ignore_self_cycles=False):
         node = queue.pop()
         if not hasattr(node, '_cyclical'):
             output.append(node)
-        del nodes[node.item]
+        del nodes[id(node.item)]
         for childnode in edges.pop_node(node):
             queue.append(childnode)
     return output
diff --git a/test/base/dependency.py b/test/base/dependency.py
index 1318ef528a..b4d42d2532 100644
--- a/test/base/dependency.py
+++ b/test/base/dependency.py
@@ -177,11 +177,13 @@ class DependencySortTest(TestBase):
         self.assert_sort(tuples, head)
 
     def testbigsort(self):
-        tuples = []
-        for i in range(0,1500, 2):
-            tuples.append((i, i+1))
+        tuples = [(i, i + 1) for i in range(0, 1500, 2)]
         head = topological.sort_as_tree(tuples, [])
 
+    def testids(self):
+        # ticket:1380 regression: would raise a KeyError
+        topological.sort([(id(i), i) for i in range(3)], [])
+
 
 if __name__ == "__main__":
     testenv.main()
-- 
2.47.3