[Checkins] SVN: BTrees/branches/pure_python/ Split out conflict resolution between sets and buckets.
Tres Seaver
cvs-admin at zope.org
Wed Nov 14 21:29:35 UTC 2012
Log message for revision 128287:
Split out conflict resolution between sets and buckets.
Changed:
_U BTrees/branches/pure_python/
U BTrees/branches/pure_python/BTrees/_base.py
U BTrees/branches/pure_python/BTrees/tests/test__base.py
-=-
Modified: BTrees/branches/pure_python/BTrees/_base.py
===================================================================
--- BTrees/branches/pure_python/BTrees/_base.py 2012-11-14 21:29:33 UTC (rev 128286)
+++ BTrees/branches/pure_python/BTrees/_base.py 2012-11-14 21:29:34 UTC (rev 128287)
@@ -144,9 +144,79 @@
has_key = __contains__
+
+class _SetIteration(object):
+
+ def __init__(self, set, useValues=False, default=None):
+ if set is None:
+ set = ()
+ self.set = set
+ if useValues:
+ try:
+ itmeth = set.iteritems
+ except AttributeError:
+ itmeth = set.__iter__
+ useValues = False
+ else:
+ self.value = None
+ else:
+ itmeth = set.__iter__
+
+ self.useValues = useValues
+ self._next = itmeth().next
+ self.active = True
+ self.position = 0
+ self.value = default
+ self.advance()
+
+ def advance(self):
+ try:
+ if self.useValues:
+ self.key, self.value = self._next()
+ else:
+ self.key = self._next()
+ self.position += 1
+ except StopIteration:
+ self.active = False
+ self.position = -1
+
+ return self
+
+
+class _MappingBase(_Base):
+
+ def setdefault(self, key, value):
+ return self._set(self._to_key(key), self._to_value(value), True)[1]
+
+ def pop(self, key, default=_marker):
+ try:
+ return self._del(self._to_key(key))[1]
+ except KeyError:
+ if default is _marker:
+ raise
+ return default
+
+ def update(self, items):
+ if hasattr(items, 'iteritems'):
+ items = items.iteritems()
+ elif hasattr(items, 'items'):
+ items = items.items()
+
+ set = self.__setitem__
+ for i in items:
+ set(*i)
+
+ def __setitem__(self, key, value):
+ # Enforce test that key has non-default comparison.
+ if ( getattr(key, '__lt__', None) is None and
+ getattr(key, '__cmp__', None) is None):
+ raise TypeError("Can't use default __cmp__")
+ self._set(self._to_key(key), self._to_value(value))
+
+ def __delitem__(self, key):
+ self._del(self._to_key(key))
+
def _p_resolveConflict(self, s_old, s_com, s_new):
- is_set = getattr(self, '_values', self) is self
-
b_old = self.__class__()
if s_old is not None:
b_old.__setstate__(s_old)
@@ -173,24 +243,17 @@
result = self.__class__()
- if is_set:
- def merge_output(it):
- result._keys.append(it.key)
- it.advance()
- else:
- def merge_output(it):
- result._keys.append(it.key)
- result._values.append(it.value)
- it.advance()
+ def merge_output(it):
+ result._keys.append(it.key)
+ result._values.append(it.value)
+ it.advance()
while i_old.active and i_com.active and i_new.active:
cmp12 = cmp(i_old.key, i_com.key)
cmp13 = cmp(i_old.key, i_new.key)
if cmp12==0:
if cmp13==0:
- if is_set:
- result.add(i_old.key)
- elif i_com.value == i_old.value:
+ if i_com.value == i_old.value:
result[i_old.key] = i_new.value
elif i_new.value == i_old.value:
result[i_old.key] = i_com.value
@@ -201,7 +264,7 @@
i_new.advance()
elif (cmp13 > 0): # insert in new
merge_output(i_new)
- elif is_set or i_old.value == i_com.value: # deleted new
+ elif i_old.value == i_com.value: # deleted new
if i_new.position == 1:
# Deleted the first item. This will modify the
# parent node, so we don't know if merging will be
@@ -214,7 +277,7 @@
elif cmp13 == 0:
if cmp12 > 0: # insert committed
merge_output(i_com)
- elif is_set or i_old.value == i_new.value: # delete committed
+ elif i_old.value == i_new.value: # delete committed
if i_com.position == 1:
# Deleted the first item. This will modify the
# parent node, so we don't know if merging will be
@@ -251,17 +314,18 @@
cmp12 = cmp(i_old.key, i_com.key)
if cmp12 > 0: # insert committed
merge_output(i_com)
- elif cmp12 == 0 and (is_set or i_old.value == i_com.value): # del in new
+ elif cmp12 == 0 and (i_old.value == i_com.value): # del in new
i_old.advance()
i_com.advance()
else: # dueling deletes or delete and change
raise merge_error(7)
- while i_old.active and i_new.active: # committed deletes rest of original
+ while i_old.active and i_new.active:
+ # committed deletes rest of original
cmp13 = cmp(i_old.key, i_new.key)
if cmp13 > 0: # insert new
merge_output(i_new)
- elif cmp13 == 0 and (is_set or i_old.value == i_new.value):
+ elif cmp13 == 0 and (i_old.value == i_new.value):
# deleted in committed
i_old.advance()
i_new.advance()
@@ -286,94 +350,145 @@
return result.__getstate__()
-class _SetIteration(object):
+class _SetBase(_Base):
- def __init__(self, set, useValues=False, default=None):
- if set is None:
- set = ()
- self.set = set
- if useValues:
- try:
- itmeth = set.iteritems
- except AttributeError:
- itmeth = set.__iter__
- useValues = False
- else:
- self.value = None
- else:
- itmeth = set.__iter__
+ #_next = None
+ def add(self, key):
+ return self._set(self._to_key(key))[0]
- self.useValues = useValues
- self._next = itmeth().next
- self.active = True
- self.position = 0
- self.value = default
- self.advance()
+ insert = add
- def advance(self):
- try:
- if self.useValues:
- self.key, self.value = self._next()
- else:
- self.key = self._next()
- self.position += 1
- except StopIteration:
- self.active = False
- self.position = -1
+ def remove(self, key):
+ self._del(self._to_key(key))
- return self
+ def update(self, items):
+ add = self.add
+ for i in items:
+ add(i)
+ def _p_resolveConflict(self, s_old, s_com, s_new):
+ b_old = self.__class__()
+ if s_old is not None:
+ b_old.__setstate__(s_old)
+ b_com = self.__class__()
+ if s_com is not None:
+ b_com.__setstate__(s_com)
+ b_new = self.__class__()
+ if s_new is not None:
+ b_new.__setstate__(s_new)
+ if (b_com._next != b_old._next or
+ b_new._next != b_old._next):
+ raise BTreesConflictError(-1, -1, -1, 0)
-class _MappingBase(_Base):
+ if not b_com or not b_new:
+ raise BTreesConflictError(-1, -1, -1, 12)
- def setdefault(self, key, value):
- return self._set(self._to_key(key), self._to_value(value), True)[1]
+ i_old = _SetIteration(b_old, True)
+ i_com = _SetIteration(b_com, True)
+ i_new = _SetIteration(b_new, True)
- def pop(self, key, default=_marker):
- try:
- return self._del(self._to_key(key))[1]
- except KeyError:
- if default is _marker:
- raise
- return default
+ def merge_error(reason):
+ return BTreesConflictError(
+ i_old.position, i_com.position, i_new.position, reason)
- def update(self, items):
- if hasattr(items, 'iteritems'):
- items = items.iteritems()
- elif hasattr(items, 'items'):
- items = items.items()
+ result = self.__class__()
- set = self.__setitem__
- for i in items:
- set(*i)
+ def merge_output(it):
+ result._keys.append(it.key)
+ it.advance()
- def __setitem__(self, key, value):
- # Enforce test that key has non-default comparison.
- if ( getattr(key, '__lt__', None) is None and
- getattr(key, '__cmp__', None) is None):
- raise TypeError("Can't use default __cmp__")
- self._set(self._to_key(key), self._to_value(value))
+ while i_old.active and i_com.active and i_new.active:
+ cmp12 = cmp(i_old.key, i_com.key)
+ cmp13 = cmp(i_old.key, i_new.key)
+ if cmp12 == 0:
+ if cmp13 == 0:
+ result.add(i_old.key)
+ i_old.advance()
+ i_com.advance()
+ i_new.advance()
+ elif cmp13 > 0: # insert in new
+ merge_output(i_new)
+ else: # deleted new
+ if i_new.position == 1:
+ # Deleted the first item. This will modify the
+ # parent node, so we don't know if merging will be
+ # safe
+ raise merge_error(13)
+ i_old.advance()
+ i_com.advance()
+ elif cmp13 == 0:
+ if cmp12 > 0: # insert committed
+ merge_output(i_com)
+ else: # delete committed
+ if i_com.position == 1:
+ # Deleted the first item. This will modify the
+ # parent node, so we don't know if merging will be
+ # safe
+ raise merge_error(13)
+ i_old.advance()
+ i_new.advance()
+ else: # both keys changed
+ cmp23 = cmp(i_com.key, i_new.key)
+ if cmp23 == 0:
+ raise merge_error(4)
+ if cmp12 > 0: # insert committed
+ if cmp23 > 0: # insert i_new first
+ merge_output(i_new)
+ else:
+ merge_output(i_com)
+ elif cmp13 > 0: # insert i_new
+ merge_output(i_new)
+ else:
+ raise merge_error(5) # both deleted same key
- def __delitem__(self, key):
- self._del(self._to_key(key))
+ while i_com.active and i_new.active: # new inserts
+ cmp23 = cmp(i_com.key, i_new.key)
+ if cmp23 == 0:
+ raise merge_error(6) # dueling insert
+ if cmp23 > 0: # insert new
+ merge_output(i_new)
+ else: # insert committed
+ merge_output(i_com)
+ while i_old.active and i_com.active: # new deletes rest of original
+ cmp12 = cmp(i_old.key, i_com.key)
+ if cmp12 > 0: # insert committed
+ merge_output(i_com)
+ elif cmp12 == 0: # del in new
+ i_old.advance()
+ i_com.advance()
+ else: # dueling deletes or delete and change
+ raise merge_error(7)
-class _SetBase(_Base):
+ while i_old.active and i_new.active:
+ # committed deletes rest of original
+ cmp13 = cmp(i_old.key, i_new.key)
+ if cmp13 > 0: # insert new
+ merge_output(i_new)
+ elif cmp13 == 0: # deleted in committed
+ i_old.advance()
+ i_new.advance()
+ else: # dueling deletes or delete and change
+ raise merge_error(8)
- def add(self, key):
- return self._set(self._to_key(key))[0]
+ if i_old.active: # dueling deletes
+ raise merge_error(9)
- insert = add
+ while i_com.active:
+ merge_output(i_com)
- def remove(self, key):
- self._del(self._to_key(key))
+ while i_new.active:
+ merge_output(i_new)
- def update(self, items):
- add = self.add
- for i in items:
- add(i)
+ if len(result._keys) == 0:
+ # If the output bucket is empty, conflict resolution doesn't have
+ # enough info to unlink it from its containing BTree correctly.
+ raise merge_error(10)
+ result._next = b_old._next
+ return result.__getstate__()
+
class Bucket(_MappingBase, _BucketBase):
_value_type = list
@@ -453,12 +568,14 @@
def items(self, *args, **kw):
keys = self._keys
values = self._values
- return [(keys[i], values[i]) for i in xrange(*self._range(*args, **kw))]
+ return [(keys[i], values[i])
+ for i in xrange(*self._range(*args, **kw))]
def iteritems(self, *args, **kw):
keys = self._keys
values = self._values
- return ((keys[i], values[i]) for i in xrange(*self._range(*args, **kw)))
+ return ((keys[i], values[i])
+ for i in xrange(*self._range(*args, **kw)))
def __getstate__(self):
keys = self._keys
@@ -957,7 +1074,7 @@
class TreeSet(_SetBase, _Tree):
- pass
+ _p_resolveConflict = _Tree._p_resolveConflict
def _set_operation(s1, s2,
Modified: BTrees/branches/pure_python/BTrees/tests/test__base.py
===================================================================
--- BTrees/branches/pure_python/BTrees/tests/test__base.py 2012-11-14 21:29:33 UTC (rev 128286)
+++ BTrees/branches/pure_python/BTrees/tests/test__base.py 2012-11-14 21:29:34 UTC (rev 128287)
@@ -21,13 +21,6 @@
from .._base import _BucketBase
return _BucketBase
- def assertRaises(self, e_type, checked, *args, **kw):
- try:
- checked(*args, **kw)
- except e_type as e:
- return e
- self.fail("Didn't raise: %s" % e_type.__name__)
-
def _makeOne(self, *args, **kw):
return self._getTargetClass()(*args, **kw)
@@ -362,14 +355,24 @@
for key in KEYS:
self.assertTrue(key in bucket)
- def _with_setstate_set(self):
- class _WithSetState(self._getTargetClass()):
- def __setstate__(self, state):
- self._keys, self._next = state
- return _WithSetState()
- def _with_setstate_bucket(self):
- class _WithSetState(self._getTargetClass()):
+def _assertRaises(self, e_type, checked, *args, **kw):
+ try:
+ checked(*args, **kw)
+ except e_type as e:
+ return e
+ self.fail("Didn't raise: %s" % e_type.__name__)
+
+class Test__MappingBase(unittest.TestCase):
+
+ assertRaises = _assertRaises
+
+ def _getTargetClass(self):
+ from .._base import _MappingBase
+ return _MappingBase
+
+ def _makeOne(self):
+ class _TestMapping(self._getTargetClass()):
_values = None
def __setstate__(self, state):
state, self._next = state
@@ -378,13 +381,56 @@
for i in range(len(state) // 2):
self._keys.append(state[i])
self._values.append(state[i+1])
+ def clear(self):
+ self._keys, self._values, self._next = [], [], None
def iteritems(self):
return iter(zip(self._keys, self._values))
- return _WithSetState()
+ return _TestMapping()
+ def test__p_resolveConflict_delete_first_new(self):
+ from ..Interfaces import BTreesConflictError
+ bucket = self._makeOne()
+ s_old = (['a', 0, 'b', 1], None)
+ s_com = (['a', 1, 'b', 2, 'c', 3], None)
+ s_new = (['b', 4], None)
+ e = self.assertRaises(BTreesConflictError,
+ bucket._p_resolveConflict, s_old, s_com, s_new)
+ self.assertEqual(e.reason, 2)
+
+ def test__p_resolveConflict_delete_first_committed(self):
+ from ..Interfaces import BTreesConflictError
+ bucket = self._makeOne()
+ s_old = (['a', 0, 'b', 1], None)
+ s_com = (['b', 4], None)
+ s_new = (['a', 1, 'b', 2, 'c', 3], None)
+ e = self.assertRaises(BTreesConflictError,
+ bucket._p_resolveConflict, s_old, s_com, s_new)
+ self.assertEqual(e.reason, 3)
+
+
+class Test__SetBase(unittest.TestCase):
+
+ assertRaises = _assertRaises
+
+ def _getTargetClass(self):
+ from .._base import _SetBase
+ return _SetBase
+
+ def _makeOne(self):
+ class _TestSet(self._getTargetClass()):
+ def __setstate__(self, state):
+ self._keys, self._next = state
+ def clear(self):
+ self._keys, self._next = [], None
+ def __len__(self):
+ return len(self._keys)
+ def __iter__(self):
+ return iter(self._keys)
+ return _TestSet()
+
def test__p_resolveConflict_new_next(self):
from ..Interfaces import BTreesConflictError
- bucket = self._with_setstate_set()
+ bucket = self._makeOne()
N_NEW = object()
s_old = ([], None)
s_com = ([], N_NEW)
@@ -395,7 +441,7 @@
def test__p_resolveConflict_committed_next(self):
from ..Interfaces import BTreesConflictError
- bucket = self._with_setstate_set()
+ bucket = self._makeOne()
N_NEW = object()
s_old = ([], None)
s_com = ([], None)
@@ -406,7 +452,7 @@
def test__p_resolveConflict_empty_committed(self):
from ..Interfaces import BTreesConflictError
- bucket = self._with_setstate_set()
+ bucket = self._makeOne()
s_old = ([], None)
s_com = ([], None)
s_new = (['a'], None)
@@ -416,7 +462,7 @@
def test__p_resolveConflict_empty_new(self):
from ..Interfaces import BTreesConflictError
- bucket = self._with_setstate_set()
+ bucket = self._makeOne()
s_old = ([], None)
s_com = (['a'], None)
s_new = ([], None)
@@ -424,9 +470,9 @@
bucket._p_resolveConflict, s_old, s_com, s_new)
self.assertEqual(e.reason, 12)
- def test__p_resolveConflict_delete_first_new_set(self):
+ def test__p_resolveConflict_delete_first_new(self):
from ..Interfaces import BTreesConflictError
- bucket = self._with_setstate_set()
+ bucket = self._makeOne()
s_old = (['a','b'], None)
s_com = (['a','b','c'], None)
s_new = (['b'], None)
@@ -434,19 +480,9 @@
bucket._p_resolveConflict, s_old, s_com, s_new)
self.assertEqual(e.reason, 13)
- def test__p_resolveConflict_delete_first_new_bucket(self):
+ def test__p_resolveConflict_delete_first_committed(self):
from ..Interfaces import BTreesConflictError
- bucket = self._with_setstate_bucket()
- s_old = (['a', 0, 'b', 1], None)
- s_com = (['a', 1, 'b', 2, 'c', 3], None)
- s_new = (['b', 4], None)
- e = self.assertRaises(BTreesConflictError,
- bucket._p_resolveConflict, s_old, s_com, s_new)
- self.assertEqual(e.reason, 2)
-
- def test__p_resolveConflict_delete_first_committed_set(self):
- from ..Interfaces import BTreesConflictError
- bucket = self._with_setstate_set()
+ bucket = self._makeOne()
s_old = (['a','b'], None)
s_com = (['b'], None)
s_new = (['a', 'b', 'c'], None)
@@ -454,17 +490,7 @@
bucket._p_resolveConflict, s_old, s_com, s_new)
self.assertEqual(e.reason, 13)
- def test__p_resolveConflict_delete_first_committed_bucket(self):
- from ..Interfaces import BTreesConflictError
- bucket = self._with_setstate_bucket()
- s_old = (['a', 0, 'b', 1], None)
- s_com = (['b', 4], None)
- s_new = (['a', 1, 'b', 2, 'c', 3], None)
- e = self.assertRaises(BTreesConflictError,
- bucket._p_resolveConflict, s_old, s_com, s_new)
- self.assertEqual(e.reason, 3)
-
def test_suite():
return unittest.TestSuite((
unittest.makeSuite(Test_BucketBase),
More information about the checkins
mailing list