Mercurial > jhg

changeset 552:45751456b471

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Annotate file changes through few revisions, walking either direction (old to new and vice versa)
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Wed, 20 Feb 2013 22:23:50 +0100
parents 4ea0351ca878
children 093a2022dad5
files src/org/tmatesoft/hg/internal/AnnotateFacility.java src/org/tmatesoft/hg/internal/IntVector.java test/org/tmatesoft/hg/test/TestAuxUtilities.java test/org/tmatesoft/hg/test/TestBlame.java
diffstat 4 files changed, 197 insertions(+), 56 deletions(-) [+]
line wrap: on
line diff
--- 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;
 		}
 	}
 
--- 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());
-	}
 }
--- 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();
--- 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 {