# HG changeset patch
# User Artem Tikhomirov <tikhomirov.artem@gmail.com>
# Date 1361395430 -3600
# Node ID 45751456b47132285f746b8a624f7c78e1ee3334
# Parent  4ea0351ca878901ecd9a23dc84860a766c4c42e6
Annotate file changes through few revisions, walking either direction (old to new and vice versa)

diff -r 4ea0351ca878 -r 45751456b471 src/org/tmatesoft/hg/internal/AnnotateFacility.java
--- a/src/org/tmatesoft/hg/internal/AnnotateFacility.java	Wed Feb 20 18:19:52 2013 +0100
+++ b/src/org/tmatesoft/hg/internal/AnnotateFacility.java	Wed Feb 20 22:23:50 2013 +0100
@@ -19,11 +19,19 @@
 import static org.tmatesoft.hg.repo.HgRepository.NO_REVISION;
 import static org.tmatesoft.hg.repo.HgRepository.TIP;
 
+import java.util.BitSet;
+import java.util.HashSet;
+import java.util.LinkedHashMap;
+import java.util.LinkedList;
+import java.util.ListIterator;
+
+import org.tmatesoft.hg.core.HgIterateDirection;
 import org.tmatesoft.hg.core.Nodeid;
 import org.tmatesoft.hg.internal.DiffHelper.LineSequence;
 import org.tmatesoft.hg.repo.HgDataFile;
 import org.tmatesoft.hg.repo.HgInvalidStateException;
 import org.tmatesoft.hg.util.CancelledException;
+import org.tmatesoft.hg.util.Pair;
 
 /**
  * 
@@ -34,58 +42,102 @@
 public class AnnotateFacility {
 	
 	/**
-	 * mimic 'hg diff -r csetRevIndex1 -r csetRevIndex2'
+	 * mimic 'hg diff -r clogRevIndex1 -r clogRevIndex2'
 	 */
-	public void diff(HgDataFile df, int csetRevIndex1, int csetRevIndex2, BlockInspector insp) {
-		int fileRevIndex1 = fileRevIndex(df, csetRevIndex1);
-		int fileRevIndex2 = fileRevIndex(df, csetRevIndex2);
-		LineSequence c1 = lines(df, fileRevIndex1);
-		LineSequence c2 = lines(df, fileRevIndex2);
+	public void diff(HgDataFile df, int clogRevIndex1, int clogRevIndex2, BlockInspector insp) {
+		int fileRevIndex1 = fileRevIndex(df, clogRevIndex1);
+		int fileRevIndex2 = fileRevIndex(df, clogRevIndex2);
+		FileLinesCache fileInfoCache = new FileLinesCache(df, 5);
+		LineSequence c1 = fileInfoCache.lines(fileRevIndex1);
+		LineSequence c2 = fileInfoCache.lines(fileRevIndex2);
 		DiffHelper<LineSequence> pg = new DiffHelper<LineSequence>();
 		pg.init(c1, c2);
-		pg.findMatchingBlocks(new BlameBlockInspector(insp, csetRevIndex1, csetRevIndex2));
+		pg.findMatchingBlocks(new BlameBlockInspector(insp, clogRevIndex1, clogRevIndex2));
+	}
+	
+	public void annotate(HgDataFile df, int changelogRevisionIndex, BlockInspector insp, HgIterateDirection iterateOrder) {
+		if (!df.exists()) {
+			return;
+		}
+		// Note, changelogRevisionIndex may be TIP, while #implAnnotateChange doesn't tolerate constants
+		//
+		// XXX df.indexWalk(0, fileRevIndex, ) might be more effective
+		int fileRevIndex = fileRevIndex(df, changelogRevisionIndex);
+		int[] fileRevParents = new int[2];
+		IntVector fileParentRevs = new IntVector((fileRevIndex+1) * 2, 0);
+		fileParentRevs.add(NO_REVISION, NO_REVISION);
+		for (int i = 1; i <= fileRevIndex; i++) {
+			df.parents(i, fileRevParents, null, null);
+			fileParentRevs.add(fileRevParents[0], fileRevParents[1]);
+		}
+		// collect file revisions to visit, from newest to oldest
+		IntVector fileRevsToVisit = new IntVector(fileRevIndex + 1, 0);
+		LinkedList<Integer> queue = new LinkedList<Integer>();
+		BitSet seen = new BitSet(fileRevIndex + 1);
+		queue.add(fileRevIndex);
+		do {
+			int x = queue.removeFirst();
+			if (seen.get(x)) {
+				continue;
+			}
+			seen.set(x);
+			fileRevsToVisit.add(x);
+			int p1 = fileParentRevs.get(2*x);
+			int p2 = fileParentRevs.get(2*x + 1);
+			if (p1 != NO_REVISION) {
+				queue.addLast(p1);
+			}
+			if (p2 != NO_REVISION) {
+				queue.addLast(p2);
+			}
+		} while (!queue.isEmpty());
+		FileLinesCache fileInfoCache = new FileLinesCache(df, 10);
+		// fileRevsToVisit now { r10, r7, r6, r5, r0 }
+		// and we'll iterate it from behind, e.g. old to new unless reversed 
+		if (iterateOrder == HgIterateDirection.NewToOld) {
+			fileRevsToVisit.reverse();
+		}
+		for (int i = fileRevsToVisit.size() - 1; i >= 0; i--) {
+			int fri = fileRevsToVisit.get(i);
+			int clogRevIndex = df.getChangesetRevisionIndex(fri);
+			fileRevParents[0] = fileParentRevs.get(fri * 2);
+			fileRevParents[1] = fileParentRevs.get(fri * 2 + 1);
+			implAnnotateChange(fileInfoCache, clogRevIndex, fri, fileRevParents, insp);
+		}
 	}
 
 	/**
 	 * Annotate file revision, line by line. 
 	 */
-	public void annotate(HgDataFile df, int changesetRevisionIndex, LineInspector insp) {
+	public void annotate(HgDataFile df, int changelogRevisionIndex, LineInspector insp) {
 		if (!df.exists()) {
 			return;
 		}
-		int fileRevIndex = fileRevIndex(df, changesetRevisionIndex);
-		int[] fileRevParents = new int[2];
 		FileAnnotation fa = new FileAnnotation(insp);
-		do {
-			// also covers changesetRevisionIndex == TIP, #implAnnotateChange doesn't tolerate constants
-			changesetRevisionIndex = df.getChangesetRevisionIndex(fileRevIndex);
-			df.parents(fileRevIndex, fileRevParents, null, null);
-			implAnnotateChange(df, changesetRevisionIndex, fileRevIndex, fileRevParents, fa);
-			fileRevIndex = fileRevParents[0];
-		} while (fileRevIndex != NO_REVISION);
+		annotate(df, changelogRevisionIndex, fa, HgIterateDirection.NewToOld);
 	}
 
 	/**
 	 * Annotates changes of the file against its parent(s)
 	 */
-	public void annotateChange(HgDataFile df, int changesetRevisionIndex, BlockInspector insp) {
+	public void annotateChange(HgDataFile df, int changelogRevisionIndex, BlockInspector insp) {
 		// TODO detect if file is text/binary (e.g. looking for chars < ' ' and not \t\r\n\f
-		int fileRevIndex = fileRevIndex(df, changesetRevisionIndex);
+		int fileRevIndex = fileRevIndex(df, changelogRevisionIndex);
 		int[] fileRevParents = new int[2];
 		df.parents(fileRevIndex, fileRevParents, null, null);
-		if (changesetRevisionIndex == TIP) {
-			changesetRevisionIndex = df.getChangesetRevisionIndex(fileRevIndex);
+		if (changelogRevisionIndex == TIP) {
+			changelogRevisionIndex = df.getChangesetRevisionIndex(fileRevIndex);
 		}
-		implAnnotateChange(df, changesetRevisionIndex, fileRevIndex, fileRevParents, insp);
+		implAnnotateChange(new FileLinesCache(df, 5), changelogRevisionIndex, fileRevIndex, fileRevParents, insp);
 	}
 
-	private void implAnnotateChange(HgDataFile df, int csetRevIndex, int fileRevIndex, int[] fileParentRevs, BlockInspector insp) {
-		final LineSequence fileRevLines = lines(df, fileRevIndex);
+	private void implAnnotateChange(FileLinesCache fl, int csetRevIndex, int fileRevIndex, int[] fileParentRevs, BlockInspector insp) {
+		final LineSequence fileRevLines = fl.lines(fileRevIndex);
 		if (fileParentRevs[0] != NO_REVISION && fileParentRevs[1] != NO_REVISION) {
-			LineSequence p1Lines = lines(df, fileParentRevs[0]);
-			LineSequence p2Lines = lines(df, fileParentRevs[1]);
-			int p1ClogIndex = df.getChangesetRevisionIndex(fileParentRevs[0]);
-			int p2ClogIndex = df.getChangesetRevisionIndex(fileParentRevs[1]);
+			LineSequence p1Lines = fl.lines(fileParentRevs[0]);
+			LineSequence p2Lines = fl.lines(fileParentRevs[1]);
+			int p1ClogIndex = fl.getChangesetRevisionIndex(fileParentRevs[0]);
+			int p2ClogIndex = fl.getChangesetRevisionIndex(fileParentRevs[1]);
 			DiffHelper<LineSequence> pg = new DiffHelper<LineSequence>();
 			pg.init(p2Lines, fileRevLines);
 			EqualBlocksCollector p2MergeCommon = new EqualBlocksCollector();
@@ -106,9 +158,9 @@
 		} else {
 			int soleParent = fileParentRevs[0] == NO_REVISION ? fileParentRevs[1] : fileParentRevs[0];
 			assert soleParent != NO_REVISION;
-			LineSequence parentLines = lines(df, soleParent);
+			LineSequence parentLines = fl.lines(soleParent);
 			
-			int parentChangesetRevIndex = df.getChangesetRevisionIndex(soleParent);
+			int parentChangesetRevIndex = fl.getChangesetRevisionIndex(soleParent);
 			DiffHelper<LineSequence> pg = new DiffHelper<LineSequence>();
 			pg.init(parentLines, fileRevLines);
 			pg.findMatchingBlocks(new BlameBlockInspector(insp, parentChangesetRevIndex, csetRevIndex));
@@ -120,17 +172,64 @@
 		return df.getRevisionIndex(fileRev);
 	}
 
-	private static LineSequence lines(HgDataFile df, int fileRevIndex) {
-		try {
-			ByteArrayChannel c;
-			df.content(fileRevIndex, c = new ByteArrayChannel());
-			return LineSequence.newlines(c.toArray());
-		} catch (CancelledException ex) {
-			// TODO likely it was bad idea to throw cancelled exception from content()
-			// deprecate and provide alternative?
-			HgInvalidStateException ise = new HgInvalidStateException("ByteArrayChannel never throws CancelledException");
-			ise.initCause(ex);
-			throw ise;
+	private static class FileLinesCache {
+		private final HgDataFile df;
+		private final LinkedList<Pair<Integer, LineSequence>> lruCache;
+		private final int limit;
+		private IntMap<Integer> fileToClogIndexMap = new IntMap<Integer>(20);
+
+		public FileLinesCache(HgDataFile file, int lruLimit) {
+			df = file;
+			limit = lruLimit;
+			lruCache = new LinkedList<Pair<Integer, LineSequence>>();
+		}
+		
+		public int getChangesetRevisionIndex(int fileRevIndex) {
+			Integer cached = fileToClogIndexMap.get(fileRevIndex);
+			if (cached == null) {
+				cached = df.getChangesetRevisionIndex(fileRevIndex);
+				fileToClogIndexMap.put(fileRevIndex, cached);
+			}
+			return cached.intValue();
+		}
+
+		public LineSequence lines(int fileRevIndex) {
+			Pair<Integer, LineSequence> cached = checkCache(fileRevIndex);
+			if (cached != null) {
+				return cached.second();
+			}
+			try {
+				ByteArrayChannel c;
+				df.content(fileRevIndex, c = new ByteArrayChannel());
+				LineSequence rv = LineSequence.newlines(c.toArray());
+				lruCache.addFirst(new Pair<Integer, LineSequence>(fileRevIndex, rv));
+				if (lruCache.size() > limit) {
+					lruCache.removeLast();
+				}
+				return rv;
+			} catch (CancelledException ex) {
+				// TODO likely it was bad idea to throw cancelled exception from content()
+				// deprecate and provide alternative?
+				HgInvalidStateException ise = new HgInvalidStateException("ByteArrayChannel never throws CancelledException");
+				ise.initCause(ex);
+				throw ise;
+			}
+		}
+		
+		private Pair<Integer,LineSequence> checkCache(int fileRevIndex) {
+			Pair<Integer, LineSequence> rv = null;
+			for (ListIterator<Pair<Integer, LineSequence>> it = lruCache.listIterator(); it.hasNext(); ) {
+				Pair<Integer, LineSequence> p = it.next();
+				if (p.first() == fileRevIndex) {
+					rv = p;
+					it.remove();
+					break;
+				}
+			}
+			if (rv != null) {
+				lruCache.addFirst(rv);
+			}
+			return rv;
 		}
 	}
 
diff -r 4ea0351ca878 -r 45751456b471 src/org/tmatesoft/hg/internal/IntVector.java
--- a/src/org/tmatesoft/hg/internal/IntVector.java	Wed Feb 20 18:19:52 2013 +0100
+++ b/src/org/tmatesoft/hg/internal/IntVector.java	Wed Feb 20 22:23:50 2013 +0100
@@ -49,7 +49,7 @@
 	
 	public void add(int... values) {
 		if (count + values.length > data.length) {
-			grow(count + values.length - data.length);
+			grow(count + values.length);
 		}
 		for (int v : values) {
 			data[count++] = v;
@@ -92,6 +92,19 @@
 		System.arraycopy(data, 0, rv, 0, count);
 		return rv;
 	}
+	
+	public void reverse() {
+		for (int a = 0, b = count-1; a < b; a++, b--) {
+			int t = data[b];
+			data[b] = data[a];
+			data[a] = t;
+		}
+	}
+
+	@Override
+	public String toString() {
+		return String.format("%s[%d]", IntVector.class.getSimpleName(), size());
+	}
 
 	/**
 	 * Use only when this instance won't be used any longer
@@ -117,9 +130,4 @@
 		System.arraycopy(data, 0, newData, 0, count);
 		data = newData;
 	}
-	
-	@Override
-	public String toString() {
-		return String.format("%s[%d]", IntVector.class.getSimpleName(), size());
-	}
 }
diff -r 4ea0351ca878 -r 45751456b471 test/org/tmatesoft/hg/test/TestAuxUtilities.java
--- a/test/org/tmatesoft/hg/test/TestAuxUtilities.java	Wed Feb 20 18:19:52 2013 +0100
+++ b/test/org/tmatesoft/hg/test/TestAuxUtilities.java	Wed Feb 20 22:23:50 2013 +0100
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2011-2012 TMate Software Ltd
+ * Copyright (c) 2011-2013 TMate Software Ltd
  *  
  * This program is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License as published by
@@ -31,6 +31,7 @@
 import org.tmatesoft.hg.core.HgCatCommand;
 import org.tmatesoft.hg.core.Nodeid;
 import org.tmatesoft.hg.internal.ArrayHelper;
+import org.tmatesoft.hg.internal.IntVector;
 import org.tmatesoft.hg.internal.PathScope;
 import org.tmatesoft.hg.internal.RevisionDescendants;
 import org.tmatesoft.hg.repo.HgChangelog;
@@ -497,6 +498,36 @@
 		errorCollector.assertEquals(Unrelated, p3.compareWith(p2));
 	}
 	
+	@Test
+	public void testIntVector() {
+		IntVector v = new IntVector();
+		v.add(10, 9, 8);
+		v.add(7);
+		errorCollector.assertEquals(4, v.size());
+		v.clear();
+		errorCollector.assertEquals(0, v.size());
+		
+		// vector that doesn't grow
+		v = new IntVector(3, 0);
+		v.add(1,2,3);
+		try {
+			v.add(4);
+			errorCollector.fail("This vector instance is not supposed to grow on demand");
+		} catch (UnsupportedOperationException ex) {
+		}
+		v = new IntVector(5, 2);
+		v.add(10,9,8);
+		v.add(7,6);
+		v.add(5,4,3,2,1);
+		errorCollector.assertEquals(10, v.size());
+		// so far so good - grow() works
+		// now, check reverse() 
+		v.reverse();
+		for (int i = 0; i < v.size(); i++) {
+			errorCollector.assertEquals(i+1, v.get(i));
+		}
+	}
+	
 	
 	public static void main(String[] args) throws Exception {
 		new TestAuxUtilities().testRepositoryConfig();
diff -r 4ea0351ca878 -r 45751456b471 test/org/tmatesoft/hg/test/TestBlame.java
--- a/test/org/tmatesoft/hg/test/TestBlame.java	Wed Feb 20 18:19:52 2013 +0100
+++ b/test/org/tmatesoft/hg/test/TestBlame.java	Wed Feb 20 22:23:50 2013 +0100
@@ -30,6 +30,7 @@
 import org.junit.Rule;
 import org.junit.Test;
 import org.tmatesoft.hg.console.Bundle.Dump;
+import org.tmatesoft.hg.core.HgIterateDirection;
 import org.tmatesoft.hg.internal.AnnotateFacility;
 import org.tmatesoft.hg.internal.AnnotateFacility.AddBlock;
 import org.tmatesoft.hg.internal.AnnotateFacility.Block;
@@ -78,7 +79,7 @@
 		OutputParser.Stub op = new OutputParser.Stub();
 		ExecHelper eh = new ExecHelper(op, null);
 
-		for (int startChangeset : new int[] { TIP, /*539, 541/ *, TIP */}) {
+		for (int startChangeset : new int[] { 539, 541 /*, TIP */}) {
 			FileAnnotateInspector fa = new FileAnnotateInspector();
 			new AnnotateFacility().annotate(df, startChangeset, fa);
 			
@@ -142,7 +143,7 @@
 		af.annotateChange(df, 531, dump);
 		
 		FileAnnotateInspector fai = new FileAnnotateInspector();
-		af.annotate(df, TIP, fai);
+		af.annotate(df, 541, fai);
 		for (int i = 0; i < fai.lineRevisions.length; i++) {
 			System.out.printf("%3d: LINE %d\n", fai.lineRevisions[i], i+1);
 		}
@@ -155,13 +156,15 @@
 		HgDataFile df = repo.getFileNode(fname);
 		AnnotateFacility af = new AnnotateFacility();
 		DiffOutInspector dump = new DiffOutInspector(System.out);
-		System.out.println("413 -> 415");
-		af.diff(df, 413, 415, dump);
-		System.out.println("408 -> 415");
-		af.diff(df, 408, 415, dump);
-		System.out.println("Combined (with merge):");
+//		System.out.println("413 -> 415");
+//		af.diff(df, 413, 415, dump);
+//		System.out.println("408 -> 415");
+//		af.diff(df, 408, 415, dump);
+//		System.out.println("Combined (with merge):");
+//		dump.needRevisions(true);
+//		af.annotateChange(df, checkChangeset, dump);
 		dump.needRevisions(true);
-		af.annotateChange(df, checkChangeset, dump);
+		af.annotate(df, checkChangeset, dump, HgIterateDirection.OldToNew);
 	}
 
 	private void leftovers() throws Exception {