gt:         Transaction txn = mDb.newTransaction();
context: /*
   *  Copyright (C) 2011-2017 Cojen.org
   *
   *  This program is free software: you can redistribute it and/or modify
   *  it under the terms of the GNU Affero General Public License as
   *  published by the Free Software Foundation, either version 3 of the
   *  License, or (at your option) any later version.
   *
   *  This program is distributed in the hope that it will be useful,
   *  but WITHOUT ANY WARRANTY; without even the implied warranty of
   *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   *  GNU Affero General Public License for more details.
   *
   *  You should have received a copy of the GNU Affero General Public License
   *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
   */
  
  package org.cojen.tupl.core;
  
  import java.lang.reflect.Method;
  
  import java.util.Random;
  
  import java.util.concurrent.TimeUnit;
  import java.util.concurrent.atomic.AtomicReference;
  
  import org.junit.*;
  import static org.junit.Assert.*;
  
  import org.cojen.tupl.*;
  
  import org.cojen.tupl.util.Latch;
  
  import static org.cojen.tupl.TestUtils.*;
  
  /**
   * 
   *
   * @author Brian S O'Neill
   */
  public class CursorTest {
      public static void main(String[] args) throws Exception {
          org.junit.runner.JUnitCore.main(CursorTest.class.getName());
      }
  
      @Before
      public void createTempDb() throws Exception {
          mDb = newTempDatabase(getClass());
      }
  
      @After
      public void teardown() throws Exception {
          deleteTempDatabases(getClass());
          mDb = null;
      }
  
      protected View openIndex(String name) throws Exception {
          return mDb.openIndex(name);
      }
  
      protected boolean verify(View ix) throws Exception {
          return ((Index) ix).verify(null);
      }
  
      // Override and return internal cursor if wrapped.
      protected Cursor treeCursor(Cursor c) {
          return c;
      }
  
      protected boolean equalPositions(Cursor a, Cursor b) throws Exception {
          a = treeCursor(a);
          b = treeCursor(b);
          Method m = a.getClass().getDeclaredMethod("equalPositions", b.getClass());
          return (Boolean) m.invoke(a, b);
      }
  
      protected Database mDb;
  
      @Test
      public void empty() throws Exception {
          View ix = openIndex("test");
          Cursor c = ix.newCursor(Transaction.BOGUS);
          c.first();
          assertNull(c.key());
          assertNull(c.value());
          c.last();
          assertNull(c.key());
          assertNull(c.value());
  
          for (int i=0; i<8; i++) {
              ix.store(Transaction.BOGUS, key(1), value(1));
  
              if ((i & 4) == 0) {
                  c.first();
              } else {
                  c.last();
              }
              fastAssertArrayEquals(key(1), c.key());
              fastAssertArrayEquals(value(1), c.value());
  
              ix.delete(Transaction.BOGUS, key(1));
  
              switch (i & 3) {
                  default -> c.first();
                  case 1 -> c.last();
                  case 2 -> c.next();
                  case 3 -> c.previous();
              }
  
              assertNull(c.key());
              assertNull(c.value());
          }
      }
  
      @Test
      public void compareKey() throws Exception {
          View ix = openIndex("test");
          Cursor c = ix.newCursor(Transaction.BOGUS);
  
          c.find("bkey".getBytes());
          assertEquals(0, c.compareKeyTo("bkey".getBytes()));
          assertEquals(0, c.compareKeyTo("---bkey---".getBytes(), 3, 4));
          assertEquals(1, c.compareKeyTo("akey".getBytes()));
          assertEquals(1, c.compareKeyTo("--akey--".getBytes(), 2, 4));
          assertEquals(-1, c.compareKeyTo("ckey".getBytes()));
          assertEquals(-1, c.compareKeyTo("-ckey-".getBytes(), 1, 4));
      }
  
      @Test
      public void stubCursor() throws Exception {
          stubCursor(false);
      }
  
      @Test
      public void stubEviction() throws Exception {
          stubCursor(true);
      }
  
      private void stubCursor(boolean eviction) throws Exception {
          View ix = openIndex("test");
  
          for (int i=0; i<1000; i++) {
              ix.store(Transaction.BOGUS, key(i), value(i));
          }
  
          Cursor c = ix.newCursor(Transaction.BOGUS);
          c.find(key(500));
          assertNotNull(c.key());
  
          for (int i=0; i<1000; i++) {
              if (i != 500) {
                  ix.delete(Transaction.BOGUS, key(i));
              }
          }
  
          // Cursor is still valid, and it references a stub parent.
          c.load();
          assertArrayEquals(key(500), c.key());
          assertArrayEquals(value(500), c.value());
  
          Cursor c2 = ix.newCursor(Transaction.BOGUS);
          c2.first();
          assertArrayEquals(key(500), c2.key());
          c2.next();
          assertNull(c2.key());
          c2.last();
          assertArrayEquals(key(500), c2.key());
  
          if (eviction) {
              // Force eviction of stub. Cannot verify directly, however.
              View ix2 = openIndex("test2");
              c.reset();
              c2.reset();
  
              for (int i=0; i<1000000; i++) {
                  ix2.store(Transaction.BOGUS, key(i), value(i));
              }
  
              c.find(key(500));
              assertArrayEquals(key(500), c.key());
  
              c2.last();
              assertArrayEquals(key(500), c2.key());
          }
  
          // Add back missing values, cursors should see them.
          for (int i=0; i<1000; i++) {
              if (i != 500) {
                  ix.store(Transaction.BOGUS, key(i), value(i));
              }
          }
  
          for (int i=501; i<1000; i++) {
              c.next();
              assertArrayEquals(key(i), c.key());
              assertArrayEquals(value(i), c.value());
          }
          c.next();
          assertNull(c.key());
  
          // Necessary for CursorDisjointUnionTest. Unions and other merge cursors read ahead,
          // and so they can't always observe values being added back in. Calling lock, load,
          // store, or a find method re-aligns the source cursors.
          c2.lock();
  
          for (int i=499; i>=0; i--) {
              c2.previous();
              assertArrayEquals(key(i), c2.key());
              assertArrayEquals(value(i), c2.value());
          }
          c2.previous();
          assertNull(c2.key());
      }
  
      @Test
      public void findLock() throws Exception {
          View ix = openIndex("test");
          ix.store(Transaction.BOGUS, key(0), value(0));
  
          // Lock key 0.
          Transaction txn = mDb.newTransaction();
          ix.store(txn, key(0), value(0));
  
          Cursor c = ix.newCursor(null);
          try {
              c.find(key(0));
              fail();
          } catch (LockTimeoutException e) {
          }
  
          txn.exit();
  
          // If timed out, cursor is at the desired key, but no value is available.
          fastAssertArrayEquals(key(0), c.key());
          assertSame(c.value(), Cursor.NOT_LOADED);
  
          c.load();
          fastAssertArrayEquals(value(0), c.value());
  
          c.reset();
      }
  
      @Test
      public void loadLock() throws Exception {
          View ix = openIndex("test");
          ix.store(Transaction.BOGUS, key(0), value(0));
  
          Cursor c = ix.newCursor(null);
          c.find(key(0));
  
          // Lock key 0.
          Transaction txn = mDb.newTransaction();
          ix.store(txn, key(0), value(0));
  
          try {
              c.load();
              fail();
          } catch (LockTimeoutException e) {
          }
  
          txn.exit();
  
          // If timed out, cursor is at the desired key, but no value is available.
          fastAssertArrayEquals(key(0), c.key());
          assertSame(c.value(), Cursor.NOT_LOADED);
  
          c.load();
          fastAssertArrayEquals(value(0), c.value());
  
          c.reset();
      }
  
      @Test
      public void findGeLock() throws Exception {
          findGeLock(false);
      }
  
      @Test
      public void findNearbyGeLock() throws Exception {
          findGeLock(true);
      }
  
      private void findGeLock(boolean nearby) throws Exception {
          View ix = openIndex("test");
          byte[] key = key(0);
          ix.store(Transaction.BOGUS, key, value(0));
  
          // Lock key 0.
          Transaction txn = mDb.newTransaction();
          ix.store(txn, key, value(0));
  
          Cursor c = ix.newCursor(null);
          try {
              if (nearby) {
                  c.findNearbyGe(key);
              } else {
                  c.findGe(key);
              }
              fail();
          } catch (LockTimeoutException e) {
          }
  
          txn.exit();
  
          // If timed out, cursor is at the desired key, but no value is available.
          fastAssertArrayEquals(key, c.key());
          assertSame(c.value(), Cursor.NOT_LOADED);
  
          c.load();
          fastAssertArrayEquals(value(0), c.value());
  
          txn.reset();
  
          // No timeout.
          if (nearby) {
              assertEquals(LockResult.UNOWNED, c.findNearbyGe(key));
          } else {
              assertEquals(LockResult.UNOWNED, c.findGe(key));
          }
  
          // Not found.
          c.link(txn);
          if (nearby) {
              assertEquals(LockResult.UNOWNED, c.findNearbyGe(key(1)));
          } else {
              assertEquals(LockResult.UNOWNED, c.findGe(key(1)));
          }
          txn.reset();
  
          c.reset();
      }
  
      @Test
      public void findGtLock() throws Exception {
          View ix = openIndex("test");
          ix.store(Transaction.BOGUS, key(0), value(0));
          ix.store(Transaction.BOGUS, key(1), value(1));
  
          // Lock key 0.
          Transaction txn = mDb.newTransaction();
          ix.store(txn, key(0), value(0));
  
          Cursor c = ix.newCursor(null);
          c.findGt(key(0));
  
          // Lock on key 0 didn't block the find.
          fastAssertArrayEquals(key(1), c.key());
          fastAssertArrayEquals(value(1), c.value());
      }
  
      @Test
      public void findLeLock() throws Exception {
          findLeLock(false);
      }
  
      @Test
      public void findNearbyLeLock() throws Exception {
          findLeLock(true);
      }
  
      private void findLeLock(boolean nearby) throws Exception {
          View ix = openIndex("test");
          byte[] key = key(1);
          ix.store(Transaction.BOGUS, key, value(1));
  
          // Lock key 1.
          Transaction txn = mDb.newTransaction();
          ix.store(txn, key, value(1));
  
          Cursor c = ix.newCursor(null);
          try {
              if (nearby) {
                  c.findNearbyLe(key);
              } else {
                  c.findLe(key);
              }
              fail();
          } catch (LockTimeoutException e) {
          }
  
          txn.exit();
  
          // If timed out, cursor is at the desired key, but no value is available.
          fastAssertArrayEquals(key, c.key());
          assertSame(c.value(), Cursor.NOT_LOADED);
  
          c.load();
          fastAssertArrayEquals(value(1), c.value());
  
          txn.reset();
  
          // No timeout.
          if (nearby) {
              assertEquals(LockResult.UNOWNED, c.findNearbyLe(key));
          } else {
              assertEquals(LockResult.UNOWNED, c.findLe(key));
          }
  
          // Not found.
          c.link(txn);
          if (nearby) {
              assertEquals(LockResult.UNOWNED, c.findNearbyLe(key(0)));
          } else {
              assertEquals(LockResult.UNOWNED, c.findLe(key(0)));
          }
          txn.reset();
  
          c.reset();
      }
  
      @Test
      public void findLtLock() throws Exception {
          View ix = openIndex("test");
          ix.store(Transaction.BOGUS, key(0), value(0));
          ix.store(Transaction.BOGUS, key(1), value(1));
  
          // Lock key 1.
          Transaction txn = mDb.newTransaction();
          ix.store(txn, key(1), value(1));
  
          Cursor c = ix.newCursor(null);
          c.findLt(key(1));
  
          // Lock on key 0 didn't block the find.
          fastAssertArrayEquals(key(0), c.key());
          fastAssertArrayEquals(value(0), c.value());
      }
  
      @Test
      public void nextLock() throws Exception {
          nextLock(false);
      }
  
      @Test
      public void lastLock() throws Exception {
          nextLock(true);
      }
  
      private void nextLock(boolean last) throws Exception {
          View ix = openIndex("test");
          ix.store(Transaction.BOGUS, key(0), value(0));
          ix.store(Transaction.BOGUS, key(1), value(1));
  
          // Lock key 1.
          Transaction txn = mDb.newTransaction();
          ix.store(txn, key(1), value(1));
  
          Cursor c = ix.newCursor(null);
          c.first();
          try {
              if (last) {
                  c.last();
              } else {
                  c.next();
              }
              fail();
          } catch (LockTimeoutException e) {
          }
  
          txn.exit();
  
          // If timed out, cursor is at the desired key, but no value is available.
          fastAssertArrayEquals(key(1), c.key());
          assertSame(c.value(), Cursor.NOT_LOADED);
  
          c.load();
          fastAssertArrayEquals(value(1), c.value());
  
          c.reset();
      }
  
      @Test
      public void previousLock() throws Exception {
          previousLock(false);
      }
  
      @Test
      public void firstLock() throws Exception {
          previousLock(true);
      }
  
      private void previousLock(boolean first) throws Exception {
          View ix = openIndex("test");
          ix.store(Transaction.BOGUS, key(0), value(0));
          ix.store(Transaction.BOGUS, key(1), value(1));
  
          // Lock key 0.
          Transaction txn = mDb.newTransaction();
          ix.store(txn, key(0), value(0));
  
          Cursor c = ix.newCursor(null);
          c.last();
          try {
              if (first) {
                  c.first();
              } else {
                  c.previous();
              }
              fail();
          } catch (LockTimeoutException e) {
          }
  
          txn.exit();
  
          // If timed out, cursor is at the desired key, but no value is available.
          fastAssertArrayEquals(key(0), c.key());
          assertSame(c.value(), Cursor.NOT_LOADED);
  
          c.load();
          fastAssertArrayEquals(value(0), c.value());
  
          c.reset();
      }
  
      @Test
      public void previousGeSkip() throws Exception {
          View ix = openIndex("test");
          ix.store(Transaction.BOGUS, key(0), value(0));
          ix.store(Transaction.BOGUS, key(1), value(1));
          ix.store(Transaction.BOGUS, key(2), value(2));
  
          Cursor c;
          {
              Transaction txn = mDb.newTransaction();
              txn.lockTimeout(60, TimeUnit.SECONDS);
              c = ix.newCursor(txn);
              c.last();
          }
  
          // Lock key 1.
          Transaction txn = mDb.newTransaction();
          ix.lockExclusive(txn, key(1));
  
          var ex = new AtomicReference<Exception>();
  
          var t = new Thread(() -> {
              try {
                  // Must fully skip past key 1.
                  c.previousGe(key(0));
              } catch (Exception e) {
                  ex.set(e);
              }
          });
  
          startAndWaitUntilBlocked(t);
  
          ix.delete(txn, key(1));
          txn.commit();
  
          t.join();
          assertNull(ex.get());
  
          fastAssertArrayEquals(value(0), c.value());
      }
  
      @Test
      public void nextLe() throws Exception {
          nextLe(3);
          nextLe(4);
      }
  
      private void nextLe(int count) throws Exception {
          View ix = openIndex("test");
          for (int i=0; i<count; i++) {
              ix.store(Transaction.BOGUS, key(i), value(i));
          }
          Cursor c = ix.newCursor(Transaction.BOGUS);
          c.first();
          fastAssertArrayEquals(key(0), c.key());
  
          byte[] end = key(2);
          
          c.nextLe(end);
          fastAssertArrayEquals(key(1), c.key());
          fastAssertArrayEquals(value(1), c.value());
  
          c.nextLe(end);
          fastAssertArrayEquals(key(2), c.key());
          fastAssertArrayEquals(value(2), c.value());
  
          c.nextLe(end);
          assertNull(c.key());
          assertNull(c.value());
      }
  
      @Test
      public void nextLeLock() throws Exception {
          View ix = openIndex("test");
          ix.store(Transaction.BOGUS, key(0), value(0));
          ix.store(Transaction.BOGUS, key(1), value(1));
  
          // Lock key 1.
          Transaction txn = mDb.newTransaction();
          ix.store(txn, key(1), value(1));
  
          Cursor c = ix.newCursor(null);
          c.first();
          try {
              c.nextLe(key(1));
              fail();
          } catch (LockTimeoutException e) {
          }
  
          txn.exit();
  
          // If timed out, cursor is at the desired key, but no value is available.
          fastAssertArrayEquals(key(1), c.key());
          assertSame(c.value(), Cursor.NOT_LOADED);
  
          c.load();
          fastAssertArrayEquals(value(1), c.value());
  
          c.reset();
      }
  
      @Test
      public void nextLeSkip() throws Exception {
          View ix = openIndex("test");
          ix.store(Transaction.BOGUS, key(0), value(0));
          ix.store(Transaction.BOGUS, key(1), value(1));
          ix.store(Transaction.BOGUS, key(2), value(2));
  
          Cursor c;
          {
              Transaction txn = mDb.newTransaction();
              txn.lockTimeout(60, TimeUnit.SECONDS);
              c = ix.newCursor(txn);
              c.first();
          }
  
          // Lock key 1.
          Transaction txn = mDb.newTransaction();
          ix.lockExclusive(txn, key(1));
  
          var ex = new AtomicReference<Exception>();
  
          var t = new Thread(() -> {
              try {
                  // Must fully skip past key 1.
                  c.nextLe(key(2));
              } catch (Exception e) {
                  ex.set(e);
              }
          });
  
          startAndWaitUntilBlocked(t);
  
          ix.delete(txn, key(1));
          txn.commit();
  
          t.join();
          assertNull(ex.get());
  
          fastAssertArrayEquals(key(2), c.key());
          fastAssertArrayEquals(value(2), c.value());
      }
  
      @Test
      public void nextLt() throws Exception {
          nextLt(3);
          nextLt(4);
      }
  
      private void nextLt(int count) throws Exception {
          View ix = openIndex("test");
          for (int i=0; i<count; i++) {
              ix.store(Transaction.BOGUS, key(i), value(i));
          }
          Cursor c = ix.newCursor(Transaction.BOGUS);
          c.first();
          fastAssertArrayEquals(key(0), c.key());
  
          byte[] end = key(2);
          
          c.nextLt(end);
          fastAssertArrayEquals(key(1), c.key());
          fastAssertArrayEquals(value(1), c.value());
  
          c.nextLt(end);
          assertNull(c.key());
          assertNull(c.value());
      }
  
      @Test
      public void nextLtLock() throws Exception {
          View ix = openIndex("test");
          ix.store(Transaction.BOGUS, key(0), value(0));
          ix.store(Transaction.BOGUS, key(1), value(1));
          ix.store(Transaction.BOGUS, key(2), value(2));
  
          // Lock key 2.
  