[ZODB-Dev] weird BTrees KeyError (CVS HEAD)

[Casey Duncan]

On Friday 27 June 2003 03:46 pm, Christian Reis wrote:
> On Fri, Jun 27, 2003 at 03:03:40PM -0400, Tim Peters wrote:
> > [Christian Reis]
> > > Would a normal list be safe, even while mutating?
> > 
> > It's never safe to mutate an object used as a BTree key, regardless of its
> > type.  Please see:
> > 
> >     http://www.zope.org/Wikis/ZODB/guide/node6.html
> > 
> > and esp. section 5.3.1 (Total Ordering and Persistence).
> 
> Hmmm. That is a problem for us, then. In IC, we do arbitrary queries for
> objects based on attributes they have; when they have list attributes we
> auto-swap them for PersistentLists, but we use these lists as the keys
> in the index BTrees. I'm trying to think how we could implement indexing
> for lists, now; we will probably need a custom class and an extra index,
> it seems.

Would it be possible to convert the lists to tuples? Assuming all members are 
always totally ordered, then you would be sure they were never mutated in 
place. If the key changes, you would have to lookup the value with the old 
tuple, delete the old key and set the value using a new tuple.

An alternative might be to subclass PersistentList and implement an immutable 
flag which would prevent mutation when the flag was set. You would set this 
flag when the list was used as a key.
 
> > There wasn't enough info in your original msg to guess what might have 
gone
> > wrong with high probability.  Something you can do is load your BTree,
> > import the check module from the BTrees package, and execute
> > 
> >     check.check(index)
> > 
> > If mutations have destroyed that the BTree's keys are in sorted order, 
that
> > line will raise AssertionError with some more info.
> 
> That tool is *very* cool. Here's the output:
> 
> AssertionError: Errors found in OOBTree (0x82cd518):
> key [<OutPayment -184497724 at 0x137161952: Pergunte AO JÃO (9)>] at
> index 0 >= key [<OutPayment -996636965 at 0x137162416:  (7)>,
> <OutPayment 685848900 at 0x137162984:  (8)>] at index 1, in OOBucket
> (0x82d4890), path from root 0
> key [<OutPayment 479303017 at 0x137144000: 23123231 (3)>] at index 4 >=
> key [<OutPayment -984951907 at 0x137156320: 21331421 (2)>] at index 5,
> in OOBucket (0x82d4890), path from root 0
> 
> So it seems that yes, we have destroyed the order the keys were sorted
> in. I'm not entirely sure *how* the order changed (since these objects
> *do* define __cmp__, which is based on an _ic_objectid attribute they
> have). But that's up to me to find out.

If these lists were mutated after they were used as keys then that would 
possibly explain it.

> > > The only thing really special here is that these objects have
> > > custom hash functions, but I don't think hash is used in this case.
> > 
> > Right, BTrees never use hash functions.  How these objects define __cmp__ 
is
> > vital, though, and if they don't have a custom __cmp__ function, sporadic
> > and seemingly random errors are *expected* (see the page referenced above
> > for why).
> 
> Well, PersistentList *does* define its own cmp based on its data
> attribute, which can only mean that the data inside it changed order.
> I just wonder how.

Does any part of the application hold a reference to this list after it is 
used as a key in the BTree?


-Casey