Mercurial > jhg

annotate src/org/tmatesoft/hg/internal/PatchGenerator.java @ 548:ab21ac7dd833

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Line-by-line annotation API and support code in place
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Mon, 18 Feb 2013 19:58:51 +0100
parents 15b406c7cd9d
children 83afa680555d
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;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
24 import org.tmatesoft.hg.repo.HgLookup;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
25 import org.tmatesoft.hg.repo.HgRepository;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
26
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
27 /**
538
dd4f6311af52 Commit: first working version
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 533
diff changeset
28 * 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
29 *
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
30 * 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
31 * <PATCH>:
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
32 * 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
33 *
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
34 * 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
35 * in the patch.
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
36 *
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
37 * 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
38 *
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 * @author Artem Tikhomirov
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
41 * @author TMate Software Ltd.
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
42 */
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
43 public class PatchGenerator<T extends PatchGenerator.ChunkSequence<?>> {
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
44
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
45 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
46 private T seq1, seq2;
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
47
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
48 // 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
49 private int matchStartS1, matchStartS2;
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
50
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
51 private MatchInspector<T> matchInspector;
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
52
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
53 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
54 seq1 = s1;
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
55 seq2 = s2;
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
56 prepare(s2);
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
57 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
58
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
59
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
60 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
61 chunk2UseIndex = new HashMap<Chunk, IntVector>();
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
62 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
63 Chunk bc = s2.chunk(i);
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
64 IntVector loc = chunk2UseIndex.get(bc);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
65 if (loc == null) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
66 chunk2UseIndex.put(bc, loc = new IntVector());
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
67 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
68 loc.add(i);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
69 // 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
70 // 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
71 // 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
72 // or kept within only one of them
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
73 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
74 // for (ChunkSequence.ByteChain bc : chunk2UseIndex.keySet()) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
75 // System.out.printf("%s: {", new String(bc.data()));
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
76 // for (int x : chunk2UseIndex.get(bc).toArray()) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
77 // System.out.printf(" %d,", x);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
78 // }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
79 // System.out.println("}");
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
80 // }
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
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
83 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
84 insp.begin(seq1, seq2);
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
85 matchInspector = insp;
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
86 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
87 insp.end();
533
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 /**
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
91 * implementation based on Python's difflib.py and SequenceMatcher
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
92 */
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
93 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
94 matchStartS1 = matchStartS2 = 0;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
95 int maxLength = 0;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
96 IntMap<Integer> chunkIndex2MatchCount = new IntMap<Integer>(8);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
97 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
98 Chunk bc = seq1.chunk(i);
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
99 IntMap<Integer> newChunkIndex2MatchCount = new IntMap<Integer>(8);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
100 IntVector occurencesInS2 = chunk2UseIndex.get(bc);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
101 if (occurencesInS2 == null) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
102 // chunkIndex2MatchCount.clear(); // TODO need clear instead of new instance
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
103 chunkIndex2MatchCount = newChunkIndex2MatchCount;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
104 continue;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
105 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
106 for (int j : occurencesInS2.toArray()) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
107 // s1[i] == s2[j]
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
108 if (j < startS2) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
109 continue;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
110 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
111 if (j >= endS2) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
112 break;
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 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
115 int k = prevChunkMatches + 1;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
116 newChunkIndex2MatchCount.put(j, k);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
117 if (k > maxLength) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
118 matchStartS1 = i-k+1;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
119 matchStartS2 = j-k+1;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
120 maxLength = k;
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 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
123 chunkIndex2MatchCount = newChunkIndex2MatchCount;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
124 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
125 return maxLength;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
126 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
127
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
128 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
129 int matchLength = longestMatch(startS1, endS1, startS2, endS2);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
130 if (matchLength > 0) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
131 final int saveStartS1 = matchStartS1, saveStartS2 = matchStartS2;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
132 if (startS1 < matchStartS1 && startS2 < matchStartS2) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
133 findMatchingBlocks(startS1, matchStartS1, startS2, matchStartS2);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
134 }
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
135 matchInspector.match(saveStartS1, saveStartS2, matchLength);
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
136 if (saveStartS1+matchLength < endS1 && saveStartS2+matchLength < endS2) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
137 findMatchingBlocks(saveStartS1 + matchLength, endS1, saveStartS2 + matchLength, endS2);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
138 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
139 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
140 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
141
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
142 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
143 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
144 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
145 void end();
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
146 }
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
147
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
148 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
149 private int matchCount;
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
150
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
151 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
152 matchCount = 0;
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
153 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
154
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
155 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
156 matchCount++;
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
157 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
158 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
159
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
160 public void end() {
545
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
161 if (matchCount == 0) {
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
162 System.out.println("NO MATCHES FOUND!");
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
163 }
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
164 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
165 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
166
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
167 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
168 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
169 protected T seq1, seq2;
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
170
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
171 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
172 seq1 = s1;
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
173 seq2 = s2;
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
174 changeStartS1 = changeStartS2 = 0;
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
175 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
176
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
177 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
178 reportDeltaElement(startSeq1, startSeq2, matchLength);
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
179 changeStartS1 = startSeq1 + matchLength;
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
180 changeStartS2 = startSeq2 + matchLength;
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
181 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
182
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
183 public void end() {
545
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
184 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
185 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
186 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
187 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
188
542
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
189 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
190 if (changeStartS1 < matchStartSeq1) {
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
191 if (changeStartS2 < matchStartSeq2) {
542
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
192 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
193 } else {
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
194 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
195 deleted(matchStartSeq2, changeStartS1, matchStartSeq1);
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
196 }
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
197 } else {
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
198 assert 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) {
545
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
200 added(changeStartS1, 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;
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
203 System.out.printf("adjustent equal blocks %d, %d and %d,%d\n", changeStartS1, matchStartSeq1, changeStartS2, matchStartSeq2);
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 }
542
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
206 if (matchLength > 0) {
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
207 unchanged(matchStartSeq1, matchStartSeq2, matchLength);
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
208 }
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
209 }
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
210
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
211 /**
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
212 * [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
213 */
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
214 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
215 // NO-OP
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
216 }
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
217
543
1e95f48d9886 Report line index for insertion and deletion, test against 'hg diff' output
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 542
diff changeset
218 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
219 // NO-OP
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 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
223 // NO-OP
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
224 }
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 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
227 // NO-OP
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
228 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
229 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
230
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
231 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
232
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
233 @Override
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
234 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
235 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
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 @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
239 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
240 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
241 }
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
242
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
243 @Override
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
244 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
245 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
246 }
545
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
247
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
248 @Override
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
249 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
250 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
251 }
542
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
252 }
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
253
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
254 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
255 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
256 // 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
257 // 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
258 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
259 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
260 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
261 if (Boolean.FALSE.booleanValue()) {
538
dd4f6311af52 Commit: first working version
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 533
diff changeset
262 return;
dd4f6311af52 Commit: first working version
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 533
diff changeset
263 }
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
264 HgRepository repo = new HgLookup().detectFromWorkingDir();
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
265 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
266 ByteArrayChannel bac1, bac2;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
267 df.content(80, bac1 = new ByteArrayChannel());
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
268 df.content(81, bac2 = new ByteArrayChannel());
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
269 // 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
270 // 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
271 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
272 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
273 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
274 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
275 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
276 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
277 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
278 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
279 }
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
280
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
281 /**
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
282 * 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
283 */
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
284 public interface Chunk {
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
285 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
286
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
287 /**
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
288 * 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
289 * 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
290 */
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
291 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
292 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
293 public int chunkCount();
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
294 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
295
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
296 static final class LineSequence implements ChunkSequence<LineSequence.ByteChain> {
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 private final byte[] input;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
299 private ArrayList<ByteChain> lines;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
300
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
301 public LineSequence(byte[] data) {
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
302 input = data;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
303 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
304
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
305 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
306 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
307 }
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
308
545
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
309 // 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
310 public LineSequence splitByNewlines() {
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
311 lines = new ArrayList<ByteChain>();
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
312 int lastStart = 0;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
313 for (int i = 0; i < input.length; i++) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
314 if (input[i] == '\n') {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
315 lines.add(new ByteChain(lastStart, i+1));
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
316 lastStart = i+1;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
317 } else if (input[i] == '\r') {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
318 if (i+1 < input.length && input[i+1] == '\n') {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
319 i++;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
320 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
321 lines.add(new ByteChain(lastStart, i+1));
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
322 lastStart = i+1;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
323 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
324 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
325 if (lastStart < input.length) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
326 lines.add(new ByteChain(lastStart, input.length));
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
327 }
538
dd4f6311af52 Commit: first working version
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 533
diff changeset
328 // 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
329 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
330 return this;
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
331 }
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 public ByteChain chunk(int index) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
334 return lines.get(index);
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 public int chunkCount() {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
338 return lines.size();
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
339 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
340
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
341 public byte[] data(int chunkFrom, int chunkTo) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
342 if (chunkFrom == chunkTo) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
343 return new byte[0];
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 int from = chunk(chunkFrom).getOffset(), to = chunk(chunkTo).getOffset();
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
346 byte[] rv = new byte[to - from];
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
347 System.arraycopy(input, from, rv, 0, rv.length);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
348 return rv;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
349 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
350
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
351
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
352 final class ByteChain implements Chunk {
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
353 private final int start, end;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
354 private final int hash;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
355
545
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
356 /**
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
357 * 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
358 * offset of the data end
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
359 */
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
360 ByteChain(int offset) {
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
361 start = end = offset;
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
362 // 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
363 hash = System.identityHashCode(this);
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
364 }
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
365
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
366 ByteChain(int s, int e) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
367 start = s;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
368 end = e;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
369 hash = calcHash(input, s, e);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
370 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
371
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
372 /**
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
373 * byte offset of the this ByteChain inside ChainSequence
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
374 */
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
375 public int getOffset() {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
376 return start;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
377 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
378
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
379 public byte[] data() {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
380 byte[] rv = new byte[end - start];
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
381 System.arraycopy(input, start, rv, 0, rv.length);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
382 return rv;
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 @Override
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
386 public boolean equals(Object obj) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
387 if (obj == null || obj.getClass() != ByteChain.class) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
388 return false;
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 ByteChain other = (ByteChain) obj;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
391 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
392 return false;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
393 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
394 return other.match(input, start);
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 private boolean match(byte[] oi, int from) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
398 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
399 if (LineSequence.this.input[i] != oi[j]) {
533
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 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
403 return true;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
404 }
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 @Override
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
407 public int hashCode() {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
408 return hash;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
409 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
410
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
411 @Override
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
412 public String toString() {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
413 return String.format("[@%d\"%s\"]", start, new String(data()));
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 }
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 // 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
418 static int calcHash(byte[] data, int from, int to) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
419 int result = 1;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
420 for (int i = from; i < to; i++) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
421 result = 31 * result + data[i];
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 return result;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
424 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
425 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
426 }