# HG changeset patch # User Artem Tikhomirov # Date 1376484711 -7200 # Node ID 7839ff0bfd7858e8d2c7e5270f34a80a62afcc45 # Parent 992fa84e78857b4ff3ebe56f43b5d76972d61556 Refactor: move diff/blame related code to a separate package diff -r 992fa84e7885 -r 7839ff0bfd78 src/org/tmatesoft/hg/core/HgAnnotateCommand.java --- a/src/org/tmatesoft/hg/core/HgAnnotateCommand.java Thu Aug 08 21:32:22 2013 +0200 +++ b/src/org/tmatesoft/hg/core/HgAnnotateCommand.java Wed Aug 14 14:51:51 2013 +0200 @@ -20,7 +20,7 @@ import org.tmatesoft.hg.internal.Callback; import org.tmatesoft.hg.internal.CsetParamKeeper; -import org.tmatesoft.hg.internal.ForwardAnnotateInspector; +import org.tmatesoft.hg.internal.diff.ForwardAnnotateInspector; import org.tmatesoft.hg.repo.HgDataFile; import org.tmatesoft.hg.repo.HgRepository; import org.tmatesoft.hg.repo.HgRuntimeException; diff -r 992fa84e7885 -r 7839ff0bfd78 src/org/tmatesoft/hg/core/HgDiffCommand.java --- a/src/org/tmatesoft/hg/core/HgDiffCommand.java Thu Aug 08 21:32:22 2013 +0200 +++ b/src/org/tmatesoft/hg/core/HgDiffCommand.java Wed Aug 14 14:51:51 2013 +0200 @@ -19,10 +19,10 @@ import static org.tmatesoft.hg.repo.HgRepository.NO_REVISION; import static org.tmatesoft.hg.repo.HgRepository.TIP; -import org.tmatesoft.hg.internal.BlameHelper; import org.tmatesoft.hg.internal.CsetParamKeeper; import org.tmatesoft.hg.internal.FileHistory; import org.tmatesoft.hg.internal.FileRevisionHistoryChunk; +import org.tmatesoft.hg.internal.diff.BlameHelper; import org.tmatesoft.hg.repo.HgDataFile; import org.tmatesoft.hg.repo.HgRepository; import org.tmatesoft.hg.repo.HgRuntimeException; diff -r 992fa84e7885 -r 7839ff0bfd78 src/org/tmatesoft/hg/internal/BlameHelper.java --- a/src/org/tmatesoft/hg/internal/BlameHelper.java Thu Aug 08 21:32:22 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,967 +0,0 @@ -/* - * Copyright (c) 2013 TMate Software Ltd - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; version 2 of the License. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * For information on how to redistribute this software under - * the terms of a license other than GNU General Public License - * contact TMate Software at support@hg4j.com - */ -package org.tmatesoft.hg.internal; - -import static org.tmatesoft.hg.core.HgIterateDirection.OldToNew; -import static org.tmatesoft.hg.repo.HgRepository.NO_REVISION; - -import java.util.ArrayList; -import java.util.Arrays; -import java.util.Iterator; -import java.util.LinkedList; -import java.util.List; -import java.util.ListIterator; - -import org.tmatesoft.hg.core.HgCallbackTargetException; -import org.tmatesoft.hg.core.Nodeid; -import org.tmatesoft.hg.internal.DiffHelper.LineSequence; -import org.tmatesoft.hg.internal.DiffHelper.LineSequence.ByteChain; -import org.tmatesoft.hg.internal.diff.DiffRangeMap; -import org.tmatesoft.hg.internal.diff.DiffRangeMap.RangePair; -import org.tmatesoft.hg.core.HgBlameInspector; -import org.tmatesoft.hg.core.HgBlameInspector.*; -import org.tmatesoft.hg.repo.HgChangelog; -import org.tmatesoft.hg.repo.HgDataFile; -import org.tmatesoft.hg.repo.HgInvalidStateException; -import org.tmatesoft.hg.repo.HgParentChildMap; -import org.tmatesoft.hg.repo.HgRepository; -import org.tmatesoft.hg.repo.HgRevisionMap; -import org.tmatesoft.hg.repo.HgRuntimeException; -import org.tmatesoft.hg.util.Adaptable; -import org.tmatesoft.hg.util.CancelledException; -import org.tmatesoft.hg.util.Pair; - -/** - * Blame implementation - * @see HgBlameInspector - * @author Artem Tikhomirov - * @author TMate Software Ltd. - */ -public class BlameHelper { - - private final HgBlameInspector insp; - private FileLinesCache linesCache; - private HgParentChildMap clogMap; - - public BlameHelper(HgBlameInspector inspector) { - insp = inspector; - } - - /** - * Build history of the file for the specified range (follow renames if necessary). This history - * is used to access various file revision data during subsequent {@link #diff(int, int, int, int)} and - * {@link #annotateChange(int, int, int[], int[])} calls. Callers can use returned history for own approaches - * to iteration over file history. - - *

NOTE, clogRevIndexEnd has to list name of the supplied file in the corresponding manifest, - * as it's not possible to trace rename history otherwise. - */ - public FileHistory prepare(HgDataFile df, int clogRevIndexStart, int clogRevIndexEnd) throws HgRuntimeException { - assert clogRevIndexStart <= clogRevIndexEnd; - FileHistory fileHistory = new FileHistory(df, clogRevIndexStart, clogRevIndexEnd); - fileHistory.build(); - int cacheHint = 5; // cache comes useful when we follow merge branches and don't want to - // parse base revision twice. There's no easy way to determine max(distance(all(base,merge))), - // hence the heuristics to use the longest history chunk: - for (FileRevisionHistoryChunk c : fileHistory.iterate(OldToNew)) { - // iteration order is not important here - if (c.revisionCount() > cacheHint) { - cacheHint = c.revisionCount(); - } - } - linesCache = new FileLinesCache(cacheHint); - for (FileRevisionHistoryChunk fhc : fileHistory.iterate(OldToNew)) { - // iteration order is not important here - linesCache.useFileUpTo(fhc.getFile(), fhc.getEndChangeset()); - } - return fileHistory; - } - - // NO_REVISION is not allowed as any argument - public void diff(int fileRevIndex1, int clogRevIndex1, int fileRevIndex2, int clogRevIndex2) throws HgCallbackTargetException, HgRuntimeException { - HgDataFile targetFile = linesCache.getFile(clogRevIndex2); - LineSequence c1 = linesCache.lines(clogRevIndex1, fileRevIndex1); - LineSequence c2 = linesCache.lines(clogRevIndex2, fileRevIndex2); - DiffHelper pg = new DiffHelper(); - pg.init(c1, c2); - BlameBlockInspector bbi = new BlameBlockInspector(targetFile, fileRevIndex2, insp, clogRevIndex1, clogRevIndex2); - pg.findMatchingBlocks(bbi); - bbi.checkErrors(); - } - - public void annotateChange(int fileRevIndex, int csetRevIndex, int[] fileParentRevs, int[] fileParentClogRevs) throws HgCallbackTargetException, HgRuntimeException { - HgDataFile targetFile = linesCache.getFile(csetRevIndex); - final LineSequence fileRevLines = linesCache.lines(csetRevIndex, fileRevIndex); - if (fileParentClogRevs[0] != NO_REVISION && fileParentClogRevs[1] != NO_REVISION) { - int p1ClogIndex = fileParentClogRevs[0]; - int p2ClogIndex = fileParentClogRevs[1]; - LineSequence p1Lines = linesCache.lines(p1ClogIndex, fileParentRevs[0]); - LineSequence p2Lines = linesCache.lines(p2ClogIndex, fileParentRevs[1]); - MergeResolutionStrategy mergeResolver = createMergeStrategy(fileRevLines, p1Lines, p2Lines, csetRevIndex, fileParentClogRevs); - // - DiffHelper pg = new DiffHelper(); - pg.init(p1Lines, fileRevLines); - BlameBlockInspector bbi = new BlameBlockInspector(targetFile, fileRevIndex, insp, p1ClogIndex, csetRevIndex); - bbi.setMergeParent2(mergeResolver, p2ClogIndex); - pg.findMatchingBlocks(bbi); - bbi.checkErrors(); - } else if (fileParentClogRevs[0] == fileParentClogRevs[1]) { - // may be equal iff both are unset - assert fileParentClogRevs[0] == NO_REVISION; - // everything added - BlameBlockInspector bbi = new BlameBlockInspector(targetFile, fileRevIndex, insp, NO_REVISION, csetRevIndex); - bbi.begin(LineSequence.newlines(new byte[0]), fileRevLines); - bbi.match(0, fileRevLines.chunkCount()-1, 0); - bbi.end(); - bbi.checkErrors(); - } else { - int soleParentIndex = fileParentClogRevs[0] == NO_REVISION ? 1 : 0; - assert fileParentClogRevs[soleParentIndex] != NO_REVISION; - LineSequence parentLines = linesCache.lines(fileParentClogRevs[soleParentIndex], fileParentRevs[soleParentIndex]); - - DiffHelper pg = new DiffHelper(); - pg.init(parentLines, fileRevLines); - BlameBlockInspector bbi = new BlameBlockInspector(targetFile, fileRevIndex, insp, fileParentClogRevs[soleParentIndex], csetRevIndex); - pg.findMatchingBlocks(bbi); - bbi.checkErrors(); - } - } - - private static final boolean useNewStrategy = Boolean.TRUE.booleanValue(); - - private MergeResolutionStrategy createMergeStrategy(LineSequence fileRevLines, LineSequence p1Lines, LineSequence p2Lines, int csetRevIndex, int[] fileParentClogRevs) { - DiffHelper pg = new DiffHelper(); - if (useNewStrategy) { - final ArrayList allMatches = new ArrayList(); - pg.init(p2Lines, fileRevLines); - pg.findAllMatchAlternatives(new DiffHelper.MatchInspector() { - private RangePairSeq matches; - - public void begin(LineSequence s1, LineSequence s2) { - matches = new RangePairSeq(); - } - - public void match(int startSeq1, int startSeq2, int matchLength) { - matches.add(startSeq1, startSeq2, matchLength); - } - - public void end() { - if (matches.size() > 0) { - allMatches.add(matches); - } - } - - }); - // - LineSequence baseLines = getBaseRevisionLines(csetRevIndex, fileParentClogRevs); - pg.init(p1Lines, baseLines); - DiffRangeMap p1ToBase = new DiffRangeMap().fill(pg); - pg.init(baseLines, p2Lines); - DiffRangeMap baseToP2 = new DiffRangeMap().fill(pg); - return new MergeStrategy2(allMatches, p1ToBase, baseToP2); - } else { - pg.init(p2Lines, fileRevLines); - EqualBlocksCollector p2MergeCommon = new EqualBlocksCollector(); - pg.findMatchingBlocks(p2MergeCommon); - return new MergeStrategy1(p2MergeCommon.matches); - } - } - - private LineSequence getBaseRevisionLines(int clogRevIndex, int[] fileParentClogRevs) { - assert fileParentClogRevs[0] >= 0; - assert fileParentClogRevs[1] >= 0; - HgDataFile targetFile = linesCache.getFile(clogRevIndex); - final HgRepository repo = targetFile.getRepo(); - if (clogMap == null) { - // FIXME replace HgParentChildMap with revlog.indexWalk(AncestorIterator)) - clogMap = new HgParentChildMap(repo.getChangelog()); - clogMap.init(); - } - final HgRevisionMap m = clogMap.getRevisionMap(); - Nodeid ancestor = clogMap.ancestor(m.revision(fileParentClogRevs[0]), m.revision(fileParentClogRevs[1])); - final int ancestorRevIndex = m.revisionIndex(ancestor); - Nodeid fr = repo.getManifest().getFileRevision(ancestorRevIndex, targetFile.getPath()); - if (fr == null) { - return LineSequence.newlines(new byte[0]); - } - return linesCache.lines(ancestorRevIndex, targetFile.getRevisionIndex(fr)); - } - - private static class FileLinesCache { - private final LinkedList> lruCache; - private final int limit; - private final LinkedList> files; // TODO in fact, need sparse array - - /** - * @param lruLimit how many parsed file revisions to keep - */ - public FileLinesCache(int lruLimit) { - limit = lruLimit; - lruCache = new LinkedList>(); - files = new LinkedList>(); - } - - public void useFileUpTo(HgDataFile df, int clogRevIndex) { - Pair newEntry = new Pair(clogRevIndex, df); - for (ListIterator> it = files.listIterator(); it.hasNext();) { - Pair e = it.next(); - if (e.first() == clogRevIndex) { - assert e.second().getPath().equals(df.getPath()); - return; - } - if (e.first() > clogRevIndex) { - // insert new entry before current - it.previous(); - it.add(newEntry); - return; - } - } - files.add(newEntry); - } - - public HgDataFile getFile(int clogRevIndex) { - for (Pair e : files) { - if (e.first() >= clogRevIndex) { - return e.second(); - } - } - throw new HgInvalidStateException(String.format("Got %d file-changelog mappings, but no luck for revision %d.", files.size(), clogRevIndex)); - } - - public LineSequence lines(int clogRevIndex, int fileRevIndex) throws HgRuntimeException { - Pair cached = checkCache(clogRevIndex); - if (cached != null) { - return cached.second(); - } - HgDataFile df = getFile(clogRevIndex); - try { - ByteArrayChannel c; - df.content(fileRevIndex, c = new ByteArrayChannel()); - LineSequence rv = LineSequence.newlines(c.toArray()); - lruCache.addFirst(new Pair(clogRevIndex, rv)); - if (lruCache.size() > limit) { - lruCache.removeLast(); - } - return rv; - } catch (CancelledException ex) { - // TODO likely it was bad idea to throw cancelled exception from content() - // deprecate and provide alternative? - HgInvalidStateException ise = new HgInvalidStateException("ByteArrayChannel never throws CancelledException"); - ise.initCause(ex); - throw ise; - } - } - - private Pair checkCache(int fileRevIndex) { - Pair rv = null; - for (ListIterator> it = lruCache.listIterator(); it.hasNext(); ) { - Pair p = it.next(); - if (p.first() == fileRevIndex) { - rv = p; - it.remove(); - break; - } - } - if (rv != null) { - lruCache.addFirst(rv); - } - return rv; - } - } - - private static class BlameBlockInspector extends DiffHelper.DeltaInspector { - private final HgBlameInspector insp; - private final int csetOrigin; - private final int csetTarget; - private MergeResolutionStrategy p2MergeCommon; - private int csetMergeParent; - private final AnnotateRev annotatedRevision; - private HgCallbackTargetException error; - - public BlameBlockInspector(HgDataFile df, int fileRevIndex, HgBlameInspector inspector, int originCset, int targetCset) { - assert inspector != null; - insp = inspector; - annotatedRevision = new AnnotateRev(); - annotatedRevision.set(df, fileRevIndex); - csetOrigin = originCset; - csetTarget = targetCset; - } - - public void setMergeParent2(MergeResolutionStrategy p2MergeStrategy, int parentCset2) { - p2MergeCommon = p2MergeStrategy; - csetMergeParent = parentCset2; - } - - @Override - public void begin(LineSequence s1, LineSequence s2) { - super.begin(s1, s2); - if (shallStop()) { - return; - } - ContentBlock originContent = new ContentBlock(s1); - ContentBlock targetContent = new ContentBlock(s2); - annotatedRevision.set(originContent, targetContent); - annotatedRevision.set(csetOrigin, csetTarget, p2MergeCommon != null ? csetMergeParent : NO_REVISION); - RevisionDescriptor.Recipient curious = Adaptable.Factory.getAdapter(insp, RevisionDescriptor.Recipient.class, null); - if (curious != null) { - try { - curious.start(annotatedRevision); - } catch (HgCallbackTargetException ex) { - error = ex; - } - } - } - - @Override - public void end() { - super.end(); - if (shallStop()) { - return; - } - RevisionDescriptor.Recipient curious = Adaptable.Factory.getAdapter(insp, RevisionDescriptor.Recipient.class, null); - if (curious != null) { - try { - curious.done(annotatedRevision); - } catch (HgCallbackTargetException ex) { - error = ex; - } - } - p2MergeCommon = null; - } - - @Override - protected void changed(int s1From, int s1To, int s2From, int s2To) { - if (shallStop()) { - return; - } - try { - if (p2MergeCommon != null) { - IntSliceSeq mergeRanges = p2MergeCommon.combineAndMarkRangesWithSource(s1From, s1To, s2From, s2To, csetOrigin, csetMergeParent); - - /* - * Usecases, how it USED TO BE initially: - * 3 lines changed to 10 lines. range of 10 lines breaks down to 2 from p2, 3 from p1, and 5 from p2. - * We report: 2 lines changed to 2(p2), then 1 line changed with 3(p1) and 5 lines added from p2. - * - * 10 lines changed to 3 lines, range of 3 lines breaks down to 2 line from p1 and 1 line from p2. - * We report: 2 lines changed to 2(p1) and 8 lines changed to 1(p2) - * - * NOW, lines from p2 are always reported as pure add (since we need their insertion point to be in p2, not in p1) - * and we try to consume p1 changes as soon as we see first p1's range - */ - int s1TotalLines = s1To - s1From, s1ConsumedLines = 0, s1Start = s1From; - - for (Iterator it = mergeRanges.iterator(); it.hasNext();) { - IntTuple mergeRange = it.next(); - final int rangeOrigin = mergeRange.at(0); - final int rangeStart = mergeRange.at(1); - final int rangeLen = mergeRange.at(2); - final boolean lastRange = it.hasNext(); - final int s1LinesLeft = s1TotalLines - s1ConsumedLines; - // how many lines we may report as changed (don't use more than in range unless it's the very last range) - final int s1LinesToBorrow = lastRange ? s1LinesLeft : Math.min(s1LinesLeft, rangeLen); - if (rangeOrigin != csetMergeParent && s1LinesToBorrow > 0) { - ChangeBlockImpl block = getChangeBlock(s1Start, s1LinesToBorrow, rangeStart, rangeLen); - block.setOriginAndTarget(rangeOrigin, csetTarget); - insp.changed(block); - s1ConsumedLines += s1LinesToBorrow; - s1Start += s1LinesToBorrow; - } else { - int blockInsPoint = rangeOrigin != csetMergeParent ? s1Start : p2MergeCommon.getLineInP2(rangeStart); - ChangeBlockImpl block = getAddBlock(rangeStart, rangeLen, blockInsPoint); - block.setOriginAndTarget(rangeOrigin, csetTarget); - insp.added(block); - } - } - if (s1ConsumedLines != s1TotalLines) { - assert s1ConsumedLines < s1TotalLines : String.format("Expected to process %d lines, but actually was %d", s1TotalLines, s1ConsumedLines); - // either there were no ranges from p1, whole s2From..s2To range came from p2, shall report as deleted - // or the ranges found were not enough to consume whole s2From..s2To - // The "deletion point" is shifted to the end of last csetOrigin->csetTarget change - int s2DeletePoint = s2From + s1ConsumedLines; - ChangeBlockImpl block = new ChangeBlockImpl(annotatedRevision.origin, null, s1Start, s1To - s1Start, -1, -1, -1, s2DeletePoint); - block.setOriginAndTarget(csetOrigin, csetTarget); - insp.deleted(block); - } - } else { - ChangeBlockImpl block = getChangeBlock(s1From, s1To - s1From, s2From, s2To - s2From); - block.setOriginAndTarget(csetOrigin, csetTarget); - insp.changed(block); - } - } catch (HgCallbackTargetException ex) { - error = ex; - } - } - - @Override - protected void added(int s1InsertPoint, int s2From, int s2To) { - if (shallStop()) { - return; - } - try { - if (p2MergeCommon != null) { - IntSliceSeq mergeRanges = p2MergeCommon.combineAndMarkRangesWithSource(s1InsertPoint, s2From, s2To, csetOrigin, csetMergeParent); - int insPoint = s1InsertPoint; // track changes to insertion point - for (IntTuple mergeRange : mergeRanges) { - int rangeOrigin = mergeRange.at(0); - int rangeStart = mergeRange.at(1); - int rangeLen = mergeRange.at(2); - // XXX likely need somewhat similar to the code above: - // int blockInsPoint = rangeOrigin != csetMergeParent ? s1Start : p2MergeCommon.reverseMapLine(rangeStart); - // - ChangeBlockImpl block = getAddBlock(rangeStart, rangeLen, insPoint); - block.setOriginAndTarget(rangeOrigin, csetTarget); - insp.added(block); - // indicate insPoint moved down number of lines we just reported - insPoint += rangeLen; - } - } else { - ChangeBlockImpl block = getAddBlock(s2From, s2To - s2From, s1InsertPoint); - block.setOriginAndTarget(csetOrigin, csetTarget); - insp.added(block); - } - } catch (HgCallbackTargetException ex) { - error = ex; - } - } - - @Override - protected void deleted(int s2DeletePoint, int s1From, int s1To) { - if (shallStop()) { - return; - } - try { - ChangeBlockImpl block = new ChangeBlockImpl(annotatedRevision.origin, null, s1From, s1To - s1From, -1, -1, -1, s2DeletePoint); - block.setOriginAndTarget(csetOrigin, csetTarget); - insp.deleted(block); - } catch (HgCallbackTargetException ex) { - error = ex; - } - } - - @Override - protected void unchanged(int s1From, int s2From, int length) { - if (shallStop()) { - return; - } - try { - EqualBlockImpl block = new EqualBlockImpl(s1From, s2From, length, annotatedRevision.target); - block.setOriginAndTarget(csetOrigin, csetTarget); - insp.same(block); - } catch (HgCallbackTargetException ex) { - error = ex; - } - } - - void checkErrors() throws HgCallbackTargetException { - if (error != null) { - throw error; - } - } - - private boolean shallStop() { - return error != null; - } - - private ChangeBlockImpl getAddBlock(int start, int len, int insPoint) { - return new ChangeBlockImpl(null, annotatedRevision.target, -1, -1, start, len, insPoint, -1); - } - - private ChangeBlockImpl getChangeBlock(int start1, int len1, int start2, int len2) { - return new ChangeBlockImpl(annotatedRevision.origin, annotatedRevision.target, start1, len1, start2, len2, start1, start2); - } - } - - private static class BlockImpl implements Block { - private int originCset; - private int targetCset; - - void setOriginAndTarget(int originChangesetIndex, int targetChangesetIndex) { - // XXX perhaps, shall be part of Inspector API, rather than Block's - // as they don't change between blocks (although the moment about merged revisions) - // is not yet clear to me - originCset = originChangesetIndex; - targetCset = targetChangesetIndex; - } - - public int originChangesetIndex() { - return originCset; - } - - public int targetChangesetIndex() { - return targetCset; - } - } - - private static class EqualBlockImpl extends BlockImpl implements EqualBlock { - private final int start1, start2; - private final int length; - private final ContentBlock fullContent; - private FilterBlock myContent; - - EqualBlockImpl(int blockStartSeq1, int blockStartSeq2, int blockLength, ContentBlock targetContent) { - start1 = blockStartSeq1; - start2 = blockStartSeq2; - length = blockLength; - fullContent = targetContent; - } - - public int originStart() { - return start1; - } - - public int targetStart() { - return start2; - } - - public int length() { - return length; - } - - public BlockData content() { - if (myContent == null) { - myContent = new FilterBlock(fullContent, start2, length); - } - return myContent; - } - - @Override - public String toString() { - return String.format("@@ [%d..%d) == [%d..%d) @@", start1, start1+length, start2, start2+length); - } - } - - private static class ChangeBlockImpl extends BlockImpl implements ChangeBlock { - private final ContentBlock oldContent; - private final ContentBlock newContent; - private final int s1Start; - private final int s1Len; - private final int s2Start; - private final int s2Len; - private final int s1InsertPoint; - private final int s2DeletePoint; - private FilterBlock addedBlock, removedBlock; - - public ChangeBlockImpl(ContentBlock c1, ContentBlock c2, int s1Start, int s1Len, int s2Start, int s2Len, int s1InsertPoint, int s2DeletePoint) { - oldContent = c1; - newContent = c2; - this.s1Start = s1Start; - this.s1Len = s1Len; - this.s2Start = s2Start; - this.s2Len = s2Len; - this.s1InsertPoint = s1InsertPoint; - this.s2DeletePoint = s2DeletePoint; - } - - public int insertedAt() { - return s1InsertPoint; - } - - public int firstAddedLine() { - return s2Start; - } - - public int totalAddedLines() { - return s2Len; - } - - public BlockData addedLines() { - if (addedBlock == null) { - addedBlock = new FilterBlock(newContent, firstAddedLine(), totalAddedLines()); - } - return addedBlock; - } - - public int removedAt() { - return s2DeletePoint; - } - - public int firstRemovedLine() { - return s1Start; - } - - public int totalRemovedLines() { - return s1Len; - } - - public BlockData removedLines() { - if (removedBlock == null) { - removedBlock = new FilterBlock(oldContent, firstRemovedLine(), totalRemovedLines()); - } - return removedBlock; - } - - @Override - public String toString() { - if (s2DeletePoint == -1) { - return String.format("@@ -%d,0 +%d,%d @@", insertedAt(), firstAddedLine(), totalAddedLines()); - } else if (s1InsertPoint == -1) { - // delete only - return String.format("@@ -%d,%d +%d,0 @@", firstRemovedLine(), totalRemovedLines(), removedAt()); - } - return String.format("@@ -%d,%d +%d,%d @@", firstRemovedLine(), totalRemovedLines(), firstAddedLine(), totalAddedLines()); - } - } - - private static class SingleLine implements BlockData { - private final ByteChain line; - - public SingleLine(ByteChain lineContent) { - line = lineContent; - } - - public BlockData elementAt(int index) { - assert false; - return null; - } - - public int elementCount() { - return 0; - } - - public byte[] asArray() { - return line.data(); - } - } - - private static class ContentBlock implements BlockData { - private final LineSequence seq; - - public ContentBlock(LineSequence sequence) { - seq = sequence; - } - - public BlockData elementAt(int index) { - return new SingleLine(seq.chunk(index)); - } - - public int elementCount() { - return seq.chunkCount() - 1; - } - - public byte[] asArray() { - return seq.data(0, seq.chunkCount() - 1); - } - } - - private static class FilterBlock implements BlockData { - private final ContentBlock contentBlock; - private final int from; - private final int length; - - public FilterBlock(ContentBlock bd, int startFrom, int len) { - assert bd != null; - assert startFrom + len < bd.seq.chunkCount(); // there's one extra chunk in the end, so strict less is ok - contentBlock = bd; - from = startFrom; - length = len; - } - - public BlockData elementAt(int index) { - if (index < 0 || index >= length) { - throw new IllegalArgumentException(String.format("Expected value from [0..%d), got %d", length, index)); - } - return contentBlock.elementAt(from + index); - } - - public int elementCount() { - return length; - } - - public byte[] asArray() { - return contentBlock.seq.data(from, from + length); - } - } - - private static class EqualBlocksCollector implements DiffHelper.MatchInspector { - private final RangePairSeq matches = new RangePairSeq(); - - public void begin(LineSequence s1, LineSequence s2) { - } - - public void match(int startSeq1, int startSeq2, int matchLength) { - matches.add(startSeq1, startSeq2, matchLength); - } - - public void end() { - } - - public void intersectWithTarget(int start, int length, IntVector result) { - int s = start; - for (int l = start, x = start + length; l < x; l++) { - if (!matches.includesTargetLine(l)) { - if (l - s > 0) { - result.add(s); - result.add(l - s); - } - s = l+1; - } - } - if (s < start+length) { - result.add(s); - result.add((start + length) - s); - } - } - - } - - interface MergeResolutionStrategy { - /** - * breaks region [start2..end2) into ranges according to deduced (or simply guessed) - * matching of [start1..end1) lines to lines in source1 and source2 - * @return list of tuples (source, start, length), where source is one of the identifiers supplied - */ - public IntSliceSeq combineAndMarkRangesWithSource(int start1, int end1, int start2, int end2, int source1, int source2); - public IntSliceSeq combineAndMarkRangesWithSource(int insPoint, int start, int end, int source1, int source2); - public int getLineInP2(int mergeLine); - } - - // report lines as merged from p2 solely based on whether target line belongs - // to a region that is equal to p2 region - private static class MergeStrategy1 implements MergeResolutionStrategy { - // equal ranges in p2 and merged revision - private final RangePairSeq matches; - private final IntSliceSeq mergeRanges; - - public MergeStrategy1(RangePairSeq p2EqualToM) { - matches = p2EqualToM; - mergeRanges = new IntSliceSeq(3, 10, 10); - } - - /* - * intersects [start..start+length) with ranges of target lines, and based on the intersection - * breaks initial range into smaller ranges and records them into result, with marker to indicate - * whether the range is from initial range (markerSource) or is a result of the intersection with target - * (markerTarget) - */ - private IntSliceSeq doCombine(int start, int length, int markerSource, int markerTarget) { - mergeRanges.clear(); - assert mergeRanges.sliceSize() == 3; - int sourceStart = start, targetStart = start, sourceEnd = start + length; - for (int l = sourceStart; l < sourceEnd; l++) { - if (matches.includesTargetLine(l)) { - // l is from target - if (sourceStart < l) { - // few lines from source range were not in the target, report them - mergeRanges.add(markerSource, sourceStart, l - sourceStart); - } - // indicate the earliest line from source range to use - sourceStart = l + 1; - } else { - // l is not in target - if (targetStart < l) { - // report lines from target range - mergeRanges.add(markerTarget, targetStart, l - targetStart); - } - // next line *may* be from target - targetStart = l + 1; - } - } - // if source range end with line from target, sourceStart would be == sourceEnd, and we need to add range with markerTarget - // if source range doesn't end with target line, targetStart == sourceEnd, while sourceStart < sourceEnd - if (sourceStart < sourceEnd) { - assert targetStart == sourceEnd; - // something left from the source range - mergeRanges.add(markerSource, sourceStart, sourceEnd - sourceStart); - } else if (targetStart < sourceEnd) { - assert sourceStart == sourceEnd; - mergeRanges.add(markerTarget, targetStart, sourceEnd - targetStart); - } - return mergeRanges; - } - - public int getLineInP2(int mergeLine) { - return matches.reverseMapLine(mergeLine); - } - - public IntSliceSeq combineAndMarkRangesWithSource(int start1, int end1, int start2, int end2, int source1, int source2) { - return doCombine(start2, end2 - start2, source1, source2); - } - - public IntSliceSeq combineAndMarkRangesWithSource(int insPoint, int start, int end, int source1, int source2) { - return doCombine(start, end - start, source1, source2); - } - } - - private static class MergeStrategy2 implements MergeResolutionStrategy { - // equal ranges in p2 and merged revision - private final List matches; - private final IntSliceSeq mergeRanges; - private final DiffRangeMap p1ToBase; - private final DiffRangeMap baseToP2; - - public MergeStrategy2(List p2EqualToM, DiffRangeMap p1ToBaseRanges, DiffRangeMap baseToP2Ranges) { - matches = p2EqualToM; - p1ToBase = p1ToBaseRanges; - baseToP2= baseToP2Ranges; - mergeRanges = new IntSliceSeq(3, 10, 10); - } - - - public IntSliceSeq combineAndMarkRangesWithSource(int insPoint, int start, int end, int source1, int source2) { - return combineAndMarkRangesWithSource(insPoint, insPoint, start, end, source1, source2); - } - - public IntSliceSeq combineAndMarkRangesWithSource(int start1, int end1, int start2, int end2, int source1, int source2) { - mergeRanges.clear(); - IntSliceSeq mergedLines = new IntSliceSeq(2, end2-start2, 0); - for (int i = start2; i < end2; i++) { - mergedLines.add(source1, 0); - } - // [s1Start..s1End) // range in p1 seen as changed in m - for (RangePair p1_b : p1ToBase.findInSource(start1, end1)) { - // there might be few ranges in (p1-base) that overlap with (p1-m) changes - for (RangePair b_p2 : baseToP2.findInSource(p1_b.start2(), p1_b.end2())) { - // regions in p2 that correspond to affected regions in base - for (int p2Line = b_p2.start2(); p2Line < b_p2.end2(); p2Line++) { - for (RangePairSeq eq : matches) { - if (eq.includesOriginLine(p2Line)) { - // this line in p2 is equal to some line in merge - int mergeLine = eq.mapLineIndex(p2Line); - if (mergeLine >= start2 && mergeLine < end2) { - mergedLines.set(mergeLine - start2, source2, p2Line); - } - } - } - } - } - } - int lineCount = 0, start = start2; - int lastSeenSource = source1; - for (IntTuple t : mergedLines) { - if (t.at(0) == lastSeenSource) { - lineCount++; - } else { - if (lineCount > 0) { - mergeRanges.add(lastSeenSource, start, lineCount); - start += lineCount; - } - lineCount = 1; - lastSeenSource = t.at(0); - } - } - if (lineCount > 0) { - mergeRanges.add(lastSeenSource, start, lineCount); - } - return mergeRanges; - } - - public int getLineInP2(int mergeLine) { - for (RangePairSeq eq : matches) { - if (eq.includesTargetLine(mergeLine)) { - return eq.reverseMapLine(mergeLine); - } - } - return -1; - } - } - - - private static class AnnotateRev implements RevisionDescriptor { - public ContentBlock origin, target; - public int originCset, targetCset, mergeCset, fileRevIndex; - public HgDataFile df; - - public void set(HgDataFile file, int fileRev) { - df = file; - fileRevIndex = fileRev; - } - public void set(ContentBlock o, ContentBlock t) { - origin = o; - target = t; - } - public void set(int o, int t, int m) { - originCset = o; - targetCset = t; - mergeCset = m; - } - - public BlockData origin() { - return origin; - } - - public BlockData target() { - return target; - } - - public int originChangesetIndex() { - return originCset; - } - - public int targetChangesetIndex() { - return targetCset; - } - - public boolean isMerge() { - return mergeCset != NO_REVISION; - } - - public int mergeChangesetIndex() { - return mergeCset; - } - - public int fileRevisionIndex() { - return fileRevIndex; - } - public HgDataFile file() { - return df; - } - @Override - public String toString() { - if (isMerge()) { - return String.format("[%d,%d->%d]", originCset, mergeCset, targetCset); - } - return String.format("[%d->%d]", originCset, targetCset); - } - } - - public static void main(String[] args) { - EqualBlocksCollector bc = new EqualBlocksCollector(); - bc.match(-1, 5, 3); - bc.match(-1, 10, 2); - bc.match(-1, 15, 3); - bc.match(-1, 20, 3); - IntVector r = new IntVector(); - bc.intersectWithTarget(7, 10, r); - for (int i = 0; i < r.size(); i+=2) { - System.out.printf("[%d..%d) ", r.get(i), r.get(i) + r.get(i+1)); - } - System.out.println(); - MergeStrategy1 ms = new MergeStrategy1(bc.matches); - IntSliceSeq mr = ms.doCombine(0, 16, 508, 514); - for (IntTuple t : mr) { - System.out.printf("%d:[%d..%d) ", t.at(0), t.at(1), t.at(1) + t.at(2)); - } - System.out.println(); - System.out.println(); - DiffRangeMap m1 = new DiffRangeMap(); // p1 -> base - m1.match(0, 0, 1); // =1..1 -> 1..1 - m1.match(7, 3, 0); // *2..7 -> 2..3 - DiffRangeMap m2 = new DiffRangeMap(); // base -> p2 - m2.match(0, 0, 1); // =1..1 -> 1..1 - m2.match(3, 3, 0); // *2..3 -> 2..3 - RangePairSeq eq1 = new RangePairSeq(); - eq1.add(0, 0, 3); - RangePairSeq eq2 = new RangePairSeq(); - eq2.add(0, 4, 3); - MergeStrategy2 ms2 = new MergeStrategy2(Arrays.asList(eq1, eq2), m1, m2); - mr = ms2.combineAndMarkRangesWithSource(5, 7, 5, 7, 33, 44); - for (IntTuple t : mr) { - System.out.printf("%d:[%d..%d) ", t.at(0), t.at(1), t.at(1) + t.at(2)); - } - } -} diff -r 992fa84e7885 -r 7839ff0bfd78 src/org/tmatesoft/hg/internal/DiffHelper.java --- a/src/org/tmatesoft/hg/internal/DiffHelper.java Thu Aug 08 21:32:22 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,437 +0,0 @@ -/* - * Copyright (c) 2013 TMate Software Ltd - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; version 2 of the License. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * For information on how to redistribute this software under - * the terms of a license other than GNU General Public License - * contact TMate Software at support@hg4j.com - */ -package org.tmatesoft.hg.internal; - -import java.util.ArrayList; -import java.util.HashMap; -import java.util.Map; - -/** - * Mercurial cares about changes only up to the line level, e.g. a simple file version dump in manifest looks like (RevlogDump output): - * - * 522: 233748 0 103 17438 433 522 521 -1 756073cf2321df44d3ed0585f2a5754bc8a1b2f6 - * : - * 3487..3578, 91:src/org/tmatesoft/hg/core/HgIterateDirection.java\00add61a8a665c5d8f092210767f812fe0d335ac8 - * - * I.e. for the {fname}{revision} entry format of manifest, not only {revision} is changed, but the whole line, with unchanged {fname} is recorded - * in the patch. - * - * Mercurial paper describes reasons for choosing this approach to delta generation, too. - * - * - * @author Artem Tikhomirov - * @author TMate Software Ltd. - */ -public class DiffHelper> { - - private Map chunk2UseIndex; - private T seq1, seq2; - - // get filled by #longestMatch, track start of common sequence in seq1 and seq2, respectively - private int matchStartS1, matchStartS2; - - private MatchInspector matchInspector; - - public void init(T s1, T s2) { - seq1 = s1; - seq2 = s2; - prepare(s2); - } - - public void init(T s1) { - if (seq2 == null) { - throw new IllegalStateException("Use this #init() only when target sequence shall be matched against different origin"); - } - seq1 = s1; - } - - - private void prepare(T s2) { - chunk2UseIndex = new HashMap(); - for (int i = 0, len = s2.chunkCount(); i < len; i++) { - Object bc = s2.chunk(i); - IntVector loc = chunk2UseIndex.get(bc); - if (loc == null) { - chunk2UseIndex.put(bc, loc = new IntVector()); - } - loc.add(i); - // bc.registerUseIn(i) - BEWARE, use of bc here is incorrect - // in this case need to find the only ByteChain to keep indexes - // i.e. when there are few equal ByteChain instances, notion of "usedIn" shall be either shared (reference same vector) - // or kept within only one of them - } - } - - public void findMatchingBlocks(MatchInspector insp) { - insp.begin(seq1, seq2); - matchInspector = insp; - findMatchingBlocks(0, seq1.chunkCount(), 0, seq2.chunkCount()); - insp.end(); - } - - /** - * look up every line in s2 that match lines in s1 - * idea: pure additions in s2 are diff-ed against s1 again and again, to see if there are any matches - */ - void findAllMatchAlternatives(final MatchInspector insp) { - assert seq1.chunkCount() > 0; - final IntSliceSeq insertions = new IntSliceSeq(2); - final boolean matchedAny[] = new boolean[] {false}; - DeltaInspector myInsp = new DeltaInspector() { - @Override - protected void unchanged(int s1From, int s2From, int length) { - matchedAny[0] = true; - insp.match(s1From, s2From, length); - } - @Override - protected void added(int s1InsertPoint, int s2From, int s2To) { - insertions.add(s2From, s2To); - } - }; - matchInspector = myInsp; - myInsp.begin(seq1, seq2); - IntSliceSeq s2RangesToCheck = new IntSliceSeq(2, 1, 0); - s2RangesToCheck.add(0, seq2.chunkCount()); - do { - IntSliceSeq nextCheck = new IntSliceSeq(2); - for (IntTuple t : s2RangesToCheck) { - int s2Start = t.at(0); - int s2End = t.at(1); - myInsp.changeStartS1 = 0; - myInsp.changeStartS2 = s2Start; - insp.begin(seq1, seq2); - matchedAny[0] = false; - findMatchingBlocks(0, seq1.chunkCount(), s2Start, s2End); - insp.end(); - myInsp.end(); - if (matchedAny[0]) { - nextCheck.addAll(insertions); - } - insertions.clear(); - } - s2RangesToCheck = nextCheck; - } while (s2RangesToCheck.size() > 0); - } - - /** - * implementation based on Python's difflib.py and SequenceMatcher - */ - public int longestMatch(int startS1, int endS1, int startS2, int endS2) { - matchStartS1 = matchStartS2 = 0; - int maxLength = 0; - IntMap chunkIndex2MatchCount = new IntMap(8); - for (int i = startS1; i < endS1; i++) { - Object bc = seq1.chunk(i); - IntVector occurencesInS2 = chunk2UseIndex.get(bc); - if (occurencesInS2 == null) { - chunkIndex2MatchCount.clear(); - continue; - } - IntMap newChunkIndex2MatchCount = new IntMap(8); - for (int j : occurencesInS2.toArray()) { - // s1[i] == s2[j] - if (j < startS2) { - continue; - } - if (j >= endS2) { - break; - } - int prevChunkMatches = chunkIndex2MatchCount.containsKey(j-1) ? chunkIndex2MatchCount.get(j-1) : 0; - int k = prevChunkMatches + 1; - newChunkIndex2MatchCount.put(j, k); - if (k > maxLength) { - matchStartS1 = i-k+1; - matchStartS2 = j-k+1; - maxLength = k; - } - } - chunkIndex2MatchCount = newChunkIndex2MatchCount; - } - return maxLength; - } - - private void findMatchingBlocks(int startS1, int endS1, int startS2, int endS2) { - int matchLength = longestMatch(startS1, endS1, startS2, endS2); - if (matchLength > 0) { - final int saveStartS1 = matchStartS1, saveStartS2 = matchStartS2; - if (startS1 < matchStartS1 && startS2 < matchStartS2) { - findMatchingBlocks(startS1, matchStartS1, startS2, matchStartS2); - } - matchInspector.match(saveStartS1, saveStartS2, matchLength); - if (saveStartS1+matchLength < endS1 && saveStartS2+matchLength < endS2) { - findMatchingBlocks(saveStartS1 + matchLength, endS1, saveStartS2 + matchLength, endS2); - } - } - } - - public interface MatchInspector> { - void begin(T s1, T s2); - void match(int startSeq1, int startSeq2, int matchLength); - void end(); - } - - static class MatchDumpInspector> implements MatchInspector { - private int matchCount; - - public void begin(T s1, T s2) { - matchCount = 0; - } - - public void match(int startSeq1, int startSeq2, int matchLength) { - matchCount++; - System.out.printf("match #%d: from line #%d and line #%d of length %d\n", matchCount, startSeq1, startSeq2, matchLength); - } - - public void end() { - if (matchCount == 0) { - System.out.println("NO MATCHES FOUND!"); - } - } - } - - /** - * Matcher implementation that translates "match/equal" notification to a delta-style "added/removed/changed". - */ - public static class DeltaInspector> implements MatchInspector { - protected int changeStartS1, changeStartS2; - protected T seq1, seq2; - - public void begin(T s1, T s2) { - seq1 = s1; - seq2 = s2; - changeStartS1 = changeStartS2 = 0; - } - - public void match(int startSeq1, int startSeq2, int matchLength) { - reportDeltaElement(startSeq1, startSeq2, matchLength); - changeStartS1 = startSeq1 + matchLength; - changeStartS2 = startSeq2 + matchLength; - } - - public void end() { - if (changeStartS1 < seq1.chunkCount()-1 || changeStartS2 < seq2.chunkCount()-1) { - reportDeltaElement(seq1.chunkCount()-1, seq2.chunkCount()-1, 0); - } - } - - protected void reportDeltaElement(int matchStartSeq1, int matchStartSeq2, int matchLength) { - if (changeStartS1 < matchStartSeq1) { - if (changeStartS2 < matchStartSeq2) { - changed(changeStartS1, matchStartSeq1, changeStartS2, matchStartSeq2); - } else { - assert changeStartS2 == matchStartSeq2; - deleted(matchStartSeq2, changeStartS1, matchStartSeq1); - } - } else { - assert changeStartS1 == matchStartSeq1; - if(changeStartS2 < matchStartSeq2) { - added(changeStartS1, changeStartS2, matchStartSeq2); - } else { - assert changeStartS2 == matchStartSeq2; - if (matchStartSeq1 > 0 || matchStartSeq2 > 0) { - assert false : String.format("adjustent equal blocks %d, %d and %d,%d", changeStartS1, matchStartSeq1, changeStartS2, matchStartSeq2); - } - } - } - if (matchLength > 0) { - unchanged(matchStartSeq1, matchStartSeq2, matchLength); - } - } - - /** - * [s1From..s1To) replaced with [s2From..s2To) - */ - protected void changed(int s1From, int s1To, int s2From, int s2To) { - // NO-OP - } - - protected void deleted(int s2DeletePoint, int s1From, int s1To) { - // NO-OP - } - - protected void added(int s1InsertPoint, int s2From, int s2To) { - // NO-OP - } - - protected void unchanged(int s1From, int s2From, int length) { - // NO-OP - } - } - - public static class DeltaDumpInspector> extends DeltaInspector { - - @Override - protected void changed(int s1From, int s1To, int s2From, int s2To) { - System.out.printf("changed [%d..%d) with [%d..%d)\n", s1From, s1To, s2From, s2To); - } - - @Override - protected void deleted(int s2DeletionPoint, int s1From, int s1To) { - System.out.printf("deleted [%d..%d)\n", s1From, s1To); - } - - @Override - protected void added(int s1InsertPoint, int s2From, int s2To) { - System.out.printf("added [%d..%d) at %d\n", s2From, s2To, s1InsertPoint); - } - - @Override - protected void unchanged(int s1From, int s2From, int length) { - System.out.printf("same [%d..%d) and [%d..%d)\n", s1From, s1From + length, s2From, s2From + length); - } - } - - /** - * Generic sequence of chunk, where chunk is anything comparable to another chunk, e.g. a string or a single char - * Sequence diff algorithm above doesn't care about sequence nature. - */ - public interface ChunkSequence { - public T chunk(int index); - public int chunkCount(); - } - - public static final class LineSequence implements ChunkSequence { - - private final byte[] input; - private ArrayList lines; - - public LineSequence(byte[] data) { - input = data; - } - - public static LineSequence newlines(byte[] array) { - return new LineSequence(array).splitByNewlines(); - } - - // sequence ends with fake, empty line chunk - public LineSequence splitByNewlines() { - lines = new ArrayList(); - int lastStart = 0; - for (int i = 0; i < input.length; i++) { - if (input[i] == '\n') { - lines.add(new ByteChain(lastStart, i+1)); - lastStart = i+1; - } else if (input[i] == '\r') { - if (i+1 < input.length && input[i+1] == '\n') { - i++; - } - lines.add(new ByteChain(lastStart, i+1)); - lastStart = i+1; - } - } - if (lastStart < input.length) { - lines.add(new ByteChain(lastStart, input.length)); - } - // empty chunk to keep offset of input end - lines.add(new ByteChain(input.length)); - return this; - } - - public ByteChain chunk(int index) { - return lines.get(index); - } - - public int chunkCount() { - return lines.size(); - } - - public byte[] data(int chunkFrom, int chunkTo) { - if (chunkFrom == chunkTo) { - return new byte[0]; - } - int from = chunk(chunkFrom).getOffset(), to = chunk(chunkTo).getOffset(); - byte[] rv = new byte[to - from]; - System.arraycopy(input, from, rv, 0, rv.length); - return rv; - } - - - public final class ByteChain { - private final int start, end; - private final int hash; - - /** - * construct a chunk with a sole purpose to keep - * offset of the data end - */ - ByteChain(int offset) { - start = end = offset; - // ensure this chunk doesn't match trailing chunk of another sequence - hash = System.identityHashCode(this); - } - - ByteChain(int s, int e) { - start = s; - end = e; - hash = calcHash(input, s, e); - } - - /** - * byte offset of the this ByteChain inside ChainSequence - */ - public int getOffset() { - return start; - } - - public byte[] data() { - byte[] rv = new byte[end - start]; - System.arraycopy(input, start, rv, 0, rv.length); - return rv; - } - - @Override - public boolean equals(Object obj) { - if (obj == null || obj.getClass() != ByteChain.class) { - return false; - } - ByteChain other = (ByteChain) obj; - if (other.hash != hash || other.end - other.start != end - start) { - return false; - } - return other.match(input, start); - } - - private boolean match(byte[] oi, int from) { - for (int i = start, j = from; i < end; i++, j++) { - if (LineSequence.this.input[i] != oi[j]) { - return false; - } - } - return true; - } - - @Override - public int hashCode() { - return hash; - } - - @Override - public String toString() { - return String.format("[@%d\"%s\"]", start, new String(data())); - } - } - - // same as Arrays.hashCode(byte[]), just for a slice of a bigger array - static int calcHash(byte[] data, int from, int to) { - int result = 1; - for (int i = from; i < to; i++) { - result = 31 * result + data[i]; - } - return result; - } - } -} diff -r 992fa84e7885 -r 7839ff0bfd78 src/org/tmatesoft/hg/internal/ForwardAnnotateInspector.java --- a/src/org/tmatesoft/hg/internal/ForwardAnnotateInspector.java Thu Aug 08 21:32:22 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,142 +0,0 @@ -/* - * Copyright (c) 2013 TMate Software Ltd - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; version 2 of the License. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * For information on how to redistribute this software under - * the terms of a license other than GNU General Public License - * contact TMate Software at support@hg4j.com - */ -package org.tmatesoft.hg.internal; - -import org.tmatesoft.hg.core.HgAnnotateCommand.Inspector; -import org.tmatesoft.hg.core.HgBlameInspector; -import org.tmatesoft.hg.core.HgCallbackTargetException; -import org.tmatesoft.hg.core.HgIterateDirection; -import org.tmatesoft.hg.util.CancelSupport; -import org.tmatesoft.hg.util.CancelledException; -import org.tmatesoft.hg.util.ProgressSupport; - -/** - * Annotate file history iterating from parents to children - * - * At the moment, doesn't handle start from any revision but 0 - * - * (+) May report annotate for any revision (with actual file change) in the visited range. - * - * @see ReverseAnnotateInspector - * @author Artem Tikhomirov - * @author TMate Software Ltd. - */ -public class ForwardAnnotateInspector implements HgBlameInspector, HgBlameInspector.RevisionDescriptor.Recipient { - final IntMap all = new IntMap(100); - // revision->map(lineNumber->lineContent) - private final IntMap> lineContent = new IntMap>(100); - private IntSliceSeq current; - private RevisionDescriptor revDescriptor; - - /** - * @return desired order of iteration for diff - */ - public HgIterateDirection iterateDirection() { - return HgIterateDirection.OldToNew; - } - - public void report(int revision, Inspector insp, ProgressSupport progress, CancelSupport cancel) throws HgCallbackTargetException, CancelledException { - int totalLines = 0; - if (!all.containsKey(revision)) { - throw new IllegalArgumentException(String.format("Revision %d has not been visited", revision)); - } - for (IntTuple t : all.get(revision)) { - totalLines += t.at(0); - } - progress.start(totalLines); - LineImpl li = new LineImpl(); - int line = 1; - for (IntTuple t : all.get(revision)) { - IntMap revLines = lineContent.get(t.at(1)); - for (int i = 0, x = t.at(0); i < x; i++) { - final int lineInRev = t.at(2) + i; - final byte[] lc = revLines.get(lineInRev); - li.init(line++, lineInRev+1, t.at(1), lc); - insp.next(li); - progress.worked(1); - cancel.checkCancelled(); - } - } - progress.done(); - } - - public void start(RevisionDescriptor rd) throws HgCallbackTargetException { - all.put(rd.targetChangesetIndex(), current = new IntSliceSeq(3)); - revDescriptor = rd; - } - - public void done(RevisionDescriptor rd) throws HgCallbackTargetException { - revDescriptor = null; - } - - public void same(EqualBlock block) throws HgCallbackTargetException { - copyBlock(block.originChangesetIndex(), block.originStart(), block.length()); - } - - public void added(AddBlock block) throws HgCallbackTargetException { - if (revDescriptor.isMerge() && block.originChangesetIndex() == revDescriptor.mergeChangesetIndex()) { - copyBlock(block.originChangesetIndex(), block.insertedAt(), block.totalAddedLines()); - return; - } - BlockData addedLines = block.addedLines(); - IntMap revLines = lineContent.get(block.targetChangesetIndex()); - if (revLines == null) { - lineContent.put(block.targetChangesetIndex(), revLines = new IntMap(block.totalAddedLines())); - } - for (int i = 0; i < block.totalAddedLines(); i++) { - revLines.put(block.firstAddedLine() + i, addedLines.elementAt(i).asArray()); - } - current.add(block.totalAddedLines(), block.targetChangesetIndex(), block.firstAddedLine()); - } - - public void changed(ChangeBlock block) throws HgCallbackTargetException { - added(block); - } - - public void deleted(DeleteBlock block) throws HgCallbackTargetException { - } - - private void copyBlock(int originChangesetIndex, int blockStart, int length) { - IntSliceSeq origin = all.get(originChangesetIndex); - assert origin != null; // shall visit parents before came to this child - int originPos = 0; - int targetBlockLen = length; - for (IntTuple t : origin) { - int originBlockLen = t.at(0); - int originBlockEnd = originPos + originBlockLen; - if (originBlockEnd > blockStart) { - // part of origin block from blockStart up to originBlockEnd, but not more - // than size of the block (when blockStart is out of block start, i.e. < originPos) - int originBlockOverlap = Math.min(originBlockLen, originBlockEnd - blockStart); - assert originBlockOverlap > 0; - // eat as much as there's left in the block being copied - int originBlockConsumed = Math.min(originBlockOverlap, targetBlockLen); - int originBlockLine = t.at(2); - if (originPos < blockStart) { - originBlockLine += originBlockLen-originBlockOverlap; - } - // copy fragment of original block; - current.add(originBlockConsumed, t.at(1), originBlockLine); - targetBlockLen -= originBlockConsumed; - if (targetBlockLen == 0) { - break; - } - } - originPos += originBlockLen; - } - } -} \ No newline at end of file diff -r 992fa84e7885 -r 7839ff0bfd78 src/org/tmatesoft/hg/internal/GeneratePatchInspector.java --- a/src/org/tmatesoft/hg/internal/GeneratePatchInspector.java Thu Aug 08 21:32:22 2013 +0200 +++ b/src/org/tmatesoft/hg/internal/GeneratePatchInspector.java Wed Aug 14 14:51:51 2013 +0200 @@ -16,8 +16,9 @@ */ package org.tmatesoft.hg.internal; -import org.tmatesoft.hg.internal.DiffHelper.DeltaInspector; -import org.tmatesoft.hg.internal.DiffHelper.LineSequence; +import org.tmatesoft.hg.internal.diff.DiffHelper; +import org.tmatesoft.hg.internal.diff.DiffHelper.DeltaInspector; +import org.tmatesoft.hg.internal.diff.DiffHelper.LineSequence; class GeneratePatchInspector extends DeltaInspector { private final Patch deltaCollector; diff -r 992fa84e7885 -r 7839ff0bfd78 src/org/tmatesoft/hg/internal/LineImpl.java --- a/src/org/tmatesoft/hg/internal/LineImpl.java Thu Aug 08 21:32:22 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,54 +0,0 @@ -/* - * Copyright (c) 2013 TMate Software Ltd - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; version 2 of the License. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * For information on how to redistribute this software under - * the terms of a license other than GNU General Public License - * contact TMate Software at support@hg4j.com - */ -package org.tmatesoft.hg.internal; - -import org.tmatesoft.hg.core.HgAnnotateCommand.LineInfo; - -/** - * @author Artem Tikhomirov - * @author TMate Software Ltd. - */ -final class LineImpl implements LineInfo { - private int ln; - private int origLine; - private int rev; - private byte[] content; - - void init(int line, int firstAppearance, int csetRev, byte[] cnt) { - ln = line; - origLine = firstAppearance; - rev = csetRev; - content = cnt; - } - - public int getLineNumber() { - return ln; - } - - - public int getOriginLineNumber() { - return origLine; - } - - public int getChangesetIndex() { - return rev; - } - - public byte[] getContent() { - return content; - } -} \ No newline at end of file diff -r 992fa84e7885 -r 7839ff0bfd78 src/org/tmatesoft/hg/internal/RangePairSeq.java --- a/src/org/tmatesoft/hg/internal/RangePairSeq.java Thu Aug 08 21:32:22 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,169 +0,0 @@ -/* - * Copyright (c) 2013 TMate Software Ltd - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; version 2 of the License. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * For information on how to redistribute this software under - * the terms of a license other than GNU General Public License - * contact TMate Software at support@hg4j.com - */ -package org.tmatesoft.hg.internal; - -import java.util.Formatter; - -/** - * Sequence of range pairs (denoted origin and target), {originStart, targetStart, length}, tailored for diff/annotate - * - * @author Artem Tikhomirov - * @author TMate Software Ltd. - */ -public final class RangePairSeq { - private final IntSliceSeq ranges = new IntSliceSeq(3); - - public void add(int start1, int start2, int length) { - int count = ranges.size(); - if (count > 0) { - int lastS1 = ranges.get(--count, 0); - int lastS2 = ranges.get(count, 1); - int lastLen = ranges.get(count, 2); - if (start1 == lastS1 + lastLen && start2 == lastS2 + lastLen) { - // new range continues the previous one - just increase the length - ranges.set(count, lastS1, lastS2, lastLen + length); - return; - } - } - ranges.add(start1, start2, length); - } - - public void clear() { - ranges.clear(); - } - - public int size() { - return ranges.size(); - } - - /** - * find out line index in the target that matches specified origin line - */ - public int mapLineIndex(int ln) { - for (IntTuple t : ranges) { - int s1 = t.at(0); - if (s1 > ln) { - return -1; - } - int l = t.at(2); - if (s1 + l > ln) { - int s2 = t.at(1); - return s2 + (ln - s1); - } - } - return -1; - } - - /** - * find out line index in origin that matches specified target line - */ - public int reverseMapLine(int targetLine) { - for (IntTuple t : ranges) { - int ts = t.at(1); - if (ts > targetLine) { - return -1; - } - int l = t.at(2); - if (ts + l > targetLine) { - int os = t.at(0); - return os + (targetLine - ts); - } - } - return -1; - } - - public RangePairSeq intersect(RangePairSeq target) { - RangePairSeq v = new RangePairSeq(); - for (IntTuple t : ranges) { - int originLine = t.at(0); - int targetLine = t.at(1); - int length = t.at(2); - int startTargetLine = -1, startOriginLine = -1, c = 0; - for (int j = 0; j < length; j++) { - int lnInFinal = target.mapLineIndex(targetLine + j); - if (lnInFinal == -1 || (startTargetLine != -1 && lnInFinal != startTargetLine + c)) { - // the line is not among "same" in ultimate origin - // or belongs to another/next "same" chunk - if (startOriginLine == -1) { - continue; - } - v.add(startOriginLine, startTargetLine, c); - c = 0; - startOriginLine = startTargetLine = -1; - // fall-through to check if it's not complete miss but a next chunk - } - if (lnInFinal != -1) { - if (startOriginLine == -1) { - startOriginLine = originLine + j; - startTargetLine = lnInFinal; - c = 1; - } else { - // lnInFinal != startTargetLine + s is covered above - assert lnInFinal == startTargetLine + c; - c++; - } - } - } - if (startOriginLine != -1) { - assert c > 0; - v.add(startOriginLine, startTargetLine, c); - } - } - return v; - } - - // true when specified line in origin is equal to a line in target - public boolean includesOriginLine(int ln) { - return includes(ln, 0); - } - - // true when specified line in target is equal to a line in origin - public boolean includesTargetLine(int ln) { - return includes(ln, 1); - } - - private boolean includes(int ln, int o) { - for (IntTuple t : ranges) { - int rangeStart = t.at(o); - if (rangeStart > ln) { - return false; - } - int rangeLen = t.at(2); - if (rangeStart + rangeLen > ln) { - return true; - } - } - return false; - } - - public CharSequence dump() { - StringBuilder sb = new StringBuilder(); - Formatter f = new Formatter(sb); - for (IntTuple t : ranges) { - int s1 = t.at(0); - int s2 = t.at(1); - int len = t.at(2); - f.format("[%d..%d) == [%d..%d); ", s1, s1 + len, s2, s2 + len); - } - return sb; - } - - @Override - public String toString() { - return String.format("RangeSeq[%d]:%s", size(), dump()); - } -} \ No newline at end of file diff -r 992fa84e7885 -r 7839ff0bfd78 src/org/tmatesoft/hg/internal/ReverseAnnotateInspector.java --- a/src/org/tmatesoft/hg/internal/ReverseAnnotateInspector.java Thu Aug 08 21:32:22 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,167 +0,0 @@ -/* - * Copyright (c) 2013 TMate Software Ltd - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; version 2 of the License. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * For information on how to redistribute this software under - * the terms of a license other than GNU General Public License - * contact TMate Software at support@hg4j.com - */ -package org.tmatesoft.hg.internal; - - -import static org.tmatesoft.hg.repo.HgRepository.NO_REVISION; - -import java.util.Arrays; - -import org.tmatesoft.hg.core.HgAnnotateCommand; -import org.tmatesoft.hg.core.HgBlameInspector; -import org.tmatesoft.hg.core.HgIterateDirection; -import org.tmatesoft.hg.core.HgBlameInspector.RevisionDescriptor; -import org.tmatesoft.hg.core.HgCallbackTargetException; -import org.tmatesoft.hg.repo.HgInvalidStateException; -import org.tmatesoft.hg.util.CancelSupport; -import org.tmatesoft.hg.util.CancelledException; -import org.tmatesoft.hg.util.ProgressSupport; - -/** - * Produce output like 'hg annotate' does. - * Expects revisions to come in order from child to parent. - * Unlike {@link ForwardAnnotateInspector}, can be easily modified to report lines as soon as its origin is detected. - * - * (+) Handles annotate of partial history, at any moment lines with ({@link #knownLines} == false indicate lines - * that were added prior to any revision already visited. - * - * @author Artem Tikhomirov - * @author TMate Software Ltd. - */ -public class ReverseAnnotateInspector implements HgBlameInspector, RevisionDescriptor.Recipient { - - // keeps of equal blocks, origin to target, from some previous step - private RangePairSeq activeEquals; - // equal blocks of the current iteration, to be recalculated before next step - // to track line number (current target to ultimate target) mapping - private RangePairSeq intermediateEquals = new RangePairSeq(); - - private boolean[] knownLines; - private RevisionDescriptor revisionDescriptor; - private BlockData lineContent; - - private IntMap mergedRanges = new IntMap(10); - private IntMap equalRanges = new IntMap(10); - private boolean activeEqualsComesFromMerge = false; - - private int[] lineRevisions; - private int[] lineNumbers; - - /** - * @return desired order of iteration for diff - */ - public HgIterateDirection iterateDirection() { - return HgIterateDirection.NewToOld; - } - - public void report(int annotateRevIndex, HgAnnotateCommand.Inspector insp, ProgressSupport progress, CancelSupport cancel) throws HgCallbackTargetException, CancelledException { - LineImpl li = new LineImpl(); - progress.start(lineRevisions.length); - for (int i = 0; i < lineRevisions.length; i++) { - byte[] c = lineContent.elementAt(i).asArray(); - li.init(i+1, lineNumbers[i] + 1, lineRevisions[i], c); - insp.next(li); - progress.worked(1); - cancel.checkCancelled(); - } - progress.done(); - } - - public void start(RevisionDescriptor rd) { - revisionDescriptor = rd; - if (knownLines == null) { - lineContent = rd.target(); - knownLines = new boolean[lineContent.elementCount()]; - lineRevisions = new int [knownLines.length]; - Arrays.fill(lineRevisions, NO_REVISION); - lineNumbers = new int[knownLines.length]; - activeEquals = new RangePairSeq(); - activeEquals.add(0, 0, knownLines.length); - equalRanges.put(rd.targetChangesetIndex(), activeEquals); - } else { - activeEquals = equalRanges.get(rd.targetChangesetIndex()); - if (activeEquals == null) { - // we didn't see this target revision as origin yet - // the only way this may happen is that this revision was a merge parent - activeEquals = mergedRanges.get(rd.targetChangesetIndex()); - activeEqualsComesFromMerge = true; - if (activeEquals == null) { - throw new HgInvalidStateException(String.format("Can't find previously visited revision %d (while in %d->%1$d diff)", rd.targetChangesetIndex(), rd.originChangesetIndex())); - } - } - } - } - - public void done(RevisionDescriptor rd) { - // update line numbers of the intermediate target to point to ultimate target's line numbers - RangePairSeq v = intermediateEquals.intersect(activeEquals); - if (activeEqualsComesFromMerge) { - mergedRanges.put(rd.originChangesetIndex(), v); - } else { - equalRanges.put(rd.originChangesetIndex(), v); - } - if (rd.isMerge() && !mergedRanges.containsKey(rd.mergeChangesetIndex())) { - // seen merge, but no lines were merged from p2. - // Add empty range to avoid uncertainty when a parent of p2 pops in - mergedRanges.put(rd.mergeChangesetIndex(), new RangePairSeq()); - } - intermediateEquals.clear(); - activeEquals = null; - activeEqualsComesFromMerge = false; - revisionDescriptor = null; - } - - public void same(EqualBlock block) { - intermediateEquals.add(block.originStart(), block.targetStart(), block.length()); - } - - public void added(AddBlock block) { - RangePairSeq rs = null; - if (revisionDescriptor.isMerge() && block.originChangesetIndex() == revisionDescriptor.mergeChangesetIndex()) { - rs = mergedRanges.get(revisionDescriptor.mergeChangesetIndex()); - if (rs == null) { - mergedRanges.put(revisionDescriptor.mergeChangesetIndex(), rs = new RangePairSeq()); - } - } - if (activeEquals.size() == 0) { - return; - } - for (int i = 0, ln = block.firstAddedLine(), x = block.totalAddedLines(); i < x; i++, ln++) { - int lnInFinal = activeEquals.mapLineIndex(ln); - if (lnInFinal != -1/* && !knownLines[lnInFinal]*/) { - if (rs != null) { - rs.add(block.insertedAt() + i, lnInFinal, 1); - } else { - line(lnInFinal, ln, block.targetChangesetIndex()); - } - knownLines[lnInFinal] = true; - } - } - } - - public void changed(ChangeBlock block) { - added(block); - } - - public void deleted(DeleteBlock block) { - } - - private void line(int lineNumber, int firstAppearance, int changesetRevIndex) { - lineRevisions[lineNumber] = changesetRevIndex; - lineNumbers[lineNumber] = firstAppearance; - } -} \ No newline at end of file diff -r 992fa84e7885 -r 7839ff0bfd78 src/org/tmatesoft/hg/internal/diff/BlameHelper.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/org/tmatesoft/hg/internal/diff/BlameHelper.java Wed Aug 14 14:51:51 2013 +0200 @@ -0,0 +1,972 @@ +/* + * Copyright (c) 2013 TMate Software Ltd + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; version 2 of the License. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * For information on how to redistribute this software under + * the terms of a license other than GNU General Public License + * contact TMate Software at support@hg4j.com + */ +package org.tmatesoft.hg.internal.diff; + +import static org.tmatesoft.hg.core.HgIterateDirection.OldToNew; +import static org.tmatesoft.hg.repo.HgRepository.NO_REVISION; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Iterator; +import java.util.LinkedList; +import java.util.List; +import java.util.ListIterator; + +import org.tmatesoft.hg.core.HgCallbackTargetException; +import org.tmatesoft.hg.core.Nodeid; +import org.tmatesoft.hg.internal.ByteArrayChannel; +import org.tmatesoft.hg.internal.FileHistory; +import org.tmatesoft.hg.internal.FileRevisionHistoryChunk; +import org.tmatesoft.hg.internal.IntSliceSeq; +import org.tmatesoft.hg.internal.IntTuple; +import org.tmatesoft.hg.internal.IntVector; +import org.tmatesoft.hg.internal.diff.DiffHelper.LineSequence; +import org.tmatesoft.hg.internal.diff.DiffHelper.LineSequence.ByteChain; +import org.tmatesoft.hg.internal.diff.DiffRangeMap.RangePair; +import org.tmatesoft.hg.core.HgBlameInspector; +import org.tmatesoft.hg.core.HgBlameInspector.*; +import org.tmatesoft.hg.repo.HgChangelog; +import org.tmatesoft.hg.repo.HgDataFile; +import org.tmatesoft.hg.repo.HgInvalidStateException; +import org.tmatesoft.hg.repo.HgParentChildMap; +import org.tmatesoft.hg.repo.HgRepository; +import org.tmatesoft.hg.repo.HgRevisionMap; +import org.tmatesoft.hg.repo.HgRuntimeException; +import org.tmatesoft.hg.util.Adaptable; +import org.tmatesoft.hg.util.CancelledException; +import org.tmatesoft.hg.util.Pair; + +/** + * Blame implementation + * @see HgBlameInspector + * @author Artem Tikhomirov + * @author TMate Software Ltd. + */ +public class BlameHelper { + + private final HgBlameInspector insp; + private FileLinesCache linesCache; + private HgParentChildMap clogMap; + + public BlameHelper(HgBlameInspector inspector) { + insp = inspector; + } + + /** + * Build history of the file for the specified range (follow renames if necessary). This history + * is used to access various file revision data during subsequent {@link #diff(int, int, int, int)} and + * {@link #annotateChange(int, int, int[], int[])} calls. Callers can use returned history for own approaches + * to iteration over file history. + + *

NOTE, clogRevIndexEnd has to list name of the supplied file in the corresponding manifest, + * as it's not possible to trace rename history otherwise. + */ + public FileHistory prepare(HgDataFile df, int clogRevIndexStart, int clogRevIndexEnd) throws HgRuntimeException { + assert clogRevIndexStart <= clogRevIndexEnd; + FileHistory fileHistory = new FileHistory(df, clogRevIndexStart, clogRevIndexEnd); + fileHistory.build(); + int cacheHint = 5; // cache comes useful when we follow merge branches and don't want to + // parse base revision twice. There's no easy way to determine max(distance(all(base,merge))), + // hence the heuristics to use the longest history chunk: + for (FileRevisionHistoryChunk c : fileHistory.iterate(OldToNew)) { + // iteration order is not important here + if (c.revisionCount() > cacheHint) { + cacheHint = c.revisionCount(); + } + } + linesCache = new FileLinesCache(cacheHint); + for (FileRevisionHistoryChunk fhc : fileHistory.iterate(OldToNew)) { + // iteration order is not important here + linesCache.useFileUpTo(fhc.getFile(), fhc.getEndChangeset()); + } + return fileHistory; + } + + // NO_REVISION is not allowed as any argument + public void diff(int fileRevIndex1, int clogRevIndex1, int fileRevIndex2, int clogRevIndex2) throws HgCallbackTargetException, HgRuntimeException { + HgDataFile targetFile = linesCache.getFile(clogRevIndex2); + LineSequence c1 = linesCache.lines(clogRevIndex1, fileRevIndex1); + LineSequence c2 = linesCache.lines(clogRevIndex2, fileRevIndex2); + DiffHelper pg = new DiffHelper(); + pg.init(c1, c2); + BlameBlockInspector bbi = new BlameBlockInspector(targetFile, fileRevIndex2, insp, clogRevIndex1, clogRevIndex2); + pg.findMatchingBlocks(bbi); + bbi.checkErrors(); + } + + public void annotateChange(int fileRevIndex, int csetRevIndex, int[] fileParentRevs, int[] fileParentClogRevs) throws HgCallbackTargetException, HgRuntimeException { + HgDataFile targetFile = linesCache.getFile(csetRevIndex); + final LineSequence fileRevLines = linesCache.lines(csetRevIndex, fileRevIndex); + if (fileParentClogRevs[0] != NO_REVISION && fileParentClogRevs[1] != NO_REVISION) { + int p1ClogIndex = fileParentClogRevs[0]; + int p2ClogIndex = fileParentClogRevs[1]; + LineSequence p1Lines = linesCache.lines(p1ClogIndex, fileParentRevs[0]); + LineSequence p2Lines = linesCache.lines(p2ClogIndex, fileParentRevs[1]); + MergeResolutionStrategy mergeResolver = createMergeStrategy(fileRevLines, p1Lines, p2Lines, csetRevIndex, fileParentClogRevs); + // + DiffHelper pg = new DiffHelper(); + pg.init(p1Lines, fileRevLines); + BlameBlockInspector bbi = new BlameBlockInspector(targetFile, fileRevIndex, insp, p1ClogIndex, csetRevIndex); + bbi.setMergeParent2(mergeResolver, p2ClogIndex); + pg.findMatchingBlocks(bbi); + bbi.checkErrors(); + } else if (fileParentClogRevs[0] == fileParentClogRevs[1]) { + // may be equal iff both are unset + assert fileParentClogRevs[0] == NO_REVISION; + // everything added + BlameBlockInspector bbi = new BlameBlockInspector(targetFile, fileRevIndex, insp, NO_REVISION, csetRevIndex); + bbi.begin(LineSequence.newlines(new byte[0]), fileRevLines); + bbi.match(0, fileRevLines.chunkCount()-1, 0); + bbi.end(); + bbi.checkErrors(); + } else { + int soleParentIndex = fileParentClogRevs[0] == NO_REVISION ? 1 : 0; + assert fileParentClogRevs[soleParentIndex] != NO_REVISION; + LineSequence parentLines = linesCache.lines(fileParentClogRevs[soleParentIndex], fileParentRevs[soleParentIndex]); + + DiffHelper pg = new DiffHelper(); + pg.init(parentLines, fileRevLines); + BlameBlockInspector bbi = new BlameBlockInspector(targetFile, fileRevIndex, insp, fileParentClogRevs[soleParentIndex], csetRevIndex); + pg.findMatchingBlocks(bbi); + bbi.checkErrors(); + } + } + + private static final boolean useNewStrategy = Boolean.TRUE.booleanValue(); + + private MergeResolutionStrategy createMergeStrategy(LineSequence fileRevLines, LineSequence p1Lines, LineSequence p2Lines, int csetRevIndex, int[] fileParentClogRevs) { + DiffHelper pg = new DiffHelper(); + if (useNewStrategy) { + final ArrayList allMatches = new ArrayList(); + pg.init(p2Lines, fileRevLines); + pg.findAllMatchAlternatives(new DiffHelper.MatchInspector() { + private RangePairSeq matches; + + public void begin(LineSequence s1, LineSequence s2) { + matches = new RangePairSeq(); + } + + public void match(int startSeq1, int startSeq2, int matchLength) { + matches.add(startSeq1, startSeq2, matchLength); + } + + public void end() { + if (matches.size() > 0) { + allMatches.add(matches); + } + } + + }); + // + LineSequence baseLines = getBaseRevisionLines(csetRevIndex, fileParentClogRevs); + pg.init(p1Lines, baseLines); + DiffRangeMap p1ToBase = new DiffRangeMap().fill(pg); + pg.init(baseLines, p2Lines); + DiffRangeMap baseToP2 = new DiffRangeMap().fill(pg); + return new MergeStrategy2(allMatches, p1ToBase, baseToP2); + } else { + pg.init(p2Lines, fileRevLines); + EqualBlocksCollector p2MergeCommon = new EqualBlocksCollector(); + pg.findMatchingBlocks(p2MergeCommon); + return new MergeStrategy1(p2MergeCommon.matches); + } + } + + private LineSequence getBaseRevisionLines(int clogRevIndex, int[] fileParentClogRevs) { + assert fileParentClogRevs[0] >= 0; + assert fileParentClogRevs[1] >= 0; + HgDataFile targetFile = linesCache.getFile(clogRevIndex); + final HgRepository repo = targetFile.getRepo(); + if (clogMap == null) { + // FIXME replace HgParentChildMap with revlog.indexWalk(AncestorIterator)) + clogMap = new HgParentChildMap(repo.getChangelog()); + clogMap.init(); + } + final HgRevisionMap m = clogMap.getRevisionMap(); + Nodeid ancestor = clogMap.ancestor(m.revision(fileParentClogRevs[0]), m.revision(fileParentClogRevs[1])); + final int ancestorRevIndex = m.revisionIndex(ancestor); + Nodeid fr = repo.getManifest().getFileRevision(ancestorRevIndex, targetFile.getPath()); + if (fr == null) { + return LineSequence.newlines(new byte[0]); + } + return linesCache.lines(ancestorRevIndex, targetFile.getRevisionIndex(fr)); + } + + private static class FileLinesCache { + private final LinkedList> lruCache; + private final int limit; + private final LinkedList> files; // TODO in fact, need sparse array + + /** + * @param lruLimit how many parsed file revisions to keep + */ + public FileLinesCache(int lruLimit) { + limit = lruLimit; + lruCache = new LinkedList>(); + files = new LinkedList>(); + } + + public void useFileUpTo(HgDataFile df, int clogRevIndex) { + Pair newEntry = new Pair(clogRevIndex, df); + for (ListIterator> it = files.listIterator(); it.hasNext();) { + Pair e = it.next(); + if (e.first() == clogRevIndex) { + assert e.second().getPath().equals(df.getPath()); + return; + } + if (e.first() > clogRevIndex) { + // insert new entry before current + it.previous(); + it.add(newEntry); + return; + } + } + files.add(newEntry); + } + + public HgDataFile getFile(int clogRevIndex) { + for (Pair e : files) { + if (e.first() >= clogRevIndex) { + return e.second(); + } + } + throw new HgInvalidStateException(String.format("Got %d file-changelog mappings, but no luck for revision %d.", files.size(), clogRevIndex)); + } + + public LineSequence lines(int clogRevIndex, int fileRevIndex) throws HgRuntimeException { + Pair cached = checkCache(clogRevIndex); + if (cached != null) { + return cached.second(); + } + HgDataFile df = getFile(clogRevIndex); + try { + ByteArrayChannel c; + df.content(fileRevIndex, c = new ByteArrayChannel()); + LineSequence rv = LineSequence.newlines(c.toArray()); + lruCache.addFirst(new Pair(clogRevIndex, rv)); + if (lruCache.size() > limit) { + lruCache.removeLast(); + } + return rv; + } catch (CancelledException ex) { + // TODO likely it was bad idea to throw cancelled exception from content() + // deprecate and provide alternative? + HgInvalidStateException ise = new HgInvalidStateException("ByteArrayChannel never throws CancelledException"); + ise.initCause(ex); + throw ise; + } + } + + private Pair checkCache(int fileRevIndex) { + Pair rv = null; + for (ListIterator> it = lruCache.listIterator(); it.hasNext(); ) { + Pair p = it.next(); + if (p.first() == fileRevIndex) { + rv = p; + it.remove(); + break; + } + } + if (rv != null) { + lruCache.addFirst(rv); + } + return rv; + } + } + + private static class BlameBlockInspector extends DiffHelper.DeltaInspector { + private final HgBlameInspector insp; + private final int csetOrigin; + private final int csetTarget; + private MergeResolutionStrategy p2MergeCommon; + private int csetMergeParent; + private final AnnotateRev annotatedRevision; + private HgCallbackTargetException error; + + public BlameBlockInspector(HgDataFile df, int fileRevIndex, HgBlameInspector inspector, int originCset, int targetCset) { + assert inspector != null; + insp = inspector; + annotatedRevision = new AnnotateRev(); + annotatedRevision.set(df, fileRevIndex); + csetOrigin = originCset; + csetTarget = targetCset; + } + + public void setMergeParent2(MergeResolutionStrategy p2MergeStrategy, int parentCset2) { + p2MergeCommon = p2MergeStrategy; + csetMergeParent = parentCset2; + } + + @Override + public void begin(LineSequence s1, LineSequence s2) { + super.begin(s1, s2); + if (shallStop()) { + return; + } + ContentBlock originContent = new ContentBlock(s1); + ContentBlock targetContent = new ContentBlock(s2); + annotatedRevision.set(originContent, targetContent); + annotatedRevision.set(csetOrigin, csetTarget, p2MergeCommon != null ? csetMergeParent : NO_REVISION); + RevisionDescriptor.Recipient curious = Adaptable.Factory.getAdapter(insp, RevisionDescriptor.Recipient.class, null); + if (curious != null) { + try { + curious.start(annotatedRevision); + } catch (HgCallbackTargetException ex) { + error = ex; + } + } + } + + @Override + public void end() { + super.end(); + if (shallStop()) { + return; + } + RevisionDescriptor.Recipient curious = Adaptable.Factory.getAdapter(insp, RevisionDescriptor.Recipient.class, null); + if (curious != null) { + try { + curious.done(annotatedRevision); + } catch (HgCallbackTargetException ex) { + error = ex; + } + } + p2MergeCommon = null; + } + + @Override + protected void changed(int s1From, int s1To, int s2From, int s2To) { + if (shallStop()) { + return; + } + try { + if (p2MergeCommon != null) { + IntSliceSeq mergeRanges = p2MergeCommon.combineAndMarkRangesWithSource(s1From, s1To, s2From, s2To, csetOrigin, csetMergeParent); + + /* + * Usecases, how it USED TO BE initially: + * 3 lines changed to 10 lines. range of 10 lines breaks down to 2 from p2, 3 from p1, and 5 from p2. + * We report: 2 lines changed to 2(p2), then 1 line changed with 3(p1) and 5 lines added from p2. + * + * 10 lines changed to 3 lines, range of 3 lines breaks down to 2 line from p1 and 1 line from p2. + * We report: 2 lines changed to 2(p1) and 8 lines changed to 1(p2) + * + * NOW, lines from p2 are always reported as pure add (since we need their insertion point to be in p2, not in p1) + * and we try to consume p1 changes as soon as we see first p1's range + */ + int s1TotalLines = s1To - s1From, s1ConsumedLines = 0, s1Start = s1From; + + for (Iterator it = mergeRanges.iterator(); it.hasNext();) { + IntTuple mergeRange = it.next(); + final int rangeOrigin = mergeRange.at(0); + final int rangeStart = mergeRange.at(1); + final int rangeLen = mergeRange.at(2); + final boolean lastRange = it.hasNext(); + final int s1LinesLeft = s1TotalLines - s1ConsumedLines; + // how many lines we may report as changed (don't use more than in range unless it's the very last range) + final int s1LinesToBorrow = lastRange ? s1LinesLeft : Math.min(s1LinesLeft, rangeLen); + if (rangeOrigin != csetMergeParent && s1LinesToBorrow > 0) { + ChangeBlockImpl block = getChangeBlock(s1Start, s1LinesToBorrow, rangeStart, rangeLen); + block.setOriginAndTarget(rangeOrigin, csetTarget); + insp.changed(block); + s1ConsumedLines += s1LinesToBorrow; + s1Start += s1LinesToBorrow; + } else { + int blockInsPoint = rangeOrigin != csetMergeParent ? s1Start : p2MergeCommon.getLineInP2(rangeStart); + ChangeBlockImpl block = getAddBlock(rangeStart, rangeLen, blockInsPoint); + block.setOriginAndTarget(rangeOrigin, csetTarget); + insp.added(block); + } + } + if (s1ConsumedLines != s1TotalLines) { + assert s1ConsumedLines < s1TotalLines : String.format("Expected to process %d lines, but actually was %d", s1TotalLines, s1ConsumedLines); + // either there were no ranges from p1, whole s2From..s2To range came from p2, shall report as deleted + // or the ranges found were not enough to consume whole s2From..s2To + // The "deletion point" is shifted to the end of last csetOrigin->csetTarget change + int s2DeletePoint = s2From + s1ConsumedLines; + ChangeBlockImpl block = new ChangeBlockImpl(annotatedRevision.origin, null, s1Start, s1To - s1Start, -1, -1, -1, s2DeletePoint); + block.setOriginAndTarget(csetOrigin, csetTarget); + insp.deleted(block); + } + } else { + ChangeBlockImpl block = getChangeBlock(s1From, s1To - s1From, s2From, s2To - s2From); + block.setOriginAndTarget(csetOrigin, csetTarget); + insp.changed(block); + } + } catch (HgCallbackTargetException ex) { + error = ex; + } + } + + @Override + protected void added(int s1InsertPoint, int s2From, int s2To) { + if (shallStop()) { + return; + } + try { + if (p2MergeCommon != null) { + IntSliceSeq mergeRanges = p2MergeCommon.combineAndMarkRangesWithSource(s1InsertPoint, s2From, s2To, csetOrigin, csetMergeParent); + int insPoint = s1InsertPoint; // track changes to insertion point + for (IntTuple mergeRange : mergeRanges) { + int rangeOrigin = mergeRange.at(0); + int rangeStart = mergeRange.at(1); + int rangeLen = mergeRange.at(2); + // XXX likely need somewhat similar to the code above: + // int blockInsPoint = rangeOrigin != csetMergeParent ? s1Start : p2MergeCommon.reverseMapLine(rangeStart); + // + ChangeBlockImpl block = getAddBlock(rangeStart, rangeLen, insPoint); + block.setOriginAndTarget(rangeOrigin, csetTarget); + insp.added(block); + // indicate insPoint moved down number of lines we just reported + insPoint += rangeLen; + } + } else { + ChangeBlockImpl block = getAddBlock(s2From, s2To - s2From, s1InsertPoint); + block.setOriginAndTarget(csetOrigin, csetTarget); + insp.added(block); + } + } catch (HgCallbackTargetException ex) { + error = ex; + } + } + + @Override + protected void deleted(int s2DeletePoint, int s1From, int s1To) { + if (shallStop()) { + return; + } + try { + ChangeBlockImpl block = new ChangeBlockImpl(annotatedRevision.origin, null, s1From, s1To - s1From, -1, -1, -1, s2DeletePoint); + block.setOriginAndTarget(csetOrigin, csetTarget); + insp.deleted(block); + } catch (HgCallbackTargetException ex) { + error = ex; + } + } + + @Override + protected void unchanged(int s1From, int s2From, int length) { + if (shallStop()) { + return; + } + try { + EqualBlockImpl block = new EqualBlockImpl(s1From, s2From, length, annotatedRevision.target); + block.setOriginAndTarget(csetOrigin, csetTarget); + insp.same(block); + } catch (HgCallbackTargetException ex) { + error = ex; + } + } + + void checkErrors() throws HgCallbackTargetException { + if (error != null) { + throw error; + } + } + + private boolean shallStop() { + return error != null; + } + + private ChangeBlockImpl getAddBlock(int start, int len, int insPoint) { + return new ChangeBlockImpl(null, annotatedRevision.target, -1, -1, start, len, insPoint, -1); + } + + private ChangeBlockImpl getChangeBlock(int start1, int len1, int start2, int len2) { + return new ChangeBlockImpl(annotatedRevision.origin, annotatedRevision.target, start1, len1, start2, len2, start1, start2); + } + } + + private static class BlockImpl implements Block { + private int originCset; + private int targetCset; + + void setOriginAndTarget(int originChangesetIndex, int targetChangesetIndex) { + // XXX perhaps, shall be part of Inspector API, rather than Block's + // as they don't change between blocks (although the moment about merged revisions) + // is not yet clear to me + originCset = originChangesetIndex; + targetCset = targetChangesetIndex; + } + + public int originChangesetIndex() { + return originCset; + } + + public int targetChangesetIndex() { + return targetCset; + } + } + + private static class EqualBlockImpl extends BlockImpl implements EqualBlock { + private final int start1, start2; + private final int length; + private final ContentBlock fullContent; + private FilterBlock myContent; + + EqualBlockImpl(int blockStartSeq1, int blockStartSeq2, int blockLength, ContentBlock targetContent) { + start1 = blockStartSeq1; + start2 = blockStartSeq2; + length = blockLength; + fullContent = targetContent; + } + + public int originStart() { + return start1; + } + + public int targetStart() { + return start2; + } + + public int length() { + return length; + } + + public BlockData content() { + if (myContent == null) { + myContent = new FilterBlock(fullContent, start2, length); + } + return myContent; + } + + @Override + public String toString() { + return String.format("@@ [%d..%d) == [%d..%d) @@", start1, start1+length, start2, start2+length); + } + } + + private static class ChangeBlockImpl extends BlockImpl implements ChangeBlock { + private final ContentBlock oldContent; + private final ContentBlock newContent; + private final int s1Start; + private final int s1Len; + private final int s2Start; + private final int s2Len; + private final int s1InsertPoint; + private final int s2DeletePoint; + private FilterBlock addedBlock, removedBlock; + + public ChangeBlockImpl(ContentBlock c1, ContentBlock c2, int s1Start, int s1Len, int s2Start, int s2Len, int s1InsertPoint, int s2DeletePoint) { + oldContent = c1; + newContent = c2; + this.s1Start = s1Start; + this.s1Len = s1Len; + this.s2Start = s2Start; + this.s2Len = s2Len; + this.s1InsertPoint = s1InsertPoint; + this.s2DeletePoint = s2DeletePoint; + } + + public int insertedAt() { + return s1InsertPoint; + } + + public int firstAddedLine() { + return s2Start; + } + + public int totalAddedLines() { + return s2Len; + } + + public BlockData addedLines() { + if (addedBlock == null) { + addedBlock = new FilterBlock(newContent, firstAddedLine(), totalAddedLines()); + } + return addedBlock; + } + + public int removedAt() { + return s2DeletePoint; + } + + public int firstRemovedLine() { + return s1Start; + } + + public int totalRemovedLines() { + return s1Len; + } + + public BlockData removedLines() { + if (removedBlock == null) { + removedBlock = new FilterBlock(oldContent, firstRemovedLine(), totalRemovedLines()); + } + return removedBlock; + } + + @Override + public String toString() { + if (s2DeletePoint == -1) { + return String.format("@@ -%d,0 +%d,%d @@", insertedAt(), firstAddedLine(), totalAddedLines()); + } else if (s1InsertPoint == -1) { + // delete only + return String.format("@@ -%d,%d +%d,0 @@", firstRemovedLine(), totalRemovedLines(), removedAt()); + } + return String.format("@@ -%d,%d +%d,%d @@", firstRemovedLine(), totalRemovedLines(), firstAddedLine(), totalAddedLines()); + } + } + + private static class SingleLine implements BlockData { + private final ByteChain line; + + public SingleLine(ByteChain lineContent) { + line = lineContent; + } + + public BlockData elementAt(int index) { + assert false; + return null; + } + + public int elementCount() { + return 0; + } + + public byte[] asArray() { + return line.data(); + } + } + + private static class ContentBlock implements BlockData { + private final LineSequence seq; + + public ContentBlock(LineSequence sequence) { + seq = sequence; + } + + public BlockData elementAt(int index) { + return new SingleLine(seq.chunk(index)); + } + + public int elementCount() { + return seq.chunkCount() - 1; + } + + public byte[] asArray() { + return seq.data(0, seq.chunkCount() - 1); + } + } + + private static class FilterBlock implements BlockData { + private final ContentBlock contentBlock; + private final int from; + private final int length; + + public FilterBlock(ContentBlock bd, int startFrom, int len) { + assert bd != null; + assert startFrom + len < bd.seq.chunkCount(); // there's one extra chunk in the end, so strict less is ok + contentBlock = bd; + from = startFrom; + length = len; + } + + public BlockData elementAt(int index) { + if (index < 0 || index >= length) { + throw new IllegalArgumentException(String.format("Expected value from [0..%d), got %d", length, index)); + } + return contentBlock.elementAt(from + index); + } + + public int elementCount() { + return length; + } + + public byte[] asArray() { + return contentBlock.seq.data(from, from + length); + } + } + + private static class EqualBlocksCollector implements DiffHelper.MatchInspector { + private final RangePairSeq matches = new RangePairSeq(); + + public void begin(LineSequence s1, LineSequence s2) { + } + + public void match(int startSeq1, int startSeq2, int matchLength) { + matches.add(startSeq1, startSeq2, matchLength); + } + + public void end() { + } + + public void intersectWithTarget(int start, int length, IntVector result) { + int s = start; + for (int l = start, x = start + length; l < x; l++) { + if (!matches.includesTargetLine(l)) { + if (l - s > 0) { + result.add(s); + result.add(l - s); + } + s = l+1; + } + } + if (s < start+length) { + result.add(s); + result.add((start + length) - s); + } + } + + } + + interface MergeResolutionStrategy { + /** + * breaks region [start2..end2) into ranges according to deduced (or simply guessed) + * matching of [start1..end1) lines to lines in source1 and source2 + * @return list of tuples (source, start, length), where source is one of the identifiers supplied + */ + public IntSliceSeq combineAndMarkRangesWithSource(int start1, int end1, int start2, int end2, int source1, int source2); + public IntSliceSeq combineAndMarkRangesWithSource(int insPoint, int start, int end, int source1, int source2); + public int getLineInP2(int mergeLine); + } + + // report lines as merged from p2 solely based on whether target line belongs + // to a region that is equal to p2 region + private static class MergeStrategy1 implements MergeResolutionStrategy { + // equal ranges in p2 and merged revision + private final RangePairSeq matches; + private final IntSliceSeq mergeRanges; + + public MergeStrategy1(RangePairSeq p2EqualToM) { + matches = p2EqualToM; + mergeRanges = new IntSliceSeq(3, 10, 10); + } + + /* + * intersects [start..start+length) with ranges of target lines, and based on the intersection + * breaks initial range into smaller ranges and records them into result, with marker to indicate + * whether the range is from initial range (markerSource) or is a result of the intersection with target + * (markerTarget) + */ + private IntSliceSeq doCombine(int start, int length, int markerSource, int markerTarget) { + mergeRanges.clear(); + assert mergeRanges.sliceSize() == 3; + int sourceStart = start, targetStart = start, sourceEnd = start + length; + for (int l = sourceStart; l < sourceEnd; l++) { + if (matches.includesTargetLine(l)) { + // l is from target + if (sourceStart < l) { + // few lines from source range were not in the target, report them + mergeRanges.add(markerSource, sourceStart, l - sourceStart); + } + // indicate the earliest line from source range to use + sourceStart = l + 1; + } else { + // l is not in target + if (targetStart < l) { + // report lines from target range + mergeRanges.add(markerTarget, targetStart, l - targetStart); + } + // next line *may* be from target + targetStart = l + 1; + } + } + // if source range end with line from target, sourceStart would be == sourceEnd, and we need to add range with markerTarget + // if source range doesn't end with target line, targetStart == sourceEnd, while sourceStart < sourceEnd + if (sourceStart < sourceEnd) { + assert targetStart == sourceEnd; + // something left from the source range + mergeRanges.add(markerSource, sourceStart, sourceEnd - sourceStart); + } else if (targetStart < sourceEnd) { + assert sourceStart == sourceEnd; + mergeRanges.add(markerTarget, targetStart, sourceEnd - targetStart); + } + return mergeRanges; + } + + public int getLineInP2(int mergeLine) { + return matches.reverseMapLine(mergeLine); + } + + public IntSliceSeq combineAndMarkRangesWithSource(int start1, int end1, int start2, int end2, int source1, int source2) { + return doCombine(start2, end2 - start2, source1, source2); + } + + public IntSliceSeq combineAndMarkRangesWithSource(int insPoint, int start, int end, int source1, int source2) { + return doCombine(start, end - start, source1, source2); + } + } + + private static class MergeStrategy2 implements MergeResolutionStrategy { + // equal ranges in p2 and merged revision + private final List matches; + private final IntSliceSeq mergeRanges; + private final DiffRangeMap p1ToBase; + private final DiffRangeMap baseToP2; + + public MergeStrategy2(List p2EqualToM, DiffRangeMap p1ToBaseRanges, DiffRangeMap baseToP2Ranges) { + matches = p2EqualToM; + p1ToBase = p1ToBaseRanges; + baseToP2= baseToP2Ranges; + mergeRanges = new IntSliceSeq(3, 10, 10); + } + + + public IntSliceSeq combineAndMarkRangesWithSource(int insPoint, int start, int end, int source1, int source2) { + return combineAndMarkRangesWithSource(insPoint, insPoint, start, end, source1, source2); + } + + public IntSliceSeq combineAndMarkRangesWithSource(int start1, int end1, int start2, int end2, int source1, int source2) { + mergeRanges.clear(); + IntSliceSeq mergedLines = new IntSliceSeq(2, end2-start2, 0); + for (int i = start2; i < end2; i++) { + mergedLines.add(source1, 0); + } + // [s1Start..s1End) // range in p1 seen as changed in m + for (RangePair p1_b : p1ToBase.findInSource(start1, end1)) { + // there might be few ranges in (p1-base) that overlap with (p1-m) changes + for (RangePair b_p2 : baseToP2.findInSource(p1_b.start2(), p1_b.end2())) { + // regions in p2 that correspond to affected regions in base + for (int p2Line = b_p2.start2(); p2Line < b_p2.end2(); p2Line++) { + for (RangePairSeq eq : matches) { + if (eq.includesOriginLine(p2Line)) { + // this line in p2 is equal to some line in merge + int mergeLine = eq.mapLineIndex(p2Line); + if (mergeLine >= start2 && mergeLine < end2) { + mergedLines.set(mergeLine - start2, source2, p2Line); + } + } + } + } + } + } + int lineCount = 0, start = start2; + int lastSeenSource = source1; + for (IntTuple t : mergedLines) { + if (t.at(0) == lastSeenSource) { + lineCount++; + } else { + if (lineCount > 0) { + mergeRanges.add(lastSeenSource, start, lineCount); + start += lineCount; + } + lineCount = 1; + lastSeenSource = t.at(0); + } + } + if (lineCount > 0) { + mergeRanges.add(lastSeenSource, start, lineCount); + } + return mergeRanges; + } + + public int getLineInP2(int mergeLine) { + for (RangePairSeq eq : matches) { + if (eq.includesTargetLine(mergeLine)) { + return eq.reverseMapLine(mergeLine); + } + } + return -1; + } + } + + + private static class AnnotateRev implements RevisionDescriptor { + public ContentBlock origin, target; + public int originCset, targetCset, mergeCset, fileRevIndex; + public HgDataFile df; + + public void set(HgDataFile file, int fileRev) { + df = file; + fileRevIndex = fileRev; + } + public void set(ContentBlock o, ContentBlock t) { + origin = o; + target = t; + } + public void set(int o, int t, int m) { + originCset = o; + targetCset = t; + mergeCset = m; + } + + public BlockData origin() { + return origin; + } + + public BlockData target() { + return target; + } + + public int originChangesetIndex() { + return originCset; + } + + public int targetChangesetIndex() { + return targetCset; + } + + public boolean isMerge() { + return mergeCset != NO_REVISION; + } + + public int mergeChangesetIndex() { + return mergeCset; + } + + public int fileRevisionIndex() { + return fileRevIndex; + } + public HgDataFile file() { + return df; + } + @Override + public String toString() { + if (isMerge()) { + return String.format("[%d,%d->%d]", originCset, mergeCset, targetCset); + } + return String.format("[%d->%d]", originCset, targetCset); + } + } + + public static void main(String[] args) { + EqualBlocksCollector bc = new EqualBlocksCollector(); + bc.match(-1, 5, 3); + bc.match(-1, 10, 2); + bc.match(-1, 15, 3); + bc.match(-1, 20, 3); + IntVector r = new IntVector(); + bc.intersectWithTarget(7, 10, r); + for (int i = 0; i < r.size(); i+=2) { + System.out.printf("[%d..%d) ", r.get(i), r.get(i) + r.get(i+1)); + } + System.out.println(); + MergeStrategy1 ms = new MergeStrategy1(bc.matches); + IntSliceSeq mr = ms.doCombine(0, 16, 508, 514); + for (IntTuple t : mr) { + System.out.printf("%d:[%d..%d) ", t.at(0), t.at(1), t.at(1) + t.at(2)); + } + System.out.println(); + System.out.println(); + DiffRangeMap m1 = new DiffRangeMap(); // p1 -> base + m1.match(0, 0, 1); // =1..1 -> 1..1 + m1.match(7, 3, 0); // *2..7 -> 2..3 + DiffRangeMap m2 = new DiffRangeMap(); // base -> p2 + m2.match(0, 0, 1); // =1..1 -> 1..1 + m2.match(3, 3, 0); // *2..3 -> 2..3 + RangePairSeq eq1 = new RangePairSeq(); + eq1.add(0, 0, 3); + RangePairSeq eq2 = new RangePairSeq(); + eq2.add(0, 4, 3); + MergeStrategy2 ms2 = new MergeStrategy2(Arrays.asList(eq1, eq2), m1, m2); + mr = ms2.combineAndMarkRangesWithSource(5, 7, 5, 7, 33, 44); + for (IntTuple t : mr) { + System.out.printf("%d:[%d..%d) ", t.at(0), t.at(1), t.at(1) + t.at(2)); + } + } +} diff -r 992fa84e7885 -r 7839ff0bfd78 src/org/tmatesoft/hg/internal/diff/DiffHelper.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/org/tmatesoft/hg/internal/diff/DiffHelper.java Wed Aug 14 14:51:51 2013 +0200 @@ -0,0 +1,442 @@ +/* + * Copyright (c) 2013 TMate Software Ltd + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; version 2 of the License. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * For information on how to redistribute this software under + * the terms of a license other than GNU General Public License + * contact TMate Software at support@hg4j.com + */ +package org.tmatesoft.hg.internal.diff; + +import java.util.ArrayList; +import java.util.HashMap; +import java.util.Map; + +import org.tmatesoft.hg.internal.IntMap; +import org.tmatesoft.hg.internal.IntSliceSeq; +import org.tmatesoft.hg.internal.IntTuple; +import org.tmatesoft.hg.internal.IntVector; + +/** + * Mercurial cares about changes only up to the line level, e.g. a simple file version dump in manifest looks like (RevlogDump output): + * + * 522: 233748 0 103 17438 433 522 521 -1 756073cf2321df44d3ed0585f2a5754bc8a1b2f6 + * : + * 3487..3578, 91:src/org/tmatesoft/hg/core/HgIterateDirection.java\00add61a8a665c5d8f092210767f812fe0d335ac8 + * + * I.e. for the {fname}{revision} entry format of manifest, not only {revision} is changed, but the whole line, with unchanged {fname} is recorded + * in the patch. + * + * Mercurial paper describes reasons for choosing this approach to delta generation, too. + * + * + * @author Artem Tikhomirov + * @author TMate Software Ltd. + */ +public class DiffHelper> { + + private Map chunk2UseIndex; + private T seq1, seq2; + + // get filled by #longestMatch, track start of common sequence in seq1 and seq2, respectively + private int matchStartS1, matchStartS2; + + private MatchInspector matchInspector; + + public void init(T s1, T s2) { + seq1 = s1; + seq2 = s2; + prepare(s2); + } + + public void init(T s1) { + if (seq2 == null) { + throw new IllegalStateException("Use this #init() only when target sequence shall be matched against different origin"); + } + seq1 = s1; + } + + + private void prepare(T s2) { + chunk2UseIndex = new HashMap(); + for (int i = 0, len = s2.chunkCount(); i < len; i++) { + Object bc = s2.chunk(i); + IntVector loc = chunk2UseIndex.get(bc); + if (loc == null) { + chunk2UseIndex.put(bc, loc = new IntVector()); + } + loc.add(i); + // bc.registerUseIn(i) - BEWARE, use of bc here is incorrect + // in this case need to find the only ByteChain to keep indexes + // i.e. when there are few equal ByteChain instances, notion of "usedIn" shall be either shared (reference same vector) + // or kept within only one of them + } + } + + public void findMatchingBlocks(MatchInspector insp) { + insp.begin(seq1, seq2); + matchInspector = insp; + findMatchingBlocks(0, seq1.chunkCount(), 0, seq2.chunkCount()); + insp.end(); + } + + /** + * look up every line in s2 that match lines in s1 + * idea: pure additions in s2 are diff-ed against s1 again and again, to see if there are any matches + */ + void findAllMatchAlternatives(final MatchInspector insp) { + assert seq1.chunkCount() > 0; + final IntSliceSeq insertions = new IntSliceSeq(2); + final boolean matchedAny[] = new boolean[] {false}; + DeltaInspector myInsp = new DeltaInspector() { + @Override + protected void unchanged(int s1From, int s2From, int length) { + matchedAny[0] = true; + insp.match(s1From, s2From, length); + } + @Override + protected void added(int s1InsertPoint, int s2From, int s2To) { + insertions.add(s2From, s2To); + } + }; + matchInspector = myInsp; + myInsp.begin(seq1, seq2); + IntSliceSeq s2RangesToCheck = new IntSliceSeq(2, 1, 0); + s2RangesToCheck.add(0, seq2.chunkCount()); + do { + IntSliceSeq nextCheck = new IntSliceSeq(2); + for (IntTuple t : s2RangesToCheck) { + int s2Start = t.at(0); + int s2End = t.at(1); + myInsp.changeStartS1 = 0; + myInsp.changeStartS2 = s2Start; + insp.begin(seq1, seq2); + matchedAny[0] = false; + findMatchingBlocks(0, seq1.chunkCount(), s2Start, s2End); + insp.end(); + myInsp.end(); + if (matchedAny[0]) { + nextCheck.addAll(insertions); + } + insertions.clear(); + } + s2RangesToCheck = nextCheck; + } while (s2RangesToCheck.size() > 0); + } + + /** + * implementation based on Python's difflib.py and SequenceMatcher + */ + public int longestMatch(int startS1, int endS1, int startS2, int endS2) { + matchStartS1 = matchStartS2 = 0; + int maxLength = 0; + IntMap chunkIndex2MatchCount = new IntMap(8); + for (int i = startS1; i < endS1; i++) { + Object bc = seq1.chunk(i); + IntVector occurencesInS2 = chunk2UseIndex.get(bc); + if (occurencesInS2 == null) { + chunkIndex2MatchCount.clear(); + continue; + } + IntMap newChunkIndex2MatchCount = new IntMap(8); + for (int j : occurencesInS2.toArray()) { + // s1[i] == s2[j] + if (j < startS2) { + continue; + } + if (j >= endS2) { + break; + } + int prevChunkMatches = chunkIndex2MatchCount.containsKey(j-1) ? chunkIndex2MatchCount.get(j-1) : 0; + int k = prevChunkMatches + 1; + newChunkIndex2MatchCount.put(j, k); + if (k > maxLength) { + matchStartS1 = i-k+1; + matchStartS2 = j-k+1; + maxLength = k; + } + } + chunkIndex2MatchCount = newChunkIndex2MatchCount; + } + return maxLength; + } + + private void findMatchingBlocks(int startS1, int endS1, int startS2, int endS2) { + int matchLength = longestMatch(startS1, endS1, startS2, endS2); + if (matchLength > 0) { + final int saveStartS1 = matchStartS1, saveStartS2 = matchStartS2; + if (startS1 < matchStartS1 && startS2 < matchStartS2) { + findMatchingBlocks(startS1, matchStartS1, startS2, matchStartS2); + } + matchInspector.match(saveStartS1, saveStartS2, matchLength); + if (saveStartS1+matchLength < endS1 && saveStartS2+matchLength < endS2) { + findMatchingBlocks(saveStartS1 + matchLength, endS1, saveStartS2 + matchLength, endS2); + } + } + } + + public interface MatchInspector> { + void begin(T s1, T s2); + void match(int startSeq1, int startSeq2, int matchLength); + void end(); + } + + static class MatchDumpInspector> implements MatchInspector { + private int matchCount; + + public void begin(T s1, T s2) { + matchCount = 0; + } + + public void match(int startSeq1, int startSeq2, int matchLength) { + matchCount++; + System.out.printf("match #%d: from line #%d and line #%d of length %d\n", matchCount, startSeq1, startSeq2, matchLength); + } + + public void end() { + if (matchCount == 0) { + System.out.println("NO MATCHES FOUND!"); + } + } + } + + /** + * Matcher implementation that translates "match/equal" notification to a delta-style "added/removed/changed". + */ + public static class DeltaInspector> implements MatchInspector { + protected int changeStartS1, changeStartS2; + protected T seq1, seq2; + + public void begin(T s1, T s2) { + seq1 = s1; + seq2 = s2; + changeStartS1 = changeStartS2 = 0; + } + + public void match(int startSeq1, int startSeq2, int matchLength) { + reportDeltaElement(startSeq1, startSeq2, matchLength); + changeStartS1 = startSeq1 + matchLength; + changeStartS2 = startSeq2 + matchLength; + } + + public void end() { + if (changeStartS1 < seq1.chunkCount()-1 || changeStartS2 < seq2.chunkCount()-1) { + reportDeltaElement(seq1.chunkCount()-1, seq2.chunkCount()-1, 0); + } + } + + protected void reportDeltaElement(int matchStartSeq1, int matchStartSeq2, int matchLength) { + if (changeStartS1 < matchStartSeq1) { + if (changeStartS2 < matchStartSeq2) { + changed(changeStartS1, matchStartSeq1, changeStartS2, matchStartSeq2); + } else { + assert changeStartS2 == matchStartSeq2; + deleted(matchStartSeq2, changeStartS1, matchStartSeq1); + } + } else { + assert changeStartS1 == matchStartSeq1; + if(changeStartS2 < matchStartSeq2) { + added(changeStartS1, changeStartS2, matchStartSeq2); + } else { + assert changeStartS2 == matchStartSeq2; + if (matchStartSeq1 > 0 || matchStartSeq2 > 0) { + assert false : String.format("adjustent equal blocks %d, %d and %d,%d", changeStartS1, matchStartSeq1, changeStartS2, matchStartSeq2); + } + } + } + if (matchLength > 0) { + unchanged(matchStartSeq1, matchStartSeq2, matchLength); + } + } + + /** + * [s1From..s1To) replaced with [s2From..s2To) + */ + protected void changed(int s1From, int s1To, int s2From, int s2To) { + // NO-OP + } + + protected void deleted(int s2DeletePoint, int s1From, int s1To) { + // NO-OP + } + + protected void added(int s1InsertPoint, int s2From, int s2To) { + // NO-OP + } + + protected void unchanged(int s1From, int s2From, int length) { + // NO-OP + } + } + + public static class DeltaDumpInspector> extends DeltaInspector { + + @Override + protected void changed(int s1From, int s1To, int s2From, int s2To) { + System.out.printf("changed [%d..%d) with [%d..%d)\n", s1From, s1To, s2From, s2To); + } + + @Override + protected void deleted(int s2DeletionPoint, int s1From, int s1To) { + System.out.printf("deleted [%d..%d)\n", s1From, s1To); + } + + @Override + protected void added(int s1InsertPoint, int s2From, int s2To) { + System.out.printf("added [%d..%d) at %d\n", s2From, s2To, s1InsertPoint); + } + + @Override + protected void unchanged(int s1From, int s2From, int length) { + System.out.printf("same [%d..%d) and [%d..%d)\n", s1From, s1From + length, s2From, s2From + length); + } + } + + /** + * Generic sequence of chunk, where chunk is anything comparable to another chunk, e.g. a string or a single char + * Sequence diff algorithm above doesn't care about sequence nature. + */ + public interface ChunkSequence { + public T chunk(int index); + public int chunkCount(); + } + + public static final class LineSequence implements ChunkSequence { + + private final byte[] input; + private ArrayList lines; + + public LineSequence(byte[] data) { + input = data; + } + + public static LineSequence newlines(byte[] array) { + return new LineSequence(array).splitByNewlines(); + } + + // sequence ends with fake, empty line chunk + public LineSequence splitByNewlines() { + lines = new ArrayList(); + int lastStart = 0; + for (int i = 0; i < input.length; i++) { + if (input[i] == '\n') { + lines.add(new ByteChain(lastStart, i+1)); + lastStart = i+1; + } else if (input[i] == '\r') { + if (i+1 < input.length && input[i+1] == '\n') { + i++; + } + lines.add(new ByteChain(lastStart, i+1)); + lastStart = i+1; + } + } + if (lastStart < input.length) { + lines.add(new ByteChain(lastStart, input.length)); + } + // empty chunk to keep offset of input end + lines.add(new ByteChain(input.length)); + return this; + } + + public ByteChain chunk(int index) { + return lines.get(index); + } + + public int chunkCount() { + return lines.size(); + } + + public byte[] data(int chunkFrom, int chunkTo) { + if (chunkFrom == chunkTo) { + return new byte[0]; + } + int from = chunk(chunkFrom).getOffset(), to = chunk(chunkTo).getOffset(); + byte[] rv = new byte[to - from]; + System.arraycopy(input, from, rv, 0, rv.length); + return rv; + } + + + public final class ByteChain { + private final int start, end; + private final int hash; + + /** + * construct a chunk with a sole purpose to keep + * offset of the data end + */ + ByteChain(int offset) { + start = end = offset; + // ensure this chunk doesn't match trailing chunk of another sequence + hash = System.identityHashCode(this); + } + + ByteChain(int s, int e) { + start = s; + end = e; + hash = calcHash(input, s, e); + } + + /** + * byte offset of the this ByteChain inside ChainSequence + */ + public int getOffset() { + return start; + } + + public byte[] data() { + byte[] rv = new byte[end - start]; + System.arraycopy(input, start, rv, 0, rv.length); + return rv; + } + + @Override + public boolean equals(Object obj) { + if (obj == null || obj.getClass() != ByteChain.class) { + return false; + } + ByteChain other = (ByteChain) obj; + if (other.hash != hash || other.end - other.start != end - start) { + return false; + } + return other.match(input, start); + } + + private boolean match(byte[] oi, int from) { + for (int i = start, j = from; i < end; i++, j++) { + if (LineSequence.this.input[i] != oi[j]) { + return false; + } + } + return true; + } + + @Override + public int hashCode() { + return hash; + } + + @Override + public String toString() { + return String.format("[@%d\"%s\"]", start, new String(data())); + } + } + + // same as Arrays.hashCode(byte[]), just for a slice of a bigger array + static int calcHash(byte[] data, int from, int to) { + int result = 1; + for (int i = from; i < to; i++) { + result = 31 * result + data[i]; + } + return result; + } + } +} diff -r 992fa84e7885 -r 7839ff0bfd78 src/org/tmatesoft/hg/internal/diff/DiffRangeMap.java --- a/src/org/tmatesoft/hg/internal/diff/DiffRangeMap.java Thu Aug 08 21:32:22 2013 +0200 +++ b/src/org/tmatesoft/hg/internal/diff/DiffRangeMap.java Wed Aug 14 14:51:51 2013 +0200 @@ -18,11 +18,10 @@ import java.util.ArrayList; -import org.tmatesoft.hg.internal.DiffHelper; -import org.tmatesoft.hg.internal.DiffHelper.MatchInspector; import org.tmatesoft.hg.internal.IntSliceSeq; import org.tmatesoft.hg.internal.IntTuple; -import org.tmatesoft.hg.internal.DiffHelper.ChunkSequence; +import org.tmatesoft.hg.internal.diff.DiffHelper.ChunkSequence; +import org.tmatesoft.hg.internal.diff.DiffHelper.MatchInspector; /** * Sequence of pairs of ranges (s1Start,s1End) - (s2Start, s2End) diff -r 992fa84e7885 -r 7839ff0bfd78 src/org/tmatesoft/hg/internal/diff/ForwardAnnotateInspector.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/org/tmatesoft/hg/internal/diff/ForwardAnnotateInspector.java Wed Aug 14 14:51:51 2013 +0200 @@ -0,0 +1,145 @@ +/* + * Copyright (c) 2013 TMate Software Ltd + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; version 2 of the License. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * For information on how to redistribute this software under + * the terms of a license other than GNU General Public License + * contact TMate Software at support@hg4j.com + */ +package org.tmatesoft.hg.internal.diff; + +import org.tmatesoft.hg.core.HgAnnotateCommand.Inspector; +import org.tmatesoft.hg.core.HgBlameInspector; +import org.tmatesoft.hg.core.HgCallbackTargetException; +import org.tmatesoft.hg.core.HgIterateDirection; +import org.tmatesoft.hg.internal.IntMap; +import org.tmatesoft.hg.internal.IntSliceSeq; +import org.tmatesoft.hg.internal.IntTuple; +import org.tmatesoft.hg.util.CancelSupport; +import org.tmatesoft.hg.util.CancelledException; +import org.tmatesoft.hg.util.ProgressSupport; + +/** + * Annotate file history iterating from parents to children + * + * At the moment, doesn't handle start from any revision but 0 + * + * (+) May report annotate for any revision (with actual file change) in the visited range. + * + * @see ReverseAnnotateInspector + * @author Artem Tikhomirov + * @author TMate Software Ltd. + */ +public class ForwardAnnotateInspector implements HgBlameInspector, HgBlameInspector.RevisionDescriptor.Recipient { + final IntMap all = new IntMap(100); + // revision->map(lineNumber->lineContent) + private final IntMap> lineContent = new IntMap>(100); + private IntSliceSeq current; + private RevisionDescriptor revDescriptor; + + /** + * @return desired order of iteration for diff + */ + public HgIterateDirection iterateDirection() { + return HgIterateDirection.OldToNew; + } + + public void report(int revision, Inspector insp, ProgressSupport progress, CancelSupport cancel) throws HgCallbackTargetException, CancelledException { + int totalLines = 0; + if (!all.containsKey(revision)) { + throw new IllegalArgumentException(String.format("Revision %d has not been visited", revision)); + } + for (IntTuple t : all.get(revision)) { + totalLines += t.at(0); + } + progress.start(totalLines); + LineImpl li = new LineImpl(); + int line = 1; + for (IntTuple t : all.get(revision)) { + IntMap revLines = lineContent.get(t.at(1)); + for (int i = 0, x = t.at(0); i < x; i++) { + final int lineInRev = t.at(2) + i; + final byte[] lc = revLines.get(lineInRev); + li.init(line++, lineInRev+1, t.at(1), lc); + insp.next(li); + progress.worked(1); + cancel.checkCancelled(); + } + } + progress.done(); + } + + public void start(RevisionDescriptor rd) throws HgCallbackTargetException { + all.put(rd.targetChangesetIndex(), current = new IntSliceSeq(3)); + revDescriptor = rd; + } + + public void done(RevisionDescriptor rd) throws HgCallbackTargetException { + revDescriptor = null; + } + + public void same(EqualBlock block) throws HgCallbackTargetException { + copyBlock(block.originChangesetIndex(), block.originStart(), block.length()); + } + + public void added(AddBlock block) throws HgCallbackTargetException { + if (revDescriptor.isMerge() && block.originChangesetIndex() == revDescriptor.mergeChangesetIndex()) { + copyBlock(block.originChangesetIndex(), block.insertedAt(), block.totalAddedLines()); + return; + } + BlockData addedLines = block.addedLines(); + IntMap revLines = lineContent.get(block.targetChangesetIndex()); + if (revLines == null) { + lineContent.put(block.targetChangesetIndex(), revLines = new IntMap(block.totalAddedLines())); + } + for (int i = 0; i < block.totalAddedLines(); i++) { + revLines.put(block.firstAddedLine() + i, addedLines.elementAt(i).asArray()); + } + current.add(block.totalAddedLines(), block.targetChangesetIndex(), block.firstAddedLine()); + } + + public void changed(ChangeBlock block) throws HgCallbackTargetException { + added(block); + } + + public void deleted(DeleteBlock block) throws HgCallbackTargetException { + } + + private void copyBlock(int originChangesetIndex, int blockStart, int length) { + IntSliceSeq origin = all.get(originChangesetIndex); + assert origin != null; // shall visit parents before came to this child + int originPos = 0; + int targetBlockLen = length; + for (IntTuple t : origin) { + int originBlockLen = t.at(0); + int originBlockEnd = originPos + originBlockLen; + if (originBlockEnd > blockStart) { + // part of origin block from blockStart up to originBlockEnd, but not more + // than size of the block (when blockStart is out of block start, i.e. < originPos) + int originBlockOverlap = Math.min(originBlockLen, originBlockEnd - blockStart); + assert originBlockOverlap > 0; + // eat as much as there's left in the block being copied + int originBlockConsumed = Math.min(originBlockOverlap, targetBlockLen); + int originBlockLine = t.at(2); + if (originPos < blockStart) { + originBlockLine += originBlockLen-originBlockOverlap; + } + // copy fragment of original block; + current.add(originBlockConsumed, t.at(1), originBlockLine); + targetBlockLen -= originBlockConsumed; + if (targetBlockLen == 0) { + break; + } + } + originPos += originBlockLen; + } + } +} \ No newline at end of file diff -r 992fa84e7885 -r 7839ff0bfd78 src/org/tmatesoft/hg/internal/diff/LineImpl.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/org/tmatesoft/hg/internal/diff/LineImpl.java Wed Aug 14 14:51:51 2013 +0200 @@ -0,0 +1,54 @@ +/* + * Copyright (c) 2013 TMate Software Ltd + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; version 2 of the License. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * For information on how to redistribute this software under + * the terms of a license other than GNU General Public License + * contact TMate Software at support@hg4j.com + */ +package org.tmatesoft.hg.internal.diff; + +import org.tmatesoft.hg.core.HgAnnotateCommand.LineInfo; + +/** + * @author Artem Tikhomirov + * @author TMate Software Ltd. + */ +final class LineImpl implements LineInfo { + private int ln; + private int origLine; + private int rev; + private byte[] content; + + void init(int line, int firstAppearance, int csetRev, byte[] cnt) { + ln = line; + origLine = firstAppearance; + rev = csetRev; + content = cnt; + } + + public int getLineNumber() { + return ln; + } + + + public int getOriginLineNumber() { + return origLine; + } + + public int getChangesetIndex() { + return rev; + } + + public byte[] getContent() { + return content; + } +} \ No newline at end of file diff -r 992fa84e7885 -r 7839ff0bfd78 src/org/tmatesoft/hg/internal/diff/RangePairSeq.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/org/tmatesoft/hg/internal/diff/RangePairSeq.java Wed Aug 14 14:51:51 2013 +0200 @@ -0,0 +1,172 @@ +/* + * Copyright (c) 2013 TMate Software Ltd + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; version 2 of the License. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * For information on how to redistribute this software under + * the terms of a license other than GNU General Public License + * contact TMate Software at support@hg4j.com + */ +package org.tmatesoft.hg.internal.diff; + +import java.util.Formatter; + +import org.tmatesoft.hg.internal.IntSliceSeq; +import org.tmatesoft.hg.internal.IntTuple; + +/** + * Sequence of range pairs (denoted origin and target), {originStart, targetStart, length}, tailored for diff/annotate + * + * @author Artem Tikhomirov + * @author TMate Software Ltd. + */ +public final class RangePairSeq { + private final IntSliceSeq ranges = new IntSliceSeq(3); + + public void add(int start1, int start2, int length) { + int count = ranges.size(); + if (count > 0) { + int lastS1 = ranges.get(--count, 0); + int lastS2 = ranges.get(count, 1); + int lastLen = ranges.get(count, 2); + if (start1 == lastS1 + lastLen && start2 == lastS2 + lastLen) { + // new range continues the previous one - just increase the length + ranges.set(count, lastS1, lastS2, lastLen + length); + return; + } + } + ranges.add(start1, start2, length); + } + + public void clear() { + ranges.clear(); + } + + public int size() { + return ranges.size(); + } + + /** + * find out line index in the target that matches specified origin line + */ + public int mapLineIndex(int ln) { + for (IntTuple t : ranges) { + int s1 = t.at(0); + if (s1 > ln) { + return -1; + } + int l = t.at(2); + if (s1 + l > ln) { + int s2 = t.at(1); + return s2 + (ln - s1); + } + } + return -1; + } + + /** + * find out line index in origin that matches specified target line + */ + public int reverseMapLine(int targetLine) { + for (IntTuple t : ranges) { + int ts = t.at(1); + if (ts > targetLine) { + return -1; + } + int l = t.at(2); + if (ts + l > targetLine) { + int os = t.at(0); + return os + (targetLine - ts); + } + } + return -1; + } + + public RangePairSeq intersect(RangePairSeq target) { + RangePairSeq v = new RangePairSeq(); + for (IntTuple t : ranges) { + int originLine = t.at(0); + int targetLine = t.at(1); + int length = t.at(2); + int startTargetLine = -1, startOriginLine = -1, c = 0; + for (int j = 0; j < length; j++) { + int lnInFinal = target.mapLineIndex(targetLine + j); + if (lnInFinal == -1 || (startTargetLine != -1 && lnInFinal != startTargetLine + c)) { + // the line is not among "same" in ultimate origin + // or belongs to another/next "same" chunk + if (startOriginLine == -1) { + continue; + } + v.add(startOriginLine, startTargetLine, c); + c = 0; + startOriginLine = startTargetLine = -1; + // fall-through to check if it's not complete miss but a next chunk + } + if (lnInFinal != -1) { + if (startOriginLine == -1) { + startOriginLine = originLine + j; + startTargetLine = lnInFinal; + c = 1; + } else { + // lnInFinal != startTargetLine + s is covered above + assert lnInFinal == startTargetLine + c; + c++; + } + } + } + if (startOriginLine != -1) { + assert c > 0; + v.add(startOriginLine, startTargetLine, c); + } + } + return v; + } + + // true when specified line in origin is equal to a line in target + public boolean includesOriginLine(int ln) { + return includes(ln, 0); + } + + // true when specified line in target is equal to a line in origin + public boolean includesTargetLine(int ln) { + return includes(ln, 1); + } + + private boolean includes(int ln, int o) { + for (IntTuple t : ranges) { + int rangeStart = t.at(o); + if (rangeStart > ln) { + return false; + } + int rangeLen = t.at(2); + if (rangeStart + rangeLen > ln) { + return true; + } + } + return false; + } + + public CharSequence dump() { + StringBuilder sb = new StringBuilder(); + Formatter f = new Formatter(sb); + for (IntTuple t : ranges) { + int s1 = t.at(0); + int s2 = t.at(1); + int len = t.at(2); + f.format("[%d..%d) == [%d..%d); ", s1, s1 + len, s2, s2 + len); + } + return sb; + } + + @Override + public String toString() { + return String.format("RangeSeq[%d]:%s", size(), dump()); + } +} \ No newline at end of file diff -r 992fa84e7885 -r 7839ff0bfd78 src/org/tmatesoft/hg/internal/diff/ReverseAnnotateInspector.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/org/tmatesoft/hg/internal/diff/ReverseAnnotateInspector.java Wed Aug 14 14:51:51 2013 +0200 @@ -0,0 +1,168 @@ +/* + * Copyright (c) 2013 TMate Software Ltd + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; version 2 of the License. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * For information on how to redistribute this software under + * the terms of a license other than GNU General Public License + * contact TMate Software at support@hg4j.com + */ +package org.tmatesoft.hg.internal.diff; + + +import static org.tmatesoft.hg.repo.HgRepository.NO_REVISION; + +import java.util.Arrays; + +import org.tmatesoft.hg.core.HgAnnotateCommand; +import org.tmatesoft.hg.core.HgBlameInspector; +import org.tmatesoft.hg.core.HgIterateDirection; +import org.tmatesoft.hg.core.HgBlameInspector.RevisionDescriptor; +import org.tmatesoft.hg.core.HgCallbackTargetException; +import org.tmatesoft.hg.internal.IntMap; +import org.tmatesoft.hg.repo.HgInvalidStateException; +import org.tmatesoft.hg.util.CancelSupport; +import org.tmatesoft.hg.util.CancelledException; +import org.tmatesoft.hg.util.ProgressSupport; + +/** + * Produce output like 'hg annotate' does. + * Expects revisions to come in order from child to parent. + * Unlike {@link ForwardAnnotateInspector}, can be easily modified to report lines as soon as its origin is detected. + * + * (+) Handles annotate of partial history, at any moment lines with ({@link #knownLines} == false indicate lines + * that were added prior to any revision already visited. + * + * @author Artem Tikhomirov + * @author TMate Software Ltd. + */ +public class ReverseAnnotateInspector implements HgBlameInspector, RevisionDescriptor.Recipient { + + // keeps of equal blocks, origin to target, from some previous step + private RangePairSeq activeEquals; + // equal blocks of the current iteration, to be recalculated before next step + // to track line number (current target to ultimate target) mapping + private RangePairSeq intermediateEquals = new RangePairSeq(); + + private boolean[] knownLines; + private RevisionDescriptor revisionDescriptor; + private BlockData lineContent; + + private IntMap mergedRanges = new IntMap(10); + private IntMap equalRanges = new IntMap(10); + private boolean activeEqualsComesFromMerge = false; + + private int[] lineRevisions; + private int[] lineNumbers; + + /** + * @return desired order of iteration for diff + */ + public HgIterateDirection iterateDirection() { + return HgIterateDirection.NewToOld; + } + + public void report(int annotateRevIndex, HgAnnotateCommand.Inspector insp, ProgressSupport progress, CancelSupport cancel) throws HgCallbackTargetException, CancelledException { + LineImpl li = new LineImpl(); + progress.start(lineRevisions.length); + for (int i = 0; i < lineRevisions.length; i++) { + byte[] c = lineContent.elementAt(i).asArray(); + li.init(i+1, lineNumbers[i] + 1, lineRevisions[i], c); + insp.next(li); + progress.worked(1); + cancel.checkCancelled(); + } + progress.done(); + } + + public void start(RevisionDescriptor rd) { + revisionDescriptor = rd; + if (knownLines == null) { + lineContent = rd.target(); + knownLines = new boolean[lineContent.elementCount()]; + lineRevisions = new int [knownLines.length]; + Arrays.fill(lineRevisions, NO_REVISION); + lineNumbers = new int[knownLines.length]; + activeEquals = new RangePairSeq(); + activeEquals.add(0, 0, knownLines.length); + equalRanges.put(rd.targetChangesetIndex(), activeEquals); + } else { + activeEquals = equalRanges.get(rd.targetChangesetIndex()); + if (activeEquals == null) { + // we didn't see this target revision as origin yet + // the only way this may happen is that this revision was a merge parent + activeEquals = mergedRanges.get(rd.targetChangesetIndex()); + activeEqualsComesFromMerge = true; + if (activeEquals == null) { + throw new HgInvalidStateException(String.format("Can't find previously visited revision %d (while in %d->%1$d diff)", rd.targetChangesetIndex(), rd.originChangesetIndex())); + } + } + } + } + + public void done(RevisionDescriptor rd) { + // update line numbers of the intermediate target to point to ultimate target's line numbers + RangePairSeq v = intermediateEquals.intersect(activeEquals); + if (activeEqualsComesFromMerge) { + mergedRanges.put(rd.originChangesetIndex(), v); + } else { + equalRanges.put(rd.originChangesetIndex(), v); + } + if (rd.isMerge() && !mergedRanges.containsKey(rd.mergeChangesetIndex())) { + // seen merge, but no lines were merged from p2. + // Add empty range to avoid uncertainty when a parent of p2 pops in + mergedRanges.put(rd.mergeChangesetIndex(), new RangePairSeq()); + } + intermediateEquals.clear(); + activeEquals = null; + activeEqualsComesFromMerge = false; + revisionDescriptor = null; + } + + public void same(EqualBlock block) { + intermediateEquals.add(block.originStart(), block.targetStart(), block.length()); + } + + public void added(AddBlock block) { + RangePairSeq rs = null; + if (revisionDescriptor.isMerge() && block.originChangesetIndex() == revisionDescriptor.mergeChangesetIndex()) { + rs = mergedRanges.get(revisionDescriptor.mergeChangesetIndex()); + if (rs == null) { + mergedRanges.put(revisionDescriptor.mergeChangesetIndex(), rs = new RangePairSeq()); + } + } + if (activeEquals.size() == 0) { + return; + } + for (int i = 0, ln = block.firstAddedLine(), x = block.totalAddedLines(); i < x; i++, ln++) { + int lnInFinal = activeEquals.mapLineIndex(ln); + if (lnInFinal != -1/* && !knownLines[lnInFinal]*/) { + if (rs != null) { + rs.add(block.insertedAt() + i, lnInFinal, 1); + } else { + line(lnInFinal, ln, block.targetChangesetIndex()); + } + knownLines[lnInFinal] = true; + } + } + } + + public void changed(ChangeBlock block) { + added(block); + } + + public void deleted(DeleteBlock block) { + } + + private void line(int lineNumber, int firstAppearance, int changesetRevIndex) { + lineRevisions[lineNumber] = changesetRevIndex; + lineNumbers[lineNumber] = firstAppearance; + } +} \ No newline at end of file diff -r 992fa84e7885 -r 7839ff0bfd78 test/org/tmatesoft/hg/test/TestAuxUtilities.java --- a/test/org/tmatesoft/hg/test/TestAuxUtilities.java Thu Aug 08 21:32:22 2013 +0200 +++ b/test/org/tmatesoft/hg/test/TestAuxUtilities.java Wed Aug 14 14:51:51 2013 +0200 @@ -36,8 +36,8 @@ import org.tmatesoft.hg.internal.IntTuple; import org.tmatesoft.hg.internal.IntVector; import org.tmatesoft.hg.internal.PathScope; -import org.tmatesoft.hg.internal.RangePairSeq; import org.tmatesoft.hg.internal.RevisionDescendants; +import org.tmatesoft.hg.internal.diff.RangePairSeq; import org.tmatesoft.hg.repo.HgChangelog; import org.tmatesoft.hg.repo.HgChangelog.RawChangeset; import org.tmatesoft.hg.repo.HgDataFile; diff -r 992fa84e7885 -r 7839ff0bfd78 test/org/tmatesoft/hg/test/TestBlame.java --- a/test/org/tmatesoft/hg/test/TestBlame.java Thu Aug 08 21:32:22 2013 +0200 +++ b/test/org/tmatesoft/hg/test/TestBlame.java Wed Aug 14 14:51:51 2013 +0200 @@ -45,9 +45,9 @@ import org.tmatesoft.hg.core.HgDiffCommand; import org.tmatesoft.hg.core.HgRepoFacade; import org.tmatesoft.hg.core.Nodeid; -import org.tmatesoft.hg.internal.ForwardAnnotateInspector; import org.tmatesoft.hg.internal.IntVector; -import org.tmatesoft.hg.internal.ReverseAnnotateInspector; +import org.tmatesoft.hg.internal.diff.ForwardAnnotateInspector; +import org.tmatesoft.hg.internal.diff.ReverseAnnotateInspector; import org.tmatesoft.hg.repo.HgChangelog; import org.tmatesoft.hg.repo.HgDataFile; import org.tmatesoft.hg.repo.HgLookup; diff -r 992fa84e7885 -r 7839ff0bfd78 test/org/tmatesoft/hg/test/TestDiffHelper.java --- a/test/org/tmatesoft/hg/test/TestDiffHelper.java Thu Aug 08 21:32:22 2013 +0200 +++ b/test/org/tmatesoft/hg/test/TestDiffHelper.java Wed Aug 14 14:51:51 2013 +0200 @@ -17,12 +17,12 @@ package org.tmatesoft.hg.test; import static org.junit.Assert.*; -import static org.tmatesoft.hg.internal.DiffHelper.LineSequence.newlines; +import static org.tmatesoft.hg.internal.diff.DiffHelper.LineSequence.newlines; import org.junit.Test; -import org.tmatesoft.hg.internal.DiffHelper; -import org.tmatesoft.hg.internal.DiffHelper.ChunkSequence; -import org.tmatesoft.hg.internal.DiffHelper.LineSequence; +import org.tmatesoft.hg.internal.diff.DiffHelper; +import org.tmatesoft.hg.internal.diff.DiffHelper.ChunkSequence; +import org.tmatesoft.hg.internal.diff.DiffHelper.LineSequence; import org.tmatesoft.hg.internal.IntVector; /** diff -r 992fa84e7885 -r 7839ff0bfd78 test/org/tmatesoft/hg/test/TestRevlog.java --- a/test/org/tmatesoft/hg/test/TestRevlog.java Thu Aug 08 21:32:22 2013 +0200 +++ b/test/org/tmatesoft/hg/test/TestRevlog.java Wed Aug 14 14:51:51 2013 +0200 @@ -25,10 +25,10 @@ import org.tmatesoft.hg.core.HgRepositoryNotFoundException; import org.tmatesoft.hg.core.Nodeid; import org.tmatesoft.hg.internal.ByteArrayDataAccess; -import org.tmatesoft.hg.internal.DiffHelper; import org.tmatesoft.hg.internal.Patch; -import org.tmatesoft.hg.internal.DiffHelper.LineSequence; import org.tmatesoft.hg.internal.RevlogDump.RevlogReader; +import org.tmatesoft.hg.internal.diff.DiffHelper; +import org.tmatesoft.hg.internal.diff.DiffHelper.LineSequence; import org.tmatesoft.hg.repo.HgLookup; import org.tmatesoft.hg.repo.HgManifest; import org.tmatesoft.hg.repo.HgManifest.Flags;