[Checkins] SVN: appendonly/ Conflict-resistant LIFO stack.
Tres Seaver
tseaver at palladion.com
Fri Jul 9 13:38:15 EDT 2010
Log message for revision 114389:
Conflict-resistant LIFO stack.
Changed:
A appendonly/
A appendonly/trunk/
A appendonly/trunk/CHANGES.txt
A appendonly/trunk/COPYRIGHT.txt
A appendonly/trunk/LICENSE.txt
A appendonly/trunk/README.txt
A appendonly/trunk/appendonly/
A appendonly/trunk/appendonly/__init__.py
A appendonly/trunk/appendonly/interfaces.py
A appendonly/trunk/appendonly/tests.py
A appendonly/trunk/setup.py
-=-
Added: appendonly/trunk/CHANGES.txt
===================================================================
--- appendonly/trunk/CHANGES.txt (rev 0)
+++ appendonly/trunk/CHANGES.txt 2010-07-09 17:38:15 UTC (rev 114389)
@@ -0,0 +1,7 @@
+``appendonly`` Changelog
+========================
+
+0.9 (unreleased)
+----------------
+
+- Initial public release.
Added: appendonly/trunk/COPYRIGHT.txt
===================================================================
--- appendonly/trunk/COPYRIGHT.txt (rev 0)
+++ appendonly/trunk/COPYRIGHT.txt 2010-07-09 17:38:15 UTC (rev 114389)
@@ -0,0 +1 @@
+Zope Foundation and Contributors
\ No newline at end of file
Added: appendonly/trunk/LICENSE.txt
===================================================================
--- appendonly/trunk/LICENSE.txt (rev 0)
+++ appendonly/trunk/LICENSE.txt 2010-07-09 17:38:15 UTC (rev 114389)
@@ -0,0 +1,44 @@
+Zope Public License (ZPL) Version 2.1
+
+A copyright notice accompanies this license document that identifies the
+copyright holders.
+
+This license has been certified as open source. It has also been designated as
+GPL compatible by the Free Software Foundation (FSF).
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+1. Redistributions in source code must retain the accompanying copyright
+notice, this list of conditions, and the following disclaimer.
+
+2. Redistributions in binary form must reproduce the accompanying copyright
+notice, this list of conditions, and the following disclaimer in the
+documentation and/or other materials provided with the distribution.
+
+3. Names of the copyright holders must not be used to endorse or promote
+products derived from this software without prior written permission from the
+copyright holders.
+
+4. The right to distribute this software or to use it for any purpose does not
+give you the right to use Servicemarks (sm) or Trademarks (tm) of the
+copyright
+holders. Use of them is covered by separate agreement with the copyright
+holders.
+
+5. If any files are modified, you must cause the modified files to carry
+prominent notices stating that you changed the files and the date of any
+change.
+
+Disclaimer
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS ``AS IS'' AND ANY EXPRESSED
+OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
+EVENT SHALL THE COPYRIGHT HOLDERS BE LIABLE FOR ANY DIRECT, INDIRECT,
+INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
+EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
Added: appendonly/trunk/README.txt
===================================================================
--- appendonly/trunk/README.txt (rev 0)
+++ appendonly/trunk/README.txt 2010-07-09 17:38:15 UTC (rev 114389)
@@ -0,0 +1,33 @@
+``appendonly`` README
+=====================
+
+This package provides a set of data structures for use in ZODB applications
+where standard BTrees are poor fits for an application's requirements.
+
+In particular, these data structures are designed to minimize conflict
+errors when doing frequent "append" operations to queues and stacks.
+
+
+``appendonly.AppendStack``
+--------------------------
+
+This class provides a LIFO stack of separately-persisted objects:
+
+- The stack manages a set of "layer" objects, with a configurable limit
+ on the number of layers. Each layer has a configurable maximum length,
+ and a sequential generation number.
+
+- The stack appends items to most recent layer until the layer is filled;
+ it then adds a new layer.
+
+- If the number of layers then exceeds the configured maximum, the stack
+ pruneds the oldest layer(s) to conform to that limit.
+
+- When pruning, the stack calls an application-supplied callback for
+ archiving / cleanup of the pruned layer.
+
+- Iteration over the stack yields (generation, index, object) tuples.
+ in reverse order to that in which the objects were appended.
+
+The stack is implemented as a single persistent record, with custom
+ZODB conflict resolution code.
Added: appendonly/trunk/appendonly/__init__.py
===================================================================
--- appendonly/trunk/appendonly/__init__.py (rev 0)
+++ appendonly/trunk/appendonly/__init__.py 2010-07-09 17:38:15 UTC (rev 114389)
@@ -0,0 +1,181 @@
+##############################################################################
+#
+# Copyright (c) 2010 Zope Foundation and Contributors.
+#
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.1 (ZPL). A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+#
+##############################################################################
+
+from persistent import Persistent
+from ZODB.POSException import ConflictError
+from zope.interface import implements
+
+from appendonly.interfaces import IAppendStack
+
+class _LayerFull(ValueError):
+ pass
+
+
+class _Layer(object):
+ """ Append-only list with maximum length.
+
+ - Raise `_LayerFull` on attempts to exceed that length.
+
+ - Iteration occurs in reverse order of appends, and yields (index, object)
+ tuples.
+
+ - Hold generation (a sequence number) on behalf of `AppendStack`.
+ """
+ def __init__(self, max_length=100, generation=0):
+ self._stack = []
+ self._max_length = max_length
+ self._generation = generation
+
+ def __iter__(self):
+ at = len(self._stack)
+ while at > 0:
+ at = at - 1
+ yield at, self._stack[at]
+
+ def newer(self, latest_index):
+ """ Yield items appended after `latest_index`.
+
+ Implemented as a method on the layer to work around lack of generator
+ expressions in Python 2.5.x.
+ """
+ for index, obj in self:
+ if index <= latest_index:
+ break
+ yield index, obj
+
+ def push(self, obj):
+ if len(self._stack) >= self._max_length:
+ raise _LayerFull()
+ self._stack.append(obj)
+
+
+class AppendStack(Persistent):
+ """ Append-only stack w/ garbage collection.
+
+ - Append items to most recent layer until full; then add a new layer.
+
+ - Discard "oldest" layer starting a new one.
+
+ - Invariant: the sequence of (generation, id) increases monotonically.
+
+ - Iteration occurs in reverse order of appends, and yields
+ (generation, index, object) tuples.
+ """
+ implements(IAppendStack)
+
+ def __init__(self, max_layers=10, max_length=100):
+ self._max_layers = max_layers
+ self._max_length = max_length
+ self._layers = [_Layer(max_length, generation=0L)]
+
+ def __iter__(self):
+ """ See IAppendStack.
+ """
+ for layer in self._layers:
+ for index, item in layer:
+ yield layer._generation, index, item
+
+ def newer(self, latest_gen, latest_index):
+ """ See IAppendStack.
+ """
+ for gen, index, obj in self:
+ if (gen, index) <= (latest_gen, latest_index):
+ break
+ yield gen, index, obj
+
+ def push(self, obj, pruner=None):
+ """ See IAppendStack.
+ """
+ layers = self._layers
+ max = self._max_layers
+ try:
+ layers[0].push(obj)
+ except _LayerFull:
+ new_layer = _Layer(self._max_length,
+ generation=layers[0]._generation+1L)
+ new_layer.push(obj)
+ self._layers.insert(0, new_layer)
+ self._layers, pruned = layers[:max], layers[max:]
+ if pruner is not None:
+ for layer in pruned:
+ pruner(layer._generation, layer._stack)
+
+ def __getstate__(self):
+ layers = [(x._generation, x._stack) for x in self._layers]
+ return (self._max_layers, self._max_length, layers)
+
+ def __setstate__(self, state):
+ self._max_layers, self._max_length, layer_data = state
+ self._layers = []
+ for generation, items in layer_data:
+ layer = _Layer(self._max_length, generation)
+ for item in items:
+ layer.push(item)
+ self._layers.append(layer)
+
+ #
+ # ZODB Conflict resolution
+ #
+ # The overall approach here is to compute the 'delta' from old -> new
+ # (objects added in new, not present in old), and push them onto the
+ # committed state to create a merged state.
+ # Unresolvable errors include:
+ # - any difference between O <-> C <-> N on the non-layers attributes.
+ # - either C or N has its oldest layer in a later generation than O's
+ # newest layer.
+ # Compute the O -> N diff via the following:
+ # - Find the layer, N' in N whose generation matches the newest generation
+ # in O, O'.
+ # - Compute the new items in N` by slicing it using the len(O').
+ # - That slice, plus any newer layers in N, form the set to be pushed
+ # onto C.
+ #
+ def _p_resolveConflict(self, old, committed, new):
+ o_m_layers, o_m_length, o_layers = old
+ c_m_layers, c_m_length, c_layers = committed
+ m_layers = [x[:] for x in c_layers]
+ n_m_layers, n_m_length, n_layers = new
+
+ if not o_m_layers == n_m_layers == n_m_layers:
+ raise ConflictError('Conflicting max layers')
+
+ if not o_m_length == c_m_length == n_m_length:
+ raise ConflictError('Conflicting max length')
+
+ o_latest_gen = o_layers[0][0]
+ o_latest_items = o_layers[0][1]
+ c_earliest_gen = c_layers[-1][0]
+ n_earliest_gen = n_layers[-1][0]
+
+ if o_latest_gen < c_earliest_gen:
+ raise ConflictError('Committed obsoletes old')
+
+ if o_latest_gen < n_earliest_gen:
+ raise ConflictError('New obsoletes old')
+
+ new_objects = []
+ for n_generation, n_items in n_layers:
+ if n_generation > o_latest_gen:
+ new_objects[:0] = n_items
+ elif n_generation == o_latest_gen:
+ new_objects[:0] = n_items[len(o_latest_items):]
+ else:
+ break
+
+ while new_objects:
+ to_push, new_objects = new_objects[0], new_objects[1:]
+ if len(m_layers[0][1]) == c_m_length:
+ m_layers.insert(0, (m_layers[0][0]+1L, []))
+ m_layers[0][1].append(to_push)
+
+ return c_m_layers, c_m_length, m_layers[:c_m_layers]
Added: appendonly/trunk/appendonly/interfaces.py
===================================================================
--- appendonly/trunk/appendonly/interfaces.py (rev 0)
+++ appendonly/trunk/appendonly/interfaces.py 2010-07-09 17:38:15 UTC (rev 114389)
@@ -0,0 +1,44 @@
+##############################################################################
+#
+# Copyright (c) 2010 Zope Foundation and Contributors.
+#
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.1 (ZPL). A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+#
+##############################################################################
+
+from zope.interface import Interface
+
+class IAppendStack(Interface):
+ """ Append-only stack w/ garbage collection.
+
+ - Append items to most recent layer until full; then add a new layer.
+
+ - When max layers reached, discard "oldest" layer starting a new one.
+
+ - Invariant: the sequence of (generation, id) increases monotonically.
+
+ - Iteration occurs in reverse order of appends, and yields
+ (generation, index, object) tuples.
+ """
+ def __iter__():
+ """ Yield (generation, index, object) in most-recent first order.
+ """
+
+ def newer(latest_gen, latest_index):
+ """ Yield items newer than (`latest_gen`, `latest_index`).
+
+ Implemented as a method on the layer to work around lack of generator
+ expressions in Python 2.5.x.
+ """
+
+ def push(obj, pruner=None):
+ """ Append an item to the stack.
+
+ - If `pruner` is passed, call it with the generation and items of
+ any pruned layer.
+ """
Added: appendonly/trunk/appendonly/tests.py
===================================================================
--- appendonly/trunk/appendonly/tests.py (rev 0)
+++ appendonly/trunk/appendonly/tests.py 2010-07-09 17:38:15 UTC (rev 114389)
@@ -0,0 +1,431 @@
+##############################################################################
+#
+# Copyright (c) 2010 Zope Foundation and Contributors.
+#
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.1 (ZPL). A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+#
+##############################################################################
+import unittest
+
+class LayerTests(unittest.TestCase):
+
+ def _getTargetClass(self):
+ from appendonly import _Layer
+ return _Layer
+
+ def _makeOne(self, *args, **kw):
+ return self._getTargetClass()(*args, **kw)
+
+ def test_ctor_defaults(self):
+ layer = self._makeOne()
+ self.assertEqual(layer._max_length, 100)
+ self.failUnless(type(layer._stack) is list)
+ self.assertEqual(layer._generation, 0)
+
+ def test_ctor_w_positional(self):
+ layer = self._makeOne(4, 14)
+ self.assertEqual(layer._max_length, 4)
+ self.failUnless(type(layer._stack) is list)
+ self.assertEqual(layer._generation, 14)
+
+ def test_ctor_w_max_length(self):
+ layer = self._makeOne(max_length=14)
+ self.assertEqual(layer._max_length, 14)
+
+ def test_ctor_w_generation(self):
+ layer = self._makeOne(generation=12)
+ self.assertEqual(layer._generation, 12)
+
+ def test___iter___empty(self):
+ layer = self._makeOne()
+ self.assertEqual(list(layer), [])
+
+ def test_newer_empty(self):
+ layer = self._makeOne()
+ self.assertEqual(list(layer.newer(0)), [])
+
+ def test_newer_miss(self):
+ layer = self._makeOne()
+ layer.push(object())
+ self.assertEqual(list(layer.newer(0)), [])
+
+ def test_newer_hit(self):
+ layer = self._makeOne()
+ OBJ1 = object()
+ OBJ2 = object()
+ OBJ3 = object()
+ layer.push(OBJ1)
+ layer.push(OBJ2)
+ layer.push(OBJ3)
+ self.assertEqual(list(layer.newer(0)),
+ [(2, OBJ3), (1, OBJ2)])
+
+ def test_push_one(self):
+ layer = self._makeOne()
+ OBJ = object()
+ layer.push(OBJ)
+ self.assertEqual(list(layer), [(0, OBJ)])
+
+ def test_push_many(self):
+ layer = self._makeOne()
+ OBJ1, OBJ2, OBJ3 = object(), object(), object()
+ layer.push(OBJ1)
+ layer.push(OBJ2)
+ layer.push(OBJ3)
+ self.assertEqual(list(layer), [(2, OBJ3),
+ (1, OBJ2),
+ (0, OBJ1),
+ ])
+
+ def test_push_overflow(self):
+ layer = self._makeOne(2)
+ OBJ1, OBJ2, OBJ3 = object(), object(), object()
+ layer.push(OBJ1)
+ layer.push(OBJ2)
+ self.assertRaises(ValueError, layer.push, OBJ3)
+ self.assertEqual(list(layer), [(1, OBJ2),
+ (0, OBJ1),
+ ])
+
+class AppendStackTests(unittest.TestCase):
+
+ def _getTargetClass(self):
+ from appendonly import AppendStack
+ return AppendStack
+
+ def _makeOne(self, *args, **kw):
+ return self._getTargetClass()(*args, **kw)
+
+ def test_class_conforms_to_IAppendStack(self):
+ from zope.interface.verify import verifyClass
+ from appendonly.interfaces import IAppendStack
+ verifyClass(IAppendStack, self._getTargetClass())
+
+ def test_instance_conforms_to_IAppendStack(self):
+ from zope.interface.verify import verifyObject
+ from appendonly.interfaces import IAppendStack
+ verifyObject(IAppendStack, self._makeOne())
+
+ def test_ctor_defaults(self):
+ stack = self._makeOne()
+ self.assertEqual(stack._max_layers, 10)
+ self.assertEqual(stack._max_length, 100)
+
+ def test_ctor_w_max_layers(self):
+ stack = self._makeOne(max_layers=37)
+ self.assertEqual(stack._max_layers, 37)
+
+ def test_ctor_w_max_length(self):
+ stack = self._makeOne(max_length=14)
+ self.assertEqual(stack._max_length, 14)
+
+ def test___iter___empty(self):
+ stack = self._makeOne()
+ self.assertEqual(list(stack), [])
+
+ def test_newer_empty(self):
+ stack = self._makeOne()
+ self.assertEqual(list(stack.newer(0, 0)), [])
+
+ def test_newer_miss(self):
+ stack = self._makeOne()
+ stack.push(object())
+ self.assertEqual(list(stack.newer(0, 0)), [])
+
+ def test_newer_hit(self):
+ stack = self._makeOne()
+ OBJ1 = object()
+ OBJ2 = object()
+ OBJ3 = object()
+ stack.push(OBJ1)
+ stack.push(OBJ2)
+ stack.push(OBJ3)
+ self.assertEqual(list(stack.newer(0, 0)),
+ [(0, 2, OBJ3), (0, 1, OBJ2)])
+
+ def test_newer_hit_across_layers(self):
+ stack = self._makeOne(max_length=2)
+ OBJ1 = object()
+ OBJ2 = object()
+ OBJ3 = object()
+ stack.push(OBJ1)
+ stack.push(OBJ2)
+ stack.push(OBJ3)
+ self.assertEqual(list(stack.newer(0, 0)),
+ [(1, 0, OBJ3), (0, 1, OBJ2)])
+
+ def test_push_one(self):
+ stack = self._makeOne()
+ OBJ = object()
+ stack.push(OBJ)
+ self.assertEqual(list(stack), [(0, 0, OBJ)])
+ self.assertEqual(len(stack._layers), 1)
+
+ def test_push_many(self):
+ stack = self._makeOne(max_length=2)
+ OBJ1, OBJ2, OBJ3 = object(), object(), object()
+ stack.push(OBJ1)
+ stack.push(OBJ2)
+ stack.push(OBJ3)
+ self.assertEqual(list(stack), [(1, 0, OBJ3),
+ (0, 1, OBJ2),
+ (0, 0, OBJ1),
+ ])
+ self.assertEqual(len(stack._layers), 2)
+ self.assertEqual(stack._layers[0]._generation, 1)
+ self.assertEqual(stack._layers[1]._generation, 0)
+
+ def test_push_trimming_layers(self):
+ stack = self._makeOne(max_layers=4)
+ for obj in range(1001):
+ stack.push(obj)
+ found = list(stack)
+ self.assertEqual(len(found), 301)
+ self.assertEqual(found[0], (10, 0, 1000))
+ self.assertEqual(found[-1], (7, 0, 700))
+ self.assertEqual(len(stack._layers), 4)
+ self.assertEqual(stack._layers[0]._generation, 10)
+ self.assertEqual(stack._layers[1]._generation, 9)
+ self.assertEqual(stack._layers[2]._generation, 8)
+ self.assertEqual(stack._layers[3]._generation, 7)
+
+ def test_push_trimming_layers_with_archive_utility(self):
+ _pruned = {}
+ def _prune(generation, items):
+ _pruned[generation] = items
+ stack = self._makeOne(max_layers=4)
+ for obj in range(1001):
+ stack.push(obj, pruner=_prune)
+ found = list(stack)
+ self.assertEqual(len(found), 301)
+ self.assertEqual(found[0], (10, 0, 1000))
+ self.assertEqual(found[-1], (7, 0, 700))
+ self.assertEqual(len(stack._layers), 4)
+ self.assertEqual(stack._layers[0]._generation, 10)
+ self.assertEqual(stack._layers[1]._generation, 9)
+ self.assertEqual(stack._layers[2]._generation, 8)
+ self.assertEqual(stack._layers[3]._generation, 7)
+ self.assertEqual(len(_pruned), 7)
+ self.assertEqual(_pruned[0], range(0, 100))
+ self.assertEqual(_pruned[1], range(100, 200))
+ self.assertEqual(_pruned[2], range(200, 300))
+ self.assertEqual(_pruned[3], range(300, 400))
+ self.assertEqual(_pruned[4], range(400, 500))
+ self.assertEqual(_pruned[5], range(500, 600))
+ self.assertEqual(_pruned[6], range(600, 700))
+
+ def test___getstate___empty(self):
+ stack = self._makeOne()
+ self.assertEqual(stack.__getstate__(), (10, 100, [(0L, [])]))
+
+ def test___getstate___filled(self):
+ stack = self._makeOne(2, 3)
+ for i in range(10):
+ stack.push(i)
+ self.assertEqual(stack.__getstate__(),
+ (2, 3, [(3L, [9]), (2L, [6, 7, 8])]))
+
+ def test___setstate___(self):
+ stack = self._makeOne()
+ STATE = (2, # _max_layers
+ 3, # _max_length
+ [(3L, [9]), # _layers[0] as (generation, list)
+ (2L, [6, 7, 8]), # _layers[1] as (generation, list)
+ ],
+ )
+ stack.__setstate__(STATE)
+ self.assertEqual(stack._max_layers, 2)
+ self.assertEqual(stack._max_length, 3)
+ self.assertEqual(list(stack), [(3, 0, 9),
+ (2, 2, 8),
+ (2, 1, 7),
+ (2, 0, 6),
+ ])
+
+ def test__p_resolveConflict_mismatched_max_layers(self):
+ from ZODB.POSException import ConflictError
+ O_STATE = (2, # _max_layers
+ 3, # _max_length
+ [(3L, [9]), # _layers[0] as (generation, list)
+ (2L, [6, 7, 8]), # _layers[1] as (generation, list)
+ ],
+ )
+ C_STATE = (2, # _max_layers
+ 3, # _max_length
+ [(3L, [9]), # _layers[0] as (generation, list)
+ (2L, [6, 7, 8]), # _layers[1] as (generation, list)
+ ],
+ )
+ N_STATE = (3, # _max_layers
+ 3, # _max_length
+ [(3L, [9]), # _layers[0] as (generation, list)
+ (2L, [6, 7, 8]), # _layers[1] as (generation, list)
+ ],
+ )
+ stack = self._makeOne()
+ self.assertRaises(ConflictError, stack._p_resolveConflict,
+ O_STATE, C_STATE, N_STATE)
+
+ def test__p_resolveConflict_mismatched_max_length(self):
+ from ZODB.POSException import ConflictError
+ O_STATE = (2, # _max_layers
+ 3, # _max_length
+ [(3L, [9]), # _layers[0] as (generation, list)
+ (2L, [6, 7, 8]), # _layers[1] as (generation, list)
+ ],
+ )
+ C_STATE = (2, # _max_layers
+ 3, # _max_length
+ [(3L, [9]), # _layers[0] as (generation, list)
+ (2L, [6, 7, 8]), # _layers[1] as (generation, list)
+ ],
+ )
+ N_STATE = (2, # _max_layers
+ 4, # _max_length
+ [(3L, [9]), # _layers[0] as (generation, list)
+ (2L, [6, 7, 8]), # _layers[1] as (generation, list)
+ ],
+ )
+ stack = self._makeOne()
+ self.assertRaises(ConflictError, stack._p_resolveConflict,
+ O_STATE, C_STATE, N_STATE)
+
+ def test__p_resolveConflict_old_latest_commited_earliest(self):
+ from ZODB.POSException import ConflictError
+ O_STATE = (2, # _max_layers
+ 3, # _max_length
+ [(3L, [9]), # _layers[0] as (generation, list)
+ (2L, [6, 7, 8]), # _layers[1] as (generation, list)
+ ],
+ )
+ C_STATE = (2, # _max_layers
+ 3, # _max_length
+ [(5L, [29]), # _layers[0] as (generation, list)
+ (4L, [26, 27, 28]), # _layers[1] as (generation, list)
+ ],
+ )
+ N_STATE = (2, # _max_layers
+ 3, # _max_length
+ [(3L, [9, 10]), # _layers[0] as (generation, list)
+ (2L, [6, 7, 8]), # _layers[1] as (generation, list)
+ ],
+ )
+ stack = self._makeOne()
+ self.assertRaises(ConflictError, stack._p_resolveConflict,
+ O_STATE, C_STATE, N_STATE)
+
+ def test__p_resolveConflict_old_latest_new_earliest(self):
+ from ZODB.POSException import ConflictError
+ O_STATE = (2, # _max_layers
+ 3, # _max_length
+ [(3L, [9]), # _layers[0] as (generation, list)
+ (2L, [6, 7, 8]), # _layers[1] as (generation, list)
+ ],
+ )
+ C_STATE = (2, # _max_layers
+ 3, # _max_length
+ [(3L, [9, 10]), # _layers[0] as (generation, list)
+ (2L, [6, 7, 8]), # _layers[1] as (generation, list)
+ ],
+ )
+ N_STATE = (2, # _max_layers
+ 3, # _max_length
+ [(5L, [29]), # _layers[0] as (generation, list)
+ (4L, [26, 27, 28]), # _layers[1] as (generation, list)
+ ],
+ )
+ stack = self._makeOne()
+ self.assertRaises(ConflictError, stack._p_resolveConflict,
+ O_STATE, C_STATE, N_STATE)
+
+ def test__p_resolveConflict_no_added_layers(self):
+ O_STATE = (2, # _max_layers
+ 3, # _max_length
+ [(3L, [9]), # _layers[0] as (generation, list)
+ (2L, [6, 7, 8]), # _layers[1] as (generation, list)
+ ],
+ )
+ C_STATE = (2, # _max_layers
+ 3, # _max_length
+ [(3L, [9, 10]), # _layers[0] as (generation, list)
+ (2L, [6, 7, 8]), # _layers[1] as (generation, list)
+ ],
+ )
+ N_STATE = (2, # _max_layers
+ 3, # _max_length
+ [(3L, [9, 11]), # _layers[0] as (generation, list)
+ (2L, [6, 7, 8]), # _layers[1] as (generation, list)
+ ],
+ )
+ M_STATE = (2, # _max_layers
+ 3, # _max_length
+ [(3L, [9, 10, 11]),# _layers[0] as (generation, list)
+ (2L, [6, 7, 8]), # _layers[1] as (generation, list)
+ ],
+ )
+ stack = self._makeOne()
+ merged = stack._p_resolveConflict(O_STATE, C_STATE, N_STATE)
+ self.assertEqual(merged, M_STATE)
+
+ def test__p_resolveConflict_added_committed_layer(self):
+ O_STATE = (2, # _max_layers
+ 3, # _max_length
+ [(3L, [9]), # _layers[0] as (generation, list)
+ (2L, [6, 7, 8]), # _layers[1] as (generation, list)
+ ],
+ )
+ C_STATE = (2, # _max_layers
+ 3, # _max_length
+ [(4L, [12]), # _layers[0] as (generation, list)
+ (3L, [9, 10, 11]),# _layers[1] as (generation, list)
+ ],
+ )
+ N_STATE = (2, # _max_layers
+ 3, # _max_length
+ [(3L, [9, 13]), # _layers[0] as (generation, list)
+ (2L, [6, 7, 8]), # _layers[1] as (generation, list)
+ ],
+ )
+ M_STATE = (2, # _max_layers
+ 3, # _max_length
+ [(4L, [12, 13]), # _layers[0] as (generation, list)
+ (3L, [9, 10, 11]),# _layers[1] as (generation, list)
+ ],
+ )
+ stack = self._makeOne()
+ merged = stack._p_resolveConflict(O_STATE, C_STATE, N_STATE)
+ self.assertEqual(merged, M_STATE)
+
+ def test__p_resolveConflict_added_new_layer(self):
+ O_STATE = (2, # _max_layers
+ 3, # _max_length
+ [(3L, [9]), # _layers[0] as (generation, list)
+ (2L, [6, 7, 8]), # _layers[1] as (generation, list)
+ ],
+ )
+ C_STATE = (2, # _max_layers
+ 3, # _max_length
+ [(3L, [9, 10]), # _layers[0] as (generation, list)
+ (2L, [6, 7, 8]), # _layers[1] as (generation, list)
+ ],
+ )
+ N_STATE = (2, # _max_layers
+ 3, # _max_length
+ [(4L, [13, 14]), # _layers[0] as (generation, list)
+ (3L, [9, 11, 12]),# _layers[1] as (generation, list)
+ ],
+ )
+ M_STATE = (2, # _max_layers
+ 3, # _max_length
+ [(4L, [12, 13, 14]),# _layers[0] as (generation, list)
+ (3L, [9, 10, 11]),# _layers[1] as (generation, list)
+ ],
+ )
+ stack = self._makeOne()
+ merged = stack._p_resolveConflict(O_STATE, C_STATE, N_STATE)
+ self.assertEqual(merged, M_STATE)
Added: appendonly/trunk/setup.py
===================================================================
--- appendonly/trunk/setup.py (rev 0)
+++ appendonly/trunk/setup.py 2010-07-09 17:38:15 UTC (rev 114389)
@@ -0,0 +1,49 @@
+##############################################################################
+#
+# Copyright (c) 2010 Zope Foundation and Contributors.
+#
+# This software is subject to the provisions of the Zope Public License,
+# Version 2.1 (ZPL). A copy of the ZPL should accompany this distribution.
+# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
+# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
+# FOR A PARTICULAR PURPOSE.
+#
+##############################################################################
+import os
+
+from setuptools import find_packages
+from setuptools import setup
+
+here = os.path.abspath(os.path.dirname(__file__))
+README = open(os.path.join(here, 'README.txt')).read()
+CHANGES = open(os.path.join(here, 'CHANGES.txt')).read()
+
+setup(name='appendonly',
+ version='0.9dev',
+ description='Persistent append-only data structures.',
+ long_description=README + '\n\n' + CHANGES,
+ classifiers=[
+ "Development Status :: 3 - Alpha",
+ "Intended Audience :: Developers",
+ "License :: OSI Approved :: Zope Public License",
+ "Operating System :: OS Independent",
+ "Programming Language :: Python :: 2.4",
+ "Programming Language :: Python :: 2.5",
+ "Programming Language :: Python :: 2.6",
+ ],
+ author='Tres Seaver, Agendaless Consulting, Inc.',
+ author_email='tseaver at agendaless.co',
+ license='ZPL',
+ url='',
+ keywords='zodb',
+ packages=find_packages(),
+ include_package_data=True,
+ zip_safe=False,
+ install_requires = [
+ 'ZODB3',
+ 'zope.interface',
+ ],
+ test_suite="appendonly.tests",
+)
+
More information about the checkins
mailing list