# HG changeset patch
# User Artem Tikhomirov <tikhomirov.artem@gmail.com>
# Date 1361814104 -3600
# Node ID 154718ae23edb4714c07a10cda4ae5145e32d119
# Parent  b9e5ac26dd8325918dd5e5146e58ede1c1cf1daa
Annotate: refactor/reuse range handling code

diff -r b9e5ac26dd83 -r 154718ae23ed src/org/tmatesoft/hg/internal/FileAnnotation.java
--- a/src/org/tmatesoft/hg/internal/FileAnnotation.java	Sun Feb 24 00:11:40 2013 +0100
+++ b/src/org/tmatesoft/hg/internal/FileAnnotation.java	Mon Feb 25 18:41:44 2013 +0100
@@ -16,7 +16,6 @@
  */
 package org.tmatesoft.hg.internal;
 
-import java.util.Formatter;
 
 import org.tmatesoft.hg.core.HgIterateDirection;
 import org.tmatesoft.hg.repo.HgBlameFacility;
@@ -160,110 +159,4 @@
 			return FileAnnotation.this.knownLines.length;
 		}
 	}
-
-	private static class RangeSeq {
-		// XXX smth like IntSliceVector to access triples (or slices of any size, in fact)
-		// with easy indexing, e.g. #get(sliceIndex, indexWithinSlice)
-		// and vect.get(7,2) instead of vect.get(7*SIZEOF_SLICE+2)
-		private final IntVector ranges = new IntVector(3*10, 3*5);
-		private int count;
-		
-		public void add(int start1, int start2, int length) {
-			if (count > 0) {
-				int lastIndex = 3 * (count-1);
-				int lastS1 = ranges.get(lastIndex);
-				int lastS2 = ranges.get(lastIndex + 1);
-				int lastLen = ranges.get(lastIndex + 2);
-				if (start1 == lastS1 + lastLen && start2 == lastS2 + lastLen) {
-					// new range continues the previous one - just increase the length
-					ranges.set(lastIndex + 2, lastLen + length);
-					return;
-				}
-			}
-			ranges.add(start1, start2, length);
-			count++;
-		}
-		
-		public void clear() {
-			ranges.clear();
-			count = 0;
-		}
-
-		public int size() {
-			return count;
-		}
-
-		public int mapLineIndex(int ln) {
-			for (int i = 0; i < ranges.size(); i += 3) {
-				int s1 = ranges.get(i);
-				if (s1 > ln) {
-					return -1;
-				}
-				int l = ranges.get(i+2);
-				if (s1 + l > ln) {
-					int s2 = ranges.get(i + 1);
-					return s2 + (ln - s1);
-				}
-			}
-			return -1;
-		}
-		
-		public RangeSeq intersect(RangeSeq target) {
-			RangeSeq v = new RangeSeq();
-			for (int i = 0; i < ranges.size(); i += 3) {
-				int originLine = ranges.get(i);
-				int targetLine = ranges.get(i + 1);
-				int length = ranges.get(i + 2);
-				int startTargetLine = -1, startOriginLine = -1, c = 0;
-				for (int j = 0; j < length; j++) {
-					int lnInFinal = target.mapLineIndex(targetLine + j);
-					if (lnInFinal == -1 || (startTargetLine != -1 && lnInFinal != startTargetLine + c)) {
-						// the line is not among "same" in ultimate origin
-						// or belongs to another/next "same" chunk 
-						if (startOriginLine == -1) {
-							continue;
-						}
-						v.add(startOriginLine, startTargetLine, c);
-						c = 0;
-						startOriginLine = startTargetLine = -1;
-						// fall-through to check if it's not complete miss but a next chunk
-					}
-					if (lnInFinal != -1) {
-						if (startOriginLine == -1) {
-							startOriginLine = originLine + j;
-							startTargetLine = lnInFinal;
-							c = 1;
-						} else {
-							// lnInFinal != startTargetLine + s is covered above
-							assert lnInFinal == startTargetLine + c;
-							c++;
-						}
-					}
-				}
-				if (startOriginLine != -1) {
-					assert c > 0;
-					v.add(startOriginLine, startTargetLine, c);
-				}
-			}
-			return v;
-		}
-		
-		@SuppressWarnings("unused")
-		public CharSequence dump() {
-			StringBuilder sb = new StringBuilder();
-			Formatter f = new Formatter(sb);
-			for (int i = 0; i < ranges.size(); i += 3) {
-				int s1 = ranges.get(i);
-				int s2 = ranges.get(i + 1);
-				int len = ranges.get(i + 2);
-				f.format("[%d..%d) == [%d..%d);  ", s1, s1 + len, s2, s2 + len);
-			}
-			return sb;
-		}
-		
-		@Override
-		public String toString() {
-			return String.format("RangeSeq[%d]:%s", count, dump());
-		}
-	}
 }
\ No newline at end of file
diff -r b9e5ac26dd83 -r 154718ae23ed src/org/tmatesoft/hg/internal/RangeSeq.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/org/tmatesoft/hg/internal/RangeSeq.java	Mon Feb 25 18:41:44 2013 +0100
@@ -0,0 +1,175 @@
+/*
+ * Copyright (c) 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
+ * the Free Software Foundation; version 2 of the License.
+ *
+ * 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 General Public License for more details.
+ *
+ * For information on how to redistribute this software under
+ * the terms of a license other than GNU General Public License
+ * contact TMate Software at support@hg4j.com
+ */
+package org.tmatesoft.hg.internal;
+
+import java.util.Formatter;
+
+/**
+ * Sequence of range pairs (denoted origin and target), {originStart, targetStart, length}, tailored for diff/annotate
+ * 
+ * @author Artem Tikhomirov
+ * @author TMate Software Ltd.
+ */
+public final class RangeSeq {
+	// XXX smth like IntSliceVector to access triples (or slices of any size, in fact)
+	// with easy indexing, e.g. #get(sliceIndex, indexWithinSlice)
+	// and vect.get(7,2) instead of vect.get(7*SIZEOF_SLICE+2)
+	private final IntVector ranges = new IntVector(3*10, 3*5);
+	private int count;
+	
+	public void add(int start1, int start2, int length) {
+		if (count > 0) {
+			int lastIndex = 3 * (count-1);
+			int lastS1 = ranges.get(lastIndex);
+			int lastS2 = ranges.get(lastIndex + 1);
+			int lastLen = ranges.get(lastIndex + 2);
+			if (start1 == lastS1 + lastLen && start2 == lastS2 + lastLen) {
+				// new range continues the previous one - just increase the length
+				ranges.set(lastIndex + 2, lastLen + length);
+				return;
+			}
+		}
+		ranges.add(start1, start2, length);
+		count++;
+	}
+	
+	public void clear() {
+		ranges.clear();
+		count = 0;
+	}
+
+	public int size() {
+		return count;
+	}
+
+	/**
+	 * find out line index in the target that matches specified origin line
+	 */
+	public int mapLineIndex(int ln) {
+		for (int i = 0; i < ranges.size(); i += 3) {
+			int s1 = ranges.get(i);
+			if (s1 > ln) {
+				return -1;
+			}
+			int l = ranges.get(i+2);
+			if (s1 + l > ln) {
+				int s2 = ranges.get(i + 1);
+				return s2 + (ln - s1);
+			}
+		}
+		return -1;
+	}
+	
+	/**
+	 * find out line index in origin that matches specified target line
+	 */
+	public int reverseMapLine(int targetLine) {
+		for (int i = 0; i < ranges.size(); i +=3) {
+			int ts = ranges.get(i + 1);
+			if (ts > targetLine) {
+				return -1;
+			}
+			int l = ranges.get(i + 2);
+			if (ts + l > targetLine) {
+				int os = ranges.get(i);
+				return os + (targetLine - ts);
+			}
+		}
+		return -1;
+	}
+	
+	public RangeSeq intersect(RangeSeq target) {
+		RangeSeq v = new RangeSeq();
+		for (int i = 0; i < ranges.size(); i += 3) {
+			int originLine = ranges.get(i);
+			int targetLine = ranges.get(i + 1);
+			int length = ranges.get(i + 2);
+			int startTargetLine = -1, startOriginLine = -1, c = 0;
+			for (int j = 0; j < length; j++) {
+				int lnInFinal = target.mapLineIndex(targetLine + j);
+				if (lnInFinal == -1 || (startTargetLine != -1 && lnInFinal != startTargetLine + c)) {
+					// the line is not among "same" in ultimate origin
+					// or belongs to another/next "same" chunk 
+					if (startOriginLine == -1) {
+						continue;
+					}
+					v.add(startOriginLine, startTargetLine, c);
+					c = 0;
+					startOriginLine = startTargetLine = -1;
+					// fall-through to check if it's not complete miss but a next chunk
+				}
+				if (lnInFinal != -1) {
+					if (startOriginLine == -1) {
+						startOriginLine = originLine + j;
+						startTargetLine = lnInFinal;
+						c = 1;
+					} else {
+						// lnInFinal != startTargetLine + s is covered above
+						assert lnInFinal == startTargetLine + c;
+						c++;
+					}
+				}
+			}
+			if (startOriginLine != -1) {
+				assert c > 0;
+				v.add(startOriginLine, startTargetLine, c);
+			}
+		}
+		return v;
+	}
+	
+	// true when specified line in origin is equal to a line in target
+	public boolean includesOriginLine(int ln) {
+		return includes(ln, 0);
+	}
+	
+	// true when specified line in target is equal to a line in origin
+	public boolean includesTargetLine(int ln) {
+		return includes(ln, 1);
+	}
+
+	private boolean includes(int ln, int o) {
+		for (int i = 2; i < ranges.size(); o += 3, i+=3) {
+			int rangeStart = ranges.get(o);
+			if (rangeStart > ln) {
+				return false;
+			}
+			int rangeLen = ranges.get(i);
+			if (rangeStart + rangeLen > ln) {
+				return true;
+			}
+		}
+		return false;
+	}
+
+	public CharSequence dump() {
+		StringBuilder sb = new StringBuilder();
+		Formatter f = new Formatter(sb);
+		for (int i = 0; i < ranges.size(); i += 3) {
+			int s1 = ranges.get(i);
+			int s2 = ranges.get(i + 1);
+			int len = ranges.get(i + 2);
+			f.format("[%d..%d) == [%d..%d);  ", s1, s1 + len, s2, s2 + len);
+		}
+		return sb;
+	}
+	
+	@Override
+	public String toString() {
+		return String.format("RangeSeq[%d]", count);
+	}
+}
\ No newline at end of file
diff -r b9e5ac26dd83 -r 154718ae23ed src/org/tmatesoft/hg/repo/HgBlameFacility.java
--- a/src/org/tmatesoft/hg/repo/HgBlameFacility.java	Sun Feb 24 00:11:40 2013 +0100
+++ b/src/org/tmatesoft/hg/repo/HgBlameFacility.java	Mon Feb 25 18:41:44 2013 +0100
@@ -33,6 +33,7 @@
 import org.tmatesoft.hg.internal.IntVector;
 import org.tmatesoft.hg.internal.DiffHelper.LineSequence;
 import org.tmatesoft.hg.internal.DiffHelper.LineSequence.ByteChain;
+import org.tmatesoft.hg.internal.RangeSeq;
 import org.tmatesoft.hg.repo.HgBlameFacility.RevisionDescriptor.Recipient;
 import org.tmatesoft.hg.util.Adaptable;
 import org.tmatesoft.hg.util.CancelledException;
@@ -740,36 +741,27 @@
 	}
 	
 
-	static class EqualBlocksCollector implements DiffHelper.MatchInspector<LineSequence> {
-		// FIXME replace with RangeSeq
-		private final IntVector matches = new IntVector(10*3, 2*3);
+	private static class EqualBlocksCollector implements DiffHelper.MatchInspector<LineSequence> {
+		private final RangeSeq matches = new RangeSeq();
 
 		public void begin(LineSequence s1, LineSequence s2) {
 		}
 
 		public void match(int startSeq1, int startSeq2, int matchLength) {
-			matches.add(startSeq1);
-			matches.add(startSeq2);
-			matches.add(matchLength);
+			matches.add(startSeq1, startSeq2, matchLength);
 		}
 
 		public void end() {
 		}
-		
-		// true when specified line in origin is equal to a line in target
-		public boolean includesOriginLine(int ln) {
-			return includes(ln, 0);
+
+		public int reverseMapLine(int ln) {
+			return matches.reverseMapLine(ln);
 		}
-		
-		// true when specified line in target is equal to a line in origin
-		public boolean includesTargetLine(int ln) {
-			return includes(ln, 1);
-		}
-		
+
 		public void intersectWithTarget(int start, int length, IntVector result) {
 			int s = start;
 			for (int l = start, x = start + length; l < x; l++) {
-				if (!includesTargetLine(l)) {
+				if (!matches.includesTargetLine(l)) {
 					if (l - s > 0) {
 						result.add(s);
 						result.add(l - s);
@@ -783,25 +775,6 @@
 			}
 		}
 		
-		/**
-		 * find out line index in origin that matches specifid target line
-		 */
-		public int reverseMapLine(int targetLine) {
-			for (int i = 0; i < matches.size(); i +=3) {
-				int os = matches.get(i);
-				int ts = matches.get(i + 1);
-				int l = matches.get(i + 2);
-				if (ts > targetLine) {
-					return -1;
-				}
-				if (ts + l > targetLine) {
-					return os + (targetLine - ts);
-				}
-			}
-			return -1;
-		}
-
-
 		/*
 		 * intersects [start..start+length) with ranges of target lines, and based on the intersection 
 		 * breaks initial range into smaller ranges and records them into result, with marker to indicate
@@ -811,7 +784,7 @@
 		public void combineAndMarkRangesWithTarget(int start, int length, int markerSource, int markerTarget, IntVector result) {
 			int sourceStart = start, targetStart = start, sourceEnd = start + length;
 			for (int l = sourceStart; l < sourceEnd; l++) {
-				if (includesTargetLine(l)) {
+				if (matches.includesTargetLine(l)) {
 					// l is from target
 					if (sourceStart < l) {
 						// few lines from source range were not in the target, report them
@@ -848,20 +821,6 @@
 				result.add(sourceEnd - targetStart);
 			}
 		}
-		
-		private boolean includes(int ln, int o) {
-			for (int i = 2; i < matches.size(); o += 3, i+=3) {
-				int rangeStart = matches.get(o);
-				if (rangeStart > ln) {
-					return false;
-				}
-				int rangeLen = matches.get(i);
-				if (rangeStart + rangeLen > ln) {
-					return true;
-				}
-			}
-			return false;
-		}
 	}
 
 	private static class AnnotateRev implements RevisionDescriptor {
@@ -923,11 +882,6 @@
 		bc.match(-1, 10, 2);
 		bc.match(-1, 15, 3);
 		bc.match(-1, 20, 3);
-		assert !bc.includesTargetLine(4);
-		assert bc.includesTargetLine(7);
-		assert !bc.includesTargetLine(8);
-		assert bc.includesTargetLine(10);
-		assert !bc.includesTargetLine(12);
 		IntVector r = new IntVector();
 		bc.intersectWithTarget(7, 10, r);
 		for (int i = 0; i < r.size(); i+=2) {
diff -r b9e5ac26dd83 -r 154718ae23ed test/org/tmatesoft/hg/test/TestAuxUtilities.java
--- a/test/org/tmatesoft/hg/test/TestAuxUtilities.java	Sun Feb 24 00:11:40 2013 +0100
+++ b/test/org/tmatesoft/hg/test/TestAuxUtilities.java	Mon Feb 25 18:41:44 2013 +0100
@@ -33,6 +33,7 @@
 import org.tmatesoft.hg.internal.ArrayHelper;
 import org.tmatesoft.hg.internal.IntVector;
 import org.tmatesoft.hg.internal.PathScope;
+import org.tmatesoft.hg.internal.RangeSeq;
 import org.tmatesoft.hg.internal.RevisionDescendants;
 import org.tmatesoft.hg.repo.HgChangelog;
 import org.tmatesoft.hg.repo.HgChangelog.RawChangeset;
@@ -528,6 +529,20 @@
 		}
 	}
 	
+	@Test
+	public void testRangeSequence() {
+		RangeSeq rs = new RangeSeq();
+		rs.add(-1, 5, 3);
+		rs.add(-1, 10, 2);
+		rs.add(-1, 15, 3);
+		rs.add(-1, 20, 3);
+		errorCollector.assertFalse(rs.includesTargetLine(4));
+		errorCollector.assertTrue(rs.includesTargetLine(7));
+		errorCollector.assertFalse(rs.includesTargetLine(8));
+		errorCollector.assertTrue(rs.includesTargetLine(10));
+		errorCollector.assertFalse(rs.includesTargetLine(12));
+	}
+	
 	
 	public static void main(String[] args) throws Exception {
 		new TestAuxUtilities().testRepositoryConfig();
diff -r b9e5ac26dd83 -r 154718ae23ed test/org/tmatesoft/hg/test/TestBlame.java
--- a/test/org/tmatesoft/hg/test/TestBlame.java	Sun Feb 24 00:11:40 2013 +0100
+++ b/test/org/tmatesoft/hg/test/TestBlame.java	Mon Feb 25 18:41:44 2013 +0100
@@ -118,9 +118,22 @@
 		HgDataFile df = repo.getFileNode("file1");
 		OutputParser.Stub op = new OutputParser.Stub();
 		eh = new ExecHelper(op, repo.getWorkingDir());
-		for (int cs : new int[] { 4, 6, TIP/*, 8 FIXME find out how come hg annotate doesn't see re-added line in rev4*/}) {
+		for (int cs : new int[] { 4, 6 /*, 8 see below*/, TIP}) {
 			doLineAnnotateTest(df, cs, op);
 		}
+		/*`hg annotate -r 8` and HgBlameFacility give different result
+		 * for "r0, line 5" line, which was deleted in rev2 and restored back in
+		 * rev4 (both in default branch), while branch with r3 and r6 kept the line intact.
+		 * HgBlame reports rev4 for the line, `hg annotate` gives original, rev0.
+		 * However `hg annotate -r 4` shows rev4 for the line, too. The aforementioned rev0 for 
+		 * the merge rev8 results from the iteration order and is implementation specific 
+		 * (i.e. one can't tell which one is right). Mercurial walks from parents to children,
+		 * and traces equal lines, wile HgBlameFacility walks from child to parents and records 
+		 * changes (additions). Seems it processes branch with rev3 and rev6 first 
+		 * (printout in context.py, annotate and annotate.pair reveals that), and the line 0_5
+		 * comes as unchanged through this branch, and later processing rev2 and rev4 doesn't 
+		 * change that. 
+		 */
 	}
 	
 	@Test