- Fixed critical issue where a complex series of branches/merges would

bog down the iteration algorithm working over redundant nodes for
millions of cycles.   An internal adjustment has been
made so that duplicate nodes are skipped within this iteration.
fixes #310

4 files changed, 224 insertions, 3 deletions

diff --git a/alembic/revision.py b/alembic/revision.py
index 4eea514..e48115a 100644
--- a/alembic/revision.py
+++ b/alembic/revision.py
@@ -545,17 +545,24 @@ class RevisionMap(object):
         if map_ is None:
             map_ = self._revision_map
 
+        seen = set()
         todo = collections.deque()
         for target in targets:
+
             todo.append(target)
             if check:
                 per_target = set()
+
             while todo:
                 rev = todo.pop()
-                todo.extend(
-                    map_[rev_id] for rev_id in fn(rev))
                 if check:
                     per_target.add(rev)
+
+                if rev in seen:
+                    continue
+                seen.add(rev)
+                todo.extend(
+                    map_[rev_id] for rev_id in fn(rev))
                 yield rev
             if check and per_target.intersection(targets).difference([target]):
                 raise RevisionError(
@@ -570,7 +577,6 @@ class RevisionMap(object):
         across branches as a whole.
 
         """
-
         requested_lowers = self.get_revisions(lower)
 
         # some complexity to accommodate an iteration where some
@@ -729,6 +735,20 @@ class Revision(object):
         self._orig_branch_labels = util.to_tuple(branch_labels, default=())
         self.branch_labels = set(self._orig_branch_labels)
 
+    def __repr__(self):
+        args = [
+            repr(self.revision),
+            repr(self.down_revision)
+        ]
+        if self.dependencies:
+            args.append("dependencies=%r" % self.dependencies)
+        if self.branch_labels:
+            args.append("branch_labels=%r" % self.branch_labels)
+        return "%s(%s)" % (
+            self.__class__.__name__,
+            ", ".join(args)
+        )
+
     def add_nextrev(self, revision):
         self._all_nextrev = self._all_nextrev.union([revision.revision])
         if self.revision in revision._versioned_down_revisions:
diff --git a/docs/build/changelog.rst b/docs/build/changelog.rst
index 473a1eb..dffdc0b 100644
--- a/docs/build/changelog.rst
+++ b/docs/build/changelog.rst
@@ -7,6 +7,15 @@ Changelog
     :version: 0.7.7
 
     .. change::
+      :tags: bug, versioning
+      :tickets: 310
+
+      Fixed critical issue where a complex series of branches/merges would
+      bog down the iteration algorithm working over redundant nodes for
+      millions of cycles.   An internal adjustment has been
+      made so that duplicate nodes are skipped within this iteration.
+
+    .. change::
       :tags: feature, batch
       :tickets: 305
 
diff --git a/tests/_large_map.py b/tests/_large_map.py
new file mode 100644
index 0000000..bc7133f
--- /dev/null
+++ b/tests/_large_map.py
@@ -0,0 +1,152 @@
+from alembic.script.revision import RevisionMap, Revision
+
+data = [
+    Revision('3fc8a578bc0a', ('4878cb1cb7f6', '454a0529f84e'), ),
+    Revision('69285b0faaa', ('36c31e4e1c37', '3a3b24a31b57'), ),
+    Revision('3b0452c64639', '2f1a0f3667f3', ),
+    Revision('2d9d787a496', '135b5fd31062', ),
+    Revision('184f65ed83af', '3b0452c64639', ),
+    Revision('430074f99c29', '54f871bfe0b0', ),
+    Revision('3ffb59981d9a', '519c9f3ce294', ),
+    Revision('454a0529f84e', ('40f6508e4373', '38a936c6ab11'), ),
+    Revision('24c2620b2e3f', ('430074f99c29', '1f5ceb1ec255'), ),
+    Revision('169a948471a9', '247ad6880f93', ),
+    Revision('2f1a0f3667f3', '17dd0f165262', ),
+    Revision('27227dc4fda8', '2a66d7c4d8a1', ),
+    Revision('4b2ad1ffe2e7', ('3b409f268da4', '4f8a9b79a063'), ),
+    Revision('124ef6a17781', '2529684536da', ),
+    Revision('4789d9c82ca7', '593b8076fb2c', ),
+    Revision('64ed798bcc3', ('44ed1bf512a0', '169a948471a9'), ),
+    Revision('2588a3c36a0f', '50c7b21c9089', ),
+    Revision('359329c2ebb', ('5810e9eff996', '339faa12616'), ),
+    Revision('540bc5634bd', '3a5db5f31209', ),
+    Revision('20fe477817d2', '53d5ff905573', ),
+    Revision('4f8a9b79a063', ('3cf34fcd6473', '300209d8594'), ),
+    Revision('6918589deaf', '3314c17f6e35', ),
+    Revision('1755e3b1481c', ('17b66754be21', '31b1d4b7fc95'), ),
+    Revision('58c988e1aa4e', ('219240032b88', 'f067f0b825c'), ),
+    Revision('593b8076fb2c', '1d94175d221b', ),
+    Revision('38d069994064', ('46b70a57edc0', '3ed56beabfb7'), ),
+    Revision('3e2f6c6d1182', '7f96a01461b', ),
+    Revision('1f6969597fe7', '1811bdae9e63', ),
+    Revision('17dd0f165262', '3cf02a593a68', ),
+    Revision('3cf02a593a68', '25a7ef58d293', ),
+    Revision('34dfac7edb2d', '28f4dd53ad3a', ),
+    Revision('4009c533e05d', '42ded7355da2', ),
+    Revision('5a0003c3b09c', ('3ed56beabfb7', '2028d94d3863'), ),
+    Revision('38a936c6ab11', '2588a3c36a0f', ),
+    Revision('59223c5b7b36', '2f93dd880bae', ),
+    Revision('4121bd6e99e9', '540bc5634bd', ),
+    Revision('260714a3f2de', '6918589deaf', ),
+    Revision('ae77a2ed69b', '274fd2642933', ),
+    Revision('18ff1ab3b4c4', '430133b6d46c', ),
+    Revision('2b9a327527a9', ('359329c2ebb', '593b8076fb2c'), ),
+    Revision('4e6167c75ed0', '325b273d61bd', ),
+    Revision('21ab11a7c5c4', ('3da31f3323ec', '22f26011d635'), ),
+    Revision('3b93e98481b1', '4e28e2f4fe2f', ),
+    Revision('145d8f1e334d', 'b4143d129e', ),
+    Revision('135b5fd31062', '1d94175d221b', ),
+    Revision('300209d8594', ('52804033910e', '593b8076fb2c'), ),
+    Revision('8dca95cce28', 'f034666cd80', ),
+    Revision('46b70a57edc0', ('145d8f1e334d', '4cc2960cbe19'), ),
+    Revision('4d45e479fbb9', '2d9d787a496', ),
+    Revision('22f085bf8bbd', '540bc5634bd', ),
+    Revision('263e91fd17d8', '2b9a327527a9', ),
+    Revision('219240032b88', ('300209d8594', '2b9a327527a9'), ),
+    Revision('325b273d61bd', '4b2ad1ffe2e7', ),
+    Revision('199943ccc774', '1aa674ccfa4e', ),
+    Revision('247ad6880f93', '1f6969597fe7', ),
+    Revision('4878cb1cb7f6', '28f4dd53ad3a', ),
+    Revision('2a66d7c4d8a1', '23f1ccb18d6d', ),
+    Revision('42b079245b55', '593b8076fb2c', ),
+    Revision('1cccf82219cb', ('20fe477817d2', '915c67915c2'), ),
+    Revision('b4143d129e', ('159331d6f484', '504d5168afe1'), ),
+    Revision('53d5ff905573', '3013877bf5bd', ),
+    Revision('1f5ceb1ec255', '3ffb59981d9a', ),
+    Revision('ef1c1c1531f', '4738812e6ece', ),
+    Revision('1f6963d1ae02', '247ad6880f93', ),
+    Revision('44d58f1d31f0', '18ff1ab3b4c4', ),
+    Revision('c3ebe64dfb5', ('3409c57b0da', '31f352e77045'), ),
+    Revision('f067f0b825c', '359329c2ebb', ),
+    Revision('52ab2d3b57ce', '96d590bd82e', ),
+    Revision('3b409f268da4', ('20e90eb3eeb6', '263e91fd17d8'), ),
+    Revision('5a4ca8889674', '4e6167c75ed0', ),
+    Revision('5810e9eff996', ('2d30d79c4093', '52804033910e'), ),
+    Revision('40f6508e4373', '4ed16fad67a7', ),
+    Revision('1811bdae9e63', '260714a3f2de', ),
+    Revision('3013877bf5bd', ('8dca95cce28', '3fc8a578bc0a'), ),
+    Revision('16426dbea880', '28f4dd53ad3a', ),
+    Revision('22f26011d635', ('4c93d063d2ba', '3b93e98481b1'), ),
+    Revision('3409c57b0da', '17b66754be21', ),
+    Revision('44373001000f', ('42b079245b55', '219240032b88'), ),
+    Revision('28f4dd53ad3a', '2e71fd90eb9d', ),
+    Revision('4cc2960cbe19', '504d5168afe1', ),
+    Revision('31f352e77045', ('17b66754be21', '22f085bf8bbd'), ),
+    Revision('4ed16fad67a7', 'f034666cd80', ),
+    Revision('3da31f3323ec', '4c93d063d2ba', ),
+    Revision('31b1d4b7fc95', '1cc4459fd115', ),
+    Revision('11bc0ff42f87', '28f4dd53ad3a', ),
+    Revision('3a5db5f31209', '59742a546b84', ),
+    Revision('20e90eb3eeb6', ('58c988e1aa4e', '44373001000f'), ),
+    Revision('23f1ccb18d6d', '52ab2d3b57ce', ),
+    Revision('1d94175d221b', '21ab11a7c5c4', ),
+    Revision('36f1a410ed', '54f871bfe0b0', ),
+    Revision('181a149173e', '2ee35cac4c62', ),
+    Revision('171ad2f0c672', '4a4e0838e206', ),
+    Revision('2f93dd880bae', '540bc5634bd', ),
+    Revision('25a7ef58d293', None, ),
+    Revision('7f96a01461b', '184f65ed83af', ),
+    Revision('b21f22233f', '3e2f6c6d1182', ),
+    Revision('52804033910e', '1d94175d221b', ),
+    Revision('1e6240aba5b3', ('4121bd6e99e9', '2c50d8bab6ee'), ),
+    Revision('1cc4459fd115', '1e6240aba5b3', ),
+    Revision('274fd2642933', '4009c533e05d', ),
+    Revision('1aa674ccfa4e', ('59223c5b7b36', '42050bf030fd'), ),
+    Revision('4e28e2f4fe2f', '596d7b9e11', ),
+    Revision('49ddec8c7a5e', ('124ef6a17781', '47578179e766'), ),
+    Revision('3e9bb349cc46', 'ef1c1c1531f', ),
+    Revision('2028d94d3863', '504d5168afe1', ),
+    Revision('159331d6f484', '34dfac7edb2d', ),
+    Revision('596d7b9e11', '171ad2f0c672', ),
+    Revision('3b96bcc8da76', 'f034666cd80', ),
+    Revision('4738812e6ece', '78982bf5499', ),
+    Revision('3314c17f6e35', '27227dc4fda8', ),
+    Revision('30931c545bf', '2e71fd90eb9d', ),
+    Revision('2e71fd90eb9d', ('c3ebe64dfb5', '1755e3b1481c'), ),
+    Revision('3ed56beabfb7', ('11bc0ff42f87', '69285b0faaa'), ),
+    Revision('96d590bd82e', '3e9bb349cc46', ),
+    Revision('339faa12616', '4d45e479fbb9', ),
+    Revision('47578179e766', '2529684536da', ),
+    Revision('2ee35cac4c62', 'b21f22233f', ),
+    Revision('50c7b21c9089', ('4ed16fad67a7', '3b96bcc8da76'), ),
+    Revision('78982bf5499', 'ae77a2ed69b', ),
+    Revision('519c9f3ce294', '2c50d8bab6ee', ),
+    Revision('2720fc75e5fd', '1cccf82219cb', ),
+    Revision('21638ec787ba', '44d58f1d31f0', ),
+    Revision('59742a546b84', '49ddec8c7a5e', ),
+    Revision('2d30d79c4093', '135b5fd31062', ),
+    Revision('f034666cd80', ('5a0003c3b09c', '38d069994064'), ),
+    Revision('430133b6d46c', '181a149173e', ),
+    Revision('3a3b24a31b57', ('16426dbea880', '4cc2960cbe19'), ),
+    Revision('2529684536da', ('64ed798bcc3', '1f6963d1ae02'), ),
+    Revision('17b66754be21', ('19e0db9d806a', '24c2620b2e3f'), ),
+    Revision('3cf34fcd6473', ('52804033910e', '4789d9c82ca7'), ),
+    Revision('36c31e4e1c37', '504d5168afe1', ),
+    Revision('54f871bfe0b0', '519c9f3ce294', ),
+    Revision('4a4e0838e206', '2a7f37cf7770', ),
+    Revision('19e0db9d806a', ('430074f99c29', '36f1a410ed'), ),
+    Revision('44ed1bf512a0', '247ad6880f93', ),
+    Revision('42050bf030fd', '2f93dd880bae', ),
+    Revision('2c50d8bab6ee', '199943ccc774', ),
+    Revision('504d5168afe1', ('28f4dd53ad3a', '30931c545bf'), ),
+    Revision('915c67915c2', '3fc8a578bc0a', ),
+    Revision('2a7f37cf7770', '2720fc75e5fd', ),
+    Revision('4c93d063d2ba', '4e28e2f4fe2f', ),
+    Revision('42ded7355da2', '21638ec787ba', ),
+]
+
+map_ = RevisionMap(
+    lambda: data
+)
+
+
diff --git a/tests/test_revision.py b/tests/test_revision.py
index d73316d..14afa84 100644
--- a/tests/test_revision.py
+++ b/tests/test_revision.py
@@ -2,6 +2,7 @@ from alembic.testing.fixtures import TestBase
 from alembic.testing import eq_, assert_raises_message
 from alembic.revision import RevisionMap, Revision, MultipleHeads, \
     RevisionError
+from . import _large_map
 
 
 class APITest(TestBase):
@@ -619,6 +620,17 @@ class BranchTravellingTest(DownIterateTest):
             inclusive=False
         )
 
+    def test_ancestor_nodes(self):
+        merge = self.map.get_revision("merge")
+        eq_(
+            set(
+                rev.revision
+                for rev in self.map._get_ancestor_nodes([merge], check=True)
+            ),
+            set(['a1', 'e2b2', 'e2b1', 'cb2', 'merge',
+                'a3', 'a2', 'b1', 'b2', 'db1', 'db2', 'cb1'])
+        )
+
 
 class MultipleBaseTest(DownIterateTest):
     def setUp(self):
@@ -901,3 +913,31 @@ class MultipleBaseCrossDependencyTestTwo(DownIterateTest):
             ['d3', 'c3', 'b3', 'a3', 'base3']
         )
 
+
+class LargeMapTest(DownIterateTest):
+    def setUp(self):
+        self.map = _large_map.map_
+
+    def test_all(self):
+        raw = [r for r in self.map._revision_map.values() if r is not None]
+
+        revs = [
+            rev for rev in
+            self.map.iterate_revisions(
+                "heads", "base"
+            )
+        ]
+
+        eq_(set(raw), set(revs))
+
+        for idx, rev in enumerate(revs):
+            ancestors = set(
+                self.map._get_ancestor_nodes([rev])).difference([rev])
+            descendants = set(
+                self.map._get_descendant_nodes([rev])).difference([rev])
+
+            assert not ancestors.intersection(descendants)
+
+            remaining = set(revs[idx + 1:])
+            if remaining:
+                assert remaining.intersection(ancestors)