tikhomirov@569: /*
tikhomirov@569:  * Copyright (c) 2013 TMate Software Ltd
tikhomirov@569:  *  
tikhomirov@569:  * This program is free software; you can redistribute it and/or modify
tikhomirov@569:  * it under the terms of the GNU General Public License as published by
tikhomirov@569:  * the Free Software Foundation; version 2 of the License.
tikhomirov@569:  *
tikhomirov@569:  * This program is distributed in the hope that it will be useful,
tikhomirov@569:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
tikhomirov@569:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
tikhomirov@569:  * GNU General Public License for more details.
tikhomirov@569:  *
tikhomirov@569:  * For information on how to redistribute this software under
tikhomirov@569:  * the terms of a license other than GNU General Public License
tikhomirov@569:  * contact TMate Software at support@hg4j.com
tikhomirov@569:  */
tikhomirov@569: package org.tmatesoft.hg.internal;
tikhomirov@569: 
tikhomirov@625: import static org.tmatesoft.hg.core.HgIterateDirection.OldToNew;
tikhomirov@569: import static org.tmatesoft.hg.repo.HgRepository.NO_REVISION;
tikhomirov@569: 
tikhomirov@674: import java.util.Iterator;
tikhomirov@569: import java.util.LinkedList;
tikhomirov@569: import java.util.ListIterator;
tikhomirov@569: 
tikhomirov@569: import org.tmatesoft.hg.core.HgCallbackTargetException;
tikhomirov@569: import org.tmatesoft.hg.internal.DiffHelper.LineSequence;
tikhomirov@569: import org.tmatesoft.hg.internal.DiffHelper.LineSequence.ByteChain;
tikhomirov@629: import org.tmatesoft.hg.core.HgBlameInspector;
tikhomirov@629: import org.tmatesoft.hg.core.HgBlameInspector.*;
tikhomirov@569: import org.tmatesoft.hg.repo.HgDataFile;
tikhomirov@569: import org.tmatesoft.hg.repo.HgInvalidStateException;
tikhomirov@628: import org.tmatesoft.hg.repo.HgRuntimeException;
tikhomirov@569: import org.tmatesoft.hg.util.Adaptable;
tikhomirov@569: import org.tmatesoft.hg.util.CancelledException;
tikhomirov@569: import org.tmatesoft.hg.util.Pair;
tikhomirov@569: 
tikhomirov@569: /**
tikhomirov@569:  * Blame implementation
tikhomirov@603:  * @see HgBlameInspector
tikhomirov@569:  * @author Artem Tikhomirov
tikhomirov@569:  * @author TMate Software Ltd.
tikhomirov@569:  */
tikhomirov@569: public class BlameHelper {
tikhomirov@569: 	
tikhomirov@603: 	private final HgBlameInspector insp;
tikhomirov@569: 	private FileLinesCache linesCache;
tikhomirov@569: 
tikhomirov@625: 	public BlameHelper(HgBlameInspector inspector) {
tikhomirov@569: 		insp = inspector;
tikhomirov@569: 	}
tikhomirov@625: 
tikhomirov@625: 	/**
tikhomirov@625: 	 * Build history of the file for the specified range (follow renames if necessary). This history
tikhomirov@625: 	 * is used to access various file revision data during subsequent {@link #diff(int, int, int, int)} and
tikhomirov@625: 	 * {@link #annotateChange(int, int, int[], int[])} calls. Callers can use returned history for own approaches 
tikhomirov@625: 	 * to iteration over file history.
tikhomirov@625: 
tikhomirov@625: 	 * <p>NOTE, clogRevIndexEnd has to list name of the supplied file in the corresponding manifest,
tikhomirov@625: 	 * as it's not possible to trace rename history otherwise.
tikhomirov@625: 	 */
tikhomirov@628: 	public FileHistory prepare(HgDataFile df, int clogRevIndexStart, int clogRevIndexEnd) throws HgRuntimeException {
tikhomirov@625: 		assert clogRevIndexStart <= clogRevIndexEnd;
tikhomirov@625: 		FileHistory fileHistory = new FileHistory(df, clogRevIndexStart, clogRevIndexEnd);
tikhomirov@625: 		fileHistory.build();
tikhomirov@625: 		int cacheHint = 5; // cache comes useful when we follow merge branches and don't want to
tikhomirov@625: 		// parse base revision twice. There's no easy way to determine max(distance(all(base,merge))),
tikhomirov@625: 		// hence the heuristics to use the longest history chunk:
tikhomirov@625: 		for (FileRevisionHistoryChunk c : fileHistory.iterate(OldToNew)) {
tikhomirov@625: 			// iteration order is not important here
tikhomirov@625: 			if (c.revisionCount() > cacheHint) {
tikhomirov@625: 				cacheHint = c.revisionCount();
tikhomirov@625: 			}
tikhomirov@625: 		}
tikhomirov@625: 		linesCache = new FileLinesCache(cacheHint);
tikhomirov@625: 		for (FileRevisionHistoryChunk fhc : fileHistory.iterate(OldToNew)) {
tikhomirov@625: 			// iteration order is not important here
tikhomirov@625: 			linesCache.useFileUpTo(fhc.getFile(), fhc.getEndChangeset());
tikhomirov@625: 		}
tikhomirov@625: 		return fileHistory;
tikhomirov@569: 	}
tikhomirov@569: 	
tikhomirov@569: 	// NO_REVISION is not allowed as any argument
tikhomirov@628: 	public void diff(int fileRevIndex1, int clogRevIndex1, int fileRevIndex2, int clogRevIndex2) throws HgCallbackTargetException, HgRuntimeException {
tikhomirov@569: 		HgDataFile targetFile = linesCache.getFile(clogRevIndex2);
tikhomirov@569: 		LineSequence c1 = linesCache.lines(clogRevIndex1, fileRevIndex1);
tikhomirov@569: 		LineSequence c2 = linesCache.lines(clogRevIndex2, fileRevIndex2);
tikhomirov@569: 		DiffHelper<LineSequence> pg = new DiffHelper<LineSequence>();
tikhomirov@569: 		pg.init(c1, c2);
tikhomirov@569: 		BlameBlockInspector bbi = new BlameBlockInspector(targetFile, fileRevIndex2, insp, clogRevIndex1, clogRevIndex2);
tikhomirov@569: 		pg.findMatchingBlocks(bbi);
tikhomirov@569: 		bbi.checkErrors();
tikhomirov@569: 	}
tikhomirov@569: 
tikhomirov@628: 	public void annotateChange(int fileRevIndex, int csetRevIndex, int[] fileParentRevs, int[] fileParentClogRevs) throws HgCallbackTargetException, HgRuntimeException {
tikhomirov@569: 		HgDataFile targetFile = linesCache.getFile(csetRevIndex);
tikhomirov@569: 		final LineSequence fileRevLines = linesCache.lines(csetRevIndex, fileRevIndex);
tikhomirov@569: 		if (fileParentClogRevs[0] != NO_REVISION && fileParentClogRevs[1] != NO_REVISION) {
tikhomirov@569: 			int p1ClogIndex = fileParentClogRevs[0];
tikhomirov@569: 			int p2ClogIndex = fileParentClogRevs[1];
tikhomirov@569: 			LineSequence p1Lines = linesCache.lines(p1ClogIndex, fileParentRevs[0]);
tikhomirov@569: 			LineSequence p2Lines = linesCache.lines(p2ClogIndex, fileParentRevs[1]);
tikhomirov@569: 			DiffHelper<LineSequence> pg = new DiffHelper<LineSequence>();
tikhomirov@569: 			pg.init(p2Lines, fileRevLines);
tikhomirov@569: 			EqualBlocksCollector p2MergeCommon = new EqualBlocksCollector();
tikhomirov@569: 			pg.findMatchingBlocks(p2MergeCommon);
tikhomirov@569: 			//
tikhomirov@569: 			pg.init(p1Lines);
tikhomirov@569: 			BlameBlockInspector bbi = new BlameBlockInspector(targetFile, fileRevIndex, insp, p1ClogIndex, csetRevIndex);
tikhomirov@678: 			bbi.setMergeParent2(new MergeStrategy1(p2MergeCommon.matches), p2ClogIndex);
tikhomirov@569: 			pg.findMatchingBlocks(bbi);
tikhomirov@569: 			bbi.checkErrors();
tikhomirov@569: 		} else if (fileParentClogRevs[0] == fileParentClogRevs[1]) {
tikhomirov@569: 			// may be equal iff both are unset
tikhomirov@569: 			assert fileParentClogRevs[0] == NO_REVISION;
tikhomirov@569: 			// everything added
tikhomirov@569: 			BlameBlockInspector bbi = new BlameBlockInspector(targetFile, fileRevIndex, insp, NO_REVISION, csetRevIndex);
tikhomirov@569: 			bbi.begin(LineSequence.newlines(new byte[0]), fileRevLines);
tikhomirov@569: 			bbi.match(0, fileRevLines.chunkCount()-1, 0);
tikhomirov@569: 			bbi.end();
tikhomirov@569: 			bbi.checkErrors();
tikhomirov@569: 		} else {
tikhomirov@569: 			int soleParentIndex = fileParentClogRevs[0] == NO_REVISION ? 1 : 0;
tikhomirov@569: 			assert fileParentClogRevs[soleParentIndex] != NO_REVISION;
tikhomirov@569: 			LineSequence parentLines = linesCache.lines(fileParentClogRevs[soleParentIndex], fileParentRevs[soleParentIndex]);
tikhomirov@569: 			
tikhomirov@569: 			DiffHelper<LineSequence> pg = new DiffHelper<LineSequence>();
tikhomirov@569: 			pg.init(parentLines, fileRevLines);
tikhomirov@569: 			BlameBlockInspector bbi = new BlameBlockInspector(targetFile, fileRevIndex, insp, fileParentClogRevs[soleParentIndex], csetRevIndex);
tikhomirov@569: 			pg.findMatchingBlocks(bbi);
tikhomirov@569: 			bbi.checkErrors();
tikhomirov@569: 		}
tikhomirov@569: 	}
tikhomirov@569: 	
tikhomirov@569: 	private static class FileLinesCache {
tikhomirov@569: 		private final LinkedList<Pair<Integer, LineSequence>> lruCache;
tikhomirov@569: 		private final int limit;
tikhomirov@569: 		private final LinkedList<Pair<Integer, HgDataFile>> files; // TODO in fact, need sparse array 
tikhomirov@569: 
tikhomirov@625: 		/**
tikhomirov@625: 		 * @param lruLimit how many parsed file revisions to keep
tikhomirov@625: 		 */
tikhomirov@569: 		public FileLinesCache(int lruLimit) {
tikhomirov@569: 			limit = lruLimit;
tikhomirov@569: 			lruCache = new LinkedList<Pair<Integer, LineSequence>>();
tikhomirov@569: 			files = new LinkedList<Pair<Integer,HgDataFile>>();
tikhomirov@569: 		}
tikhomirov@569: 		
tikhomirov@569: 		public void useFileUpTo(HgDataFile df, int clogRevIndex) {
tikhomirov@569: 			Pair<Integer, HgDataFile> newEntry = new Pair<Integer, HgDataFile>(clogRevIndex, df);
tikhomirov@569: 			for (ListIterator<Pair<Integer, HgDataFile>> it = files.listIterator(); it.hasNext();) {
tikhomirov@569: 				Pair<Integer, HgDataFile> e = it.next();
tikhomirov@569: 				if (e.first() == clogRevIndex) {
tikhomirov@569: 					assert e.second().getPath().equals(df.getPath());
tikhomirov@569: 					return;
tikhomirov@569: 				}
tikhomirov@569: 				if (e.first() > clogRevIndex) {
tikhomirov@569: 					// insert new entry before current
tikhomirov@569: 					it.previous();
tikhomirov@569: 					it.add(newEntry);
tikhomirov@569: 					return;
tikhomirov@569: 				}
tikhomirov@569: 			}
tikhomirov@569: 			files.add(newEntry);
tikhomirov@569: 		}
tikhomirov@569: 		
tikhomirov@569: 		public HgDataFile getFile(int clogRevIndex) {
tikhomirov@569: 			for (Pair<Integer, HgDataFile> e : files) {
tikhomirov@569: 				if (e.first() >= clogRevIndex) {
tikhomirov@569: 					return e.second();
tikhomirov@569: 				}
tikhomirov@569: 			}
tikhomirov@569: 			throw new HgInvalidStateException(String.format("Got %d file-changelog mappings, but no luck for revision %d.", files.size(), clogRevIndex));
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@628: 		public LineSequence lines(int clogRevIndex, int fileRevIndex) throws HgRuntimeException {
tikhomirov@569: 			Pair<Integer, LineSequence> cached = checkCache(clogRevIndex);
tikhomirov@569: 			if (cached != null) {
tikhomirov@569: 				return cached.second();
tikhomirov@569: 			}
tikhomirov@569: 			HgDataFile df = getFile(clogRevIndex);
tikhomirov@569: 			try {
tikhomirov@569: 				ByteArrayChannel c;
tikhomirov@569: 				df.content(fileRevIndex, c = new ByteArrayChannel());
tikhomirov@569: 				LineSequence rv = LineSequence.newlines(c.toArray());
tikhomirov@569: 				lruCache.addFirst(new Pair<Integer, LineSequence>(clogRevIndex, rv));
tikhomirov@569: 				if (lruCache.size() > limit) {
tikhomirov@569: 					lruCache.removeLast();
tikhomirov@569: 				}
tikhomirov@569: 				return rv;
tikhomirov@569: 			} catch (CancelledException ex) {
tikhomirov@569: 				// TODO likely it was bad idea to throw cancelled exception from content()
tikhomirov@569: 				// deprecate and provide alternative?
tikhomirov@569: 				HgInvalidStateException ise = new HgInvalidStateException("ByteArrayChannel never throws CancelledException");
tikhomirov@569: 				ise.initCause(ex);
tikhomirov@569: 				throw ise;
tikhomirov@569: 			}
tikhomirov@569: 		}
tikhomirov@569: 		
tikhomirov@569: 		private Pair<Integer,LineSequence> checkCache(int fileRevIndex) {
tikhomirov@569: 			Pair<Integer, LineSequence> rv = null;
tikhomirov@569: 			for (ListIterator<Pair<Integer, LineSequence>> it = lruCache.listIterator(); it.hasNext(); ) {
tikhomirov@569: 				Pair<Integer, LineSequence> p = it.next();
tikhomirov@569: 				if (p.first() == fileRevIndex) {
tikhomirov@569: 					rv = p;
tikhomirov@569: 					it.remove();
tikhomirov@569: 					break;
tikhomirov@569: 				}
tikhomirov@569: 			}
tikhomirov@569: 			if (rv != null) {
tikhomirov@569: 				lruCache.addFirst(rv);
tikhomirov@569: 			}
tikhomirov@569: 			return rv;
tikhomirov@569: 		}
tikhomirov@569: 	}
tikhomirov@569: 
tikhomirov@569: 	private static class BlameBlockInspector extends DiffHelper.DeltaInspector<LineSequence> {
tikhomirov@603: 		private final HgBlameInspector insp;
tikhomirov@569: 		private final int csetOrigin;
tikhomirov@569: 		private final int csetTarget;
tikhomirov@678: 		private MergeResolutionStrategy p2MergeCommon;
tikhomirov@569: 		private int csetMergeParent;
tikhomirov@569: 		private final AnnotateRev annotatedRevision;
tikhomirov@569: 		private HgCallbackTargetException error;
tikhomirov@569: 
tikhomirov@603: 		public BlameBlockInspector(HgDataFile df, int fileRevIndex, HgBlameInspector inspector, int originCset, int targetCset) {
tikhomirov@569: 			assert inspector != null;
tikhomirov@569: 			insp = inspector;
tikhomirov@569: 			annotatedRevision = new AnnotateRev();
tikhomirov@569: 			annotatedRevision.set(df, fileRevIndex);
tikhomirov@569: 			csetOrigin = originCset;
tikhomirov@569: 			csetTarget = targetCset;
tikhomirov@569: 		}
tikhomirov@569: 		
tikhomirov@678: 		public void setMergeParent2(MergeResolutionStrategy p2MergeStrategy, int parentCset2) {
tikhomirov@678: 			p2MergeCommon = p2MergeStrategy;
tikhomirov@569: 			csetMergeParent = parentCset2;
tikhomirov@569: 		}
tikhomirov@569: 		
tikhomirov@569: 		@Override
tikhomirov@569: 		public void begin(LineSequence s1, LineSequence s2) {
tikhomirov@569: 			super.begin(s1, s2);
tikhomirov@569: 			if (shallStop()) {
tikhomirov@569: 				return;
tikhomirov@569: 			}
tikhomirov@569: 			ContentBlock originContent = new ContentBlock(s1);
tikhomirov@569: 			ContentBlock targetContent = new ContentBlock(s2);
tikhomirov@569: 			annotatedRevision.set(originContent, targetContent);
tikhomirov@569: 			annotatedRevision.set(csetOrigin, csetTarget, p2MergeCommon != null ? csetMergeParent : NO_REVISION);
tikhomirov@629: 			RevisionDescriptor.Recipient curious = Adaptable.Factory.getAdapter(insp, RevisionDescriptor.Recipient.class, null);
tikhomirov@569: 			if (curious != null) {
tikhomirov@569: 				try {
tikhomirov@569: 					curious.start(annotatedRevision);
tikhomirov@569: 				} catch (HgCallbackTargetException ex) {
tikhomirov@569: 					error = ex;
tikhomirov@569: 				}
tikhomirov@569: 			}
tikhomirov@569: 		}
tikhomirov@569: 		
tikhomirov@569: 		@Override
tikhomirov@569: 		public void end() {
tikhomirov@569: 			super.end();
tikhomirov@569: 			if (shallStop()) {
tikhomirov@569: 				return;
tikhomirov@569: 			}
tikhomirov@629: 			RevisionDescriptor.Recipient curious = Adaptable.Factory.getAdapter(insp, RevisionDescriptor.Recipient.class, null);
tikhomirov@569: 			if (curious != null) {
tikhomirov@569: 				try {
tikhomirov@569: 					curious.done(annotatedRevision);
tikhomirov@569: 				} catch (HgCallbackTargetException ex) {
tikhomirov@569: 					error = ex;
tikhomirov@569: 				}
tikhomirov@569: 			}
tikhomirov@569: 			p2MergeCommon = null;
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		@Override
tikhomirov@569: 		protected void changed(int s1From, int s1To, int s2From, int s2To) {
tikhomirov@569: 			if (shallStop()) {
tikhomirov@569: 				return;
tikhomirov@569: 			}
tikhomirov@569: 			try {
tikhomirov@569: 				if (p2MergeCommon != null) {
tikhomirov@678: 					IntSliceSeq mergeRanges = p2MergeCommon.combineAndMarkRangesWithSource(s2From, s2To - s2From, csetOrigin, csetMergeParent);
tikhomirov@569: 					
tikhomirov@569: 					/*
tikhomirov@569: 					 * Usecases, how it USED TO BE initially:
tikhomirov@569: 					 * 3 lines changed to 10 lines. range of 10 lines breaks down to 2 from p2, 3 from p1, and 5 from p2.
tikhomirov@569: 					 * We report: 2 lines changed to 2(p2), then 1 line changed with 3(p1) and 5 lines added from p2.
tikhomirov@569: 					 * 
tikhomirov@569: 					 * 10 lines changed to 3 lines, range of 3 lines breaks down to 2 line from p1 and 1 line from p2.
tikhomirov@569: 					 * We report: 2 lines changed to 2(p1) and 8 lines changed to 1(p2)
tikhomirov@569: 					 * 
tikhomirov@569: 					 * NOW, lines from p2 are always reported as pure add (since we need their insertion point to be in p2, not in p1)
tikhomirov@569: 					 * and we try to consume p1 changes as soon as we see first p1's range 
tikhomirov@569: 					 */
tikhomirov@569: 					int s1TotalLines = s1To - s1From, s1ConsumedLines = 0, s1Start = s1From;
tikhomirov@569: 					
tikhomirov@674: 					for (Iterator<IntTuple> it = mergeRanges.iterator(); it.hasNext();) {
tikhomirov@674: 						IntTuple mergeRange = it.next();
tikhomirov@674: 						final int rangeOrigin = mergeRange.at(0);
tikhomirov@674: 						final int rangeStart = mergeRange.at(1);
tikhomirov@674: 						final int rangeLen = mergeRange.at(2);
tikhomirov@674: 						final boolean lastRange = it.hasNext();
tikhomirov@569: 						final int s1LinesLeft = s1TotalLines - s1ConsumedLines;
tikhomirov@569: 						// how many lines we may report as changed (don't use more than in range unless it's the very last range)
tikhomirov@569: 						final int s1LinesToBorrow = lastRange ? s1LinesLeft : Math.min(s1LinesLeft, rangeLen);
tikhomirov@569: 						if (rangeOrigin != csetMergeParent && s1LinesToBorrow > 0) {
tikhomirov@569: 							ChangeBlockImpl block = getChangeBlock(s1Start, s1LinesToBorrow, rangeStart, rangeLen);
tikhomirov@569: 							block.setOriginAndTarget(rangeOrigin, csetTarget);
tikhomirov@569: 							insp.changed(block);
tikhomirov@569: 							s1ConsumedLines += s1LinesToBorrow;
tikhomirov@569: 							s1Start += s1LinesToBorrow;
tikhomirov@569: 						} else {
tikhomirov@678: 							int blockInsPoint = rangeOrigin != csetMergeParent ? s1Start : p2MergeCommon.getLineInP2(rangeStart);
tikhomirov@569: 							ChangeBlockImpl block = getAddBlock(rangeStart, rangeLen, blockInsPoint);
tikhomirov@569: 							block.setOriginAndTarget(rangeOrigin, csetTarget);
tikhomirov@569: 							insp.added(block);
tikhomirov@569: 						}
tikhomirov@569: 					}
tikhomirov@569: 					if (s1ConsumedLines != s1TotalLines) {
tikhomirov@569: 						assert s1ConsumedLines < s1TotalLines : String.format("Expected to process %d lines, but actually was %d", s1TotalLines, s1ConsumedLines);
tikhomirov@569: 						// either there were no ranges from p1, whole s2From..s2To range came from p2, shall report as deleted
tikhomirov@569: 						// or the ranges found were not enough to consume whole s2From..s2To
tikhomirov@569: 						// The "deletion point" is shifted to the end of last csetOrigin->csetTarget change
tikhomirov@569: 						int s2DeletePoint = s2From + s1ConsumedLines;
tikhomirov@569: 						ChangeBlockImpl block =  new ChangeBlockImpl(annotatedRevision.origin, null, s1Start, s1To - s1Start, -1, -1, -1, s2DeletePoint);
tikhomirov@569: 						block.setOriginAndTarget(csetOrigin, csetTarget);
tikhomirov@569: 						insp.deleted(block);
tikhomirov@569: 					}
tikhomirov@569: 				} else {
tikhomirov@569: 					ChangeBlockImpl block = getChangeBlock(s1From, s1To - s1From, s2From, s2To - s2From);
tikhomirov@569: 					block.setOriginAndTarget(csetOrigin, csetTarget);
tikhomirov@569: 					insp.changed(block);
tikhomirov@569: 				}
tikhomirov@569: 			} catch (HgCallbackTargetException ex) {
tikhomirov@569: 				error = ex;
tikhomirov@569: 			}
tikhomirov@569: 		}
tikhomirov@569: 		
tikhomirov@569: 		@Override
tikhomirov@569: 		protected void added(int s1InsertPoint, int s2From, int s2To) {
tikhomirov@569: 			if (shallStop()) {
tikhomirov@569: 				return;
tikhomirov@569: 			}
tikhomirov@569: 			try {
tikhomirov@569: 				if (p2MergeCommon != null) {
tikhomirov@678: 					IntSliceSeq mergeRanges = p2MergeCommon.combineAndMarkRangesWithSource(s2From, s2To - s2From, csetOrigin, csetMergeParent);
tikhomirov@569: 					int insPoint = s1InsertPoint; // track changes to insertion point
tikhomirov@674: 					for (IntTuple mergeRange : mergeRanges) {
tikhomirov@674: 						int rangeOrigin = mergeRange.at(0);
tikhomirov@674: 						int rangeStart = mergeRange.at(1);
tikhomirov@674: 						int rangeLen = mergeRange.at(2);
tikhomirov@678: 						// XXX likely need somewhat similar to the code above: 
tikhomirov@678: 						// int blockInsPoint = rangeOrigin != csetMergeParent ? s1Start : p2MergeCommon.reverseMapLine(rangeStart);
tikhomirov@678: 						//
tikhomirov@569: 						ChangeBlockImpl block = getAddBlock(rangeStart, rangeLen, insPoint);
tikhomirov@569: 						block.setOriginAndTarget(rangeOrigin, csetTarget);
tikhomirov@569: 						insp.added(block);
tikhomirov@569: 						// indicate insPoint moved down number of lines we just reported
tikhomirov@569: 						insPoint += rangeLen;
tikhomirov@569: 					}
tikhomirov@569: 				} else {
tikhomirov@569: 					ChangeBlockImpl block = getAddBlock(s2From, s2To - s2From, s1InsertPoint);
tikhomirov@569: 					block.setOriginAndTarget(csetOrigin, csetTarget);
tikhomirov@569: 					insp.added(block);
tikhomirov@569: 				}
tikhomirov@569: 			} catch (HgCallbackTargetException ex) {
tikhomirov@569: 				error = ex;
tikhomirov@569: 			}
tikhomirov@569: 		}
tikhomirov@569: 		
tikhomirov@569: 		@Override
tikhomirov@569: 		protected void deleted(int s2DeletePoint, int s1From, int s1To) {
tikhomirov@569: 			if (shallStop()) {
tikhomirov@569: 				return;
tikhomirov@569: 			}
tikhomirov@569: 			try {
tikhomirov@569: 				ChangeBlockImpl block = new ChangeBlockImpl(annotatedRevision.origin, null, s1From, s1To - s1From, -1, -1, -1, s2DeletePoint);
tikhomirov@569: 				block.setOriginAndTarget(csetOrigin, csetTarget);
tikhomirov@569: 				insp.deleted(block);
tikhomirov@569: 			} catch (HgCallbackTargetException ex) {
tikhomirov@569: 				error = ex;
tikhomirov@569: 			}
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		@Override
tikhomirov@569: 		protected void unchanged(int s1From, int s2From, int length) {
tikhomirov@569: 			if (shallStop()) {
tikhomirov@569: 				return;
tikhomirov@569: 			}
tikhomirov@569: 			try {
tikhomirov@569: 				EqualBlockImpl block = new EqualBlockImpl(s1From, s2From, length, annotatedRevision.target);
tikhomirov@569: 				block.setOriginAndTarget(csetOrigin, csetTarget);
tikhomirov@569: 				insp.same(block);
tikhomirov@569: 			} catch (HgCallbackTargetException ex) {
tikhomirov@569: 				error = ex;
tikhomirov@569: 			}
tikhomirov@569: 		}
tikhomirov@569: 		
tikhomirov@569: 		void checkErrors() throws HgCallbackTargetException {
tikhomirov@569: 			if (error != null) {
tikhomirov@569: 				throw error;
tikhomirov@569: 			}
tikhomirov@569: 		}
tikhomirov@569: 		
tikhomirov@569: 		private boolean shallStop() {
tikhomirov@569: 			return error != null;
tikhomirov@569: 		}
tikhomirov@569: 		
tikhomirov@569: 		private ChangeBlockImpl getAddBlock(int start, int len, int insPoint) {
tikhomirov@569: 			return new ChangeBlockImpl(null, annotatedRevision.target, -1, -1, start, len, insPoint, -1);
tikhomirov@569: 		}
tikhomirov@569: 		
tikhomirov@569: 		private ChangeBlockImpl getChangeBlock(int start1, int len1, int start2, int len2) {
tikhomirov@569: 			return new ChangeBlockImpl(annotatedRevision.origin, annotatedRevision.target, start1, len1, start2, len2, start1, start2);
tikhomirov@569: 		}
tikhomirov@569: 	}
tikhomirov@569: 	
tikhomirov@569: 	private static class BlockImpl implements Block {
tikhomirov@569: 		private int originCset;
tikhomirov@569: 		private int targetCset;
tikhomirov@569: 
tikhomirov@569: 		void setOriginAndTarget(int originChangesetIndex, int targetChangesetIndex) {
tikhomirov@569: 			// XXX perhaps, shall be part of Inspector API, rather than Block's
tikhomirov@569: 			// as they don't change between blocks (although the moment about merged revisions)
tikhomirov@569: 			// is not yet clear to me
tikhomirov@569: 			originCset = originChangesetIndex;
tikhomirov@569: 			targetCset = targetChangesetIndex;
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public int originChangesetIndex() {
tikhomirov@569: 			return originCset;
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public int targetChangesetIndex() {
tikhomirov@569: 			return targetCset;
tikhomirov@569: 		}
tikhomirov@569: 	}
tikhomirov@569: 
tikhomirov@569: 	private static class EqualBlockImpl extends BlockImpl implements EqualBlock {
tikhomirov@569: 		private final int start1, start2;
tikhomirov@569: 		private final int length;
tikhomirov@569: 		private final ContentBlock fullContent;
tikhomirov@569: 		private FilterBlock myContent;
tikhomirov@569: 		
tikhomirov@569: 		EqualBlockImpl(int blockStartSeq1, int blockStartSeq2, int blockLength, ContentBlock targetContent) {
tikhomirov@569: 			start1 = blockStartSeq1;
tikhomirov@569: 			start2 = blockStartSeq2;
tikhomirov@569: 			length = blockLength;
tikhomirov@569: 			fullContent = targetContent;
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public int originStart() {
tikhomirov@569: 			return start1;
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public int targetStart() {
tikhomirov@569: 			return start2;
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public int length() {
tikhomirov@569: 			return length;
tikhomirov@569: 		}
tikhomirov@569: 		
tikhomirov@569: 		public BlockData content() {
tikhomirov@569: 			if (myContent == null) {
tikhomirov@569: 				myContent = new FilterBlock(fullContent, start2, length);
tikhomirov@569: 			}
tikhomirov@569: 			return myContent;
tikhomirov@569: 		}
tikhomirov@569: 		
tikhomirov@569: 		@Override
tikhomirov@569: 		public String toString() {
tikhomirov@569: 			return String.format("@@ [%d..%d) == [%d..%d) @@", start1, start1+length, start2, start2+length);
tikhomirov@569: 		}
tikhomirov@569: 	}
tikhomirov@569: 	
tikhomirov@569: 	private static class ChangeBlockImpl extends BlockImpl implements ChangeBlock {
tikhomirov@569: 		private final ContentBlock oldContent;
tikhomirov@569: 		private final ContentBlock newContent;
tikhomirov@569: 		private final int s1Start;
tikhomirov@569: 		private final int s1Len;
tikhomirov@569: 		private final int s2Start;
tikhomirov@569: 		private final int s2Len;
tikhomirov@569: 		private final int s1InsertPoint;
tikhomirov@569: 		private final int s2DeletePoint;
tikhomirov@569: 		private FilterBlock addedBlock, removedBlock;
tikhomirov@569: 
tikhomirov@569: 		public ChangeBlockImpl(ContentBlock c1, ContentBlock c2, int s1Start, int s1Len, int s2Start, int s2Len, int s1InsertPoint, int s2DeletePoint) {
tikhomirov@569: 			oldContent = c1;
tikhomirov@569: 			newContent = c2;
tikhomirov@569: 			this.s1Start = s1Start;
tikhomirov@569: 			this.s1Len = s1Len;
tikhomirov@569: 			this.s2Start = s2Start;
tikhomirov@569: 			this.s2Len = s2Len;
tikhomirov@569: 			this.s1InsertPoint = s1InsertPoint;
tikhomirov@569: 			this.s2DeletePoint = s2DeletePoint;
tikhomirov@569: 		}
tikhomirov@569: 		
tikhomirov@569: 		public int insertedAt() {
tikhomirov@569: 			return s1InsertPoint;
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public int firstAddedLine() {
tikhomirov@569: 			return s2Start;
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public int totalAddedLines() {
tikhomirov@569: 			return s2Len;
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public BlockData addedLines() {
tikhomirov@569: 			if (addedBlock == null) {
tikhomirov@569: 				addedBlock = new FilterBlock(newContent, firstAddedLine(), totalAddedLines());
tikhomirov@569: 			}
tikhomirov@569: 			return addedBlock;
tikhomirov@569: 		}
tikhomirov@569: 		
tikhomirov@569: 		public int removedAt() {
tikhomirov@569: 			return s2DeletePoint;
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public int firstRemovedLine() {
tikhomirov@569: 			return s1Start;
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public int totalRemovedLines() {
tikhomirov@569: 			return s1Len;
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public BlockData removedLines() {
tikhomirov@569: 			if (removedBlock == null) {
tikhomirov@569: 				removedBlock = new FilterBlock(oldContent, firstRemovedLine(), totalRemovedLines());
tikhomirov@569: 			}
tikhomirov@569: 			return removedBlock;
tikhomirov@569: 		}
tikhomirov@569: 		
tikhomirov@569: 		@Override
tikhomirov@569: 		public String toString() {
tikhomirov@569: 			if (s2DeletePoint == -1) {
tikhomirov@569: 				return String.format("@@ -%d,0 +%d,%d @@", insertedAt(), firstAddedLine(), totalAddedLines());
tikhomirov@569: 			} else if (s1InsertPoint == -1) {
tikhomirov@569: 				// delete only
tikhomirov@569: 				return String.format("@@ -%d,%d +%d,0 @@", firstRemovedLine(), totalRemovedLines(), removedAt());
tikhomirov@569: 			}
tikhomirov@569: 			return String.format("@@ -%d,%d +%d,%d @@", firstRemovedLine(), totalRemovedLines(), firstAddedLine(), totalAddedLines());
tikhomirov@569: 		}
tikhomirov@569: 	}
tikhomirov@569: 	
tikhomirov@569: 	private static class SingleLine implements BlockData {
tikhomirov@569: 		private final ByteChain line;
tikhomirov@569: 
tikhomirov@569: 		public SingleLine(ByteChain lineContent) {
tikhomirov@569: 			line = lineContent;
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public BlockData elementAt(int index) {
tikhomirov@569: 			assert false;
tikhomirov@569: 			return null;
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public int elementCount() {
tikhomirov@569: 			return 0;
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public byte[] asArray() {
tikhomirov@569: 			return line.data();
tikhomirov@569: 		}
tikhomirov@569: 	}
tikhomirov@569: 	
tikhomirov@569: 	private static class ContentBlock implements BlockData {
tikhomirov@569: 		private final LineSequence seq;
tikhomirov@569: 
tikhomirov@569: 		public ContentBlock(LineSequence sequence) {
tikhomirov@569: 			seq = sequence;
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public BlockData elementAt(int index) {
tikhomirov@569: 			return new SingleLine(seq.chunk(index));
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public int elementCount() {
tikhomirov@569: 			return seq.chunkCount() - 1;
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public byte[] asArray() {
tikhomirov@569: 			return seq.data(0, seq.chunkCount() - 1);
tikhomirov@569: 		}
tikhomirov@569: 	}
tikhomirov@569: 	
tikhomirov@569: 	private static class FilterBlock implements BlockData {
tikhomirov@569: 		private final ContentBlock contentBlock;
tikhomirov@569: 		private final int from;
tikhomirov@569: 		private final int length;
tikhomirov@569: 
tikhomirov@569: 		public FilterBlock(ContentBlock bd, int startFrom, int len) {
tikhomirov@569: 			assert bd != null;
tikhomirov@569: 			assert startFrom + len < bd.seq.chunkCount(); // there's one extra chunk in the end, so strict less is ok
tikhomirov@569: 			contentBlock = bd;
tikhomirov@569: 			from = startFrom;
tikhomirov@569: 			length = len;
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public BlockData elementAt(int index) {
tikhomirov@569: 			if (index < 0 || index >= length) {
tikhomirov@569: 				throw new IllegalArgumentException(String.format("Expected value from [0..%d), got %d", length, index));
tikhomirov@569: 			}
tikhomirov@569: 			return contentBlock.elementAt(from + index);
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public int elementCount() {
tikhomirov@569: 			return length;
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public byte[] asArray() {
tikhomirov@569: 			return contentBlock.seq.data(from, from + length);
tikhomirov@569: 		}
tikhomirov@569: 	}
tikhomirov@569: 	
tikhomirov@678: 	
tikhomirov@678: 	interface MergeResolutionStrategy {
tikhomirov@678: 		/**
tikhomirov@678: 		 * breaks region [start..start+length) into ranges according to deduced (or simply guessed)
tikhomirov@678: 		 * matching of these lines to lines in source1 and source2
tikhomirov@678: 		 * @return list of tuples (source, start, length), where source is one of the identifiers supplied
tikhomirov@678: 		 */
tikhomirov@678: 		public IntSliceSeq combineAndMarkRangesWithSource(int start, int length, int source1, int source2);
tikhomirov@678: 		public int getLineInP2(int mergeLine);
tikhomirov@678: 	}
tikhomirov@678: 	
tikhomirov@569: 	private static class EqualBlocksCollector implements DiffHelper.MatchInspector<LineSequence> {
tikhomirov@674: 		private final RangePairSeq matches = new RangePairSeq();
tikhomirov@569: 
tikhomirov@569: 		public void begin(LineSequence s1, LineSequence s2) {
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public void match(int startSeq1, int startSeq2, int matchLength) {
tikhomirov@569: 			matches.add(startSeq1, startSeq2, matchLength);
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public void end() {
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public void intersectWithTarget(int start, int length, IntVector result) {
tikhomirov@569: 			int s = start;
tikhomirov@569: 			for (int l = start, x = start + length; l < x; l++) {
tikhomirov@569: 				if (!matches.includesTargetLine(l)) {
tikhomirov@569: 					if (l - s > 0) {
tikhomirov@569: 						result.add(s);
tikhomirov@569: 						result.add(l - s);
tikhomirov@569: 					}
tikhomirov@569: 					s = l+1;
tikhomirov@569: 				}
tikhomirov@569: 			}
tikhomirov@569: 			if (s < start+length) {
tikhomirov@569: 				result.add(s);
tikhomirov@569: 				result.add((start + length) - s);
tikhomirov@569: 			}
tikhomirov@569: 		}
tikhomirov@569: 		
tikhomirov@678: 	}
tikhomirov@678: 	
tikhomirov@678: 	private static class MergeStrategy1 implements MergeResolutionStrategy {
tikhomirov@678: 		// equal ranges in p2 and merged revision
tikhomirov@678: 		private final RangePairSeq matches; 
tikhomirov@678: 		private final IntSliceSeq mergeRanges;
tikhomirov@678: 
tikhomirov@678: 		public MergeStrategy1(RangePairSeq p2EqualToM) {
tikhomirov@678: 			matches = p2EqualToM;
tikhomirov@678: 			mergeRanges = new IntSliceSeq(3, 10, 10);
tikhomirov@678: 		}
tikhomirov@678: 
tikhomirov@569: 		/*
tikhomirov@569: 		 * intersects [start..start+length) with ranges of target lines, and based on the intersection 
tikhomirov@569: 		 * breaks initial range into smaller ranges and records them into result, with marker to indicate
tikhomirov@569: 		 * whether the range is from initial range (markerSource) or is a result of the intersection with target
tikhomirov@569: 		 * (markerTarget)
tikhomirov@569: 		 */
tikhomirov@678: 		public IntSliceSeq combineAndMarkRangesWithSource(int start, int length, int markerSource, int markerTarget) {
tikhomirov@678: 			mergeRanges.clear();
tikhomirov@678: 			assert mergeRanges.sliceSize() == 3;
tikhomirov@569: 			int sourceStart = start, targetStart = start, sourceEnd = start + length;
tikhomirov@569: 			for (int l = sourceStart; l < sourceEnd; l++) {
tikhomirov@569: 				if (matches.includesTargetLine(l)) {
tikhomirov@569: 					// l is from target
tikhomirov@569: 					if (sourceStart < l) {
tikhomirov@569: 						// few lines from source range were not in the target, report them
tikhomirov@678: 						mergeRanges.add(markerSource, sourceStart, l - sourceStart);
tikhomirov@569: 					}
tikhomirov@569: 					// indicate the earliest line from source range to use
tikhomirov@569: 					sourceStart = l + 1;
tikhomirov@569: 				} else {
tikhomirov@569: 					// l is not in target
tikhomirov@569: 					if (targetStart < l) {
tikhomirov@569: 						// report lines from target range
tikhomirov@678: 						mergeRanges.add(markerTarget, targetStart, l - targetStart);
tikhomirov@569: 					}
tikhomirov@569: 					// next line *may* be from target
tikhomirov@569: 					targetStart = l + 1;
tikhomirov@569: 				}
tikhomirov@569: 			}
tikhomirov@569: 			// if source range end with line from target, sourceStart would be == sourceEnd, and we need to add range with markerTarget
tikhomirov@569: 			// if source range doesn't end with target line, targetStart == sourceEnd, while sourceStart < sourceEnd
tikhomirov@569: 			if (sourceStart < sourceEnd) {
tikhomirov@569: 				assert targetStart == sourceEnd;
tikhomirov@569: 				// something left from the source range
tikhomirov@678: 				mergeRanges.add(markerSource, sourceStart, sourceEnd - sourceStart);
tikhomirov@569: 			} else if (targetStart < sourceEnd) {
tikhomirov@569: 				assert sourceStart == sourceEnd;
tikhomirov@678: 				mergeRanges.add(markerTarget, targetStart, sourceEnd - targetStart);
tikhomirov@569: 			}
tikhomirov@678: 			return mergeRanges;
tikhomirov@678: 		}
tikhomirov@678: 
tikhomirov@678: 		public int getLineInP2(int mergeLine) {
tikhomirov@678: 			return matches.reverseMapLine(mergeLine);
tikhomirov@569: 		}
tikhomirov@569: 	}
tikhomirov@569: 
tikhomirov@569: 	private static class AnnotateRev implements RevisionDescriptor {
tikhomirov@569: 		public ContentBlock origin, target;
tikhomirov@569: 		public int originCset, targetCset, mergeCset, fileRevIndex;
tikhomirov@569: 		public HgDataFile df;
tikhomirov@569: 		
tikhomirov@569: 		public void set(HgDataFile file, int fileRev) {
tikhomirov@569: 			df = file;
tikhomirov@569: 			fileRevIndex = fileRev;
tikhomirov@569: 		}
tikhomirov@569: 		public void set(ContentBlock o, ContentBlock t) {
tikhomirov@569: 			origin = o;
tikhomirov@569: 			target = t;
tikhomirov@569: 		}
tikhomirov@569: 		public void set(int o, int t, int m) {
tikhomirov@569: 			originCset = o;
tikhomirov@569: 			targetCset = t;
tikhomirov@569: 			mergeCset = m;
tikhomirov@569: 		}
tikhomirov@569: 		
tikhomirov@569: 		public BlockData origin() {
tikhomirov@569: 			return origin;
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public BlockData target() {
tikhomirov@569: 			return target;
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public int originChangesetIndex() {
tikhomirov@569: 			return originCset;
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public int targetChangesetIndex() {
tikhomirov@569: 			return targetCset;
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public boolean isMerge() {
tikhomirov@569: 			return mergeCset != NO_REVISION;
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public int mergeChangesetIndex() {
tikhomirov@569: 			return mergeCset;
tikhomirov@569: 		}
tikhomirov@569: 
tikhomirov@569: 		public int fileRevisionIndex() {
tikhomirov@569: 			return fileRevIndex;
tikhomirov@569: 		}
tikhomirov@569: 		public HgDataFile file() {
tikhomirov@569: 			return df;
tikhomirov@569: 		}
tikhomirov@569: 		@Override
tikhomirov@569: 		public String toString() {
tikhomirov@569: 			if (isMerge()) {
tikhomirov@569: 				return String.format("[%d,%d->%d]", originCset, mergeCset, targetCset);
tikhomirov@569: 			}
tikhomirov@569: 			return String.format("[%d->%d]", originCset, targetCset);
tikhomirov@569: 		}
tikhomirov@569: 	}
tikhomirov@569: 
tikhomirov@569: 	public static void main(String[] args) {
tikhomirov@569: 		EqualBlocksCollector bc = new EqualBlocksCollector();
tikhomirov@569: 		bc.match(-1, 5, 3);
tikhomirov@569: 		bc.match(-1, 10, 2);
tikhomirov@569: 		bc.match(-1, 15, 3);
tikhomirov@569: 		bc.match(-1, 20, 3);
tikhomirov@569: 		IntVector r = new IntVector();
tikhomirov@569: 		bc.intersectWithTarget(7, 10, r);
tikhomirov@569: 		for (int i = 0; i < r.size(); i+=2) {
tikhomirov@569: 			System.out.printf("[%d..%d) ", r.get(i), r.get(i) + r.get(i+1));
tikhomirov@569: 		}
tikhomirov@569: 		System.out.println();
tikhomirov@678: 		MergeStrategy1 ms = new MergeStrategy1(bc.matches);
tikhomirov@678: 		IntSliceSeq mr = ms.combineAndMarkRangesWithSource(0, 16, 508, 514);
tikhomirov@674: 		for (IntTuple t : mr) {
tikhomirov@674: 			System.out.printf("%d:[%d..%d)  ", t.at(0), t.at(1), t.at(1) + t.at(2));
tikhomirov@569: 		}
tikhomirov@569: 	}
tikhomirov@569: }