Bug Summary

File:OMEdit/OMEditLIB/TransformationalDebugger/diff_match_patch.cpp
Warning:line 1209, column 9
Access to field 'operation' results in a dereference of a null pointer (loaded from variable 'prevDiff')

Annotated Source Code

[?] Use j/k keys for keyboard navigation

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