[Zodb-checkins] CVS: Zope3/src/zodb/btrees - MergeTemplate.c:1.4 interfaces.py:1.6

Tim Peters tim.one@comcast.net
Thu, 16 Jan 2003 15:10:50 -0500


Update of /cvs-repository/Zope3/src/zodb/btrees
In directory cvs.zope.org:/tmp/cvs-serv12360/src/zodb/btrees

Modified Files:
	MergeTemplate.c interfaces.py 
Log Message:
After discussing it with Jim, cleared up (almost) all the XXX comments
I added yesterday.  Removed them and wrote up what I learned.


=== Zope3/src/zodb/btrees/MergeTemplate.c 1.3 => 1.4 ===
--- Zope3/src/zodb/btrees/MergeTemplate.c:1.3	Wed Jan 15 23:47:01 2003
+++ Zope3/src/zodb/btrees/MergeTemplate.c	Thu Jan 16 15:10:47 2003
@@ -56,6 +56,36 @@
   return NULL;
 }
 
+/* It's hard to explain "the rules" for bucket_merge, in large part because
+ * any automatic conflict-resolution scheme is going to be incorrect for
+ * some endcases of *some* app.  The scheme here is pretty conservative,
+ * and should be OK for most apps.  It's easier to explain what the code
+ * allows than what it forbids:
+ *
+ * Leaving things alone:  it's OK if both s2 and s3 leave a piece of s1
+ * alone (don't delete the key, and don't change the value).
+ *
+ * Key deletion:  a transaction (s2 or s3) can delete a key (from s1), but
+ * only if the other transaction (of s2 and s3) doesn't delete the same key.
+ * However, it's not OK for s2 and s3 to, between them, end up deleting all
+ * the keys.  This is a higher-level constraint, due to that the caller of
+ * bucket_merge() doesn't have enough info to unlink the resulting empty
+ * bucket from its BTree correctly.
+ * XXX The code below doesn't yet raise ConflictError in the empty-output-
+ * XXX bucket case.  This is a bug; the symptom is segfaults when later
+ * XXX code tries to dereference NULL pointers in the empty bucket.
+ *
+ * Key insertion:  s2 or s3 can add a new key, provided the other transaction
+ * doesn't insert the same key.  It's not OK even if they insert the same
+ * <key, value> pair.
+ *
+ * Mapping value modification:  s2 or s3 can modify the value associated
+ * with a key in s1, provided the other transaction doesn't make a
+ * modification of the same key to a different value.  It's OK if s2 and s3
+ * both give the same new value to the key (XXX while it's hard to be
+ * precise about why, this doesn't seem consistent with that it's *not* OK
+ * for both to add a new key mapping to the same value).
+ */
 static PyObject *
 bucket_merge(Bucket *s1, Bucket *s2, Bucket *s3)
 {
@@ -123,7 +153,7 @@
               if (i3.next(&i3) < 0) goto err;
             }
           else if (set || (TEST_VALUE(i1.value, i2.value) == 0))
-            {                   /* delete i3 */
+            {                   /* deleted in i3 */
               if (i1.next(&i1) < 0) goto err;
               if (i2.next(&i2) < 0) goto err;
             }
@@ -141,7 +171,7 @@
               if (i2.next(&i2) < 0) goto err;
             }
           else if (set || (TEST_VALUE(i1.value, i3.value) == 0))
-            {                   /* delete i2 */
+            {                   /* deleted in i2 */
               if (i1.next(&i1) < 0) goto err;
               if (i3.next(&i3) < 0) goto err;
             }
@@ -156,14 +186,6 @@
           TEST_KEY_SET_OR(cmp23, i2.key, i3.key) goto err;
           if (cmp23==0)
             {                   /* dualing inserts or deletes */
-              /* XXX Why is this a conflict?  Suppose i2 and i3 both
-               * XXX added the same key.  If this is a set, that's not
-               * XXX a conflict.  Or if it's a mapping and they both added
-               * XXX the same value too, ditto.  If it's a mapping and they
-               * XXX added different values, *that* would be a conflict.
-               * XXX Or if they both deleted the same key, that's not a
-               * XXX conflict either.
-               */
               merge_error(i1.position, i2.position, i3.position, 4);
               goto err;
             }
@@ -186,13 +208,8 @@
               if (i3.next(&i3) < 0) goto err;
             }
           else
-            {                   /* Dueling deletes */
-              /* XXX I don't think this is a conflict:  i1.key < i2.key,
-               * XXX and i1.key < i3.key here.  That just means i1.key
-               * XXX was deleted by both, and we should simply advance i1
-               * XXX without merging anything into the output.
-               */
-              merge_error(i1.position, i2.position, i3.position, 5);
+            {                   /* 1<2 and 1<3:  both deleted 1.key */
+               merge_error(i1.position, i2.position, i3.position, 5);
               goto err;
             }
         }
@@ -203,10 +220,6 @@
       TEST_KEY_SET_OR(cmp23, i2.key, i3.key) goto err;
       if (cmp23==0)
         {                       /* dualing inserts */
-          /* XXX I don't believe this should be a conflict for sets,
-           * XXX and it should be a conflict for mappings iff the
-           * XXX associated values differ.
-           */
           merge_error(i1.position, i2.position, i3.position, 6);
           goto err;
         }
@@ -223,11 +236,7 @@
     }
 
   while (i1.position >= 0 && i2.position >= 0)
-    {                           /* deleting i3 */
-      /* XXX I don't understand the "deleting i3" comment.  It seems more
-       * XXX that i3 deleted some keys from the tail end of i1, and i2 may
-       * XXX have added some keys that i3 didn't add.
-       */
+    {                           /* remainder of i1 deleted in i3 */
       TEST_KEY_SET_OR(cmp12, i1.key, i2.key) goto err;
       if (cmp12 > 0)
         {                       /* insert i2 */
@@ -241,21 +250,13 @@
         }
       else
         {                       /* Dueling deletes or delete and change */
-          /* XXX If i1.key < i2.key at this point, I think that just means
-           * XXX that i2 and i3 both deleted i1.key, and that shouldn't be
-           * XXX a conflict.
-           */
           merge_error(i1.position, i2.position, i3.position, 7);
           goto err;
         }
     }
 
   while (i1.position >= 0 && i3.position >= 0)
-    {                           /* deleting i2 */
-      /* XXX I don't understand the "deleting i2" comment.  It seems more
-       * XXX that i2 deleted some keys from the tail end of i1, and i3 may
-       * XXX have added some keys that i2 didn't add.
-       */
+    {                           /* remainer of i1 deleted in i2 */
       TEST_KEY_SET_OR(cmp13, i1.key, i3.key) goto err;
       if (cmp13 > 0)
         {                       /* insert i3 */
@@ -269,10 +270,6 @@
         }
       else
         {                       /* Dueling deletes or delete and change */
-          /* XXX If i1.key < i3.key at this point, I think that just means
-           * XXX that i2 and i3 both deleted i1.key, and that shouldn't be
-           * XXX a conflict.
-           */
           merge_error(i1.position, i2.position, i3.position, 8);
           goto err;
         }
@@ -280,9 +277,6 @@
 
   if (i1.position >= 0)
     {                           /* Dueling deletes */
-      /* XXX If i2 and i3 both deleted these guys, why is that a conflict?
-       * XXX I think we should ignore this.
-       */
       merge_error(i1.position, i2.position, i3.position, 9);
       goto err;
     }
@@ -294,7 +288,7 @@
     }
 
   while (i3.position >= 0)
-    {                           /* Inserting i2 at end */
+    {                           /* Inserting i3 at end */
       if (merge_output(r, &i3, mapping) < 0) goto err;
       if (i3.next(&i3) < 0) goto err;
     }
@@ -302,6 +296,8 @@
   finiSetIteration(&i1);
   finiSetIteration(&i2);
   finiSetIteration(&i3);
+
+  /* XXX raise ConflictError here if s1 is empty. */
 
   if (s1->next)
     {


=== Zope3/src/zodb/btrees/interfaces.py 1.5 => 1.6 ===
--- Zope3/src/zodb/btrees/interfaces.py:1.5	Wed Jan 15 23:47:01 2003
+++ Zope3/src/zodb/btrees/interfaces.py	Thu Jan 16 15:10:47 2003
@@ -24,45 +24,30 @@
             'Conflicting changes',
 
             # 2; i1's value changed in i2, but key+value deleted in i3
-            'Conflicting del and change',
+            'Conflicting delete and change',
 
             # 3; i1's value changed in i3, but key+value deleted in i2
-            'Conflicting del and change',
+            'Conflicting delete and change',
 
-            # 4; see XXX comments in bucket_merge:  this seems to be raised
-            # if:
-            #    i1 and i2 both add the same key to a set
-            #    i1 and i2 both add the same <key, value> pair to a mapping
-            #    i1 and i2 both delete the same key from a set or mapping
-            #    i1 and i2 both add the same key to a mapping but with
-            #        different values
-            # I believe only the last should be called a conflict, and in
-            # that case this msg should be "conflicting inserts".
+            # 4; i1 and i2 both added the same key, or both deleted the
+            # same key
             'Conflicting inserts or deletes',
 
-            # 5; see XXX comments in bucket_merge; i2 and i3 both deleted
-            # the same key if we get here, and I don't believe that should
-            # be a conflict.
+            # 5;  i2 and i3 both deleted the same key
             'Conflicting deletes',
 
-            # 6; see XXX comments in bucket_merge; i2 and i3 both added the
-            # same key, but this is considered a conflict even if it's a set,
-            # or if it's a mapping and the values also match.
+            # 6; i2 and i3 both added the same key
             'Conflicting inserts',
 
-            # 7; see XXX comments in bucket_merge; I don't believe it should
-            # be a conflict to delete the same key, and then this msg should
-            # be "Conflicting del and change".
-            'Conflicting dels or del and change',
-
-            # 8; see XXX comments in bucket_merge; I don't believe it should
-            # be a conflict to delete the same key, and then this msg should
-            # be "Conflicting del and change".
-            'Conflicting dels or del and change',
-
-            # 9; see XXX comments in bucket_merge; i2 and i3 both deleted
-            # the same key if we get here, and I don't believe that should
-            # be a conflict.
+            # 7; i2 and i3 both deleted the same key, or i2 changed the value
+            # associated with a key and i3 deleted that key
+            'Conflicting deletes, or delete and change',
+
+            # 8; i2 and i3 both deleted the same key, or i3 changed the value
+            # associated with a key and i2 deleted that key
+            'Conflicting deletes, or delete and change',
+
+            # 9; i2 and i3 both deleted the same key
             'Conflicting deletes',
             ]