[Zope3-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:49 -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',
]