_iterate_related_revisions gets stuck with duplicate revisions

[sqlalchemy-bot]

Migrated issue, originally created by Michael Bayer (@zzzeek)

attached test illustrates a complex revision tree, where the _iterate_related_revisions() gets bogged down doing the same nodes over and over again. As only needs to emit unique nodes we need to put a seen set into it:

index e9958b1..40cfbb2 100644
--- a/alembic/script/revision.py
+++ b/alembic/script/revision.py
@@ -544,17 +544,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(

---

Attachments: runtest.py

[sqlalchemy-bot]

Michael Bayer (@zzzeek) wrote:

• 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

→ dad4be3

[sqlalchemy-bot]

Michael Bayer (@zzzeek) wrote:

• 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

→ 61183b7

[sqlalchemy-bot]

Changes by Michael Bayer (@zzzeek):

• changed status to closed