Mercurial > jhg

comparison src/org/tmatesoft/hg/internal/PatchGenerator.java @ 541:946b13196252

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
PatchGenerator: refactoring to facilitate use in annotate/blame
author Artem Tikhomirov <tikhomirov.artem@gmail.com>
date Wed, 13 Feb 2013 19:42:22 +0100
parents dd4f6311af52
children a71a05ec11bc
comparison
equal deleted inserted replaced
540:67d4b0f73984 541:946b13196252
45 private Map<ChunkSequence.ByteChain, IntVector> chunk2UseIndex; 45 private Map<ChunkSequence.ByteChain, IntVector> chunk2UseIndex;
46 private ChunkSequence seq1, seq2; 46 private ChunkSequence seq1, seq2;
47 47
48 // get filled by #longestMatch, track start of common sequence in seq1 and seq2, respectively 48 // get filled by #longestMatch, track start of common sequence in seq1 and seq2, respectively
49 private int matchStartS1, matchStartS2; 49 private int matchStartS1, matchStartS2;
50 // get filled by #findMatchingBlocks, track start of changed/unknown sequence in seq1 and seq2 50
51 private int changeStartS1, changeStartS2; 51 private MatchInspector matchInspector;
52 52
53 public void init(byte[] data1, byte[] data2) { 53 public void init(byte[] data1, byte[] data2) {
54 seq1 = new ChunkSequence(data1); 54 seq1 = new ChunkSequence(data1);
55 seq1.splitByNewlines(); 55 seq1.splitByNewlines();
56 seq2 = new ChunkSequence(data2); 56 seq2 = new ChunkSequence(data2);
79 // } 79 // }
80 // System.out.println("}"); 80 // System.out.println("}");
81 // } 81 // }
82 } 82 }
83 83
84 public void findMatchingBlocks() { 84 public void findMatchingBlocks(MatchInspector insp) {
85 changeStartS1 = changeStartS2 = 0; 85 insp.begin(seq1, seq2);
86 matchInspector = insp;
86 findMatchingBlocks(0, seq1.chunkCount(), 0, seq2.chunkCount()); 87 findMatchingBlocks(0, seq1.chunkCount(), 0, seq2.chunkCount());
87 if (changeStartS1 < seq1.chunkCount() || changeStartS2 < seq2.chunkCount()) { 88 insp.end();
88 reportDeltaElement(seq1.chunkCount(), seq2.chunkCount());
89 }
90 } 89 }
91 90
92 /** 91 /**
93 * implementation based on Python's difflib.py and SequenceMatcher 92 * implementation based on Python's difflib.py and SequenceMatcher
94 */ 93 */
125 chunkIndex2MatchCount = newChunkIndex2MatchCount; 124 chunkIndex2MatchCount = newChunkIndex2MatchCount;
126 } 125 }
127 return maxLength; 126 return maxLength;
128 } 127 }
129 128
130 public void findMatchingBlocks(int startS1, int endS1, int startS2, int endS2) { 129 private void findMatchingBlocks(int startS1, int endS1, int startS2, int endS2) {
131 int matchLength = longestMatch(startS1, endS1, startS2, endS2); 130 int matchLength = longestMatch(startS1, endS1, startS2, endS2);
132 if (matchLength > 0) { 131 if (matchLength > 0) {
133 final int saveStartS1 = matchStartS1, saveStartS2 = matchStartS2; 132 final int saveStartS1 = matchStartS1, saveStartS2 = matchStartS2;
134 if (startS1 < matchStartS1 && startS2 < matchStartS2) { 133 if (startS1 < matchStartS1 && startS2 < matchStartS2) {
135 findMatchingBlocks(startS1, matchStartS1, startS2, matchStartS2); 134 findMatchingBlocks(startS1, matchStartS1, startS2, matchStartS2);
136 } 135 }
137 reportDeltaElement(saveStartS1, saveStartS2); 136 matchInspector.match(saveStartS1, saveStartS2, matchLength);
138 changeStartS1 = saveStartS1 + matchLength;
139 changeStartS2 = saveStartS2 + matchLength;
140 // System.out.printf("match: from line #%d and line #%d of length %d\n", saveStartS1, saveStartS2, matchLength);
141 if (saveStartS1+matchLength < endS1 && saveStartS2+matchLength < endS2) { 137 if (saveStartS1+matchLength < endS1 && saveStartS2+matchLength < endS2) {
142 findMatchingBlocks(saveStartS1 + matchLength, endS1, saveStartS2 + matchLength, endS2); 138 findMatchingBlocks(saveStartS1 + matchLength, endS1, saveStartS2 + matchLength, endS2);
143 } 139 }
144 } 140 }
145 } 141 }
146 142
147 private Patch deltaCollector; 143 interface MatchInspector {
148 144 void begin(ChunkSequence s1, ChunkSequence s2);
149 private void reportDeltaElement(int i, int j) { 145 void match(int startSeq1, int startSeq2, int matchLength);
150 if (changeStartS1 < i) { 146 void end();
151 if (changeStartS2 < j) { 147 }
152 System.out.printf("changed [%d..%d) with [%d..%d)\n", changeStartS1, i, changeStartS2, j); 148
149 static class MatchDumpInspector implements MatchInspector {
150 public void begin(ChunkSequence s1, ChunkSequence s2) {
151 }
152
153 public void match(int startSeq1, int startSeq2, int matchLength) {
154 System.out.printf("match: from line #%d and line #%d of length %d\n", startSeq1, startSeq2, matchLength);
155 }
156
157 public void end() {
158 }
159 }
160
161 static class DeltaDumpInspector implements MatchInspector {
162 protected int changeStartS1, changeStartS2;
163 protected ChunkSequence seq1, seq2;
164
165
166 public void begin(ChunkSequence s1, ChunkSequence s2) {
167 seq1 = s1;
168 seq2 = s2;
169 changeStartS1 = changeStartS2 = 0;
170 }
171
172 public void match(int startSeq1, int startSeq2, int matchLength) {
173 reportDeltaElement(startSeq1, startSeq2);
174 changeStartS1 = startSeq1 + matchLength;
175 changeStartS2 = startSeq2 + matchLength;
176 }
177
178 public void end() {
179 if (changeStartS1 < seq1.chunkCount() || changeStartS2 < seq2.chunkCount()) {
180 reportDeltaElement(seq1.chunkCount(), seq2.chunkCount());
181 }
182 }
183
184 protected void reportDeltaElement(int matchStartSeq1, int matchStartSeq2) {
185 if (changeStartS1 < matchStartSeq1) {
186 if (changeStartS2 < matchStartSeq2) {
187 System.out.printf("changed [%d..%d) with [%d..%d)\n", changeStartS1, matchStartSeq1, changeStartS2, matchStartSeq2);
188 } else {
189 assert changeStartS2 == matchStartSeq2;
190 System.out.printf("deleted [%d..%d)\n", changeStartS1, matchStartSeq1);
191 }
153 } else { 192 } else {
154 assert changeStartS2 == j; 193 assert changeStartS1 == matchStartSeq1;
155 System.out.printf("deleted [%d..%d)\n", changeStartS1, i); 194 if(changeStartS2 < matchStartSeq2) {
156 } 195 System.out.printf("added [%d..%d)\n", changeStartS2, matchStartSeq2);
157 if (deltaCollector != null) { 196 } else {
197 assert changeStartS2 == matchStartSeq2;
198 System.out.printf("adjustent equal blocks %d, %d and %d,%d\n", changeStartS1, matchStartSeq1, changeStartS2, matchStartSeq2);
199 }
200 }
201 }
202 }
203
204 static class PatchFillInspector extends DeltaDumpInspector {
205 private final Patch deltaCollector;
206
207 PatchFillInspector(Patch p) {
208 assert p != null;
209 deltaCollector = p;
210 }
211
212 @Override
213 protected void reportDeltaElement(int matchStartSeq1, int matchStartSeq2) {
214 if (changeStartS1 < matchStartSeq1) {
158 int from = seq1.chunk(changeStartS1).getOffset(); 215 int from = seq1.chunk(changeStartS1).getOffset();
159 int to = seq1.chunk(i).getOffset(); 216 int to = seq1.chunk(matchStartSeq1).getOffset();
160 byte[] data = seq2.data(changeStartS2, j); 217 byte[] data = seq2.data(changeStartS2, matchStartSeq2);
161 deltaCollector.add(from, to, data); 218 deltaCollector.add(from, to, data);
162 }
163 } else {
164 assert changeStartS1 == i;
165 if(changeStartS2 < j) {
166 System.out.printf("added [%d..%d)\n", changeStartS2, j);
167 } else { 219 } else {
168 assert changeStartS2 == j; 220 assert changeStartS1 == matchStartSeq1;
169 System.out.printf("adjustent equal blocks %d, %d and %d,%d\n", changeStartS1, i, changeStartS2, j);
170 }
171 if (deltaCollector != null) {
172 int insPoint = seq1.chunk(changeStartS1).getOffset(); 221 int insPoint = seq1.chunk(changeStartS1).getOffset();
173 byte[] data = seq2.data(changeStartS2, j); 222 byte[] data = seq2.data(changeStartS2, matchStartSeq2);
174 deltaCollector.add(insPoint, insPoint, data); 223 deltaCollector.add(insPoint, insPoint, data);
175 } 224 }
176 } 225 }
177 } 226 }
227
228
178 229
179 public static void main(String[] args) throws Exception { 230 public static void main(String[] args) throws Exception {
180 PatchGenerator pg1 = new PatchGenerator(); 231 PatchGenerator pg1 = new PatchGenerator();
181 pg1.init("hello".getBytes(), "hello\nworld".getBytes()); 232 pg1.init("hello".getBytes(), "hello\nworld".getBytes());
182 pg1.findMatchingBlocks(); 233 pg1.findMatchingBlocks(new MatchDumpInspector());
183 if (Boolean.TRUE.booleanValue()) { 234 pg1.findMatchingBlocks(new DeltaDumpInspector());
235 if (Boolean.FALSE.booleanValue()) {
184 return; 236 return;
185 } 237 }
186 HgRepository repo = new HgLookup().detectFromWorkingDir(); 238 HgRepository repo = new HgLookup().detectFromWorkingDir();
187 HgDataFile df = repo.getFileNode("cmdline/org/tmatesoft/hg/console/Main.java"); 239 HgDataFile df = repo.getFileNode("cmdline/org/tmatesoft/hg/console/Main.java");
188 ByteArrayChannel bac1, bac2; 240 ByteArrayChannel bac1, bac2;
190 df.content(81, bac2 = new ByteArrayChannel()); 242 df.content(81, bac2 = new ByteArrayChannel());
191 // String s1 = "line 1\nline 2\r\nline 3\n\nline 1\nline 2"; 243 // String s1 = "line 1\nline 2\r\nline 3\n\nline 1\nline 2";
192 // String s2 = "abc\ncdef\r\nline 2\r\nline 3\nline 2"; 244 // String s2 = "abc\ncdef\r\nline 2\r\nline 3\nline 2";
193 PatchGenerator pg = new PatchGenerator(); 245 PatchGenerator pg = new PatchGenerator();
194 pg.init(bac1.toArray(), bac2.toArray()); 246 pg.init(bac1.toArray(), bac2.toArray());
195 pg.findMatchingBlocks(); 247 System.out.println("Matches:");
248 pg.findMatchingBlocks(new MatchDumpInspector());
249 System.out.println("Deltas:");
250 pg.findMatchingBlocks(new DeltaDumpInspector());
196 } 251 }
197 252
198 public Patch delta(byte[] prev, byte[] content) { 253 public Patch delta(byte[] prev, byte[] content) {
199 deltaCollector = new Patch(); 254 Patch rv = new Patch();
200 init(prev, content); 255 init(prev, content);
201 findMatchingBlocks(); 256 findMatchingBlocks(new PatchFillInspector(rv));
202 return deltaCollector; 257 return rv;
203 } 258 }
204 259
205 private static class ChunkSequence { 260 private static class ChunkSequence {
206 261
207 private final byte[] input; 262 private final byte[] input;