Mercurial > jhg

annotate src/org/tmatesoft/hg/internal/DiffHelper.java @ 671:002ed1b2baad

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
AIOOBE in BundleGenerator.ChunkGenerator.iterate when there are no outgoing changes on push
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Fri, 12 Jul 2013 15:29:37 +0200
parents 507602cb4fb3
children 58a6900f845d
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 /**
538
dd4f6311af52 Commit: first working version
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 533
diff changeset
24 * 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
25 *
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
26 * 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
27 * <PATCH>:
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
28 * 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
29 *
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
30 * 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
31 * in the patch.
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
32 *
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
33 * 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
34 *
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
35 *
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
36 * @author Artem Tikhomirov
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
37 * @author TMate Software Ltd.
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
38 */
551
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 549
diff changeset
39 public class DiffHelper<T extends DiffHelper.ChunkSequence<?>> {
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
40
551
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 549
diff changeset
41 private Map<Object, IntVector> chunk2UseIndex;
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
42 private T seq1, seq2;
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
43
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
44 // 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
45 private int matchStartS1, matchStartS2;
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
46
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
47 private MatchInspector<T> matchInspector;
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
48
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
49 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
50 seq1 = s1;
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
51 seq2 = s2;
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
52 prepare(s2);
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
53 }
549
83afa680555d Annotate merge revision (combined diff against two parents without looking further)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 545
diff changeset
54
83afa680555d Annotate merge revision (combined diff against two parents without looking further)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 545
diff changeset
55 public void init(T s1) {
83afa680555d Annotate merge revision (combined diff against two parents without looking further)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 545
diff changeset
56 if (seq2 == null) {
83afa680555d Annotate merge revision (combined diff against two parents without looking further)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 545
diff changeset
57 throw new IllegalStateException("Use this #init() only when target sequence shall be matched against different origin");
83afa680555d Annotate merge revision (combined diff against two parents without looking further)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 545
diff changeset
58 }
83afa680555d Annotate merge revision (combined diff against two parents without looking further)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 545
diff changeset
59 seq1 = s1;
83afa680555d Annotate merge revision (combined diff against two parents without looking further)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 545
diff changeset
60 }
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
61
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
62
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
63 private void prepare(T s2) {
551
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 549
diff changeset
64 chunk2UseIndex = new HashMap<Object, IntVector>();
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
65 for (int i = 0, len = s2.chunkCount(); i < len; i++) {
551
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 549
diff changeset
66 Object bc = s2.chunk(i);
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
67 IntVector loc = chunk2UseIndex.get(bc);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
68 if (loc == null) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
69 chunk2UseIndex.put(bc, loc = new IntVector());
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
70 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
71 loc.add(i);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
72 // 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
73 // 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
74 // 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
75 // or kept within only one of them
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
76 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
77 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
78
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
79 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
80 insp.begin(seq1, seq2);
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
81 matchInspector = insp;
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
82 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
83 insp.end();
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
84 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
85
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
86 /**
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
87 * implementation based on Python's difflib.py and SequenceMatcher
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 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
90 matchStartS1 = matchStartS2 = 0;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
91 int maxLength = 0;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
92 IntMap<Integer> chunkIndex2MatchCount = new IntMap<Integer>(8);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
93 for (int i = startS1; i < endS1; i++) {
551
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 549
diff changeset
94 Object bc = seq1.chunk(i);
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
95 IntVector occurencesInS2 = chunk2UseIndex.get(bc);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
96 if (occurencesInS2 == null) {
551
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 549
diff changeset
97 chunkIndex2MatchCount.clear();
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
98 continue;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
99 }
551
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 549
diff changeset
100 IntMap<Integer> newChunkIndex2MatchCount = new IntMap<Integer>(8);
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
101 for (int j : occurencesInS2.toArray()) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
102 // s1[i] == s2[j]
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
103 if (j < startS2) {
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 if (j >= endS2) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
107 break;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
108 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
109 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
110 int k = prevChunkMatches + 1;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
111 newChunkIndex2MatchCount.put(j, k);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
112 if (k > maxLength) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
113 matchStartS1 = i-k+1;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
114 matchStartS2 = j-k+1;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
115 maxLength = k;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
116 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
117 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
118 chunkIndex2MatchCount = newChunkIndex2MatchCount;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
119 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
120 return maxLength;
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
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
123 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
124 int matchLength = longestMatch(startS1, endS1, startS2, endS2);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
125 if (matchLength > 0) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
126 final int saveStartS1 = matchStartS1, saveStartS2 = matchStartS2;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
127 if (startS1 < matchStartS1 && startS2 < matchStartS2) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
128 findMatchingBlocks(startS1, matchStartS1, startS2, matchStartS2);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
129 }
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
130 matchInspector.match(saveStartS1, saveStartS2, matchLength);
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
131 if (saveStartS1+matchLength < endS1 && saveStartS2+matchLength < endS2) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
132 findMatchingBlocks(saveStartS1 + matchLength, endS1, saveStartS2 + matchLength, endS2);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
133 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
134 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
135 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
136
551
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 549
diff changeset
137 public interface MatchInspector<T extends ChunkSequence<?>> {
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
138 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
139 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
140 void end();
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
141 }
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
142
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
143 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
144 private int matchCount;
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
145
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
146 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
147 matchCount = 0;
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
148 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
149
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
150 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
151 matchCount++;
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
152 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
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 end() {
545
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
156 if (matchCount == 0) {
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
157 System.out.println("NO MATCHES FOUND!");
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
158 }
541
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 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
161
551
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 549
diff changeset
162 /**
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 549
diff changeset
163 * Matcher implementation that translates "match/equal" notification to a delta-style "added/removed/changed".
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 549
diff changeset
164 */
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 549
diff changeset
165 public 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
166 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
167 protected T seq1, seq2;
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
168
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
169 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
170 seq1 = s1;
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
171 seq2 = s2;
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
172 changeStartS1 = changeStartS2 = 0;
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
173 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
174
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
175 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
176 reportDeltaElement(startSeq1, startSeq2, matchLength);
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
177 changeStartS1 = startSeq1 + matchLength;
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
178 changeStartS2 = startSeq2 + matchLength;
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
179 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
180
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
181 public void end() {
545
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
182 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
183 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
184 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
185 }
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
186
542
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
187 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
188 if (changeStartS1 < matchStartSeq1) {
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
189 if (changeStartS2 < matchStartSeq2) {
542
a71a05ec11bc Towards annotate/blame support: general outline of the functionality
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 541
diff changeset
190 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
191 } else {
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
192 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
193 deleted(matchStartSeq2, changeStartS1, matchStartSeq1);
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
194 }
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
195 } else {
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
196 assert changeStartS1 == matchStartSeq1;
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
197 if(changeStartS2 < matchStartSeq2) {
545
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
198 added(changeStartS1, changeStartS2, matchStartSeq2);
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
199 } else {
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
200 assert changeStartS2 == matchStartSeq2;
549
83afa680555d Annotate merge revision (combined diff against two parents without looking further)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 545
diff changeset
201 if (matchStartSeq1 > 0 || matchStartSeq2 > 0) {
624
507602cb4fb3 FIXMEs and TODOs: pay some technical debt
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 583
diff changeset
202 assert false : String.format("adjustent equal blocks %d, %d and %d,%d", changeStartS1, matchStartSeq1, changeStartS2, matchStartSeq2);
549
83afa680555d Annotate merge revision (combined diff against two parents without looking further)
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 545
diff changeset
203 }
541
946b13196252 PatchGenerator: refactoring to facilitate use in annotate/blame
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 538
diff changeset
204 }
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
205 }
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
583
47dfa0ec7e35 Effective revlog patching
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 556
diff changeset
231 public 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
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
254 /**
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
255 * 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
256 * 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
257 */
551
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 549
diff changeset
258 public interface ChunkSequence<T> {
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
259 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
260 public int chunkCount();
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
261 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
262
551
4ea0351ca878 Better (precise) name for diff facility, tests
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 549
diff changeset
263 public static final class LineSequence implements ChunkSequence<LineSequence.ByteChain> {
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
264
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
265 private final byte[] input;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
266 private ArrayList<ByteChain> lines;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
267
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
268 public LineSequence(byte[] data) {
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
269 input = data;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
270 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
271
544
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
272 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
273 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
274 }
7f5998a9619d Refactor PatchGenerator to be generic and welcome sequence of any nature
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 543
diff changeset
275
545
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
276 // 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
277 public LineSequence splitByNewlines() {
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
278 lines = new ArrayList<ByteChain>();
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
279 int lastStart = 0;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
280 for (int i = 0; i < input.length; i++) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
281 if (input[i] == '\n') {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
282 lines.add(new ByteChain(lastStart, i+1));
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
283 lastStart = i+1;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
284 } else if (input[i] == '\r') {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
285 if (i+1 < input.length && input[i+1] == '\n') {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
286 i++;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
287 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
288 lines.add(new ByteChain(lastStart, i+1));
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
289 lastStart = i+1;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
290 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
291 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
292 if (lastStart < input.length) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
293 lines.add(new ByteChain(lastStart, input.length));
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
294 }
538
dd4f6311af52 Commit: first working version
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 533
diff changeset
295 // 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
296 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
297 return this;
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
298 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
299
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
300 public ByteChain chunk(int index) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
301 return lines.get(index);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
302 }
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 public int chunkCount() {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
305 return lines.size();
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
306 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
307
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
308 public byte[] data(int chunkFrom, int chunkTo) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
309 if (chunkFrom == chunkTo) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
310 return new byte[0];
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
311 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
312 int from = chunk(chunkFrom).getOffset(), to = chunk(chunkTo).getOffset();
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
313 byte[] rv = new byte[to - from];
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
314 System.arraycopy(input, from, rv, 0, rv.length);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
315 return rv;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
316 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
317
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
318
556
e55f17a7a195 AnnotateFacility renamed to HgBlameFacility and exposed, API shapes out and got some javadoc
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 551
diff changeset
319 public final class ByteChain {
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
320 private final int start, end;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
321 private final int hash;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
322
545
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
323 /**
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
324 * 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
325 * offset of the data end
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
326 */
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
327 ByteChain(int offset) {
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
328 start = end = offset;
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
329 // 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
330 hash = System.identityHashCode(this);
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
331 }
15b406c7cd9d First round of annotate file is functional
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents: 544
diff changeset
332
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
333 ByteChain(int s, int e) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
334 start = s;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
335 end = e;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
336 hash = calcHash(input, s, e);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
337 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
338
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 * byte offset of the this ByteChain inside ChainSequence
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
341 */
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
342 public int getOffset() {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
343 return start;
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
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
346 public byte[] data() {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
347 byte[] rv = new byte[end - start];
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
348 System.arraycopy(input, start, rv, 0, rv.length);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
349 return rv;
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
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
352 @Override
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
353 public boolean equals(Object obj) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
354 if (obj == null || obj.getClass() != ByteChain.class) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
355 return false;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
356 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
357 ByteChain other = (ByteChain) obj;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
358 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
359 return false;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
360 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
361 return other.match(input, start);
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
362 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
363
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
364 private boolean match(byte[] oi, int from) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
365 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
366 if (LineSequence.this.input[i] != oi[j]) {
533
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
367 return false;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
368 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
369 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
370 return true;
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 @Override
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
374 public int hashCode() {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
375 return hash;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
376 }
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 @Override
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
379 public String toString() {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
380 return String.format("[@%d\"%s\"]", start, new String(data()));
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
381 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
382 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
383
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
384 // 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
385 static int calcHash(byte[] data, int from, int to) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
386 int result = 1;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
387 for (int i = from; i < to; i++) {
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
388 result = 31 * result + data[i];
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 return result;
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
391 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
392 }
e6f72c9829a6 Generate patches using diff algorithm
Artem Tikhomirov <tikhomirov.artem@gmail.com>
parents:
diff changeset
393 }