Mercurial > jhg

annotate src/org/tmatesoft/hg/internal/PatchGenerator.java @ 546:cd78e8b9d7bc

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
File annotate test. Refactored FileAnnotation as standalone class, introduced LineInspector to make line offset calc code shared
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Mon, 18 Feb 2013 19:19:48 +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 }