Bug Summary

File:OMEdit/OMEditLIB/TransformationalDebugger/diff_match_patch.cpp
Warning:line 820, 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 false
10
'?' condition is false
734 while (thisDiff != NULL__null) {
11
Loop condition is false. Execution continues on line 799
735 if (thisDiff->operation == OMC_OP_EQUAL) {
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) {
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()
753 && (lastequality.length()
754 <= std::max(length_insertions1, length_deletions1))
755 && (lastequality.length()
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()) {
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()) {
771 // Throw away the previous equality (it needs to be reevaluated).
772 equalities.pop();
773 }
774 if (equalities.isEmpty()) {
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()) {
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;
796 }
797
798 // Normalize the diff.
799 if (changes) {
12
Taking false branch
800 diff_cleanupMerge(diffs);
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()) {
13
Assuming the condition is true
14
Taking true branch
814 prevDiff = &pointer.next();
815 if (pointer.hasNext()) {
15
Assuming the condition is true
16
Taking true branch
816 thisDiff = &pointer.next();
817 }
818 }
819 while (thisDiff != NULL__null) {
17
Loop condition is true. Entering loop body
29
Loop condition is true. Entering loop body
820 if (prevDiff->operation == OMC_OP_DELETE &&
18
Assuming the condition is true
20
Taking true branch
30
Access to field 'operation' results in a dereference of a null pointer (loaded from variable 'prevDiff')
821 thisDiff->operation == OMC_OP_INSERT) {
19
Assuming the condition is true
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) {
21
Taking false branch
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 ||
22
Taking false branch
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;
23
Assuming the condition is false
24
'?' condition is false
25
Null pointer value stored to 'thisDiff'
855 }
856 prevDiff = thisDiff;
26
Null pointer value stored to 'prevDiff'
857 thisDiff = pointer.hasNext() ? &pointer.next() : NULL__null;
27
Assuming the condition is true
28
'?' condition is true
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;
1107 Diff *prevEqual = NULL__null;
1108 int commonlength;
1109 while (thisDiff != NULL__null) {
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()) {
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;
1204 thisDiff = pointer.hasNext() ? &pointer.next() : NULL__null;
1205 Diff *nextDiff = pointer.hasNext() ? &pointer.next() : NULL__null;
1206
1207 // Intentionally ignore the first and last element (don't need checking).
1208 while (nextDiff != NULL__null) {
1209 if (prevDiff->operation == OMC_OP_EQUAL &&
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}