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
19 * http://code.google.com/p/google-diff-match-patch/
20 */
21
22 /*
23 * Version slightly modified to compile with Qt 5.2 (2 minor fixes: toAscii() -> toLatin()).
24 */
25
26 #include <algorithm>
27 #include <limits>
28 // Code known to compile and run with Qt 4.3 through Qt 4.7.
29 #include <QtCore>
30 #include <time.h>
31 #include "diff_match_patch.h"
32
33
34 //////////////////////////
35 //
36 // Diff Class
37 //
38 //////////////////////////
39
40
41 /**
42 * Constructor. Initializes the diff with the provided values.
43 * @param operation One of INSERT, DELETE or EQUAL
44 * @param text The text being applied
45 */
Diff(Operation _operation,const QString & _text)46 Diff::Diff(Operation _operation, const QString &_text) :
47 operation(_operation), text(_text) {
48 // Construct a diff with the specified operation and text.
49 }
50
Diff()51 Diff::Diff() {
52 }
53
54
strOperation(Operation op)55 QString Diff::strOperation(Operation op) {
56 switch (op) {
57 case INSERT:
58 return "INSERT";
59 case DELETE:
60 return "DELETE";
61 case EQUAL:
62 return "EQUAL";
63 }
64 throw "Invalid operation.";
65 }
66
67 /**
68 * Display a human-readable version of this Diff.
69 * @return text version
70 */
toString() const71 QString Diff::toString() const {
72 QString prettyText = text;
73 // Replace linebreaks with Pilcrow signs.
74 prettyText.replace('\n', L'\u00b6');
75 return QString("Diff(") + strOperation(operation) + QString(",\"")
76 + prettyText + QString("\")");
77 }
78
79 /**
80 * Is this Diff equivalent to another Diff?
81 * @param d Another Diff to compare against
82 * @return true or false
83 */
operator ==(const Diff & d) const84 bool Diff::operator==(const Diff &d) const {
85 return (d.operation == this->operation) && (d.text == this->text);
86 }
87
operator !=(const Diff & d) const88 bool Diff::operator!=(const Diff &d) const {
89 return !(operator == (d));
90 }
91
92
93 /////////////////////////////////////////////
94 //
95 // Patch Class
96 //
97 /////////////////////////////////////////////
98
99
100 /**
101 * Constructor. Initializes with an empty list of diffs.
102 */
Patch()103 Patch::Patch() :
104 start1(0), start2(0),
105 length1(0), length2(0) {
106 }
107
isNull() const108 bool Patch::isNull() const {
109 if (start1 == 0 && start2 == 0 && length1 == 0 && length2 == 0
110 && diffs.size() == 0) {
111 return true;
112 }
113 return false;
114 }
115
116
117 /**
118 * Emmulate GNU diff's format.
119 * Header: @@ -382,8 +481,9 @@
120 * Indicies are printed as 1-based, not 0-based.
121 * @return The GNU diff string
122 */
toString()123 QString Patch::toString() {
124 QString coords1, coords2;
125 if (length1 == 0) {
126 coords1 = QString::number(start1) + QString(",0");
127 } else if (length1 == 1) {
128 coords1 = QString::number(start1 + 1);
129 } else {
130 coords1 = QString::number(start1 + 1) + QString(",")
131 + QString::number(length1);
132 }
133 if (length2 == 0) {
134 coords2 = QString::number(start2) + QString(",0");
135 } else if (length2 == 1) {
136 coords2 = QString::number(start2 + 1);
137 } else {
138 coords2 = QString::number(start2 + 1) + QString(",")
139 + QString::number(length2);
140 }
141 QString text;
142 text = QString("@@ -") + coords1 + QString(" +") + coords2
143 + QString(" @@\n");
144 // Escape the body of the patch with %xx notation.
145 for (Diff aDiff : diffs) {
146 switch (aDiff.operation) {
147 case INSERT:
148 text += QString('+');
149 break;
150 case DELETE:
151 text += QString('-');
152 break;
153 case EQUAL:
154 text += QString(' ');
155 break;
156 }
157 text += QString(QUrl::toPercentEncoding(aDiff.text, " !~*'();/?:@&=+$,#"))
158 + QString("\n");
159 }
160
161 return text;
162 }
163
164
165 /////////////////////////////////////////////
166 //
167 // diff_match_patch Class
168 //
169 /////////////////////////////////////////////
170
diff_match_patch()171 diff_match_patch::diff_match_patch() :
172 Diff_Timeout(1.0f),
173 Diff_EditCost(4),
174 Match_Threshold(0.5f),
175 Match_Distance(1000),
176 Patch_DeleteThreshold(0.5f),
177 Patch_Margin(4),
178 Match_MaxBits(32) {
179 }
180
181
diff_main(const QString & text1,const QString & text2)182 QList<Diff> diff_match_patch::diff_main(const QString &text1,
183 const QString &text2) {
184 return diff_main(text1, text2, true);
185 }
186
diff_main(const QString & text1,const QString & text2,bool checklines)187 QList<Diff> diff_match_patch::diff_main(const QString &text1,
188 const QString &text2, bool checklines) {
189 // Set a deadline by which time the diff must be complete.
190 clock_t deadline;
191 if (Diff_Timeout <= 0) {
192 deadline = std::numeric_limits<clock_t>::max();
193 } else {
194 deadline = clock() + (clock_t)(Diff_Timeout * CLOCKS_PER_SEC);
195 }
196 return diff_main(text1, text2, checklines, deadline);
197 }
198
diff_main(const QString & text1,const QString & text2,bool checklines,clock_t deadline)199 QList<Diff> diff_match_patch::diff_main(const QString &text1,
200 const QString &text2, bool checklines, clock_t deadline) {
201 // Check for null inputs.
202 if (text1.isNull() || text2.isNull()) {
203 throw "Null inputs. (diff_main)";
204 }
205
206 // Check for equality (speedup).
207 QList<Diff> diffs;
208 if (text1 == text2) {
209 if (!text1.isEmpty()) {
210 diffs.append(Diff(EQUAL, text1));
211 }
212 return diffs;
213 }
214
215 // Trim off common prefix (speedup).
216 int commonlength = diff_commonPrefix(text1, text2);
217 const QString &commonprefix = text1.left(commonlength);
218 QString textChopped1 = text1.mid(commonlength);
219 QString textChopped2 = text2.mid(commonlength);
220
221 // Trim off common suffix (speedup).
222 commonlength = diff_commonSuffix(textChopped1, textChopped2);
223 const QString &commonsuffix = textChopped1.right(commonlength);
224 textChopped1 = textChopped1.left(textChopped1.length() - commonlength);
225 textChopped2 = textChopped2.left(textChopped2.length() - commonlength);
226
227 // Compute the diff on the middle block.
228 diffs = diff_compute(textChopped1, textChopped2, checklines, deadline);
229
230 // Restore the prefix and suffix.
231 if (!commonprefix.isEmpty()) {
232 diffs.prepend(Diff(EQUAL, commonprefix));
233 }
234 if (!commonsuffix.isEmpty()) {
235 diffs.append(Diff(EQUAL, commonsuffix));
236 }
237
238 diff_cleanupMerge(diffs);
239
240 return diffs;
241 }
242
243
diff_compute(QString text1,QString text2,bool checklines,clock_t deadline)244 QList<Diff> diff_match_patch::diff_compute(QString text1, QString text2,
245 bool checklines, clock_t deadline) {
246 QList<Diff> diffs;
247
248 if (text1.isEmpty()) {
249 // Just add some text (speedup).
250 diffs.append(Diff(INSERT, text2));
251 return diffs;
252 }
253
254 if (text2.isEmpty()) {
255 // Just delete some text (speedup).
256 diffs.append(Diff(DELETE, text1));
257 return diffs;
258 }
259
260 {
261 const QString longtext = text1.length() > text2.length() ? text1 : text2;
262 const QString shorttext = text1.length() > text2.length() ? text2 : text1;
263 const int i = longtext.indexOf(shorttext);
264 if (i != -1) {
265 // Shorter text is inside the longer text (speedup).
266 const Operation op = (text1.length() > text2.length()) ? DELETE : INSERT;
267 diffs.append(Diff(op, longtext.left(i)));
268 diffs.append(Diff(EQUAL, shorttext));
269 diffs.append(Diff(op, safeMid(longtext, i + shorttext.length())));
270 return diffs;
271 }
272
273 if (shorttext.length() == 1) {
274 // Single character string.
275 // After the previous speedup, the character can't be an equality.
276 diffs.append(Diff(DELETE, text1));
277 diffs.append(Diff(INSERT, text2));
278 return diffs;
279 }
280 // Garbage collect longtext and shorttext by scoping out.
281 }
282
283 // Check to see if the problem can be split in two.
284 const QStringList hm = diff_halfMatch(text1, text2);
285 if (hm.count() > 0) {
286 // A half-match was found, sort out the return data.
287 const QString text1_a = hm[0];
288 const QString text1_b = hm[1];
289 const QString text2_a = hm[2];
290 const QString text2_b = hm[3];
291 const QString mid_common = hm[4];
292 // Send both pairs off for separate processing.
293 const QList<Diff> diffs_a = diff_main(text1_a, text2_a,
294 checklines, deadline);
295 const QList<Diff> diffs_b = diff_main(text1_b, text2_b,
296 checklines, deadline);
297 // Merge the results.
298 diffs = diffs_a;
299 diffs.append(Diff(EQUAL, mid_common));
300 diffs += diffs_b;
301 return diffs;
302 }
303
304 // Perform a real diff.
305 if (checklines && text1.length() > 100 && text2.length() > 100) {
306 return diff_lineMode(text1, text2, deadline);
307 }
308
309 return diff_bisect(text1, text2, deadline);
310 }
311
312
diff_lineMode(QString text1,QString text2,clock_t deadline)313 QList<Diff> diff_match_patch::diff_lineMode(QString text1, QString text2,
314 clock_t deadline) {
315 // Scan the text on a line-by-line basis first.
316 const QList<QVariant> b = diff_linesToChars(text1, text2);
317 text1 = b[0].toString();
318 text2 = b[1].toString();
319 QStringList linearray = b[2].toStringList();
320
321 QList<Diff> diffs = diff_main(text1, text2, false, deadline);
322
323 // Convert the diff back to original text.
324 diff_charsToLines(diffs, linearray);
325 // Eliminate freak matches (e.g. blank lines)
326 diff_cleanupSemantic(diffs);
327
328 // Rediff any replacement blocks, this time character-by-character.
329 // Add a dummy entry at the end.
330 diffs.append(Diff(EQUAL, ""));
331 int count_delete = 0;
332 int count_insert = 0;
333 QString text_delete = "";
334 QString text_insert = "";
335
336 QMutableListIterator<Diff> pointer(diffs);
337 Diff *thisDiff = pointer.hasNext() ? &pointer.next() : NULL;
338 while (thisDiff != NULL) {
339 switch (thisDiff->operation) {
340 case INSERT:
341 count_insert++;
342 text_insert += thisDiff->text;
343 break;
344 case DELETE:
345 count_delete++;
346 text_delete += thisDiff->text;
347 break;
348 case EQUAL:
349 // Upon reaching an equality, check for prior redundancies.
350 if (count_delete >= 1 && count_insert >= 1) {
351 // Delete the offending records and add the merged ones.
352 pointer.previous();
353 for (int j = 0; j < count_delete + count_insert; j++) {
354 pointer.previous();
355 pointer.remove();
356 }
357 foreach(Diff newDiff,
358 diff_main(text_delete, text_insert, false, deadline)) {
359 pointer.insert(newDiff);
360 }
361 }
362 count_insert = 0;
363 count_delete = 0;
364 text_delete = "";
365 text_insert = "";
366 break;
367 }
368 thisDiff = pointer.hasNext() ? &pointer.next() : NULL;
369 }
370 diffs.removeLast(); // Remove the dummy entry at the end.
371
372 return diffs;
373 }
374
375
diff_bisect(const QString & text1,const QString & text2,clock_t deadline)376 QList<Diff> diff_match_patch::diff_bisect(const QString &text1,
377 const QString &text2, clock_t deadline) {
378 // Cache the text lengths to prevent multiple calls.
379 const int text1_length = text1.length();
380 const int text2_length = text2.length();
381 const int max_d = (text1_length + text2_length + 1) / 2;
382 const int v_offset = max_d;
383 const int v_length = 2 * max_d;
384 int *v1 = new int[v_length];
385 int *v2 = new int[v_length];
386 for (int x = 0; x < v_length; x++) {
387 v1[x] = -1;
388 v2[x] = -1;
389 }
390 v1[v_offset + 1] = 0;
391 v2[v_offset + 1] = 0;
392 const int delta = text1_length - text2_length;
393 // If the total number of characters is odd, then the front path will
394 // collide with the reverse path.
395 const bool front = (delta % 2 != 0);
396 // Offsets for start and end of k loop.
397 // Prevents mapping of space beyond the grid.
398 int k1start = 0;
399 int k1end = 0;
400 int k2start = 0;
401 int k2end = 0;
402 for (int d = 0; d < max_d; d++) {
403 // Bail out if deadline is reached.
404 if (clock() > deadline) {
405 break;
406 }
407
408 // Walk the front path one step.
409 for (int k1 = -d + k1start; k1 <= d - k1end; k1 += 2) {
410 const int k1_offset = v_offset + k1;
411 int x1;
412 if (k1 == -d || (k1 != d && v1[k1_offset - 1] < v1[k1_offset + 1])) {
413 x1 = v1[k1_offset + 1];
414 } else {
415 x1 = v1[k1_offset - 1] + 1;
416 }
417 int y1 = x1 - k1;
418 while (x1 < text1_length && y1 < text2_length
419 && text1[x1] == text2[y1]) {
420 x1++;
421 y1++;
422 }
423 v1[k1_offset] = x1;
424 if (x1 > text1_length) {
425 // Ran off the right of the graph.
426 k1end += 2;
427 } else if (y1 > text2_length) {
428 // Ran off the bottom of the graph.
429 k1start += 2;
430 } else if (front) {
431 int k2_offset = v_offset + delta - k1;
432 if (k2_offset >= 0 && k2_offset < v_length && v2[k2_offset] != -1) {
433 // Mirror x2 onto top-left coordinate system.
434 int x2 = text1_length - v2[k2_offset];
435 if (x1 >= x2) {
436 // Overlap detected.
437 delete [] v1;
438 delete [] v2;
439 return diff_bisectSplit(text1, text2, x1, y1, deadline);
440 }
441 }
442 }
443 }
444
445 // Walk the reverse path one step.
446 for (int k2 = -d + k2start; k2 <= d - k2end; k2 += 2) {
447 const int k2_offset = v_offset + k2;
448 int x2;
449 if (k2 == -d || (k2 != d && v2[k2_offset - 1] < v2[k2_offset + 1])) {
450 x2 = v2[k2_offset + 1];
451 } else {
452 x2 = v2[k2_offset - 1] + 1;
453 }
454 int y2 = x2 - k2;
455 while (x2 < text1_length && y2 < text2_length
456 && text1[text1_length - x2 - 1] == text2[text2_length - y2 - 1]) {
457 x2++;
458 y2++;
459 }
460 v2[k2_offset] = x2;
461 if (x2 > text1_length) {
462 // Ran off the left of the graph.
463 k2end += 2;
464 } else if (y2 > text2_length) {
465 // Ran off the top of the graph.
466 k2start += 2;
467 } else if (!front) {
468 int k1_offset = v_offset + delta - k2;
469 if (k1_offset >= 0 && k1_offset < v_length && v1[k1_offset] != -1) {
470 int x1 = v1[k1_offset];
471 int y1 = v_offset + x1 - k1_offset;
472 // Mirror x2 onto top-left coordinate system.
473 x2 = text1_length - x2;
474 if (x1 >= x2) {
475 // Overlap detected.
476 delete [] v1;
477 delete [] v2;
478 return diff_bisectSplit(text1, text2, x1, y1, deadline);
479 }
480 }
481 }
482 }
483 }
484 delete [] v1;
485 delete [] v2;
486 // Diff took too long and hit the deadline or
487 // number of diffs equals number of characters, no commonality at all.
488 QList<Diff> diffs;
489 diffs.append(Diff(DELETE, text1));
490 diffs.append(Diff(INSERT, text2));
491 return diffs;
492 }
493
diff_bisectSplit(const QString & text1,const QString & text2,int x,int y,clock_t deadline)494 QList<Diff> diff_match_patch::diff_bisectSplit(const QString &text1,
495 const QString &text2, int x, int y, clock_t deadline) {
496 QString text1a = text1.left(x);
497 QString text2a = text2.left(y);
498 QString text1b = safeMid(text1, x);
499 QString text2b = safeMid(text2, y);
500
501 // Compute both diffs serially.
502 QList<Diff> diffs = diff_main(text1a, text2a, false, deadline);
503 QList<Diff> diffsb = diff_main(text1b, text2b, false, deadline);
504
505 return diffs + diffsb;
506 }
507
diff_linesToChars(const QString & text1,const QString & text2)508 QList<QVariant> diff_match_patch::diff_linesToChars(const QString &text1,
509 const QString &text2) {
510 QStringList lineArray;
511 QMap<QString, int> lineHash;
512 // e.g. linearray[4] == "Hello\n"
513 // e.g. linehash.get("Hello\n") == 4
514
515 // "\x00" is a valid character, but various debuggers don't like it.
516 // So we'll insert a junk entry to avoid generating a null character.
517 lineArray.append("");
518
519 const QString chars1 = diff_linesToCharsMunge(text1, lineArray, lineHash);
520 const QString chars2 = diff_linesToCharsMunge(text2, lineArray, lineHash);
521
522 QList<QVariant> listRet;
523 listRet.append(QVariant::fromValue(chars1));
524 listRet.append(QVariant::fromValue(chars2));
525 listRet.append(QVariant::fromValue(lineArray));
526 return listRet;
527 }
528
529
diff_linesToCharsMunge(const QString & text,QStringList & lineArray,QMap<QString,int> & lineHash)530 QString diff_match_patch::diff_linesToCharsMunge(const QString &text,
531 QStringList &lineArray,
532 QMap<QString, int> &lineHash) {
533 int lineStart = 0;
534 int lineEnd = -1;
535 QString line;
536 QString chars;
537 // Walk the text, pulling out a substring for each line.
538 // text.split('\n') would would temporarily double our memory footprint.
539 // Modifying text would create many large strings to garbage collect.
540 while (lineEnd < text.length() - 1) {
541 lineEnd = text.indexOf('\n', lineStart);
542 if (lineEnd == -1) {
543 lineEnd = text.length() - 1;
544 }
545 line = safeMid(text, lineStart, lineEnd + 1 - lineStart);
546 lineStart = lineEnd + 1;
547
548 if (lineHash.contains(line)) {
549 chars += QChar(static_cast<ushort>(lineHash.value(line)));
550 } else {
551 lineArray.append(line);
552 lineHash.insert(line, lineArray.size() - 1);
553 chars += QChar(static_cast<ushort>(lineArray.size() - 1));
554 }
555 }
556 return chars;
557 }
558
559
560
diff_charsToLines(QList<Diff> & diffs,const QStringList & lineArray)561 void diff_match_patch::diff_charsToLines(QList<Diff> &diffs,
562 const QStringList &lineArray) {
563 // Qt has no mutable foreach construct.
564 QMutableListIterator<Diff> i(diffs);
565 while (i.hasNext()) {
566 Diff &diff = i.next();
567 QString text;
568 for (int y = 0; y < diff.text.length(); y++) {
569 text += lineArray.value(static_cast<ushort>(diff.text[y].unicode()));
570 }
571 diff.text = text;
572 }
573 }
574
575
diff_commonPrefix(const QString & text1,const QString & text2)576 int diff_match_patch::diff_commonPrefix(const QString &text1,
577 const QString &text2) {
578 // Performance analysis: http://neil.fraser.name/news/2007/10/09/
579 const int n = std::min(text1.length(), text2.length());
580 for (int i = 0; i < n; i++) {
581 if (text1[i] != text2[i]) {
582 return i;
583 }
584 }
585 return n;
586 }
587
588
diff_commonSuffix(const QString & text1,const QString & text2)589 int diff_match_patch::diff_commonSuffix(const QString &text1,
590 const QString &text2) {
591 // Performance analysis: http://neil.fraser.name/news/2007/10/09/
592 const int text1_length = text1.length();
593 const int text2_length = text2.length();
594 const int n = std::min(text1_length, text2_length);
595 for (int i = 1; i <= n; i++) {
596 if (text1[text1_length - i] != text2[text2_length - i]) {
597 return i - 1;
598 }
599 }
600 return n;
601 }
602
diff_commonOverlap(const QString & text1,const QString & text2)603 int diff_match_patch::diff_commonOverlap(const QString &text1,
604 const QString &text2) {
605 // Cache the text lengths to prevent multiple calls.
606 const int text1_length = text1.length();
607 const int text2_length = text2.length();
608 // Eliminate the null case.
609 if (text1_length == 0 || text2_length == 0) {
610 return 0;
611 }
612 // Truncate the longer string.
613 QString text1_trunc = text1;
614 QString text2_trunc = text2;
615 if (text1_length > text2_length) {
616 text1_trunc = text1.right(text2_length);
617 } else if (text1_length < text2_length) {
618 text2_trunc = text2.left(text1_length);
619 }
620 const int text_length = std::min(text1_length, text2_length);
621 // Quick check for the worst case.
622 if (text1_trunc == text2_trunc) {
623 return text_length;
624 }
625
626 // Start by looking for a single character match
627 // and increase length until no match is found.
628 // Performance analysis: http://neil.fraser.name/news/2010/11/04/
629 int best = 0;
630 int length = 1;
631 while (true) {
632 QString pattern = text1_trunc.right(length);
633 int found = text2_trunc.indexOf(pattern);
634 if (found == -1) {
635 return best;
636 }
637 length += found;
638 if (found == 0 || text1_trunc.right(length) == text2_trunc.left(length)) {
639 best = length;
640 length++;
641 }
642 }
643 }
644
diff_halfMatch(const QString & text1,const QString & text2)645 QStringList diff_match_patch::diff_halfMatch(const QString &text1,
646 const QString &text2) {
647 if (Diff_Timeout <= 0) {
648 // Don't risk returning a non-optimal diff if we have unlimited time.
649 return QStringList();
650 }
651 const QString longtext = text1.length() > text2.length() ? text1 : text2;
652 const QString shorttext = text1.length() > text2.length() ? text2 : text1;
653 if (longtext.length() < 4 || shorttext.length() * 2 < longtext.length()) {
654 return QStringList(); // Pointless.
655 }
656
657 // First check if the second quarter is the seed for a half-match.
658 const QStringList hm1 = diff_halfMatchI(longtext, shorttext,
659 (longtext.length() + 3) / 4);
660 // Check again based on the third quarter.
661 const QStringList hm2 = diff_halfMatchI(longtext, shorttext,
662 (longtext.length() + 1) / 2);
663 QStringList hm;
664 if (hm1.isEmpty() && hm2.isEmpty()) {
665 return QStringList();
666 } else if (hm2.isEmpty()) {
667 hm = hm1;
668 } else if (hm1.isEmpty()) {
669 hm = hm2;
670 } else {
671 // Both matched. Select the longest.
672 hm = hm1[4].length() > hm2[4].length() ? hm1 : hm2;
673 }
674
675 // A half-match was found, sort out the return data.
676 if (text1.length() > text2.length()) {
677 return hm;
678 } else {
679 QStringList listRet;
680 listRet << hm[2] << hm[3] << hm[0] << hm[1] << hm[4];
681 return listRet;
682 }
683 }
684
685
diff_halfMatchI(const QString & longtext,const QString & shorttext,int i)686 QStringList diff_match_patch::diff_halfMatchI(const QString &longtext,
687 const QString &shorttext,
688 int i) {
689 // Start with a 1/4 length substring at position i as a seed.
690 const QString seed = safeMid(longtext, i, longtext.length() / 4);
691 int j = -1;
692 QString best_common;
693 QString best_longtext_a, best_longtext_b;
694 QString best_shorttext_a, best_shorttext_b;
695 while ((j = shorttext.indexOf(seed, j + 1)) != -1) {
696 const int prefixLength = diff_commonPrefix(safeMid(longtext, i),
697 safeMid(shorttext, j));
698 const int suffixLength = diff_commonSuffix(longtext.left(i),
699 shorttext.left(j));
700 if (best_common.length() < suffixLength + prefixLength) {
701 best_common = safeMid(shorttext, j - suffixLength, suffixLength)
702 + safeMid(shorttext, j, prefixLength);
703 best_longtext_a = longtext.left(i - suffixLength);
704 best_longtext_b = safeMid(longtext, i + prefixLength);
705 best_shorttext_a = shorttext.left(j - suffixLength);
706 best_shorttext_b = safeMid(shorttext, j + prefixLength);
707 }
708 }
709 if (best_common.length() * 2 >= longtext.length()) {
710 QStringList listRet;
711 listRet << best_longtext_a << best_longtext_b << best_shorttext_a
712 << best_shorttext_b << best_common;
713 return listRet;
714 } else {
715 return QStringList();
716 }
717 }
718
719
diff_cleanupSemantic(QList<Diff> & diffs)720 void diff_match_patch::diff_cleanupSemantic(QList<Diff> &diffs) {
721 if (diffs.isEmpty()) {
722 return;
723 }
724 bool changes = false;
725 QStack<Diff> equalities; // Stack of equalities.
726 QString lastequality; // Always equal to equalities.lastElement().text
727 QMutableListIterator<Diff> pointer(diffs);
728 // Number of characters that changed prior to the equality.
729 int length_insertions1 = 0;
730 int length_deletions1 = 0;
731 // Number of characters that changed after the equality.
732 int length_insertions2 = 0;
733 int length_deletions2 = 0;
734 Diff *thisDiff = pointer.hasNext() ? &pointer.next() : NULL;
735 while (thisDiff != NULL) {
736 if (thisDiff->operation == EQUAL) {
737 // Equality found.
738 equalities.push(*thisDiff);
739 length_insertions1 = length_insertions2;
740 length_deletions1 = length_deletions2;
741 length_insertions2 = 0;
742 length_deletions2 = 0;
743 lastequality = thisDiff->text;
744 } else {
745 // An insertion or deletion.
746 if (thisDiff->operation == INSERT) {
747 length_insertions2 += thisDiff->text.length();
748 } else {
749 length_deletions2 += thisDiff->text.length();
750 }
751 // Eliminate an equality that is smaller or equal to the edits on both
752 // sides of it.
753 if (!lastequality.isNull()
754 && (lastequality.length()
755 <= std::max(length_insertions1, length_deletions1))
756 && (lastequality.length()
757 <= std::max(length_insertions2, length_deletions2))) {
758 // printf("Splitting: '%s'\n", qPrintable(lastequality));
759 // Walk back to offending equality.
760 while (*thisDiff != equalities.top()) {
761 thisDiff = &pointer.previous();
762 }
763 pointer.next();
764
765 // Replace equality with a delete.
766 pointer.setValue(Diff(DELETE, lastequality));
767 // Insert a corresponding an insert.
768 pointer.insert(Diff(INSERT, lastequality));
769
770 equalities.pop(); // Throw away the equality we just deleted.
771 if (!equalities.isEmpty()) {
772 // Throw away the previous equality (it needs to be reevaluated).
773 equalities.pop();
774 }
775 if (equalities.isEmpty()) {
776 // There are no previous equalities, walk back to the start.
777 while (pointer.hasPrevious()) {
778 pointer.previous();
779 }
780 } else {
781 // There is a safe equality we can fall back to.
782 thisDiff = &equalities.top();
783 while (*thisDiff != pointer.previous()) {
784 // Intentionally empty loop.
785 }
786 }
787
788 length_insertions1 = 0; // Reset the counters.
789 length_deletions1 = 0;
790 length_insertions2 = 0;
791 length_deletions2 = 0;
792 lastequality = QString();
793 changes = true;
794 }
795 }
796 thisDiff = pointer.hasNext() ? &pointer.next() : NULL;
797 }
798
799 // Normalize the diff.
800 if (changes) {
801 diff_cleanupMerge(diffs);
802 }
803 diff_cleanupSemanticLossless(diffs);
804
805 // Find any overlaps between deletions and insertions.
806 // e.g: <del>abcxxx</del><ins>xxxdef</ins>
807 // -> <del>abc</del>xxx<ins>def</ins>
808 // e.g: <del>xxxabc</del><ins>defxxx</ins>
809 // -> <ins>def</ins>xxx<del>abc</del>
810 // Only extract an overlap if it is as big as the edit ahead or behind it.
811 pointer.toFront();
812 Diff *prevDiff = NULL;
813 thisDiff = NULL;
814 if (pointer.hasNext()) {
815 prevDiff = &pointer.next();
816 if (pointer.hasNext()) {
817 thisDiff = &pointer.next();
818 }
819 }
820 while (thisDiff != NULL) {
821 if (prevDiff->operation == DELETE &&
822 thisDiff->operation == INSERT) {
823 QString deletion = prevDiff->text;
824 QString insertion = thisDiff->text;
825 int overlap_length1 = diff_commonOverlap(deletion, insertion);
826 int overlap_length2 = diff_commonOverlap(insertion, deletion);
827 if (overlap_length1 >= overlap_length2) {
828 if (overlap_length1 >= deletion.length() / 2.0 ||
829 overlap_length1 >= insertion.length() / 2.0) {
830 // Overlap found. Insert an equality and trim the surrounding edits.
831 pointer.previous();
832 pointer.insert(Diff(EQUAL, insertion.left(overlap_length1)));
833 prevDiff->text =
834 deletion.left(deletion.length() - overlap_length1);
835 thisDiff->text = safeMid(insertion, overlap_length1);
836 // pointer.insert inserts the element before the cursor, so there is
837 // no need to step past the new element.
838 }
839 } else {
840 if (overlap_length2 >= deletion.length() / 2.0 ||
841 overlap_length2 >= insertion.length() / 2.0) {
842 // Reverse overlap found.
843 // Insert an equality and swap and trim the surrounding edits.
844 pointer.previous();
845 pointer.insert(Diff(EQUAL, deletion.left(overlap_length2)));
846 prevDiff->operation = INSERT;
847 prevDiff->text =
848 insertion.left(insertion.length() - overlap_length2);
849 thisDiff->operation = DELETE;
850 thisDiff->text = safeMid(deletion, overlap_length2);
851 // pointer.insert inserts the element before the cursor, so there is
852 // no need to step past the new element.
853 }
854 }
855 thisDiff = pointer.hasNext() ? &pointer.next() : NULL;
856 }
857 prevDiff = thisDiff;
858 thisDiff = pointer.hasNext() ? &pointer.next() : NULL;
859 }
860 }
861
862
diff_cleanupSemanticLossless(QList<Diff> & diffs)863 void diff_match_patch::diff_cleanupSemanticLossless(QList<Diff> &diffs) {
864 QString equality1, edit, equality2;
865 QString commonString;
866 int commonOffset;
867 int score, bestScore;
868 QString bestEquality1, bestEdit, bestEquality2;
869 // Create a new iterator at the start.
870 QMutableListIterator<Diff> pointer(diffs);
871 Diff *prevDiff = pointer.hasNext() ? &pointer.next() : NULL;
872 Diff *thisDiff = pointer.hasNext() ? &pointer.next() : NULL;
873 Diff *nextDiff = pointer.hasNext() ? &pointer.next() : NULL;
874
875 // Intentionally ignore the first and last element (don't need checking).
876 while (nextDiff != NULL) {
877 if (prevDiff->operation == EQUAL &&
878 nextDiff->operation == EQUAL) {
879 // This is a single edit surrounded by equalities.
880 equality1 = prevDiff->text;
881 edit = thisDiff->text;
882 equality2 = nextDiff->text;
883
884 // First, shift the edit as far left as possible.
885 commonOffset = diff_commonSuffix(equality1, edit);
886 if (commonOffset != 0) {
887 commonString = safeMid(edit, edit.length() - commonOffset);
888 equality1 = equality1.left(equality1.length() - commonOffset);
889 edit = commonString + edit.left(edit.length() - commonOffset);
890 equality2 = commonString + equality2;
891 }
892
893 // Second, step character by character right, looking for the best fit.
894 bestEquality1 = equality1;
895 bestEdit = edit;
896 bestEquality2 = equality2;
897 bestScore = diff_cleanupSemanticScore(equality1, edit)
898 + diff_cleanupSemanticScore(edit, equality2);
899 while (!edit.isEmpty() && !equality2.isEmpty()
900 && edit[0] == equality2[0]) {
901 equality1 += edit[0];
902 edit = safeMid(edit, 1) + equality2[0];
903 equality2 = safeMid(equality2, 1);
904 score = diff_cleanupSemanticScore(equality1, edit)
905 + diff_cleanupSemanticScore(edit, equality2);
906 // The >= encourages trailing rather than leading whitespace on edits.
907 if (score >= bestScore) {
908 bestScore = score;
909 bestEquality1 = equality1;
910 bestEdit = edit;
911 bestEquality2 = equality2;
912 }
913 }
914
915 if (prevDiff->text != bestEquality1) {
916 // We have an improvement, save it back to the diff.
917 if (!bestEquality1.isEmpty()) {
918 prevDiff->text = bestEquality1;
919 } else {
920 pointer.previous(); // Walk past nextDiff.
921 pointer.previous(); // Walk past thisDiff.
922 pointer.previous(); // Walk past prevDiff.
923 pointer.remove(); // Delete prevDiff.
924 pointer.next(); // Walk past thisDiff.
925 pointer.next(); // Walk past nextDiff.
926 }
927 thisDiff->text = bestEdit;
928 if (!bestEquality2.isEmpty()) {
929 nextDiff->text = bestEquality2;
930 } else {
931 pointer.remove(); // Delete nextDiff.
932 nextDiff = thisDiff;
933 thisDiff = prevDiff;
934 }
935 }
936 }
937 prevDiff = thisDiff;
938 thisDiff = nextDiff;
939 nextDiff = pointer.hasNext() ? &pointer.next() : NULL;
940 }
941 }
942
943
diff_cleanupSemanticScore(const QString & one,const QString & two)944 int diff_match_patch::diff_cleanupSemanticScore(const QString &one,
945 const QString &two) {
946 if (one.isEmpty() || two.isEmpty()) {
947 // Edges are the best.
948 return 6;
949 }
950
951 // Each port of this function behaves slightly differently due to
952 // subtle differences in each language's definition of things like
953 // 'whitespace'. Since this function's purpose is largely cosmetic,
954 // the choice has been made to use each language's native features
955 // rather than force total conformity.
956 QChar char1 = one[one.length() - 1];
957 QChar char2 = two[0];
958 bool nonAlphaNumeric1 = !char1.isLetterOrNumber();
959 bool nonAlphaNumeric2 = !char2.isLetterOrNumber();
960 bool whitespace1 = nonAlphaNumeric1 && char1.isSpace();
961 bool whitespace2 = nonAlphaNumeric2 && char2.isSpace();
962 bool lineBreak1 = whitespace1 && char1.category() == QChar::Other_Control;
963 bool lineBreak2 = whitespace2 && char2.category() == QChar::Other_Control;
964 bool blankLine1 = lineBreak1 && BLANKLINEEND.indexIn(one) != -1;
965 bool blankLine2 = lineBreak2 && BLANKLINESTART.indexIn(two) != -1;
966
967 if (blankLine1 || blankLine2) {
968 // Five points for blank lines.
969 return 5;
970 } else if (lineBreak1 || lineBreak2) {
971 // Four points for line breaks.
972 return 4;
973 } else if (nonAlphaNumeric1 && !whitespace1 && whitespace2) {
974 // Three points for end of sentences.
975 return 3;
976 } else if (whitespace1 || whitespace2) {
977 // Two points for whitespace.
978 return 2;
979 } else if (nonAlphaNumeric1 || nonAlphaNumeric2) {
980 // One point for non-alphanumeric.
981 return 1;
982 }
983 return 0;
984 }
985
986
987 // Define some regex patterns for matching boundaries.
988 QRegExp diff_match_patch::BLANKLINEEND = QRegExp("\\n\\r?\\n$");
989 QRegExp diff_match_patch::BLANKLINESTART = QRegExp("^\\r?\\n\\r?\\n");
990
991
diff_cleanupEfficiency(QList<Diff> & diffs)992 void diff_match_patch::diff_cleanupEfficiency(QList<Diff> &diffs) {
993 if (diffs.isEmpty()) {
994 return;
995 }
996 bool changes = false;
997 QStack<Diff> equalities; // Stack of equalities.
998 QString lastequality; // Always equal to equalities.lastElement().text
999 QMutableListIterator<Diff> pointer(diffs);
1000 // Is there an insertion operation before the last equality.
1001 bool pre_ins = false;
1002 // Is there a deletion operation before the last equality.
1003 bool pre_del = false;
1004 // Is there an insertion operation after the last equality.
1005 bool post_ins = false;
1006 // Is there a deletion operation after the last equality.
1007 bool post_del = false;
1008
1009 Diff *thisDiff = pointer.hasNext() ? &pointer.next() : NULL;
1010 Diff *safeDiff = thisDiff;
1011
1012 while (thisDiff != NULL) {
1013 if (thisDiff->operation == EQUAL) {
1014 // Equality found.
1015 if (thisDiff->text.length() < Diff_EditCost && (post_ins || post_del)) {
1016 // Candidate found.
1017 equalities.push(*thisDiff);
1018 pre_ins = post_ins;
1019 pre_del = post_del;
1020 lastequality = thisDiff->text;
1021 } else {
1022 // Not a candidate, and can never become one.
1023 equalities.clear();
1024 lastequality = QString();
1025 safeDiff = thisDiff;
1026 }
1027 post_ins = post_del = false;
1028 } else {
1029 // An insertion or deletion.
1030 if (thisDiff->operation == DELETE) {
1031 post_del = true;
1032 } else {
1033 post_ins = true;
1034 }
1035 /*
1036 * Five types to be split:
1037 * <ins>A</ins><del>B</del>XY<ins>C</ins><del>D</del>
1038 * <ins>A</ins>X<ins>C</ins><del>D</del>
1039 * <ins>A</ins><del>B</del>X<ins>C</ins>
1040 * <ins>A</del>X<ins>C</ins><del>D</del>
1041 * <ins>A</ins><del>B</del>X<del>C</del>
1042 */
1043 if (!lastequality.isNull()
1044 && ((pre_ins && pre_del && post_ins && post_del)
1045 || ((lastequality.length() < Diff_EditCost / 2)
1046 && ((pre_ins ? 1 : 0) + (pre_del ? 1 : 0)
1047 + (post_ins ? 1 : 0) + (post_del ? 1 : 0)) == 3))) {
1048 // printf("Splitting: '%s'\n", qPrintable(lastequality));
1049 // Walk back to offending equality.
1050 while (*thisDiff != equalities.top()) {
1051 thisDiff = &pointer.previous();
1052 }
1053 pointer.next();
1054
1055 // Replace equality with a delete.
1056 pointer.setValue(Diff(DELETE, lastequality));
1057 // Insert a corresponding an insert.
1058 pointer.insert(Diff(INSERT, lastequality));
1059 thisDiff = &pointer.previous();
1060 pointer.next();
1061
1062 equalities.pop(); // Throw away the equality we just deleted.
1063 lastequality = QString();
1064 if (pre_ins && pre_del) {
1065 // No changes made which could affect previous entry, keep going.
1066 post_ins = post_del = true;
1067 equalities.clear();
1068 safeDiff = thisDiff;
1069 } else {
1070 if (!equalities.isEmpty()) {
1071 // Throw away the previous equality (it needs to be reevaluated).
1072 equalities.pop();
1073 }
1074 if (equalities.isEmpty()) {
1075 // There are no previous questionable equalities,
1076 // walk back to the last known safe diff.
1077 thisDiff = safeDiff;
1078 } else {
1079 // There is an equality we can fall back to.
1080 thisDiff = &equalities.top();
1081 }
1082 while (*thisDiff != pointer.previous()) {
1083 // Intentionally empty loop.
1084 }
1085 post_ins = post_del = false;
1086 }
1087
1088 changes = true;
1089 }
1090 }
1091 thisDiff = pointer.hasNext() ? &pointer.next() : NULL;
1092 }
1093
1094 if (changes) {
1095 diff_cleanupMerge(diffs);
1096 }
1097 }
1098
1099
diff_cleanupMerge(QList<Diff> & diffs)1100 void diff_match_patch::diff_cleanupMerge(QList<Diff> &diffs) {
1101 diffs.append(Diff(EQUAL, "")); // Add a dummy entry at the end.
1102 QMutableListIterator<Diff> pointer(diffs);
1103 int count_delete = 0;
1104 int count_insert = 0;
1105 QString text_delete = "";
1106 QString text_insert = "";
1107 Diff *thisDiff = pointer.hasNext() ? &pointer.next() : NULL;
1108 Diff *prevEqual = NULL;
1109 int commonlength;
1110 while (thisDiff != NULL) {
1111 switch (thisDiff->operation) {
1112 case INSERT:
1113 count_insert++;
1114 text_insert += thisDiff->text;
1115 prevEqual = NULL;
1116 break;
1117 case DELETE:
1118 count_delete++;
1119 text_delete += thisDiff->text;
1120 prevEqual = NULL;
1121 break;
1122 case EQUAL:
1123 if (count_delete + count_insert > 1) {
1124 bool both_types = count_delete != 0 && count_insert != 0;
1125 // Delete the offending records.
1126 pointer.previous(); // Reverse direction.
1127 while (count_delete-- > 0) {
1128 pointer.previous();
1129 pointer.remove();
1130 }
1131 while (count_insert-- > 0) {
1132 pointer.previous();
1133 pointer.remove();
1134 }
1135 if (both_types) {
1136 // Factor out any common prefixies.
1137 commonlength = diff_commonPrefix(text_insert, text_delete);
1138 if (commonlength != 0) {
1139 if (pointer.hasPrevious()) {
1140 thisDiff = &pointer.previous();
1141 if (thisDiff->operation != EQUAL) {
1142 throw "Previous diff should have been an equality.";
1143 }
1144 thisDiff->text += text_insert.left(commonlength);
1145 pointer.next();
1146 } else {
1147 pointer.insert(Diff(EQUAL, text_insert.left(commonlength)));
1148 }
1149 text_insert = safeMid(text_insert, commonlength);
1150 text_delete = safeMid(text_delete, commonlength);
1151 }
1152 // Factor out any common suffixies.
1153 commonlength = diff_commonSuffix(text_insert, text_delete);
1154 if (commonlength != 0) {
1155 thisDiff = &pointer.next();
1156 thisDiff->text = safeMid(text_insert, text_insert.length()
1157 - commonlength) + thisDiff->text;
1158 text_insert = text_insert.left(text_insert.length()
1159 - commonlength);
1160 text_delete = text_delete.left(text_delete.length()
1161 - commonlength);
1162 pointer.previous();
1163 }
1164 }
1165 // Insert the merged records.
1166 if (!text_delete.isEmpty()) {
1167 pointer.insert(Diff(DELETE, text_delete));
1168 }
1169 if (!text_insert.isEmpty()) {
1170 pointer.insert(Diff(INSERT, text_insert));
1171 }
1172 // Step forward to the equality.
1173 thisDiff = pointer.hasNext() ? &pointer.next() : NULL;
1174
1175 } else if (prevEqual != NULL) {
1176 // Merge this equality with the previous one.
1177 prevEqual->text += thisDiff->text;
1178 pointer.remove();
1179 thisDiff = &pointer.previous();
1180 pointer.next(); // Forward direction
1181 }
1182 count_insert = 0;
1183 count_delete = 0;
1184 text_delete = "";
1185 text_insert = "";
1186 prevEqual = thisDiff;
1187 break;
1188 }
1189 thisDiff = pointer.hasNext() ? &pointer.next() : NULL;
1190 }
1191 if (diffs.back().text.isEmpty()) {
1192 diffs.removeLast(); // Remove the dummy entry at the end.
1193 }
1194
1195 /*
1196 * Second pass: look for single edits surrounded on both sides by equalities
1197 * which can be shifted sideways to eliminate an equality.
1198 * e.g: A<ins>BA</ins>C -> <ins>AB</ins>AC
1199 */
1200 bool changes = false;
1201 // Create a new iterator at the start.
1202 // (As opposed to walking the current one back.)
1203 pointer.toFront();
1204 Diff *prevDiff = pointer.hasNext() ? &pointer.next() : NULL;
1205 thisDiff = pointer.hasNext() ? &pointer.next() : NULL;
1206 Diff *nextDiff = pointer.hasNext() ? &pointer.next() : NULL;
1207
1208 // Intentionally ignore the first and last element (don't need checking).
1209 while (nextDiff != NULL) {
1210 if (prevDiff->operation == EQUAL &&
1211 nextDiff->operation == EQUAL) {
1212 // This is a single edit surrounded by equalities.
1213 if (thisDiff->text.endsWith(prevDiff->text)) {
1214 // Shift the edit over the previous equality.
1215 thisDiff->text = prevDiff->text
1216 + thisDiff->text.left(thisDiff->text.length()
1217 - prevDiff->text.length());
1218 nextDiff->text = prevDiff->text + nextDiff->text;
1219 pointer.previous(); // Walk past nextDiff.
1220 pointer.previous(); // Walk past thisDiff.
1221 pointer.previous(); // Walk past prevDiff.
1222 pointer.remove(); // Delete prevDiff.
1223 pointer.next(); // Walk past thisDiff.
1224 thisDiff = &pointer.next(); // Walk past nextDiff.
1225 nextDiff = pointer.hasNext() ? &pointer.next() : NULL;
1226 changes = true;
1227 } else if (thisDiff->text.startsWith(nextDiff->text)) {
1228 // Shift the edit over the next equality.
1229 prevDiff->text += nextDiff->text;
1230 thisDiff->text = safeMid(thisDiff->text, nextDiff->text.length())
1231 + nextDiff->text;
1232 pointer.remove(); // Delete nextDiff.
1233 nextDiff = pointer.hasNext() ? &pointer.next() : NULL;
1234 changes = true;
1235 }
1236 }
1237 prevDiff = thisDiff;
1238 thisDiff = nextDiff;
1239 nextDiff = pointer.hasNext() ? &pointer.next() : NULL;
1240 }
1241 // If shifts were made, the diff needs reordering and another shift sweep.
1242 if (changes) {
1243 diff_cleanupMerge(diffs);
1244 }
1245 }
1246
1247
diff_xIndex(const QList<Diff> & diffs,int loc)1248 int diff_match_patch::diff_xIndex(const QList<Diff> &diffs, int loc) {
1249 int chars1 = 0;
1250 int chars2 = 0;
1251 int last_chars1 = 0;
1252 int last_chars2 = 0;
1253 Diff lastDiff;
1254 for (Diff aDiff : diffs) {
1255 if (aDiff.operation != INSERT) {
1256 // Equality or deletion.
1257 chars1 += aDiff.text.length();
1258 }
1259 if (aDiff.operation != DELETE) {
1260 // Equality or insertion.
1261 chars2 += aDiff.text.length();
1262 }
1263 if (chars1 > loc) {
1264 // Overshot the location.
1265 lastDiff = aDiff;
1266 break;
1267 }
1268 last_chars1 = chars1;
1269 last_chars2 = chars2;
1270 }
1271 if (lastDiff.operation == DELETE) {
1272 // The location was deleted.
1273 return last_chars2;
1274 }
1275 // Add the remaining character length.
1276 return last_chars2 + (loc - last_chars1);
1277 }
1278
1279
diff_prettyHtml(const QList<Diff> & diffs)1280 QString diff_match_patch::diff_prettyHtml(const QList<Diff> &diffs) {
1281 QString html;
1282 QString text;
1283 for (Diff aDiff : diffs) {
1284 text = aDiff.text;
1285 text.replace("&", "&").replace("<", "<")
1286 .replace(">", ">").replace("\n", "¶<br>");
1287 switch (aDiff.operation) {
1288 case INSERT:
1289 html += QString("<ins style=\"background:#e6ffe6;\">") + text
1290 + QString("</ins>");
1291 break;
1292 case DELETE:
1293 html += QString("<del style=\"background:#ffe6e6;\">") + text
1294 + QString("</del>");
1295 break;
1296 case EQUAL:
1297 html += QString("<span>") + text + QString("</span>");
1298 break;
1299 }
1300 }
1301 return html;
1302 }
1303
1304
diff_text1(const QList<Diff> & diffs)1305 QString diff_match_patch::diff_text1(const QList<Diff> &diffs) {
1306 QString text;
1307 for (Diff aDiff : diffs) {
1308 if (aDiff.operation != INSERT) {
1309 text += aDiff.text;
1310 }
1311 }
1312 return text;
1313 }
1314
1315
diff_text2(const QList<Diff> & diffs)1316 QString diff_match_patch::diff_text2(const QList<Diff> &diffs) {
1317 QString text;
1318 for (Diff aDiff : diffs) {
1319 if (aDiff.operation != DELETE) {
1320 text += aDiff.text;
1321 }
1322 }
1323 return text;
1324 }
1325
1326
diff_levenshtein(const QList<Diff> & diffs)1327 int diff_match_patch::diff_levenshtein(const QList<Diff> &diffs) {
1328 int levenshtein = 0;
1329 int insertions = 0;
1330 int deletions = 0;
1331 for (Diff aDiff : diffs) {
1332 switch (aDiff.operation) {
1333 case INSERT:
1334 insertions += aDiff.text.length();
1335 break;
1336 case DELETE:
1337 deletions += aDiff.text.length();
1338 break;
1339 case EQUAL:
1340 // A deletion and an insertion is one substitution.
1341 levenshtein += std::max(insertions, deletions);
1342 insertions = 0;
1343 deletions = 0;
1344 break;
1345 }
1346 }
1347 levenshtein += std::max(insertions, deletions);
1348 return levenshtein;
1349 }
1350
1351
diff_toDelta(const QList<Diff> & diffs)1352 QString diff_match_patch::diff_toDelta(const QList<Diff> &diffs) {
1353 QString text;
1354 for (Diff aDiff : diffs) {
1355 switch (aDiff.operation) {
1356 case INSERT: {
1357 QString encoded = QString(QUrl::toPercentEncoding(aDiff.text,
1358 " !~*'();/?:@&=+$,#"));
1359 text += QString("+") + encoded + QString("\t");
1360 break;
1361 }
1362 case DELETE:
1363 text += QString("-") + QString::number(aDiff.text.length())
1364 + QString("\t");
1365 break;
1366 case EQUAL:
1367 text += QString("=") + QString::number(aDiff.text.length())
1368 + QString("\t");
1369 break;
1370 }
1371 }
1372 if (!text.isEmpty()) {
1373 // Strip off trailing tab character.
1374 text = text.left(text.length() - 1);
1375 }
1376 return text;
1377 }
1378
1379
diff_fromDelta(const QString & text1,const QString & delta)1380 QList<Diff> diff_match_patch::diff_fromDelta(const QString &text1,
1381 const QString &delta) {
1382 QList<Diff> diffs;
1383 int pointer = 0; // Cursor in text1
1384 QStringList tokens = delta.split("\t");
1385 for (QString token : tokens) {
1386 if (token.isEmpty()) {
1387 // Blank tokens are ok (from a trailing \t).
1388 continue;
1389 }
1390 // Each token begins with a one character parameter which specifies the
1391 // operation of this token (delete, insert, equality).
1392 QString param = safeMid(token, 1);
1393 switch (token[0].toLatin1()) {
1394 case '+':
1395 param = QUrl::fromPercentEncoding(qPrintable(param));
1396 diffs.append(Diff(INSERT, param));
1397 break;
1398 case '-':
1399 // Fall through.
1400 case '=': {
1401 int n;
1402 n = param.toInt();
1403 if (n < 0) {
1404 throw QString("Negative number in diff_fromDelta: %1").arg(param);
1405 }
1406 QString text;
1407 text = safeMid(text1, pointer, n);
1408 pointer += n;
1409 if (token[0] == QChar('=')) {
1410 diffs.append(Diff(EQUAL, text));
1411 } else {
1412 diffs.append(Diff(DELETE, text));
1413 }
1414 break;
1415 }
1416 default:
1417 throw QString("Invalid diff operation in diff_fromDelta: %1")
1418 .arg(token[0]);
1419 }
1420 }
1421 if (pointer != text1.length()) {
1422 throw QString("Delta length (%1) smaller than source text length (%2)")
1423 .arg(pointer).arg(text1.length());
1424 }
1425 return diffs;
1426 }
1427
1428
1429 // MATCH FUNCTIONS
1430
1431
match_main(const QString & text,const QString & pattern,int loc)1432 int diff_match_patch::match_main(const QString &text, const QString &pattern,
1433 int loc) {
1434 // Check for null inputs.
1435 if (text.isNull() || pattern.isNull()) {
1436 throw "Null inputs. (match_main)";
1437 }
1438
1439 loc = std::max(0, std::min(loc, text.length()));
1440 if (text == pattern) {
1441 // Shortcut (potentially not guaranteed by the algorithm)
1442 return 0;
1443 } else if (text.isEmpty()) {
1444 // Nothing to match.
1445 return -1;
1446 } else if (loc + pattern.length() <= text.length()
1447 && safeMid(text, loc, pattern.length()) == pattern) {
1448 // Perfect match at the perfect spot! (Includes case of null pattern)
1449 return loc;
1450 } else {
1451 // Do a fuzzy compare.
1452 return match_bitap(text, pattern, loc);
1453 }
1454 }
1455
1456
match_bitap(const QString & text,const QString & pattern,int loc)1457 int diff_match_patch::match_bitap(const QString &text, const QString &pattern,
1458 int loc) {
1459 if (!(Match_MaxBits == 0 || pattern.length() <= Match_MaxBits)) {
1460 throw "Pattern too long for this application.";
1461 }
1462
1463 // Initialise the alphabet.
1464 QMap<QChar, int> s = match_alphabet(pattern);
1465
1466 // Highest score beyond which we give up.
1467 double score_threshold = Match_Threshold;
1468 // Is there a nearby exact match? (speedup)
1469 int best_loc = text.indexOf(pattern, loc);
1470 if (best_loc != -1) {
1471 score_threshold = std::min(match_bitapScore(0, best_loc, loc, pattern),
1472 score_threshold);
1473 // What about in the other direction? (speedup)
1474 best_loc = text.lastIndexOf(pattern, loc + pattern.length());
1475 if (best_loc != -1) {
1476 score_threshold = std::min(match_bitapScore(0, best_loc, loc, pattern),
1477 score_threshold);
1478 }
1479 }
1480
1481 // Initialise the bit arrays.
1482 int matchmask = 1 << (pattern.length() - 1);
1483 best_loc = -1;
1484
1485 int bin_min, bin_mid;
1486 int bin_max = pattern.length() + text.length();
1487 int *rd;
1488 int *last_rd = NULL;
1489 for (int d = 0; d < pattern.length(); d++) {
1490 // Scan for the best match; each iteration allows for one more error.
1491 // Run a binary search to determine how far from 'loc' we can stray at
1492 // this error level.
1493 bin_min = 0;
1494 bin_mid = bin_max;
1495 while (bin_min < bin_mid) {
1496 if (match_bitapScore(d, loc + bin_mid, loc, pattern)
1497 <= score_threshold) {
1498 bin_min = bin_mid;
1499 } else {
1500 bin_max = bin_mid;
1501 }
1502 bin_mid = (bin_max - bin_min) / 2 + bin_min;
1503 }
1504 // Use the result from this iteration as the maximum for the next.
1505 bin_max = bin_mid;
1506 int start = std::max(1, loc - bin_mid + 1);
1507 int finish = std::min(loc + bin_mid, text.length()) + pattern.length();
1508
1509 rd = new int[finish + 2];
1510 rd[finish + 1] = (1 << d) - 1;
1511 for (int j = finish; j >= start; j--) {
1512 int charMatch;
1513 if (text.length() <= j - 1) {
1514 // Out of range.
1515 charMatch = 0;
1516 } else {
1517 charMatch = s.value(text[j - 1], 0);
1518 }
1519 if (d == 0) {
1520 // First pass: exact match.
1521 rd[j] = ((rd[j + 1] << 1) | 1) & charMatch;
1522 } else {
1523 // Subsequent passes: fuzzy match.
1524 rd[j] = (((rd[j + 1] << 1) | 1) & charMatch)
1525 | (((last_rd[j + 1] | last_rd[j]) << 1) | 1)
1526 | last_rd[j + 1];
1527 }
1528 if ((rd[j] & matchmask) != 0) {
1529 double score = match_bitapScore(d, j - 1, loc, pattern);
1530 // This match will almost certainly be better than any existing
1531 // match. But check anyway.
1532 if (score <= score_threshold) {
1533 // Told you so.
1534 score_threshold = score;
1535 best_loc = j - 1;
1536 if (best_loc > loc) {
1537 // When passing loc, don't exceed our current distance from loc.
1538 start = std::max(1, 2 * loc - best_loc);
1539 } else {
1540 // Already passed loc, downhill from here on in.
1541 break;
1542 }
1543 }
1544 }
1545 }
1546 if (match_bitapScore(d + 1, loc, loc, pattern) > score_threshold) {
1547 // No hope for a (better) match at greater error levels.
1548 break;
1549 }
1550 delete [] last_rd;
1551 last_rd = rd;
1552 }
1553 delete [] last_rd;
1554 delete [] rd;
1555 return best_loc;
1556 }
1557
1558
match_bitapScore(int e,int x,int loc,const QString & pattern)1559 double diff_match_patch::match_bitapScore(int e, int x, int loc,
1560 const QString &pattern) {
1561 const float accuracy = static_cast<float> (e) / pattern.length();
1562 const int proximity = qAbs(loc - x);
1563 if (Match_Distance == 0) {
1564 // Dodge divide by zero error.
1565 return proximity == 0 ? accuracy : 1.0;
1566 }
1567 return accuracy + (proximity / static_cast<float> (Match_Distance));
1568 }
1569
1570
match_alphabet(const QString & pattern)1571 QMap<QChar, int> diff_match_patch::match_alphabet(const QString &pattern) {
1572 QMap<QChar, int> s;
1573 int i;
1574 for (i = 0; i < pattern.length(); i++) {
1575 QChar c = pattern[i];
1576 s.insert(c, 0);
1577 }
1578 for (i = 0; i < pattern.length(); i++) {
1579 QChar c = pattern[i];
1580 s.insert(c, s.value(c) | (1 << (pattern.length() - i - 1)));
1581 }
1582 return s;
1583 }
1584
1585
1586 // PATCH FUNCTIONS
1587
1588
patch_addContext(Patch & patch,const QString & text)1589 void diff_match_patch::patch_addContext(Patch &patch, const QString &text) {
1590 if (text.isEmpty()) {
1591 return;
1592 }
1593 QString pattern = safeMid(text, patch.start2, patch.length1);
1594 int padding = 0;
1595
1596 // Look for the first and last matches of pattern in text. If two different
1597 // matches are found, increase the pattern length.
1598 while (text.indexOf(pattern) != text.lastIndexOf(pattern)
1599 && pattern.length() < Match_MaxBits - Patch_Margin - Patch_Margin) {
1600 padding += Patch_Margin;
1601 pattern = safeMid(text, std::max(0, patch.start2 - padding),
1602 std::min(text.length(), patch.start2 + patch.length1 + padding)
1603 - std::max(0, patch.start2 - padding));
1604 }
1605 // Add one chunk for good luck.
1606 padding += Patch_Margin;
1607
1608 // Add the prefix.
1609 QString prefix = safeMid(text, std::max(0, patch.start2 - padding),
1610 patch.start2 - std::max(0, patch.start2 - padding));
1611 if (!prefix.isEmpty()) {
1612 patch.diffs.prepend(Diff(EQUAL, prefix));
1613 }
1614 // Add the suffix.
1615 QString suffix = safeMid(text, patch.start2 + patch.length1,
1616 std::min(text.length(), patch.start2 + patch.length1 + padding)
1617 - (patch.start2 + patch.length1));
1618 if (!suffix.isEmpty()) {
1619 patch.diffs.append(Diff(EQUAL, suffix));
1620 }
1621
1622 // Roll back the start points.
1623 patch.start1 -= prefix.length();
1624 patch.start2 -= prefix.length();
1625 // Extend the lengths.
1626 patch.length1 += prefix.length() + suffix.length();
1627 patch.length2 += prefix.length() + suffix.length();
1628 }
1629
1630
patch_make(const QString & text1,const QString & text2)1631 QList<Patch> diff_match_patch::patch_make(const QString &text1,
1632 const QString &text2) {
1633 // Check for null inputs.
1634 if (text1.isNull() || text2.isNull()) {
1635 throw "Null inputs. (patch_make)";
1636 }
1637
1638 // No diffs provided, compute our own.
1639 QList<Diff> diffs = diff_main(text1, text2, true);
1640 if (diffs.size() > 2) {
1641 diff_cleanupSemantic(diffs);
1642 diff_cleanupEfficiency(diffs);
1643 }
1644
1645 return patch_make(text1, diffs);
1646 }
1647
1648
patch_make(const QList<Diff> & diffs)1649 QList<Patch> diff_match_patch::patch_make(const QList<Diff> &diffs) {
1650 // No origin string provided, compute our own.
1651 const QString text1 = diff_text1(diffs);
1652 return patch_make(text1, diffs);
1653 }
1654
1655
patch_make(const QString & text1,const QString & text2,const QList<Diff> & diffs)1656 QList<Patch> diff_match_patch::patch_make(const QString &text1,
1657 const QString &text2,
1658 const QList<Diff> &diffs) {
1659 // text2 is entirely unused.
1660 return patch_make(text1, diffs);
1661
1662 Q_UNUSED(text2)
1663 }
1664
1665
patch_make(const QString & text1,const QList<Diff> & diffs)1666 QList<Patch> diff_match_patch::patch_make(const QString &text1,
1667 const QList<Diff> &diffs) {
1668 // Check for null inputs.
1669 if (text1.isNull()) {
1670 throw "Null inputs. (patch_make)";
1671 }
1672
1673 QList<Patch> patches;
1674 if (diffs.isEmpty()) {
1675 return patches; // Get rid of the null case.
1676 }
1677 Patch patch;
1678 int char_count1 = 0; // Number of characters into the text1 string.
1679 int char_count2 = 0; // Number of characters into the text2 string.
1680 // Start with text1 (prepatch_text) and apply the diffs until we arrive at
1681 // text2 (postpatch_text). We recreate the patches one by one to determine
1682 // context info.
1683 QString prepatch_text = text1;
1684 QString postpatch_text = text1;
1685 for (Diff aDiff : diffs) {
1686 if (patch.diffs.isEmpty() && aDiff.operation != EQUAL) {
1687 // A new patch starts here.
1688 patch.start1 = char_count1;
1689 patch.start2 = char_count2;
1690 }
1691
1692 switch (aDiff.operation) {
1693 case INSERT:
1694 patch.diffs.append(aDiff);
1695 patch.length2 += aDiff.text.length();
1696 postpatch_text = postpatch_text.left(char_count2)
1697 + aDiff.text + safeMid(postpatch_text, char_count2);
1698 break;
1699 case DELETE:
1700 patch.length1 += aDiff.text.length();
1701 patch.diffs.append(aDiff);
1702 postpatch_text = postpatch_text.left(char_count2)
1703 + safeMid(postpatch_text, char_count2 + aDiff.text.length());
1704 break;
1705 case EQUAL:
1706 if (aDiff.text.length() <= 2 * Patch_Margin
1707 && !patch.diffs.isEmpty() && !(aDiff == diffs.back())) {
1708 // Small equality inside a patch.
1709 patch.diffs.append(aDiff);
1710 patch.length1 += aDiff.text.length();
1711 patch.length2 += aDiff.text.length();
1712 }
1713
1714 if (aDiff.text.length() >= 2 * Patch_Margin) {
1715 // Time for a new patch.
1716 if (!patch.diffs.isEmpty()) {
1717 patch_addContext(patch, prepatch_text);
1718 patches.append(patch);
1719 patch = Patch();
1720 // Unlike Unidiff, our patch lists have a rolling context.
1721 // http://code.google.com/p/google-diff-match-patch/wiki/Unidiff
1722 // Update prepatch text & pos to reflect the application of the
1723 // just completed patch.
1724 prepatch_text = postpatch_text;
1725 char_count1 = char_count2;
1726 }
1727 }
1728 break;
1729 }
1730
1731 // Update the current character count.
1732 if (aDiff.operation != INSERT) {
1733 char_count1 += aDiff.text.length();
1734 }
1735 if (aDiff.operation != DELETE) {
1736 char_count2 += aDiff.text.length();
1737 }
1738 }
1739 // Pick up the leftover patch if not empty.
1740 if (!patch.diffs.isEmpty()) {
1741 patch_addContext(patch, prepatch_text);
1742 patches.append(patch);
1743 }
1744
1745 return patches;
1746 }
1747
1748
patch_deepCopy(QList<Patch> & patches)1749 QList<Patch> diff_match_patch::patch_deepCopy(QList<Patch> &patches) {
1750 QList<Patch> patchesCopy;
1751 for (Patch aPatch : patches) {
1752 Patch patchCopy = Patch();
1753 for (Diff aDiff : aPatch.diffs) {
1754 Diff diffCopy = Diff(aDiff.operation, aDiff.text);
1755 patchCopy.diffs.append(diffCopy);
1756 }
1757 patchCopy.start1 = aPatch.start1;
1758 patchCopy.start2 = aPatch.start2;
1759 patchCopy.length1 = aPatch.length1;
1760 patchCopy.length2 = aPatch.length2;
1761 patchesCopy.append(patchCopy);
1762 }
1763 return patchesCopy;
1764 }
1765
1766
patch_apply(QList<Patch> & patches,const QString & sourceText)1767 QPair<QString, QVector<bool> > diff_match_patch::patch_apply(
1768 QList<Patch> &patches, const QString &sourceText) {
1769 QString text = sourceText; // Copy to preserve original.
1770 if (patches.isEmpty()) {
1771 return QPair<QString,QVector<bool> >(text, QVector<bool>(0));
1772 }
1773
1774 // Deep copy the patches so that no changes are made to originals.
1775 QList<Patch> patchesCopy = patch_deepCopy(patches);
1776
1777 QString nullPadding = patch_addPadding(patchesCopy);
1778 text = nullPadding + text + nullPadding;
1779 patch_splitMax(patchesCopy);
1780
1781 int x = 0;
1782 // delta keeps track of the offset between the expected and actual location
1783 // of the previous patch. If there are patches expected at positions 10 and
1784 // 20, but the first patch was found at 12, delta is 2 and the second patch
1785 // has an effective expected position of 22.
1786 int delta = 0;
1787 QVector<bool> results(patchesCopy.size());
1788 for (Patch aPatch : patchesCopy) {
1789 int expected_loc = aPatch.start2 + delta;
1790 QString text1 = diff_text1(aPatch.diffs);
1791 int start_loc;
1792 int end_loc = -1;
1793 if (text1.length() > Match_MaxBits) {
1794 // patch_splitMax will only provide an oversized pattern in the case of
1795 // a monster delete.
1796 start_loc = match_main(text, text1.left(Match_MaxBits), expected_loc);
1797 if (start_loc != -1) {
1798 end_loc = match_main(text, text1.right(Match_MaxBits),
1799 expected_loc + text1.length() - Match_MaxBits);
1800 if (end_loc == -1 || start_loc >= end_loc) {
1801 // Can't find valid trailing context. Drop this patch.
1802 start_loc = -1;
1803 }
1804 }
1805 } else {
1806 start_loc = match_main(text, text1, expected_loc);
1807 }
1808 if (start_loc == -1) {
1809 // No match found. :(
1810 results[x] = false;
1811 // Subtract the delta for this failed patch from subsequent patches.
1812 delta -= aPatch.length2 - aPatch.length1;
1813 } else {
1814 // Found a match. :)
1815 results[x] = true;
1816 delta = start_loc - expected_loc;
1817 QString text2;
1818 if (end_loc == -1) {
1819 text2 = safeMid(text, start_loc, text1.length());
1820 } else {
1821 text2 = safeMid(text, start_loc, end_loc + Match_MaxBits - start_loc);
1822 }
1823 if (text1 == text2) {
1824 // Perfect match, just shove the replacement text in.
1825 text = text.left(start_loc) + diff_text2(aPatch.diffs)
1826 + safeMid(text, start_loc + text1.length());
1827 } else {
1828 // Imperfect match. Run a diff to get a framework of equivalent
1829 // indices.
1830 QList<Diff> diffs = diff_main(text1, text2, false);
1831 if (text1.length() > Match_MaxBits
1832 && diff_levenshtein(diffs) / static_cast<float> (text1.length())
1833 > Patch_DeleteThreshold) {
1834 // The end points match, but the content is unacceptably bad.
1835 results[x] = false;
1836 } else {
1837 diff_cleanupSemanticLossless(diffs);
1838 int index1 = 0;
1839 for (Diff aDiff : aPatch.diffs) {
1840 if (aDiff.operation != EQUAL) {
1841 int index2 = diff_xIndex(diffs, index1);
1842 if (aDiff.operation == INSERT) {
1843 // Insertion
1844 text = text.left(start_loc + index2) + aDiff.text
1845 + safeMid(text, start_loc + index2);
1846 } else if (aDiff.operation == DELETE) {
1847 // Deletion
1848 text = text.left(start_loc + index2)
1849 + safeMid(text, start_loc + diff_xIndex(diffs,
1850 index1 + aDiff.text.length()));
1851 }
1852 }
1853 if (aDiff.operation != DELETE) {
1854 index1 += aDiff.text.length();
1855 }
1856 }
1857 }
1858 }
1859 }
1860 x++;
1861 }
1862 // Strip the padding off.
1863 text = safeMid(text, nullPadding.length(), text.length()
1864 - 2 * nullPadding.length());
1865 return QPair<QString, QVector<bool> >(text, results);
1866 }
1867
1868
patch_addPadding(QList<Patch> & patches)1869 QString diff_match_patch::patch_addPadding(QList<Patch> &patches) {
1870 short paddingLength = Patch_Margin;
1871 QString nullPadding = "";
1872 for (short x = 1; x <= paddingLength; x++) {
1873 nullPadding += QChar((ushort)x);
1874 }
1875
1876 // Bump all the patches forward.
1877 QMutableListIterator<Patch> pointer(patches);
1878 while (pointer.hasNext()) {
1879 Patch &aPatch = pointer.next();
1880 aPatch.start1 += paddingLength;
1881 aPatch.start2 += paddingLength;
1882 }
1883
1884 // Add some padding on start of first diff.
1885 Patch &firstPatch = patches.first();
1886 QList<Diff> &firstPatchDiffs = firstPatch.diffs;
1887 if (firstPatchDiffs.empty() || firstPatchDiffs.first().operation != EQUAL) {
1888 // Add nullPadding equality.
1889 firstPatchDiffs.prepend(Diff(EQUAL, nullPadding));
1890 firstPatch.start1 -= paddingLength; // Should be 0.
1891 firstPatch.start2 -= paddingLength; // Should be 0.
1892 firstPatch.length1 += paddingLength;
1893 firstPatch.length2 += paddingLength;
1894 } else if (paddingLength > firstPatchDiffs.first().text.length()) {
1895 // Grow first equality.
1896 Diff &firstDiff = firstPatchDiffs.first();
1897 int extraLength = paddingLength - firstDiff.text.length();
1898 firstDiff.text = safeMid(nullPadding, firstDiff.text.length(),
1899 paddingLength - firstDiff.text.length()) + firstDiff.text;
1900 firstPatch.start1 -= extraLength;
1901 firstPatch.start2 -= extraLength;
1902 firstPatch.length1 += extraLength;
1903 firstPatch.length2 += extraLength;
1904 }
1905
1906 // Add some padding on end of last diff.
1907 Patch &lastPatch = patches.first();
1908 QList<Diff> &lastPatchDiffs = lastPatch.diffs;
1909 if (lastPatchDiffs.empty() || lastPatchDiffs.last().operation != EQUAL) {
1910 // Add nullPadding equality.
1911 lastPatchDiffs.append(Diff(EQUAL, nullPadding));
1912 lastPatch.length1 += paddingLength;
1913 lastPatch.length2 += paddingLength;
1914 } else if (paddingLength > lastPatchDiffs.last().text.length()) {
1915 // Grow last equality.
1916 Diff &lastDiff = lastPatchDiffs.last();
1917 int extraLength = paddingLength - lastDiff.text.length();
1918 lastDiff.text += nullPadding.left(extraLength);
1919 lastPatch.length1 += extraLength;
1920 lastPatch.length2 += extraLength;
1921 }
1922
1923 return nullPadding;
1924 }
1925
1926
patch_splitMax(QList<Patch> & patches)1927 void diff_match_patch::patch_splitMax(QList<Patch> &patches) {
1928 short patch_size = Match_MaxBits;
1929 QString precontext, postcontext;
1930 Patch patch;
1931 int start1, start2;
1932 bool empty;
1933 Operation diff_type;
1934 QString diff_text;
1935 QMutableListIterator<Patch> pointer(patches);
1936 Patch bigpatch;
1937
1938 if (pointer.hasNext()) {
1939 bigpatch = pointer.next();
1940 }
1941
1942 while (!bigpatch.isNull()) {
1943 if (bigpatch.length1 <= patch_size) {
1944 bigpatch = pointer.hasNext() ? pointer.next() : Patch();
1945 continue;
1946 }
1947 // Remove the big old patch.
1948 pointer.remove();
1949 start1 = bigpatch.start1;
1950 start2 = bigpatch.start2;
1951 precontext = "";
1952 while (!bigpatch.diffs.isEmpty()) {
1953 // Create one of several smaller patches.
1954 patch = Patch();
1955 empty = true;
1956 patch.start1 = start1 - precontext.length();
1957 patch.start2 = start2 - precontext.length();
1958 if (!precontext.isEmpty()) {
1959 patch.length1 = patch.length2 = precontext.length();
1960 patch.diffs.append(Diff(EQUAL, precontext));
1961 }
1962 while (!bigpatch.diffs.isEmpty()
1963 && patch.length1 < patch_size - Patch_Margin) {
1964 diff_type = bigpatch.diffs.front().operation;
1965 diff_text = bigpatch.diffs.front().text;
1966 if (diff_type == INSERT) {
1967 // Insertions are harmless.
1968 patch.length2 += diff_text.length();
1969 start2 += diff_text.length();
1970 patch.diffs.append(bigpatch.diffs.front());
1971 bigpatch.diffs.removeFirst();
1972 empty = false;
1973 } else if (diff_type == DELETE && patch.diffs.size() == 1
1974 && patch.diffs.front().operation == EQUAL
1975 && diff_text.length() > 2 * patch_size) {
1976 // This is a large deletion. Let it pass in one chunk.
1977 patch.length1 += diff_text.length();
1978 start1 += diff_text.length();
1979 empty = false;
1980 patch.diffs.append(Diff(diff_type, diff_text));
1981 bigpatch.diffs.removeFirst();
1982 } else {
1983 // Deletion or equality. Only take as much as we can stomach.
1984 diff_text = diff_text.left(std::min(diff_text.length(),
1985 patch_size - patch.length1 - Patch_Margin));
1986 patch.length1 += diff_text.length();
1987 start1 += diff_text.length();
1988 if (diff_type == EQUAL) {
1989 patch.length2 += diff_text.length();
1990 start2 += diff_text.length();
1991 } else {
1992 empty = false;
1993 }
1994 patch.diffs.append(Diff(diff_type, diff_text));
1995 if (diff_text == bigpatch.diffs.front().text) {
1996 bigpatch.diffs.removeFirst();
1997 } else {
1998 bigpatch.diffs.front().text = safeMid(bigpatch.diffs.front().text,
1999 diff_text.length());
2000 }
2001 }
2002 }
2003 // Compute the head context for the next patch.
2004 precontext = diff_text2(patch.diffs);
2005 precontext = safeMid(precontext, precontext.length() - Patch_Margin);
2006 // Append the end context for this patch.
2007 if (diff_text1(bigpatch.diffs).length() > Patch_Margin) {
2008 postcontext = diff_text1(bigpatch.diffs).left(Patch_Margin);
2009 } else {
2010 postcontext = diff_text1(bigpatch.diffs);
2011 }
2012 if (!postcontext.isEmpty()) {
2013 patch.length1 += postcontext.length();
2014 patch.length2 += postcontext.length();
2015 if (!patch.diffs.isEmpty()
2016 && patch.diffs.back().operation == EQUAL) {
2017 patch.diffs.back().text += postcontext;
2018 } else {
2019 patch.diffs.append(Diff(EQUAL, postcontext));
2020 }
2021 }
2022 if (!empty) {
2023 pointer.insert(patch);
2024 }
2025 }
2026 bigpatch = pointer.hasNext() ? pointer.next() : Patch();
2027 }
2028 }
2029
2030
patch_toText(const QList<Patch> & patches)2031 QString diff_match_patch::patch_toText(const QList<Patch> &patches) {
2032 QString text;
2033 for (Patch aPatch : patches) {
2034 text.append(aPatch.toString());
2035 }
2036 return text;
2037 }
2038
2039
patch_fromText(const QString & textline)2040 QList<Patch> diff_match_patch::patch_fromText(const QString &textline) {
2041 QList<Patch> patches;
2042 if (textline.isEmpty()) {
2043 return patches;
2044 }
2045 QStringList text = textline.split("\n",
2046 #if (QT_VERSION >= QT_VERSION_CHECK(5, 14, 0))
2047 Qt::SkipEmptyParts
2048 #else
2049 QString::SkipEmptyParts
2050 #endif
2051 );
2052 Patch patch;
2053 QRegExp patchHeader("^@@ -(\\d+),?(\\d*) \\+(\\d+),?(\\d*) @@$");
2054 char sign;
2055 QString line;
2056 while (!text.isEmpty()) {
2057 if (!patchHeader.exactMatch(text.front())) {
2058 throw QString("Invalid patch string: %1").arg(text.front());
2059 }
2060
2061 patch = Patch();
2062 patch.start1 = patchHeader.cap(1).toInt();
2063 if (patchHeader.cap(2).isEmpty()) {
2064 patch.start1--;
2065 patch.length1 = 1;
2066 } else if (patchHeader.cap(2) == "0") {
2067 patch.length1 = 0;
2068 } else {
2069 patch.start1--;
2070 patch.length1 = patchHeader.cap(2).toInt();
2071 }
2072
2073 patch.start2 = patchHeader.cap(3).toInt();
2074 if (patchHeader.cap(4).isEmpty()) {
2075 patch.start2--;
2076 patch.length2 = 1;
2077 } else if (patchHeader.cap(4) == "0") {
2078 patch.length2 = 0;
2079 } else {
2080 patch.start2--;
2081 patch.length2 = patchHeader.cap(4).toInt();
2082 }
2083 text.removeFirst();
2084
2085 while (!text.isEmpty()) {
2086 if (text.front().isEmpty()) {
2087 text.removeFirst();
2088 continue;
2089 }
2090 sign = text.front()[0].toLatin1();
2091 line = safeMid(text.front(), 1);
2092 line = line.replace("+", "%2B"); // decode would change all "+" to " "
2093 line = QUrl::fromPercentEncoding(qPrintable(line));
2094 if (sign == '-') {
2095 // Deletion.
2096 patch.diffs.append(Diff(DELETE, line));
2097 } else if (sign == '+') {
2098 // Insertion.
2099 patch.diffs.append(Diff(INSERT, line));
2100 } else if (sign == ' ') {
2101 // Minor equality.
2102 patch.diffs.append(Diff(EQUAL, line));
2103 } else if (sign == '@') {
2104 // Start of next patch.
2105 break;
2106 } else {
2107 // WTF?
2108 throw QString("Invalid patch mode '%1' in: %2").arg(sign).arg(line);
2109 return QList<Patch>();
2110 }
2111 text.removeFirst();
2112 }
2113
2114 patches.append(patch);
2115
2116 }
2117 return patches;
2118 }
2119