Cascade traversal algorithm converted from recursive to iterative to support deep object graphs.

4 files changed, 29 insertions, 22 deletions

diff --git a/CHANGES b/CHANGES
index 4f78ceb94..522eaf1a8 100644
--- a/CHANGES
+++ b/CHANGES
@@ -155,6 +155,9 @@ CHANGES
       one collection with another into collections.bulk_replace,
       useful to anyone building multi-level collections.
 
+    - Cascade traversal algorithm converted from recursive to
+      iterative to support deep object graphs.
+
 - sql
     - Schema-qualified tables now will place the schemaname
       ahead of the tablename in all column expressions as well
diff --git a/lib/sqlalchemy/orm/interfaces.py b/lib/sqlalchemy/orm/interfaces.py
index c43bae6c0..f00c42421 100644
--- a/lib/sqlalchemy/orm/interfaces.py
+++ b/lib/sqlalchemy/orm/interfaces.py
@@ -334,9 +334,9 @@ class MapperProperty(object):
 
         raise NotImplementedError()
 
-    def cascade_iterator(self, type, object, recursive=None, halt_on=None):
-        """Iterate through instances related to the given instance along
-        a particular 'cascade' path, starting with this MapperProperty.
+    def cascade_iterator(self, type_, state, visited_instances=None, halt_on=None):
+        """Iterate through instances related to the given instance for
+        a particular 'cascade', starting with this MapperProperty.
 
         See PropertyLoader for the related instance implementation.
         """
diff --git a/lib/sqlalchemy/orm/mapper.py b/lib/sqlalchemy/orm/mapper.py
index 07e7d8d86..12e7d03a9 100644
--- a/lib/sqlalchemy/orm/mapper.py
+++ b/lib/sqlalchemy/orm/mapper.py
@@ -1294,11 +1294,11 @@ class Mapper(object):
         for dep in self._dependency_processors:
             dep.register_dependencies(uowcommit)
 
-    def cascade_iterator(self, type, state, recursive=None, halt_on=None):
+    def cascade_iterator(self, type_, state, halt_on=None):
         """Iterate each element and its mapper in an object graph,
         for all relations that meet the given cascade rule.
 
-        type
+        type_
           The name of the cascade rule (i.e. save-update, delete,
           etc.)
 
@@ -1306,19 +1306,25 @@ class Mapper(object):
           The lead InstanceState.  child items will be processed per
           the relations defined for this object's mapper.
 
-        recursive
-          Used by the function for internal context during recursive
-          calls, leave as None.
-
         the return value are object instances; this provides a strong
         reference so that they don't fall out of scope immediately.
         """
 
-        if recursive is None:
-            recursive=util.IdentitySet()
-        for prop in self.__props.values():
-            for (c, m) in prop.cascade_iterator(type, state, recursive, halt_on=halt_on):
-                yield (c, m)
+        visited_instances = util.IdentitySet()
+        visitables = [(self.__props.itervalues(), 'property', state)]
+
+        while visitables:
+            iterator,item_type,parent_state = visitables[-1]
+            try:
+                if item_type == 'property':
+                    prop = iterator.next()
+                    visitables.append((prop.cascade_iterator(type_, parent_state, visited_instances, halt_on), 'mapper', None))
+                elif item_type == 'mapper':
+                    instance, instance_mapper, corresponding_state  = iterator.next()
+                    yield (instance, instance_mapper)
+                    visitables.append((instance_mapper.__props.itervalues(), 'property', corresponding_state))
+            except StopIteration:
+                visitables.pop()
 
     def _instance(self, context, row, result=None, polymorphic_from=None, extension=None, only_load_props=None, refresh_instance=None):
         if not extension:
diff --git a/lib/sqlalchemy/orm/properties.py b/lib/sqlalchemy/orm/properties.py
index 31452c50e..9f8e852f1 100644
--- a/lib/sqlalchemy/orm/properties.py
+++ b/lib/sqlalchemy/orm/properties.py
@@ -447,24 +447,22 @@ class PropertyLoader(StrategizedProperty):
                     else:
                         setattr(dest, self.key, obj)
 
-    def cascade_iterator(self, type, state, recursive, halt_on=None):
-        if not type in self.cascade:
+    def cascade_iterator(self, type_, state, visited_instances, halt_on=None):
+        if not type_ in self.cascade:
             return
-        passive = type != 'delete' or self.passive_deletes
+        passive = type_ != 'delete' or self.passive_deletes
         mapper = self.mapper.primary_mapper()
         instances = attributes.get_as_list(state, self.key, passive=passive)
         if instances:
             for c in instances:
-                if c is not None and c not in recursive and (halt_on is None or not halt_on(c)):
+                if c is not None and c not in visited_instances and (halt_on is None or not halt_on(c)):
                     if not isinstance(c, self.mapper.class_):
                         raise exceptions.AssertionError("Attribute '%s' on class '%s' doesn't handle objects of type '%s'" % (self.key, str(self.parent.class_), str(c.__class__)))
-                    recursive.add(c)
+                    visited_instances.add(c)
 
                     # cascade using the mapper local to this object, so that its individual properties are located
                     instance_mapper = object_mapper(c, entity_name=mapper.entity_name)
-                    yield (c, instance_mapper)
-                    for (c2, m) in instance_mapper.cascade_iterator(type, c._state, recursive):
-                        yield (c2, m)
+                    yield (c, instance_mapper, c._state)
 
     def _get_target_class(self):
         """Return the target class of the relation, even if the