# HG changeset patch
# User Artem Tikhomirov <tikhomirov.artem@gmail.com>
# Date 1374419734 -7200
# Node ID 58a6900f845d8e04dfe6564bba56adcedb56f29a
# Parent  19f5167c2155b02b22c258cba6fe67a491967f5a
Blame: alternative strategy to handle merge revisions: map(diff(p1->base->p2)) to understand merge intentions better

diff -r 19f5167c2155 -r 58a6900f845d src/org/tmatesoft/hg/core/HgAnnotateCommand.java
--- a/src/org/tmatesoft/hg/core/HgAnnotateCommand.java	Sat Jul 20 17:40:52 2013 +0200
+++ b/src/org/tmatesoft/hg/core/HgAnnotateCommand.java	Sun Jul 21 17:15:34 2013 +0200
@@ -80,6 +80,17 @@
 		return this;
 	}
 	
+	
+	/**
+	 * Select file to annotate,
+	 * @param fileNode repository file to annotate 
+	 * @param followCopyRename true to follow copies/renames.
+	 * @return <code>this</code> for convenience
+	 */
+	public HgAnnotateCommand file(HgDataFile fileNode, boolean followCopyRename) {
+		return file(fileNode.getPath(), followCopyRename);
+	}
+
 	// TODO [post-1.1] set encoding and provide String line content from LineInfo
 	// TODO FWIW: diff algorithms: http://bramcohen.livejournal.com/73318.html
 
diff -r 19f5167c2155 -r 58a6900f845d src/org/tmatesoft/hg/internal/BlameHelper.java
--- a/src/org/tmatesoft/hg/internal/BlameHelper.java	Sat Jul 20 17:40:52 2013 +0200
+++ b/src/org/tmatesoft/hg/internal/BlameHelper.java	Sun Jul 21 17:15:34 2013 +0200
@@ -19,17 +19,27 @@
 import static org.tmatesoft.hg.core.HgIterateDirection.OldToNew;
 import static org.tmatesoft.hg.repo.HgRepository.NO_REVISION;
 
+import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.Iterator;
 import java.util.LinkedList;
+import java.util.List;
 import java.util.ListIterator;
 
 import org.tmatesoft.hg.core.HgCallbackTargetException;
+import org.tmatesoft.hg.core.Nodeid;
 import org.tmatesoft.hg.internal.DiffHelper.LineSequence;
 import org.tmatesoft.hg.internal.DiffHelper.LineSequence.ByteChain;
+import org.tmatesoft.hg.internal.diff.DiffRangeMap;
+import org.tmatesoft.hg.internal.diff.DiffRangeMap.RangePair;
 import org.tmatesoft.hg.core.HgBlameInspector;
 import org.tmatesoft.hg.core.HgBlameInspector.*;
+import org.tmatesoft.hg.repo.HgChangelog;
 import org.tmatesoft.hg.repo.HgDataFile;
 import org.tmatesoft.hg.repo.HgInvalidStateException;
+import org.tmatesoft.hg.repo.HgParentChildMap;
+import org.tmatesoft.hg.repo.HgRepository;
+import org.tmatesoft.hg.repo.HgRevisionMap;
 import org.tmatesoft.hg.repo.HgRuntimeException;
 import org.tmatesoft.hg.util.Adaptable;
 import org.tmatesoft.hg.util.CancelledException;
@@ -45,6 +55,7 @@
 	
 	private final HgBlameInspector insp;
 	private FileLinesCache linesCache;
+	private HgParentChildMap<HgChangelog> clogMap;
 
 	public BlameHelper(HgBlameInspector inspector) {
 		insp = inspector;
@@ -100,14 +111,12 @@
 			int p2ClogIndex = fileParentClogRevs[1];
 			LineSequence p1Lines = linesCache.lines(p1ClogIndex, fileParentRevs[0]);
 			LineSequence p2Lines = linesCache.lines(p2ClogIndex, fileParentRevs[1]);
+			MergeResolutionStrategy mergeResolver = createMergeStrategy(fileRevLines, p1Lines, p2Lines, csetRevIndex, fileParentClogRevs);
+			//
 			DiffHelper<LineSequence> pg = new DiffHelper<LineSequence>();
-			pg.init(p2Lines, fileRevLines);
-			EqualBlocksCollector p2MergeCommon = new EqualBlocksCollector();
-			pg.findMatchingBlocks(p2MergeCommon);
-			//
-			pg.init(p1Lines);
+			pg.init(p1Lines, fileRevLines);
 			BlameBlockInspector bbi = new BlameBlockInspector(targetFile, fileRevIndex, insp, p1ClogIndex, csetRevIndex);
-			bbi.setMergeParent2(new MergeStrategy1(p2MergeCommon.matches), p2ClogIndex);
+			bbi.setMergeParent2(mergeResolver, p2ClogIndex);
 			pg.findMatchingBlocks(bbi);
 			bbi.checkErrors();
 		} else if (fileParentClogRevs[0] == fileParentClogRevs[1]) {
@@ -132,6 +141,66 @@
 		}
 	}
 	
+	private static final boolean useNewStrategy = Boolean.TRUE.booleanValue();
+	
+	private MergeResolutionStrategy createMergeStrategy(LineSequence fileRevLines, LineSequence p1Lines, LineSequence p2Lines, int csetRevIndex, int[] fileParentClogRevs) {
+		DiffHelper<LineSequence> pg = new DiffHelper<LineSequence>();
+		if (useNewStrategy) {
+			final ArrayList<RangePairSeq> allMatches = new ArrayList<RangePairSeq>();
+			pg.init(p2Lines, fileRevLines);
+			pg.findAllMatchAlternatives(new DiffHelper.MatchInspector<LineSequence>() {
+				private RangePairSeq matches;
+
+				public void begin(LineSequence s1, LineSequence s2) {
+					matches = new RangePairSeq();
+				}
+
+				public void match(int startSeq1, int startSeq2, int matchLength) {
+					matches.add(startSeq1, startSeq2, matchLength);
+				}
+
+				public void end() {
+					if (matches.size() > 0) {
+						allMatches.add(matches);
+					}
+				}
+				
+			});
+			//
+			LineSequence baseLines = getBaseRevisionLines(csetRevIndex, fileParentClogRevs);
+			pg.init(p1Lines, baseLines);
+			DiffRangeMap p1ToBase = new DiffRangeMap().fill(pg);
+			pg.init(baseLines, p2Lines);
+			DiffRangeMap baseToP2 = new DiffRangeMap().fill(pg);
+			return new MergeStrategy2(allMatches, p1ToBase, baseToP2);
+		} else {
+			pg.init(p2Lines, fileRevLines);
+			EqualBlocksCollector p2MergeCommon = new EqualBlocksCollector();
+			pg.findMatchingBlocks(p2MergeCommon);
+			return new MergeStrategy1(p2MergeCommon.matches);
+		}
+	}
+
+	private LineSequence getBaseRevisionLines(int clogRevIndex, int[] fileParentClogRevs) {
+		assert fileParentClogRevs[0] >= 0;
+		assert fileParentClogRevs[1] >= 0;
+		HgDataFile targetFile = linesCache.getFile(clogRevIndex);
+		final HgRepository repo = targetFile.getRepo();
+		if (clogMap == null) {
+			// FIXME replace HgParentChildMap with revlog.indexWalk(AncestorIterator))
+			clogMap = new HgParentChildMap<HgChangelog>(repo.getChangelog());
+			clogMap.init();
+		}
+		final HgRevisionMap<HgChangelog> m = clogMap.getRevisionMap();
+		Nodeid ancestor = clogMap.ancestor(m.revision(fileParentClogRevs[0]), m.revision(fileParentClogRevs[1]));
+		final int ancestorRevIndex = m.revisionIndex(ancestor);
+		Nodeid fr = repo.getManifest().getFileRevision(ancestorRevIndex, targetFile.getPath());
+		if (fr == null) {
+			return LineSequence.newlines(new byte[0]);
+		}
+		return linesCache.lines(ancestorRevIndex, targetFile.getRevisionIndex(fr));
+	}
+
 	private static class FileLinesCache {
 		private final LinkedList<Pair<Integer, LineSequence>> lruCache;
 		private final int limit;
@@ -281,7 +350,7 @@
 			}
 			try {
 				if (p2MergeCommon != null) {
-					IntSliceSeq mergeRanges = p2MergeCommon.combineAndMarkRangesWithSource(s2From, s2To - s2From, csetOrigin, csetMergeParent);
+					IntSliceSeq mergeRanges = p2MergeCommon.combineAndMarkRangesWithSource(s1From, s1To, s2From, s2To, csetOrigin, csetMergeParent);
 					
 					/*
 					 * Usecases, how it USED TO BE initially:
@@ -345,7 +414,7 @@
 			}
 			try {
 				if (p2MergeCommon != null) {
-					IntSliceSeq mergeRanges = p2MergeCommon.combineAndMarkRangesWithSource(s2From, s2To - s2From, csetOrigin, csetMergeParent);
+					IntSliceSeq mergeRanges = p2MergeCommon.combineAndMarkRangesWithSource(s1InsertPoint, s2From, s2To, csetOrigin, csetMergeParent);
 					int insPoint = s1InsertPoint; // track changes to insertion point
 					for (IntTuple mergeRange : mergeRanges) {
 						int rangeOrigin = mergeRange.at(0);
@@ -617,18 +686,7 @@
 			return contentBlock.seq.data(from, from + length);
 		}
 	}
-	
-	
-	interface MergeResolutionStrategy {
-		/**
-		 * breaks region [start..start+length) into ranges according to deduced (or simply guessed)
-		 * matching of these lines to lines in source1 and source2
-		 * @return list of tuples (source, start, length), where source is one of the identifiers supplied
-		 */
-		public IntSliceSeq combineAndMarkRangesWithSource(int start, int length, int source1, int source2);
-		public int getLineInP2(int mergeLine);
-	}
-	
+
 	private static class EqualBlocksCollector implements DiffHelper.MatchInspector<LineSequence> {
 		private final RangePairSeq matches = new RangePairSeq();
 
@@ -660,7 +718,20 @@
 		}
 		
 	}
-	
+
+	interface MergeResolutionStrategy {
+		/**
+		 * breaks region [start2..end2) into ranges according to deduced (or simply guessed)
+		 * matching of [start1..end1) lines to lines in source1 and source2
+		 * @return list of tuples (source, start, length), where source is one of the identifiers supplied
+		 */
+		public IntSliceSeq combineAndMarkRangesWithSource(int start1, int end1, int start2, int end2, int source1, int source2);
+		public IntSliceSeq combineAndMarkRangesWithSource(int insPoint, int start, int end, int source1, int source2);
+		public int getLineInP2(int mergeLine);
+	}
+
+	// report lines as merged from p2 solely based on whether target line belongs
+	// to a region that is equal to p2 region
 	private static class MergeStrategy1 implements MergeResolutionStrategy {
 		// equal ranges in p2 and merged revision
 		private final RangePairSeq matches; 
@@ -677,7 +748,7 @@
 		 * whether the range is from initial range (markerSource) or is a result of the intersection with target
 		 * (markerTarget)
 		 */
-		public IntSliceSeq combineAndMarkRangesWithSource(int start, int length, int markerSource, int markerTarget) {
+		private IntSliceSeq doCombine(int start, int length, int markerSource, int markerTarget) {
 			mergeRanges.clear();
 			assert mergeRanges.sliceSize() == 3;
 			int sourceStart = start, targetStart = start, sourceEnd = start + length;
@@ -716,7 +787,89 @@
 		public int getLineInP2(int mergeLine) {
 			return matches.reverseMapLine(mergeLine);
 		}
+
+		public IntSliceSeq combineAndMarkRangesWithSource(int start1, int end1, int start2, int end2, int source1, int source2) {
+			return doCombine(start2, end2 - start2, source1, source2);
+		}
+
+		public IntSliceSeq combineAndMarkRangesWithSource(int insPoint, int start, int end, int source1, int source2) {
+			return doCombine(start, end - start, source1, source2);
+		}
 	}
+	
+	private static class MergeStrategy2 implements MergeResolutionStrategy {
+		// equal ranges in p2 and merged revision
+		private final List<RangePairSeq> matches; 
+		private final IntSliceSeq mergeRanges;
+		private final DiffRangeMap p1ToBase;
+		private final DiffRangeMap baseToP2;
+
+		public MergeStrategy2(List<RangePairSeq> p2EqualToM, DiffRangeMap p1ToBaseRanges, DiffRangeMap baseToP2Ranges) {
+			matches = p2EqualToM;
+			p1ToBase = p1ToBaseRanges;
+			baseToP2= baseToP2Ranges;
+			mergeRanges = new IntSliceSeq(3, 10, 10);
+		}
+
+
+		public IntSliceSeq combineAndMarkRangesWithSource(int insPoint, int start, int end, int source1, int source2) {
+			return combineAndMarkRangesWithSource(insPoint, insPoint, start, end, source1, source2);
+		}
+
+		public IntSliceSeq combineAndMarkRangesWithSource(int start1, int end1, int start2, int end2, int source1, int source2) {
+			mergeRanges.clear();
+			IntSliceSeq mergedLines = new IntSliceSeq(2, end2-start2, 0);
+			for (int i = start2; i < end2; i++) {
+				mergedLines.add(source1, 0);
+			}
+			// [s1Start..s1End) // range in p1 seen as changed in m
+			for (RangePair p1_b : p1ToBase.findInSource(start1, end1)) {
+				// there might be few ranges in (p1-base) that overlap with (p1-m) changes
+				for (RangePair b_p2 : baseToP2.findInSource(p1_b.start2(), p1_b.end2())) {
+					// regions in p2 that correspond to affected regions in base
+					for (int p2Line = b_p2.start2(); p2Line < b_p2.end2(); p2Line++) {
+						for (RangePairSeq eq : matches) {
+							if (eq.includesOriginLine(p2Line)) {
+								// this line in p2 is equal to some line in merge
+								int mergeLine = eq.mapLineIndex(p2Line);
+								if (mergeLine >= start2 && mergeLine < end2) {
+									mergedLines.set(mergeLine - start2, source2, p2Line);
+								}
+							}
+						}
+					}
+				}
+			}
+			int lineCount = 0, start = start2;
+			int lastSeenSource = source1;
+			for (IntTuple t : mergedLines) {
+				if (t.at(0) == lastSeenSource) {
+					lineCount++;
+				} else {
+					if (lineCount > 0) {
+						mergeRanges.add(lastSeenSource, start, lineCount);
+						start += lineCount;
+					}
+					lineCount = 1;
+					lastSeenSource = t.at(0);
+				}
+			}
+			if (lineCount > 0) {
+				mergeRanges.add(lastSeenSource, start, lineCount);
+			}
+			return mergeRanges;
+		}
+
+		public int getLineInP2(int mergeLine) {
+			for (RangePairSeq eq : matches) {
+				if (eq.includesTargetLine(mergeLine)) {
+					return eq.reverseMapLine(mergeLine);
+				}
+			}
+			return -1;
+		}
+	}
+
 
 	private static class AnnotateRev implements RevisionDescriptor {
 		public ContentBlock origin, target;
@@ -789,7 +942,24 @@
 		}
 		System.out.println();
 		MergeStrategy1 ms = new MergeStrategy1(bc.matches);
-		IntSliceSeq mr = ms.combineAndMarkRangesWithSource(0, 16, 508, 514);
+		IntSliceSeq mr = ms.doCombine(0, 16, 508, 514);
+		for (IntTuple t : mr) {
+			System.out.printf("%d:[%d..%d)  ", t.at(0), t.at(1), t.at(1) + t.at(2));
+		}
+		System.out.println();
+		System.out.println();
+		DiffRangeMap m1 = new DiffRangeMap(); // p1 -> base
+		m1.match(0, 0, 1); // =1..1 -> 1..1
+		m1.match(7, 3, 0);  // *2..7 -> 2..3
+		DiffRangeMap m2 = new DiffRangeMap(); // base -> p2
+		m2.match(0, 0, 1); // =1..1 -> 1..1
+		m2.match(3, 3, 0); // *2..3 -> 2..3
+		RangePairSeq eq1 = new RangePairSeq();
+		eq1.add(0, 0, 3);
+		RangePairSeq eq2 = new RangePairSeq();
+		eq2.add(0, 4, 3);
+		MergeStrategy2 ms2 = new MergeStrategy2(Arrays.asList(eq1, eq2), m1, m2);
+		mr = ms2.combineAndMarkRangesWithSource(5, 7, 5, 7, 33, 44);
 		for (IntTuple t : mr) {
 			System.out.printf("%d:[%d..%d)  ", t.at(0), t.at(1), t.at(1) + t.at(2));
 		}
diff -r 19f5167c2155 -r 58a6900f845d src/org/tmatesoft/hg/internal/DiffHelper.java
--- a/src/org/tmatesoft/hg/internal/DiffHelper.java	Sat Jul 20 17:40:52 2013 +0200
+++ b/src/org/tmatesoft/hg/internal/DiffHelper.java	Sun Jul 21 17:15:34 2013 +0200
@@ -83,6 +83,50 @@
 		insp.end();
 	}
 	
+	/** 
+	 * look up every line in s2 that match lines in s1
+	 * idea: pure additions in s2 are diff-ed against s1 again and again, to see if there are any matches
+	 */
+	void findAllMatchAlternatives(final MatchInspector<T> insp) {
+		assert seq1.chunkCount() > 0;
+		final IntSliceSeq insertions = new IntSliceSeq(2);
+		final boolean matchedAny[] = new boolean[] {false};
+		DeltaInspector<T> myInsp = new DeltaInspector<T>() {
+			@Override
+			protected void unchanged(int s1From, int s2From, int length) {
+				matchedAny[0] = true;
+				insp.match(s1From, s2From, length);
+			}
+			@Override
+			protected void added(int s1InsertPoint, int s2From, int s2To) {
+				insertions.add(s2From, s2To);
+			}
+		};
+		matchInspector = myInsp;
+		myInsp.begin(seq1, seq2);
+		IntSliceSeq s2RangesToCheck = new IntSliceSeq(2, 1, 0);
+		s2RangesToCheck.add(0, seq2.chunkCount());
+		do {
+			IntSliceSeq nextCheck = new IntSliceSeq(2);
+			for (IntTuple t : s2RangesToCheck) {
+				int s2Start = t.at(0);
+				int s2End = t.at(1);
+				myInsp.changeStartS1 = 0;
+				myInsp.changeStartS2 = s2Start;
+				insp.begin(seq1, seq2);
+				matchedAny[0] = false;
+				findMatchingBlocks(0, seq1.chunkCount(), s2Start, s2End);
+				insp.end();
+				myInsp.end();
+				if (matchedAny[0]) {
+					nextCheck.addAll(insertions);
+				}
+				insertions.clear();
+			}
+			s2RangesToCheck = nextCheck;
+		} while (s2RangesToCheck.size() > 0);
+	}
+	
 	/**
 	 * implementation based on Python's difflib.py and SequenceMatcher 
 	 */
diff -r 19f5167c2155 -r 58a6900f845d src/org/tmatesoft/hg/internal/ForwardAnnotateInspector.java
--- a/src/org/tmatesoft/hg/internal/ForwardAnnotateInspector.java	Sat Jul 20 17:40:52 2013 +0200
+++ b/src/org/tmatesoft/hg/internal/ForwardAnnotateInspector.java	Sun Jul 21 17:15:34 2013 +0200
@@ -17,14 +17,9 @@
 package org.tmatesoft.hg.internal;
 
 import org.tmatesoft.hg.core.HgAnnotateCommand.Inspector;
-import org.tmatesoft.hg.core.HgAnnotateCommand.LineInfo;
 import org.tmatesoft.hg.core.HgBlameInspector;
 import org.tmatesoft.hg.core.HgCallbackTargetException;
-import org.tmatesoft.hg.core.HgDiffCommand;
-import org.tmatesoft.hg.core.HgException;
 import org.tmatesoft.hg.core.HgIterateDirection;
-import org.tmatesoft.hg.repo.HgLookup;
-import org.tmatesoft.hg.repo.HgRepository;
 import org.tmatesoft.hg.util.CancelSupport;
 import org.tmatesoft.hg.util.CancelledException;
 import org.tmatesoft.hg.util.ProgressSupport;
@@ -141,24 +136,4 @@
 			originPos += originBlockLen;
 		}
 	}
-
-
-	public static void main(String[] args) throws HgCallbackTargetException, CancelledException, HgException {
-		HgRepository repo = new HgLookup().detect("/home/artem/hg/junit-test-repos/test-annotate/");
-		HgDiffCommand cmd = new HgDiffCommand(repo);
-		cmd.file(repo.getFileNode("file1")).order(HgIterateDirection.OldToNew);
-		final int cset = 8;
-		cmd.range(0, cset);
-		final ForwardAnnotateInspector c2 = new ForwardAnnotateInspector();
-		cmd.executeAnnotate(c2);
-		for (IntTuple t : c2.all.get(cset)) {
-			System.out.printf("Block %d lines from revision %d (starts with line %d in the origin)\n", t.at(0), t.at(1), 1+t.at(2));
-		}
-		c2.report(cset, new Inspector() {
-			
-			public void next(LineInfo lineInfo) throws HgCallbackTargetException {
-				System.out.printf("%3d:%3d: %s", lineInfo.getChangesetIndex(), lineInfo.getOriginLineNumber(), new String(lineInfo.getContent()));
-			}
-		}, ProgressSupport.Factory.get(null), CancelSupport.Factory.get(null));
-	}
 }
\ No newline at end of file
diff -r 19f5167c2155 -r 58a6900f845d src/org/tmatesoft/hg/internal/IntSliceSeq.java
--- a/src/org/tmatesoft/hg/internal/IntSliceSeq.java	Sat Jul 20 17:40:52 2013 +0200
+++ b/src/org/tmatesoft/hg/internal/IntSliceSeq.java	Sun Jul 21 17:15:34 2013 +0200
@@ -24,7 +24,7 @@
  * @author Artem Tikhomirov
  * @author TMate Software Ltd.
  */
-public final class IntSliceSeq implements Iterable<IntTuple> {
+public final class IntSliceSeq implements Iterable<IntTuple>, Cloneable {
 	private final IntVector slices;
 	private final int slice;
 
@@ -39,13 +39,13 @@
 	}
 	
 	public IntSliceSeq add(int... values) {
-		checkValues(values);
+		checkValuesAny(values);
 		slices.add(values);
 		return this;
 	}
 	
 	public IntSliceSeq set(int sliceIndex, int... values) {
-		checkValues(values);
+		checkValuesExact(values);
 		for (int i = 0, j = sliceIndex*slice; i < slice; i++,j++) {
 			slices.set(j, values[i]);
 		}
@@ -63,6 +63,13 @@
 		return slices.get(sliceIndex*slice + valueIndex);
 	}
 	
+	public void addAll(IntSliceSeq other) {
+		if (other.slice != this.slice) {
+			throw new IllegalArgumentException(String.format("Tuple size doesn't match: %d and %d", slice, other.slice));
+		}
+		slices.addAll(other.slices);
+	}
+	
 	public int size() {
 		return slices.size() / slice;
 	}
@@ -117,6 +124,15 @@
 		}
 		return sb.toString();
 	}
+	
+	@Override
+	public IntSliceSeq clone() {
+		try {
+			return (IntSliceSeq) super.clone();
+		} catch (CloneNotSupportedException ex) {
+			throw new Error(ex);
+		}
+	}
 
 	private void checkArgRange(int rangeSize, int index) {
 		if (index >= 0 && index < rangeSize) {
@@ -124,9 +140,14 @@
 		}
 		throw new IllegalArgumentException(String.valueOf(index));
 	}
-	private void checkValues(int[] values) {
+	private void checkValuesExact(int[] values) {
 		if (values == null || values.length != slice) {
 			throw new IllegalArgumentException(String.valueOf(values == null ? values : values.length));
 		}
 	}
+	private void checkValuesAny(int[] values) {
+		if (values == null || values.length % slice != 0) {
+			throw new IllegalArgumentException(String.valueOf(values == null ? values : values.length));
+		}
+	}
 }
diff -r 19f5167c2155 -r 58a6900f845d src/org/tmatesoft/hg/internal/IntVector.java
--- a/src/org/tmatesoft/hg/internal/IntVector.java	Sat Jul 20 17:40:52 2013 +0200
+++ b/src/org/tmatesoft/hg/internal/IntVector.java	Sun Jul 21 17:15:34 2013 +0200
@@ -24,7 +24,7 @@
  * @author Artem Tikhomirov
  * @author TMate Software Ltd.
  */
-public class IntVector {
+public class IntVector implements Cloneable {
 	
 	private int[] data;
 	private final int increment;
@@ -57,7 +57,17 @@
 			data[count++] = v;
 		}
 	}
-	
+
+	public void addAll(IntVector other) {
+		final int otherLen = other.count;
+		if (count + otherLen > data.length) {
+			grow(count + otherLen);
+		}
+		for (int i = 0; i < otherLen; i++) {
+			data[count++] = other.data[i];
+		}
+	}
+
 	public int get(int i) {
 		if (i < 0 || i >= count) {
 			throw new IndexOutOfBoundsException(String.format("Index: %d, size: %d", i, count));
@@ -126,6 +136,15 @@
 	public String toString() {
 		return String.format("%s[%d]", IntVector.class.getSimpleName(), size());
 	}
+	
+	@Override
+	public IntVector clone() {
+		try {
+			return (IntVector) super.clone();
+		} catch (CloneNotSupportedException ex) {
+			throw new Error(ex);
+		}
+	}
 
 	/**
 	 * Use only when this instance won't be used any longer
diff -r 19f5167c2155 -r 58a6900f845d src/org/tmatesoft/hg/internal/diff/DiffRangeMap.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/org/tmatesoft/hg/internal/diff/DiffRangeMap.java	Sun Jul 21 17:15:34 2013 +0200
@@ -0,0 +1,138 @@
+/*
+ * 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.diff;
+
+import java.util.ArrayList;
+
+import org.tmatesoft.hg.internal.DiffHelper;
+import org.tmatesoft.hg.internal.IntSliceSeq;
+import org.tmatesoft.hg.internal.IntTuple;
+import org.tmatesoft.hg.internal.DiffHelper.ChunkSequence;
+
+/**
+ * Sequence of pairs of ranges (s1Start,s1End) - (s2Start, s2End)
+ * @author Artem Tikhomirov
+ * @author TMate Software Ltd.
+ */
+public class DiffRangeMap extends DiffHelper.DeltaInspector<ChunkSequence<?>> {
+	private final IntSliceSeq ranges;
+	
+	public DiffRangeMap() {
+		ranges = new IntSliceSeq(5);
+	}
+	
+	/**
+	 * handy method to fill this map from supplied DiffHelper
+	 * <pre>
+	 *   DiffHelper<LineSequence> pg = ...
+	 *   pg.findMatchingBlocks(p1ToBase); // doesn't compile
+	 *   DiffHelper<?> dh = pg;
+	 *   dh.findMatchingBlocks(p1ToBase); // compiles ok!
+	 * </pre>
+	 */
+	public DiffRangeMap fill(DiffHelper<?> dh) {
+		dh.findMatchingBlocks(this);
+		return this;
+	}
+	
+	@Override
+	protected void added(int s1InsertPoint, int s2From, int s2To) {
+		ranges.add(s1InsertPoint, s1InsertPoint, s2From, s2To, (int)'+');
+	}
+	@Override
+	protected void changed(int s1From, int s1To, int s2From, int s2To) {
+		ranges.add(s1From, s1To, s2From, s2To, (int)'*');
+	}
+	@Override
+	protected void deleted(int s2DeletePoint, int s1From, int s1To) {
+		ranges.add(s1From, s1To, s2DeletePoint, s2DeletePoint, (int)'-');
+	}
+	@Override
+	protected void unchanged(int s1From, int s2From, int length) {
+		ranges.add(s1From, s1From + length, s2From, s2From + length, (int)'=');
+	}
+
+	public Iterable<RangePair> findInSource(int sourceStart, int sourceEnd) {
+		ArrayList<RangePair> rv = new ArrayList<RangePair>(4); 
+		for (IntTuple t : ranges) {
+			int srcRangeStart = t.at(0);
+			int srcRangeEnd = t.at(1);
+			if (srcRangeEnd <= sourceStart) { // srcRangeEnd exclusive
+				continue;
+			}
+			if (srcRangeStart >= sourceEnd) {
+				break;
+			}
+			rv.add(new RangePair(srcRangeStart, srcRangeEnd, t.at(2), t.at(3)));
+		}
+		return rv;
+	}
+	
+	public Iterable<RangePair> insertions() {
+		return rangesOfKind('+');
+	}
+
+	public Iterable<RangePair> same() {
+		return rangesOfKind('=');
+	}
+
+	private Iterable<RangePair> rangesOfKind(int kind) {
+		ArrayList<RangePair> rv = new ArrayList<RangePair>(4); 
+		for (IntTuple t : ranges) {
+			if (t.at(4) == kind) {
+				rv.add(new RangePair(t.at(0), t.at(1), t.at(2), t.at(3)));
+			}
+		}
+		return rv;
+	}
+	
+	public static final class RangePair {
+		private final int s1Start;
+		private final int s1End;
+		private final int s2Start;
+		private final int s2End;
+
+		public RangePair(int s1Start, int s1End, int s2Start, int s2End) {
+			this.s1Start = s1Start;
+			this.s1End = s1End;
+			this.s2Start = s2Start;
+			this.s2End = s2End;
+		}
+		public int start1() {
+			return s1Start;
+		}
+		public int end1() {
+			return s1End;
+		}
+		public int length1() {
+			return s1End - s1Start;
+		}
+		public int start2() {
+			return s2Start;
+		}
+		public int end2() {
+			return s2End;
+		}
+		public int length2() {
+			return s2End - s2Start;
+		}
+		@Override
+		public String toString() {
+			return String.format("[%d..%d)->[%d..%d)", s1Start, s1End, s2Start, s2End);
+		}
+	}
+}
diff -r 19f5167c2155 -r 58a6900f845d test-data/test-repos.jar
Binary file test-data/test-repos.jar has changed
diff -r 19f5167c2155 -r 58a6900f845d test/org/tmatesoft/hg/test/TestBlame.java
--- a/test/org/tmatesoft/hg/test/TestBlame.java	Sat Jul 20 17:40:52 2013 +0200
+++ b/test/org/tmatesoft/hg/test/TestBlame.java	Sun Jul 21 17:15:34 2013 +0200
@@ -262,24 +262,6 @@
 		doAnnotateLineCheck(changeset, ar, ai);
 	}
 	
-	private void doAnnotateLineCheck(int cs, AnnotateRunner ar, AnnotateInspector hg4jResult) {
-		String[] hgAnnotateLines = ar.getLines();
-		assertTrue("[sanity]", hgAnnotateLines.length > 0);
-		assertEquals("Number of lines reported by native annotate and our impl", hgAnnotateLines.length, hg4jResult.getLineCount());
-
-		for (int i = 0; i < hgAnnotateLines.length; i++) {
-			String[] hgLine = hgAnnotateLines[i].split(":");
-			assertTrue(hgAnnotateLines[i], hgLine.length >= 3);
-			int hgAnnotateRevIndex = Integer.parseInt(hgLine[0].trim());
-			int hgFirstAppLine = Integer.parseInt(hgLine[1].trim());
-			String hgLineText = hgAnnotateLines[i].substring(hgLine[0].length() + hgLine[1].length() + 2).trim(); 
-			errorCollector.assertEquals(String.format("Revision mismatch for line %d (annotating rev: %d)", i+1, cs), hgAnnotateRevIndex, hg4jResult.getChangeset(i));
-			errorCollector.assertEquals(hgLineText, hg4jResult.getLine(i).trim());
-			errorCollector.assertEquals(hgFirstAppLine, hg4jResult.getOriginLine(i));
-		}
-	}
-	
-	
 	@Test
 	public void testDiffTwoRevisions() throws Exception {
 		HgRepository repo = Configuration.get().find("test-annotate");
@@ -319,6 +301,32 @@
 		String[] expected = splitLines(gp.result());
 		Assert.assertArrayEquals(expected, apiResult);
 	}
+	
+	@Test
+	public void testAnnotateMergeMapViaBase() throws Exception {
+		HgRepository repo = Configuration.get().find("test-annotate3");
+		HgDataFile df1 = repo.getFileNode("file1");
+		HgDataFile df4 = repo.getFileNode("file4");
+		HgDataFile df5 = repo.getFileNode("file5");
+		assertTrue("[sanity]", df1.exists() && df4.exists());
+		// hg annotate handles merge in its own way, here we check 
+		// how map(diff(p1->base->p2)) merge strategy works
+		final String file1AnnotateResult = "3:1:1\n3:2:2x\n3:3:3y\n2:4:z\n0:1:1\n1:2:2x\n4:3:3y\n";
+		final String file4AnnotateResult = "3:1:1\n1:2:2x\n4:3:3y\n2:4:z\n0:1:1\n3:6:2x\n3:7:3y\n";
+		final String file5AnnotateResult = "0:1:1\n1:2:2x\n4:3:3y\n2:4:z\n5:5:1\n5:6:2x\n5:7:3y\n";
+		HgAnnotateCommand cmd = new HgAnnotateCommand(repo);
+		cmd.changeset(5);
+		AnnotateInspector insp = new AnnotateInspector();
+		// file1
+		cmd.file(df1, false).execute(insp);
+		doAnnotateLineCheck(5, splitLines(file1AnnotateResult), insp);
+		// file4
+		cmd.file(df4, false).execute(insp = new AnnotateInspector());
+		doAnnotateLineCheck(5, splitLines(file4AnnotateResult), insp);
+		// file5
+		cmd.file(df5, false).execute(insp = new AnnotateInspector());
+		doAnnotateLineCheck(5, splitLines(file5AnnotateResult), insp);
+}
 
 	// TODO HgWorkingCopyStatusCollector (and HgStatusCollector), with their ancestors (rev 59/69) have examples
 	// of *incorrect* assignment of common lines (like "}") - our impl doesn't process common lines in any special way
@@ -349,6 +357,25 @@
 		return rv;
 	}
 	
+	private void doAnnotateLineCheck(int cs, AnnotateRunner ar, AnnotateInspector hg4jResult) {
+		String[] hgAnnotateLines = ar.getLines();
+		assertTrue("[sanity]", hgAnnotateLines.length > 0);
+		assertEquals("Number of lines reported by native annotate and our impl", hgAnnotateLines.length, hg4jResult.getLineCount());
+		doAnnotateLineCheck(cs, hgAnnotateLines, hg4jResult);
+	}
+
+	private void doAnnotateLineCheck(int cs, String[] expectedAnnotateLines, AnnotateInspector hg4jResult) { 
+		for (int i = 0; i < expectedAnnotateLines.length; i++) {
+			String[] hgLine = expectedAnnotateLines[i].split(":");
+			assertTrue(expectedAnnotateLines[i], hgLine.length >= 3);
+			int hgAnnotateRevIndex = Integer.parseInt(hgLine[0].trim());
+			int hgFirstAppLine = Integer.parseInt(hgLine[1].trim());
+			String hgLineText = expectedAnnotateLines[i].substring(hgLine[0].length() + hgLine[1].length() + 2).trim(); 
+			errorCollector.assertEquals(String.format("Revision mismatch for line %d (annotating rev: %d)", i+1, cs), hgAnnotateRevIndex, hg4jResult.getChangeset(i));
+			errorCollector.assertEquals("Line text", hgLineText, hg4jResult.getLine(i).trim());
+			errorCollector.assertEquals("Line in origin", hgFirstAppLine, hg4jResult.getOriginLine(i));
+		}
+	}
 	
 	private void ccc() throws Throwable {
 		HgRepository repo = new HgLookup().detect("/home/artem/hg/hgtest-annotate-merge/");