[Zodb-checkins] SVN: ZODB/trunk/src/BTrees/ Fix bug indexing BTreeItems with negative values. Previous code assumed that idexes passed to BTreeItem_item would be negative, in practice this was not the case, and an index of -1 actually passed len(items)-1 as the index argument. Consequently, it was possible to access each item using two negative indexes (i.e., -1 and -len(items)-1). This made each item appear twice in a reverse iteration.

[Casey Duncan]

Log message for revision 25134:
Fix bug indexing BTreeItems with negative values. Previous code assumed that idexes passed to BTreeItem_item would be negative, in practice this was not the case, and an index of -1 actually passed len(items)-1 as the index argument. Consequently, it was possible to access each item using two negative indexes (i.e., -1 and -len(items)-1). This made each item appear twice in a reverse iteration.

Code in BTreeItems_seek attempted to match the sign of the pseudoindex kept in the BTreeItems obj and the incoming index. Since this incoming index was never legitimately negative as it assumed, actually negatives passed in due to "overshooting" the first item would repeat the items again from the end. Removal of this code corrects the problem.

Unittests which provoke the error in the original code have also been added.



-=-
Modified: ZODB/trunk/src/BTrees/BTreeItemsTemplate.c
===================================================================
--- ZODB/trunk/src/BTrees/BTreeItemsTemplate.c	2004-05-30 21:54:54 UTC (rev 25133)
+++ ZODB/trunk/src/BTrees/BTreeItemsTemplate.c	2004-05-31 02:33:35 UTC (rev 25134)
@@ -143,20 +143,6 @@
     currentbucket = self->currentbucket;
     if (currentbucket == NULL) goto no_match;
 
-    /* Make sure that the index and pseudoindex have the same sign. */
-    if (pseudoindex < 0 && i >= 0) {
-        /* Position to the start of the sequence. */
-        currentbucket = self->firstbucket;
-        currentoffset = self->first;
-        pseudoindex = 0;
-    }
-    else if (pseudoindex >= 0 && i < 0) {
-        /* Position to the end of the sequence. */
-        currentbucket = self->lastbucket;
-        currentoffset = self->last;
-        pseudoindex = -1;
-    }
-
     delta = i - pseudoindex;
     while (delta > 0) {         /* move right */
         int max;

Modified: ZODB/trunk/src/BTrees/tests/testBTrees.py
===================================================================
--- ZODB/trunk/src/BTrees/tests/testBTrees.py	2004-05-30 21:54:54 UTC (rev 25133)
+++ ZODB/trunk/src/BTrees/tests/testBTrees.py	2004-05-31 02:33:35 UTC (rev 25134)
@@ -187,6 +187,7 @@
         v = self.t.values()
         for i in range(100):
             self.assertEqual(v[i], i*i)
+        self.assertRaises(IndexError, lambda: v[i+1])
         i = 0
         for value in self.t.itervalues():
             self.assertEqual(value, i*i)
@@ -204,6 +205,16 @@
             lst = list(self.t.values(max=99-x, min=0+x))
             lst.sort()
             self.assertEqual(lst,range(0+x,99-x+1))
+    
+    def testValuesNegativeIndex(self):
+        L = [-3, 6, -11, 4]
+        for i in L:
+            self.t[i] = i
+        L.sort()
+        vals = self.t.values()
+        for i in range(-1, -4, -1):
+            self.assertEqual(vals[i], L[i])
+        self.assertRaises(IndexError, lambda: vals[-5])
 
     def testKeysWorks(self):
         for x in range(100):
@@ -213,6 +224,7 @@
         for x in v:
             self.assertEqual(x,i)
             i = i + 1
+        self.assertRaises(IndexError, lambda: v[i])
 
         for x in range(40):
             lst = self.t.keys(0+x,99-x)
@@ -222,6 +234,16 @@
             self.assertEqual(list(lst), range(0+x, 99-x+1))
 
         self.assertEqual(len(v), 100)
+    
+    def testKeysNegativeIndex(self):
+        L = [-3, 6, -11, 4]
+        for i in L:
+            self.t[i] = i
+        L.sort()
+        keys = self.t.keys()
+        for i in range(-1, -4, -1):
+            self.assertEqual(keys[i], L[i])
+        self.assertRaises(IndexError, lambda: keys[-5])
 
     def testItemsWorks(self):
         for x in range(100):
@@ -232,6 +254,7 @@
             self.assertEqual(x[0], i)
             self.assertEqual(x[1], 2*i)
             i += 1
+        self.assertRaises(IndexError, lambda: v[i+1])
 
         i = 0
         for x in self.t.iteritems():
@@ -243,8 +266,17 @@
 
         items = list(self.t.iteritems(min=12, max=20))
         self.assertEqual(items, zip(range(12, 21), range(24, 43, 2)))
+    
+    def testItemsNegativeIndex(self):
+        L = [-3, 6, -11, 4]
+        for i in L:
+            self.t[i] = i
+        L.sort()
+        items = self.t.items()
+        for i in range(-1, -4, -1):
+            self.assertEqual(items[i], (L[i], L[i]))
+        self.assertRaises(IndexError, lambda: items[-5])
 
-
     def testDeleteInvalidKeyRaisesKeyError(self):
         self.assertRaises(KeyError, self._deletefail)