1 | |
|
2 | |
|
3 | |
|
4 | |
|
5 | |
|
6 | |
|
7 | |
|
8 | |
|
9 | |
|
10 | |
|
11 | |
|
12 | |
|
13 | |
|
14 | |
|
15 | |
|
16 | |
|
17 | |
|
18 | |
|
19 | |
|
20 | |
package org.crosswire.common.diff; |
21 | |
|
22 | |
import java.util.ArrayList; |
23 | |
import java.util.List; |
24 | |
import java.util.ListIterator; |
25 | |
import java.util.regex.Matcher; |
26 | |
import java.util.regex.Pattern; |
27 | |
|
28 | |
|
29 | |
|
30 | |
|
31 | |
|
32 | |
|
33 | |
|
34 | |
|
35 | |
|
36 | |
|
37 | |
|
38 | |
public class Patch { |
39 | |
|
40 | |
|
41 | |
|
42 | 0 | public Patch() { |
43 | 0 | patches = new ArrayList<PatchEntry>(); |
44 | 0 | margin = PatchEntry.getMargin(); |
45 | 0 | } |
46 | |
|
47 | |
|
48 | |
|
49 | |
|
50 | |
|
51 | |
|
52 | |
|
53 | |
public Patch(String input) { |
54 | 0 | this(); |
55 | 0 | fromText(input); |
56 | 0 | } |
57 | |
|
58 | |
|
59 | |
|
60 | |
|
61 | |
|
62 | |
|
63 | |
|
64 | |
|
65 | |
|
66 | |
public Patch(String source, String target) { |
67 | 0 | this(source, target, null); |
68 | 0 | } |
69 | |
|
70 | |
|
71 | |
|
72 | |
|
73 | |
|
74 | |
|
75 | |
|
76 | |
|
77 | |
|
78 | |
|
79 | |
|
80 | |
|
81 | |
public Patch(String source, String target, List<Difference> diffs) { |
82 | 0 | this(); |
83 | 0 | make(source, target, diffs); |
84 | 0 | } |
85 | |
|
86 | |
|
87 | |
|
88 | |
|
89 | |
|
90 | |
|
91 | |
|
92 | |
|
93 | |
|
94 | |
|
95 | |
|
96 | |
|
97 | |
|
98 | |
public Patch make(String source, String target, List<Difference> diffList) { |
99 | 0 | List<Difference> diffs = diffList; |
100 | 0 | if (diffs == null) { |
101 | 0 | Diff diff = new Diff(source, target); |
102 | 0 | diffs = diff.compare(); |
103 | 0 | if (diffs.size() > 2) { |
104 | 0 | DiffCleanup.cleanupSemantic(diffs); |
105 | 0 | DiffCleanup.cleanupEfficiency(diffs); |
106 | |
} |
107 | |
} |
108 | |
|
109 | 0 | patches.clear(); |
110 | |
|
111 | 0 | if (diffs.isEmpty()) { |
112 | 0 | return this; |
113 | |
} |
114 | |
|
115 | 0 | PatchEntry patch = new PatchEntry(); |
116 | 0 | int charCount1 = 0; |
117 | 0 | int charCount2 = 0; |
118 | |
|
119 | 0 | String prePatchText = source; |
120 | 0 | String postPatchText = source; |
121 | 0 | int x = 0; |
122 | 0 | for (Difference diff : diffs) { |
123 | 0 | EditType editType = diff.getEditType(); |
124 | 0 | String diffText = diff.getText(); |
125 | 0 | int len = diffText.length(); |
126 | |
|
127 | 0 | if (!patch.hasDifferences() && !EditType.EQUAL.equals(editType)) { |
128 | |
|
129 | 0 | patch.setSourceStart(charCount1); |
130 | 0 | patch.setTargetStart(charCount2); |
131 | |
} |
132 | |
|
133 | 0 | if (EditType.INSERT.equals(editType)) { |
134 | |
|
135 | 0 | patch.addDifference(diff); |
136 | 0 | patch.adjustTargetLength(len); |
137 | 0 | postPatchText = postPatchText.substring(0, charCount2) + diffText + postPatchText.substring(charCount2); |
138 | 0 | } else if (EditType.DELETE.equals(editType)) { |
139 | |
|
140 | 0 | patch.adjustSourceLength(len); |
141 | 0 | patch.addDifference(diff); |
142 | 0 | postPatchText = postPatchText.substring(0, charCount2) + postPatchText.substring(charCount2 + len); |
143 | 0 | } else if (EditType.EQUAL.equals(editType) && len <= 2 * margin && patch.hasDifferences() && diffs.size() != x + 1) { |
144 | |
|
145 | 0 | patch.addDifference(diff); |
146 | 0 | patch.adjustSourceLength(len); |
147 | 0 | patch.adjustTargetLength(len); |
148 | |
} |
149 | |
|
150 | |
|
151 | 0 | if (EditType.EQUAL.equals(editType) && len >= 2 * margin && patch.hasDifferences()) { |
152 | 0 | patch.addContext(prePatchText); |
153 | 0 | patches.add(patch); |
154 | 0 | patch = new PatchEntry(); |
155 | 0 | prePatchText = postPatchText; |
156 | |
} |
157 | |
|
158 | |
|
159 | 0 | if (!EditType.INSERT.equals(editType)) { |
160 | 0 | charCount1 += len; |
161 | |
} |
162 | |
|
163 | 0 | if (!EditType.DELETE.equals(editType)) { |
164 | 0 | charCount2 += len; |
165 | |
} |
166 | |
|
167 | 0 | x++; |
168 | 0 | } |
169 | |
|
170 | |
|
171 | 0 | if (patch.hasDifferences()) { |
172 | 0 | patch.addContext(prePatchText); |
173 | 0 | patches.add(patch); |
174 | |
} |
175 | |
|
176 | 0 | return this; |
177 | |
} |
178 | |
|
179 | |
|
180 | |
|
181 | |
|
182 | |
|
183 | |
|
184 | |
|
185 | |
|
186 | |
|
187 | |
public PatchResults apply(String text) { |
188 | 0 | splitMax(); |
189 | 0 | boolean[] results = new boolean[patches.size()]; |
190 | 0 | String resultText = text; |
191 | 0 | int delta = 0; |
192 | 0 | int expectedLoc = 0; |
193 | 0 | int startLoc = -1; |
194 | 0 | String text1 = ""; |
195 | 0 | String text2 = ""; |
196 | |
List<Difference> diffs; |
197 | 0 | int index1 = 0; |
198 | 0 | int index2 = 0; |
199 | 0 | int x = 0; |
200 | 0 | for (PatchEntry aPatch : patches) { |
201 | 0 | expectedLoc = aPatch.getTargetStart() + delta; |
202 | 0 | text1 = aPatch.getSourceText(); |
203 | 0 | Match match = new Match(resultText, text1, expectedLoc); |
204 | 0 | startLoc = match.locate(); |
205 | 0 | if (startLoc == -1) { |
206 | |
|
207 | 0 | results[x] = false; |
208 | |
} else { |
209 | |
|
210 | 0 | results[x] = true; |
211 | 0 | delta = startLoc - expectedLoc; |
212 | 0 | text2 = resultText.substring(startLoc, startLoc + text1.length()); |
213 | 0 | if (text1.equals(text2)) { |
214 | |
|
215 | 0 | resultText = resultText.substring(0, startLoc) + aPatch.getTargetText() + resultText.substring(startLoc + text1.length()); |
216 | |
} else { |
217 | |
|
218 | |
|
219 | 0 | Diff diff = new Diff(text1, text2, false); |
220 | 0 | diffs = diff.compare(); |
221 | 0 | index1 = 0; |
222 | 0 | for (Difference aDiff : aPatch) { |
223 | 0 | EditType editType = aDiff.getEditType(); |
224 | 0 | if (!EditType.EQUAL.equals(editType)) { |
225 | 0 | index2 = diff.xIndex(diffs, index1); |
226 | |
} |
227 | |
|
228 | 0 | if (EditType.INSERT.equals(editType)) { |
229 | |
|
230 | 0 | resultText = resultText.substring(0, startLoc + index2) + aDiff.getText() + resultText.substring(startLoc + index2); |
231 | 0 | } else if (EditType.DELETE.equals(editType)) { |
232 | |
|
233 | 0 | resultText = resultText.substring(0, startLoc + index2) |
234 | |
+ resultText.substring(startLoc + diff.xIndex(diffs, index1 + aDiff.getText().length())); |
235 | |
} |
236 | |
|
237 | 0 | if (!EditType.DELETE.equals(editType)) { |
238 | 0 | index1 += aDiff.getText().length(); |
239 | |
} |
240 | 0 | } |
241 | |
} |
242 | |
} |
243 | 0 | x++; |
244 | 0 | } |
245 | 0 | return new PatchResults(resultText, results); |
246 | |
} |
247 | |
|
248 | |
|
249 | |
|
250 | |
|
251 | |
|
252 | |
public void splitMax() { |
253 | 0 | int maxPatternLength = new Match().maxPatternLength(); |
254 | 0 | ListIterator<PatchEntry> pointer = patches.listIterator(); |
255 | 0 | PatchEntry bigPatch = pointer.hasNext() ? pointer.next() : null; |
256 | 0 | while (bigPatch != null) { |
257 | 0 | if (bigPatch.getSourceLength() <= maxPatternLength) { |
258 | 0 | if (!pointer.hasNext()) { |
259 | 0 | break; |
260 | |
} |
261 | |
|
262 | 0 | bigPatch = pointer.next(); |
263 | |
} |
264 | |
|
265 | |
|
266 | 0 | pointer.remove(); |
267 | 0 | int patchSize = maxPatternLength; |
268 | 0 | int start1 = bigPatch.getSourceStart(); |
269 | 0 | int start2 = bigPatch.getTargetStart(); |
270 | 0 | String preContext = ""; |
271 | 0 | while (bigPatch.hasDifferences()) { |
272 | |
|
273 | 0 | PatchEntry patch = new PatchEntry(); |
274 | 0 | boolean empty = true; |
275 | |
|
276 | 0 | int len = preContext.length(); |
277 | 0 | patch.setSourceStart(start1 - len); |
278 | 0 | patch.setTargetStart(start2 - len); |
279 | 0 | if (len > 0) { |
280 | 0 | patch.setSourceLength(len); |
281 | 0 | patch.setTargetLength(len); |
282 | 0 | patch.addDifference(new Difference(EditType.EQUAL, preContext)); |
283 | |
} |
284 | |
|
285 | 0 | while (bigPatch.hasDifferences() && patch.getSourceLength() < patchSize - margin) { |
286 | 0 | Difference bigDiff = bigPatch.getFirstDifference(); |
287 | 0 | EditType editType = bigDiff.getEditType(); |
288 | 0 | String diffText = bigDiff.getText(); |
289 | 0 | if (EditType.INSERT.equals(editType)) { |
290 | |
|
291 | 0 | len = diffText.length(); |
292 | 0 | patch.adjustTargetLength(len); |
293 | 0 | start2 += len; |
294 | 0 | patch.addDifference(bigPatch.removeFirstDifference()); |
295 | 0 | empty = false; |
296 | |
} else { |
297 | |
|
298 | |
|
299 | 0 | diffText = diffText.substring(0, Math.min(diffText.length(), patchSize - patch.getSourceLength() - margin)); |
300 | 0 | len = diffText.length(); |
301 | 0 | patch.adjustSourceLength(len); |
302 | 0 | start1 += len; |
303 | 0 | if (EditType.EQUAL.equals(editType)) { |
304 | 0 | patch.adjustTargetLength(len); |
305 | 0 | start2 += len; |
306 | |
} else { |
307 | 0 | empty = false; |
308 | |
} |
309 | |
|
310 | 0 | patch.addDifference(new Difference(editType, diffText)); |
311 | |
|
312 | 0 | if (diffText.equals(bigDiff.getText())) { |
313 | 0 | bigPatch.removeFirstDifference(); |
314 | |
} else { |
315 | 0 | bigDiff.setText(bigDiff.getText().substring(len)); |
316 | |
} |
317 | |
} |
318 | 0 | } |
319 | |
|
320 | |
|
321 | 0 | preContext = patch.getTargetText(); |
322 | 0 | preContext = preContext.substring(Math.max(0, preContext.length() - margin)); |
323 | |
|
324 | |
|
325 | 0 | String postcontext = null; |
326 | 0 | if (bigPatch.getSourceText().length() > margin) { |
327 | 0 | postcontext = bigPatch.getSourceText().substring(0, margin); |
328 | |
} else { |
329 | 0 | postcontext = bigPatch.getSourceText(); |
330 | |
} |
331 | 0 | if (postcontext.length() > 0) { |
332 | 0 | patch.adjustSourceLength(postcontext.length()); |
333 | 0 | patch.adjustTargetLength(postcontext.length()); |
334 | 0 | if (patch.getDifferenceCount() > 0 && EditType.EQUAL.equals(patch.getLastDifference().getEditType())) { |
335 | 0 | Difference diff = patch.getLastDifference(); |
336 | 0 | diff.appendText(postcontext); |
337 | 0 | } else { |
338 | 0 | patch.addDifference(new Difference(EditType.EQUAL, postcontext)); |
339 | |
} |
340 | |
} |
341 | |
|
342 | 0 | if (!empty) { |
343 | 0 | pointer.add(patch); |
344 | |
} |
345 | 0 | } |
346 | |
|
347 | 0 | bigPatch = pointer.hasNext() ? pointer.next() : null; |
348 | 0 | } |
349 | 0 | } |
350 | |
|
351 | |
|
352 | |
|
353 | |
|
354 | |
|
355 | |
|
356 | |
public String toText() { |
357 | 0 | StringBuilder text = new StringBuilder(); |
358 | 0 | for (PatchEntry entry : patches) { |
359 | 0 | text.append(entry); |
360 | |
} |
361 | 0 | return text.toString(); |
362 | |
} |
363 | |
|
364 | |
|
365 | |
|
366 | |
|
367 | |
|
368 | |
|
369 | |
|
370 | |
|
371 | |
|
372 | |
public Patch fromText(String input) { |
373 | 0 | patches.clear(); |
374 | |
|
375 | 0 | Matcher m = patchBoundaryPattern.matcher(input); |
376 | |
|
377 | |
|
378 | 0 | int index = 0; |
379 | 0 | while (m.find()) { |
380 | 0 | int start = m.start(); |
381 | 0 | String match = input.substring(index, start); |
382 | 0 | patches.add(new PatchEntry(match)); |
383 | 0 | index = start + 1; |
384 | 0 | } |
385 | |
|
386 | 0 | if (index == 0) { |
387 | |
|
388 | 0 | patches.add(new PatchEntry(input)); |
389 | |
} else { |
390 | |
|
391 | 0 | patches.add(new PatchEntry(input.substring(index))); |
392 | |
} |
393 | |
|
394 | 0 | return this; |
395 | |
} |
396 | |
|
397 | |
|
398 | |
|
399 | |
|
400 | |
|
401 | |
public static class PatchResults { |
402 | |
|
403 | |
|
404 | |
|
405 | |
|
406 | 0 | public PatchResults(String text, boolean[] results) { |
407 | 0 | this.text = text; |
408 | 0 | this.results = results.clone(); |
409 | 0 | } |
410 | |
|
411 | |
|
412 | |
|
413 | |
|
414 | |
public boolean[] getResults() { |
415 | 0 | return results.clone(); |
416 | |
} |
417 | |
|
418 | |
|
419 | |
|
420 | |
|
421 | |
public String getText() { |
422 | 0 | return text; |
423 | |
} |
424 | |
|
425 | |
private String text; |
426 | |
private boolean[] results; |
427 | |
} |
428 | |
|
429 | |
|
430 | |
|
431 | 0 | private static Pattern patchBoundaryPattern = Pattern.compile("\n@@"); |
432 | |
|
433 | |
private List<PatchEntry> patches; |
434 | |
private int margin; |
435 | |
} |