[Zope-Checkins] CVS: Zope/lib/python/BTrees - BTreeItemsTemplate.c:1.11

Tim Peters tim.one@comcast.net
Sun, 9 Jun 2002 15:27:49 -0400


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

Modified Files:
	BTreeItemsTemplate.c 
Log Message:
Fix for http://collector.zope.org/Zope/419,
"BTreeItems slice contains 1 too many elements"
This also fixes many related glitches, such as that giving an
out-of-bound slice index raised IndexError instead of clipping.

BTreeItems_slice():  Emulate Python slicing semantics in all cases.

testBTrees.py:  new testSlicing() tests in MappingBase and NormalSetTests
to ensure that slicing of .keys()/.items()/.values() works exactly the
same way as slicing of Python lists, in all one-sided, two-sided and
whole-structure ([:]) cases, with both negative and positive slice indices,
and mixtures of + and -, and whether in bounds or out of bounds.


=== Zope/lib/python/BTrees/BTreeItemsTemplate.c 1.10 => 1.11 ===
 typedef struct {
   PyObject_HEAD
-  Bucket *firstbucket;			/* First bucket known		*/
-  Bucket *currentbucket;		/* Current bucket position	*/
-  Bucket *lastbucket;			/* Last bucket position		*/
-  int currentoffset;			/* Start count of current bucket*/
-  int pseudoindex;			/* Its an indicator		*/
+  Bucket *firstbucket;		/* First bucket known		*/
+  Bucket *currentbucket;	/* Current bucket position	*/
+  Bucket *lastbucket;		/* Last bucket position		*/
+  int currentoffset;		/* Start count of current bucket*/
+  int pseudoindex;		/* It's an indicator		*/
   int first, last;
   char kind;
 } BTreeItems;
@@ -348,18 +348,70 @@
   Bucket *highbucket;
   int lowoffset;
   int highoffset;
+  int length = -1;  /* len(self), but computed only if needed */
 
+  /* Complications:
+   * A Python slice never raises IndexError, but BTreeItems_seek does.
+   * Python did only part of index normalization before calling this:
+   *     ilow may be < 0 now, and ihigh may be arbitrarily large.  It's
+   *     our responsibility to clip them.
+   * A Python slice is exclusive of the high index, but a BTreeItems
+   *     struct is inclusive on both ends.
+   */
+
+  /* First adjust ilow and ihigh to be legit endpoints in the Python
+   * sense (ilow inclusive, ihigh exclusive).  This block duplicates the
+   * logic from Python's list_slice function (slicing for builtin lists).
+   */
+  if (ilow < 0)
+      ilow = 0;
+  else {
+      if (length < 0)
+          length = BTreeItems_length(self);
+      if (ilow > length)
+          ilow = length;
+  }
 
-  if (BTreeItems_seek(self, ilow) < 0) return NULL;
-
-  lowbucket = self->currentbucket;
-  lowoffset = self->currentoffset;
+  if (ihigh < ilow)
+      ihigh = ilow;
+  else {
+      if (length < 0)
+          length = BTreeItems_length(self);
+      if (ihigh > length)
+          ihigh = length;
+  }
+  assert(0 <= ilow && ilow <= ihigh);
+  assert(length < 0 || ihigh <= length);
 
-  if (BTreeItems_seek(self, ihigh) < 0) return NULL;
+  /* Now adjust for that our struct is inclusive on both ends.  This is
+   * easy *except* when the slice is empty:  there's no good way to spell
+   * that in an inclusive-on-both-ends scheme.  For example, if the
+   * slice is btree.items([:0]), ilow == ihigh == 0 at this point, and if
+   * we were to subtract 1 from ihigh that would get interpreted by
+   * BTreeItems_seek as meaning the *entire* set of items.  Setting ilow==1
+   * and ihigh==0 doesn't work either, as BTreeItems_seek raises IndexError
+   * if we attempt to seek to ilow==1 when the underlying sequence is empty.
+   * It seems simplest to deal with empty slices as a special case here.
+   */
+   if (ilow == ihigh) {
+       /* empty slice */
+       lowbucket = highbucket = self->currentbucket;
+       lowoffset = 1;
+       highoffset = 0;
+   }
+   else {
+       assert(ilow < ihigh);
+       --ihigh;  /* exclusive -> inclusive */
+
+       if (BTreeItems_seek(self, ilow) < 0) return NULL;
+       lowbucket = self->currentbucket;
+       lowoffset = self->currentoffset;
 
-  highbucket = self->currentbucket;
-  highoffset = self->currentoffset;
+       if (BTreeItems_seek(self, ihigh) < 0) return NULL;
 
+       highbucket = self->currentbucket;
+       highoffset = self->currentoffset;
+  }
   return newBTreeItems(self->kind,
                        lowbucket, lowoffset, highbucket, highoffset);
 }