[Zodb-checkins] CVS: Zope/lib/python/BTrees/tests - test_check.py:1.1.4.1 testBTrees.py:1.48.2.1
Tim Peters
tim.one@comcast.net
Tue, 14 Jan 2003 17:26:23 -0500
Update of /cvs-repository/Zope/lib/python/BTrees/tests
In directory cvs.zope.org:/tmp/cvs-serv11176/lib/python/BTrees/tests
Modified Files:
Tag: Zope-2_6-branch
testBTrees.py
Added Files:
Tag: Zope-2_6-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 Zope/lib/python/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)
=== Zope/lib/python/BTrees/tests/testBTrees.py 1.48 => 1.48.2.1 ===
--- Zope/lib/python/BTrees/tests/testBTrees.py:1.48 Tue Aug 27 14:37:07 2002
+++ Zope/lib/python/BTrees/tests/testBTrees.py Tue Jan 14 17:26:19 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)