# HG changeset patch
# User Artem Tikhomirov <tikhomirov.artem@gmail.com>
# Date 1339010637 -7200
# Node ID 2e402c12ebc6c1ba6ba1ad7c2cf3a52a678b222b
# Parent  056f724bdc21bdd2d04f77d73cae12ee35b5c13e
Issue 31: Revlog#walk() fails with AIOOBE when start > 0

diff -r 056f724bdc21 -r 2e402c12ebc6 src/org/tmatesoft/hg/internal/IntMap.java
--- a/src/org/tmatesoft/hg/internal/IntMap.java	Wed Jun 06 20:11:17 2012 +0200
+++ b/src/org/tmatesoft/hg/internal/IntMap.java	Wed Jun 06 21:23:57 2012 +0200
@@ -21,6 +21,7 @@
 
 /**
  * Map implementation that uses plain int keys and performs with log n effectiveness.
+ * May contain null values
  * 
  * @author Artem Tikhomirov
  * @author TMate Software Ltd.
diff -r 056f724bdc21 -r 2e402c12ebc6 src/org/tmatesoft/hg/internal/PhasesHelper.java
--- a/src/org/tmatesoft/hg/internal/PhasesHelper.java	Wed Jun 06 20:11:17 2012 +0200
+++ b/src/org/tmatesoft/hg/internal/PhasesHelper.java	Wed Jun 06 21:23:57 2012 +0200
@@ -114,7 +114,7 @@
 				 */
 				final HashSet<Nodeid> parents2consider = new HashSet<Nodeid>(roots);
 				final boolean[] result = new boolean[] { false };
-				hgRepo.getChangelog().walk(0/*earlierstRootRevIndex*/, csetRevIndex, new HgChangelog.ParentInspector() {
+				hgRepo.getChangelog().walk(earliestRootRevIndex, csetRevIndex, new HgChangelog.ParentInspector() {
 					
 					public void next(int revisionIndex, Nodeid revision, int parent1, int parent2, Nodeid nidParent1, Nodeid nidParent2) {
 						boolean descendant = false;
diff -r 056f724bdc21 -r 2e402c12ebc6 src/org/tmatesoft/hg/repo/Revlog.java
--- a/src/org/tmatesoft/hg/repo/Revlog.java	Wed Jun 06 20:11:17 2012 +0200
+++ b/src/org/tmatesoft/hg/repo/Revlog.java	Wed Jun 06 21:23:57 2012 +0200
@@ -36,6 +36,7 @@
 import org.tmatesoft.hg.internal.ArrayHelper;
 import org.tmatesoft.hg.internal.DataAccess;
 import org.tmatesoft.hg.internal.Experimental;
+import org.tmatesoft.hg.internal.IntMap;
 import org.tmatesoft.hg.internal.Preview;
 import org.tmatesoft.hg.internal.RevlogStream;
 import org.tmatesoft.hg.util.Adaptable;
@@ -259,36 +260,80 @@
 	@Experimental
 	public final void walk(int start, int end, final Revlog.Inspector inspector) throws HgInvalidRevisionException, HgInvalidControlFileException {
 		int lastRev = getLastRevision();
-		if (start == TIP) {
-			start = lastRev;
-		}
+		final int _start = start == TIP ? lastRev : start;
 		if (end == TIP) {
 			end = lastRev;
 		}
 		final RevisionInspector revisionInsp = Adaptable.Factory.getAdapter(inspector, RevisionInspector.class, null);
 		final ParentInspector parentInsp = Adaptable.Factory.getAdapter(inspector, ParentInspector.class, null);
-		final Nodeid[] allRevisions = parentInsp == null ? null : new Nodeid[end - start + 1]; 
-		if (parentInsp != null && start != 0) {
-			// e.g. start == 6, end == 7 and parentOf(start) == 5. allRevisions.length == 2, allRevisions[parentOf(start)] => AIOOBE 
-			throw new IllegalStateException("There's a defect in the code that doesn't allow walks other than from the very beginning");
-			// TestAuxUtilities#testRevlogInspectors
-		}
+		final Nodeid[] allRevisions = parentInsp == null ? null : new Nodeid[end - _start + 1];
+		// next are to build set of parent indexes that are not part of the range iteration
+		// i.e. those parents we need to read separately. See Issue 31 for details.
+		final int[]      firstParentIndexes = parentInsp == null || _start == 0 ? null : new int[allRevisions.length];
+		final int[]     secondParentIndexes = parentInsp == null || _start == 0 ? null : new int[allRevisions.length];
+		final IntMap<Nodeid> missingParents = parentInsp == null || _start == 0 ? null : new IntMap<Nodeid>(16); 
 
-		content.iterate(start, end, false, new RevlogStream.Inspector() {
+		content.iterate(_start, end, false, new RevlogStream.Inspector() {
+			private int i = 0;
 			
-			public void next(int revisionNumber, int actualLen, int baseRevision, int linkRevision, int parent1Revision, int parent2Revision, byte[] nodeid, DataAccess data) {
+			public void next(int revisionIndex, int actualLen, int baseRevIndex, int linkRevIndex, int parent1RevIndex, int parent2RevIndex, byte[] nodeid, DataAccess data) {
 				Nodeid nid = Nodeid.fromBinary(nodeid, 0);
 				if (revisionInsp != null) {
-					revisionInsp.next(revisionNumber, nid, linkRevision);
+					revisionInsp.next(revisionIndex, nid, linkRevIndex);
 				}
 				if (parentInsp != null) {
-					Nodeid p1 = parent1Revision == -1 ? Nodeid.NULL : allRevisions[parent1Revision];
-					Nodeid p2 = parent2Revision == -1 ? Nodeid.NULL : allRevisions[parent2Revision];
-					allRevisions[revisionNumber] = nid;
-					parentInsp.next(revisionNumber, nid, parent1Revision, parent2Revision, p1, p2);
+					allRevisions[i] = nid;
+					if (_start > 0) {
+						firstParentIndexes[i] = parent1RevIndex;
+						secondParentIndexes[i] = parent2RevIndex;
+						if (parent1RevIndex < _start && parent1RevIndex >= 0) {
+							missingParents.put(parent1RevIndex, null);
+						}
+						if (parent2RevIndex < _start && parent2RevIndex >= 0) {
+							missingParents.put(parent2RevIndex, null);
+						}
+					} else {
+						Nodeid p1 = parent1RevIndex == -1 ? Nodeid.NULL : allRevisions[parent1RevIndex];
+						Nodeid p2 = parent2RevIndex == -1 ? Nodeid.NULL : allRevisions[parent2RevIndex];
+						parentInsp.next(revisionIndex, allRevisions[i], parent1RevIndex, parent2RevIndex, p1, p2);
+					}
+					i++;
 				}
 			}
 		});
+		if (parentInsp != null && _start > 0) {
+			assert missingParents.size() > 0; // in fact, more relaxed than assert. rather 'assume'
+			// TODO int[] IntMap#keys() or even sort of iterator that can modify values
+			for (int k = missingParents.firstKey(), l = missingParents.lastKey(); k <= l; k++) {
+				if (missingParents.containsKey(k)) {
+					Nodeid nid = getRepo().getChangelog().getRevision(k);
+					missingParents.put(k, nid);
+				}
+			}
+
+			for (int i = 0, revNum = _start; i < allRevisions.length; i++, revNum++) {
+				int riP1 = firstParentIndexes[i];
+				int riP2 = secondParentIndexes[i];
+				Nodeid p1, p2;
+				p1 = p2 = Nodeid.NULL;
+				if (riP1 >= _start) {
+					// p1 of revNum's revision is out of iterated range
+					// (don't check for riP1<end as I assume parents come prior to children in the changelog)
+					p1 = allRevisions[riP1 - start];
+				} else if (riP1 != -1) {
+					assert riP1 >=0 && riP1 < _start;
+					p1 = missingParents.get(riP1);
+				}
+				// same for Pp2
+				if (riP2 >= _start) {
+					p2 = allRevisions[riP2 - start];
+				} else if (riP2 != -1) {
+					assert riP2 >= 0 && riP2 < _start;
+					p2 = missingParents.get(riP2);
+				}
+				parentInsp.next(revNum, allRevisions[i], riP1, riP2, p1, p2);
+			}
+		}
 	}
 
 	/**
diff -r 056f724bdc21 -r 2e402c12ebc6 test/org/tmatesoft/hg/test/TestAuxUtilities.java
--- a/test/org/tmatesoft/hg/test/TestAuxUtilities.java	Wed Jun 06 20:11:17 2012 +0200
+++ b/test/org/tmatesoft/hg/test/TestAuxUtilities.java	Wed Jun 06 21:23:57 2012 +0200
@@ -245,28 +245,35 @@
 			}
 		});
 		class ParentInspectorCheck implements HgDataFile.ParentInspector {
-			private int i;
+			private int i, c;
 			private Nodeid[] all;
+			private final int start;
 			
 			public ParentInspectorCheck(int start, int total) {
-				i = start;
+				this.start = start;
+				i = start; // revision index being iterated
+				c = 0; // index/counter of visited revisions
 				all = new Nodeid[total];
 			}
 
 			public void next(int localRevision, Nodeid revision, int parent1, int parent2, Nodeid nidParent1, Nodeid nidParent2) {
 				Assert.assertEquals(i++, localRevision);
-				all[localRevision] = revision;
+				all[c++] = revision;
 				Assert.assertNotNull(revision);
 				Assert.assertFalse(localRevision == 0 && (parent1 != -1 || parent2 != -1));
 				Assert.assertFalse(localRevision > 0 && parent1 == -1 && parent2 == -1);
 				if (parent1 != -1) {
 					Assert.assertNotNull(nidParent1);
-					// deliberately ==, not asserEquals to ensure same instance
-					Assert.assertTrue(nidParent1 == all[parent1]);  
+					if (parent1 >= start) {
+						// deliberately ==, not asserEquals to ensure same instance
+						Assert.assertTrue(nidParent1 == all[parent1-start]);  
+					}
 				}
 				if (parent2 != -1) {
 					Assert.assertNotNull(nidParent2);
-					Assert.assertTrue(nidParent2 == all[parent2]);  
+					if (parent2 >= start) {
+						Assert.assertTrue(nidParent2 == all[parent2-start]);
+					}
 				}
 			}
 		};