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&para;<BR></SPAN><DEL STYLE=\"background:#FFE6E6;\" TITLE=\"i=2\">&lt;B&gt;b&lt;/B&gt;</DEL><INS STYLE=\"background:#E6FFE6;\" TITLE=\"i=2\">c&amp;d</INS>", dmp.diff_prettyHtml(diffs));
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