[Zodb-checkins] CVS: Zope3/src/zodb/btrees/tests - test_check.py:1.1 test_btrees.py:1.3

[Tim Peters]

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

Modified Files:
	test_btrees.py 
Added Files:
	test_check.py 
Log Message:
New btrees module check.py (and test program).  The primary new function
is check.check(btree), which performs value-based sanity checks on a BTree
(or TreeSet) that the btree._check() method doesn't do.  The new checks
include that all the bucket keys are in sorted order, and that all the
keys within each bucket, and within each internal BTree node, lie within
the range necessary for that node.  That last is a subtle invariant that
can't be checked locally:  it requires propagating range info down the
tree, and modifying it for each child and each level.  This *should* catch
any BTree B for which iterating over the keys yields a key K for which
B.has_key(K) returns false.

Another function check.display(btree) prints the internal structure of
a BTree (or TreeSet, Bucket, or Set) to stdout.  If check.check(B)
ever complains, a clearer picture of the damage can be gotten by
staring at check.display(B)'s output.

Also beefed up the regular BTree tests by calling check.check() in key
places.  No surprises (the tests still pass).


=== Added File Zope3/src/zodb/btrees/tests/test_check.py ===
##############################################################################
#
# Copyright (c) 2003 Zope Corporation and Contributors.
# All Rights Reserved.
#
# This software is subject to the provisions of the Zope Public License,
# Version 2.0 (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.
#
##############################################################################
"""Test the BTree check.check() function."""

import unittest

from zodb.btrees.OOBTree import OOBTree
from zodb.btrees.check import check

class CheckTest(unittest.TestCase):

    def setUp(self):
        self.t = t = OOBTree()
        for i in range(31):
            t[i] = 2*i
        self.state = t.__getstate__()

    def testNormal(self):
        s = self.state
        # Looks like (state, first_bucket)
        # where state looks like (bucket0, 15, bucket1).
        self.assertEqual(len(s), 2)
        self.assertEqual(len(s[0]), 3)
        self.assertEqual(s[0][1], 15)
        self.t._check() # shouldn't blow up
        check(self.t)   # shouldn't blow up

    def testKeyTooLarge(self):
        # Damage an invariant by dropping the BTree key to 14.
        s = self.state
        news = (s[0][0], 14, s[0][2]), s[1]
        self.t.__setstate__(news)
        self.t._check() # not caught
        try:
            # Expecting "... key %r >= upper bound %r at index %d"
            check(self.t)
        except AssertionError, detail:
            self.failUnless(str(detail).find(">= upper bound") > 0)
        else:
            self.fail("expected self.t_check() to catch the problem")

    def testKeyTooSmall(self):
        # Damage an invariant by bumping the BTree key to 16.
        s = self.state
        news = (s[0][0], 16, s[0][2]), s[1]
        self.t.__setstate__(news)
        self.t._check() # not caught
        try:
            # Expecting "... key %r < lower bound %r at index %d"
            check(self.t)
        except AssertionError, detail:
            self.failUnless(str(detail).find("< lower bound") > 0)
        else:
            self.fail("expected self.t_check() to catch the problem")

    def testKeysSwappedl(self):
        # Damage an invariant by swapping two key/value pairs.
        s = self.state
        # Looks like (state, first_bucket)
        # where state looks like (bucket0, 15, bucket1).
        (b0, num, b1), firstbucket = s
        self.assertEqual(b0[4], 8)
        self.assertEqual(b0[5], 10)
        b0state = b0.__getstate__()
        self.assertEqual(len(b0state), 2)
        # b0state looks like
        # ((k0, v0, k1, v1, ...), nextbucket)
        pairs, nextbucket = b0state
        self.assertEqual(pairs[8], 4)
        self.assertEqual(pairs[9], 8)
        self.assertEqual(pairs[10], 5)
        self.assertEqual(pairs[11], 10)
        newpairs = pairs[:8] + (5, 10, 4, 8) + pairs[12:]
        b0.__setstate__((newpairs, nextbucket))
        self.t._check() # not caught
        try:
            check(self.t)
        except AssertionError, detail:
            self.failUnless(str(detail).find(
                "key 5 at index 4 >= key 4 at index 5") > 0)
        else:
            self.fail("expected self.t_check() to catch the problem")

def test_suite():
    return unittest.makeSuite(CheckTest)


=== Zope3/src/zodb/btrees/tests/test_btrees.py 1.2 => 1.3 ===
--- Zope3/src/zodb/btrees/tests/test_btrees.py:1.2	Wed Dec 25 09:12:17 2002
+++ Zope3/src/zodb/btrees/tests/test_btrees.py	Tue Jan 14 16:51:46 2003
@@ -16,6 +16,9 @@
 from zodb.btrees.IIBTree import IIBTree, IIBucket, IISet, IITreeSet
 from zodb.btrees.OIBTree import OIBTree, OIBucket, OISet, OITreeSet
 
+from zodb.btrees.check import check
+
+
 from transaction import get_transaction
 
 from glob import glob
@@ -646,6 +649,7 @@
 
     def tearDown(self):
         self.t._check()
+        check(self.t)
         MappingBase.tearDown(self)
 
     def testDeleteNoChildrenWorks(self):
@@ -1072,6 +1076,7 @@
         t = ts()
         t.__setstate__(((tree13, 4, tree5711), bucket1))
         t._check()
+        check(t)
         return t, [1, 3, 5, 7, 11]
 
     def testBasicOps(self):
@@ -1133,6 +1138,7 @@
                 t.remove(key)
                 keys.remove(key)
                 t._check()
+                check(t)
                 self._checkRanges(t, keys)
             # We removed all the keys, so the tree should be empty now.
             self.assertEqual(t.__getstate__(), None)