[Zodb-checkins] CVS: ZODB3/BTrees/tests - test_check.py:1.1.2.1 testBTrees.py:1.48.4.1

[Tim Peters]

Update of /cvs-repository/ZODB3/BTrees/tests
In directory cvs.zope.org:/tmp/cvs-serv11036/BTrees/tests

Modified Files:
      Tag: ZODB3-3_1-branch
	testBTrees.py 
Added Files:
      Tag: ZODB3-3_1-branch
	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 ZODB3/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 BTrees.OOBTree import OOBTree
from 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 testKeysSwapped(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)


=== ZODB3/BTrees/tests/testBTrees.py 1.48 => 1.48.4.1 ===
--- ZODB3/BTrees/tests/testBTrees.py:1.48	Tue Aug 27 14:37:07 2002
+++ ZODB3/BTrees/tests/testBTrees.py	Tue Jan 14 17:25:13 2003
@@ -18,6 +18,9 @@
 from BTrees.IOBTree import IOBTree, IOBucket, IOSet, IOTreeSet
 from BTrees.IIBTree import IIBTree, IIBucket, IISet, IITreeSet
 from BTrees.OIBTree import OIBTree, OIBucket, OISet, OITreeSet
+
+from BTrees.check import check
+
 from unittest import TestCase, TestSuite, TextTestRunner, makeSuite
 
 from glob import glob
@@ -524,6 +527,7 @@
 
     def tearDown(self):
         self.t._check()
+        check(self.t)
         MappingBase.tearDown(self)
 
     def testDeleteNoChildrenWorks(self):
@@ -981,6 +985,7 @@
         t = ts()
         t.__setstate__(((tree13, 4, tree5711), bucket1))
         t._check()
+        check(t)
         return t, [1, 3, 5, 7, 11]
 
     def testDegenerateBasicOps(self):
@@ -1042,6 +1047,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)