Home | History | Annotate | Download | only in plaintext
      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 
     20 package name.fraser.neil.plaintext;
     21 
     22 import junit.framework.TestCase;
     23 
     24 import java.util.ArrayList;
     25 import java.util.Arrays;
     26 import java.util.HashMap;
     27 import java.util.HashSet;
     28 import java.util.LinkedList;
     29 import java.util.List;
     30 import java.util.Map;
     31 import java.util.Set;
     32 
     33 import name.fraser.neil.plaintext.diff_match_patch.Diff;
     34 import name.fraser.neil.plaintext.diff_match_patch.LinesToCharsResult;
     35 import name.fraser.neil.plaintext.diff_match_patch.Patch;
     36 
     37 public 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