Mercurial > jhg

comparison src/org/tmatesoft/hg/repo/HgBlameFacility.java @ 556:e55f17a7a195

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
AnnotateFacility renamed to HgBlameFacility and exposed, API shapes out and got some javadoc
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Fri, 22 Feb 2013 20:21:24 +0100
parents src/org/tmatesoft/hg/internal/AnnotateFacility.java@e623aa2ca526
children b9e5ac26dd83
comparison
equal deleted inserted replaced
555:e623aa2ca526 556:e55f17a7a195
1 /*
2 * Copyright (c) 2013 TMate Software Ltd
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation; version 2 of the License.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU General Public License for more details.
12 *
13 * For information on how to redistribute this software under
14 * the terms of a license other than GNU General Public License
15 * contact TMate Software at support@hg4j.com
16 */
17 package org.tmatesoft.hg.repo;
18
19 import static org.tmatesoft.hg.repo.HgRepository.NO_REVISION;
20 import static org.tmatesoft.hg.repo.HgRepository.TIP;
21
22 import java.util.BitSet;
23 import java.util.LinkedList;
24 import java.util.ListIterator;
25
26 import org.tmatesoft.hg.core.HgIterateDirection;
27 import org.tmatesoft.hg.core.Nodeid;
28 import org.tmatesoft.hg.internal.ByteArrayChannel;
29 import org.tmatesoft.hg.internal.Callback;
30 import org.tmatesoft.hg.internal.DiffHelper;
31 import org.tmatesoft.hg.internal.Experimental;
32 import org.tmatesoft.hg.internal.IntMap;
33 import org.tmatesoft.hg.internal.IntVector;
34 import org.tmatesoft.hg.internal.DiffHelper.LineSequence;
35 import org.tmatesoft.hg.internal.DiffHelper.LineSequence.ByteChain;
36 import org.tmatesoft.hg.repo.HgBlameFacility.RevisionDescriptor.Recipient;
37 import org.tmatesoft.hg.util.Adaptable;
38 import org.tmatesoft.hg.util.CancelledException;
39 import org.tmatesoft.hg.util.Pair;
40
41 /**
42 * Facility with diff/annotate functionality.
43 *
44 * @author Artem Tikhomirov
45 * @author TMate Software Ltd.
46 */
47 @Experimental(reason="Unstable API")
48 public final class HgBlameFacility {
49
50 /**
51 * mimic 'hg diff -r clogRevIndex1 -r clogRevIndex2'
52 */
53 public void diff(HgDataFile df, int clogRevIndex1, int clogRevIndex2, BlockInspector insp) {
54 int fileRevIndex1 = fileRevIndex(df, clogRevIndex1);
55 int fileRevIndex2 = fileRevIndex(df, clogRevIndex2);
56 FileLinesCache fileInfoCache = new FileLinesCache(df, 5);
57 LineSequence c1 = fileInfoCache.lines(fileRevIndex1);
58 LineSequence c2 = fileInfoCache.lines(fileRevIndex2);
59 DiffHelper<LineSequence> pg = new DiffHelper<LineSequence>();
60 pg.init(c1, c2);
61 pg.findMatchingBlocks(new BlameBlockInspector(fileRevIndex2, insp, clogRevIndex1, clogRevIndex2));
62 }
63
64 /**
65 * Walk file history up to revision at given changeset and report changes for each revision
66 */
67 public void annotate(HgDataFile df, int changelogRevisionIndex, BlockInspector insp, HgIterateDirection iterateOrder) {
68 if (!df.exists()) {
69 return;
70 }
71 // Note, changelogRevisionIndex may be TIP, while #implAnnotateChange doesn't tolerate constants
72 //
73 // XXX df.indexWalk(0, fileRevIndex, ) might be more effective
74 int fileRevIndex = fileRevIndex(df, changelogRevisionIndex);
75 int[] fileRevParents = new int[2];
76 IntVector fileParentRevs = new IntVector((fileRevIndex+1) * 2, 0);
77 fileParentRevs.add(NO_REVISION, NO_REVISION);
78 for (int i = 1; i <= fileRevIndex; i++) {
79 df.parents(i, fileRevParents, null, null);
80 fileParentRevs.add(fileRevParents[0], fileRevParents[1]);
81 }
82 // collect file revisions to visit, from newest to oldest
83 IntVector fileRevsToVisit = new IntVector(fileRevIndex + 1, 0);
84 LinkedList<Integer> queue = new LinkedList<Integer>();
85 BitSet seen = new BitSet(fileRevIndex + 1);
86 queue.add(fileRevIndex);
87 do {
88 int x = queue.removeFirst();
89 if (seen.get(x)) {
90 continue;
91 }
92 seen.set(x);
93 fileRevsToVisit.add(x);
94 int p1 = fileParentRevs.get(2*x);
95 int p2 = fileParentRevs.get(2*x + 1);
96 if (p1 != NO_REVISION) {
97 queue.addLast(p1);
98 }
99 if (p2 != NO_REVISION) {
100 queue.addLast(p2);
101 }
102 } while (!queue.isEmpty());
103 FileLinesCache fileInfoCache = new FileLinesCache(df, 10);
104 // fileRevsToVisit now { r10, r7, r6, r5, r0 }
105 // and we'll iterate it from behind, e.g. old to new unless reversed
106 if (iterateOrder == HgIterateDirection.NewToOld) {
107 fileRevsToVisit.reverse();
108 }
109 for (int i = fileRevsToVisit.size() - 1; i >= 0; i--) {
110 int fri = fileRevsToVisit.get(i);
111 int clogRevIndex = df.getChangesetRevisionIndex(fri);
112 fileRevParents[0] = fileParentRevs.get(fri * 2);
113 fileRevParents[1] = fileParentRevs.get(fri * 2 + 1);
114 implAnnotateChange(fileInfoCache, clogRevIndex, fri, fileRevParents, insp);
115 }
116 }
117
118 /**
119 * Annotates changes of the file against its parent(s).
120 * Unlike {@link #annotate(HgDataFile, int, BlockInspector, HgIterateDirection)}, doesn't
121 * walk file history, looks at the specified revision only. Handles both parents (if merge revision).
122 */
123 public void annotateSingleRevision(HgDataFile df, int changelogRevisionIndex, BlockInspector insp) {
124 // TODO detect if file is text/binary (e.g. looking for chars < ' ' and not \t\r\n\f
125 int fileRevIndex = fileRevIndex(df, changelogRevisionIndex);
126 int[] fileRevParents = new int[2];
127 df.parents(fileRevIndex, fileRevParents, null, null);
128 if (changelogRevisionIndex == TIP) {
129 changelogRevisionIndex = df.getChangesetRevisionIndex(fileRevIndex);
130 }
131 implAnnotateChange(new FileLinesCache(df, 5), changelogRevisionIndex, fileRevIndex, fileRevParents, insp);
132 }
133
134 private void implAnnotateChange(FileLinesCache fl, int csetRevIndex, int fileRevIndex, int[] fileParentRevs, BlockInspector insp) {
135 final LineSequence fileRevLines = fl.lines(fileRevIndex);
136 if (fileParentRevs[0] != NO_REVISION && fileParentRevs[1] != NO_REVISION) {
137 LineSequence p1Lines = fl.lines(fileParentRevs[0]);
138 LineSequence p2Lines = fl.lines(fileParentRevs[1]);
139 int p1ClogIndex = fl.getChangesetRevisionIndex(fileParentRevs[0]);
140 int p2ClogIndex = fl.getChangesetRevisionIndex(fileParentRevs[1]);
141 DiffHelper<LineSequence> pg = new DiffHelper<LineSequence>();
142 pg.init(p2Lines, fileRevLines);
143 EqualBlocksCollector p2MergeCommon = new EqualBlocksCollector();
144 pg.findMatchingBlocks(p2MergeCommon);
145 //
146 pg.init(p1Lines);
147 BlameBlockInspector bbi = new BlameBlockInspector(fileRevIndex, insp, p1ClogIndex, csetRevIndex);
148 bbi.setMergeParent2(p2MergeCommon, p2ClogIndex);
149 pg.findMatchingBlocks(bbi);
150 } else if (fileParentRevs[0] == fileParentRevs[1]) {
151 // may be equal iff both are unset
152 assert fileParentRevs[0] == NO_REVISION;
153 // everything added
154 BlameBlockInspector bbi = new BlameBlockInspector(fileRevIndex, insp, NO_REVISION, csetRevIndex);
155 bbi.begin(LineSequence.newlines(new byte[0]), fileRevLines);
156 bbi.match(0, fileRevLines.chunkCount()-1, 0);
157 bbi.end();
158 } else {
159 int soleParent = fileParentRevs[0] == NO_REVISION ? fileParentRevs[1] : fileParentRevs[0];
160 assert soleParent != NO_REVISION;
161 LineSequence parentLines = fl.lines(soleParent);
162
163 int parentChangesetRevIndex = fl.getChangesetRevisionIndex(soleParent);
164 DiffHelper<LineSequence> pg = new DiffHelper<LineSequence>();
165 pg.init(parentLines, fileRevLines);
166 pg.findMatchingBlocks(new BlameBlockInspector(fileRevIndex, insp, parentChangesetRevIndex, csetRevIndex));
167 }
168 }
169
170 private static int fileRevIndex(HgDataFile df, int csetRevIndex) {
171 Nodeid fileRev = df.getRepo().getManifest().getFileRevision(csetRevIndex, df.getPath());
172 return df.getRevisionIndex(fileRev);
173 }
174
175 private static class FileLinesCache {
176 private final HgDataFile df;
177 private final LinkedList<Pair<Integer, LineSequence>> lruCache;
178 private final int limit;
179 private IntMap<Integer> fileToClogIndexMap = new IntMap<Integer>(20);
180
181 public FileLinesCache(HgDataFile file, int lruLimit) {
182 df = file;
183 limit = lruLimit;
184 lruCache = new LinkedList<Pair<Integer, LineSequence>>();
185 }
186
187 public int getChangesetRevisionIndex(int fileRevIndex) {
188 Integer cached = fileToClogIndexMap.get(fileRevIndex);
189 if (cached == null) {
190 cached = df.getChangesetRevisionIndex(fileRevIndex);
191 fileToClogIndexMap.put(fileRevIndex, cached);
192 }
193 return cached.intValue();
194 }
195
196 public LineSequence lines(int fileRevIndex) {
197 Pair<Integer, LineSequence> cached = checkCache(fileRevIndex);
198 if (cached != null) {
199 return cached.second();
200 }
201 try {
202 ByteArrayChannel c;
203 df.content(fileRevIndex, c = new ByteArrayChannel());
204 LineSequence rv = LineSequence.newlines(c.toArray());
205 lruCache.addFirst(new Pair<Integer, LineSequence>(fileRevIndex, rv));
206 if (lruCache.size() > limit) {
207 lruCache.removeLast();
208 }
209 return rv;
210 } catch (CancelledException ex) {
211 // TODO likely it was bad idea to throw cancelled exception from content()
212 // deprecate and provide alternative?
213 HgInvalidStateException ise = new HgInvalidStateException("ByteArrayChannel never throws CancelledException");
214 ise.initCause(ex);
215 throw ise;
216 }
217 }
218
219 private Pair<Integer,LineSequence> checkCache(int fileRevIndex) {
220 Pair<Integer, LineSequence> rv = null;
221 for (ListIterator<Pair<Integer, LineSequence>> it = lruCache.listIterator(); it.hasNext(); ) {
222 Pair<Integer, LineSequence> p = it.next();
223 if (p.first() == fileRevIndex) {
224 rv = p;
225 it.remove();
226 break;
227 }
228 }
229 if (rv != null) {
230 lruCache.addFirst(rv);
231 }
232 return rv;
233 }
234 }
235
236 /**
237 * Client's sink for revision differences.
238 *
239 * When implemented, clients shall not expect new {@link Block blocks} instances in each call.
240 *
241 * In case more information about annotated revision is needed, inspector instances may supply
242 * {@link RevisionDescriptor.Recipient} through {@link Adaptable}.
243 */
244 @Callback
245 public interface BlockInspector {
246 void same(EqualBlock block);
247 void added(AddBlock block);
248 void changed(ChangeBlock block);
249 void deleted(DeleteBlock block);
250 }
251
252 /**
253 * Represents content of a block, either as a sequence of bytes or a
254 * sequence of smaller blocks (lines), if appropriate (according to usage context).
255 *
256 * This approach allows line-by-line access to content data along with complete byte sequence for the whole block, i.e.
257 * <pre>
258 * BlockData bd = addBlock.addedLines()
259 * // bd describes data from the addition completely.
260 * // elements of the BlockData are lines
261 * bd.elementCount() == addBlock.totalAddedLines();
262 * // one cat obtain complete addition with
263 * byte[] everythingAdded = bd.asArray();
264 * // or iterate line by line
265 * for (int i = 0; i < bd.elementCount(); i++) {
266 * byte[] lineContent = bd.elementAt(i);
267 * String line = new String(lineContent, fileEncodingCharset);
268 * }
269 * where bd.elementAt(0) is the line at index addBlock.firstAddedLine()
270 * </pre>
271 *
272 * LineData or ChunkData?
273 */
274 public interface BlockData {
275 BlockData elementAt(int index);
276 int elementCount();
277 byte[] asArray();
278 }
279
280 /**
281 * {@link BlockInspector} may optionally request extra information about revisions
282 * being inspected, denoting itself as a {@link RevisionDescriptor.Recipient}. This class
283 * provides complete information about file revision under annotation now.
284 */
285 public interface RevisionDescriptor {
286 /**
287 * @return complete source of the diff origin, never <code>null</code>
288 */
289 BlockData origin();
290 /**
291 * @return complete source of the diff target, never <code>null</code>
292 */
293 BlockData target();
294 /**
295 * @return changeset revision index of original file, or {@link HgRepository#NO_REVISION} if it's the very first revision
296 */
297 int originChangesetIndex();
298 /**
299 * @return changeset revision index of the target file
300 */
301 int targetChangesetIndex();
302 /**
303 * @return <code>true</code> if this revision is merge
304 */
305 boolean isMerge();
306 /**
307 * @return changeset revision index of the second, merged parent
308 */
309 int mergeChangesetIndex();
310 /**
311 * @return revision index of the change in target file's revlog
312 */
313 int fileRevisionIndex();
314
315 /**
316 * Implement to indicate interest in {@link RevisionDescriptor}.
317 *
318 * Note, instance of {@link RevisionDescriptor} is the same for
319 * {@link #start(RevisionDescriptor)} and {@link #done(RevisionDescriptor)}
320 * methods, and not necessarily a new one (i.e. <code>==</code>) for the next
321 * revision announced.
322 */
323 @Callback
324 public interface Recipient {
325 /**
326 * Comes prior to any change {@link Block blocks}
327 */
328 void start(RevisionDescriptor revisionDescription);
329 /**
330 * Comes after all change {@link Block blocks} were dispatched
331 */
332 void done(RevisionDescriptor revisionDescription);
333 }
334 }
335
336 /**
337 * Each change block comes from a single origin, blocks that are result of a merge
338 * have {@link #originChangesetIndex()} equal to {@link RevisionDescriptor#mergeChangesetIndex()}.
339 */
340 public interface Block {
341 int originChangesetIndex();
342 int targetChangesetIndex();
343 }
344
345 public interface EqualBlock extends Block {
346 int originStart();
347 int targetStart();
348 int length();
349 BlockData content();
350 }
351
352 public interface AddBlock extends Block {
353 /**
354 * @return line index in the origin where this block is inserted
355 */
356 int insertedAt();
357 /**
358 * @return line index of the first added line in the target revision
359 */
360 int firstAddedLine();
361 /**
362 * @return number of added lines in this block
363 */
364 int totalAddedLines();
365 /**
366 * @return content of added lines
367 */
368 BlockData addedLines();
369 }
370 public interface DeleteBlock extends Block {
371 /**
372 * @return line index in the target revision were this deleted block would be
373 */
374 int removedAt();
375 /**
376 * @return line index of the first removed line in the original revision
377 */
378 int firstRemovedLine();
379 /**
380 * @return number of deleted lines in this block
381 */
382 int totalRemovedLines();
383 /**
384 * @return content of deleted lines
385 */
386 BlockData removedLines();
387 }
388 public interface ChangeBlock extends AddBlock, DeleteBlock {
389 }
390
391 private static class BlameBlockInspector extends DiffHelper.DeltaInspector<LineSequence> {
392 private final BlockInspector insp;
393 private final int csetOrigin;
394 private final int csetTarget;
395 private EqualBlocksCollector p2MergeCommon;
396 private int csetMergeParent;
397 private IntVector mergeRanges;
398 private final AnnotateRev annotatedRevision;
399
400 public BlameBlockInspector(int fileRevIndex, BlockInspector inspector, int originCset, int targetCset) {
401 assert inspector != null;
402 insp = inspector;
403 annotatedRevision = new AnnotateRev();
404 annotatedRevision.set(fileRevIndex);
405 csetOrigin = originCset;
406 csetTarget = targetCset;
407 }
408
409 public void setMergeParent2(EqualBlocksCollector p2Merge, int parentCset2) {
410 p2MergeCommon = p2Merge;
411 csetMergeParent = parentCset2;
412 mergeRanges = new IntVector(3*10, 3*10);
413 }
414
415 @Override
416 public void begin(LineSequence s1, LineSequence s2) {
417 super.begin(s1, s2);
418 ContentBlock originContent = new ContentBlock(s1);
419 ContentBlock targetContent = new ContentBlock(s2);
420 annotatedRevision.set(originContent, targetContent);
421 annotatedRevision.set(csetOrigin, csetTarget, p2MergeCommon != null ? csetMergeParent : NO_REVISION);
422 Recipient curious = Adaptable.Factory.getAdapter(insp, Recipient.class, null);
423 if (curious != null) {
424 curious.start(annotatedRevision);
425 }
426 }
427
428 @Override
429 public void end() {
430 super.end();
431 Recipient curious = Adaptable.Factory.getAdapter(insp, Recipient.class, null);
432 if (curious != null) {
433 curious.done(annotatedRevision);
434 }
435 p2MergeCommon = null;
436 }
437
438 @Override
439 protected void changed(int s1From, int s1To, int s2From, int s2To) {
440 if (p2MergeCommon != null) {
441 mergeRanges.clear();
442 p2MergeCommon.combineAndMarkRangesWithTarget(s2From, s2To - s2From, csetOrigin, csetMergeParent, mergeRanges);
443
444 /*
445 * Usecases:
446 * 3 lines changed to 10 lines. range of 10 lines breaks down to 2 from p2, 3 from p1, and 5 from p2.
447 * We report: 2 lines changed to 2(p2), then 1 line changed with 3(p1) and 5 lines added from p2.
448 *
449 * 10 lines changed to 3 lines, range of 3 lines breaks down to 2 line from p1 and 1 line from p2.
450 * We report: 2 lines changed to 2(p1) and 8 lines changed to 1(p2)
451 */
452 int s1TotalLines = s1To - s1From, s1ConsumedLines = 0, s1Start = s1From;
453
454 for (int i = 0; i < mergeRanges.size(); i += 3) {
455 final int rangeOrigin = mergeRanges.get(i);
456 final int rangeStart = mergeRanges.get(i+1);
457 final int rangeLen = mergeRanges.get(i+2);
458 final boolean lastRange = i+3 >= mergeRanges.size();
459 final int s1LinesLeft = s1TotalLines - s1ConsumedLines;
460 // how many lines we may reported as changed (don't use more than in range unless it's the very last range)
461 final int s1LinesToBorrow = lastRange ? s1LinesLeft : Math.min(s1LinesLeft, rangeLen);
462 if (s1LinesToBorrow > 0) {
463 ChangeBlockImpl block = getChangeBlock(s1Start, s1LinesToBorrow, rangeStart, rangeLen);
464 block.setOriginAndTarget(rangeOrigin, csetTarget);
465 insp.changed(block);
466 s1ConsumedLines += s1LinesToBorrow;
467 s1Start += s1LinesToBorrow;
468 } else {
469 ChangeBlockImpl block = getAddBlock(rangeStart, rangeLen, s1Start);
470 block.setOriginAndTarget(rangeOrigin, csetTarget);
471 insp.added(block);
472 }
473 }
474 if (s1ConsumedLines != s1TotalLines) {
475 throw new HgInvalidStateException(String.format("Expected to process %d lines, but actually was %d", s1TotalLines, s1ConsumedLines));
476 }
477 } else {
478 ChangeBlockImpl block = getChangeBlock(s1From, s1To - s1From, s2From, s2To - s2From);
479 block.setOriginAndTarget(csetOrigin, csetTarget);
480 insp.changed(block);
481 }
482 }
483
484 @Override
485 protected void added(int s1InsertPoint, int s2From, int s2To) {
486 if (p2MergeCommon != null) {
487 mergeRanges.clear();
488 p2MergeCommon.combineAndMarkRangesWithTarget(s2From, s2To - s2From, csetOrigin, csetMergeParent, mergeRanges);
489 int insPoint = s1InsertPoint; // track changes to insertion point
490 for (int i = 0; i < mergeRanges.size(); i += 3) {
491 int rangeOrigin = mergeRanges.get(i);
492 int rangeStart = mergeRanges.get(i+1);
493 int rangeLen = mergeRanges.get(i+2);
494 ChangeBlockImpl block = getAddBlock(rangeStart, rangeLen, insPoint);
495 block.setOriginAndTarget(rangeOrigin, csetTarget);
496 insp.added(block);
497 // indicate insPoint moved down number of lines we just reported
498 insPoint += rangeLen;
499 }
500 } else {
501 ChangeBlockImpl block = getAddBlock(s2From, s2To - s2From, s1InsertPoint);
502 block.setOriginAndTarget(csetOrigin, csetTarget);
503 insp.added(block);
504 }
505 }
506
507 @Override
508 protected void deleted(int s2DeletePoint, int s1From, int s1To) {
509 ChangeBlockImpl block = new ChangeBlockImpl(annotatedRevision.origin, null, s1From, s1To - s1From, -1, -1, -1, s2DeletePoint);
510 block.setOriginAndTarget(csetOrigin, csetTarget);
511 insp.deleted(block);
512 }
513
514 @Override
515 protected void unchanged(int s1From, int s2From, int length) {
516 EqualBlockImpl block = new EqualBlockImpl(s1From, s2From, length, annotatedRevision.target);
517 block.setOriginAndTarget(csetOrigin, csetTarget);
518 insp.same(block);
519 }
520
521 private ChangeBlockImpl getAddBlock(int start, int len, int insPoint) {
522 return new ChangeBlockImpl(null, annotatedRevision.target, -1, -1, start, len, insPoint, -1);
523 }
524
525 private ChangeBlockImpl getChangeBlock(int start1, int len1, int start2, int len2) {
526 return new ChangeBlockImpl(annotatedRevision.origin, annotatedRevision.target, start1, len1, start2, len2, start1, start2);
527 }
528 }
529
530 private static class BlockImpl implements Block {
531 private int originCset;
532 private int targetCset;
533
534 void setOriginAndTarget(int originChangesetIndex, int targetChangesetIndex) {
535 // XXX perhaps, shall be part of Inspector API, rather than Block's
536 // as they don't change between blocks (although the moment about merged revisions)
537 // is not yet clear to me
538 originCset = originChangesetIndex;
539 targetCset = targetChangesetIndex;
540 }
541
542 public int originChangesetIndex() {
543 return originCset;
544 }
545
546 public int targetChangesetIndex() {
547 return targetCset;
548 }
549 }
550
551 private static class EqualBlockImpl extends BlockImpl implements EqualBlock {
552 private final int start1, start2;
553 private final int length;
554 private final ContentBlock fullContent;
555 private FilterBlock myContent;
556
557 EqualBlockImpl(int blockStartSeq1, int blockStartSeq2, int blockLength, ContentBlock targetContent) {
558 start1 = blockStartSeq1;
559 start2 = blockStartSeq2;
560 length = blockLength;
561 fullContent = targetContent;
562 }
563
564 public int originStart() {
565 return start1;
566 }
567
568 public int targetStart() {
569 return start2;
570 }
571
572 public int length() {
573 return length;
574 }
575
576 public BlockData content() {
577 if (myContent == null) {
578 myContent = new FilterBlock(fullContent, start2, length);
579 }
580 return myContent;
581 }
582
583 @Override
584 public String toString() {
585 return String.format("@@ [%d..%d) == [%d..%d) @@", start1, start1+length, start2, start2+length);
586 }
587 }
588
589 private static class ChangeBlockImpl extends BlockImpl implements ChangeBlock {
590 private final ContentBlock oldContent;
591 private final ContentBlock newContent;
592 private final int s1Start;
593 private final int s1Len;
594 private final int s2Start;
595 private final int s2Len;
596 private final int s1InsertPoint;
597 private final int s2DeletePoint;
598 private FilterBlock addedBlock, removedBlock;
599
600 public ChangeBlockImpl(ContentBlock c1, ContentBlock c2, int s1Start, int s1Len, int s2Start, int s2Len, int s1InsertPoint, int s2DeletePoint) {
601 oldContent = c1;
602 newContent = c2;
603 this.s1Start = s1Start;
604 this.s1Len = s1Len;
605 this.s2Start = s2Start;
606 this.s2Len = s2Len;
607 this.s1InsertPoint = s1InsertPoint;
608 this.s2DeletePoint = s2DeletePoint;
609 }
610
611 public int insertedAt() {
612 return s1InsertPoint;
613 }
614
615 public int firstAddedLine() {
616 return s2Start;
617 }
618
619 public int totalAddedLines() {
620 return s2Len;
621 }
622
623 public BlockData addedLines() {
624 if (addedBlock == null) {
625 addedBlock = new FilterBlock(newContent, firstAddedLine(), totalAddedLines());
626 }
627 return addedBlock;
628 }
629
630 public int removedAt() {
631 return s2DeletePoint;
632 }
633
634 public int firstRemovedLine() {
635 return s1Start;
636 }
637
638 public int totalRemovedLines() {
639 return s1Len;
640 }
641
642 public BlockData removedLines() {
643 if (removedBlock == null) {
644 removedBlock = new FilterBlock(oldContent, firstRemovedLine(), totalRemovedLines());
645 }
646 return removedBlock;
647 }
648
649 @Override
650 public String toString() {
651 if (s2DeletePoint == -1) {
652 return String.format("@@ -%d,0 +%d,%d @@", insertedAt(), firstAddedLine(), totalAddedLines());
653 } else if (s1InsertPoint == -1) {
654 // delete only
655 return String.format("@@ -%d,%d +%d,0 @@", firstRemovedLine(), totalRemovedLines(), removedAt());
656 }
657 return String.format("@@ -%d,%d +%d,%d @@", firstRemovedLine(), totalRemovedLines(), firstAddedLine(), totalAddedLines());
658 }
659 }
660
661 private static class SingleLine implements BlockData {
662 private final ByteChain line;
663
664 public SingleLine(ByteChain lineContent) {
665 line = lineContent;
666 }
667
668 public BlockData elementAt(int index) {
669 assert false;
670 return null;
671 }
672
673 public int elementCount() {
674 return 0;
675 }
676
677 public byte[] asArray() {
678 return line.data();
679 }
680 }
681
682 private static class ContentBlock implements BlockData {
683 private final LineSequence seq;
684
685 public ContentBlock(LineSequence sequence) {
686 seq = sequence;
687 }
688
689 public BlockData elementAt(int index) {
690 return new SingleLine(seq.chunk(index));
691 }
692
693 public int elementCount() {
694 return seq.chunkCount() - 1;
695 }
696
697 public byte[] asArray() {
698 return seq.data(0, seq.chunkCount() - 1);
699 }
700 }
701
702 private static class FilterBlock implements BlockData {
703 private final ContentBlock contentBlock;
704 private final int from;
705 private final int length;
706
707 public FilterBlock(ContentBlock bd, int startFrom, int len) {
708 assert bd != null;
709 assert startFrom + len < bd.seq.chunkCount(); // there's one extra chunk in the end, so strict less is ok
710 contentBlock = bd;
711 from = startFrom;
712 length = len;
713 }
714
715 public BlockData elementAt(int index) {
716 if (index < 0 || index >= length) {
717 throw new IllegalArgumentException(String.format("Expected value from [0..%d), got %d", length, index));
718 }
719 return contentBlock.elementAt(from + index);
720 }
721
722 public int elementCount() {
723 return length;
724 }
725
726 public byte[] asArray() {
727 return contentBlock.seq.data(from, from + length);
728 }
729 }
730
731
732 static class EqualBlocksCollector implements DiffHelper.MatchInspector<LineSequence> {
733 private final IntVector matches = new IntVector(10*3, 2*3);
734
735 public void begin(LineSequence s1, LineSequence s2) {
736 }
737
738 public void match(int startSeq1, int startSeq2, int matchLength) {
739 matches.add(startSeq1);
740 matches.add(startSeq2);
741 matches.add(matchLength);
742 }
743
744 public void end() {
745 }
746
747 // true when specified line in origin is equal to a line in target
748 public boolean includesOriginLine(int ln) {
749 return includes(ln, 0);
750 }
751
752 // true when specified line in target is equal to a line in origin
753 public boolean includesTargetLine(int ln) {
754 return includes(ln, 1);
755 }
756
757 public void intersectWithTarget(int start, int length, IntVector result) {
758 int s = start;
759 for (int l = start, x = start + length; l < x; l++) {
760 if (!includesTargetLine(l)) {
761 if (l - s > 0) {
762 result.add(s);
763 result.add(l - s);
764 }
765 s = l+1;
766 }
767 }
768 if (s < start+length) {
769 result.add(s);
770 result.add((start + length) - s);
771 }
772 }
773
774 /*
775 * intersects [start..start+length) with ranges of target lines, and based on the intersection
776 * breaks initial range into smaller ranges and records them into result, with marker to indicate
777 * whether the range is from initial range (markerSource) or is a result of the intersection with target
778 * (markerTarget)
779 */
780 public void combineAndMarkRangesWithTarget(int start, int length, int markerSource, int markerTarget, IntVector result) {
781 int sourceStart = start, targetStart = start, sourceEnd = start + length;
782 for (int l = sourceStart; l < sourceEnd; l++) {
783 if (includesTargetLine(l)) {
784 // l is from target
785 if (sourceStart < l) {
786 // few lines from source range were not in the target, report them
787 result.add(markerSource);
788 result.add(sourceStart);
789 result.add(l - sourceStart);
790 }
791 // indicate the earliest line from source range to use
792 sourceStart = l + 1;
793 } else {
794 // l is not in target
795 if (targetStart < l) {
796 // report lines from target range
797 result.add(markerTarget);
798 result.add(targetStart);
799 result.add(l - targetStart);
800 }
801 // next line *may* be from target
802 targetStart = l + 1;
803 }
804 }
805 // if source range end with line from target, sourceStart would be == sourceEnd, and we need to add range with markerTarget
806 // if source range doesn't end with target line, targetStart == sourceEnd, while sourceStart < sourceEnd
807 if (sourceStart < sourceEnd) {
808 assert targetStart == sourceEnd;
809 // something left from the source range
810 result.add(markerSource);
811 result.add(sourceStart);
812 result.add(sourceEnd - sourceStart);
813 } else if (targetStart < sourceEnd) {
814 assert sourceStart == sourceEnd;
815 result.add(markerTarget);
816 result.add(targetStart);
817 result.add(sourceEnd - targetStart);
818 }
819 }
820
821 private boolean includes(int ln, int o) {
822 for (int i = 2; i < matches.size(); o += 3, i+=3) {
823 int rangeStart = matches.get(o);
824 if (rangeStart > ln) {
825 return false;
826 }
827 int rangeLen = matches.get(i);
828 if (rangeStart + rangeLen > ln) {
829 return true;
830 }
831 }
832 return false;
833 }
834 }
835
836 private static class AnnotateRev implements RevisionDescriptor {
837 public ContentBlock origin, target;
838 public int originCset, targetCset, mergeCset, fileRevIndex;
839
840 public void set(int fileRev) {
841 fileRevIndex = fileRev;
842 }
843 public void set(ContentBlock o, ContentBlock t) {
844 origin = o;
845 target = t;
846 }
847 public void set(int o, int t, int m) {
848 originCset = o;
849 targetCset = t;
850 mergeCset = m;
851 }
852
853 public BlockData origin() {
854 return origin;
855 }
856
857 public BlockData target() {
858 return target;
859 }
860
861 public int originChangesetIndex() {
862 return originCset;
863 }
864
865 public int targetChangesetIndex() {
866 return targetCset;
867 }
868
869 public boolean isMerge() {
870 return mergeCset != NO_REVISION;
871 }
872
873 public int mergeChangesetIndex() {
874 return mergeCset;
875 }
876
877 public int fileRevisionIndex() {
878 return fileRevIndex;
879 }
880 }
881
882 public static void main(String[] args) {
883 EqualBlocksCollector bc = new EqualBlocksCollector();
884 bc.match(-1, 5, 3);
885 bc.match(-1, 10, 2);
886 bc.match(-1, 15, 3);
887 bc.match(-1, 20, 3);
888 assert !bc.includesTargetLine(4);
889 assert bc.includesTargetLine(7);
890 assert !bc.includesTargetLine(8);
891 assert bc.includesTargetLine(10);
892 assert !bc.includesTargetLine(12);
893 IntVector r = new IntVector();
894 bc.intersectWithTarget(7, 10, r);
895 for (int i = 0; i < r.size(); i+=2) {
896 System.out.printf("[%d..%d) ", r.get(i), r.get(i) + r.get(i+1));
897 }
898 System.out.println();
899 r.clear();
900 bc.combineAndMarkRangesWithTarget(0, 16, 508, 514, r);
901 for (int i = 0; i < r.size(); i+=3) {
902 System.out.printf("%d:[%d..%d) ", r.get(i), r.get(i+1), r.get(i+1) + r.get(i+2));
903 }
904 }
905 }