Mercurial > jhg

annotate src/org/tmatesoft/hg/internal/PatchGenerator.java @ 549:83afa680555d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Annotate merge revision (combined diff against two parents without looking further)
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Tue, 19 Feb 2013 21:17:39 +0100
parents 15b406c7cd9d
children
rev   line source
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
1 /*
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
2 * Copyright (c) 2013 TMate Software Ltd
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
3 *
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
4 * This program is free software; you can redistribute it and/or modify
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
5 * it under the terms of the GNU General Public License as published by
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
6 * the Free Software Foundation; version 2 of the License.
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
7 *
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
8 * This program is distributed in the hope that it will be useful,
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
11 * GNU General Public License for more details.
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
12 *
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
13 * For information on how to redistribute this software under
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
14 * the terms of a license other than GNU General Public License
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
15 * contact TMate Software at support@hg4j.com
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
16 */
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
17 package org.tmatesoft.hg.internal;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
18
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
19 import java.util.ArrayList;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
20 import java.util.HashMap;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
21 import java.util.Map;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
22
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
23 import org.tmatesoft.hg.repo.HgDataFile;
549
83afa680555d Annotate merge revision (combined diff against two parents without looking further)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 545
diff changeset
24 import org.tmatesoft.hg.repo.HgInvalidStateException;
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
25 import org.tmatesoft.hg.repo.HgLookup;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
26 import org.tmatesoft.hg.repo.HgRepository;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
27
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
28 /**
538
dd4f6311af52 Commit: first working version
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 533
diff changeset
29 * Mercurial cares about changes only up to the line level, e.g. a simple file version dump in manifest looks like (RevlogDump output):
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
30 *
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
31 * 522: 233748 0 103 17438 433 522 521 -1 756073cf2321df44d3ed0585f2a5754bc8a1b2f6
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
32 * <PATCH>:
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
33 * 3487..3578, 91:src/org/tmatesoft/hg/core/HgIterateDirection.java\00add61a8a665c5d8f092210767f812fe0d335ac8
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
34 *
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
35 * I.e. for the {fname}{revision} entry format of manifest, not only {revision} is changed, but the whole line, with unchanged {fname} is recorded
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
36 * in the patch.
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
37 *
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
38 * Mercurial paper describes reasons for choosing this approach to delta generation, too.
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
39 *
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
40 *
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
41 * @author Artem Tikhomirov
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
42 * @author TMate Software Ltd.
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
43 */
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
44 public class PatchGenerator<T extends PatchGenerator.ChunkSequence<?>> {
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
45
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
46 private Map<Chunk, IntVector> chunk2UseIndex;
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
47 private T seq1, seq2;
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
48
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
49 // get filled by #longestMatch, track start of common sequence in seq1 and seq2, respectively
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
50 private int matchStartS1, matchStartS2;
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
51
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
52 private MatchInspector<T> matchInspector;
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
53
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
54 public void init(T s1, T s2) {
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
55 seq1 = s1;
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
56 seq2 = s2;
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
57 prepare(s2);
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
58 }
549
83afa680555d Annotate merge revision (combined diff against two parents without looking further)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 545
diff changeset
59
83afa680555d Annotate merge revision (combined diff against two parents without looking further)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 545
diff changeset
60 public void init(T s1) {
83afa680555d Annotate merge revision (combined diff against two parents without looking further)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 545
diff changeset
61 if (seq2 == null) {
83afa680555d Annotate merge revision (combined diff against two parents without looking further)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 545
diff changeset
62 throw new IllegalStateException("Use this #init() only when target sequence shall be matched against different origin");
83afa680555d Annotate merge revision (combined diff against two parents without looking further)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 545
diff changeset
63 }
83afa680555d Annotate merge revision (combined diff against two parents without looking further)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 545
diff changeset
64 seq1 = s1;
83afa680555d Annotate merge revision (combined diff against two parents without looking further)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 545
diff changeset
65 }
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
66
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
67
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
68 private void prepare(T s2) {
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
69 chunk2UseIndex = new HashMap<Chunk, IntVector>();
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
70 for (int i = 0, len = s2.chunkCount(); i < len; i++) {
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
71 Chunk bc = s2.chunk(i);
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
72 IntVector loc = chunk2UseIndex.get(bc);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
73 if (loc == null) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
74 chunk2UseIndex.put(bc, loc = new IntVector());
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
75 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
76 loc.add(i);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
77 // bc.registerUseIn(i) - BEWARE, use of bc here is incorrect
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
78 // in this case need to find the only ByteChain to keep indexes
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
79 // i.e. when there are few equal ByteChain instances, notion of "usedIn" shall be either shared (reference same vector)
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
80 // or kept within only one of them
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
81 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
82 // for (ChunkSequence.ByteChain bc : chunk2UseIndex.keySet()) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
83 // System.out.printf("%s: {", new String(bc.data()));
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
84 // for (int x : chunk2UseIndex.get(bc).toArray()) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
85 // System.out.printf(" %d,", x);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
86 // }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
87 // System.out.println("}");
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
88 // }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
89 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
90
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
91 public void findMatchingBlocks(MatchInspector<T> insp) {
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
92 insp.begin(seq1, seq2);
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
93 matchInspector = insp;
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
94 findMatchingBlocks(0, seq1.chunkCount(), 0, seq2.chunkCount());
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
95 insp.end();
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
96 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
97
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
98 /**
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
99 * implementation based on Python's difflib.py and SequenceMatcher
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
100 */
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
101 public int longestMatch(int startS1, int endS1, int startS2, int endS2) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
102 matchStartS1 = matchStartS2 = 0;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
103 int maxLength = 0;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
104 IntMap<Integer> chunkIndex2MatchCount = new IntMap<Integer>(8);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
105 for (int i = startS1; i < endS1; i++) {
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
106 Chunk bc = seq1.chunk(i);
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
107 IntMap<Integer> newChunkIndex2MatchCount = new IntMap<Integer>(8);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
108 IntVector occurencesInS2 = chunk2UseIndex.get(bc);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
109 if (occurencesInS2 == null) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
110 // chunkIndex2MatchCount.clear(); // TODO need clear instead of new instance
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
111 chunkIndex2MatchCount = newChunkIndex2MatchCount;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
112 continue;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
113 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
114 for (int j : occurencesInS2.toArray()) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
115 // s1[i] == s2[j]
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
116 if (j < startS2) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
117 continue;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
118 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
119 if (j >= endS2) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
120 break;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
121 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
122 int prevChunkMatches = chunkIndex2MatchCount.containsKey(j-1) ? chunkIndex2MatchCount.get(j-1) : 0;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
123 int k = prevChunkMatches + 1;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
124 newChunkIndex2MatchCount.put(j, k);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
125 if (k > maxLength) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
126 matchStartS1 = i-k+1;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
127 matchStartS2 = j-k+1;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
128 maxLength = k;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
129 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
130 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
131 chunkIndex2MatchCount = newChunkIndex2MatchCount;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
132 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
133 return maxLength;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
134 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
135
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
136 private void findMatchingBlocks(int startS1, int endS1, int startS2, int endS2) {
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
137 int matchLength = longestMatch(startS1, endS1, startS2, endS2);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
138 if (matchLength > 0) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
139 final int saveStartS1 = matchStartS1, saveStartS2 = matchStartS2;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
140 if (startS1 < matchStartS1 && startS2 < matchStartS2) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
141 findMatchingBlocks(startS1, matchStartS1, startS2, matchStartS2);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
142 }
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
143 matchInspector.match(saveStartS1, saveStartS2, matchLength);
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
144 if (saveStartS1+matchLength < endS1 && saveStartS2+matchLength < endS2) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
145 findMatchingBlocks(saveStartS1 + matchLength, endS1, saveStartS2 + matchLength, endS2);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
146 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
147 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
148 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
149
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
150 interface MatchInspector<T extends ChunkSequence<?>> {
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
151 void begin(T s1, T s2);
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
152 void match(int startSeq1, int startSeq2, int matchLength);
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
153 void end();
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
154 }
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
155
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
156 static class MatchDumpInspector<T extends ChunkSequence<?>> implements MatchInspector<T> {
545
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
157 private int matchCount;
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
158
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
159 public void begin(T s1, T s2) {
545
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
160 matchCount = 0;
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
161 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
162
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
163 public void match(int startSeq1, int startSeq2, int matchLength) {
545
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
164 matchCount++;
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
165 System.out.printf("match #%d: from line #%d and line #%d of length %d\n", matchCount, startSeq1, startSeq2, matchLength);
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
166 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
167
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
168 public void end() {
545
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
169 if (matchCount == 0) {
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
170 System.out.println("NO MATCHES FOUND!");
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
171 }
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
172 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
173 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
174
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
175 static class DeltaInspector<T extends ChunkSequence<?>> implements MatchInspector<T> {
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
176 protected int changeStartS1, changeStartS2;
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
177 protected T seq1, seq2;
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
178
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
179 public void begin(T s1, T s2) {
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
180 seq1 = s1;
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
181 seq2 = s2;
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
182 changeStartS1 = changeStartS2 = 0;
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
183 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
184
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
185 public void match(int startSeq1, int startSeq2, int matchLength) {
542
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
186 reportDeltaElement(startSeq1, startSeq2, matchLength);
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
187 changeStartS1 = startSeq1 + matchLength;
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
188 changeStartS2 = startSeq2 + matchLength;
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
189 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
190
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
191 public void end() {
545
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
192 if (changeStartS1 < seq1.chunkCount()-1 || changeStartS2 < seq2.chunkCount()-1) {
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
193 reportDeltaElement(seq1.chunkCount()-1, seq2.chunkCount()-1, 0);
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
194 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
195 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
196
542
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
197 protected void reportDeltaElement(int matchStartSeq1, int matchStartSeq2, int matchLength) {
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
198 if (changeStartS1 < matchStartSeq1) {
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
199 if (changeStartS2 < matchStartSeq2) {
542
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
200 changed(changeStartS1, matchStartSeq1, changeStartS2, matchStartSeq2);
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
201 } else {
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
202 assert changeStartS2 == matchStartSeq2;
543
1e95f48d9886 Report line index for insertion and deletion, test against 'hg diff' output
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 542
diff changeset
203 deleted(matchStartSeq2, changeStartS1, matchStartSeq1);
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
204 }
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
205 } else {
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
206 assert changeStartS1 == matchStartSeq1;
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
207 if(changeStartS2 < matchStartSeq2) {
545
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
208 added(changeStartS1, changeStartS2, matchStartSeq2);
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
209 } else {
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
210 assert changeStartS2 == matchStartSeq2;
549
83afa680555d Annotate merge revision (combined diff against two parents without looking further)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 545
diff changeset
211 if (matchStartSeq1 > 0 || matchStartSeq2 > 0) {
83afa680555d Annotate merge revision (combined diff against two parents without looking further)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 545
diff changeset
212 // FIXME perhaps, exception is too much for the case
83afa680555d Annotate merge revision (combined diff against two parents without looking further)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 545
diff changeset
213 // once diff is covered with tests, replace with assert false : msg;
83afa680555d Annotate merge revision (combined diff against two parents without looking further)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 545
diff changeset
214 throw new HgInvalidStateException(String.format("adjustent equal blocks %d, %d and %d,%d", changeStartS1, matchStartSeq1, changeStartS2, matchStartSeq2));
83afa680555d Annotate merge revision (combined diff against two parents without looking further)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 545
diff changeset
215 }
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
216 }
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
217 }
542
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
218 if (matchLength > 0) {
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
219 unchanged(matchStartSeq1, matchStartSeq2, matchLength);
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
220 }
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
221 }
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
222
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
223 /**
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
224 * [s1From..s1To) replaced with [s2From..s2To)
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
225 */
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
226 protected void changed(int s1From, int s1To, int s2From, int s2To) {
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
227 // NO-OP
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
228 }
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
229
543
1e95f48d9886 Report line index for insertion and deletion, test against 'hg diff' output
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 542
diff changeset
230 protected void deleted(int s2DeletePoint, int s1From, int s1To) {
542
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
231 // NO-OP
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
232 }
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
233
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
234 protected void added(int s1InsertPoint, int s2From, int s2To) {
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
235 // NO-OP
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
236 }
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
237
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
238 protected void unchanged(int s1From, int s2From, int length) {
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
239 // NO-OP
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
240 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
241 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
242
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
243 static class DeltaDumpInspector<T extends ChunkSequence<?>> extends DeltaInspector<T> {
542
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
244
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
245 @Override
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
246 protected void changed(int s1From, int s1To, int s2From, int s2To) {
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
247 System.out.printf("changed [%d..%d) with [%d..%d)\n", s1From, s1To, s2From, s2To);
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
248 }
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
249
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
250 @Override
543
1e95f48d9886 Report line index for insertion and deletion, test against 'hg diff' output
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 542
diff changeset
251 protected void deleted(int s2DeletionPoint, int s1From, int s1To) {
542
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
252 System.out.printf("deleted [%d..%d)\n", s1From, s1To);
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
253 }
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
254
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
255 @Override
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
256 protected void added(int s1InsertPoint, int s2From, int s2To) {
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
257 System.out.printf("added [%d..%d) at %d\n", s2From, s2To, s1InsertPoint);
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
258 }
545
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
259
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
260 @Override
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
261 protected void unchanged(int s1From, int s2From, int length) {
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
262 System.out.printf("same [%d..%d) and [%d..%d)\n", s1From, s1From + length, s2From, s2From + length);
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
263 }
542
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
264 }
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
265
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
266 public static void main(String[] args) throws Exception {
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
267 PatchGenerator<LineSequence> pg1 = new PatchGenerator<LineSequence>();
545
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
268 // pg1.init(LineSequence.newlines("hello\nabc".getBytes()), LineSequence.newlines("hello\nworld".getBytes()));
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
269 // pg1.init(LineSequence.newlines("".getBytes()), LineSequence.newlines("hello\nworld".getBytes()));
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
270 pg1.init(LineSequence.newlines("hello\nworld".getBytes()), LineSequence.newlines("".getBytes()));
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
271 pg1.findMatchingBlocks(new MatchDumpInspector<LineSequence>());
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
272 pg1.findMatchingBlocks(new DeltaDumpInspector<LineSequence>());
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
273 if (Boolean.FALSE.booleanValue()) {
538
dd4f6311af52 Commit: first working version
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 533
diff changeset
274 return;
dd4f6311af52 Commit: first working version
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 533
diff changeset
275 }
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
276 HgRepository repo = new HgLookup().detectFromWorkingDir();
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
277 HgDataFile df = repo.getFileNode("cmdline/org/tmatesoft/hg/console/Main.java");
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
278 ByteArrayChannel bac1, bac2;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
279 df.content(80, bac1 = new ByteArrayChannel());
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
280 df.content(81, bac2 = new ByteArrayChannel());
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
281 // String s1 = "line 1\nline 2\r\nline 3\n\nline 1\nline 2";
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
282 // String s2 = "abc\ncdef\r\nline 2\r\nline 3\nline 2";
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
283 PatchGenerator<LineSequence> pg = new PatchGenerator<LineSequence>();
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
284 byte[] data1 = bac1.toArray();
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
285 byte[] data2 = bac2.toArray();
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
286 pg.init(new LineSequence(data1).splitByNewlines(), new LineSequence(data2).splitByNewlines());
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
287 System.out.println("Matches:");
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
288 pg.findMatchingBlocks(new MatchDumpInspector<LineSequence>());
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
289 System.out.println("Deltas:");
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
290 pg.findMatchingBlocks(new DeltaDumpInspector<LineSequence>());
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
291 }
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
292
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
293 /**
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
294 * Unsure if this marker interface worth presence
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
295 */
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
296 public interface Chunk {
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
297 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
298
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
299 /**
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
300 * Generic sequence of chunk, where chunk is anything comparable to another chunk, e.g. a string or a single char
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
301 * Sequence diff algorithm above doesn't care about sequence nature.
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
302 */
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
303 public interface ChunkSequence<T extends Chunk> {
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
304 public T chunk(int index);
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
305 public int chunkCount();
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
306 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
307
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
308 static final class LineSequence implements ChunkSequence<LineSequence.ByteChain> {
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
309
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
310 private final byte[] input;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
311 private ArrayList<ByteChain> lines;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
312
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
313 public LineSequence(byte[] data) {
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
314 input = data;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
315 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
316
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
317 public static LineSequence newlines(byte[] array) {
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
318 return new LineSequence(array).splitByNewlines();
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
319 }
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
320
545
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
321 // sequence ends with fake, empty line chunk
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
322 public LineSequence splitByNewlines() {
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
323 lines = new ArrayList<ByteChain>();
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
324 int lastStart = 0;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
325 for (int i = 0; i < input.length; i++) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
326 if (input[i] == '\n') {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
327 lines.add(new ByteChain(lastStart, i+1));
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
328 lastStart = i+1;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
329 } else if (input[i] == '\r') {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
330 if (i+1 < input.length && input[i+1] == '\n') {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
331 i++;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
332 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
333 lines.add(new ByteChain(lastStart, i+1));
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
334 lastStart = i+1;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
335 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
336 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
337 if (lastStart < input.length) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
338 lines.add(new ByteChain(lastStart, input.length));
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
339 }
538
dd4f6311af52 Commit: first working version
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 533
diff changeset
340 // empty chunk to keep offset of input end
545
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
341 lines.add(new ByteChain(input.length));
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
342 return this;
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
343 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
344
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
345 public ByteChain chunk(int index) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
346 return lines.get(index);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
347 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
348
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
349 public int chunkCount() {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
350 return lines.size();
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
351 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
352
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
353 public byte[] data(int chunkFrom, int chunkTo) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
354 if (chunkFrom == chunkTo) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
355 return new byte[0];
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
356 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
357 int from = chunk(chunkFrom).getOffset(), to = chunk(chunkTo).getOffset();
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
358 byte[] rv = new byte[to - from];
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
359 System.arraycopy(input, from, rv, 0, rv.length);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
360 return rv;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
361 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
362
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
363
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
364 final class ByteChain implements Chunk {
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
365 private final int start, end;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
366 private final int hash;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
367
545
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
368 /**
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
369 * construct a chunk with a sole purpose to keep
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
370 * offset of the data end
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
371 */
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
372 ByteChain(int offset) {
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
373 start = end = offset;
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
374 // ensure this chunk doesn't match trailing chunk of another sequence
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
375 hash = System.identityHashCode(this);
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
376 }
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
377
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
378 ByteChain(int s, int e) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
379 start = s;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
380 end = e;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
381 hash = calcHash(input, s, e);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
382 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
383
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
384 /**
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
385 * byte offset of the this ByteChain inside ChainSequence
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
386 */
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
387 public int getOffset() {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
388 return start;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
389 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
390
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
391 public byte[] data() {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
392 byte[] rv = new byte[end - start];
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
393 System.arraycopy(input, start, rv, 0, rv.length);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
394 return rv;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
395 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
396
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
397 @Override
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
398 public boolean equals(Object obj) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
399 if (obj == null || obj.getClass() != ByteChain.class) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
400 return false;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
401 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
402 ByteChain other = (ByteChain) obj;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
403 if (other.hash != hash || other.end - other.start != end - start) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
404 return false;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
405 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
406 return other.match(input, start);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
407 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
408
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
409 private boolean match(byte[] oi, int from) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
410 for (int i = start, j = from; i < end; i++, j++) {
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
411 if (LineSequence.this.input[i] != oi[j]) {
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
412 return false;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
413 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
414 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
415 return true;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
416 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
417
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
418 @Override
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
419 public int hashCode() {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
420 return hash;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
421 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
422
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
423 @Override
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
424 public String toString() {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
425 return String.format("[@%d\"%s\"]", start, new String(data()));
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
426 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
427 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
428
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
429 // same as Arrays.hashCode(byte[]), just for a slice of a bigger array
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
430 static int calcHash(byte[] data, int from, int to) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
431 int result = 1;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
432 for (int i = from; i < to; i++) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
433 result = 31 * result + data[i];
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
434 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
435 return result;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
436 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
437 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
438 }