Maksymilian Osowski | ed79165 | 2010-07-26 17:00:30 +0100 | [diff] [blame] | 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¶<BR></SPAN><DEL STYLE=\"background:#FFE6E6;\" TITLE=\"i=2\"><B>b</B></DEL><INS STYLE=\"background:#E6FFE6;\" TITLE=\"i=2\">c&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 | } |