1/*
2 * Test harness for diff_match_patch.java
3 *
4 * Copyright 2006 Google Inc.
5 * http://code.google.com/p/google-diff-match-patch/
6 *
7 * Licensed under the Apache License, Version 2.0 (the "License");
8 * you may not use this file except in compliance with the License.
9 * You may obtain a copy of the License at
10 *
11 *   http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing, software
14 * distributed under the License is distributed on an "AS IS" BASIS,
15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 * See the License for the specific language governing permissions and
17 * limitations under the License.
18 */
19
20package name.fraser.neil.plaintext;
21
22import junit.framework.TestCase;
23
24import java.util.ArrayList;
25import java.util.Arrays;
26import java.util.HashMap;
27import java.util.HashSet;
28import java.util.LinkedList;
29import java.util.List;
30import java.util.Map;
31import java.util.Set;
32
33import name.fraser.neil.plaintext.diff_match_patch.Diff;
34import name.fraser.neil.plaintext.diff_match_patch.LinesToCharsResult;
35import name.fraser.neil.plaintext.diff_match_patch.Patch;
36
37public class diff_match_patch_test extends TestCase {
38
39  private diff_match_patch dmp;
40  private diff_match_patch.Operation DELETE = diff_match_patch.Operation.DELETE;
41  private diff_match_patch.Operation EQUAL = diff_match_patch.Operation.EQUAL;
42  private diff_match_patch.Operation INSERT = diff_match_patch.Operation.INSERT;
43
44  protected void setUp() {
45    // Create an instance of the diff_match_patch object.
46    dmp = new diff_match_patch();
47  }
48
49
50  //  DIFF TEST FUNCTIONS
51
52
53  public void testDiffCommonPrefix() {
54    // Detect and remove any common prefix.
55    assertEquals("diff_commonPrefix: Null case.", 0, dmp.diff_commonPrefix("abc", "xyz"));
56
57    assertEquals("diff_commonPrefix: Non-null case.", 4, dmp.diff_commonPrefix("1234abcdef", "1234xyz"));
58
59    assertEquals("diff_commonPrefix: Whole case.", 4, dmp.diff_commonPrefix("1234", "1234xyz"));
60  }
61
62  public void testDiffCommonSuffix() {
63    // Detect and remove any common suffix.
64    assertEquals("diff_commonSuffix: Null case.", 0, dmp.diff_commonSuffix("abc", "xyz"));
65
66    assertEquals("diff_commonSuffix: Non-null case.", 4, dmp.diff_commonSuffix("abcdef1234", "xyz1234"));
67
68    assertEquals("diff_commonSuffix: Whole case.", 4, dmp.diff_commonSuffix("1234", "xyz1234"));
69  }
70
71  public void testDiffHalfmatch() {
72    // Detect a halfmatch.
73    assertNull("diff_halfMatch: No match.", dmp.diff_halfMatch("1234567890", "abcdef"));
74
75    assertArrayEquals("diff_halfMatch: Single Match #1.", new String[]{"12", "90", "a", "z", "345678"}, dmp.diff_halfMatch("1234567890", "a345678z"));
76
77    assertArrayEquals("diff_halfMatch: Single Match #2.", new String[]{"a", "z", "12", "90", "345678"}, dmp.diff_halfMatch("a345678z", "1234567890"));
78
79    assertArrayEquals("diff_halfMatch: Multiple Matches #1.", new String[]{"12123", "123121", "a", "z", "1234123451234"}, dmp.diff_halfMatch("121231234123451234123121", "a1234123451234z"));
80
81    assertArrayEquals("diff_halfMatch: Multiple Matches #2.", new String[]{"", "-=-=-=-=-=", "x", "", "x-=-=-=-=-=-=-="}, dmp.diff_halfMatch("x-=-=-=-=-=-=-=-=-=-=-=-=", "xx-=-=-=-=-=-=-="));
82
83    assertArrayEquals("diff_halfMatch: Multiple Matches #3.", new String[]{"-=-=-=-=-=", "", "", "y", "-=-=-=-=-=-=-=y"}, dmp.diff_halfMatch("-=-=-=-=-=-=-=-=-=-=-=-=y", "-=-=-=-=-=-=-=yy"));
84  }
85
86  public void testDiffLinesToChars() {
87    // Convert lines down to characters.
88    ArrayList<String> tmpVector = new ArrayList<String>();
89    tmpVector.add("");
90    tmpVector.add("alpha\n");
91    tmpVector.add("beta\n");
92    assertLinesToCharsResultEquals("diff_linesToChars:", new LinesToCharsResult("\u0001\u0002\u0001", "\u0002\u0001\u0002", tmpVector), dmp.diff_linesToChars("alpha\nbeta\nalpha\n", "beta\nalpha\nbeta\n"));
93
94    tmpVector.clear();
95    tmpVector.add("");
96    tmpVector.add("alpha\r\n");
97    tmpVector.add("beta\r\n");
98    tmpVector.add("\r\n");
99    assertLinesToCharsResultEquals("diff_linesToChars:", new LinesToCharsResult("", "\u0001\u0002\u0003\u0003", tmpVector), dmp.diff_linesToChars("", "alpha\r\nbeta\r\n\r\n\r\n"));
100
101    tmpVector.clear();
102    tmpVector.add("");
103    tmpVector.add("a");
104    tmpVector.add("b");
105    assertLinesToCharsResultEquals("diff_linesToChars:", new LinesToCharsResult("\u0001", "\u0002", tmpVector), dmp.diff_linesToChars("a", "b"));
106
107    // More than 256 to reveal any 8-bit limitations.
108    int n = 300;
109    tmpVector.clear();
110    StringBuilder lineList = new StringBuilder();
111    StringBuilder charList = new StringBuilder();
112    for (int x = 1; x < n + 1; x++) {
113      tmpVector.add(x + "\n");
114      lineList.append(x + "\n");
115      charList.append(String.valueOf((char) x));
116    }
117    assertEquals(n, tmpVector.size());
118    String lines = lineList.toString();
119    String chars = charList.toString();
120    assertEquals(n, chars.length());
121    tmpVector.add(0, "");
122    assertLinesToCharsResultEquals("diff_linesToChars: More than 256.", new LinesToCharsResult(chars, "", tmpVector), dmp.diff_linesToChars(lines, ""));
123  }
124
125  public void testDiffCharsToLines() {
126    // First check that Diff equality works.
127    assertTrue("diff_charsToLines:", new Diff(EQUAL, "a").equals(new Diff(EQUAL, "a")));
128
129    assertEquals("diff_charsToLines:", new Diff(EQUAL, "a"), new Diff(EQUAL, "a"));
130
131    // Convert chars up to lines
132    LinkedList<Diff> diffs = diffList(new Diff(EQUAL, "\u0001\u0002\u0001"), new Diff(INSERT, "\u0002\u0001\u0002"));
133    ArrayList<String> tmpVector = new ArrayList<String>();
134    tmpVector.add("");
135    tmpVector.add("alpha\n");
136    tmpVector.add("beta\n");
137    dmp.diff_charsToLines(diffs, tmpVector);
138    assertEquals("diff_charsToLines:", diffList(new Diff(EQUAL, "alpha\nbeta\nalpha\n"), new Diff(INSERT, "beta\nalpha\nbeta\n")), diffs);
139
140    // More than 256 to reveal any 8-bit limitations.
141    int n = 300;
142    tmpVector.clear();
143    StringBuilder lineList = new StringBuilder();
144    StringBuilder charList = new StringBuilder();
145    for (int x = 1; x < n + 1; x++) {
146      tmpVector.add(x + "\n");
147      lineList.append(x + "\n");
148      charList.append(String.valueOf((char) x));
149    }
150    assertEquals(n, tmpVector.size());
151    String lines = lineList.toString();
152    String chars = charList.toString();
153    assertEquals(n, chars.length());
154    tmpVector.add(0, "");
155    diffs = diffList(new Diff(DELETE, chars));
156    dmp.diff_charsToLines(diffs, tmpVector);
157    assertEquals("diff_charsToLines: More than 256.", diffList(new Diff(DELETE, lines)), diffs);
158  }
159
160  public void testDiffCleanupMerge() {
161    // Cleanup a messy diff.
162    LinkedList<Diff> diffs = diffList();
163    dmp.diff_cleanupMerge(diffs);
164    assertEquals("diff_cleanupMerge: Null case.", diffList(), diffs);
165
166    diffs = diffList(new Diff(EQUAL, "a"), new Diff(DELETE, "b"), new Diff(INSERT, "c"));
167    dmp.diff_cleanupMerge(diffs);
168    assertEquals("diff_cleanupMerge: No change case.", diffList(new Diff(EQUAL, "a"), new Diff(DELETE, "b"), new Diff(INSERT, "c")), diffs);
169
170    diffs = diffList(new Diff(EQUAL, "a"), new Diff(EQUAL, "b"), new Diff(EQUAL, "c"));
171    dmp.diff_cleanupMerge(diffs);
172    assertEquals("diff_cleanupMerge: Merge equalities.", diffList(new Diff(EQUAL, "abc")), diffs);
173
174    diffs = diffList(new Diff(DELETE, "a"), new Diff(DELETE, "b"), new Diff(DELETE, "c"));
175    dmp.diff_cleanupMerge(diffs);
176    assertEquals("diff_cleanupMerge: Merge deletions.", diffList(new Diff(DELETE, "abc")), diffs);
177
178    diffs = diffList(new Diff(INSERT, "a"), new Diff(INSERT, "b"), new Diff(INSERT, "c"));
179    dmp.diff_cleanupMerge(diffs);
180    assertEquals("diff_cleanupMerge: Merge insertions.", diffList(new Diff(INSERT, "abc")), diffs);
181
182    diffs = diffList(new Diff(DELETE, "a"), new Diff(INSERT, "b"), new Diff(DELETE, "c"), new Diff(INSERT, "d"), new Diff(EQUAL, "e"), new Diff(EQUAL, "f"));
183    dmp.diff_cleanupMerge(diffs);
184    assertEquals("diff_cleanupMerge: Merge interweave.", diffList(new Diff(DELETE, "ac"), new Diff(INSERT, "bd"), new Diff(EQUAL, "ef")), diffs);
185
186    diffs = diffList(new Diff(DELETE, "a"), new Diff(INSERT, "abc"), new Diff(DELETE, "dc"));
187    dmp.diff_cleanupMerge(diffs);
188    assertEquals("diff_cleanupMerge: Prefix and suffix detection.", diffList(new Diff(EQUAL, "a"), new Diff(DELETE, "d"), new Diff(INSERT, "b"), new Diff(EQUAL, "c")), diffs);
189
190    diffs = diffList(new Diff(EQUAL, "a"), new Diff(INSERT, "ba"), new Diff(EQUAL, "c"));
191    dmp.diff_cleanupMerge(diffs);
192    assertEquals("diff_cleanupMerge: Slide edit left.", diffList(new Diff(INSERT, "ab"), new Diff(EQUAL, "ac")), diffs);
193
194    diffs = diffList(new Diff(EQUAL, "c"), new Diff(INSERT, "ab"), new Diff(EQUAL, "a"));
195    dmp.diff_cleanupMerge(diffs);
196    assertEquals("diff_cleanupMerge: Slide edit right.", diffList(new Diff(EQUAL, "ca"), new Diff(INSERT, "ba")), diffs);
197
198    diffs = diffList(new Diff(EQUAL, "a"), new Diff(DELETE, "b"), new Diff(EQUAL, "c"), new Diff(DELETE, "ac"), new Diff(EQUAL, "x"));
199    dmp.diff_cleanupMerge(diffs);
200    assertEquals("diff_cleanupMerge: Slide edit left recursive.", diffList(new Diff(DELETE, "abc"), new Diff(EQUAL, "acx")), diffs);
201
202    diffs = diffList(new Diff(EQUAL, "x"), new Diff(DELETE, "ca"), new Diff(EQUAL, "c"), new Diff(DELETE, "b"), new Diff(EQUAL, "a"));
203    dmp.diff_cleanupMerge(diffs);
204    assertEquals("diff_cleanupMerge: Slide edit right recursive.", diffList(new Diff(EQUAL, "xca"), new Diff(DELETE, "cba")), diffs);
205  }
206
207  public void testDiffCleanupSemanticLossless() {
208    // Slide diffs to match logical boundaries.
209    LinkedList<Diff> diffs = diffList();
210    dmp.diff_cleanupSemanticLossless(diffs);
211    assertEquals("diff_cleanupSemanticLossless: Null case.", diffList(), diffs);
212
213    diffs = diffList(new Diff(EQUAL, "AAA\r\n\r\nBBB"), new Diff(INSERT, "\r\nDDD\r\n\r\nBBB"), new Diff(EQUAL, "\r\nEEE"));
214    dmp.diff_cleanupSemanticLossless(diffs);
215    assertEquals("diff_cleanupSemanticLossless: Blank lines.", diffList(new Diff(EQUAL, "AAA\r\n\r\n"), new Diff(INSERT, "BBB\r\nDDD\r\n\r\n"), new Diff(EQUAL, "BBB\r\nEEE")), diffs);
216
217    diffs = diffList(new Diff(EQUAL, "AAA\r\nBBB"), new Diff(INSERT, " DDD\r\nBBB"), new Diff(EQUAL, " EEE"));
218    dmp.diff_cleanupSemanticLossless(diffs);
219    assertEquals("diff_cleanupSemanticLossless: Line boundaries.", diffList(new Diff(EQUAL, "AAA\r\n"), new Diff(INSERT, "BBB DDD\r\n"), new Diff(EQUAL, "BBB EEE")), diffs);
220
221    diffs = diffList(new Diff(EQUAL, "The c"), new Diff(INSERT, "ow and the c"), new Diff(EQUAL, "at."));
222    dmp.diff_cleanupSemanticLossless(diffs);
223    assertEquals("diff_cleanupSemanticLossless: Word boundaries.", diffList(new Diff(EQUAL, "The "), new Diff(INSERT, "cow and the "), new Diff(EQUAL, "cat.")), diffs);
224
225    diffs = diffList(new Diff(EQUAL, "The-c"), new Diff(INSERT, "ow-and-the-c"), new Diff(EQUAL, "at."));
226    dmp.diff_cleanupSemanticLossless(diffs);
227    assertEquals("diff_cleanupSemanticLossless: Alphanumeric boundaries.", diffList(new Diff(EQUAL, "The-"), new Diff(INSERT, "cow-and-the-"), new Diff(EQUAL, "cat.")), diffs);
228
229    diffs = diffList(new Diff(EQUAL, "a"), new Diff(DELETE, "a"), new Diff(EQUAL, "ax"));
230    dmp.diff_cleanupSemanticLossless(diffs);
231    assertEquals("diff_cleanupSemanticLossless: Hitting the start.", diffList(new Diff(DELETE, "a"), new Diff(EQUAL, "aax")), diffs);
232
233    diffs = diffList(new Diff(EQUAL, "xa"), new Diff(DELETE, "a"), new Diff(EQUAL, "a"));
234    dmp.diff_cleanupSemanticLossless(diffs);
235    assertEquals("diff_cleanupSemanticLossless: Hitting the end.", diffList(new Diff(EQUAL, "xaa"), new Diff(DELETE, "a")), diffs);
236  }
237
238  public void testDiffCleanupSemantic() {
239    // Cleanup semantically trivial equalities.
240    LinkedList<Diff> diffs = diffList();
241    dmp.diff_cleanupSemantic(diffs);
242    assertEquals("diff_cleanupSemantic: Null case.", diffList(), diffs);
243
244    diffs = diffList(new Diff(DELETE, "a"), new Diff(INSERT, "b"), new Diff(EQUAL, "cd"), new Diff(DELETE, "e"));
245    dmp.diff_cleanupSemantic(diffs);
246    assertEquals("diff_cleanupSemantic: No elimination.", diffList(new Diff(DELETE, "a"), new Diff(INSERT, "b"), new Diff(EQUAL, "cd"), new Diff(DELETE, "e")), diffs);
247
248    diffs = diffList(new Diff(DELETE, "a"), new Diff(EQUAL, "b"), new Diff(DELETE, "c"));
249    dmp.diff_cleanupSemantic(diffs);
250    assertEquals("diff_cleanupSemantic: Simple elimination.", diffList(new Diff(DELETE, "abc"), new Diff(INSERT, "b")), diffs);
251
252    diffs = diffList(new Diff(DELETE, "ab"), new Diff(EQUAL, "cd"), new Diff(DELETE, "e"), new Diff(EQUAL, "f"), new Diff(INSERT, "g"));
253    dmp.diff_cleanupSemantic(diffs);
254    assertEquals("diff_cleanupSemantic: Backpass elimination.", diffList(new Diff(DELETE, "abcdef"), new Diff(INSERT, "cdfg")), diffs);
255
256    diffs = diffList(new Diff(INSERT, "1"), new Diff(EQUAL, "A"), new Diff(DELETE, "B"), new Diff(INSERT, "2"), new Diff(EQUAL, "_"), new Diff(INSERT, "1"), new Diff(EQUAL, "A"), new Diff(DELETE, "B"), new Diff(INSERT, "2"));
257    dmp.diff_cleanupSemantic(diffs);
258    assertEquals("diff_cleanupSemantic: Multiple elimination.", diffList(new Diff(DELETE, "AB_AB"), new Diff(INSERT, "1A2_1A2")), diffs);
259
260    diffs = diffList(new Diff(EQUAL, "The c"), new Diff(DELETE, "ow and the c"), new Diff(EQUAL, "at."));
261    dmp.diff_cleanupSemantic(diffs);
262    assertEquals("diff_cleanupSemantic: Word boundaries.", diffList(new Diff(EQUAL, "The "), new Diff(DELETE, "cow and the "), new Diff(EQUAL, "cat.")), diffs);
263  }
264
265  public void testDiffCleanupEfficiency() {
266    // Cleanup operationally trivial equalities.
267    dmp.Diff_EditCost = 4;
268    LinkedList<Diff> diffs = diffList();
269    dmp.diff_cleanupEfficiency(diffs);
270    assertEquals("diff_cleanupEfficiency: Null case.", diffList(), diffs);
271
272    diffs = diffList(new Diff(DELETE, "ab"), new Diff(INSERT, "12"), new Diff(EQUAL, "wxyz"), new Diff(DELETE, "cd"), new Diff(INSERT, "34"));
273    dmp.diff_cleanupEfficiency(diffs);
274    assertEquals("diff_cleanupEfficiency: No elimination.", diffList(new Diff(DELETE, "ab"), new Diff(INSERT, "12"), new Diff(EQUAL, "wxyz"), new Diff(DELETE, "cd"), new Diff(INSERT, "34")), diffs);
275
276    diffs = diffList(new Diff(DELETE, "ab"), new Diff(INSERT, "12"), new Diff(EQUAL, "xyz"), new Diff(DELETE, "cd"), new Diff(INSERT, "34"));
277    dmp.diff_cleanupEfficiency(diffs);
278    assertEquals("diff_cleanupEfficiency: Four-edit elimination.", diffList(new Diff(DELETE, "abxyzcd"), new Diff(INSERT, "12xyz34")), diffs);
279
280    diffs = diffList(new Diff(INSERT, "12"), new Diff(EQUAL, "x"), new Diff(DELETE, "cd"), new Diff(INSERT, "34"));
281    dmp.diff_cleanupEfficiency(diffs);
282    assertEquals("diff_cleanupEfficiency: Three-edit elimination.", diffList(new Diff(DELETE, "xcd"), new Diff(INSERT, "12x34")), diffs);
283
284    diffs = diffList(new Diff(DELETE, "ab"), new Diff(INSERT, "12"), new Diff(EQUAL, "xy"), new Diff(INSERT, "34"), new Diff(EQUAL, "z"), new Diff(DELETE, "cd"), new Diff(INSERT, "56"));
285    dmp.diff_cleanupEfficiency(diffs);
286    assertEquals("diff_cleanupEfficiency: Backpass elimination.", diffList(new Diff(DELETE, "abxyzcd"), new Diff(INSERT, "12xy34z56")), diffs);
287
288    dmp.Diff_EditCost = 5;
289    diffs = diffList(new Diff(DELETE, "ab"), new Diff(INSERT, "12"), new Diff(EQUAL, "wxyz"), new Diff(DELETE, "cd"), new Diff(INSERT, "34"));
290    dmp.diff_cleanupEfficiency(diffs);
291    assertEquals("diff_cleanupEfficiency: High cost elimination.", diffList(new Diff(DELETE, "abwxyzcd"), new Diff(INSERT, "12wxyz34")), diffs);
292    dmp.Diff_EditCost = 4;
293  }
294
295  public void testDiffPrettyHtml() {
296    // Pretty print.
297    LinkedList<Diff> diffs = diffList(new Diff(EQUAL, "a\n"), new Diff(DELETE, "<B>b</B>"), new Diff(INSERT, "c&d"));
298    assertEquals("diff_prettyHtml:", "<SPAN TITLE=\"i=0\">a&para;<BR></SPAN><DEL STYLE=\"background:#FFE6E6;\" TITLE=\"i=2\">&lt;B&gt;b&lt;/B&gt;</DEL><INS STYLE=\"background:#E6FFE6;\" TITLE=\"i=2\">c&amp;d</INS>", dmp.diff_prettyHtml(diffs));
299  }
300
301  public void testDiffText() {
302    // Compute the source and destination texts.
303    LinkedList<Diff> diffs = diffList(new Diff(EQUAL, "jump"), new Diff(DELETE, "s"), new Diff(INSERT, "ed"), new Diff(EQUAL, " over "), new Diff(DELETE, "the"), new Diff(INSERT, "a"), new Diff(EQUAL, " lazy"));
304    assertEquals("diff_text1:", "jumps over the lazy", dmp.diff_text1(diffs));
305    assertEquals("diff_text2:", "jumped over a lazy", dmp.diff_text2(diffs));
306  }
307
308  public void testDiffDelta() {
309    // Convert a diff into delta string.
310    LinkedList<Diff> diffs = diffList(new Diff(EQUAL, "jump"), new Diff(DELETE, "s"), new Diff(INSERT, "ed"), new Diff(EQUAL, " over "), new Diff(DELETE, "the"), new Diff(INSERT, "a"), new Diff(EQUAL, " lazy"), new Diff(INSERT, "old dog"));
311    String text1 = dmp.diff_text1(diffs);
312    assertEquals("diff_text1: Base text.", "jumps over the lazy", text1);
313
314    String delta = dmp.diff_toDelta(diffs);
315    assertEquals("diff_toDelta:", "=4\t-1\t+ed\t=6\t-3\t+a\t=5\t+old dog", delta);
316
317    // Convert delta string into a diff.
318    assertEquals("diff_fromDelta: Normal.", diffs, dmp.diff_fromDelta(text1, delta));
319
320    // Generates error (19 < 20).
321    try {
322      dmp.diff_fromDelta(text1 + "x", delta);
323      fail("diff_fromDelta: Too long.");
324    } catch (IllegalArgumentException ex) {
325      // Exception expected.
326    }
327
328    // Generates error (19 > 18).
329    try {
330      dmp.diff_fromDelta(text1.substring(1), delta);
331      fail("diff_fromDelta: Too short.");
332    } catch (IllegalArgumentException ex) {
333      // Exception expected.
334    }
335
336    // Generates error (%c3%xy invalid Unicode).
337    try {
338      dmp.diff_fromDelta("", "+%c3%xy");
339      fail("diff_fromDelta: Invalid character.");
340    } catch (IllegalArgumentException ex) {
341      // Exception expected.
342    }
343
344    // Test deltas with special characters.
345    diffs = diffList(new Diff(EQUAL, "\u0680 \000 \t %"), new Diff(DELETE, "\u0681 \001 \n ^"), new Diff(INSERT, "\u0682 \002 \\ |"));
346    text1 = dmp.diff_text1(diffs);
347    assertEquals("diff_text1: Unicode text.", "\u0680 \000 \t %\u0681 \001 \n ^", text1);
348
349    delta = dmp.diff_toDelta(diffs);
350    assertEquals("diff_toDelta: Unicode.", "=7\t-7\t+%DA%82 %02 %5C %7C", delta);
351
352    assertEquals("diff_fromDelta: Unicode.", diffs, dmp.diff_fromDelta(text1, delta));
353
354    // Verify pool of unchanged characters.
355    diffs = diffList(new Diff(INSERT, "A-Z a-z 0-9 - _ . ! ~ * ' ( ) ; / ? : @ & = + $ , # "));
356    String text2 = dmp.diff_text2(diffs);
357    assertEquals("diff_text2: Unchanged characters.", "A-Z a-z 0-9 - _ . ! ~ * \' ( ) ; / ? : @ & = + $ , # ", text2);
358
359    delta = dmp.diff_toDelta(diffs);
360    assertEquals("diff_toDelta: Unchanged characters.", "+A-Z a-z 0-9 - _ . ! ~ * \' ( ) ; / ? : @ & = + $ , # ", delta);
361
362    // Convert delta string into a diff.
363    assertEquals("diff_fromDelta: Unchanged characters.", diffs, dmp.diff_fromDelta("", delta));
364  }
365
366  public void testDiffXIndex() {
367    // Translate a location in text1 to text2.
368    LinkedList<Diff> diffs = diffList(new Diff(DELETE, "a"), new Diff(INSERT, "1234"), new Diff(EQUAL, "xyz"));
369    assertEquals("diff_xIndex: Translation on equality.", 5, dmp.diff_xIndex(diffs, 2));
370
371    diffs = diffList(new Diff(EQUAL, "a"), new Diff(DELETE, "1234"), new Diff(EQUAL, "xyz"));
372    assertEquals("diff_xIndex: Translation on deletion.", 1, dmp.diff_xIndex(diffs, 3));
373  }
374
375  public void testDiffLevenshtein() {
376    LinkedList<Diff> diffs = diffList(new Diff(DELETE, "abc"), new Diff(INSERT, "1234"), new Diff(EQUAL, "xyz"));
377    assertEquals("Levenshtein with trailing equality.", 4, dmp.diff_levenshtein(diffs));
378
379    diffs = diffList(new Diff(EQUAL, "xyz"), new Diff(DELETE, "abc"), new Diff(INSERT, "1234"));
380    assertEquals("Levenshtein with leading equality.", 4, dmp.diff_levenshtein(diffs));
381
382    diffs = diffList(new Diff(DELETE, "abc"), new Diff(EQUAL, "xyz"), new Diff(INSERT, "1234"));
383    assertEquals("Levenshtein with middle equality.", 7, dmp.diff_levenshtein(diffs));
384  }
385
386  public void testDiffPath() {
387    // First, check footprints are different.
388    assertTrue("diff_footprint:", dmp.diff_footprint(1, 10) != dmp.diff_footprint(10, 1));
389
390    // Single letters.
391    // Trace a path from back to front.
392    List<Set<Long>> v_map;
393    Set<Long> row_set;
394    v_map = new ArrayList<Set<Long>>();
395    {
396      row_set = new HashSet<Long>();
397      row_set.add(dmp.diff_footprint(0, 0));
398      v_map.add(row_set);
399      row_set = new HashSet<Long>();
400      row_set.add(dmp.diff_footprint(0, 1));
401      row_set.add(dmp.diff_footprint(1, 0));
402      v_map.add(row_set);
403      row_set = new HashSet<Long>();
404      row_set.add(dmp.diff_footprint(0, 2));
405      row_set.add(dmp.diff_footprint(2, 0));
406      row_set.add(dmp.diff_footprint(2, 2));
407      v_map.add(row_set);
408      row_set = new HashSet<Long>();
409      row_set.add(dmp.diff_footprint(0, 3));
410      row_set.add(dmp.diff_footprint(2, 3));
411      row_set.add(dmp.diff_footprint(3, 0));
412      row_set.add(dmp.diff_footprint(4, 3));
413      v_map.add(row_set);
414      row_set = new HashSet<Long>();
415      row_set.add(dmp.diff_footprint(0, 4));
416      row_set.add(dmp.diff_footprint(2, 4));
417      row_set.add(dmp.diff_footprint(4, 0));
418      row_set.add(dmp.diff_footprint(4, 4));
419      row_set.add(dmp.diff_footprint(5, 3));
420      v_map.add(row_set);
421      row_set = new HashSet<Long>();
422      row_set.add(dmp.diff_footprint(0, 5));
423      row_set.add(dmp.diff_footprint(2, 5));
424      row_set.add(dmp.diff_footprint(4, 5));
425      row_set.add(dmp.diff_footprint(5, 0));
426      row_set.add(dmp.diff_footprint(6, 3));
427      row_set.add(dmp.diff_footprint(6, 5));
428      v_map.add(row_set);
429      row_set = new HashSet<Long>();
430      row_set.add(dmp.diff_footprint(0, 6));
431      row_set.add(dmp.diff_footprint(2, 6));
432      row_set.add(dmp.diff_footprint(4, 6));
433      row_set.add(dmp.diff_footprint(6, 6));
434      row_set.add(dmp.diff_footprint(7, 5));
435      v_map.add(row_set);
436    }
437    LinkedList<Diff> diffs = diffList(new Diff(INSERT, "W"), new Diff(DELETE, "A"), new Diff(EQUAL, "1"), new Diff(DELETE, "B"), new Diff(EQUAL, "2"), new Diff(INSERT, "X"), new Diff(DELETE, "C"), new Diff(EQUAL, "3"), new Diff(DELETE, "D"));
438    assertEquals("diff_path1: Single letters.", diffs, dmp.diff_path1(v_map, "A1B2C3D", "W12X3"));
439
440    // Trace a path from front to back.
441    v_map.remove(v_map.size() - 1);
442    diffs = diffList(new Diff(EQUAL, "4"), new Diff(DELETE, "E"), new Diff(INSERT, "Y"), new Diff(EQUAL, "5"), new Diff(DELETE, "F"), new Diff(EQUAL, "6"), new Diff(DELETE, "G"), new Diff(INSERT, "Z"));
443    assertEquals("diff_path2: Single letters.", diffs, dmp.diff_path2(v_map, "4E5F6G", "4Y56Z"));
444
445    // Double letters.
446    // Trace a path from back to front.
447    v_map = new ArrayList<Set<Long>>();
448    {
449      row_set = new HashSet<Long>();
450      row_set.add(dmp.diff_footprint(0, 0));
451      v_map.add(row_set);
452      row_set = new HashSet<Long>();
453      row_set.add(dmp.diff_footprint(0, 1));
454      row_set.add(dmp.diff_footprint(1, 0));
455      v_map.add(row_set);
456      row_set = new HashSet<Long>();
457      row_set.add(dmp.diff_footprint(0, 2));
458      row_set.add(dmp.diff_footprint(1, 1));
459      row_set.add(dmp.diff_footprint(2, 0));
460      v_map.add(row_set);
461      row_set = new HashSet<Long>();
462      row_set.add(dmp.diff_footprint(0, 3));
463      row_set.add(dmp.diff_footprint(1, 2));
464      row_set.add(dmp.diff_footprint(2, 1));
465      row_set.add(dmp.diff_footprint(3, 0));
466      v_map.add(row_set);
467      row_set = new HashSet<Long>();
468      row_set.add(dmp.diff_footprint(0, 4));
469      row_set.add(dmp.diff_footprint(1, 3));
470      row_set.add(dmp.diff_footprint(3, 1));
471      row_set.add(dmp.diff_footprint(4, 0));
472      row_set.add(dmp.diff_footprint(4, 4));
473      v_map.add(row_set);
474    }
475    diffs = diffList(new Diff(INSERT, "WX"), new Diff(DELETE, "AB"), new Diff(EQUAL, "12"));
476    assertEquals("diff_path1: Double letters.", diffs, dmp.diff_path1(v_map, "AB12", "WX12"));
477
478    // Trace a path from front to back.
479    v_map = new ArrayList<Set<Long>>();
480    {
481      row_set = new HashSet<Long>();
482      row_set.add(dmp.diff_footprint(0, 0));
483      v_map.add(row_set);
484      row_set = new HashSet<Long>();
485      row_set.add(dmp.diff_footprint(0, 1));
486      row_set.add(dmp.diff_footprint(1, 0));
487      v_map.add(row_set);
488      row_set = new HashSet<Long>();
489      row_set.add(dmp.diff_footprint(1, 1));
490      row_set.add(dmp.diff_footprint(2, 0));
491      row_set.add(dmp.diff_footprint(2, 4));
492      v_map.add(row_set);
493      row_set = new HashSet<Long>();
494      row_set.add(dmp.diff_footprint(2, 1));
495      row_set.add(dmp.diff_footprint(2, 5));
496      row_set.add(dmp.diff_footprint(3, 0));
497      row_set.add(dmp.diff_footprint(3, 4));
498      v_map.add(row_set);
499      row_set = new HashSet<Long>();
500      row_set.add(dmp.diff_footprint(2, 6));
501      row_set.add(dmp.diff_footprint(3, 5));
502      row_set.add(dmp.diff_footprint(4, 4));
503      v_map.add(row_set);
504    }
505    diffs = diffList(new Diff(DELETE, "CD"), new Diff(EQUAL, "34"), new Diff(INSERT, "YZ"));
506    assertEquals("diff_path2: Double letters.", diffs, dmp.diff_path2(v_map, "CD34", "34YZ"));
507  }
508
509  public void testDiffMain() {
510    // Perform a trivial diff.
511    LinkedList<Diff> diffs = diffList(new Diff(EQUAL, "abc"));
512    assertEquals("diff_main: Null case.", diffs, dmp.diff_main("abc", "abc", false));
513
514    diffs = diffList(new Diff(EQUAL, "ab"), new Diff(INSERT, "123"), new Diff(EQUAL, "c"));
515    assertEquals("diff_main: Simple insertion.", diffs, dmp.diff_main("abc", "ab123c", false));
516
517    diffs = diffList(new Diff(EQUAL, "a"), new Diff(DELETE, "123"), new Diff(EQUAL, "bc"));
518    assertEquals("diff_main: Simple deletion.", diffs, dmp.diff_main("a123bc", "abc", false));
519
520    diffs = diffList(new Diff(EQUAL, "a"), new Diff(INSERT, "123"), new Diff(EQUAL, "b"), new Diff(INSERT, "456"), new Diff(EQUAL, "c"));
521    assertEquals("diff_main: Two insertions.", diffs, dmp.diff_main("abc", "a123b456c", false));
522
523    diffs = diffList(new Diff(EQUAL, "a"), new Diff(DELETE, "123"), new Diff(EQUAL, "b"), new Diff(DELETE, "456"), new Diff(EQUAL, "c"));
524    assertEquals("diff_main: Two deletions.", diffs, dmp.diff_main("a123b456c", "abc", false));
525
526    // Perform a real diff.
527    // Switch off the timeout.
528    dmp.Diff_Timeout = 0;
529    dmp.Diff_DualThreshold = 32;
530    diffs = diffList(new Diff(DELETE, "a"), new Diff(INSERT, "b"));
531    assertEquals("diff_main: Simple case #1.", diffs, dmp.diff_main("a", "b", false));
532
533    diffs = diffList(new Diff(DELETE, "Apple"), new Diff(INSERT, "Banana"), new Diff(EQUAL, "s are a"), new Diff(INSERT, "lso"), new Diff(EQUAL, " fruit."));
534    assertEquals("diff_main: Simple case #2.", diffs, dmp.diff_main("Apples are a fruit.", "Bananas are also fruit.", false));
535
536    diffs = diffList(new Diff(DELETE, "a"), new Diff(INSERT, "\u0680"), new Diff(EQUAL, "x"), new Diff(DELETE, "\t"), new Diff(INSERT, "\000"));
537    assertEquals("diff_main: Simple case #3.", diffs, dmp.diff_main("ax\t", "\u0680x\000", false));
538
539    diffs = diffList(new Diff(DELETE, "1"), new Diff(EQUAL, "a"), new Diff(DELETE, "y"), new Diff(EQUAL, "b"), new Diff(DELETE, "2"), new Diff(INSERT, "xab"));
540    assertEquals("diff_main: Overlap #1.", diffs, dmp.diff_main("1ayb2", "abxab", false));
541
542    diffs = diffList(new Diff(INSERT, "xaxcx"), new Diff(EQUAL, "abc"), new Diff(DELETE, "y"));
543    assertEquals("diff_main: Overlap #2.", diffs, dmp.diff_main("abcy", "xaxcxabc", false));
544
545    // Sub-optimal double-ended diff.
546    dmp.Diff_DualThreshold = 2;
547    diffs = diffList(new Diff(INSERT, "x"), new Diff(EQUAL, "a"), new Diff(DELETE, "b"), new Diff(INSERT, "x"), new Diff(EQUAL, "c"), new Diff(DELETE, "y"), new Diff(INSERT, "xabc"));
548    assertEquals("diff_main: Overlap #3.", diffs, dmp.diff_main("abcy", "xaxcxabc", false));
549
550    dmp.Diff_DualThreshold = 32;
551    dmp.Diff_Timeout = 0.001f;  // 1ms
552    String a = "`Twas brillig, and the slithy toves\nDid gyre and gimble in the wabe:\nAll mimsy were the borogoves,\nAnd the mome raths outgrabe.\n";
553    String b = "I am the very model of a modern major general,\nI've information vegetable, animal, and mineral,\nI know the kings of England, and I quote the fights historical,\nFrom Marathon to Waterloo, in order categorical.\n";
554    // Increase the text lengths by 1024 times to ensure a timeout.
555    for (int x = 0; x < 10; x++) {
556      a = a + a;
557      b = b + b;
558    }
559    assertNull("diff_main: Timeout.", dmp.diff_map(a, b));
560    dmp.Diff_Timeout = 0;
561
562    // Test the linemode speedup.
563    // Must be long to pass the 200 char cutoff.
564    a = "1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n";
565    b = "abcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\n";
566    assertEquals("diff_main: Simple.", dmp.diff_main(a, b, true), dmp.diff_main(a, b, false));
567
568    a = "1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n";
569    b = "abcdefghij\n1234567890\n1234567890\n1234567890\nabcdefghij\n1234567890\n1234567890\n1234567890\nabcdefghij\n1234567890\n1234567890\n1234567890\nabcdefghij\n";
570    String[] texts_linemode = diff_rebuildtexts(dmp.diff_main(a, b, true));
571    String[] texts_textmode = diff_rebuildtexts(dmp.diff_main(a, b, false));
572    assertArrayEquals("diff_main: Overlap.", texts_textmode, texts_linemode);
573
574    // Test null inputs.
575    try {
576      dmp.diff_main(null, null);
577      fail("diff_main: Null inputs.");
578    } catch (IllegalArgumentException ex) {
579      // Error expected.
580    }
581  }
582
583
584  //  MATCH TEST FUNCTIONS
585
586
587  public void testMatchAlphabet() {
588    // Initialise the bitmasks for Bitap.
589    Map<Character, Integer> bitmask;
590    bitmask = new HashMap<Character, Integer>();
591    bitmask.put('a', 4); bitmask.put('b', 2); bitmask.put('c', 1);
592    assertEquals("match_alphabet: Unique.", bitmask, dmp.match_alphabet("abc"));
593
594    bitmask = new HashMap<Character, Integer>();
595    bitmask.put('a', 37); bitmask.put('b', 18); bitmask.put('c', 8);
596    assertEquals("match_alphabet: Duplicates.", bitmask, dmp.match_alphabet("abcaba"));
597  }
598
599  public void testMatchBitap() {
600    // Bitap algorithm.
601    dmp.Match_Distance = 100;
602    dmp.Match_Threshold = 0.5f;
603    assertEquals("match_bitap: Exact match #1.", 5, dmp.match_bitap("abcdefghijk", "fgh", 5));
604
605    assertEquals("match_bitap: Exact match #2.", 5, dmp.match_bitap("abcdefghijk", "fgh", 0));
606
607    assertEquals("match_bitap: Fuzzy match #1.", 4, dmp.match_bitap("abcdefghijk", "efxhi", 0));
608
609    assertEquals("match_bitap: Fuzzy match #2.", 2, dmp.match_bitap("abcdefghijk", "cdefxyhijk", 5));
610
611    assertEquals("match_bitap: Fuzzy match #3.", -1, dmp.match_bitap("abcdefghijk", "bxy", 1));
612
613    assertEquals("match_bitap: Overflow.", 2, dmp.match_bitap("123456789xx0", "3456789x0", 2));
614
615    assertEquals("match_bitap: Before start match.", 0, dmp.match_bitap("abcdef", "xxabc", 4));
616
617    assertEquals("match_bitap: Beyond end match.", 3, dmp.match_bitap("abcdef", "defyy", 4));
618
619    assertEquals("match_bitap: Oversized pattern.", 0, dmp.match_bitap("abcdef", "xabcdefy", 0));
620
621    dmp.Match_Threshold = 0.4f;
622    assertEquals("match_bitap: Threshold #1.", 4, dmp.match_bitap("abcdefghijk", "efxyhi", 1));
623
624    dmp.Match_Threshold = 0.3f;
625    assertEquals("match_bitap: Threshold #2.", -1, dmp.match_bitap("abcdefghijk", "efxyhi", 1));
626
627    dmp.Match_Threshold = 0.0f;
628    assertEquals("match_bitap: Threshold #3.", 1, dmp.match_bitap("abcdefghijk", "bcdef", 1));
629
630    dmp.Match_Threshold = 0.5f;
631    assertEquals("match_bitap: Multiple select #1.", 0, dmp.match_bitap("abcdexyzabcde", "abccde", 3));
632
633    assertEquals("match_bitap: Multiple select #2.", 8, dmp.match_bitap("abcdexyzabcde", "abccde", 5));
634
635    dmp.Match_Distance = 10;  // Strict location.
636    assertEquals("match_bitap: Distance test #1.", -1, dmp.match_bitap("abcdefghijklmnopqrstuvwxyz", "abcdefg", 24));
637
638    assertEquals("match_bitap: Distance test #2.", 0, dmp.match_bitap("abcdefghijklmnopqrstuvwxyz", "abcdxxefg", 1));
639
640    dmp.Match_Distance = 1000;  // Loose location.
641    assertEquals("match_bitap: Distance test #3.", 0, dmp.match_bitap("abcdefghijklmnopqrstuvwxyz", "abcdefg", 24));
642  }
643
644  public void testMatchMain() {
645    // Full match.
646    assertEquals("match_main: Equality.", 0, dmp.match_main("abcdef", "abcdef", 1000));
647
648    assertEquals("match_main: Null text.", -1, dmp.match_main("", "abcdef", 1));
649
650    assertEquals("match_main: Null pattern.", 3, dmp.match_main("abcdef", "", 3));
651
652    assertEquals("match_main: Exact match.", 3, dmp.match_main("abcdef", "de", 3));
653
654    assertEquals("match_main: Beyond end match.", 3, dmp.match_main("abcdef", "defy", 4));
655
656    assertEquals("match_main: Oversized pattern.", 0, dmp.match_main("abcdef", "abcdefy", 0));
657
658    dmp.Match_Threshold = 0.7f;
659    assertEquals("match_main: Complex match.", 4, dmp.match_main("I am the very model of a modern major general.", " that berry ", 5));
660    dmp.Match_Threshold = 0.5f;
661
662    // Test null inputs.
663    try {
664      dmp.match_main(null, null, 0);
665      fail("match_main: Null inputs.");
666    } catch (IllegalArgumentException ex) {
667      // Error expected.
668    }
669  }
670
671
672  //  PATCH TEST FUNCTIONS
673
674
675  public void testPatchObj() {
676    // Patch Object.
677    Patch p = new Patch();
678    p.start1 = 20;
679    p.start2 = 21;
680    p.length1 = 18;
681    p.length2 = 17;
682    p.diffs = diffList(new Diff(EQUAL, "jump"), new Diff(DELETE, "s"), new Diff(INSERT, "ed"), new Diff(EQUAL, " over "), new Diff(DELETE, "the"), new Diff(INSERT, "a"), new Diff(EQUAL, "\nlaz"));
683    String strp = "@@ -21,18 +22,17 @@\n jump\n-s\n+ed\n  over \n-the\n+a\n %0Alaz\n";
684    assertEquals("Patch: toString.", strp, p.toString());
685  }
686
687  public void testPatchFromText() {
688    assertTrue("patch_fromText: #0.", dmp.patch_fromText("").isEmpty());
689
690    String strp = "@@ -21,18 +22,17 @@\n jump\n-s\n+ed\n  over \n-the\n+a\n %0Alaz\n";
691    assertEquals("patch_fromText: #1.", strp, dmp.patch_fromText(strp).get(0).toString());
692
693    assertEquals("patch_fromText: #2.", "@@ -1 +1 @@\n-a\n+b\n", dmp.patch_fromText("@@ -1 +1 @@\n-a\n+b\n").get(0).toString());
694
695    assertEquals("patch_fromText: #3.", "@@ -1,3 +0,0 @@\n-abc\n", dmp.patch_fromText("@@ -1,3 +0,0 @@\n-abc\n").get(0).toString());
696
697    assertEquals("patch_fromText: #4.", "@@ -0,0 +1,3 @@\n+abc\n", dmp.patch_fromText("@@ -0,0 +1,3 @@\n+abc\n").get(0).toString());
698
699    // Generates error.
700    try {
701      dmp.patch_fromText("Bad\nPatch\n");
702      fail("patch_fromText: #5.");
703    } catch (IllegalArgumentException ex) {
704      // Exception expected.
705    }
706  }
707
708  public void testPatchToText() {
709    String strp = "@@ -21,18 +22,17 @@\n jump\n-s\n+ed\n  over \n-the\n+a\n  laz\n";
710    List<Patch> patches;
711    patches = dmp.patch_fromText(strp);
712    assertEquals("patch_toText: Single", strp, dmp.patch_toText(patches));
713
714    strp = "@@ -1,9 +1,9 @@\n-f\n+F\n oo+fooba\n@@ -7,9 +7,9 @@\n obar\n-,\n+.\n  tes\n";
715    patches = dmp.patch_fromText(strp);
716    assertEquals("patch_toText: Dual", strp, dmp.patch_toText(patches));
717  }
718
719  public void testPatchAddContext() {
720    dmp.Patch_Margin = 4;
721    Patch p;
722    p = dmp.patch_fromText("@@ -21,4 +21,10 @@\n-jump\n+somersault\n").get(0);
723    dmp.patch_addContext(p, "The quick brown fox jumps over the lazy dog.");
724    assertEquals("patch_addContext: Simple case.", "@@ -17,12 +17,18 @@\n fox \n-jump\n+somersault\n s ov\n", p.toString());
725
726    p = dmp.patch_fromText("@@ -21,4 +21,10 @@\n-jump\n+somersault\n").get(0);
727    dmp.patch_addContext(p, "The quick brown fox jumps.");
728    assertEquals("patch_addContext: Not enough trailing context.", "@@ -17,10 +17,16 @@\n fox \n-jump\n+somersault\n s.\n", p.toString());
729
730    p = dmp.patch_fromText("@@ -3 +3,2 @@\n-e\n+at\n").get(0);
731    dmp.patch_addContext(p, "The quick brown fox jumps.");
732    assertEquals("patch_addContext: Not enough leading context.", "@@ -1,7 +1,8 @@\n Th\n-e\n+at\n  qui\n", p.toString());
733
734    p = dmp.patch_fromText("@@ -3 +3,2 @@\n-e\n+at\n").get(0);
735    dmp.patch_addContext(p, "The quick brown fox jumps.  The quick brown fox crashes.");
736    assertEquals("patch_addContext: Ambiguity.", "@@ -1,27 +1,28 @@\n Th\n-e\n+at\n  quick brown fox jumps. \n", p.toString());
737  }
738
739  @SuppressWarnings("deprecation")
740  public void testPatchMake() {
741    LinkedList<Patch> patches;
742    String text1 = "The quick brown fox jumps over the lazy dog.";
743    String text2 = "That quick brown fox jumped over a lazy dog.";
744    String expectedPatch = "@@ -1,8 +1,7 @@\n Th\n-at\n+e\n  qui\n@@ -21,17 +21,18 @@\n jump\n-ed\n+s\n  over \n-a\n+the\n  laz\n";
745    // The second patch must be "-21,17 +21,18", not "-22,17 +21,18" due to rolling context.
746    patches = dmp.patch_make(text2, text1);
747    assertEquals("patch_make: Text2+Text1 inputs", expectedPatch, dmp.patch_toText(patches));
748
749    expectedPatch = "@@ -1,11 +1,12 @@\n Th\n-e\n+at\n  quick b\n@@ -22,18 +22,17 @@\n jump\n-s\n+ed\n  over \n-the\n+a\n  laz\n";
750    patches = dmp.patch_make(text1, text2);
751    assertEquals("patch_make: Text1+Text2 inputs", expectedPatch, dmp.patch_toText(patches));
752
753    LinkedList<Diff> diffs = dmp.diff_main(text1, text2, false);
754    patches = dmp.patch_make(diffs);
755    assertEquals("patch_make: Diff input", expectedPatch, dmp.patch_toText(patches));
756
757    patches = dmp.patch_make(text1, diffs);
758    assertEquals("patch_make: Text1+Diff inputs", expectedPatch, dmp.patch_toText(patches));
759
760    patches = dmp.patch_make(text1, text2, diffs);
761    assertEquals("patch_make: Text1+Text2+Diff inputs (deprecated)", expectedPatch, dmp.patch_toText(patches));
762
763    patches = dmp.patch_make("`1234567890-=[]\\;',./", "~!@#$%^&*()_+{}|:\"<>?");
764    assertEquals("patch_toText: Character encoding.", "@@ -1,21 +1,21 @@\n-%601234567890-=%5B%5D%5C;',./\n+~!@#$%25%5E&*()_+%7B%7D%7C:%22%3C%3E?\n", dmp.patch_toText(patches));
765
766    diffs = diffList(new Diff(DELETE, "`1234567890-=[]\\;',./"), new Diff(INSERT, "~!@#$%^&*()_+{}|:\"<>?"));
767    assertEquals("patch_fromText: Character decoding.", diffs, dmp.patch_fromText("@@ -1,21 +1,21 @@\n-%601234567890-=%5B%5D%5C;',./\n+~!@#$%25%5E&*()_+%7B%7D%7C:%22%3C%3E?\n").get(0).diffs);
768
769    text1 = "";
770    for (int x = 0; x < 100; x++) {
771      text1 += "abcdef";
772    }
773    text2 = text1 + "123";
774    expectedPatch = "@@ -573,28 +573,31 @@\n cdefabcdefabcdefabcdefabcdef\n+123\n";
775    patches = dmp.patch_make(text1, text2);
776    assertEquals("patch_make: Long string with repeats.", expectedPatch, dmp.patch_toText(patches));
777
778    // Test null inputs.
779    try {
780      dmp.patch_make(null);
781      fail("patch_make: Null inputs.");
782    } catch (IllegalArgumentException ex) {
783      // Error expected.
784    }
785  }
786
787  public void testPatchSplitMax() {
788    // Assumes that Match_MaxBits is 32.
789    LinkedList<Patch> patches;
790    patches = dmp.patch_make("abcdefghijklmnopqrstuvwxyz01234567890", "XabXcdXefXghXijXklXmnXopXqrXstXuvXwxXyzX01X23X45X67X89X0");
791    dmp.patch_splitMax(patches);
792    assertEquals("patch_splitMax: #1.", "@@ -1,32 +1,46 @@\n+X\n ab\n+X\n cd\n+X\n ef\n+X\n gh\n+X\n ij\n+X\n kl\n+X\n mn\n+X\n op\n+X\n qr\n+X\n st\n+X\n uv\n+X\n wx\n+X\n yz\n+X\n 012345\n@@ -25,13 +39,18 @@\n zX01\n+X\n 23\n+X\n 45\n+X\n 67\n+X\n 89\n+X\n 0\n", dmp.patch_toText(patches));
793
794    patches = dmp.patch_make("abcdef1234567890123456789012345678901234567890123456789012345678901234567890uvwxyz", "abcdefuvwxyz");
795    String oldToText = dmp.patch_toText(patches);
796    dmp.patch_splitMax(patches);
797    assertEquals("patch_splitMax: #2.", oldToText, dmp.patch_toText(patches));
798
799    patches = dmp.patch_make("1234567890123456789012345678901234567890123456789012345678901234567890", "abc");
800    dmp.patch_splitMax(patches);
801    assertEquals("patch_splitMax: #3.", "@@ -1,32 +1,4 @@\n-1234567890123456789012345678\n 9012\n@@ -29,32 +1,4 @@\n-9012345678901234567890123456\n 7890\n@@ -57,14 +1,3 @@\n-78901234567890\n+abc\n", dmp.patch_toText(patches));
802
803    patches = dmp.patch_make("abcdefghij , h : 0 , t : 1 abcdefghij , h : 0 , t : 1 abcdefghij , h : 0 , t : 1", "abcdefghij , h : 1 , t : 1 abcdefghij , h : 1 , t : 1 abcdefghij , h : 0 , t : 1");
804    dmp.patch_splitMax(patches);
805    assertEquals("patch_splitMax: #4.", "@@ -2,32 +2,32 @@\n bcdefghij , h : \n-0\n+1\n  , t : 1 abcdef\n@@ -29,32 +29,32 @@\n bcdefghij , h : \n-0\n+1\n  , t : 1 abcdef\n", dmp.patch_toText(patches));
806  }
807
808  public void testPatchAddPadding() {
809    LinkedList<Patch> patches;
810    patches = dmp.patch_make("", "test");
811    assertEquals("patch_addPadding: Both edges full.", "@@ -0,0 +1,4 @@\n+test\n", dmp.patch_toText(patches));
812    dmp.patch_addPadding(patches);
813    assertEquals("patch_addPadding: Both edges full.", "@@ -1,8 +1,12 @@\n %01%02%03%04\n+test\n %01%02%03%04\n", dmp.patch_toText(patches));
814
815    patches = dmp.patch_make("XY", "XtestY");
816    assertEquals("patch_addPadding: Both edges partial.", "@@ -1,2 +1,6 @@\n X\n+test\n Y\n", dmp.patch_toText(patches));
817    dmp.patch_addPadding(patches);
818    assertEquals("patch_addPadding: Both edges partial.", "@@ -2,8 +2,12 @@\n %02%03%04X\n+test\n Y%01%02%03\n", dmp.patch_toText(patches));
819
820    patches = dmp.patch_make("XXXXYYYY", "XXXXtestYYYY");
821    assertEquals("patch_addPadding: Both edges none.", "@@ -1,8 +1,12 @@\n XXXX\n+test\n YYYY\n", dmp.patch_toText(patches));
822    dmp.patch_addPadding(patches);
823    assertEquals("patch_addPadding: Both edges none.", "@@ -5,8 +5,12 @@\n XXXX\n+test\n YYYY\n", dmp.patch_toText(patches));
824  }
825
826  public void testPatchApply() {
827    dmp.Match_Distance = 1000;
828    dmp.Match_Threshold = 0.5f;
829    dmp.Patch_DeleteThreshold = 0.5f;
830    LinkedList<Patch> patches;
831    patches = dmp.patch_make("The quick brown fox jumps over the lazy dog.", "That quick brown fox jumped over a lazy dog.");
832    Object[] results = dmp.patch_apply(patches, "The quick brown fox jumps over the lazy dog.");
833    boolean[] boolArray = (boolean[]) results[1];
834    String resultStr = results[0] + "\t" + boolArray[0] + "\t" + boolArray[1];
835    assertEquals("patch_apply: Exact match.", "That quick brown fox jumped over a lazy dog.\ttrue\ttrue", resultStr);
836
837    results = dmp.patch_apply(patches, "The quick red rabbit jumps over the tired tiger.");
838    boolArray = (boolean[]) results[1];
839    resultStr = results[0] + "\t" + boolArray[0] + "\t" + boolArray[1];
840    assertEquals("patch_apply: Partial match.", "That quick red rabbit jumped over a tired tiger.\ttrue\ttrue", resultStr);
841
842    results = dmp.patch_apply(patches, "I am the very model of a modern major general.");
843    boolArray = (boolean[]) results[1];
844    resultStr = results[0] + "\t" + boolArray[0] + "\t" + boolArray[1];
845    assertEquals("patch_apply: Failed match.", "I am the very model of a modern major general.\tfalse\tfalse", resultStr);
846
847    patches = dmp.patch_make("x1234567890123456789012345678901234567890123456789012345678901234567890y", "xabcy");
848    results = dmp.patch_apply(patches, "x123456789012345678901234567890-----++++++++++-----123456789012345678901234567890y");
849    boolArray = (boolean[]) results[1];
850    resultStr = results[0] + "\t" + boolArray[0] + "\t" + boolArray[1];
851    assertEquals("patch_apply: Big delete, small change.", "xabcy\ttrue\ttrue", resultStr);
852
853    patches = dmp.patch_make("x1234567890123456789012345678901234567890123456789012345678901234567890y", "xabcy");
854    results = dmp.patch_apply(patches, "x12345678901234567890---------------++++++++++---------------12345678901234567890y");
855    boolArray = (boolean[]) results[1];
856    resultStr = results[0] + "\t" + boolArray[0] + "\t" + boolArray[1];
857    assertEquals("patch_apply: Big delete, big change 1.", "xabc12345678901234567890---------------++++++++++---------------12345678901234567890y\tfalse\ttrue", resultStr);
858
859    dmp.Patch_DeleteThreshold = 0.6f;
860    patches = dmp.patch_make("x1234567890123456789012345678901234567890123456789012345678901234567890y", "xabcy");
861    results = dmp.patch_apply(patches, "x12345678901234567890---------------++++++++++---------------12345678901234567890y");
862    boolArray = (boolean[]) results[1];
863    resultStr = results[0] + "\t" + boolArray[0] + "\t" + boolArray[1];
864    assertEquals("patch_apply: Big delete, big change 2.", "xabcy\ttrue\ttrue", resultStr);
865    dmp.Patch_DeleteThreshold = 0.5f;
866
867    // Compensate for failed patch.
868    dmp.Match_Threshold = 0.0f;
869    dmp.Match_Distance = 0;
870    patches = dmp.patch_make("abcdefghijklmnopqrstuvwxyz--------------------1234567890", "abcXXXXXXXXXXdefghijklmnopqrstuvwxyz--------------------1234567YYYYYYYYYY890");
871    results = dmp.patch_apply(patches, "ABCDEFGHIJKLMNOPQRSTUVWXYZ--------------------1234567890");
872    boolArray = (boolean[]) results[1];
873    resultStr = results[0] + "\t" + boolArray[0] + "\t" + boolArray[1];
874    assertEquals("ABCDEFGHIJKLMNOPQRSTUVWXYZ--------------------1234567YYYYYYYYYY890\tfalse\ttrue", resultStr);
875    dmp.Match_Threshold = 0.5f;
876    dmp.Match_Distance = 1000;
877
878    patches = dmp.patch_make("", "test");
879    String patchStr = dmp.patch_toText(patches);
880    dmp.patch_apply(patches, "");
881    assertEquals("patch_apply: No side effects.", patchStr, dmp.patch_toText(patches));
882
883    patches = dmp.patch_make("The quick brown fox jumps over the lazy dog.", "Woof");
884    patchStr = dmp.patch_toText(patches);
885    dmp.patch_apply(patches, "The quick brown fox jumps over the lazy dog.");
886    assertEquals("patch_apply: No side effects with major delete.", patchStr, dmp.patch_toText(patches));
887
888    patches = dmp.patch_make("", "test");
889    results = dmp.patch_apply(patches, "");
890    boolArray = (boolean[]) results[1];
891    resultStr = results[0] + "\t" + boolArray[0];
892    assertEquals("patch_apply: Edge exact match.", "test\ttrue", resultStr);
893
894    patches = dmp.patch_make("XY", "XtestY");
895    results = dmp.patch_apply(patches, "XY");
896    boolArray = (boolean[]) results[1];
897    resultStr = results[0] + "\t" + boolArray[0];
898    assertEquals("patch_apply: Near edge exact match.", "XtestY\ttrue", resultStr);
899
900    patches = dmp.patch_make("y", "y123");
901    results = dmp.patch_apply(patches, "x");
902    boolArray = (boolean[]) results[1];
903    resultStr = results[0] + "\t" + boolArray[0];
904    assertEquals("patch_apply: Edge partial match.", "x123\ttrue", resultStr);
905  }
906
907
908  private void assertArrayEquals(String error_msg, Object[] a, Object[] b) {
909    List<Object> list_a = Arrays.asList(a);
910    List<Object> list_b = Arrays.asList(b);
911    assertEquals(error_msg, list_a, list_b);
912  }
913
914
915  private void assertLinesToCharsResultEquals(String error_msg,
916      LinesToCharsResult a, LinesToCharsResult b) {
917    assertEquals(error_msg, a.chars1, b.chars1);
918    assertEquals(error_msg, a.chars2, b.chars2);
919    assertEquals(error_msg, a.lineArray, b.lineArray);
920  }
921
922  // Construct the two texts which made up the diff originally.
923  private static String[] diff_rebuildtexts(LinkedList<Diff> diffs) {
924    String[] text = {"", ""};
925    for (Diff myDiff : diffs) {
926      if (myDiff.operation != diff_match_patch.Operation.INSERT) {
927        text[0] += myDiff.text;
928      }
929      if (myDiff.operation != diff_match_patch.Operation.DELETE) {
930        text[1] += myDiff.text;
931      }
932    }
933    return text;
934  }
935
936
937  // Private function for quickly building lists of diffs.
938  private static LinkedList<Diff> diffList(Diff... diffs) {
939    LinkedList<Diff> myDiffList = new LinkedList<Diff>();
940    for (Diff myDiff : diffs) {
941      myDiffList.add(myDiff);
942    }
943    return myDiffList;
944  }
945}
946