1 /*
2 * Copyright 2008 Google Inc. All Rights Reserved.
3 * Author: fraser@google.com (Neil Fraser)
4 * Author: mikeslemmer@gmail.com (Mike Slemmer)
5 *
6 * Licensed under the Apache License, Version 2.0 (the "License");
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 *
18 * Diff Match and Patch -- Test Harness
19 * http://code.google.com/p/google-diff-match-patch/
20 */
21
22 // Code known to compile and run with Qt 4.3.3 and Qt 4.4.0.
23 #include <QtCore>
24 #include "diff_match_patch.h"
25 #include "diff_match_patch_test.h"
26
main(int argc,char ** argv)27 int main(int argc, char **argv) {
28 diff_match_patch_test dmp_test;
29 qDebug("Starting diff_match_patch unit tests.");
30 dmp_test.run_all_tests();
31 qDebug("Done.");
32 return 0;
33 Q_UNUSED(argc)
34 Q_UNUSED(argv)
35 }
36
37
diff_match_patch_test()38 diff_match_patch_test::diff_match_patch_test() {
39 }
40
run_all_tests()41 void diff_match_patch_test::run_all_tests() {
42 QTime t;
43 t.start();
44 try {
45 testDiffCommonPrefix();
46 testDiffCommonSuffix();
47 testDiffHalfmatch();
48 testDiffLinesToChars();
49 testDiffCharsToLines();
50 testDiffCleanupMerge();
51 testDiffCleanupSemanticLossless();
52 testDiffCleanupSemantic();
53 testDiffCleanupEfficiency();
54 testDiffPrettyHtml();
55 testDiffText();
56 testDiffDelta();
57 testDiffXIndex();
58 testDiffPath();
59 testDiffMain();
60 testMatchAlphabet();
61 testMatchBitap();
62 testMatchMain();
63 testPatchObj();
64 testPatchFromText();
65 testPatchToText();
66 testPatchAddContext();
67 testPatchMake();
68 testPatchSplitMax();
69 testPatchAddPadding();
70 testPatchApply();
71 qDebug("All tests passed.");
72 } catch (QString strCase) {
73 qDebug(qPrintable(QString("Test failed: %1").arg(strCase)));
74 }
75 qDebug("Total time: %d ms", t.elapsed());
76 }
77
78 // DIFF TEST FUNCTIONS
79
testDiffCommonPrefix()80 void diff_match_patch_test::testDiffCommonPrefix() {
81 // Detect and remove any common prefix.
82 assertEquals("diff_commonPrefix: Null case.", 0, dmp.diff_commonPrefix("abc", "xyz"));
83
84 assertEquals("diff_commonPrefix: Non-null case.", 4, dmp.diff_commonPrefix("1234abcdef", "1234xyz"));
85
86 assertEquals("diff_commonPrefix: Whole case.", 4, dmp.diff_commonPrefix("1234", "1234xyz"));
87 }
88
testDiffCommonSuffix()89 void diff_match_patch_test::testDiffCommonSuffix() {
90 // Detect and remove any common suffix.
91 assertEquals("diff_commonSuffix: Null case.", 0, dmp.diff_commonSuffix("abc", "xyz"));
92
93 assertEquals("diff_commonSuffix: Non-null case.", 4, dmp.diff_commonSuffix("abcdef1234", "xyz1234"));
94
95 assertEquals("diff_commonSuffix: Whole case.", 4, dmp.diff_commonSuffix("1234", "xyz1234"));
96 }
97
testDiffHalfmatch()98 void diff_match_patch_test::testDiffHalfmatch() {
99 // Detect a halfmatch.
100 assertNull("diff_halfMatch: No match.", dmp.diff_halfMatch("1234567890", "abcdef"));
101
102 assertEquals("diff_halfMatch: Single Match #1.", QString("12,90,a,z,345678").split(","), dmp.diff_halfMatch("1234567890", "a345678z"));
103
104 assertEquals("diff_halfMatch: Single Match #2.", QString("a,z,12,90,345678").split(","), dmp.diff_halfMatch("a345678z", "1234567890"));
105
106 assertEquals("diff_halfMatch: Multiple Matches #1.", QString("12123,123121,a,z,1234123451234").split(","), dmp.diff_halfMatch("121231234123451234123121", "a1234123451234z"));
107
108 assertEquals("diff_halfMatch: Multiple Matches #2.", QString(",-=-=-=-=-=,x,,x-=-=-=-=-=-=-=").split(","), dmp.diff_halfMatch("x-=-=-=-=-=-=-=-=-=-=-=-=", "xx-=-=-=-=-=-=-="));
109
110 assertEquals("diff_halfMatch: Multiple Matches #3.", QString("-=-=-=-=-=,,,y,-=-=-=-=-=-=-=y").split(","), dmp.diff_halfMatch("-=-=-=-=-=-=-=-=-=-=-=-=y", "-=-=-=-=-=-=-=yy"));
111 }
112
testDiffLinesToChars()113 void diff_match_patch_test::testDiffLinesToChars() {
114 // Convert lines down to characters.
115 QStringList tmpVector;
116 QList<QVariant> tmpVarList;
117 tmpVector.append("");
118 tmpVector.append("alpha\n");
119 tmpVector.append("beta\n");
120 tmpVarList << QVariant::fromValue(QString() + QChar((ushort)1) + QChar((ushort)2) + QChar((ushort)1)); //(("\u0001\u0002\u0001"));
121 tmpVarList << QVariant::fromValue(QString() + QChar((ushort)2) + QChar((ushort)1) + QChar((ushort)2)); // (("\u0002\u0001\u0002"));
122 tmpVarList << QVariant::fromValue(tmpVector);
123 assertEquals("diff_linesToChars:", tmpVarList, dmp.diff_linesToChars("alpha\nbeta\nalpha\n", "beta\nalpha\nbeta\n"));
124
125 tmpVector.clear();
126 tmpVarList.clear();
127 tmpVector.append("");
128 tmpVector.append("alpha\r\n");
129 tmpVector.append("beta\r\n");
130 tmpVector.append("\r\n");
131 tmpVarList << QVariant::fromValue(QString(""));
132 tmpVarList << QVariant::fromValue(QString() + QChar((ushort)1) + QChar((ushort)2) + QChar((ushort)3) + QChar((ushort)3)); // (("\u0001\u0002\u0003\u0003"));
133 tmpVarList << QVariant::fromValue(tmpVector);
134 assertEquals("diff_linesToChars:", tmpVarList, dmp.diff_linesToChars("", "alpha\r\nbeta\r\n\r\n\r\n"));
135
136 tmpVector.clear();
137 tmpVarList.clear();
138 tmpVector.append("");
139 tmpVector.append("a");
140 tmpVector.append("b");
141 tmpVarList << QVariant::fromValue(QString() + QChar((ushort)1)); // (("\u0001"));
142 tmpVarList << QVariant::fromValue(QString() + QChar((ushort)2)); // (("\u0002"));
143 tmpVarList << QVariant::fromValue(tmpVector);
144 assertEquals("diff_linesToChars:", tmpVarList, dmp.diff_linesToChars("a", "b"));
145
146 // More than 256 to reveal any 8-bit limitations.
147 int n = 300;
148 tmpVector.clear();
149 tmpVarList.clear();
150 QString lines;
151 QString chars;
152 for (int x = 1; x < n + 1; x++) {
153 tmpVector.append(QString::number(x) + "\n");
154 lines += QString::number(x) + "\n";
155 chars += QChar(static_cast<ushort>(x));
156 }
157 assertEquals("diff_linesToChars: More than 256 (setup).", n, tmpVector.size());
158 assertEquals("diff_linesToChars: More than 256 (setup).", n, chars.length());
159 tmpVector.prepend("");
160 tmpVarList << QVariant::fromValue(chars);
161 tmpVarList << QVariant::fromValue(QString(""));
162 tmpVarList << QVariant::fromValue(tmpVector);
163 assertEquals("diff_linesToChars: More than 256.", tmpVarList, dmp.diff_linesToChars(lines, ""));
164 }
165
testDiffCharsToLines()166 void diff_match_patch_test::testDiffCharsToLines() {
167 // First check that Diff equality works.
168 assertTrue("diff_charsToLines:", Diff(EQUAL, "a") == Diff(EQUAL, "a"));
169
170 assertEquals("diff_charsToLines:", Diff(EQUAL, "a"), Diff(EQUAL, "a"));
171
172 // Convert chars up to lines.
173 QList<Diff> diffs;
174 diffs << Diff(EQUAL, QString() + QChar((ushort)1) + QChar((ushort)2) + QChar((ushort)1)); // ("\u0001\u0002\u0001");
175 diffs << Diff(INSERT, QString() + QChar((ushort)2) + QChar((ushort)1) + QChar((ushort)2)); // ("\u0002\u0001\u0002");
176 QStringList tmpVector;
177 tmpVector.append("");
178 tmpVector.append("alpha\n");
179 tmpVector.append("beta\n");
180 dmp.diff_charsToLines(diffs, tmpVector);
181 assertEquals("diff_charsToLines:", diffList(Diff(EQUAL, "alpha\nbeta\nalpha\n"), Diff(INSERT, "beta\nalpha\nbeta\n")), diffs);
182
183 // More than 256 to reveal any 8-bit limitations.
184 int n = 300;
185 tmpVector.clear();
186 QList<QVariant> tmpVarList;
187 QString lines;
188 QString chars;
189 for (int x = 1; x < n + 1; x++) {
190 tmpVector.append(QString::number(x) + "\n");
191 lines += QString::number(x) + "\n";
192 chars += QChar(static_cast<ushort>(x));
193 }
194 assertEquals("diff_linesToChars: More than 256 (setup).", n, tmpVector.size());
195 assertEquals("diff_linesToChars: More than 256 (setup).", n, chars.length());
196 tmpVector.prepend("");
197 diffs = diffList(Diff(DELETE, chars));
198 dmp.diff_charsToLines(diffs, tmpVector);
199 assertEquals("diff_charsToLines: More than 256.", diffList(Diff(DELETE, lines)), diffs);
200 }
201
testDiffCleanupMerge()202 void diff_match_patch_test::testDiffCleanupMerge() {
203 // Cleanup a messy diff.
204 QList<Diff> diffs;
205 dmp.diff_cleanupMerge(diffs);
206 assertEquals("diff_cleanupMerge: Null case.", diffList(), diffs);
207
208 diffs = diffList(Diff(EQUAL, "a"), Diff(DELETE, "b"), Diff(INSERT, "c"));
209 dmp.diff_cleanupMerge(diffs);
210 assertEquals("diff_cleanupMerge: No change case.", diffList(Diff(EQUAL, "a"), Diff(DELETE, "b"), Diff(INSERT, "c")), diffs);
211
212 diffs = diffList(Diff(EQUAL, "a"), Diff(EQUAL, "b"), Diff(EQUAL, "c"));
213 dmp.diff_cleanupMerge(diffs);
214 assertEquals("diff_cleanupMerge: Merge equalities.", diffList(Diff(EQUAL, "abc")), diffs);
215
216 diffs = diffList(Diff(DELETE, "a"), Diff(DELETE, "b"), Diff(DELETE, "c"));
217 dmp.diff_cleanupMerge(diffs);
218 assertEquals("diff_cleanupMerge: Merge deletions.", diffList(Diff(DELETE, "abc")), diffs);
219
220 diffs = diffList(Diff(INSERT, "a"), Diff(INSERT, "b"), Diff(INSERT, "c"));
221 dmp.diff_cleanupMerge(diffs);
222 assertEquals("diff_cleanupMerge: Merge insertions.", diffList(Diff(INSERT, "abc")), diffs);
223
224 diffs = diffList(Diff(DELETE, "a"), Diff(INSERT, "b"), Diff(DELETE, "c"), Diff(INSERT, "d"), Diff(EQUAL, "e"), Diff(EQUAL, "f"));
225 dmp.diff_cleanupMerge(diffs);
226 assertEquals("diff_cleanupMerge: Merge interweave.", diffList(Diff(DELETE, "ac"), Diff(INSERT, "bd"), Diff(EQUAL, "ef")), diffs);
227
228 diffs = diffList(Diff(DELETE, "a"), Diff(INSERT, "abc"), Diff(DELETE, "dc"));
229 dmp.diff_cleanupMerge(diffs);
230 assertEquals("diff_cleanupMerge: Prefix and suffix detection.", diffList(Diff(EQUAL, "a"), Diff(DELETE, "d"), Diff(INSERT, "b"), Diff(EQUAL, "c")), diffs);
231
232 diffs = diffList(Diff(EQUAL, "a"), Diff(INSERT, "ba"), Diff(EQUAL, "c"));
233 dmp.diff_cleanupMerge(diffs);
234 assertEquals("diff_cleanupMerge: Slide edit left.", diffList(Diff(INSERT, "ab"), Diff(EQUAL, "ac")), diffs);
235
236 diffs = diffList(Diff(EQUAL, "c"), Diff(INSERT, "ab"), Diff(EQUAL, "a"));
237 dmp.diff_cleanupMerge(diffs);
238 assertEquals("diff_cleanupMerge: Slide edit right.", diffList(Diff(EQUAL, "ca"), Diff(INSERT, "ba")), diffs);
239
240 diffs = diffList(Diff(EQUAL, "a"), Diff(DELETE, "b"), Diff(EQUAL, "c"), Diff(DELETE, "ac"), Diff(EQUAL, "x"));
241 dmp.diff_cleanupMerge(diffs);
242 assertEquals("diff_cleanupMerge: Slide edit left recursive.", diffList(Diff(DELETE, "abc"), Diff(EQUAL, "acx")), diffs);
243
244 diffs = diffList(Diff(EQUAL, "x"), Diff(DELETE, "ca"), Diff(EQUAL, "c"), Diff(DELETE, "b"), Diff(EQUAL, "a"));
245 dmp.diff_cleanupMerge(diffs);
246 assertEquals("diff_cleanupMerge: Slide edit right recursive.", diffList(Diff(EQUAL, "xca"), Diff(DELETE, "cba")), diffs);
247 }
248
testDiffCleanupSemanticLossless()249 void diff_match_patch_test::testDiffCleanupSemanticLossless() {
250 // Slide diffs to match logical boundaries.
251 QList<Diff> diffs = diffList();
252 dmp.diff_cleanupSemanticLossless(diffs);
253 assertEquals("diff_cleanupSemantic: Null case.", diffList(), diffs);
254
255 diffs = diffList(Diff(EQUAL, "AAA\r\n\r\nBBB"), Diff(INSERT, "\r\nDDD\r\n\r\nBBB"), Diff(EQUAL, "\r\nEEE"));
256 dmp.diff_cleanupSemanticLossless(diffs);
257 assertEquals("diff_cleanupSemanticLossless: Blank lines.", diffList(Diff(EQUAL, "AAA\r\n\r\n"), Diff(INSERT, "BBB\r\nDDD\r\n\r\n"), Diff(EQUAL, "BBB\r\nEEE")), diffs);
258
259 diffs = diffList(Diff(EQUAL, "AAA\r\nBBB"), Diff(INSERT, " DDD\r\nBBB"), Diff(EQUAL, " EEE"));
260 dmp.diff_cleanupSemanticLossless(diffs);
261 assertEquals("diff_cleanupSemanticLossless: Line boundaries.", diffList(Diff(EQUAL, "AAA\r\n"), Diff(INSERT, "BBB DDD\r\n"), Diff(EQUAL, "BBB EEE")), diffs);
262
263 diffs = diffList(Diff(EQUAL, "The c"), Diff(INSERT, "ow and the c"), Diff(EQUAL, "at."));
264 dmp.diff_cleanupSemanticLossless(diffs);
265 assertEquals("diff_cleanupSemantic: Word boundaries.", diffList(Diff(EQUAL, "The "), Diff(INSERT, "cow and the "), Diff(EQUAL, "cat.")), diffs);
266
267 diffs = diffList(Diff(EQUAL, "The-c"), Diff(INSERT, "ow-and-the-c"), Diff(EQUAL, "at."));
268 dmp.diff_cleanupSemanticLossless(diffs);
269 assertEquals("diff_cleanupSemantic: Alphanumeric boundaries.", diffList(Diff(EQUAL, "The-"), Diff(INSERT, "cow-and-the-"), Diff(EQUAL, "cat.")), diffs);
270
271 diffs = diffList(Diff(EQUAL, "a"), Diff(DELETE, "a"), Diff(EQUAL, "ax"));
272 dmp.diff_cleanupSemanticLossless(diffs);
273 assertEquals("diff_cleanupSemantic: Hitting the start.", diffList(Diff(DELETE, "a"), Diff(EQUAL, "aax")), diffs);
274
275 diffs = diffList(Diff(EQUAL, "xa"), Diff(DELETE, "a"), Diff(EQUAL, "a"));
276 dmp.diff_cleanupSemanticLossless(diffs);
277 assertEquals("diff_cleanupSemantic: Hitting the end.", diffList(Diff(EQUAL, "xaa"), Diff(DELETE, "a")), diffs);
278 }
279
testDiffCleanupSemantic()280 void diff_match_patch_test::testDiffCleanupSemantic() {
281 // Cleanup semantically trivial equalities.
282 QList<Diff> diffs = diffList();
283 dmp.diff_cleanupSemantic(diffs);
284 assertEquals("diff_cleanupSemantic: Null case.", diffList(), diffs);
285
286 diffs = diffList(Diff(DELETE, "a"), Diff(INSERT, "b"), Diff(EQUAL, "cd"), Diff(DELETE, "e"));
287 dmp.diff_cleanupSemantic(diffs);
288 assertEquals("diff_cleanupSemantic: No elimination.", diffList(Diff(DELETE, "a"), Diff(INSERT, "b"), Diff(EQUAL, "cd"), Diff(DELETE, "e")), diffs);
289
290 diffs = diffList(Diff(DELETE, "a"), Diff(EQUAL, "b"), Diff(DELETE, "c"));
291 dmp.diff_cleanupSemantic(diffs);
292 assertEquals("diff_cleanupSemantic: Simple elimination.", diffList(Diff(DELETE, "abc"), Diff(INSERT, "b")), diffs);
293
294 diffs = diffList(Diff(DELETE, "ab"), Diff(EQUAL, "cd"), Diff(DELETE, "e"), Diff(EQUAL, "f"), Diff(INSERT, "g"));
295 dmp.diff_cleanupSemantic(diffs);
296 assertEquals("diff_cleanupSemantic: Backpass elimination.", diffList(Diff(DELETE, "abcdef"), Diff(INSERT, "cdfg")), diffs);
297
298 diffs = diffList(Diff(INSERT, "1"), Diff(EQUAL, "A"), Diff(DELETE, "B"), Diff(INSERT, "2"), Diff(EQUAL, "_"), Diff(INSERT, "1"), Diff(EQUAL, "A"), Diff(DELETE, "B"), Diff(INSERT, "2"));
299 dmp.diff_cleanupSemantic(diffs);
300 assertEquals("diff_cleanupSemantic: Multiple elimination.", diffList(Diff(DELETE, "AB_AB"), Diff(INSERT, "1A2_1A2")), diffs);
301
302 diffs = diffList(Diff(EQUAL, "The c"), Diff(DELETE, "ow and the c"), Diff(EQUAL, "at."));
303 dmp.diff_cleanupSemantic(diffs);
304 assertEquals("diff_cleanupSemantic: Word boundaries.", diffList(Diff(EQUAL, "The "), Diff(DELETE, "cow and the "), Diff(EQUAL, "cat.")), diffs);
305 }
306
testDiffCleanupEfficiency()307 void diff_match_patch_test::testDiffCleanupEfficiency() {
308 // Cleanup operationally trivial equalities.
309 dmp.Diff_EditCost = 4;
310 QList<Diff> diffs = diffList();
311 dmp.diff_cleanupEfficiency(diffs);
312 assertEquals("diff_cleanupEfficiency: Null case.", diffList(), diffs);
313
314 diffs = diffList(Diff(DELETE, "ab"), Diff(INSERT, "12"), Diff(EQUAL, "wxyz"), Diff(DELETE, "cd"), Diff(INSERT, "34"));
315 dmp.diff_cleanupEfficiency(diffs);
316 assertEquals("diff_cleanupEfficiency: No elimination.", diffList(Diff(DELETE, "ab"), Diff(INSERT, "12"), Diff(EQUAL, "wxyz"), Diff(DELETE, "cd"), Diff(INSERT, "34")), diffs);
317
318 diffs = diffList(Diff(DELETE, "ab"), Diff(INSERT, "12"), Diff(EQUAL, "xyz"), Diff(DELETE, "cd"), Diff(INSERT, "34"));
319 dmp.diff_cleanupEfficiency(diffs);
320 assertEquals("diff_cleanupEfficiency: Four-edit elimination.", diffList(Diff(DELETE, "abxyzcd"), Diff(INSERT, "12xyz34")), diffs);
321
322 diffs = diffList(Diff(INSERT, "12"), Diff(EQUAL, "x"), Diff(DELETE, "cd"), Diff(INSERT, "34"));
323 dmp.diff_cleanupEfficiency(diffs);
324 assertEquals("diff_cleanupEfficiency: Three-edit elimination.", diffList(Diff(DELETE, "xcd"), Diff(INSERT, "12x34")), diffs);
325
326 diffs = diffList(Diff(DELETE, "ab"), Diff(INSERT, "12"), Diff(EQUAL, "xy"), Diff(INSERT, "34"), Diff(EQUAL, "z"), Diff(DELETE, "cd"), Diff(INSERT, "56"));
327 dmp.diff_cleanupEfficiency(diffs);
328 assertEquals("diff_cleanupEfficiency: Backpass elimination.", diffList(Diff(DELETE, "abxyzcd"), Diff(INSERT, "12xy34z56")), diffs);
329
330 dmp.Diff_EditCost = 5;
331 diffs = diffList(Diff(DELETE, "ab"), Diff(INSERT, "12"), Diff(EQUAL, "wxyz"), Diff(DELETE, "cd"), Diff(INSERT, "34"));
332 dmp.diff_cleanupEfficiency(diffs);
333 assertEquals("diff_cleanupEfficiency: High cost elimination.", diffList(Diff(DELETE, "abwxyzcd"), Diff(INSERT, "12wxyz34")), diffs);
334 dmp.Diff_EditCost = 4;
335 }
336
testDiffPrettyHtml()337 void diff_match_patch_test::testDiffPrettyHtml() {
338 // Pretty print.
339 QList<Diff> diffs = diffList(Diff(EQUAL, "a\n"), Diff(DELETE, "<B>b</B>"), Diff(INSERT, "c&d"));
340 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));
341 }
342
testDiffText()343 void diff_match_patch_test::testDiffText() {
344 // Compute the source and destination texts.
345 QList<Diff> diffs = diffList(Diff(EQUAL, "jump"), Diff(DELETE, "s"), Diff(INSERT, "ed"), Diff(EQUAL, " over "), Diff(DELETE, "the"), Diff(INSERT, "a"), Diff(EQUAL, " lazy"));
346 assertEquals("diff_text1:", "jumps over the lazy", dmp.diff_text1(diffs));
347 assertEquals("diff_text2:", "jumped over a lazy", dmp.diff_text2(diffs));
348 }
349
testDiffDelta()350 void diff_match_patch_test::testDiffDelta() {
351 // Convert a diff into delta string.
352 QList<Diff> diffs = diffList(Diff(EQUAL, "jump"), Diff(DELETE, "s"), Diff(INSERT, "ed"), Diff(EQUAL, " over "), Diff(DELETE, "the"), Diff(INSERT, "a"), Diff(EQUAL, " lazy"), Diff(INSERT, "old dog"));
353 QString text1 = dmp.diff_text1(diffs);
354 assertEquals("diff_text1: Base text.", "jumps over the lazy", text1);
355
356 QString delta = dmp.diff_toDelta(diffs);
357 assertEquals("diff_toDelta:", "=4\t-1\t+ed\t=6\t-3\t+a\t=5\t+old dog", delta);
358
359 // Convert delta string into a diff.
360 assertEquals("diff_fromDelta: Normal.", diffs, dmp.diff_fromDelta(text1, delta));
361
362 // Generates error (19 < 20).
363 try {
364 dmp.diff_fromDelta(text1 + "x", delta);
365 throw "diff_fromDelta: Too long.";
366 } catch (QString ex) {
367 // Exception expected.
368 }
369
370 // Generates error (19 > 18).
371 try {
372 dmp.diff_fromDelta(text1.mid(1), delta);
373 throw "diff_fromDelta: Too short.";
374 } catch (QString ex) {
375 // Exception expected.
376 }
377
378 // Generates error (%c3%xy invalid Unicode).
379 /* This test does not work because QUrl::fromPercentEncoding("%xy") -> "?"
380 try {
381 dmp.diff_fromDelta("", "+%c3%xy");
382 throw "diff_fromDelta: Invalid character.";
383 } catch (QString ex) {
384 // Exception expected.
385 }
386 */
387
388 // Test deltas with special characters.
389 diffs = diffList(Diff(EQUAL, QString::fromWCharArray((const wchar_t*) L"\u0680 \000 \t %", 7)), Diff(DELETE, QString::fromWCharArray((const wchar_t*) L"\u0681 \001 \n ^", 7)), Diff(INSERT, QString::fromWCharArray((const wchar_t*) L"\u0682 \002 \\ |", 7)));
390 text1 = dmp.diff_text1(diffs);
391 assertEquals("diff_text1: Unicode text.", QString::fromWCharArray((const wchar_t*) L"\u0680 \000 \t %\u0681 \001 \n ^", 14), text1);
392
393 delta = dmp.diff_toDelta(diffs);
394 assertEquals("diff_toDelta: Unicode.", "=7\t-7\t+%DA%82 %02 %5C %7C", delta);
395
396 assertEquals("diff_fromDelta: Unicode.", diffs, dmp.diff_fromDelta(text1, delta));
397
398 // Verify pool of unchanged characters.
399 diffs = diffList(Diff(INSERT, "A-Z a-z 0-9 - _ . ! ~ * ' ( ) ; / ? : @ & = + $ , # "));
400 QString text2 = dmp.diff_text2(diffs);
401 assertEquals("diff_text2: Unchanged characters.", "A-Z a-z 0-9 - _ . ! ~ * \' ( ) ; / ? : @ & = + $ , # ", text2);
402
403 delta = dmp.diff_toDelta(diffs);
404 assertEquals("diff_toDelta: Unchanged characters.", "+A-Z a-z 0-9 - _ . ! ~ * \' ( ) ; / ? : @ & = + $ , # ", delta);
405
406 // Convert delta string into a diff.
407 assertEquals("diff_fromDelta: Unchanged characters.", diffs, dmp.diff_fromDelta("", delta));
408 }
409
testDiffXIndex()410 void diff_match_patch_test::testDiffXIndex() {
411 // Translate a location in text1 to text2.
412 QList<Diff> diffs = diffList(Diff(DELETE, "a"), Diff(INSERT, "1234"), Diff(EQUAL, "xyz"));
413 assertEquals("diff_xIndex: Translation on equality.", 5, dmp.diff_xIndex(diffs, 2));
414
415 diffs = diffList(Diff(EQUAL, "a"), Diff(DELETE, "1234"), Diff(EQUAL, "xyz"));
416 assertEquals("diff_xIndex: Translation on deletion.", 1, dmp.diff_xIndex(diffs, 3));
417 }
418
testDiffLevenshtein()419 void diff_match_patch_test::testDiffLevenshtein() {
420 QList<Diff> diffs = diffList(Diff(DELETE, "abc"), Diff(INSERT, "1234"), Diff(EQUAL, "xyz"));
421 assertEquals("Levenshtein with trailing equality.", 4, dmp.diff_levenshtein(diffs));
422
423 diffs = diffList(Diff(EQUAL, "xyz"), Diff(DELETE, "abc"), Diff(INSERT, "1234"));
424 assertEquals("Levenshtein with leading equality.", 4, dmp.diff_levenshtein(diffs));
425
426 diffs = diffList(Diff(DELETE, "abc"), Diff(EQUAL, "xyz"), Diff(INSERT, "1234"));
427 assertEquals("Levenshtein with middle equality.", 7, dmp.diff_levenshtein(diffs));
428 }
429
testDiffPath()430 void diff_match_patch_test::testDiffPath() {
431 // Single letters.
432 // Trace a path from back to front.
433 QList<QSet<QPair<int, int> > > v_map;
434 QSet<QPair<int, int> > row_set;
435 {
436 row_set = QSet<QPair<int, int> >();
437 row_set.insert(QPair<int, int>(0, 0));
438 v_map.append(row_set);
439 row_set = QSet<QPair<int, int> >();
440 row_set.insert(QPair<int, int>(0, 1));
441 row_set.insert(QPair<int, int>(1, 0));
442 v_map.append(row_set);
443 row_set = QSet<QPair<int, int> >();
444 row_set.insert(QPair<int, int>(0, 2));
445 row_set.insert(QPair<int, int>(2, 0));
446 row_set.insert(QPair<int, int>(2, 2));
447 v_map.append(row_set);
448 row_set = QSet<QPair<int, int> >();
449 row_set.insert(QPair<int, int>(0, 3));
450 row_set.insert(QPair<int, int>(2, 3));
451 row_set.insert(QPair<int, int>(3, 0));
452 row_set.insert(QPair<int, int>(4, 3));
453 v_map.append(row_set);
454 row_set = QSet<QPair<int, int> >();
455 row_set.insert(QPair<int, int>(0, 4));
456 row_set.insert(QPair<int, int>(2, 4));
457 row_set.insert(QPair<int, int>(4, 0));
458 row_set.insert(QPair<int, int>(4, 4));
459 row_set.insert(QPair<int, int>(5, 3));
460 v_map.append(row_set);
461 row_set = QSet<QPair<int, int> >();
462 row_set.insert(QPair<int, int>(0, 5));
463 row_set.insert(QPair<int, int>(2, 5));
464 row_set.insert(QPair<int, int>(4, 5));
465 row_set.insert(QPair<int, int>(5, 0));
466 row_set.insert(QPair<int, int>(6, 3));
467 row_set.insert(QPair<int, int>(6, 5));
468 v_map.append(row_set);
469 row_set = QSet<QPair<int, int> >();
470 row_set.insert(QPair<int, int>(0, 6));
471 row_set.insert(QPair<int, int>(2, 6));
472 row_set.insert(QPair<int, int>(4, 6));
473 row_set.insert(QPair<int, int>(6, 6));
474 row_set.insert(QPair<int, int>(7, 5));
475 v_map.append(row_set);
476 }
477 QList<Diff> diffs = diffList(Diff(INSERT, "W"), Diff(DELETE, "A"), Diff(EQUAL, "1"), Diff(DELETE, "B"), Diff(EQUAL, "2"), Diff(INSERT, "X"), Diff(DELETE, "C"), Diff(EQUAL, "3"), Diff(DELETE, "D"));
478 assertEquals("diff_path1: Single letters.", diffs, dmp.diff_path1(v_map, "A1B2C3D", "W12X3"));
479
480 // Trace a path from front to back.
481 v_map.removeAt(v_map.size() - 1);
482 diffs = diffList(Diff(EQUAL, "4"), Diff(DELETE, "E"), Diff(INSERT, "Y"), Diff(EQUAL, "5"), Diff(DELETE, "F"), Diff(EQUAL, "6"), Diff(DELETE, "G"), Diff(INSERT, "Z"));
483 assertEquals("diff_path2: Single letters.", diffs, dmp.diff_path2(v_map, "4E5F6G", "4Y56Z"));
484
485 // Double letters.
486 // Trace a path from back to front.
487 v_map = QList<QSet<QPair<int, int> > >();
488 {
489 row_set = QSet<QPair<int, int> >();
490 row_set.insert(QPair<int, int>(0, 0));
491 v_map.append(row_set);
492 row_set = QSet<QPair<int, int> >();
493 row_set.insert(QPair<int, int>(0, 1));
494 row_set.insert(QPair<int, int>(1, 0));
495 v_map.append(row_set);
496 row_set = QSet<QPair<int, int> >();
497 row_set.insert(QPair<int, int>(0, 2));
498 row_set.insert(QPair<int, int>(1, 1));
499 row_set.insert(QPair<int, int>(2, 0));
500 v_map.append(row_set);
501 row_set = QSet<QPair<int, int> >();
502 row_set.insert(QPair<int, int>(0, 3));
503 row_set.insert(QPair<int, int>(1, 2));
504 row_set.insert(QPair<int, int>(2, 1));
505 row_set.insert(QPair<int, int>(3, 0));
506 v_map.append(row_set);
507 row_set = QSet<QPair<int, int> >();
508 row_set.insert(QPair<int, int>(0, 4));
509 row_set.insert(QPair<int, int>(1, 3));
510 row_set.insert(QPair<int, int>(3, 1));
511 row_set.insert(QPair<int, int>(4, 0));
512 row_set.insert(QPair<int, int>(4, 4));
513 v_map.append(row_set);
514 }
515 diffs = diffList(Diff(INSERT, "WX"), Diff(DELETE, "AB"), Diff(EQUAL, "12"));
516 assertEquals("diff_path1: Double letters.", diffs, dmp.diff_path1(v_map, "AB12", "WX12"));
517
518 // Trace a path from front to back.
519 v_map = QList<QSet<QPair<int, int> > >();
520 {
521 row_set = QSet<QPair<int, int> >();
522 row_set.insert(QPair<int, int>(0, 0));
523 v_map.append(row_set);
524 row_set = QSet<QPair<int, int> >();
525 row_set.insert(QPair<int, int>(0, 1));
526 row_set.insert(QPair<int, int>(1, 0));
527 v_map.append(row_set);
528 row_set = QSet<QPair<int, int> >();
529 row_set.insert(QPair<int, int>(1, 1));
530 row_set.insert(QPair<int, int>(2, 0));
531 row_set.insert(QPair<int, int>(2, 4));
532 v_map.append(row_set);
533 row_set = QSet<QPair<int, int> >();
534 row_set.insert(QPair<int, int>(2, 1));
535 row_set.insert(QPair<int, int>(2, 5));
536 row_set.insert(QPair<int, int>(3, 0));
537 row_set.insert(QPair<int, int>(3, 4));
538 v_map.append(row_set);
539 row_set = QSet<QPair<int, int> >();
540 row_set.insert(QPair<int, int>(2, 6));
541 row_set.insert(QPair<int, int>(3, 5));
542 row_set.insert(QPair<int, int>(4, 4));
543 v_map.append(row_set);
544 }
545 diffs = diffList(Diff(DELETE, "CD"), Diff(EQUAL, "34"), Diff(INSERT, "YZ"));
546 assertEquals("diff_path2: Double letters.", diffs, dmp.diff_path2(v_map, "CD34", "34YZ"));
547 }
548
testDiffMain()549 void diff_match_patch_test::testDiffMain() {
550 // Perform a trivial diff.
551 QList<Diff> diffs = diffList(Diff(EQUAL, "abc"));
552 assertEquals("diff_main: Null case.", diffs, dmp.diff_main("abc", "abc", false));
553
554 diffs = diffList(Diff(EQUAL, "ab"), Diff(INSERT, "123"), Diff(EQUAL, "c"));
555 assertEquals("diff_main: Simple insertion.", diffs, dmp.diff_main("abc", "ab123c", false));
556
557 diffs = diffList(Diff(EQUAL, "a"), Diff(DELETE, "123"), Diff(EQUAL, "bc"));
558 assertEquals("diff_main: Simple deletion.", diffs, dmp.diff_main("a123bc", "abc", false));
559
560 diffs = diffList(Diff(EQUAL, "a"), Diff(INSERT, "123"), Diff(EQUAL, "b"), Diff(INSERT, "456"), Diff(EQUAL, "c"));
561 assertEquals("diff_main: Two insertions.", diffs, dmp.diff_main("abc", "a123b456c", false));
562
563 diffs = diffList(Diff(EQUAL, "a"), Diff(DELETE, "123"), Diff(EQUAL, "b"), Diff(DELETE, "456"), Diff(EQUAL, "c"));
564 assertEquals("diff_main: Two deletions.", diffs, dmp.diff_main("a123b456c", "abc", false));
565
566 // Perform a real diff.
567 // Switch off the timeout.
568 dmp.Diff_Timeout = 0;
569 dmp.Diff_DualThreshold = 32;
570 diffs = diffList(Diff(DELETE, "a"), Diff(INSERT, "b"));
571 assertEquals("diff_main: Simple case #1.", diffs, dmp.diff_main("a", "b", false));
572
573 diffs = diffList(Diff(DELETE, "Apple"), Diff(INSERT, "Banana"), Diff(EQUAL, "s are a"), Diff(INSERT, "lso"), Diff(EQUAL, " fruit."));
574 assertEquals("diff_main: Simple case #2.", diffs, dmp.diff_main("Apples are a fruit.", "Bananas are also fruit.", false));
575
576 diffs = diffList(Diff(DELETE, "a"), Diff(INSERT, QString::fromWCharArray((const wchar_t*) L"\u0680", 1)), Diff(EQUAL, "x"), Diff(DELETE, "\t"), Diff(INSERT, QString::fromWCharArray((const wchar_t*) L"\000", 1)));
577 assertEquals("diff_main: Simple case #3.", diffs, dmp.diff_main("ax\t", QString::fromWCharArray((const wchar_t*) L"\u0680x\000", 3), false));
578
579 diffs = diffList(Diff(DELETE, "1"), Diff(EQUAL, "a"), Diff(DELETE, "y"), Diff(EQUAL, "b"), Diff(DELETE, "2"), Diff(INSERT, "xab"));
580 assertEquals("diff_main: Overlap #1.", diffs, dmp.diff_main("1ayb2", "abxab", false));
581
582 diffs = diffList(Diff(INSERT, "xaxcx"), Diff(EQUAL, "abc"), Diff(DELETE, "y"));
583 assertEquals("diff_main: Overlap #2.", diffs, dmp.diff_main("abcy", "xaxcxabc", false));
584
585 // Sub-optimal double-ended diff.
586 dmp.Diff_DualThreshold = 2;
587 diffs = diffList(Diff(INSERT, "x"), Diff(EQUAL, "a"), Diff(DELETE, "b"), Diff(INSERT, "x"), Diff(EQUAL, "c"), Diff(DELETE, "y"), Diff(INSERT, "xabc"));
588 assertEquals("diff_main: Overlap #3.", diffs, dmp.diff_main("abcy", "xaxcxabc", false));
589 dmp.Diff_DualThreshold = 32;
590
591 dmp.Diff_Timeout = 0.001f; // 1ms
592 // This test may 'fail' on extremely fast computers. If so, just increase the text lengths.
593 QString 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";
594 QString 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";
595 // Increase the text lengths by 1024 times to ensure a timeout.
596 for (int x = 0; x < 10; x++) {
597 a = a + a;
598 b = b + b;
599 }
600 assertNull("diff_main: Timeout.", dmp.diff_map(a, b));
601 dmp.Diff_Timeout = 0;
602
603 // Test the linemode speedup.
604 // Must be long to pass the 200 char cutoff.
605 a = "1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n";
606 b = "abcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\nabcdefghij\n";
607 assertEquals("diff_main: Simple.", dmp.diff_main(a, b, true), dmp.diff_main(a, b, false));
608
609 a = "1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n1234567890\n";
610 b = "abcdefghij\n1234567890\n1234567890\n1234567890\nabcdefghij\n1234567890\n1234567890\n1234567890\nabcdefghij\n1234567890\n1234567890\n1234567890\nabcdefghij\n";
611 QStringList texts_linemode = diff_rebuildtexts(dmp.diff_main(a, b, true));
612 QStringList texts_textmode = diff_rebuildtexts(dmp.diff_main(a, b, false));
613 assertEquals("diff_main: Overlap.", texts_textmode, texts_linemode);
614 }
615
616
617 // MATCH TEST FUNCTIONS
618
619
testMatchAlphabet()620 void diff_match_patch_test::testMatchAlphabet() {
621 // Initialise the bitmasks for Bitap.
622 QMap<QChar, int> bitmask;
623 bitmask.insert('a', 4);
624 bitmask.insert('b', 2);
625 bitmask.insert('c', 1);
626 assertEquals("match_alphabet: Unique.", bitmask, dmp.match_alphabet("abc"));
627
628 bitmask = QMap<QChar, int>();
629 bitmask.insert('a', 37);
630 bitmask.insert('b', 18);
631 bitmask.insert('c', 8);
632 assertEquals("match_alphabet: Duplicates.", bitmask, dmp.match_alphabet("abcaba"));
633 }
634
testMatchBitap()635 void diff_match_patch_test::testMatchBitap() {
636 // Bitap algorithm.
637 dmp.Match_Distance = 100;
638 dmp.Match_Threshold = 0.5f;
639 assertEquals("match_bitap: Exact match #1.", 5, dmp.match_bitap("abcdefghijk", "fgh", 5));
640
641 assertEquals("match_bitap: Exact match #2.", 5, dmp.match_bitap("abcdefghijk", "fgh", 0));
642
643 assertEquals("match_bitap: Fuzzy match #1.", 4, dmp.match_bitap("abcdefghijk", "efxhi", 0));
644
645 assertEquals("match_bitap: Fuzzy match #2.", 2, dmp.match_bitap("abcdefghijk", "cdefxyhijk", 5));
646
647 assertEquals("match_bitap: Fuzzy match #3.", -1, dmp.match_bitap("abcdefghijk", "bxy", 1));
648
649 assertEquals("match_bitap: Overflow.", 2, dmp.match_bitap("123456789xx0", "3456789x0", 2));
650
651 assertEquals("match_bitap: Before start match.", 0, dmp.match_bitap("abcdef", "xxabc", 4));
652
653 assertEquals("match_bitap: Beyond end match.", 3, dmp.match_bitap("abcdef", "defyy", 4));
654
655 assertEquals("match_bitap: Oversized pattern.", 0, dmp.match_bitap("abcdef", "xabcdefy", 0));
656
657 dmp.Match_Threshold = 0.4f;
658 assertEquals("match_bitap: Threshold #1.", 4, dmp.match_bitap("abcdefghijk", "efxyhi", 1));
659
660 dmp.Match_Threshold = 0.3f;
661 assertEquals("match_bitap: Threshold #2.", -1, dmp.match_bitap("abcdefghijk", "efxyhi", 1));
662
663 dmp.Match_Threshold = 0.0f;
664 assertEquals("match_bitap: Threshold #3.", 1, dmp.match_bitap("abcdefghijk", "bcdef", 1));
665
666 dmp.Match_Threshold = 0.5f;
667 assertEquals("match_bitap: Multiple select #1.", 0, dmp.match_bitap("abcdexyzabcde", "abccde", 3));
668
669 assertEquals("match_bitap: Multiple select #2.", 8, dmp.match_bitap("abcdexyzabcde", "abccde", 5));
670
671 dmp.Match_Distance = 10; // Strict location.
672 assertEquals("match_bitap: Distance test #1.", -1, dmp.match_bitap("abcdefghijklmnopqrstuvwxyz", "abcdefg", 24));
673
674 assertEquals("match_bitap: Distance test #2.", 0, dmp.match_bitap("abcdefghijklmnopqrstuvwxyz", "abcdxxefg", 1));
675
676 dmp.Match_Distance = 1000; // Loose location.
677 assertEquals("match_bitap: Distance test #3.", 0, dmp.match_bitap("abcdefghijklmnopqrstuvwxyz", "abcdefg", 24));
678 }
679
testMatchMain()680 void diff_match_patch_test::testMatchMain() {
681 // Full match.
682 assertEquals("match_main: Equality.", 0, dmp.match_main("abcdef", "abcdef", 1000));
683
684 assertEquals("match_main: Null text.", -1, dmp.match_main("", "abcdef", 1));
685
686 assertEquals("match_main: Null pattern.", 3, dmp.match_main("abcdef", "", 3));
687
688 assertEquals("match_main: Exact match.", 3, dmp.match_main("abcdef", "de", 3));
689
690 dmp.Match_Threshold = 0.7f;
691 assertEquals("match_main: Complex match.", 4, dmp.match_main("I am the very model of a modern major general.", " that berry ", 5));
692 dmp.Match_Threshold = 0.5f;
693 }
694
695
696 // PATCH TEST FUNCTIONS
697
698
testPatchObj()699 void diff_match_patch_test::testPatchObj() {
700 // Patch Object.
701 Patch p;
702 p.start1 = 20;
703 p.start2 = 21;
704 p.length1 = 18;
705 p.length2 = 17;
706 p.diffs = diffList(Diff(EQUAL, "jump"), Diff(DELETE, "s"), Diff(INSERT, "ed"), Diff(EQUAL, " over "), Diff(DELETE, "the"), Diff(INSERT, "a"), Diff(EQUAL, "\nlaz"));
707 QString strp = "@@ -21,18 +22,17 @@\n jump\n-s\n+ed\n over \n-the\n+a\n %0Alaz\n";
708 assertEquals("Patch: toString.", strp, p.toString());
709 }
710
testPatchFromText()711 void diff_match_patch_test::testPatchFromText() {
712 assertTrue("patch_fromText: #0.", dmp.patch_fromText("").isEmpty());
713
714 QString strp = "@@ -21,18 +22,17 @@\n jump\n-s\n+ed\n over \n-the\n+a\n %0Alaz\n";
715 assertEquals("patch_fromText: #1.", strp, dmp.patch_fromText(strp).value(0).toString());
716
717 assertEquals("patch_fromText: #2.", "@@ -1 +1 @@\n-a\n+b\n", dmp.patch_fromText("@@ -1 +1 @@\n-a\n+b\n").value(0).toString());
718
719 assertEquals("patch_fromText: #3.", "@@ -1,3 +0,0 @@\n-abc\n", dmp.patch_fromText("@@ -1,3 +0,0 @@\n-abc\n").value(0).toString());
720
721 assertEquals("patch_fromText: #4.", "@@ -0,0 +1,3 @@\n+abc\n", dmp.patch_fromText("@@ -0,0 +1,3 @@\n+abc\n").value(0).toString());
722
723 // Generates error.
724 try {
725 dmp.patch_fromText("Bad\nPatch\n");
726 throw "patch_fromText: #5";
727 } catch (QString ex) {
728 // Exception expected.
729 }
730 }
731
testPatchToText()732 void diff_match_patch_test::testPatchToText() {
733 QString strp = "@@ -21,18 +22,17 @@\n jump\n-s\n+ed\n over \n-the\n+a\n laz\n";
734 QList<Patch> patches;
735 patches = dmp.patch_fromText(strp);
736 assertEquals("patch_toText: Single", strp, dmp.patch_toText(patches));
737
738 strp = "@@ -1,9 +1,9 @@\n-f\n+F\n oo+fooba\n@@ -7,9 +7,9 @@\n obar\n-,\n+.\n tes\n";
739 patches = dmp.patch_fromText(strp);
740 assertEquals("patch_toText: Dual", strp, dmp.patch_toText(patches));
741 }
742
testPatchAddContext()743 void diff_match_patch_test::testPatchAddContext() {
744 dmp.Patch_Margin = 4;
745 Patch p;
746 p = dmp.patch_fromText("@@ -21,4 +21,10 @@\n-jump\n+somersault\n").value(0);
747 dmp.patch_addContext(p, "The quick brown fox jumps over the lazy dog.");
748 assertEquals("patch_addContext: Simple case.", "@@ -17,12 +17,18 @@\n fox \n-jump\n+somersault\n s ov\n", p.toString());
749
750 p = dmp.patch_fromText("@@ -21,4 +21,10 @@\n-jump\n+somersault\n").value(0);
751 dmp.patch_addContext(p, "The quick brown fox jumps.");
752 assertEquals("patch_addContext: Not enough trailing context.", "@@ -17,10 +17,16 @@\n fox \n-jump\n+somersault\n s.\n", p.toString());
753
754 p = dmp.patch_fromText("@@ -3 +3,2 @@\n-e\n+at\n").value(0);
755 dmp.patch_addContext(p, "The quick brown fox jumps.");
756 assertEquals("patch_addContext: Not enough leading context.", "@@ -1,7 +1,8 @@\n Th\n-e\n+at\n qui\n", p.toString());
757
758 p = dmp.patch_fromText("@@ -3 +3,2 @@\n-e\n+at\n").value(0);
759 dmp.patch_addContext(p, "The quick brown fox jumps. The quick brown fox crashes.");
760 assertEquals("patch_addContext: Ambiguity.", "@@ -1,27 +1,28 @@\n Th\n-e\n+at\n quick brown fox jumps. \n", p.toString());
761 }
762
testPatchMake()763 void diff_match_patch_test::testPatchMake() {
764 QList<Patch> patches;
765 QString text1 = "The quick brown fox jumps over the lazy dog.";
766 QString text2 = "That quick brown fox jumped over a lazy dog.";
767 QString 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";
768 // The second patch must be "-21,17 +21,18", not "-22,17 +21,18" due to rolling context.
769 patches = dmp.patch_make(text2, text1);
770 assertEquals("patch_make: Text2+Text1 inputs", expectedPatch, dmp.patch_toText(patches));
771
772 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";
773 patches = dmp.patch_make(text1, text2);
774 assertEquals("patch_make: Text1+Text2 inputs", expectedPatch, dmp.patch_toText(patches));
775
776 QList<Diff> diffs = dmp.diff_main(text1, text2, false);
777 patches = dmp.patch_make(diffs);
778 assertEquals("patch_make: Diff input", expectedPatch, dmp.patch_toText(patches));
779
780 patches = dmp.patch_make(text1, diffs);
781 assertEquals("patch_make: Text1+Diff inputs", expectedPatch, dmp.patch_toText(patches));
782
783 patches = dmp.patch_make(text1, text2, diffs);
784 assertEquals("patch_make: Text1+Text2+Diff inputs (deprecated)", expectedPatch, dmp.patch_toText(patches));
785
786 patches = dmp.patch_make("`1234567890-=[]\\;',./", "~!@#$%^&*()_+{}|:\"<>?");
787 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));
788
789 diffs = diffList(Diff(DELETE, "`1234567890-=[]\\;',./"), Diff(INSERT, "~!@#$%^&*()_+{}|:\"<>?"));
790 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").value(0).diffs);
791
792 text1 = "";
793 for (int x = 0; x < 100; x++) {
794 text1 += "abcdef";
795 }
796 text2 = text1 + "123";
797 expectedPatch = "@@ -573,28 +573,31 @@\n cdefabcdefabcdefabcdefabcdef\n+123\n";
798 patches = dmp.patch_make(text1, text2);
799 assertEquals("patch_make: Long string with repeats.", expectedPatch, dmp.patch_toText(patches));
800 }
801
testPatchSplitMax()802 void diff_match_patch_test::testPatchSplitMax() {
803 // Assumes that Match_MaxBits is 32.
804 QList<Patch> patches;
805 patches = dmp.patch_make("abcdefghijklmnopqrstuvwxyz01234567890", "XabXcdXefXghXijXklXmnXopXqrXstXuvXwxXyzX01X23X45X67X89X0");
806 dmp.patch_splitMax(patches);
807 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));
808
809 patches = dmp.patch_make("abcdef1234567890123456789012345678901234567890123456789012345678901234567890uvwxyz", "abcdefuvwxyz");
810 QString oldToText = dmp.patch_toText(patches);
811 dmp.patch_splitMax(patches);
812 assertEquals("patch_splitMax: #2.", oldToText, dmp.patch_toText(patches));
813
814 patches = dmp.patch_make("1234567890123456789012345678901234567890123456789012345678901234567890", "abc");
815 dmp.patch_splitMax(patches);
816 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));
817
818 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");
819 dmp.patch_splitMax(patches);
820 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));
821 }
822
testPatchAddPadding()823 void diff_match_patch_test::testPatchAddPadding() {
824 QList<Patch> patches;
825 patches = dmp.patch_make("", "test");
826 assertEquals("patch_addPadding: Both edges full.", "@@ -0,0 +1,4 @@\n+test\n", dmp.patch_toText(patches));
827 dmp.patch_addPadding(patches);
828 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));
829
830 patches = dmp.patch_make("XY", "XtestY");
831 assertEquals("patch_addPadding: Both edges partial.", "@@ -1,2 +1,6 @@\n X\n+test\n Y\n", dmp.patch_toText(patches));
832 dmp.patch_addPadding(patches);
833 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));
834
835 patches = dmp.patch_make("XXXXYYYY", "XXXXtestYYYY");
836 assertEquals("patch_addPadding: Both edges none.", "@@ -1,8 +1,12 @@\n XXXX\n+test\n YYYY\n", dmp.patch_toText(patches));
837 dmp.patch_addPadding(patches);
838 assertEquals("patch_addPadding: Both edges none.", "@@ -5,8 +5,12 @@\n XXXX\n+test\n YYYY\n", dmp.patch_toText(patches));
839 }
840
testPatchApply()841 void diff_match_patch_test::testPatchApply() {
842 dmp.Match_Distance = 1000;
843 dmp.Match_Threshold = 0.5f;
844 dmp.Patch_DeleteThreshold = 0.5f;
845 QList<Patch> patches;
846 patches = dmp.patch_make("The quick brown fox jumps over the lazy dog.", "That quick brown fox jumped over a lazy dog.");
847 QPair<QString, QVector<bool> > results = dmp.patch_apply(patches, "The quick brown fox jumps over the lazy dog.");
848 QVector<bool> boolArray = results.second;
849 QString resultStr = results.first + "\t" + (boolArray[0] ? "true" : "false") + "\t" + (boolArray[1] ? "true" : "false");
850 assertEquals("patch_apply: Exact match.", "That quick brown fox jumped over a lazy dog.\ttrue\ttrue", resultStr);
851
852 results = dmp.patch_apply(patches, "The quick red rabbit jumps over the tired tiger.");
853 boolArray = results.second;
854 resultStr = results.first + "\t" + (boolArray[0] ? "true" : "false") + "\t" + (boolArray[1] ? "true" : "false");
855 assertEquals("patch_apply: Partial match.", "That quick red rabbit jumped over a tired tiger.\ttrue\ttrue", resultStr);
856
857 results = dmp.patch_apply(patches, "I am the very model of a modern major general.");
858 boolArray = results.second;
859 resultStr = results.first + "\t" + (boolArray[0] ? "true" : "false") + "\t" + (boolArray[1] ? "true" : "false");
860 assertEquals("patch_apply: Failed match.", "I am the very model of a modern major general.\tfalse\tfalse", resultStr);
861
862 patches = dmp.patch_make("x1234567890123456789012345678901234567890123456789012345678901234567890y", "xabcy");
863 results = dmp.patch_apply(patches, "x123456789012345678901234567890-----++++++++++-----123456789012345678901234567890y");
864 boolArray = results.second;
865 resultStr = results.first + "\t" + (boolArray[0] ? "true" : "false") + "\t" + (boolArray[1] ? "true" : "false");
866 assertEquals("patch_apply: Big delete, small change.", "xabcy\ttrue\ttrue", resultStr);
867
868 patches = dmp.patch_make("x1234567890123456789012345678901234567890123456789012345678901234567890y", "xabcy");
869 results = dmp.patch_apply(patches, "x12345678901234567890---------------++++++++++---------------12345678901234567890y");
870 boolArray = results.second;
871 resultStr = results.first + "\t" + (boolArray[0] ? "true" : "false") + "\t" + (boolArray[1] ? "true" : "false");
872 assertEquals("patch_apply: Big delete, large change 1.", "xabc12345678901234567890---------------++++++++++---------------12345678901234567890y\tfalse\ttrue", resultStr);
873
874 dmp.Patch_DeleteThreshold = 0.6f;
875 patches = dmp.patch_make("x1234567890123456789012345678901234567890123456789012345678901234567890y", "xabcy");
876 results = dmp.patch_apply(patches, "x12345678901234567890---------------++++++++++---------------12345678901234567890y");
877 boolArray = results.second;
878 resultStr = results.first + "\t" + (boolArray[0] ? "true" : "false") + "\t" + (boolArray[1] ? "true" : "false");
879 assertEquals("patch_apply: Big delete, large change 2.", "xabcy\ttrue\ttrue", resultStr);
880 dmp.Patch_DeleteThreshold = 0.5f;
881
882 dmp.Match_Threshold = 0.0f;
883 dmp.Match_Distance = 0;
884 patches = dmp.patch_make("abcdefghijklmnopqrstuvwxyz--------------------1234567890", "abcXXXXXXXXXXdefghijklmnopqrstuvwxyz--------------------1234567YYYYYYYYYY890");
885 results = dmp.patch_apply(patches, "ABCDEFGHIJKLMNOPQRSTUVWXYZ--------------------1234567890");
886 boolArray = results.second;
887 resultStr = results.first + "\t" + (boolArray[0] ? "true" : "false") + "\t" + (boolArray[1] ? "true" : "false");
888 assertEquals("Compensate for failed patch.", "ABCDEFGHIJKLMNOPQRSTUVWXYZ--------------------1234567YYYYYYYYYY890\tfalse\ttrue", resultStr);
889 dmp.Match_Threshold = 0.5f;
890 dmp.Match_Distance = 1000;
891
892 patches = dmp.patch_make("", "test");
893 QString patchStr = dmp.patch_toText(patches);
894 dmp.patch_apply(patches, "");
895 assertEquals("patch_apply: No side effects.", patchStr, dmp.patch_toText(patches));
896
897 patches = dmp.patch_make("The quick brown fox jumps over the lazy dog.", "Woof");
898 patchStr = dmp.patch_toText(patches);
899 dmp.patch_apply(patches, "The quick brown fox jumps over the lazy dog.");
900 assertEquals("patch_apply: No side effects with major delete.", patchStr, dmp.patch_toText(patches));
901
902 patches = dmp.patch_make("", "test");
903 results = dmp.patch_apply(patches, "");
904 boolArray = results.second;
905 resultStr = results.first + "\t" + (boolArray[0] ? "true" : "false");
906 assertEquals("patch_apply: Edge exact match.", "test\ttrue", resultStr);
907
908 patches = dmp.patch_make("XY", "XtestY");
909 results = dmp.patch_apply(patches, "XY");
910 boolArray = results.second;
911 resultStr = results.first + "\t" + (boolArray[0] ? "true" : "false");
912 assertEquals("patch_apply: Near edge exact match.", "XtestY\ttrue", resultStr);
913
914 patches = dmp.patch_make("y", "y123");
915 results = dmp.patch_apply(patches, "x");
916 boolArray = results.second;
917 resultStr = results.first + "\t" + (boolArray[0] ? "true" : "false");
918 assertEquals("patch_apply: Edge partial match.", "x123\ttrue", resultStr);
919 }
920
921
assertEquals(const QString & strCase,int n1,int n2)922 void diff_match_patch_test::assertEquals(const QString &strCase, int n1, int n2) {
923 if (n1 != n2) {
924 qDebug(qPrintable(QString("%1 FAIL\nExpected: %2\nActual: %3")
925 .arg(strCase, QString::number(n1), QString::number(n2))));
926 throw strCase;
927 }
928 qDebug(qPrintable(QString("%1 OK").arg(strCase)));
929 }
930
assertEquals(const QString & strCase,const QString & s1,const QString & s2)931 void diff_match_patch_test::assertEquals(const QString &strCase, const QString &s1, const QString &s2) {
932 if (s1 != s2) {
933 qDebug(qPrintable(QString("%1 FAIL\nExpected: %2\nActual: %3")
934 .arg(strCase, s1, s2)));
935 throw strCase;
936 }
937 qDebug(qPrintable(QString("%1 OK").arg(strCase)));
938 }
939
assertEquals(const QString & strCase,const Diff & d1,const Diff & d2)940 void diff_match_patch_test::assertEquals(const QString &strCase, const Diff &d1, const Diff &d2) {
941 if (d1 != d2) {
942 qDebug(qPrintable(QString("%1 FAIL\nExpected: %2\nActual: %3")
943 .arg(strCase, d1.toString(), d2.toString())));
944 throw strCase;
945 }
946 qDebug(qPrintable(QString("%1 OK").arg(strCase)));
947 }
948
assertEquals(const QString & strCase,const QList<Diff> & list1,const QList<Diff> & list2)949 void diff_match_patch_test::assertEquals(const QString &strCase, const QList<Diff> &list1, const QList<Diff> &list2) {
950 bool fail = false;
951 if (list1.count() == list2.count()) {
952 int i = 0;
953 foreach(Diff d1, list1) {
954 Diff d2 = list2.value(i);
955 if (d1 != d2) {
956 fail = true;
957 break;
958 }
959 i++;
960 }
961 } else {
962 fail = true;
963 }
964
965 if (fail) {
966 // Build human readable description of both lists.
967 QString listString1 = "(";
968 bool first = true;
969 foreach(Diff d1, list1) {
970 if (!first) {
971 listString1 += ", ";
972 }
973 listString1 += d1.toString();
974 first = false;
975 }
976 listString1 += ")";
977 QString listString2 = "(";
978 first = true;
979 foreach(Diff d2, list2) {
980 if (!first) {
981 listString2 += ", ";
982 }
983 listString2 += d2.toString();
984 first = false;
985 }
986 listString2 += ")";
987 qDebug(qPrintable(QString("%1 FAIL\nExpected: %2\nActual: %3")
988 .arg(strCase, listString1, listString2)));
989 throw strCase;
990 }
991 qDebug(qPrintable(QString("%1 OK").arg(strCase)));
992 }
993
assertEquals(const QString & strCase,const QList<QVariant> & list1,const QList<QVariant> & list2)994 void diff_match_patch_test::assertEquals(const QString &strCase, const QList<QVariant> &list1, const QList<QVariant> &list2) {
995 bool fail = false;
996 if (list1.count() == list2.count()) {
997 int i = 0;
998 foreach(QVariant q1, list1) {
999 QVariant q2 = list2.value(i);
1000 if (q1 != q2) {
1001 fail = true;
1002 break;
1003 }
1004 i++;
1005 }
1006 } else {
1007 fail = true;
1008 }
1009
1010 if (fail) {
1011 // Build human readable description of both lists.
1012 QString listString1 = "(";
1013 bool first = true;
1014 foreach(QVariant q1, list1) {
1015 if (!first) {
1016 listString1 += ", ";
1017 }
1018 listString1 += q1.toString();
1019 first = false;
1020 }
1021 listString1 += ")";
1022 QString listString2 = "(";
1023 first = true;
1024 foreach(QVariant q2, list2) {
1025 if (!first) {
1026 listString2 += ", ";
1027 }
1028 listString2 += q2.toString();
1029 first = false;
1030 }
1031 listString2 += ")";
1032 qDebug(qPrintable(QString("%1 FAIL\nExpected: %2\nActual: %3")
1033 .arg(strCase, listString1, listString2)));
1034 throw strCase;
1035 }
1036 qDebug(qPrintable(QString("%1 OK").arg(strCase)));
1037 }
1038
assertEquals(const QString & strCase,const QVariant & var1,const QVariant & var2)1039 void diff_match_patch_test::assertEquals(const QString &strCase, const QVariant &var1, const QVariant &var2) {
1040 if (var1 != var2) {
1041 qDebug(qPrintable(QString("%1 FAIL\nExpected: %2\nActual: %3")
1042 .arg(strCase, var1.toString(), var2.toString())));
1043 throw strCase;
1044 }
1045 qDebug(qPrintable(QString("%1 OK").arg(strCase)));
1046 }
1047
assertEquals(const QString & strCase,const QMap<QChar,int> & m1,const QMap<QChar,int> & m2)1048 void diff_match_patch_test::assertEquals(const QString &strCase, const QMap<QChar, int> &m1, const QMap<QChar, int> &m2) {
1049 QMapIterator<QChar, int> i1(m1), i2(m2);
1050
1051 while (i1.hasNext() && i2.hasNext()) {
1052 i1.next();
1053 i2.next();
1054 if (i1.key() != i2.key() || i1.value() != i2.value()) {
1055 qDebug(qPrintable(QString("%1 FAIL\nExpected: (%2, %3)\nActual: (%4, %5)")
1056 .arg(strCase, QString(i1.key()), QString::number(i1.value()), QString(i2.key()), QString::number(i2.value()))));
1057 throw strCase;
1058 }
1059 }
1060
1061 if (i1.hasNext()) {
1062 i1.next();
1063 qDebug(qPrintable(QString("%1 FAIL\nExpected: (%2, %3)\nActual: none")
1064 .arg(strCase, QString(i1.key()), QString::number(i1.value()))));
1065 throw strCase;
1066 }
1067 if (i2.hasNext()) {
1068 i2.next();
1069 qDebug(qPrintable(QString("%1 FAIL\nExpected: none\nActual: (%2, %3)")
1070 .arg(strCase, QString(i2.key()), QString::number(i2.value()))));
1071 throw strCase;
1072 }
1073 qDebug(qPrintable(QString("%1 OK").arg(strCase)));
1074 }
1075
assertEquals(const QString & strCase,const QStringList & list1,const QStringList & list2)1076 void diff_match_patch_test::assertEquals(const QString &strCase, const QStringList &list1, const QStringList &list2) {
1077 if (list1 != list2) {
1078 qDebug(qPrintable(QString("%1 FAIL\nExpected: %2\nActual: %3")
1079 .arg(strCase, list1.join(","), list2.join(","))));
1080 throw strCase;
1081 }
1082 qDebug(qPrintable(QString("%1 OK").arg(strCase)));
1083 }
1084
assertTrue(const QString & strCase,bool value)1085 void diff_match_patch_test::assertTrue(const QString &strCase, bool value) {
1086 if (!value) {
1087 qDebug(qPrintable(QString("%1 FAIL\nExpected: %2\nActual: %3")
1088 .arg(strCase, "true", "false")));
1089 throw strCase;
1090 }
1091 qDebug(qPrintable(QString("%1 OK").arg(strCase)));
1092 }
1093
assertFalse(const QString & strCase,bool value)1094 void diff_match_patch_test::assertFalse(const QString &strCase, bool value) {
1095 if (value) {
1096 qDebug(qPrintable(QString("%1 FAIL\nExpected: %2\nActual: %3")
1097 .arg(strCase, "false", "true")));
1098 throw strCase;
1099 }
1100 qDebug(qPrintable(QString("%1 OK").arg(strCase)));
1101 }
1102
1103
1104 // Construct the two texts which made up the diff originally.
diff_rebuildtexts(QList<Diff> diffs)1105 QStringList diff_match_patch_test::diff_rebuildtexts(QList<Diff> diffs) {
1106 QStringList text;
1107 text << QString("") << QString("");
1108 foreach (Diff myDiff, diffs) {
1109 if (myDiff.operation != INSERT) {
1110 text[0] += myDiff.text;
1111 }
1112 if (myDiff.operation != DELETE) {
1113 text[1] += myDiff.text;
1114 }
1115 }
1116 return text;
1117 }
1118
assertNull(const QString & strCase,const QStringList & list)1119 void diff_match_patch_test::assertNull(const QString &strCase, const QStringList &list) {
1120 if (!list.isEmpty()) {
1121 throw strCase;
1122 }
1123 }
1124
assertNull(const QString & strCase,const QList<Diff> & list)1125 void diff_match_patch_test::assertNull(const QString &strCase, const QList<Diff> &list) {
1126 if (!list.isEmpty()) {
1127 throw strCase;
1128 }
1129 }
1130
1131
1132 // Private function for quickly building lists of diffs.
diffList(Diff d1,Diff d2,Diff d3,Diff d4,Diff d5,Diff d6,Diff d7,Diff d8,Diff d9,Diff d10)1133 QList<Diff> diff_match_patch_test::diffList(Diff d1, Diff d2, Diff d3, Diff d4, Diff d5,
1134 Diff d6, Diff d7, Diff d8, Diff d9, Diff d10) {
1135 QList<Diff> listRet;
1136 if (d1.operation == EQUAL && d1.text == NULL) {
1137 return listRet;
1138 }
1139 listRet << d1;
1140
1141 if (d2.operation == EQUAL && d2.text == NULL) {
1142 return listRet;
1143 }
1144 listRet << d2;
1145
1146 if (d3.operation == EQUAL && d3.text == NULL) {
1147 return listRet;
1148 }
1149 listRet << d3;
1150
1151 if (d4.operation == EQUAL && d4.text == NULL) {
1152 return listRet;
1153 }
1154 listRet << d4;
1155
1156 if (d5.operation == EQUAL && d5.text == NULL) {
1157 return listRet;
1158 }
1159 listRet << d5;
1160
1161 if (d6.operation == EQUAL && d6.text == NULL) {
1162 return listRet;
1163 }
1164 listRet << d6;
1165
1166 if (d7.operation == EQUAL && d7.text == NULL) {
1167 return listRet;
1168 }
1169 listRet << d7;
1170
1171 if (d8.operation == EQUAL && d8.text == NULL) {
1172 return listRet;
1173 }
1174 listRet << d8;
1175
1176 if (d9.operation == EQUAL && d9.text == NULL) {
1177 return listRet;
1178 }
1179 listRet << d9;
1180
1181 if (d10.operation == EQUAL && d10.text == NULL) {
1182 return listRet;
1183 }
1184 listRet << d10;
1185
1186 return listRet;
1187 }
1188
1189
1190 /*
1191 Compile instructions for MinGW and QT4 on Windows:
1192 qmake -project
1193 qmake
1194 mingw32-make
1195 g++ -o diff_match_patch_test debug\diff_match_patch_test.o debug\diff_match_patch.o \qt4\lib\libQtCore4.a
1196 diff_match_patch_test.exe
1197 */
1198