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 pg = new DiffHelper(); 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 queue = new LinkedList(); 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 pg = new DiffHelper(); 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 pg = new DiffHelper(); 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> lruCache; tikhomirov@552: private final int limit; tikhomirov@552: private IntMap fileToClogIndexMap = new IntMap(20); tikhomirov@552: tikhomirov@552: public FileLinesCache(HgDataFile file, int lruLimit) { tikhomirov@552: df = file; tikhomirov@552: limit = lruLimit; tikhomirov@552: lruCache = new LinkedList>(); 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 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(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 checkCache(int fileRevIndex) { tikhomirov@552: Pair rv = null; tikhomirov@552: for (ListIterator> it = lruCache.listIterator(); it.hasNext(); ) { tikhomirov@552: Pair 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: *
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: 	 * 
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 { 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 { 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: }