[Zodb-checkins] CVS: Zope3/lib/python/Persistence/BTrees - BTreeItemsTemplate.c:1.1.2.6

[Tim Peters]

Update of /cvs-repository/Zope3/lib/python/Persistence/BTrees
In directory cvs.zope.org:/tmp/cvs-serv17621

Modified Files:
      Tag: Zope-3x-branch
	BTreeItemsTemplate.c 
Log Message:
Porting from the trunk:

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.


=== Zope3/lib/python/Persistence/BTrees/BTreeItemsTemplate.c 1.1.2.5 => 1.1.2.6 ===
   int lowoffset;
   int highoffset;
+  int length = -1;  /* len(self), but computed only if needed */
 
-
-  if (BTreeItems_seek(self, ilow) < 0) return NULL;
-
-  lowbucket = self->currentbucket;
-  lowoffset = self->currentoffset;
-
-  if (BTreeItems_seek(self, ihigh) < 0) return NULL;
-
-  highbucket = self->currentbucket;
-  highoffset = self->currentoffset;
-
+  /* 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 (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);
+
+  /* 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;
+
+       if (BTreeItems_seek(self, ihigh) < 0) return NULL;
+
+       highbucket = self->currentbucket;
+       highoffset = self->currentoffset;
+  }
   return newBTreeItems(self->kind,
                        lowbucket, lowoffset, highbucket, highoffset);
 }