[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