tikhomirov@546: /*
tikhomirov@546:  * Copyright (c) 2013 TMate Software Ltd
tikhomirov@546:  *  
tikhomirov@546:  * This program is free software; you can redistribute it and/or modify
tikhomirov@546:  * it under the terms of the GNU General Public License as published by
tikhomirov@546:  * the Free Software Foundation; version 2 of the License.
tikhomirov@546:  *
tikhomirov@546:  * This program is distributed in the hope that it will be useful,
tikhomirov@546:  * but WITHOUT ANY WARRANTY; without even the implied warranty of
tikhomirov@546:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
tikhomirov@546:  * GNU General Public License for more details.
tikhomirov@546:  *
tikhomirov@546:  * For information on how to redistribute this software under
tikhomirov@546:  * the terms of a license other than GNU General Public License
tikhomirov@546:  * contact TMate Software at support@hg4j.com
tikhomirov@546:  */
tikhomirov@548: package org.tmatesoft.hg.internal;
tikhomirov@546: 
tikhomirov@557: import java.util.Formatter;
tikhomirov@546: 
tikhomirov@555: import org.tmatesoft.hg.core.HgIterateDirection;
tikhomirov@556: import org.tmatesoft.hg.repo.HgBlameFacility;
tikhomirov@557: import org.tmatesoft.hg.repo.HgInvalidStateException;
tikhomirov@557: import org.tmatesoft.hg.repo.HgBlameFacility.AddBlock;
tikhomirov@557: import org.tmatesoft.hg.repo.HgBlameFacility.BlockData;
tikhomirov@557: import org.tmatesoft.hg.repo.HgBlameFacility.ChangeBlock;
tikhomirov@557: import org.tmatesoft.hg.repo.HgBlameFacility.DeleteBlock;
tikhomirov@557: import org.tmatesoft.hg.repo.HgBlameFacility.EqualBlock;
tikhomirov@557: import org.tmatesoft.hg.repo.HgBlameFacility.RevisionDescriptor;
tikhomirov@555: import org.tmatesoft.hg.repo.HgDataFile;
tikhomirov@546: 
tikhomirov@546: /**
tikhomirov@555:  * Produce output like 'hg annotate' does
tikhomirov@546:  * 
tikhomirov@546:  * @author Artem Tikhomirov
tikhomirov@546:  * @author TMate Software Ltd.
tikhomirov@546:  */
tikhomirov@556: public class FileAnnotation implements HgBlameFacility.BlockInspector, RevisionDescriptor.Recipient {
tikhomirov@546: 
tikhomirov@555: 	@Experimental(reason="The line-by-line inspector likely to become part of core/command API")
tikhomirov@555: 	@Callback
tikhomirov@555: 	public interface LineInspector {
tikhomirov@555: 		/**
tikhomirov@555: 		 * Not necessarily invoked sequentially by line numbers
tikhomirov@555: 		 */
tikhomirov@557: 		void line(int lineNumber, int changesetRevIndex, BlockData lineContent, LineDescriptor ld);
tikhomirov@555: 	}
tikhomirov@555: 
tikhomirov@555: 	public interface LineDescriptor {
tikhomirov@555: 		int totalLines();
tikhomirov@555: 	}
tikhomirov@555: 
tikhomirov@555: 	/**
tikhomirov@555: 	 * Annotate file revision, line by line.
tikhomirov@555: 	 */
tikhomirov@555: 	public static void annotate(HgDataFile df, int changelogRevisionIndex, LineInspector insp) {
tikhomirov@555: 		if (!df.exists()) {
tikhomirov@555: 			return;
tikhomirov@555: 		}
tikhomirov@555: 		FileAnnotation fa = new FileAnnotation(insp);
tikhomirov@556: 		HgBlameFacility af = new HgBlameFacility();
tikhomirov@555: 		af.annotate(df, changelogRevisionIndex, fa, HgIterateDirection.NewToOld);
tikhomirov@555: 	}
tikhomirov@555: 
tikhomirov@557: 	// keeps <startSeq1, startSeq2, len> of equal blocks, origin to target, from some previous step
tikhomirov@557: 	private RangeSeq activeEquals;
tikhomirov@555: 	// equal blocks of the current iteration, to be recalculated before next step
tikhomirov@555: 	// to track line number (current target to ultimate target) mapping 
tikhomirov@557: 	private RangeSeq intermediateEquals = new RangeSeq();
tikhomirov@555: 
tikhomirov@555: 	private boolean[] knownLines;
tikhomirov@555: 	private final LineInspector delegate;
tikhomirov@557: 	private RevisionDescriptor revisionDescriptor;
tikhomirov@557: 	private BlockData lineContent;
tikhomirov@557: 
tikhomirov@557: 	private IntMap<RangeSeq> mergedRanges = new IntMap<RangeSeq>(10);
tikhomirov@557: 	private IntMap<RangeSeq> equalRanges = new IntMap<RangeSeq>(10);
tikhomirov@557: 	private boolean activeEqualsComesFromMerge = false;
tikhomirov@555: 
tikhomirov@555: 	public FileAnnotation(LineInspector lineInspector) {
tikhomirov@555: 		delegate = lineInspector;
tikhomirov@555: 	}
tikhomirov@555: 
tikhomirov@555: 	public void start(RevisionDescriptor rd) {
tikhomirov@557: 		revisionDescriptor = rd;
tikhomirov@555: 		if (knownLines == null) {
tikhomirov@557: 			lineContent = rd.target();
tikhomirov@557: 			knownLines = new boolean[lineContent.elementCount()];
tikhomirov@557: 			activeEquals = new RangeSeq();
tikhomirov@557: 			activeEquals.add(0, 0, knownLines.length);
tikhomirov@557: 			equalRanges.put(rd.targetChangesetIndex(), activeEquals);
tikhomirov@557: 		} else {
tikhomirov@557: 			activeEquals = equalRanges.get(rd.targetChangesetIndex());
tikhomirov@557: 			if (activeEquals == null) {
tikhomirov@557: 				// we didn't see this target revision as origin yet
tikhomirov@557: 				// the only way this may happen is that this revision was a merge parent
tikhomirov@557: 				activeEquals = mergedRanges.get(rd.targetChangesetIndex());
tikhomirov@557: 				activeEqualsComesFromMerge = true;
tikhomirov@557: 				if (activeEquals == null) {
tikhomirov@557: 					throw new HgInvalidStateException(String.format("Can't find previously visited revision %d (while in %d->%1$d diff)", rd.targetChangesetIndex(), rd.originChangesetIndex()));
tikhomirov@557: 				}
tikhomirov@557: 			}
tikhomirov@555: 		}
tikhomirov@555: 	}
tikhomirov@555: 
tikhomirov@557: 	public void done(RevisionDescriptor rd) {
tikhomirov@557: 		// update line numbers of the intermediate target to point to ultimate target's line numbers
tikhomirov@557: 		RangeSeq v = intermediateEquals.intersect(activeEquals);
tikhomirov@557: 		if (activeEqualsComesFromMerge) {
tikhomirov@557: 			mergedRanges.put(rd.originChangesetIndex(), v);
tikhomirov@557: 		} else {
tikhomirov@557: 			equalRanges.put(rd.originChangesetIndex(), v);
tikhomirov@557: 		}
tikhomirov@557: 		intermediateEquals.clear();
tikhomirov@557: 		activeEquals = null;
tikhomirov@557: 		activeEqualsComesFromMerge = false;
tikhomirov@557: 		revisionDescriptor = null;
tikhomirov@557: 	}
tikhomirov@555: 
tikhomirov@557: 	public void same(EqualBlock block) {
tikhomirov@557: 		intermediateEquals.add(block.originStart(), block.targetStart(), block.length());
tikhomirov@557: 	}
tikhomirov@557: 
tikhomirov@557: 	public void added(AddBlock block) {
tikhomirov@557: 		RangeSeq rs = null;
tikhomirov@557: 		if (revisionDescriptor.isMerge() && block.originChangesetIndex() == revisionDescriptor.mergeChangesetIndex()) {
tikhomirov@557: 			rs = mergedRanges.get(revisionDescriptor.mergeChangesetIndex());
tikhomirov@557: 			if (rs == null) {
tikhomirov@557: 				mergedRanges.put(revisionDescriptor.mergeChangesetIndex(), rs = new RangeSeq());
tikhomirov@557: 			}
tikhomirov@557: 		}
tikhomirov@557: 		if (activeEquals.size() == 0) {
tikhomirov@557: 			return;
tikhomirov@557: 		}
tikhomirov@557: 		for (int i = 0, ln = block.firstAddedLine(), x = block.totalAddedLines(); i < x; i++, ln++) {
tikhomirov@557: 			int lnInFinal = activeEquals.mapLineIndex(ln);
tikhomirov@557: 			if (lnInFinal != -1/* && !knownLines[lnInFinal]*/) {
tikhomirov@557: 				if (rs != null) {
tikhomirov@557: 					rs.add(block.insertedAt() + i, lnInFinal, 1);
tikhomirov@557: 				} else {
tikhomirov@557: 					delegate.line(lnInFinal, block.targetChangesetIndex(), lineContent.elementAt(lnInFinal), new LineDescriptorImpl());
tikhomirov@557: 				}
tikhomirov@557: 				knownLines[lnInFinal] = true;
tikhomirov@557: 			}
tikhomirov@557: 		}
tikhomirov@557: 	}
tikhomirov@557: 
tikhomirov@557: 	public void changed(ChangeBlock block) {
tikhomirov@557: 		added(block);
tikhomirov@557: 	}
tikhomirov@557: 
tikhomirov@557: 	public void deleted(DeleteBlock block) {
tikhomirov@557: 	}
tikhomirov@557: 
tikhomirov@557: 	private final class LineDescriptorImpl implements LineDescriptor {
tikhomirov@557: 		LineDescriptorImpl() {
tikhomirov@557: 		}
tikhomirov@557: 
tikhomirov@557: 		public int totalLines() {
tikhomirov@557: 			return FileAnnotation.this.knownLines.length;
tikhomirov@557: 		}
tikhomirov@557: 	}
tikhomirov@557: 
tikhomirov@557: 	private static class RangeSeq {
tikhomirov@557: 		// XXX smth like IntSliceVector to access triples (or slices of any size, in fact)
tikhomirov@557: 		// with easy indexing, e.g. #get(sliceIndex, indexWithinSlice)
tikhomirov@557: 		// and vect.get(7,2) instead of vect.get(7*SIZEOF_SLICE+2)
tikhomirov@557: 		private final IntVector ranges = new IntVector(3*10, 3*5);
tikhomirov@557: 		private int count;
tikhomirov@557: 		
tikhomirov@557: 		public void add(int start1, int start2, int length) {
tikhomirov@557: 			if (count > 0) {
tikhomirov@557: 				int lastIndex = 3 * (count-1);
tikhomirov@557: 				int lastS1 = ranges.get(lastIndex);
tikhomirov@557: 				int lastS2 = ranges.get(lastIndex + 1);
tikhomirov@557: 				int lastLen = ranges.get(lastIndex + 2);
tikhomirov@557: 				if (start1 == lastS1 + lastLen && start2 == lastS2 + lastLen) {
tikhomirov@557: 					// new range continues the previous one - just increase the length
tikhomirov@557: 					ranges.set(lastIndex + 2, lastLen + length);
tikhomirov@557: 					return;
tikhomirov@557: 				}
tikhomirov@557: 			}
tikhomirov@557: 			ranges.add(start1, start2, length);
tikhomirov@557: 			count++;
tikhomirov@557: 		}
tikhomirov@557: 		
tikhomirov@557: 		public void clear() {
tikhomirov@557: 			ranges.clear();
tikhomirov@557: 			count = 0;
tikhomirov@557: 		}
tikhomirov@557: 
tikhomirov@557: 		public int size() {
tikhomirov@557: 			return count;
tikhomirov@557: 		}
tikhomirov@557: 
tikhomirov@557: 		public int mapLineIndex(int ln) {
tikhomirov@557: 			for (int i = 0; i < ranges.size(); i += 3) {
tikhomirov@557: 				int s1 = ranges.get(i);
tikhomirov@557: 				if (s1 > ln) {
tikhomirov@557: 					return -1;
tikhomirov@557: 				}
tikhomirov@557: 				int l = ranges.get(i+2);
tikhomirov@557: 				if (s1 + l > ln) {
tikhomirov@557: 					int s2 = ranges.get(i + 1);
tikhomirov@557: 					return s2 + (ln - s1);
tikhomirov@557: 				}
tikhomirov@557: 			}
tikhomirov@557: 			return -1;
tikhomirov@557: 		}
tikhomirov@557: 		
tikhomirov@557: 		public RangeSeq intersect(RangeSeq target) {
tikhomirov@557: 			RangeSeq v = new RangeSeq();
tikhomirov@557: 			for (int i = 0; i < ranges.size(); i += 3) {
tikhomirov@557: 				int originLine = ranges.get(i);
tikhomirov@557: 				int targetLine = ranges.get(i + 1);
tikhomirov@557: 				int length = ranges.get(i + 2);
tikhomirov@555: 				int startTargetLine = -1, startOriginLine = -1, c = 0;
tikhomirov@555: 				for (int j = 0; j < length; j++) {
tikhomirov@557: 					int lnInFinal = target.mapLineIndex(targetLine + j);
tikhomirov@555: 					if (lnInFinal == -1 || (startTargetLine != -1 && lnInFinal != startTargetLine + c)) {
tikhomirov@555: 						// the line is not among "same" in ultimate origin
tikhomirov@555: 						// or belongs to another/next "same" chunk 
tikhomirov@555: 						if (startOriginLine == -1) {
tikhomirov@555: 							continue;
tikhomirov@546: 						}
tikhomirov@557: 						v.add(startOriginLine, startTargetLine, c);
tikhomirov@555: 						c = 0;
tikhomirov@555: 						startOriginLine = startTargetLine = -1;
tikhomirov@555: 						// fall-through to check if it's not complete miss but a next chunk
tikhomirov@555: 					}
tikhomirov@555: 					if (lnInFinal != -1) {
tikhomirov@555: 						if (startOriginLine == -1) {
tikhomirov@555: 							startOriginLine = originLine + j;
tikhomirov@555: 							startTargetLine = lnInFinal;
tikhomirov@555: 							c = 1;
tikhomirov@555: 						} else {
tikhomirov@557: 							// lnInFinal != startTargetLine + s is covered above
tikhomirov@555: 							assert lnInFinal == startTargetLine + c;
tikhomirov@555: 							c++;
tikhomirov@555: 						}
tikhomirov@546: 					}
tikhomirov@546: 				}
tikhomirov@555: 				if (startOriginLine != -1) {
tikhomirov@555: 					assert c > 0;
tikhomirov@557: 					v.add(startOriginLine, startTargetLine, c);
tikhomirov@546: 				}
tikhomirov@546: 			}
tikhomirov@557: 			return v;
tikhomirov@555: 		}
tikhomirov@557: 		
tikhomirov@557: 		@SuppressWarnings("unused")
tikhomirov@557: 		public CharSequence dump() {
tikhomirov@557: 			StringBuilder sb = new StringBuilder();
tikhomirov@557: 			Formatter f = new Formatter(sb);
tikhomirov@557: 			for (int i = 0; i < ranges.size(); i += 3) {
tikhomirov@557: 				int s1 = ranges.get(i);
tikhomirov@557: 				int s2 = ranges.get(i + 1);
tikhomirov@557: 				int len = ranges.get(i + 2);
tikhomirov@557: 				f.format("[%d..%d) == [%d..%d);  ", s1, s1 + len, s2, s2 + len);
tikhomirov@555: 			}
tikhomirov@557: 			return sb;
tikhomirov@555: 		}
tikhomirov@557: 		
tikhomirov@557: 		@Override
tikhomirov@557: 		public String toString() {
tikhomirov@557: 			return String.format("RangeSeq[%d]:%s", count, dump());
tikhomirov@546: 		}
tikhomirov@555: 	}
tikhomirov@555: }