[Zodb-checkins] CVS: Zope/lib/python/BTrees/tests - testBTrees.py:1.35

[Tim Peters]

Update of /cvs-repository/Zope/lib/python/BTrees/tests
In directory cvs.zope.org:/tmp/cvs-serv31462/tests

Modified Files:
	testBTrees.py 
Log Message:
BTree_findRangeEnd():  Fixed "the range search bug":  if the smallest
key S in a bucket in a BTree is deleted, doing a range search on the
BTree with S on the high end may claim that the range is empty even when
it's not.  It proved difficult to fix this correctly and efficiently in
all cases (our BTrees don't like "searching backwards").  The
implementation here is a new and non-recursive one (in effect, to do
this efficiently you have to remember the deepest point in the tree where
it was *possible* to "go one left" of where binary search tells you to go;
an iterative algorithm makes that part all but obvious).  Alas, the
number of uses of persistence macros is amazing, unfortunately making
this still-hairy algorithm hard to follow.

testPathologicalRangeSearch():  uncommented the lines that failed
before this patch.  They pass now.

Insecurity:  The test case only exercises the simplest possible form
of the failure.  Any failing case is hard to provoke, even the simplest.
The hairier failing cases require generating degenerate trees, deep
and with some interior nodes near the top having just one or two children
(since the tree needs to be deep too, that isn't easy to provoke).  I'll
think about how to provoke this without needing to build up multi-million
element trees first; maybe using __setstate__ directly is the answer.


=== Zope/lib/python/BTrees/tests/testBTrees.py 1.34 => 1.35 ===
         del t[firstkey]
         therange = t.keys(-1, firstkey)
-        # XXX The next two currently fail.  I'm working on a fix (tim).
-        #self.assertEqual(len(therange), firstkey)
-        #self.assertEqual(list(therange), range(firstkey))
+        self.assertEqual(len(therange), firstkey)
+        self.assertEqual(list(therange), range(firstkey))
 
     def testInsertMethod(self):
         t = self.t