Merge lp:~pbeaman/akiban-persistit/fix-1023549-traverse-wrong into lp:akiban-persistit

[Peter Beaman]

Fix bug 1023549: traverse(LTEQ, false, 0) incorrectly returns true.

The bug resulted from some failure to handle a couple of cases in the Exchange#traverse method. Proposed code sets the "matches" variable on each applicable code path. Also fixes an infinite loop in code path for travers(EQ, false, 0) where the key provided is for an MVV that has no visible versions.

Currently Akiban Server works around this problem: see

   com.akiban.server.store.PersistitStore#keyExistsInIndexcom.akiban.server.store

With this proposed branch I have successfully tested a version of Akiban Server in which the deep flag is set to false as originally intended.

Since the changes are subtle and Akiban Server currently works around this problem I recommend holding this proposal out of 3.2.0.

[Nathan Williams (nwilliams)]

Looks good.

Holding off big-A until version bump gets through.

review: Approve

[Peter Beaman (pbeaman)]

Pushing this through since 3.2.1 update is now merged.

=== modified file 'src/main/java/com/persistit/Exchange.java'
--- src/main/java/com/persistit/Exchange.java	2012-10-08 19:48:22 +0000
+++ src/main/java/com/persistit/Exchange.java	2012-10-15 19:30:28 +0000
@@ -2053,7 +2053,7 @@
             for (;;) {
                 ++_keysVisitedDuringTraverse;
                 final LevelCache lc = _levelCache[0];
-                boolean matches = false;
+                boolean matches;
                 //
                 // Optimal path - pick up the buffer and location left
                 // by previous operation.
@@ -2103,9 +2103,9 @@
                 if (edge && (foundAt & EXACT_MASK) != 0) {
                     matches = true;
                 } else if (edge && !deep && Buffer.decodeDepth(foundAt) == index) {
-                    // None
+                    matches = true;
                 } else if (direction == EQ) {
-                    // None
+                    matches = false;
                 } else {
                     edge = false;
                     foundAt = buffer.traverse(_key, direction, foundAt);
@@ -2123,7 +2123,12 @@
                             buffer = rightSibling;
                             checkPageType(buffer, PAGE_TYPE_DATA, false);
                             foundAt = buffer.traverse(_key, direction, buffer.toKeyBlock(0));
+                            matches = !buffer.isAfterRightEdge(foundAt);
+                        } else {
+                            matches = false;
                         }
+                    } else {
+                        matches = true;
                     }
 
                     //
@@ -2164,7 +2169,7 @@
                 // finishing
 
                 if (reverse && _key.isLeftEdge() || !reverse && _key.isRightEdge() || stopDueToKeyDepth) {
-                    // None
+                    matches = false;
                 } else {
                     if (deep) {
                         matches |= direction != EQ;
@@ -2186,7 +2191,7 @@
                             parentIndex = 0;
                         }
 
-                        matches = (spareKey.compareKeyFragment(_key, 0, parentIndex) == 0);
+                        matches &= (spareKey.compareKeyFragment(_key, 0, parentIndex) == 0);
 
                         if (matches) {
                             index = _key.nextElementIndex(parentIndex);
@@ -2201,10 +2206,14 @@
                                 //
                                 if (!isVisibleMatch) {
                                     nudged = false;
-                                    nudgeForMVCC = (direction == GTEQ || direction == LTEQ);
                                     buffer.release();
                                     buffer = null;
-                                    continue;
+                                    if (direction == EQ) {
+                                        matches = false;
+                                    } else {
+                                        nudgeForMVCC = (direction == GTEQ || direction == LTEQ);
+                                        continue;
+                                    }
                                 }
                                 //
                                 // It was a niece or nephew, record non-exact
 
=== modified file 'src/test/java/com/persistit/unit/ExchangeTest.java'
--- src/test/java/com/persistit/unit/ExchangeTest.java	2012-10-08 17:59:29 +0000
+++ src/test/java/com/persistit/unit/ExchangeTest.java	2012-10-15 19:30:28 +0000
@@ -424,6 +424,18 @@
         assertEquals("Should be false", false, ex.traverse(Key.LT, deep, -1));
         ex.clear();
 
+        ex.append(1);
+        assertEquals("Should be false", false, ex.traverse(Key.EQ, deep, -1));
+        ex.clear().append(1);
+        assertEquals("Should be false", false, ex.traverse(Key.GTEQ, deep, -1));
+        ex.clear().append(1);
+        assertEquals("Should be false", false, ex.traverse(Key.GT, deep, -1));
+        ex.clear().append(1);
+        assertEquals("Should be false", false, ex.traverse(Key.LTEQ, deep, -1));
+        ex.clear().append(1);
+        assertEquals("Should be false", false, ex.traverse(Key.LT, deep, -1));
+        ex.clear().append(1);
+
         ex.append(1).append(2).store();
         ex.clear().append(Key.BEFORE);
         assertEquals("Should be false", false, ex.traverse(Key.EQ, deep, -1));