XXX Should start still do path munging?

search returned a seemingly random slice of the tree.  A new test on the
painfully constructed highly-degenerate BTree turned up lots of these.
It turns out that BTree_rangeSearch had a much harder job than it
thought it had <0.7 wink>.

for lo > hi either, except if they happened to be in the same bucket.  All
sorts of strange results followed (the range should be empty if lo > hi,
and is after this patch).

passed in, it was quite possible for this to return *low > *high, and the
caller could crash due to trying to create a list with "negative length".
Changed the routine to consider a range empty if min>max on input, and added
test cases that fail before this patch.

legitimate) BTree.  New test testDegenerateBasicOps() does basic sanity
checks on it.  More tests against this tree will follow.

classes entirely (like for IITreeSets), and to run other test classes
twice.

plus cleanup of a previous such fix.

bucket reference.

BTree_rangeSearch():  Fixed one place likewise.

little on redundant activations.

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.

references, what must not be and what may be a ghost, and exactly what
"last" means, it was surprisingly unclear).  Also simplified the
implementation (to my eyes -- it's arguable, but I'm the one working
on it, so my eyes count <wink>).  I believe this routine is key to
fixing the range-search bug efficiently.

commented out for now, because it fails.  I'm working on a fix.  The
problem was found by eyeballing the range-test implementation.  If you
delete a key from a BTree that just happens to be the first key in a
bucket, then a later high-end range search giving that specific key as
the endpoint claims that no keys are in the range, and whether or not
that's actually true.

so makes the full suite brittle.  Cleaned out all the places where unit
tests change sys.path.  (Use the PYTHONPATH environment variable instead.)

Also brought SearchIndex tests up to date, which I didn't really need to do
since SearchIndex is deprecated, but I did it as part of figuring out the
failed Interface tests, so I might as well check in my work. ;-)  One of the
test modules in SearchIndex forgets to define a global named "Dummy",
actually, so all the tests were failing before this checkin anyway.

Reindent MUCH_RING_CHECKING test.

Ignore invalidations on objects where _p_oid is None.
In other places, assert the _p_oid is not None.

Also, add whitespace in a bunch of places.

on Mac OS Roman Numeral <wink>.  The prototypes sorters.c needs here
should be supplied by <stdlib.h> anyway, which is also being included.

caller was compensating for this, others weren't, easier to fix the
routine than its callers (it's unexpected that an error return may
require the caller to decref an output argument).  Noted but did not
yet fix what looks to be a subtle algorithmic problem that can result
in a bad answer in an unlikely (but possible) case.

Do not encode the file position in the transaction id used for undo.
An attacker could construct a pickle with a bogus transaction record
in its binary data, deduce the position of the pickle in the file from
the undo log, then submit an undo with a bogus file position that
caused the pickle to get written as a regular data record.  Bad stuff.

The new implementation uses a straight linear search backwards from
the most recent transaction header.

directly without doing the unghostification dance.  Repaired to cache
the child length once in a local vrbl, bracketed by the right
persistence stuff.

an error return.

error return let a newly allocated object leak; curiously, there was
one more of these in the Zope3 version of the code than on the trunk.

If MUCH_RING_CHECKING is not defined (the default), then:
  - use a macro for OBJECT_FROM_RING() instead of a function call, and
  - define IS_RING_CORRUPT() to be constant 0.

XXX Sometime before Zope 2.6 final we should probably remove the
MUCH_RING_CHECKING and ENGINE_NOISE code entirely.

finish the persistence dance.

code and slashed nesting depth, but no semantic changes yet.

In the TRACE_REFS version of the code, call _Py_NewReference() instead
of INCREF to bump the refcount from zero to one.

When exiting the function, don't DECREF the object back to zero
refcount, as that will reinvoke the object's deallocation function.
XXX Why did this ever work?

and Zope3 branch versions of this function.  No semantic change.