Changeset 7722

Timestamp:

06/21/08 15:57:05 (3 months ago)

Author:

lukeplant

Message:

Fixed bug with Model.delete() which did not always delete objects in the right order.

Files:

• django/trunk/django/db/models/base.py (modified) (4 diffs)
• django/trunk/django/db/models/query.py (modified) (5 diffs)
• django/trunk/tests/modeltests/delete/models.py (modified) (6 diffs)

django/trunk/django/db/models/base.py

@@ -11 +11 @@
-from django.db.models.fields import AutoField, ImageField, FieldDoesNotExist
-from django.db.models.fields.related import OneToOneRel, ManyToOneRel, OneToOneField
-
+, CollectedObjects
-from django.db.models.options import Options, AdminOptions
-from django.db import connection, transaction
@@ -369 +369 @@
-        return error_dict
-
-
+, parent=None, nullable=False
-        """
-        Recursively populates seen_objs with all objects related to this object.
-
-{model_class: {pk_val: obj, pk_val: obj, ...}
-model_class: {pk_val: obj, pk_val: obj, ...}, ...}
+.items()
+[(model_class, {pk_val: obj, pk_val: obj, ...})
+(model_class, {pk_val: obj, pk_val: obj, ...}),...]
-        """
-        pk_val = self._get_pk_val()
-pk_val in seen_objs.setdefault(self.__class__, {}
+seen_objs.add(self.__class__, pk_val, self, parent, nullable
-            return
-        seen_objs[self.__class__][pk_val] = self
-
-        for related in self._meta.get_all_related_objects():
@@ -389 +388 @@
-                    pass
-                else:
-
+, self.__class__, related.field.null
-            else:
-                for sub_obj in getattr(self, rel_opts_name).all():
-
+, self.__class__, related.field.null
-
-    def delete(self):
@@ -398 +397 @@
-
-        # Find all the objects than need to be deleted
-SortedDict
+CollectedObjects
-        self._collect_sub_objects(seen_objs)
-

django/trunk/django/db/models/query.py

@@ -16 +16 @@
-# Pull into this namespace for backwards compatibility
-EmptyResultSet = sql.EmptyResultSet
+
+class CyclicDependency(Exception):
+    pass
+
+class CollectedObjects(object):
+    """
+    A container that stores keys and lists of values along with
+    remembering the parent objects for all the keys.
+
+    This is used for the database object deletion routines so that we
+    can calculate the 'leaf' objects which should be deleted first.
+    """
+
+    def __init__(self):
+        self.data = {}
+        self.children = {}
+
+    def add(self, model, pk, obj, parent_model, nullable=False):
+        """
+        Adds an item.
+        model is the class of the object being added,
+        pk is the primary key, obj is the object itself, 
+        parent_model is the model of the parent object
+        that this object was reached through, nullable should
+        be True if this relation is nullable.
+
+        If the item already existed in the structure,
+        returns true, otherwise false.
+        """
+        d = self.data.setdefault(model, SortedDict())
+        retval = pk in d
+        d[pk] = obj
+        # Nullable relationships can be ignored -- they
+        # are nulled out before deleting, and therefore
+        # do not affect the order in which objects have
+        # to be deleted.
+        if parent_model is not None and not nullable:
+            self.children.setdefault(parent_model, []).append(model)
+
+        return retval
+
+    def __contains__(self, key):
+        return self.data.__contains__(key)
+
+    def __getitem__(self, key):
+        return self.data[key]
+
+    def __nonzero__(self):
+        return bool(self.data)
+
+    def iteritems(self):
+        for k in self.ordered_keys():
+            yield k, self[k]
+
+    def items(self):
+        return list(self.iteritems())
+
+    def keys(self):
+        return self.ordered_keys()
+
+    def ordered_keys(self):
+        """
+        Returns the models in the order that they should be 
+        dealth with i.e. models with no dependencies first.
+        """
+        dealt_with = SortedDict()
+        # Start with items that have no children
+        models = self.data.keys()
+        while len(dealt_with) < len(models):
+            found = False
+            for model in models:
+                children = self.children.setdefault(model, [])
+                if len([c for c in children if c not in dealt_with]) == 0:
+                    dealt_with[model] = None
+                    found = True
+            if not found:
+                raise CyclicDependency("There is a cyclic dependency of items to be processed.")
+            
+        return dealt_with.keys()
+
+    def unordered_keys(self):
+        """
+        Fallback for the case where is a cyclic dependency but we
+        don't care.
+        """
+        return self.data.keys()
-
-class QuerySet(object):
@@ -276 +362 @@
-            # Collect all the objects to be deleted in this chunk, and all the
-            # objects that are related to the objects that are to be deleted.
-SortedDict
+CollectedObjects
-            for object in del_query[:CHUNK_SIZE]:
-                object._collect_sub_objects(seen_objs)
@@ -683 +769 @@
-    referred to.
-    """
-
-
-
+
+
+
+
+
+
+
+
+
+
-    for cls in ordered_classes:
-
-
+
+
+
-
-        # Pre notify all instances to be deleted
-seen_objs[cls]
+items
-            dispatcher.send(signal=signals.pre_delete, sender=cls,
-                    instance=instance)
-
-seen_objs[cls]
+items
-        del_query = sql.DeleteQuery(cls, connection)
-        del_query.delete_batch_related(pk_list)
@@ -706 +800 @@
-    # Now delete the actual data
-    for cls in ordered_classes:
-
-
+
+
+
+
-        del_query = sql.DeleteQuery(cls, connection)
-        del_query.delete_batch(pk_list)
@@ -714 +810 @@
-        # object, NULL the primary key of the found objects, and perform
-        # post-notification.
-seen_objs[cls]
+items
-            for field in cls._meta.fields:
-                if field.rel and field.null and field.rel.to in seen_objs:

django/trunk/tests/modeltests/delete/models.py

@@ -34 +34 @@
-# case things will be nice), or find Ds first.
-
+# Some mutually dependent models, but nullable
+class E(DefaultRepr, models.Model):
+    f = models.ForeignKey('F', null=True, related_name='e_rel')
+
+class F(DefaultRepr, models.Model):
+    e = models.ForeignKey(E, related_name='f_rel')
+
-
-__test__ = {'API_TESTS': """
+# First, some tests for the datastructure we use
+
+>>> from django.db.models.query import CollectedObjects
+
+>>> g = CollectedObjects()
+>>> g.add("key1", 1, "item1", None)
+False
+>>> g["key1"]
+{1: 'item1'}
+>>> g.add("key2", 1, "item1", "key1")
+False
+>>> g.add("key2", 2, "item2", "key1")
+False
+>>> g["key2"]
+{1: 'item1', 2: 'item2'}
+>>> g.add("key3", 1, "item1", "key1")
+False
+>>> g.add("key3", 1, "item1", "key2")
+True
+>>> g.ordered_keys()
+['key3', 'key2', 'key1']
+
+>>> g.add("key2", 1, "item1", "key3")
+True
+>>> g.ordered_keys()
+Traceback (most recent call last):
+    ...
+CyclicDependency: There is a cyclic dependency of items to be processed.
+
+
+
-# Due to the way that transactions work in the test harness,
-# doing m.delete() here can work but fail in a real situation,
@@ -43 +81 @@
-# Also, it is possible that the order is correct 'accidentally', due
-# solely to order of imports etc.  To check this, we set the order
-tricky
-the reverse and try again
-.
+nice
+a known 'tricky' order
+ :-)
-
->>> from django.utils.datastructures import SortedDict
->>> from django.db.models.loading import cache
-
@@ -56 +93 @@
->>> del C._meta._related_objects_cache
->>> del D._meta._related_objects_cache
-
-
-
->>> a1 = A()
@@ -68 +103 @@
->>> d1.save()
-
-sd = SortedDict
-sd
-list(reversed(sd.keys())
+o = CollectedObjects
+o
+o.keys(
-[<class 'modeltests.delete.models.D'>, <class 'modeltests.delete.models.C'>, <class 'modeltests.delete.models.B'>, <class 'modeltests.delete.models.A'>]
->>> a1.delete()
@@ -81 +116 @@
->>> del D._meta._related_objects_cache
-
-
->>> a2 = A()
->>> a2.save()
@@ -91 +125 @@
->>> d2.save()
-
-sd2 = SortedDict
-sd2
-list(reversed(sd2.keys())
+o = CollectedObjects
+o
+o.keys(
-[<class 'modeltests.delete.models.D'>, <class 'modeltests.delete.models.C'>, <class 'modeltests.delete.models.B'>, <class 'modeltests.delete.models.A'>]
->>> a2.delete()
-
+# Tests for nullable related fields
-
+>>> g = CollectedObjects()
+>>> g.add("key1", 1, "item1", None)
+False
+>>> g.add("key2", 1, "item1", "key1", nullable=True)
+False
+>>> g.add("key1", 1, "item1", "key2")
+True
+>>> g.ordered_keys()
+['key1', 'key2']
+
+>>> e1 = E()
+>>> e1.save()
+>>> f1 = F(e=e1)
+>>> f1.save()
+>>> e1.f = f1
+>>> e1.save()
+
+# Since E.f is nullable, we should delete F first (after nulling out
+# the E.f field), then E.
+
+>>> o = CollectedObjects()
+>>> e1._collect_sub_objects(o)
+>>> o.keys()
+[<class 'modeltests.delete.models.F'>, <class 'modeltests.delete.models.E'>]
+
+>>> e1.delete()
+
+>>> e2 = E()
+>>> e2.save()
+>>> f2 = F(e=e2)
+>>> f2.save()
+>>> e2.f = f2
+>>> e2.save()
+
+# Same deal as before, though we are starting from the other object.
+
+>>> o = CollectedObjects()
+>>> f2._collect_sub_objects(o)
+>>> o.keys()
+[<class 'modeltests.delete.models.F'>, <class 'modeltests.delete.models.E'>]
+
+>>> f2.delete()
-
-"""