| Patch.java |
1 /**
2 * Distribution License:
3 * JSword is free software; you can redistribute it and/or modify it under
4 * the terms of the GNU Lesser General Public License, version 2.1 or later
5 * as published by the Free Software Foundation. This program is distributed
6 * in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even
7 * the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
8 * See the GNU Lesser General Public License for more details.
9 *
10 * The License is available on the internet at:
11 * http://www.gnu.org/copyleft/lgpl.html
12 * or by writing to:
13 * Free Software Foundation, Inc.
14 * 59 Temple Place - Suite 330
15 * Boston, MA 02111-1307, USA
16 *
17 * © CrossWire Bible Society, 2007 - 2016
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 * Marshals a patch to a list of Differences, Differences to a patch and applies
30 * a list of differences to text to patch it.
31 *
32 * Based on the LGPL Diff_Match_Patch v1.5 javascript of Neil Fraser, Copyright (C) 2006<br>
33 * <a href="http://neil.fraser.name/software/diff_match_patch/">http://neil.fraser.name/software/diff_match_patch/</a>
34 *
35 * @see gnu.lgpl.License The GNU Lesser General Public License for details.
36 * @author DM Smith
37 */
38 public class Patch {
39 /**
40 * Create an empty patch.
41 */
42 public Patch() {
43 patches = new ArrayList<PatchEntry>();
44 margin = PatchEntry.getMargin();
45 }
46
47 /**
48 * Create a Patch from a textual representation,
49 *
50 * @param input
51 * Text representation of patches
52 */
53 public Patch(String input) {
54 this();
55 fromText(input);
56 }
57
58 /**
59 * Create a patch that can turn text1 into text2.
60 *
61 * @param source
62 * Old text
63 * @param target
64 * New text
65 */
66 public Patch(String source, String target) {
67 this(source, target, null);
68 }
69
70 /**
71 * Create a patch that can turn text1 into text2. Use the diffs provided, if
72 * not null. Compute diffs otherwise.
73 *
74 * @param source
75 * Old text
76 * @param target
77 * New text
78 * @param diffs
79 * Optional array of diff tuples for text1 to text2.
80 */
81 public Patch(String source, String target, List<Difference> diffs) {
82 this();
83 make(source, target, diffs);
84 }
85
86 /**
87 * Compute a list of patches to turn text1 into text2. Use the diffs
88 * provided.
89 *
90 * @param source
91 * Old text
92 * @param target
93 * New text
94 * @param diffList
95 * Optional array of diff tuples for text1 to text2.
96 * @return this patch
97 */
98 public Patch make(String source, String target, List<Difference> diffList) {
99 List<Difference> diffs = diffList;
100 if (diffs == null) {
101 Diff diff = new Diff(source, target);
102 diffs = diff.compare();
103 if (diffs.size() > 2) {
104 DiffCleanup.cleanupSemantic(diffs);
105 DiffCleanup.cleanupEfficiency(diffs);
106 }
107 }
108
109 patches.clear();
110
111 if (diffs.isEmpty()) {
112 return this; // Get rid of the null case.
113 }
114
115 PatchEntry patch = new PatchEntry();
116 int charCount1 = 0; // Number of characters into the text1 string.
117 int charCount2 = 0; // Number of characters into the text2 string.
118 // Recreate the patches to determine context info.
119 String prePatchText = source;
120 String postPatchText = source;
121 int x = 0;
122 for (Difference diff : diffs) {
123 EditType editType = diff.getEditType();
124 String diffText = diff.getText();
125 int len = diffText.length();
126
127 if (!patch.hasDifferences() && !EditType.EQUAL.equals(editType)) {
128 // A new patch starts here.
129 patch.setSourceStart(charCount1);
130 patch.setTargetStart(charCount2);
131 }
132
133 if (EditType.INSERT.equals(editType)) {
134 // Insertion
135 patch.addDifference(diff);
136 patch.adjustTargetLength(len);
137 postPatchText = postPatchText.substring(0, charCount2) + diffText + postPatchText.substring(charCount2);
138 } else if (EditType.DELETE.equals(editType)) {
139 // Deletion.
140 patch.adjustSourceLength(len);
141 patch.addDifference(diff);
142 postPatchText = postPatchText.substring(0, charCount2) + postPatchText.substring(charCount2 + len);
143 } else if (EditType.EQUAL.equals(editType) && len <= 2 * margin && patch.hasDifferences() && diffs.size() != x + 1) {
144 // Small equality inside a patch.
145 patch.addDifference(diff);
146 patch.adjustSourceLength(len);
147 patch.adjustTargetLength(len);
148 }
149
150 // Time for a new patch.
151 if (EditType.EQUAL.equals(editType) && len >= 2 * margin && patch.hasDifferences()) {
152 patch.addContext(prePatchText);
153 patches.add(patch);
154 patch = new PatchEntry();
155 prePatchText = postPatchText;
156 }
157
158 // Update the current character count.
159 if (!EditType.INSERT.equals(editType)) {
160 charCount1 += len;
161 }
162
163 if (!EditType.DELETE.equals(editType)) {
164 charCount2 += len;
165 }
166
167 x++;
168 }
169
170 // Pick up the leftover patch if not empty.
171 if (patch.hasDifferences()) {
172 patch.addContext(prePatchText);
173 patches.add(patch);
174 }
175
176 return this;
177 }
178
179 /**
180 * Merge this patch onto the text. Return a patched text, as well as an
181 * array of true/false values indicating which patches were applied.
182 *
183 * @param text
184 * Old text
185 * @return the patch result
186 */
187 public PatchResults apply(String text) {
188 splitMax();
189 boolean[] results = new boolean[patches.size()];
190 String resultText = text;
191 int delta = 0;
192 int expectedLoc = 0;
193 int startLoc = -1;
194 String text1 = "";
195 String text2 = "";
196 List<Difference> diffs;
197 int index1 = 0;
198 int index2 = 0;
199 int x = 0;
200 for (PatchEntry aPatch : patches) {
201 expectedLoc = aPatch.getTargetStart() + delta;
202 text1 = aPatch.getSourceText();
203 Match match = new Match(resultText, text1, expectedLoc);
204 startLoc = match.locate();
205 if (startLoc == -1) {
206 // No match found. :(
207 results[x] = false;
208 } else {
209 // Found a match. :)
210 results[x] = true;
211 delta = startLoc - expectedLoc;
212 text2 = resultText.substring(startLoc, startLoc + text1.length());
213 if (text1.equals(text2)) {
214 // Perfect match, just shove the replacement text in.
215 resultText = resultText.substring(0, startLoc) + aPatch.getTargetText() + resultText.substring(startLoc + text1.length());
216 } else {
217 // Imperfect match. Run a diff to get a framework of
218 // equivalent indicies.
219 Diff diff = new Diff(text1, text2, false);
220 diffs = diff.compare();
221 index1 = 0;
222 for (Difference aDiff : aPatch) {
223 EditType editType = aDiff.getEditType();
224 if (!EditType.EQUAL.equals(editType)) {
225 index2 = diff.xIndex(diffs, index1);
226 }
227
228 if (EditType.INSERT.equals(editType)) {
229 // Insertion
230 resultText = resultText.substring(0, startLoc + index2) + aDiff.getText() + resultText.substring(startLoc + index2);
231 } else if (EditType.DELETE.equals(editType)) {
232 // Deletion
233 resultText = resultText.substring(0, startLoc + index2)
234 + resultText.substring(startLoc + diff.xIndex(diffs, index1 + aDiff.getText().length()));
235 }
236
237 if (!EditType.DELETE.equals(editType)) {
238 index1 += aDiff.getText().length();
239 }
240 }
241 }
242 }
243 x++;
244 }
245 return new PatchResults(resultText, results);
246 }
247
248 /**
249 * Look through the patches and break up any which are longer than the
250 * maximum limit of the match algorithm.
251 */
252 public void splitMax() {
253 int maxPatternLength = new Match().maxPatternLength();
254 ListIterator<PatchEntry> pointer = patches.listIterator();
255 PatchEntry bigPatch = pointer.hasNext() ? pointer.next() : null;
256 while (bigPatch != null) {
257 if (bigPatch.getSourceLength() <= maxPatternLength) {
258 if (!pointer.hasNext()) {
259 break;
260 }
261
262 bigPatch = pointer.next();
263 }
264
265 // Remove the big old patch.
266 pointer.remove();
267 int patchSize = maxPatternLength;
268 int start1 = bigPatch.getSourceStart();
269 int start2 = bigPatch.getTargetStart();
270 String preContext = "";
271 while (bigPatch.hasDifferences()) {
272 // Create one of several smaller patches.
273 PatchEntry patch = new PatchEntry();
274 boolean empty = true;
275
276 int len = preContext.length();
277 patch.setSourceStart(start1 - len);
278 patch.setTargetStart(start2 - len);
279 if (len > 0) {
280 patch.setSourceLength(len);
281 patch.setTargetLength(len);
282 patch.addDifference(new Difference(EditType.EQUAL, preContext));
283 }
284
285 while (bigPatch.hasDifferences() && patch.getSourceLength() < patchSize - margin) {
286 Difference bigDiff = bigPatch.getFirstDifference();
287 EditType editType = bigDiff.getEditType();
288 String diffText = bigDiff.getText();
289 if (EditType.INSERT.equals(editType)) {
290 // Insertions are harmless.
291 len = diffText.length();
292 patch.adjustTargetLength(len);
293 start2 += len;
294 patch.addDifference(bigPatch.removeFirstDifference());
295 empty = false;
296 } else {
297 // Deletion or equality. Only take as much as we can
298 // stomach.
299 diffText = diffText.substring(0, Math.min(diffText.length(), patchSize - patch.getSourceLength() - margin));
300 len = diffText.length();
301 patch.adjustSourceLength(len);
302 start1 += len;
303 if (EditType.EQUAL.equals(editType)) {
304 patch.adjustTargetLength(len);
305 start2 += len;
306 } else {
307 empty = false;
308 }
309
310 patch.addDifference(new Difference(editType, diffText));
311
312 if (diffText.equals(bigDiff.getText())) {
313 bigPatch.removeFirstDifference();
314 } else {
315 bigDiff.setText(bigDiff.getText().substring(len));
316 }
317 }
318 }
319
320 // Compute the head context for the next patch.
321 preContext = patch.getTargetText();
322 preContext = preContext.substring(Math.max(0, preContext.length() - margin));
323
324 // Append the end context for this patch.
325 String postcontext = null;
326 if (bigPatch.getSourceText().length() > margin) {
327 postcontext = bigPatch.getSourceText().substring(0, margin);
328 } else {
329 postcontext = bigPatch.getSourceText();
330 }
331 if (postcontext.length() > 0) {
332 patch.adjustSourceLength(postcontext.length());
333 patch.adjustTargetLength(postcontext.length());
334 if (patch.getDifferenceCount() > 0 && EditType.EQUAL.equals(patch.getLastDifference().getEditType())) {
335 Difference diff = patch.getLastDifference();
336 diff.appendText(postcontext);
337 } else {
338 patch.addDifference(new Difference(EditType.EQUAL, postcontext));
339 }
340 }
341
342 if (!empty) {
343 pointer.add(patch);
344 }
345 }
346
347 bigPatch = pointer.hasNext() ? pointer.next() : null;
348 }
349 }
350
351 /**
352 * Take a list of patches and return a textual representation.
353 *
354 * @return Text representation of patches.
355 */
356 public String toText() {
357 StringBuilder text = new StringBuilder();
358 for (PatchEntry entry : patches) {
359 text.append(entry);
360 }
361 return text.toString();
362 }
363
364 /**
365 * Parse a textual representation of patches and return a List of Patch
366 * objects.
367 *
368 * @param input
369 * Text representation of patches
370 * @return List of Patch objects
371 */
372 public Patch fromText(String input) {
373 patches.clear();
374
375 Matcher m = patchBoundaryPattern.matcher(input);
376
377 // Add segments before each match found
378 int index = 0;
379 while (m.find()) {
380 int start = m.start();
381 String match = input.substring(index, start);
382 patches.add(new PatchEntry(match));
383 index = start + 1;
384 }
385
386 if (index == 0) {
387 // No match was found, the patch consists of the entire string
388 patches.add(new PatchEntry(input));
389 } else {
390 // Add remaining segment
391 patches.add(new PatchEntry(input.substring(index)));
392 }
393
394 return this;
395 }
396
397 /**
398 * A holder of the results of a patch, with a results indicating which patch
399 * entries were able to be applied.
400 */
401 public static class PatchResults {
402 /**
403 * @param text the text
404 * @param results the results
405 */
406 public PatchResults(String text, boolean[] results) {
407 this.text = text;
408 this.results = results.clone();
409 }
410
411 /**
412 * @return the results
413 */
414 public boolean[] getResults() {
415 return results.clone();
416 }
417
418 /**
419 * @return the text
420 */
421 public String getText() {
422 return text;
423 }
424
425 private String text;
426 private boolean[] results;
427 }
428
429 // Ideally we'd like to have the @@ be merely a look-ahead, but it doesn't
430 // work that way with split.
431 private static Pattern patchBoundaryPattern = Pattern.compile("\n@@");
432
433 private List<PatchEntry> patches;
434 private int margin;
435 }
436