tikhomirov@542: /*
tikhomirov@542:  * Copyright (c) 2013 TMate Software Ltd
tikhomirov@542:  *  
tikhomirov@542:  * This program is free software; you can redistribute it and/or modify
tikhomirov@542:  * it under the terms of the GNU General Public License as published by
tikhomirov@542:  * the Free Software Foundation; version 2 of the License.
tikhomirov@542:  *
tikhomirov@542:  * This program is distributed in the hope that it will be useful,
tikhomirov@542:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
tikhomirov@542:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
tikhomirov@542:  * GNU General Public License for more details.
tikhomirov@542:  *
tikhomirov@542:  * For information on how to redistribute this software under
tikhomirov@542:  * the terms of a license other than GNU General Public License
tikhomirov@542:  * contact TMate Software at support@hg4j.com
tikhomirov@542:  */
tikhomirov@542: package org.tmatesoft.hg.internal;
tikhomirov@542: 
tikhomirov@542: import static org.tmatesoft.hg.repo.HgRepository.NO_REVISION;
tikhomirov@548: import static org.tmatesoft.hg.repo.HgRepository.TIP;
tikhomirov@542: 
tikhomirov@552: import java.util.BitSet;
tikhomirov@552: import java.util.LinkedList;
tikhomirov@552: import java.util.ListIterator;
tikhomirov@552: 
tikhomirov@552: import org.tmatesoft.hg.core.HgIterateDirection;
tikhomirov@542: import org.tmatesoft.hg.core.Nodeid;
tikhomirov@554: import org.tmatesoft.hg.internal.AnnotateFacility.BlockData;
tikhomirov@551: import org.tmatesoft.hg.internal.DiffHelper.LineSequence;
tikhomirov@554: import org.tmatesoft.hg.internal.DiffHelper.LineSequence.ByteChain;
tikhomirov@542: import org.tmatesoft.hg.repo.HgDataFile;
tikhomirov@542: import org.tmatesoft.hg.repo.HgInvalidStateException;
tikhomirov@542: import org.tmatesoft.hg.util.CancelledException;
tikhomirov@552: import org.tmatesoft.hg.util.Pair;
tikhomirov@542: 
tikhomirov@542: /**
tikhomirov@542:  * 
tikhomirov@542:  * @author Artem Tikhomirov
tikhomirov@542:  * @author TMate Software Ltd.
tikhomirov@542:  */
tikhomirov@542: @Experimental(reason="work in progress")
tikhomirov@542: public class AnnotateFacility {
tikhomirov@549: 	
tikhomirov@549: 	/**
tikhomirov@552: 	 * mimic 'hg diff -r clogRevIndex1 -r clogRevIndex2'
tikhomirov@549: 	 */
tikhomirov@552: 	public void diff(HgDataFile df, int clogRevIndex1, int clogRevIndex2, BlockInspector insp) {
tikhomirov@552: 		int fileRevIndex1 = fileRevIndex(df, clogRevIndex1);
tikhomirov@552: 		int fileRevIndex2 = fileRevIndex(df, clogRevIndex2);
tikhomirov@552: 		FileLinesCache fileInfoCache = new FileLinesCache(df, 5);
tikhomirov@552: 		LineSequence c1 = fileInfoCache.lines(fileRevIndex1);
tikhomirov@552: 		LineSequence c2 = fileInfoCache.lines(fileRevIndex2);
tikhomirov@551: 		DiffHelper<LineSequence> pg = new DiffHelper<LineSequence>();
tikhomirov@549: 		pg.init(c1, c2);
tikhomirov@552: 		pg.findMatchingBlocks(new BlameBlockInspector(insp, clogRevIndex1, clogRevIndex2));
tikhomirov@552: 	}
tikhomirov@552: 	
tikhomirov@552: 	public void annotate(HgDataFile df, int changelogRevisionIndex, BlockInspector insp, HgIterateDirection iterateOrder) {
tikhomirov@552: 		if (!df.exists()) {
tikhomirov@552: 			return;
tikhomirov@552: 		}
tikhomirov@552: 		// Note, changelogRevisionIndex may be TIP, while #implAnnotateChange doesn't tolerate constants
tikhomirov@552: 		//
tikhomirov@552: 		// XXX df.indexWalk(0, fileRevIndex, ) might be more effective
tikhomirov@552: 		int fileRevIndex = fileRevIndex(df, changelogRevisionIndex);
tikhomirov@552: 		int[] fileRevParents = new int[2];
tikhomirov@552: 		IntVector fileParentRevs = new IntVector((fileRevIndex+1) * 2, 0);
tikhomirov@552: 		fileParentRevs.add(NO_REVISION, NO_REVISION);
tikhomirov@552: 		for (int i = 1; i <= fileRevIndex; i++) {
tikhomirov@552: 			df.parents(i, fileRevParents, null, null);
tikhomirov@552: 			fileParentRevs.add(fileRevParents[0], fileRevParents[1]);
tikhomirov@552: 		}
tikhomirov@552: 		// collect file revisions to visit, from newest to oldest
tikhomirov@552: 		IntVector fileRevsToVisit = new IntVector(fileRevIndex + 1, 0);
tikhomirov@552: 		LinkedList<Integer> queue = new LinkedList<Integer>();
tikhomirov@552: 		BitSet seen = new BitSet(fileRevIndex + 1);
tikhomirov@552: 		queue.add(fileRevIndex);
tikhomirov@552: 		do {
tikhomirov@552: 			int x = queue.removeFirst();
tikhomirov@552: 			if (seen.get(x)) {
tikhomirov@552: 				continue;
tikhomirov@552: 			}
tikhomirov@552: 			seen.set(x);
tikhomirov@552: 			fileRevsToVisit.add(x);
tikhomirov@552: 			int p1 = fileParentRevs.get(2*x);
tikhomirov@552: 			int p2 = fileParentRevs.get(2*x + 1);
tikhomirov@552: 			if (p1 != NO_REVISION) {
tikhomirov@552: 				queue.addLast(p1);
tikhomirov@552: 			}
tikhomirov@552: 			if (p2 != NO_REVISION) {
tikhomirov@552: 				queue.addLast(p2);
tikhomirov@552: 			}
tikhomirov@552: 		} while (!queue.isEmpty());
tikhomirov@552: 		FileLinesCache fileInfoCache = new FileLinesCache(df, 10);
tikhomirov@552: 		// fileRevsToVisit now { r10, r7, r6, r5, r0 }
tikhomirov@552: 		// and we'll iterate it from behind, e.g. old to new unless reversed 
tikhomirov@552: 		if (iterateOrder == HgIterateDirection.NewToOld) {
tikhomirov@552: 			fileRevsToVisit.reverse();
tikhomirov@552: 		}
tikhomirov@552: 		for (int i = fileRevsToVisit.size() - 1; i >= 0; i--) {
tikhomirov@552: 			int fri = fileRevsToVisit.get(i);
tikhomirov@552: 			int clogRevIndex = df.getChangesetRevisionIndex(fri);
tikhomirov@552: 			fileRevParents[0] = fileParentRevs.get(fri * 2);
tikhomirov@552: 			fileRevParents[1] = fileParentRevs.get(fri * 2 + 1);
tikhomirov@552: 			implAnnotateChange(fileInfoCache, clogRevIndex, fri, fileRevParents, insp);
tikhomirov@552: 		}
tikhomirov@549: 	}
tikhomirov@548: 
tikhomirov@548: 	/**
tikhomirov@548: 	 * Annotate file revision, line by line. 
tikhomirov@548: 	 */
tikhomirov@552: 	public void annotate(HgDataFile df, int changelogRevisionIndex, LineInspector insp) {
tikhomirov@548: 		if (!df.exists()) {
tikhomirov@548: 			return;
tikhomirov@548: 		}
tikhomirov@548: 		FileAnnotation fa = new FileAnnotation(insp);
tikhomirov@552: 		annotate(df, changelogRevisionIndex, fa, HgIterateDirection.NewToOld);
tikhomirov@548: 	}
tikhomirov@548: 
tikhomirov@544: 	/**
tikhomirov@544: 	 * Annotates changes of the file against its parent(s)
tikhomirov@544: 	 */
tikhomirov@552: 	public void annotateChange(HgDataFile df, int changelogRevisionIndex, BlockInspector insp) {
tikhomirov@545: 		// TODO detect if file is text/binary (e.g. looking for chars < ' ' and not \t\r\n\f
tikhomirov@552: 		int fileRevIndex = fileRevIndex(df, changelogRevisionIndex);
tikhomirov@542: 		int[] fileRevParents = new int[2];
tikhomirov@542: 		df.parents(fileRevIndex, fileRevParents, null, null);
tikhomirov@552: 		if (changelogRevisionIndex == TIP) {
tikhomirov@552: 			changelogRevisionIndex = df.getChangesetRevisionIndex(fileRevIndex);
tikhomirov@548: 		}
tikhomirov@552: 		implAnnotateChange(new FileLinesCache(df, 5), changelogRevisionIndex, fileRevIndex, fileRevParents, insp);
tikhomirov@548: 	}
tikhomirov@548: 
tikhomirov@552: 	private void implAnnotateChange(FileLinesCache fl, int csetRevIndex, int fileRevIndex, int[] fileParentRevs, BlockInspector insp) {
tikhomirov@552: 		final LineSequence fileRevLines = fl.lines(fileRevIndex);
tikhomirov@549: 		if (fileParentRevs[0] != NO_REVISION && fileParentRevs[1] != NO_REVISION) {
tikhomirov@552: 			LineSequence p1Lines = fl.lines(fileParentRevs[0]);
tikhomirov@552: 			LineSequence p2Lines = fl.lines(fileParentRevs[1]);
tikhomirov@552: 			int p1ClogIndex = fl.getChangesetRevisionIndex(fileParentRevs[0]);
tikhomirov@552: 			int p2ClogIndex = fl.getChangesetRevisionIndex(fileParentRevs[1]);
tikhomirov@551: 			DiffHelper<LineSequence> pg = new DiffHelper<LineSequence>();
tikhomirov@549: 			pg.init(p2Lines, fileRevLines);
tikhomirov@549: 			EqualBlocksCollector p2MergeCommon = new EqualBlocksCollector();
tikhomirov@549: 			pg.findMatchingBlocks(p2MergeCommon);
tikhomirov@549: 			//
tikhomirov@549: 			pg.init(p1Lines);
tikhomirov@549: 			BlameBlockInspector bbi = new BlameBlockInspector(insp, p1ClogIndex, csetRevIndex);
tikhomirov@549: 			bbi.setMergeParent2(p2MergeCommon, p2ClogIndex);
tikhomirov@549: 			pg.findMatchingBlocks(bbi);
tikhomirov@549: 		} else if (fileParentRevs[0] == fileParentRevs[1]) {
tikhomirov@549: 			// may be equal iff both are unset
tikhomirov@549: 			assert fileParentRevs[0] == NO_REVISION;
tikhomirov@549: 			// everything added
tikhomirov@549: 			BlameBlockInspector bbi = new BlameBlockInspector(insp, NO_REVISION, csetRevIndex);
tikhomirov@549: 			bbi.begin(LineSequence.newlines(new byte[0]), fileRevLines);
tikhomirov@549: 			bbi.match(0, fileRevLines.chunkCount()-1, 0);
tikhomirov@549: 			bbi.end();
tikhomirov@549: 		} else {
tikhomirov@549: 			int soleParent = fileParentRevs[0] == NO_REVISION ? fileParentRevs[1] : fileParentRevs[0];
tikhomirov@549: 			assert soleParent != NO_REVISION;
tikhomirov@552: 			LineSequence parentLines = fl.lines(soleParent);
tikhomirov@549: 			
tikhomirov@552: 			int parentChangesetRevIndex = fl.getChangesetRevisionIndex(soleParent);
tikhomirov@551: 			DiffHelper<LineSequence> pg = new DiffHelper<LineSequence>();
tikhomirov@549: 			pg.init(parentLines, fileRevLines);
tikhomirov@549: 			pg.findMatchingBlocks(new BlameBlockInspector(insp, parentChangesetRevIndex, csetRevIndex));
tikhomirov@549: 		}
tikhomirov@549: 	}
tikhomirov@549: 
tikhomirov@549: 	private static int fileRevIndex(HgDataFile df, int csetRevIndex) {
tikhomirov@549: 		Nodeid fileRev = df.getRepo().getManifest().getFileRevision(csetRevIndex, df.getPath());
tikhomirov@549: 		return df.getRevisionIndex(fileRev);
tikhomirov@549: 	}
tikhomirov@549: 
tikhomirov@552: 	private static class FileLinesCache {
tikhomirov@552: 		private final HgDataFile df;
tikhomirov@552: 		private final LinkedList<Pair<Integer, LineSequence>> lruCache;
tikhomirov@552: 		private final int limit;
tikhomirov@552: 		private IntMap<Integer> fileToClogIndexMap = new IntMap<Integer>(20);
tikhomirov@552: 
tikhomirov@552: 		public FileLinesCache(HgDataFile file, int lruLimit) {
tikhomirov@552: 			df = file;
tikhomirov@552: 			limit = lruLimit;
tikhomirov@552: 			lruCache = new LinkedList<Pair<Integer, LineSequence>>();
tikhomirov@552: 		}
tikhomirov@552: 		
tikhomirov@552: 		public int getChangesetRevisionIndex(int fileRevIndex) {
tikhomirov@552: 			Integer cached = fileToClogIndexMap.get(fileRevIndex);
tikhomirov@552: 			if (cached == null) {
tikhomirov@552: 				cached = df.getChangesetRevisionIndex(fileRevIndex);
tikhomirov@552: 				fileToClogIndexMap.put(fileRevIndex, cached);
tikhomirov@552: 			}
tikhomirov@552: 			return cached.intValue();
tikhomirov@552: 		}
tikhomirov@552: 
tikhomirov@552: 		public LineSequence lines(int fileRevIndex) {
tikhomirov@552: 			Pair<Integer, LineSequence> cached = checkCache(fileRevIndex);
tikhomirov@552: 			if (cached != null) {
tikhomirov@552: 				return cached.second();
tikhomirov@552: 			}
tikhomirov@552: 			try {
tikhomirov@552: 				ByteArrayChannel c;
tikhomirov@552: 				df.content(fileRevIndex, c = new ByteArrayChannel());
tikhomirov@552: 				LineSequence rv = LineSequence.newlines(c.toArray());
tikhomirov@552: 				lruCache.addFirst(new Pair<Integer, LineSequence>(fileRevIndex, rv));
tikhomirov@552: 				if (lruCache.size() > limit) {
tikhomirov@552: 					lruCache.removeLast();
tikhomirov@552: 				}
tikhomirov@552: 				return rv;
tikhomirov@552: 			} catch (CancelledException ex) {
tikhomirov@552: 				// TODO likely it was bad idea to throw cancelled exception from content()
tikhomirov@552: 				// deprecate and provide alternative?
tikhomirov@552: 				HgInvalidStateException ise = new HgInvalidStateException("ByteArrayChannel never throws CancelledException");
tikhomirov@552: 				ise.initCause(ex);
tikhomirov@552: 				throw ise;
tikhomirov@552: 			}
tikhomirov@552: 		}
tikhomirov@552: 		
tikhomirov@552: 		private Pair<Integer,LineSequence> checkCache(int fileRevIndex) {
tikhomirov@552: 			Pair<Integer, LineSequence> rv = null;
tikhomirov@552: 			for (ListIterator<Pair<Integer, LineSequence>> it = lruCache.listIterator(); it.hasNext(); ) {
tikhomirov@552: 				Pair<Integer, LineSequence> p = it.next();
tikhomirov@552: 				if (p.first() == fileRevIndex) {
tikhomirov@552: 					rv = p;
tikhomirov@552: 					it.remove();
tikhomirov@552: 					break;
tikhomirov@552: 				}
tikhomirov@552: 			}
tikhomirov@552: 			if (rv != null) {
tikhomirov@552: 				lruCache.addFirst(rv);
tikhomirov@552: 			}
tikhomirov@552: 			return rv;
tikhomirov@542: 		}
tikhomirov@542: 	}
tikhomirov@542: 
tikhomirov@542: 	@Callback
tikhomirov@546: 	public interface BlockInspector {
tikhomirov@545: 		void same(EqualBlock block);
tikhomirov@542: 		void added(AddBlock block);
tikhomirov@542: 		void changed(ChangeBlock block);
tikhomirov@542: 		void deleted(DeleteBlock block);
tikhomirov@542: 	}
tikhomirov@542: 	
tikhomirov@545: 	@Callback
tikhomirov@546: 	public interface BlockInspectorEx extends BlockInspector { // XXX better name
tikhomirov@545: 		// XXX perhaps, shall pass object instead of separate values for future extension?
tikhomirov@554: 		void start(BlockData originContent, BlockData targetContent);
tikhomirov@545: 		void done();
tikhomirov@545: 	}
tikhomirov@545: 	
tikhomirov@554: 	/**
tikhomirov@554: 	 * Represents content of a block, either as a sequence of bytes or a 
tikhomirov@554: 	 * sequence of smaller blocks (lines), if appropriate (according to usage context).
tikhomirov@554: 	 * 
tikhomirov@554: 	 * This approach allows line-by-line access to content data along with complete byte sequence for the whole block, i.e.
tikhomirov@554: 	 * <pre>
tikhomirov@554: 	 *    BlockData bd = addBlock.addedLines()
tikhomirov@554: 	 *    // bd describes data from the addition completely.
tikhomirov@554: 	 *    // elements of the BlockData are lines
tikhomirov@554: 	 *    bd.elementCount() == addBlock.totalAddedLines();
tikhomirov@554: 	 *    // one cat obtain complete addition with
tikhomirov@554: 	 *    byte[] everythingAdded = bd.asArray();
tikhomirov@554: 	 *    // or iterate line by line
tikhomirov@554: 	 *    for (int i = 0; i < bd.elementCount(); i++) {
tikhomirov@554: 	 *    	 byte[] lineContent = bd.elementAt(i);
tikhomirov@554: 	 *       String line = new String(lineContent, fileEncodingCharset);
tikhomirov@554: 	 *    }
tikhomirov@554: 	 *    where bd.elementAt(0) is the line at index addBlock.firstAddedLine() 
tikhomirov@554: 	 * </pre> 
tikhomirov@554: 	 * 
tikhomirov@554: 	 * LineData or ChunkData? 
tikhomirov@554: 	 */
tikhomirov@554: 	public interface BlockData {
tikhomirov@554: 		BlockData elementAt(int index);
tikhomirov@554: 		int elementCount();
tikhomirov@554: 		byte[] asArray();
tikhomirov@554: 	}
tikhomirov@554: 	
tikhomirov@542: 	public interface Block {
tikhomirov@545: 		int originChangesetIndex();
tikhomirov@545: 		int targetChangesetIndex();
tikhomirov@542: //		boolean isMergeRevision();
tikhomirov@542: //		int fileRevisionIndex();
tikhomirov@542: //		int originFileRevisionIndex();
tikhomirov@542: //		String[] lines();
tikhomirov@542: //		byte[] data();
tikhomirov@542: 	}
tikhomirov@542: 	
tikhomirov@545: 	public interface EqualBlock extends Block {
tikhomirov@545: 		int originStart();
tikhomirov@545: 		int targetStart();
tikhomirov@545: 		int length();
tikhomirov@554: 		BlockData content();
tikhomirov@545: 	}
tikhomirov@545: 	
tikhomirov@542: 	public interface AddBlock extends Block {
tikhomirov@543: 		int insertedAt(); // line index in the old file 
tikhomirov@542: 		int firstAddedLine();
tikhomirov@542: 		int totalAddedLines();
tikhomirov@554: 		BlockData addedLines();
tikhomirov@542: 	}
tikhomirov@542: 	public interface DeleteBlock extends Block {
tikhomirov@543: 		int removedAt(); // line index in the new file
tikhomirov@542: 		int firstRemovedLine();
tikhomirov@542: 		int totalRemovedLines();
tikhomirov@554: 		BlockData removedLines();
tikhomirov@542: 	}
tikhomirov@542: 	public interface ChangeBlock extends AddBlock, DeleteBlock {
tikhomirov@542: 	}
tikhomirov@546: 	
tikhomirov@546: 	@Callback
tikhomirov@546: 	public interface LineInspector {
tikhomirov@548: 		/**
tikhomirov@548: 		 * Not necessarily invoked sequentially by line numbers
tikhomirov@548: 		 */
tikhomirov@546: 		void line(int lineNumber, int changesetRevIndex, LineDescriptor ld);
tikhomirov@546: 	}
tikhomirov@546: 	
tikhomirov@546: 	public interface LineDescriptor {
tikhomirov@546: 		int totalLines();
tikhomirov@546: 	}
tikhomirov@546: 	
tikhomirov@546: 
tikhomirov@542: 
tikhomirov@551: 	static class BlameBlockInspector extends DiffHelper.DeltaInspector<LineSequence> {
tikhomirov@546: 		private final BlockInspector insp;
tikhomirov@549: 		private final int csetOrigin;
tikhomirov@545: 		private final int csetTarget;
tikhomirov@549: 		private EqualBlocksCollector p2MergeCommon;
tikhomirov@549: 		private int csetMergeParent;
tikhomirov@549: 		private IntVector mergeRanges;
tikhomirov@554: 		private ContentBlock originContent, targetContent;
tikhomirov@542: 
tikhomirov@549: 		public BlameBlockInspector(BlockInspector inspector, int originCset, int targetCset) {
tikhomirov@542: 			assert inspector != null;
tikhomirov@542: 			insp = inspector;
tikhomirov@549: 			csetOrigin = originCset;
tikhomirov@545: 			csetTarget = targetCset;
tikhomirov@545: 		}
tikhomirov@545: 		
tikhomirov@549: 		public void setMergeParent2(EqualBlocksCollector p2Merge, int parentCset2) {
tikhomirov@549: 			p2MergeCommon = p2Merge;
tikhomirov@549: 			csetMergeParent = parentCset2;
tikhomirov@549: 			mergeRanges = new IntVector(3*10, 3*10);
tikhomirov@549: 		}
tikhomirov@549: 		
tikhomirov@545: 		@Override
tikhomirov@545: 		public void begin(LineSequence s1, LineSequence s2) {
tikhomirov@545: 			super.begin(s1, s2);
tikhomirov@554: 			originContent = new ContentBlock(s1);
tikhomirov@554: 			targetContent = new ContentBlock(s2);
tikhomirov@546: 			if (insp instanceof BlockInspectorEx) {
tikhomirov@554: 				((BlockInspectorEx) insp).start(originContent, targetContent);
tikhomirov@545: 			}
tikhomirov@545: 		}
tikhomirov@545: 		
tikhomirov@545: 		@Override
tikhomirov@545: 		public void end() {
tikhomirov@545: 			super.end();
tikhomirov@546: 			if(insp instanceof BlockInspectorEx) {
tikhomirov@546: 				((BlockInspectorEx) insp).done();
tikhomirov@545: 			}
tikhomirov@542: 		}
tikhomirov@542: 
tikhomirov@542: 		@Override
tikhomirov@542: 		protected void changed(int s1From, int s1To, int s2From, int s2To) {
tikhomirov@549: 			if (p2MergeCommon != null) {
tikhomirov@549: 				mergeRanges.clear();
tikhomirov@549: 				p2MergeCommon.combineAndMarkRangesWithTarget(s2From, s2To - s2From, csetOrigin, csetMergeParent, mergeRanges);
tikhomirov@549: 				
tikhomirov@549: 				/*
tikhomirov@549: 				 * Usecases:
tikhomirov@549: 				 * 3 lines changed to 10 lines. range of 10 lines breaks down to 2 from p2, 3 from p1, and 5 from p2.
tikhomirov@549: 				 * We report: 2 lines changed to 2(p2), then 1 line changed with 3(p1) and 5 lines added from p2.
tikhomirov@549: 				 * 
tikhomirov@549: 				 * 10 lines changed to 3 lines, range of 3 lines breaks down to 2 line from p1 and 1 line from p2.
tikhomirov@549: 				 * We report: 2 lines changed to 2(p1) and 8 lines changed to 1(p2) 
tikhomirov@549: 				 */
tikhomirov@549: 				int s1TotalLines = s1To - s1From, s1ConsumedLines = 0, s1Start = s1From;
tikhomirov@549: 				
tikhomirov@549: 				for (int i = 0; i < mergeRanges.size(); i += 3) {
tikhomirov@549: 					final int rangeOrigin = mergeRanges.get(i);
tikhomirov@549: 					final int rangeStart = mergeRanges.get(i+1);
tikhomirov@549: 					final int rangeLen = mergeRanges.get(i+2);
tikhomirov@549: 					final boolean lastRange = i+3 >= mergeRanges.size();
tikhomirov@549: 					final int s1LinesLeft = s1TotalLines - s1ConsumedLines;
tikhomirov@549: 					// how many lines we may reported as changed (don't use more than in range unless it's the very last range)
tikhomirov@549: 					final int s1LinesToBorrow = lastRange ? s1LinesLeft : Math.min(s1LinesLeft, rangeLen);
tikhomirov@549: 					if (s1LinesToBorrow > 0) {
tikhomirov@554: 						ChangeBlockImpl block = new ChangeBlockImpl(originContent, targetContent, s1Start, s1LinesToBorrow, rangeStart, rangeLen, s1Start, rangeStart);
tikhomirov@549: 						block.setOriginAndTarget(rangeOrigin, csetTarget);
tikhomirov@549: 						insp.changed(block);
tikhomirov@549: 						s1ConsumedLines += s1LinesToBorrow;
tikhomirov@549: 						s1Start += s1LinesToBorrow;
tikhomirov@549: 					} else {
tikhomirov@554: 						ChangeBlockImpl block = getAddBlock(rangeStart, rangeLen, s1Start);
tikhomirov@549: 						block.setOriginAndTarget(rangeOrigin, csetTarget);
tikhomirov@549: 						insp.added(block);
tikhomirov@549: 					}
tikhomirov@549: 				}
tikhomirov@549: 				if (s1ConsumedLines != s1TotalLines) {
tikhomirov@549: 					throw new HgInvalidStateException(String.format("Expected to process %d lines, but actually was %d", s1TotalLines, s1ConsumedLines));
tikhomirov@549: 				}
tikhomirov@549: 			} else {
tikhomirov@554: 				ChangeBlockImpl block = new ChangeBlockImpl(originContent, targetContent, s1From, s1To-s1From, s2From, s2To - s2From, s1From, s2From);
tikhomirov@549: 				block.setOriginAndTarget(csetOrigin, csetTarget);
tikhomirov@549: 				insp.changed(block);
tikhomirov@549: 			}
tikhomirov@542: 		}
tikhomirov@542: 		
tikhomirov@542: 		@Override
tikhomirov@542: 		protected void added(int s1InsertPoint, int s2From, int s2To) {
tikhomirov@549: 			if (p2MergeCommon != null) {
tikhomirov@549: 				mergeRanges.clear();
tikhomirov@549: 				p2MergeCommon.combineAndMarkRangesWithTarget(s2From, s2To - s2From, csetOrigin, csetMergeParent, mergeRanges);
tikhomirov@549: 				int insPoint = s1InsertPoint; // track changes to insertion point
tikhomirov@549: 				for (int i = 0; i < mergeRanges.size(); i += 3) {
tikhomirov@549: 					int rangeOrigin = mergeRanges.get(i);
tikhomirov@549: 					int rangeStart = mergeRanges.get(i+1);
tikhomirov@549: 					int rangeLen = mergeRanges.get(i+2);
tikhomirov@554: 					ChangeBlockImpl block = getAddBlock(rangeStart, rangeLen, insPoint);
tikhomirov@549: 					block.setOriginAndTarget(rangeOrigin, csetTarget);
tikhomirov@549: 					insp.added(block);
tikhomirov@549: 					// indicate insPoint moved down number of lines we just reported
tikhomirov@549: 					insPoint += rangeLen;
tikhomirov@549: 				}
tikhomirov@549: 			} else {
tikhomirov@554: 				ChangeBlockImpl block = getAddBlock(s2From, s2To - s2From, s1InsertPoint);
tikhomirov@549: 				block.setOriginAndTarget(csetOrigin, csetTarget);
tikhomirov@549: 				insp.added(block);
tikhomirov@549: 			}
tikhomirov@542: 		}
tikhomirov@542: 		
tikhomirov@542: 		@Override
tikhomirov@543: 		protected void deleted(int s2DeletePoint, int s1From, int s1To) {
tikhomirov@554: 			ChangeBlockImpl block = new ChangeBlockImpl(originContent, null, s1From, s1To - s1From, -1, -1, -1, s2DeletePoint);
tikhomirov@549: 			block.setOriginAndTarget(csetOrigin, csetTarget);
tikhomirov@545: 			insp.deleted(block);
tikhomirov@542: 		}
tikhomirov@542: 
tikhomirov@542: 		@Override
tikhomirov@542: 		protected void unchanged(int s1From, int s2From, int length) {
tikhomirov@554: 			EqualBlockImpl block = new EqualBlockImpl(s1From, s2From, length, targetContent);
tikhomirov@549: 			block.setOriginAndTarget(csetOrigin, csetTarget);
tikhomirov@545: 			insp.same(block);
tikhomirov@545: 		}
tikhomirov@549: 		
tikhomirov@554: 		private ChangeBlockImpl getAddBlock(int start, int len, int insPoint) {
tikhomirov@554: 			return new ChangeBlockImpl(null, targetContent, -1, -1, start, len, insPoint, -1);
tikhomirov@549: 		}
tikhomirov@545: 	}
tikhomirov@545: 	
tikhomirov@545: 	static class BlockImpl implements Block {
tikhomirov@545: 		
tikhomirov@545: 		private int originCset;
tikhomirov@545: 		private int targetCset;
tikhomirov@545: 
tikhomirov@545: 		void setOriginAndTarget(int originChangesetIndex, int targetChangesetIndex) {
tikhomirov@545: 			// XXX perhaps, shall be part of Inspector API, rather than Block's
tikhomirov@545: 			// as they don't change between blocks (although the moment about merged revisions)
tikhomirov@545: 			// is not yet clear to me
tikhomirov@545: 			originCset = originChangesetIndex;
tikhomirov@545: 			targetCset = targetChangesetIndex;
tikhomirov@545: 		}
tikhomirov@545: 
tikhomirov@545: 		public int originChangesetIndex() {
tikhomirov@545: 			return originCset;
tikhomirov@545: 		}
tikhomirov@545: 
tikhomirov@545: 		public int targetChangesetIndex() {
tikhomirov@545: 			return targetCset;
tikhomirov@542: 		}
tikhomirov@542: 	}
tikhomirov@542: 
tikhomirov@554: 	static class EqualBlockImpl extends BlockImpl implements EqualBlock {
tikhomirov@545: 		private final int start1, start2;
tikhomirov@542: 		private final int length;
tikhomirov@554: 		private final ContentBlock fullContent;
tikhomirov@554: 		private FilterBlock myContent;
tikhomirov@542: 		
tikhomirov@554: 		EqualBlockImpl(int blockStartSeq1, int blockStartSeq2, int blockLength, ContentBlock targetContent) {
tikhomirov@545: 			start1 = blockStartSeq1;
tikhomirov@545: 			start2 = blockStartSeq2;
tikhomirov@545: 			length = blockLength;
tikhomirov@554: 			fullContent = targetContent;
tikhomirov@542: 		}
tikhomirov@542: 
tikhomirov@545: 		public int originStart() {
tikhomirov@545: 			return start1;
tikhomirov@545: 		}
tikhomirov@545: 
tikhomirov@545: 		public int targetStart() {
tikhomirov@545: 			return start2;
tikhomirov@545: 		}
tikhomirov@545: 
tikhomirov@545: 		public int length() {
tikhomirov@545: 			return length;
tikhomirov@542: 		}
tikhomirov@542: 		
tikhomirov@554: 		public BlockData content() {
tikhomirov@554: 			if (myContent == null) {
tikhomirov@554: 				myContent = new FilterBlock(fullContent, start2, length);
tikhomirov@554: 			}
tikhomirov@554: 			return myContent;
tikhomirov@554: 		}
tikhomirov@554: 		
tikhomirov@545: 		@Override
tikhomirov@545: 		public String toString() {
tikhomirov@545: 			return String.format("@@ [%d..%d) == [%d..%d) @@", start1, start1+length, start2, start2+length);
tikhomirov@545: 		}
tikhomirov@542: 	}
tikhomirov@542: 	
tikhomirov@554: 	static class ChangeBlockImpl extends BlockImpl implements ChangeBlock {
tikhomirov@542: 		
tikhomirov@554: 		private final ContentBlock oldContent;
tikhomirov@554: 		private final ContentBlock newContent;
tikhomirov@542: 		private final int s1Start;
tikhomirov@542: 		private final int s1Len;
tikhomirov@542: 		private final int s2Start;
tikhomirov@542: 		private final int s2Len;
tikhomirov@543: 		private final int s1InsertPoint;
tikhomirov@543: 		private final int s2DeletePoint;
tikhomirov@554: 		private FilterBlock addedBlock, removedBlock;
tikhomirov@542: 
tikhomirov@554: 		public ChangeBlockImpl(ContentBlock c1, ContentBlock c2, int s1Start, int s1Len, int s2Start, int s2Len, int s1InsertPoint, int s2DeletePoint) {
tikhomirov@554: 			oldContent = c1;
tikhomirov@554: 			newContent = c2;
tikhomirov@542: 			this.s1Start = s1Start;
tikhomirov@542: 			this.s1Len = s1Len;
tikhomirov@542: 			this.s2Start = s2Start;
tikhomirov@542: 			this.s2Len = s2Len;
tikhomirov@543: 			this.s1InsertPoint = s1InsertPoint;
tikhomirov@543: 			this.s2DeletePoint = s2DeletePoint;
tikhomirov@543: 		}
tikhomirov@543: 		
tikhomirov@543: 		public int insertedAt() {
tikhomirov@543: 			return s1InsertPoint;
tikhomirov@542: 		}
tikhomirov@542: 
tikhomirov@542: 		public int firstAddedLine() {
tikhomirov@542: 			return s2Start;
tikhomirov@542: 		}
tikhomirov@542: 
tikhomirov@542: 		public int totalAddedLines() {
tikhomirov@542: 			return s2Len;
tikhomirov@542: 		}
tikhomirov@542: 
tikhomirov@554: 		public BlockData addedLines() {
tikhomirov@554: 			if (addedBlock == null) {
tikhomirov@554: 				addedBlock = new FilterBlock(newContent, firstAddedLine(), totalAddedLines());
tikhomirov@554: 			}
tikhomirov@554: 			return addedBlock;
tikhomirov@542: 		}
tikhomirov@543: 		
tikhomirov@543: 		public int removedAt() {
tikhomirov@543: 			return s2DeletePoint;
tikhomirov@543: 		}
tikhomirov@542: 
tikhomirov@542: 		public int firstRemovedLine() {
tikhomirov@542: 			return s1Start;
tikhomirov@542: 		}
tikhomirov@542: 
tikhomirov@542: 		public int totalRemovedLines() {
tikhomirov@542: 			return s1Len;
tikhomirov@542: 		}
tikhomirov@542: 
tikhomirov@554: 		public BlockData removedLines() {
tikhomirov@554: 			if (removedBlock == null) {
tikhomirov@554: 				removedBlock = new FilterBlock(oldContent, firstRemovedLine(), totalRemovedLines());
tikhomirov@542: 			}
tikhomirov@554: 			return removedBlock;
tikhomirov@542: 		}
tikhomirov@545: 		
tikhomirov@545: 		@Override
tikhomirov@545: 		public String toString() {
tikhomirov@545: 			if (s2DeletePoint == -1) {
tikhomirov@545: 				return String.format("@@ -%d,0 +%d,%d @@", insertedAt(), firstAddedLine(), totalAddedLines());
tikhomirov@545: 			} else if (s1InsertPoint == -1) {
tikhomirov@545: 				// delete only
tikhomirov@545: 				return String.format("@@ -%d,%d +%d,0 @@", firstRemovedLine(), totalRemovedLines(), removedAt());
tikhomirov@545: 			}
tikhomirov@545: 			return String.format("@@ -%d,%d +%d,%d @@", firstRemovedLine(), totalRemovedLines(), firstAddedLine(), totalAddedLines());
tikhomirov@545: 		}
tikhomirov@542: 	}
tikhomirov@554: 	
tikhomirov@554: 	private static class SingleLine implements BlockData {
tikhomirov@554: 		private final ByteChain line;
tikhomirov@554: 
tikhomirov@554: 		public SingleLine(ByteChain lineContent) {
tikhomirov@554: 			line = lineContent;
tikhomirov@554: 		}
tikhomirov@554: 
tikhomirov@554: 		public BlockData elementAt(int index) {
tikhomirov@554: 			assert false;
tikhomirov@554: 			return null;
tikhomirov@554: 		}
tikhomirov@554: 
tikhomirov@554: 		public int elementCount() {
tikhomirov@554: 			return 0;
tikhomirov@554: 		}
tikhomirov@554: 
tikhomirov@554: 		public byte[] asArray() {
tikhomirov@554: 			return line.data();
tikhomirov@554: 		}
tikhomirov@554: 	}
tikhomirov@554: 	
tikhomirov@554: 	private static class ContentBlock implements BlockData {
tikhomirov@554: 		private final LineSequence seq;
tikhomirov@554: 
tikhomirov@554: 		public ContentBlock(LineSequence sequence) {
tikhomirov@554: 			seq = sequence;
tikhomirov@554: 		}
tikhomirov@554: 
tikhomirov@554: 		public BlockData elementAt(int index) {
tikhomirov@554: 			return new SingleLine(seq.chunk(index));
tikhomirov@554: 		}
tikhomirov@554: 
tikhomirov@554: 		public int elementCount() {
tikhomirov@554: 			return seq.chunkCount() - 1;
tikhomirov@554: 		}
tikhomirov@554: 
tikhomirov@554: 		public byte[] asArray() {
tikhomirov@554: 			return seq.data(0, seq.chunkCount() - 1);
tikhomirov@554: 		}
tikhomirov@554: 	}
tikhomirov@554: 	
tikhomirov@554: 	private static class FilterBlock implements BlockData {
tikhomirov@554: 		private final ContentBlock contentBlock;
tikhomirov@554: 		private final int from;
tikhomirov@554: 		private final int length;
tikhomirov@554: 
tikhomirov@554: 		public FilterBlock(ContentBlock bd, int startFrom, int len) {
tikhomirov@554: 			assert bd != null;
tikhomirov@554: 			assert startFrom + len < bd.seq.chunkCount(); // there's one extra chunk in the end, so strict less is ok
tikhomirov@554: 			contentBlock = bd;
tikhomirov@554: 			from = startFrom;
tikhomirov@554: 			length = len;
tikhomirov@554: 		}
tikhomirov@554: 
tikhomirov@554: 		public BlockData elementAt(int index) {
tikhomirov@554: 			if (index < 0 || index >= length) {
tikhomirov@554: 				throw new IllegalArgumentException(String.format("Expected value from [0..%d), got %d", length, index));
tikhomirov@554: 			}
tikhomirov@554: 			return contentBlock.elementAt(from + index);
tikhomirov@554: 		}
tikhomirov@554: 
tikhomirov@554: 		public int elementCount() {
tikhomirov@554: 			return length;
tikhomirov@554: 		}
tikhomirov@554: 
tikhomirov@554: 		public byte[] asArray() {
tikhomirov@554: 			return contentBlock.seq.data(from, from + length);
tikhomirov@554: 		}
tikhomirov@554: 	}
tikhomirov@554: 	
tikhomirov@549: 
tikhomirov@551: 	static class EqualBlocksCollector implements DiffHelper.MatchInspector<LineSequence> {
tikhomirov@549: 		private final IntVector matches = new IntVector(10*3, 2*3);
tikhomirov@549: 
tikhomirov@549: 		public void begin(LineSequence s1, LineSequence s2) {
tikhomirov@549: 		}
tikhomirov@549: 
tikhomirov@549: 		public void match(int startSeq1, int startSeq2, int matchLength) {
tikhomirov@549: 			matches.add(startSeq1);
tikhomirov@549: 			matches.add(startSeq2);
tikhomirov@549: 			matches.add(matchLength);
tikhomirov@549: 		}
tikhomirov@549: 
tikhomirov@549: 		public void end() {
tikhomirov@549: 		}
tikhomirov@549: 		
tikhomirov@549: 		// true when specified line in origin is equal to a line in target
tikhomirov@549: 		public boolean includesOriginLine(int ln) {
tikhomirov@549: 			return includes(ln, 0);
tikhomirov@549: 		}
tikhomirov@549: 		
tikhomirov@549: 		// true when specified line in target is equal to a line in origin
tikhomirov@549: 		public boolean includesTargetLine(int ln) {
tikhomirov@549: 			return includes(ln, 1);
tikhomirov@549: 		}
tikhomirov@549: 		
tikhomirov@549: 		public void intersectWithTarget(int start, int length, IntVector result) {
tikhomirov@549: 			int s = start;
tikhomirov@549: 			for (int l = start, x = start + length; l < x; l++) {
tikhomirov@549: 				if (!includesTargetLine(l)) {
tikhomirov@549: 					if (l - s > 0) {
tikhomirov@549: 						result.add(s);
tikhomirov@549: 						result.add(l - s);
tikhomirov@549: 					}
tikhomirov@549: 					s = l+1;
tikhomirov@549: 				}
tikhomirov@549: 			}
tikhomirov@549: 			if (s < start+length) {
tikhomirov@549: 				result.add(s);
tikhomirov@549: 				result.add((start + length) - s);
tikhomirov@549: 			}
tikhomirov@549: 		}
tikhomirov@549: 		
tikhomirov@549: 		/*
tikhomirov@549: 		 * intersects [start..start+length) with ranges of target lines, and based on the intersection 
tikhomirov@549: 		 * breaks initial range into smaller ranges and records them into result, with marker to indicate
tikhomirov@549: 		 * whether the range is from initial range (markerSource) or is a result of the intersection with target
tikhomirov@549: 		 * (markerTarget)
tikhomirov@549: 		 */
tikhomirov@549: 		public void combineAndMarkRangesWithTarget(int start, int length, int markerSource, int markerTarget, IntVector result) {
tikhomirov@549: 			int sourceStart = start, targetStart = start, sourceEnd = start + length;
tikhomirov@549: 			for (int l = sourceStart; l < sourceEnd; l++) {
tikhomirov@549: 				if (includesTargetLine(l)) {
tikhomirov@549: 					// l is from target
tikhomirov@549: 					if (sourceStart < l) {
tikhomirov@549: 						// few lines from source range were not in the target, report them
tikhomirov@549: 						result.add(markerSource);
tikhomirov@549: 						result.add(sourceStart);
tikhomirov@549: 						result.add(l - sourceStart);
tikhomirov@549: 					}
tikhomirov@549: 					// indicate the earliest line from source range to use
tikhomirov@549: 					sourceStart = l + 1;
tikhomirov@549: 				} else {
tikhomirov@549: 					// l is not in target
tikhomirov@549: 					if (targetStart < l) {
tikhomirov@549: 						// report lines from target range
tikhomirov@549: 						result.add(markerTarget);
tikhomirov@549: 						result.add(targetStart);
tikhomirov@549: 						result.add(l - targetStart);
tikhomirov@549: 					}
tikhomirov@549: 					// next line *may* be from target
tikhomirov@549: 					targetStart = l + 1;
tikhomirov@549: 				}
tikhomirov@549: 			}
tikhomirov@549: 			// if source range end with line from target, sourceStart would be == sourceEnd, and we need to add range with markerTarget
tikhomirov@549: 			// if source range doesn't end with target line, targetStart == sourceEnd, while sourceStart < sourceEnd
tikhomirov@549: 			if (sourceStart < sourceEnd) {
tikhomirov@549: 				assert targetStart == sourceEnd;
tikhomirov@549: 				// something left from the source range
tikhomirov@549: 				result.add(markerSource);
tikhomirov@549: 				result.add(sourceStart);
tikhomirov@549: 				result.add(sourceEnd - sourceStart);
tikhomirov@549: 			} else if (targetStart < sourceEnd) {
tikhomirov@549: 				assert sourceStart == sourceEnd;
tikhomirov@549: 				result.add(markerTarget);
tikhomirov@549: 				result.add(targetStart);
tikhomirov@549: 				result.add(sourceEnd - targetStart);
tikhomirov@549: 			}
tikhomirov@549: 		}
tikhomirov@549: 		
tikhomirov@549: 		private boolean includes(int ln, int o) {
tikhomirov@549: 			for (int i = 2; i < matches.size(); o += 3, i+=3) {
tikhomirov@549: 				int rangeStart = matches.get(o);
tikhomirov@549: 				if (rangeStart > ln) {
tikhomirov@549: 					return false;
tikhomirov@549: 				}
tikhomirov@549: 				int rangeLen = matches.get(i);
tikhomirov@549: 				if (rangeStart + rangeLen > ln) {
tikhomirov@549: 					return true;
tikhomirov@549: 				}
tikhomirov@549: 			}
tikhomirov@549: 			return false;
tikhomirov@549: 		}
tikhomirov@549: 	}
tikhomirov@549: 
tikhomirov@549: 	public static void main(String[] args) {
tikhomirov@549: 		EqualBlocksCollector bc = new EqualBlocksCollector();
tikhomirov@549: 		bc.match(-1, 5, 3);
tikhomirov@549: 		bc.match(-1, 10, 2);
tikhomirov@549: 		bc.match(-1, 15, 3);
tikhomirov@549: 		bc.match(-1, 20, 3);
tikhomirov@549: 		assert !bc.includesTargetLine(4);
tikhomirov@549: 		assert bc.includesTargetLine(7);
tikhomirov@549: 		assert !bc.includesTargetLine(8);
tikhomirov@549: 		assert bc.includesTargetLine(10);
tikhomirov@549: 		assert !bc.includesTargetLine(12);
tikhomirov@549: 		IntVector r = new IntVector();
tikhomirov@549: 		bc.intersectWithTarget(7, 10, r);
tikhomirov@549: 		for (int i = 0; i < r.size(); i+=2) {
tikhomirov@549: 			System.out.printf("[%d..%d) ", r.get(i), r.get(i) + r.get(i+1));
tikhomirov@549: 		}
tikhomirov@549: 		System.out.println();
tikhomirov@549: 		r.clear();
tikhomirov@549: 		bc.combineAndMarkRangesWithTarget(0, 16, 508, 514, r);
tikhomirov@549: 		for (int i = 0; i < r.size(); i+=3) {
tikhomirov@549: 			System.out.printf("%d:[%d..%d)  ", r.get(i), r.get(i+1), r.get(i+1) + r.get(i+2));
tikhomirov@549: 		}
tikhomirov@549: 	}
tikhomirov@542: }