diff.cpp 47.2 KB
Newer Older
Joachim Eibl's avatar
Joachim Eibl committed
1
/***************************************************************************
Michael Reeves's avatar
Michael Reeves committed
2 3
 *   Copyright (C) 2003-2007 by Joachim Eibl <joachim.eibl at gmx.de>      *
 *   Copyright (C) 2018 Michael Reeves reeves.87@gmail.com                 *
Joachim Eibl's avatar
Joachim Eibl committed
4 5 6 7 8 9 10
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/
11

Michael Reeves's avatar
Michael Reeves committed
12 13 14
#include "diff.h"

#include "Utils.h"
Joachim Eibl's avatar
Joachim Eibl committed
15
#include "fileaccess.h"
16 17 18
#include "gnudiff_diff.h"
#include "options.h"
#include "progress.h"
Joachim Eibl's avatar
Joachim Eibl committed
19

Michael Reeves's avatar
Michael Reeves committed
20 21 22 23 24 25 26
#include <cstdlib>
#include <ctype.h>
#include <map>

#include <qglobal.h>
#include <KLocalizedString>
#include <KMessageBox>
Joachim Eibl's avatar
Joachim Eibl committed
27

28 29
int LineData::width(int tabSize) const
{
30 31
    int w = 0;
    int j = 0;
32
    for(int i = 0; i < size(); ++i)
33 34 35 36 37 38 39 40 41
    {
        if(pLine[i] == '\t')
        {
            for(j %= tabSize; j < tabSize; ++j)
                ++w;
            j = 0;
        }
        else
        {
Joachim Eibl's avatar
Joachim Eibl committed
42
            ++w;
43 44 45 46
            ++j;
        }
    }
    return w;
Joachim Eibl's avatar
Joachim Eibl committed
47 48 49 50 51 52
}

// The bStrict flag is true during the test where a nonmatching area ends.
// Then the equal()-function requires that the match has more than 2 nonwhite characters.
// This is to avoid matches on trivial lines (e.g. with white space only).
// This choice is good for C/C++.
53
bool equal(const LineData& l1, const LineData& l2, bool bStrict)
54
{
55
    if(l1.getLine() == nullptr || l2.getLine() == nullptr) return false;
56

57
    if(bStrict && g_bIgnoreTrivialMatches)
58
        return false;
59

60
    // Ignore white space diff
61 62
    const QChar* p1 = l1.getLine();
    const QChar* p1End = p1 + l1.size();
63

64 65
    const QChar* p2 = l2.getLine();
    const QChar* p2End = p2 + l2.size();
66

67 68 69 70 71 72 73
    if(g_bIgnoreWhiteSpace)
    {
        int nonWhite = 0;
        for(;;)
        {
            while(isWhite(*p1) && p1 != p1End) ++p1;
            while(isWhite(*p2) && p2 != p2End) ++p2;
74

75 76 77 78 79 80 81 82
            if(p1 == p1End && p2 == p2End)
            {
                if(bStrict && g_bIgnoreTrivialMatches)
                { // Then equality is not enough
                    return nonWhite > 2;
                }
                else // equality is enough
                    return true;
Joachim Eibl's avatar
Joachim Eibl committed
83
            }
84 85 86 87 88 89 90 91 92 93 94 95
            else if(p1 == p1End || p2 == p2End)
                return false;

            if(*p1 != *p2)
                return false;
            ++p1;
            ++p2;
            ++nonWhite;
        }
    }
    else
    {
96
        return (l1.size() == l2.size() && memcmp(p1, p2, l1.size()) == 0);
97
    }
Joachim Eibl's avatar
Joachim Eibl committed
98 99 100 101
}

// First step
void calcDiff3LineListUsingAB(
102 103
    const DiffList* pDiffListAB,
    Diff3LineList& d3ll)
104
{
105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128
    // First make d3ll for AB (from pDiffListAB)

    DiffList::const_iterator i = pDiffListAB->begin();
    int lineA = 0;
    int lineB = 0;
    Diff d(0, 0, 0);

    for(;;)
    {
        if(d.nofEquals == 0 && d.diff1 == 0 && d.diff2 == 0)
        {
            if(i != pDiffListAB->end())
            {
                d = *i;
                ++i;
            }
            else
                break;
        }

        Diff3Line d3l;
        if(d.nofEquals > 0)
        {
            d3l.bAEqB = true;
129 130
            d3l.setLineA(lineA);
            d3l.setLineB(lineB);
131 132 133 134 135 136
            --d.nofEquals;
            ++lineA;
            ++lineB;
        }
        else if(d.diff1 > 0 && d.diff2 > 0)
        {
137 138
            d3l.setLineA(lineA);
            d3l.setLineB(lineB);
139 140 141 142 143 144 145
            --d.diff1;
            --d.diff2;
            ++lineA;
            ++lineB;
        }
        else if(d.diff1 > 0)
        {
146
            d3l.setLineA(lineA);
147 148 149 150 151
            --d.diff1;
            ++lineA;
        }
        else if(d.diff2 > 0)
        {
152
            d3l.setLineB(lineB);
153 154 155
            --d.diff2;
            ++lineB;
        }
Michael Reeves's avatar
Michael Reeves committed
156

157
        Q_ASSERT(d.nofEquals >= 0);
158 159 160

        d3ll.push_back(d3l);
    }
Joachim Eibl's avatar
Joachim Eibl committed
161 162 163
}

// Second step
Joachim Eibl's avatar
Joachim Eibl committed
164
void calcDiff3LineListUsingAC(
165 166
    const DiffList* pDiffListAC,
    Diff3LineList& d3ll)
167
{
168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193
    ////////////////
    // Now insert data from C using pDiffListAC

    DiffList::const_iterator i = pDiffListAC->begin();
    Diff3LineList::iterator i3 = d3ll.begin();
    int lineA = 0;
    int lineC = 0;
    Diff d(0, 0, 0);

    for(;;)
    {
        if(d.nofEquals == 0 && d.diff1 == 0 && d.diff2 == 0)
        {
            if(i != pDiffListAC->end())
            {
                d = *i;
                ++i;
            }
            else
                break;
        }

        Diff3Line d3l;
        if(d.nofEquals > 0)
        {
            // Find the corresponding lineA
194
            while((*i3).getLineA() != lineA)
195 196
                ++i3;

197
            (*i3).setLineC(lineC);
198 199 200 201 202 203
            (*i3).bAEqC = true;
            (*i3).bBEqC = (*i3).bAEqB;

            --d.nofEquals;
            ++lineA;
            ++lineC;
Joachim Eibl's avatar
Joachim Eibl committed
204
            ++i3;
205 206 207
        }
        else if(d.diff1 > 0 && d.diff2 > 0)
        {
208
            d3l.setLineC(lineC);
209 210 211 212 213 214 215 216 217 218 219 220 221
            d3ll.insert(i3, d3l);
            --d.diff1;
            --d.diff2;
            ++lineA;
            ++lineC;
        }
        else if(d.diff1 > 0)
        {
            --d.diff1;
            ++lineA;
        }
        else if(d.diff2 > 0)
        {
222
            d3l.setLineC(lineC);
223 224 225 226 227 228
            d3ll.insert(i3, d3l);
            --d.diff2;
            ++lineC;
        }
    }
}
Joachim Eibl's avatar
Joachim Eibl committed
229 230

// Third step
Joachim Eibl's avatar
Joachim Eibl committed
231
void calcDiff3LineListUsingBC(
232 233
    const DiffList* pDiffListBC,
    Diff3LineList& d3ll)
234
{
235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260
    ////////////////
    // Now improve the position of data from C using pDiffListBC
    // If a line from C equals a line from A then it is in the
    // same Diff3Line already.
    // If a line from C equals a line from B but not A, this
    // information will be used here.

    DiffList::const_iterator i = pDiffListBC->begin();
    Diff3LineList::iterator i3b = d3ll.begin();
    Diff3LineList::iterator i3c = d3ll.begin();
    int lineB = 0;
    int lineC = 0;
    Diff d(0, 0, 0);

    for(;;)
    {
        if(d.nofEquals == 0 && d.diff1 == 0 && d.diff2 == 0)
        {
            if(i != pDiffListBC->end())
            {
                d = *i;
                ++i;
            }
            else
                break;
        }
Joachim Eibl's avatar
Joachim Eibl committed
261

262 263 264 265
        Diff3Line d3l;
        if(d.nofEquals > 0)
        {
            // Find the corresponding lineB and lineC
266
            while(i3b != d3ll.end() && (*i3b).getLineB() != lineB)
267
                ++i3b;
Michael Reeves's avatar
Michael Reeves committed
268

269
            while(i3c != d3ll.end() && (*i3c).getLineC() != lineC)
270
                ++i3c;
271

272 273
            Q_ASSERT(i3b != d3ll.end());
            Q_ASSERT(i3c != d3ll.end());
274

275
            if(i3b == i3c)
276
            {
277
                Q_ASSERT((*i3b).getLineC() == lineC);
278
                (*i3b).bBEqC = true;
Joachim Eibl's avatar
Joachim Eibl committed
279
            }
280
            else
281
            {
282 283 284 285 286 287 288 289
                // Is it possible to move this line up?
                // Test if no other B's are used between i3c and i3b

                // First test which is before: i3c or i3b ?
                Diff3LineList::iterator i3c1 = i3c;
                Diff3LineList::iterator i3b1 = i3b;
                while(i3c1 != i3b && i3b1 != i3c)
                {
290
                    Q_ASSERT(i3b1 != d3ll.end() || i3c1 != d3ll.end());
291 292 293 294 295 296 297 298 299
                    if(i3c1 != d3ll.end()) ++i3c1;
                    if(i3b1 != d3ll.end()) ++i3b1;
                }

                if(i3c1 == i3b && !(*i3b).bAEqB) // i3c before i3b
                {
                    Diff3LineList::iterator i3 = i3c;
                    int nofDisturbingLines = 0;
                    while(i3 != i3b && i3 != d3ll.end())
Michael Reeves's avatar
Michael Reeves committed
300
                    {
301
                        if((*i3).getLineB() != -1)
302 303
                            ++nofDisturbingLines;
                        ++i3;
Michael Reeves's avatar
Michael Reeves committed
304 305
                    }

306 307 308 309 310 311 312 313 314 315 316
                    if(nofDisturbingLines > 0) //&& nofDisturbingLines < d.nofEquals*d.nofEquals+4 )
                    {
                        Diff3LineList::iterator i3_last_equal_A = d3ll.end();

                        i3 = i3c;
                        while(i3 != i3b)
                        {
                            if(i3->bAEqB)
                            {
                                i3_last_equal_A = i3;
                            }
Michael Reeves's avatar
Michael Reeves committed
317
                            ++i3;
318 319 320
                        }

                        /* If i3_last_equal_A isn't still set to d3ll.end(), then
Michael Reeves's avatar
Michael Reeves committed
321 322 323
                   * we've found a line in A that is equal to one in B
                   * somewhere between i3c and i3b
                   */
324 325 326 327 328
                        bool before_or_on_equal_line_in_A = (i3_last_equal_A != d3ll.end());

                        // Move the disturbing lines up, out of sight.
                        i3 = i3c;
                        while(i3 != i3b)
Michael Reeves's avatar
Michael Reeves committed
329
                        {
330 331
                            if((*i3).getLineB() != -1 ||
                               (before_or_on_equal_line_in_A && i3->getLineA() != -1))
332
                            {
333 334
                                d3l.setLineB((*i3).getLineB());
                                (*i3).setLineB(-1);
335 336 337 338

                                // Move A along if it matched B
                                if(before_or_on_equal_line_in_A)
                                {
339
                                    d3l.setLineA(i3->getLineA());
340
                                    d3l.bAEqB = i3->bAEqB;
341
                                    i3->setLineA(-1);
342 343 344 345 346 347 348 349 350 351 352 353 354 355
                                    i3->bAEqC = false;
                                }

                                (*i3).bAEqB = false;
                                (*i3).bBEqC = false;
                                d3ll.insert(i3c, d3l);
                            }

                            if(i3 == i3_last_equal_A)
                            {
                                before_or_on_equal_line_in_A = false;
                            }

                            ++i3;
Michael Reeves's avatar
Michael Reeves committed
356
                        }
357 358
                        nofDisturbingLines = 0;
                    }
Michael Reeves's avatar
Michael Reeves committed
359

360
                    if(nofDisturbingLines == 0)
Michael Reeves's avatar
Michael Reeves committed
361
                    {
362
                        // Yes, the line from B can be moved.
363
                        (*i3b).setLineB(-1); // This might leave an empty line: removed later.
364 365
                        (*i3b).bAEqB = false;
                        (*i3b).bBEqC = false;
366
                        (*i3c).setLineB(lineB);
367 368 369 370 371 372 373 374 375 376
                        (*i3c).bBEqC = true;
                        (*i3c).bAEqB = (*i3c).bAEqC;
                    }
                }
                else if(i3b1 == i3c && !(*i3c).bAEqC)
                {
                    Diff3LineList::iterator i3 = i3b;
                    int nofDisturbingLines = 0;
                    while(i3 != i3c && i3 != d3ll.end())
                    {
377
                        if((*i3).getLineC() != -1)
378 379
                            ++nofDisturbingLines;
                        ++i3;
Michael Reeves's avatar
Michael Reeves committed
380 381
                    }

382 383 384 385 386 387 388 389 390 391 392
                    if(nofDisturbingLines > 0) //&& nofDisturbingLines < d.nofEquals*d.nofEquals+4 )
                    {
                        Diff3LineList::iterator i3_last_equal_A = d3ll.end();

                        i3 = i3b;
                        while(i3 != i3c)
                        {
                            if(i3->bAEqC)
                            {
                                i3_last_equal_A = i3;
                            }
Michael Reeves's avatar
Michael Reeves committed
393
                            ++i3;
394 395 396
                        }

                        /* If i3_last_equal_A isn't still set to d3ll.end(), then
Michael Reeves's avatar
Michael Reeves committed
397 398 399
                   * we've found a line in A that is equal to one in C
                   * somewhere between i3b and i3c
                   */
400 401 402 403 404
                        bool before_or_on_equal_line_in_A = (i3_last_equal_A != d3ll.end());

                        // Move the disturbing lines up.
                        i3 = i3b;
                        while(i3 != i3c)
Michael Reeves's avatar
Michael Reeves committed
405
                        {
406 407
                            if((*i3).getLineC() != -1 ||
                               (before_or_on_equal_line_in_A && i3->getLineA() != -1))
408
                            {
409 410
                                d3l.setLineC((*i3).getLineC());
                                (*i3).setLineC(-1);
411 412 413 414

                                // Move A along if it matched C
                                if(before_or_on_equal_line_in_A)
                                {
415
                                    d3l.setLineA(i3->getLineA());
416
                                    d3l.bAEqC = i3->bAEqC;
417
                                    i3->setLineA(-1);
418 419 420 421 422 423 424 425 426 427 428 429 430 431
                                    i3->bAEqB = false;
                                }

                                (*i3).bAEqC = false;
                                (*i3).bBEqC = false;
                                d3ll.insert(i3b, d3l);
                            }

                            if(i3 == i3_last_equal_A)
                            {
                                before_or_on_equal_line_in_A = false;
                            }

                            ++i3;
Michael Reeves's avatar
Michael Reeves committed
432
                        }
433 434
                        nofDisturbingLines = 0;
                    }
Michael Reeves's avatar
Michael Reeves committed
435

436 437 438
                    if(nofDisturbingLines == 0)
                    {
                        // Yes, the line from C can be moved.
439
                        (*i3c).setLineC(-1); // This might leave an empty line: removed later.
440 441
                        (*i3c).bAEqC = false;
                        (*i3c).bBEqC = false;
442
                        (*i3b).setLineC(lineC);
443 444 445 446
                        (*i3b).bBEqC = true;
                        (*i3b).bAEqC = (*i3b).bAEqB;
                    }
                }
Michael Reeves's avatar
Michael Reeves committed
447
            }
448

449 450 451 452 453 454 455 456 457
            --d.nofEquals;
            ++lineB;
            ++lineC;
            ++i3b;
            ++i3c;
        }
        else if(d.diff1 > 0)
        {
            Diff3LineList::iterator i3 = i3b;
458
            while((*i3).getLineB() != lineB)
459
                ++i3;
460
            if(i3 != i3b && !(*i3).bAEqB)
461 462
            {
                // Take B from this line and move it up as far as possible
463
                d3l.setLineB(lineB);
464
                d3ll.insert(i3b, d3l);
465
                (*i3).setLineB(-1);
466 467 468 469 470 471 472 473
            }
            else
            {
                i3b = i3;
            }
            --d.diff1;
            ++lineB;
            ++i3b;
474

475 476 477 478 479 480 481 482
            if(d.diff2 > 0)
            {
                --d.diff2;
                ++lineC;
            }
        }
        else if(d.diff2 > 0)
        {
Joachim Eibl's avatar
Joachim Eibl committed
483 484
            --d.diff2;
            ++lineC;
485 486 487
        }
    }
    /*
488 489 490 491 492
   Diff3LineList::iterator it = d3ll.begin();
   int li=0;
   for( ; it!=d3ll.end(); ++it, ++li )
   {
      printf( "%4d %4d %4d %4d  A%c=B A%c=C B%c=C\n",
493
         li, (*it).getLineA(), (*it).getLineB(), (*it).getLineC(),
494 495 496
         (*it).bAEqB ? '=' : '!', (*it).bAEqC ? '=' : '!', (*it).bBEqC ? '=' : '!' );
   }
   printf("\n");*/
Joachim Eibl's avatar
Joachim Eibl committed
497 498
}

Joachim Eibl's avatar
Joachim Eibl committed
499
// Test if the move would pass a barrier. Return true if not.
500
bool ManualDiffHelpList::isValidMove(int line1, int line2, int winIdx1, int winIdx2) const
501
{
502 503 504
    if(line1 >= 0 && line2 >= 0)
    {
        ManualDiffHelpList::const_iterator i;
505
        for(i = begin(); i != end(); ++i)
506 507 508
        {
            const ManualDiffHelpEntry& mdhe = *i;

509
            if(!mdhe.isValidMove(line1, line2, winIdx1, winIdx2)) return false;
510 511 512
        }
    }
    return true; // no barrier passed.
Joachim Eibl's avatar
Joachim Eibl committed
513 514
}

515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535
bool ManualDiffHelpEntry::isValidMove(int line1, int line2, int winIdx1, int winIdx2) const
{
    // Barrier
    int l1 = winIdx1 == 1 ? lineA1 : winIdx1 == 2 ? lineB1 : lineC1;
    int l2 = winIdx2 == 1 ? lineA1 : winIdx2 == 2 ? lineB1 : lineC1;

    if(l1 >= 0 && l2 >= 0)
    {
        if((line1 >= l1 && line2 < l2) || (line1 < l1 && line2 >= l2))
            return false;
        l1 = winIdx1 == 1 ? lineA2 : winIdx1 == 2 ? lineB2 : lineC2;
        l2 = winIdx2 == 1 ? lineA2 : winIdx2 == 2 ? lineB2 : lineC2;
        ++l1;
        ++l2;
        if((line1 >= l1 && line2 < l2) || (line1 < l1 && line2 >= l2))
            return false;
    }

    return true;
}

536
static bool runDiff(const LineData* p1, LineRef size1, const LineData* p2, LineRef size2, DiffList& diffList,
537
                    Options* pOptions)
538
{
539 540 541 542 543 544
    ProgressProxy pp;
    static GnuDiff gnuDiff; // All values are initialized with zeros.

    pp.setCurrent(0);

    diffList.clear();
545
    if(p1[0].getLine() == nullptr || p2[0].getLine() == nullptr || size1 == 0 || size2 == 0)
546 547
    {
        Diff d(0, 0, 0);
548
        if(p1[0].getLine() == nullptr && p2[0].getLine() == nullptr && size1 == size2)
549 550 551 552 553 554 555 556 557 558 559 560 561
            d.nofEquals = size1;
        else
        {
            d.diff1 = size1;
            d.diff2 = size2;
        }

        diffList.push_back(d);
    }
    else
    {
        GnuDiff::comparison comparisonInput;
        memset(&comparisonInput, 0, sizeof(comparisonInput));
Michael Reeves's avatar
Michael Reeves committed
562
        comparisonInput.parent = nullptr;
563 564 565 566
        comparisonInput.file[0].buffer = p1[0].getLine();                                                //ptr to buffer
        comparisonInput.file[0].buffered = (p1[size1 - 1].getLine() - p1[0].getLine() + p1[size1 - 1].size()); // size of buffer
        comparisonInput.file[1].buffer = p2[0].getLine();                                                //ptr to buffer
        comparisonInput.file[1].buffered = (p2[size2 - 1].getLine() - p2[0].getLine() + p2[size2 - 1].size()); // size of buffer
567 568 569 570 571 572 573 574

        gnuDiff.ignore_white_space = GnuDiff::IGNORE_ALL_SPACE; // I think nobody needs anything else ...
        gnuDiff.bIgnoreWhiteSpace = true;
        gnuDiff.bIgnoreNumbers = pOptions->m_bIgnoreNumbers;
        gnuDiff.minimal = pOptions->m_bTryHard;
        gnuDiff.ignore_case = false;
        GnuDiff::change* script = gnuDiff.diff_2_files(&comparisonInput);

575 576 577
        LineRef equalLinesAtStart = comparisonInput.file[0].prefix_lines;
        LineRef currentLine1 = 0;
        LineRef currentLine2 = 0;
Michael Reeves's avatar
Michael Reeves committed
578
        GnuDiff::change* p = nullptr;
579 580 581 582
        for(GnuDiff::change* e = script; e; e = p)
        {
            Diff d(0, 0, 0);
            d.nofEquals = e->line0 - currentLine1;
583
            Q_ASSERT(d.nofEquals == e->line1 - currentLine2);
584 585 586 587 588
            d.diff1 = e->deleted;
            d.diff2 = e->inserted;
            currentLine1 += d.nofEquals + d.diff1;
            currentLine2 += d.nofEquals + d.diff2;
            diffList.push_back(d);
589

590 591 592
            p = e->link;
            free(e);
        }
593

594 595 596
        if(diffList.empty())
        {
            Diff d(0, 0, 0);
597
            d.nofEquals = std::min(size1, size2);
598 599 600 601
            d.diff1 = size1 - d.nofEquals;
            d.diff2 = size2 - d.nofEquals;
            diffList.push_back(d);
            /*         Diff d(0,0,0);
602 603 604 605 606 607 608 609 610 611 612 613 614
         d.nofEquals = equalLinesAtStart;
         if ( gnuDiff.files[0].missing_newline != gnuDiff.files[1].missing_newline )
         {
            d.diff1 = gnuDiff.files[0].missing_newline ? 0 : 1;
            d.diff2 = gnuDiff.files[1].missing_newline ? 0 : 1;
            ++d.nofEquals;
         }
         else if ( !gnuDiff.files[0].missing_newline )
         {
            ++d.nofEquals;
         }
         diffList.push_back(d);
*/
615 616 617 618 619 620 621
        }
        else
        {
            diffList.front().nofEquals += equalLinesAtStart;
            currentLine1 += equalLinesAtStart;
            currentLine2 += equalLinesAtStart;

622
            LineRef nofEquals = std::min(size1 - currentLine1, size2 - currentLine2);
623 624 625 626 627 628 629 630 631 632
            if(nofEquals == 0)
            {
                diffList.back().diff1 += size1 - currentLine1;
                diffList.back().diff2 += size2 - currentLine2;
            }
            else
            {
                Diff d(nofEquals, size1 - currentLine1 - nofEquals, size2 - currentLine2 - nofEquals);
                diffList.push_back(d);
            }
633

634
            /*
635 636 637 638 639 640 641 642 643 644
         if ( gnuDiff.files[0].missing_newline != gnuDiff.files[1].missing_newline )
         {
            diffList.back().diff1 += gnuDiff.files[0].missing_newline ? 0 : 1;
            diffList.back().diff2 += gnuDiff.files[1].missing_newline ? 0 : 1;
         }
         else if ( !gnuDiff.files[0].missing_newline )
         {
            ++ diffList.back().nofEquals;
         }
         */
645 646
        }
    }
647

648 649
    // Verify difflist
    {
650 651
        LineRef l1 = 0;
        LineRef l2 = 0;
652 653 654 655 656 657 658 659
        DiffList::iterator i;
        for(i = diffList.begin(); i != diffList.end(); ++i)
        {
            l1 += i->nofEquals + i->diff1;
            l2 += i->nofEquals + i->diff2;
        }

        //if( l1!=p1-p1start || l2!=p2-p2start )
660
        Q_ASSERT(l1 == size1 && l2 == size2);
661
    }
662

663
    pp.setCurrent(1);
664

665
    return true;
666 667
}

668
bool runDiff(const LineData* p1, LineRef size1, const LineData* p2, LineRef size2, DiffList& diffList,
669 670 671
             int winIdx1, int winIdx2,
             ManualDiffHelpList* pManualDiffHelpList,
             Options* pOptions)
672
{
673
    Q_ASSERT(p1 != nullptr && p2 != nullptr);
674 675 676 677 678 679 680 681 682 683
    diffList.clear();
    DiffList diffList2;

    int l1begin = 0;
    int l2begin = 0;
    ManualDiffHelpList::const_iterator i;
    for(i = pManualDiffHelpList->begin(); i != pManualDiffHelpList->end(); ++i)
    {
        const ManualDiffHelpEntry& mdhe = *i;

684 685
        int l1end = mdhe.getLine1(winIdx1);
        int l2end = mdhe.getLine1(winIdx2);
686 687 688 689 690

        if(l1end >= 0 && l2end >= 0)
        {
            runDiff(p1 + l1begin, l1end - l1begin, p2 + l2begin, l2end - l2begin, diffList2, pOptions);
            diffList.splice(diffList.end(), diffList2);
691 692
            l1begin = l1end;
            l2begin = l2end;
693

694 695
            l1end = mdhe.getLine2(winIdx1);
            l2end = mdhe.getLine2(winIdx2);
696

697
            if(l1end >= 0 && l2end >= 0)
698
            {
699 700 701 702 703 704
                ++l1end; // point to line after last selected line
                ++l2end;
                runDiff(p1 + l1begin, l1end - l1begin, p2 + l2begin, l2end - l2begin, diffList2, pOptions);
                diffList.splice(diffList.end(), diffList2);
                l1begin = l1end;
                l2begin = l2end;
705
            }
706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724
        }
    }
    runDiff(p1 + l1begin, size1 - l1begin, p2 + l2begin, size2 - l2begin, diffList2, pOptions);
    diffList.splice(diffList.end(), diffList2);
    return true;
}

void correctManualDiffAlignment(Diff3LineList& d3ll, ManualDiffHelpList* pManualDiffHelpList)
{
    if(pManualDiffHelpList->empty())
        return;

    // If a line appears unaligned in comparison to the manual alignment, correct this.

    ManualDiffHelpList::iterator iMDHL;
    for(iMDHL = pManualDiffHelpList->begin(); iMDHL != pManualDiffHelpList->end(); ++iMDHL)
    {
        Diff3LineList::iterator i3 = d3ll.begin();
        int missingWinIdx = 0;
725
        int alignedSum = (iMDHL->getLine1(1) < 0 ? 0 : 1) + (iMDHL->getLine1(2) < 0 ? 0 : 1) + (iMDHL->getLine1(3) < 0 ? 0 : 1);
726 727 728 729 730
        if(alignedSum == 2)
        {
            // If only A & B are aligned then let C rather be aligned with A
            // If only A & C are aligned then let B rather be aligned with A
            // If only B & C are aligned then let A rather be aligned with B
731
            missingWinIdx = iMDHL->getLine1(1) < 0 ? 1 : (iMDHL->getLine1(2) < 0 ? 2 : 3);
732 733 734 735 736 737 738 739 740 741 742 743 744 745 746
        }
        else if(alignedSum <= 1)
        {
            return;
        }

        // At the first aligned line, move up the two other lines into new d3ls until the second input is aligned
        // Then move up the third input until all three lines are aligned.
        int wi = 0;
        for(; i3 != d3ll.end(); ++i3)
        {
            for(wi = 1; wi <= 3; ++wi)
            {
                if(i3->getLineInFile(wi) >= 0 && iMDHL->firstLine(wi) == i3->getLineInFile(wi))
                    break;
Joachim Eibl's avatar
Joachim Eibl committed
747
            }
748 749 750 751 752 753 754 755 756 757 758 759
            if(wi <= 3)
                break;
        }

        if(wi >= 1 && wi <= 3)
        {
            // Found manual alignment for one source
            Diff3LineList::iterator iDest = i3;

            // Move lines up until the next firstLine is found. Omit wi from move and search.
            int wi2 = 0;
            for(; i3 != d3ll.end(); ++i3)
760
            {
761 762 763 764 765 766 767 768 769 770 771 772 773
                for(wi2 = 1; wi2 <= 3; ++wi2)
                {
                    if(wi != wi2 && i3->getLineInFile(wi2) >= 0 && iMDHL->firstLine(wi2) == i3->getLineInFile(wi2))
                        break;
                }
                if(wi2 > 3)
                { // Not yet found
                    // Move both others up
                    Diff3Line d3l;
                    // Move both up
                    if(wi == 1) // Move B and C up
                    {
                        d3l.bBEqC = i3->bBEqC;
774 775 776 777
                        d3l.setLineB(i3->getLineB());
                        d3l.setLineC(i3->getLineC());
                        i3->setLineB(-1);
                        i3->setLineC(-1);
778 779 780 781
                    }
                    if(wi == 2) // Move A and C up
                    {
                        d3l.bAEqC = i3->bAEqC;
782 783 784 785
                        d3l.setLineA(i3->getLineA());
                        d3l.setLineC(i3->getLineC());
                        i3->setLineA(-1);
                        i3->setLineC(-1);
786 787 788 789
                    }
                    if(wi == 3) // Move A and B up
                    {
                        d3l.bAEqB = i3->bAEqB;
790 791 792 793
                        d3l.setLineA(i3->getLineA());
                        d3l.setLineB(i3->getLineB());
                        i3->setLineA(-1);
                        i3->setLineB(-1);
794 795 796 797 798 799 800 801 802 803 804 805
                    }
                    i3->bAEqB = false;
                    i3->bAEqC = false;
                    i3->bBEqC = false;
                    d3ll.insert(iDest, d3l);
                }
                else
                {
                    // align the found line with the line we already have here
                    if(i3 != iDest)
                    {
                        if(wi2 == 1)
806
                        {
807 808
                            iDest->setLineA(i3->getLineA());
                            i3->setLineA(-1);
809 810
                            i3->bAEqB = false;
                            i3->bAEqC = false;
Joachim Eibl's avatar
Joachim Eibl committed
811
                        }
812
                        else if(wi2 == 2)
813
                        {
814 815
                            iDest->setLineB(i3->getLineB());
                            i3->setLineB(-1);
816 817
                            i3->bAEqB = false;
                            i3->bBEqC = false;
Joachim Eibl's avatar
Joachim Eibl committed
818
                        }
819
                        else if(wi2 == 3)
820
                        {
821 822
                            iDest->setLineC(i3->getLineC());
                            i3->setLineC(-1);
823 824
                            i3->bBEqC = false;
                            i3->bAEqC = false;
Joachim Eibl's avatar
Joachim Eibl committed
825
                        }
826 827 828 829 830 831 832 833 834 835 836 837 838 839 840
                    }

                    if(missingWinIdx != 0)
                    {
                        for(; i3 != d3ll.end(); ++i3)
                        {
                            int wi3 = missingWinIdx;
                            if(i3->getLineInFile(wi3) >= 0)
                            {
                                // not found, move the line before iDest
                                Diff3Line d3l;
                                if(wi3 == 1)
                                {
                                    if(i3->bAEqB) // Stop moving lines up if one equal is found.
                                        break;
841 842
                                    d3l.setLineA(i3->getLineA());
                                    i3->setLineA(-1);
843 844 845 846 847 848 849
                                    i3->bAEqB = false;
                                    i3->bAEqC = false;
                                }
                                if(wi3 == 2)
                                {
                                    if(i3->bAEqB)
                                        break;
850 851
                                    d3l.setLineB(i3->getLineB());
                                    i3->setLineB(-1);
852 853 854 855 856 857 858
                                    i3->bAEqB = false;
                                    i3->bBEqC = false;
                                }
                                if(wi3 == 3)
                                {
                                    if(i3->bAEqC)
                                        break;
859 860
                                    d3l.setLineC(i3->getLineC());
                                    i3->setLineC(-1);
861 862 863 864 865 866 867 868 869 870 871 872
                                    i3->bAEqC = false;
                                    i3->bBEqC = false;
                                }
                                d3ll.insert(iDest, d3l);
                            }
                        } // for(), searching for wi3
                    }
                    break;
                }
            } // for(), searching for wi2
        }     // if, wi found
    }         // for (iMDHL)
Joachim Eibl's avatar
Joachim Eibl committed
873 874
}

Joachim Eibl's avatar
Joachim Eibl committed
875
// Fourth step
Joachim Eibl's avatar
Joachim Eibl committed
876
void calcDiff3LineListTrim(
877
    Diff3LineList& d3ll, const LineData* pldA, const LineData* pldB, const LineData* pldC, ManualDiffHelpList* pManualDiffHelpList)
878
{
879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900
    const Diff3Line d3l_empty;
    d3ll.removeAll(d3l_empty);

    Diff3LineList::iterator i3 = d3ll.begin();
    Diff3LineList::iterator i3A = d3ll.begin();
    Diff3LineList::iterator i3B = d3ll.begin();
    Diff3LineList::iterator i3C = d3ll.begin();

    int line = 0;  // diff3line counters
    int lineA = 0; //
    int lineB = 0;
    int lineC = 0;

    ManualDiffHelpList::iterator iMDHL = pManualDiffHelpList->begin();
    // The iterator i3 and the variable line look ahead.
    // The iterators i3A, i3B, i3C and corresponding lineA, lineB and lineC stop at empty lines, if found.
    // If possible, then the texts from the look ahead will be moved back to the empty places.

    for(; i3 != d3ll.end(); ++i3, ++line)
    {
        if(iMDHL != pManualDiffHelpList->end())
        {
901 902 903
            if((i3->getLineA() >= 0 && i3->getLineA() == iMDHL->getLine1(1)) ||
               (i3->getLineB() >= 0 && i3->getLineB() == iMDHL->getLine1(2)) ||
               (i3->getLineC() >= 0 && i3->getLineC() == iMDHL->getLine1(3)))
904 905 906 907 908 909 910 911 912 913 914
            {
                i3A = i3;
                i3B = i3;
                i3C = i3;
                lineA = line;
                lineB = line;
                lineC = line;
                ++iMDHL;
            }
        }

915 916 917 918
        if(line > lineA && (*i3).getLineA() != -1 && (*i3A).getLineB() != -1 && (*i3A).bBEqC &&
           ::equal(pldA[(*i3).getLineA()], pldB[(*i3A).getLineB()], false) &&
           pManualDiffHelpList->isValidMove((*i3).getLineA(), (*i3A).getLineB(), 1, 2) &&
           pManualDiffHelpList->isValidMove((*i3).getLineA(), (*i3A).getLineC(), 1, 3))
919 920
        {
            // Empty space for A. A matches B and C in the empty line. Move it up.
921
            (*i3A).setLineA((*i3).getLineA());
922 923
            (*i3A).bAEqB = true;
            (*i3A).bAEqC = true;
Michael Reeves's avatar
Michael Reeves committed
924

925
            (*i3).setLineA(-1);
926 927 928 929 930 931
            (*i3).bAEqB = false;
            (*i3).bAEqC = false;
            ++i3A;
            ++lineA;
        }

932 933 934 935
        if(line > lineB && (*i3).getLineB() != -1 && (*i3B).getLineA() != -1 && (*i3B).bAEqC &&
           ::equal(pldB[(*i3).getLineB()], pldA[(*i3B).getLineA()], false) &&
           pManualDiffHelpList->isValidMove((*i3).getLineB(), (*i3B).getLineA(), 2, 1) &&
           pManualDiffHelpList->isValidMove((*i3).getLineB(), (*i3B).getLineC(), 2, 3))
936 937
        {
            // Empty space for B. B matches A and C in the empty line. Move it up.
938
            (*i3B).setLineB((*i3).getLineB());
939 940
            (*i3B).bAEqB = true;
            (*i3B).bBEqC = true;
941
            (*i3).setLineB(-1);
942 943 944 945 946 947
            (*i3).bAEqB = false;
            (*i3).bBEqC = false;
            ++i3B;
            ++lineB;
        }

948 949 950 951
        if(line > lineC && (*i3).getLineC() != -1 && (*i3C).getLineA() != -1 && (*i3C).bAEqB &&
           ::equal(pldC[(*i3).getLineC()], pldA[(*i3C).getLineA()], false) &&
           pManualDiffHelpList->isValidMove((*i3).getLineC(), (*i3C).getLineA(), 3, 1) &&
           pManualDiffHelpList->isValidMove((*i3).getLineC(), (*i3C).getLineB(), 3, 2))
952 953
        {
            // Empty space for C. C matches A and B in the empty line. Move it up.
954
            (*i3C).setLineC((*i3).getLineC());
955 956
            (*i3C).bAEqC = true;
            (*i3C).bBEqC = true;
957
            (*i3).setLineC(-1);
958 959 960 961 962
            (*i3).bAEqC = false;
            (*i3).bBEqC = false;
            ++i3C;
            ++lineC;
        }
Michael Reeves's avatar
Michael Reeves committed
963

964 965 966
        if(line > lineA && (*i3).getLineA() != -1 && !(*i3).bAEqB && !(*i3).bAEqC &&
           pManualDiffHelpList->isValidMove((*i3).getLineA(), (*i3A).getLineB(), 1, 2) &&
           pManualDiffHelpList->isValidMove((*i3).getLineA(), (*i3A).getLineC(), 1, 3)) {
967
            // Empty space for A. A doesn't match B or C. Move it up.
968 969
            (*i3A).setLineA((*i3).getLineA());
            (*i3).setLineA(-1);
970

971
            if(i3A->getLineB() != -1 && ::equal(pldA[i3A->getLineA()], pldB[i3A->getLineB()], false))
972 973 974 975
            {
                i3A->bAEqB = true;
            }
            if((i3A->bAEqB && i3A->bBEqC) ||
976
               (i3A->getLineC() != -1 && ::equal(pldA[i3A->getLineA()], pldC[i3A->getLineC()], false)))
977 978 979
            {
                i3A->bAEqC = true;
            }
980

981 982 983 984
            ++i3A;
            ++lineA;
        }

985 986 987
        if(line > lineB && (*i3).getLineB() != -1 && !(*i3).bAEqB && !(*i3).bBEqC &&
           pManualDiffHelpList->isValidMove((*i3).getLineB(), (*i3B).getLineA(), 2, 1) &&
           pManualDiffHelpList->isValidMove((*i3).getLineB(), (*i3B).getLineC(), 2, 3))
988 989
        {
            // Empty space for B. B matches neither A nor C. Move B up.
990 991
            (*i3B).setLineB((*i3).getLineB());
            (*i3).setLineB(-1);
992

993
            if(i3B->getLineA() != -1 && ::equal(pldA[i3B->getLineA()], pldB[i3B->getLineB()], false))
994 995 996 997
            {
                i3B->bAEqB = true;
            }
            if((i3B->bAEqB && i3B->bAEqC) ||
998
               (i3B->getLineC() != -1 && ::equal(pldB[i3B->getLineB()], pldC[i3B->getLineC()], false)))
Michael Reeves's avatar
Michael Reeves committed
999
            {
1000
                i3B->bBEqC = true;
Michael Reeves's avatar
Michael Reeves committed
1001 1002
            }

Joachim Eibl's avatar
Joachim Eibl committed
1003
            ++i3B;
1004 1005 1006
            ++lineB;
        }

1007 1008 1009
        if(line > lineC && (*i3).getLineC() != -1 && !(*i3).bAEqC && !(*i3).bBEqC &&
           pManualDiffHelpList->isValidMove( (*i3).getLineC(), (*i3C).getLineA(), 3, 1) &&
           pManualDiffHelpList->isValidMove( (*i3).getLineC(), (*i3C).getLineB(), 3, 2))
1010 1011
        {
            // Empty space for C. C matches neither A nor B. Move C up.
1012 1013
            (*i3C).setLineC((*i3).getLineC());
            (*i3).setLineC(-1);
1014

1015
            if(i3C->getLineA() != -1 && ::equal(pldA[i3C->getLineA()], pldC[i3C->getLineC()], false))
1016 1017 1018 1019
            {
                i3C->bAEqC = true;
            }
            if((i3C->bAEqC && i3C->bAEqB) ||
1020
               (i3C->getLineB() != -1 && ::equal(pldB[i3C->getLineB()], pldC[i3C->getLineC()], false)))
Michael Reeves's avatar
Michael Reeves committed
1021
            {
1022
                i3C->bBEqC = true;
Michael Reeves's avatar
Michael Reeves committed
1023 1024
            }

Joachim Eibl's avatar
Joachim Eibl committed
1025
            ++i3C;
1026 1027
            ++lineC;
        }
1028

1029
        if(line > lineA && line > lineB && (*i3).getLineA() != -1 && (*i3).bAEqB && !(*i3).bAEqC)
1030 1031 1032 1033 1034
        {
            // Empty space for A and B. A matches B, but not C. Move A & B up.
            Diff3LineList::iterator i = lineA > lineB ? i3A : i3B;
            int l = lineA > lineB ? lineA : lineB;

1035 1036
            if(pManualDiffHelpList->isValidMove( i->getLineC(), (*i3).getLineA(), 3, 1) &&
               pManualDiffHelpList->isValidMove( i->getLineC(), (*i3).getLineB(), 3, 2))
1037
            {
1038 1039
                (*i).setLineA((*i3).getLineA());
                (*i).setLineB((*i3).getLineB());
1040 1041
                (*i).bAEqB = true;

1042
                if(i->getLineC() != -1 && ::equal(pldA[i->getLineA()], pldC[i->getLineC()], false))
1043 1044 1045 1046 1047
                {
                    (*i).bAEqC = true;
                    (*i).bBEqC = true;
                }

1048 1049
                (*i3).setLineA(-1);
                (*i3).setLineB(-1);
1050 1051 1052 1053 1054 1055 1056 1057 1058
                (*i3).bAEqB = false;
                i3A = i;
                i3B = i;
                ++i3A;
                ++i3B;
                lineA = l + 1;
                lineB = l + 1;
            }
        }
1059
        else if(line > lineA && line > lineC && (*i3).getLineA() != -1 && (*i3).bAEqC && !(*i3).bAEqB)
1060 1061 1062 1063 1064
        {
            // Empty space for A and C. A matches C, but not B. Move A & C up.
            Diff3LineList::iterator i = lineA > lineC ? i3A : i3C;
            int l = lineA > lineC ? lineA : lineC;

1065 1066
            if(pManualDiffHelpList->isValidMove(i->getLineB(), (*i3).getLineA(), 2, 1) &&
               pManualDiffHelpList->isValidMove(i->getLineB(), (*i3).getLineC(), 2, 3))
1067
            {
1068 1069
                (*i).setLineA((*i3).getLineA());
                (*i).setLineC((*i3).getLineC());
1070 1071
                (*i).bAEqC = true;

1072
                if(i->getLineB() != -1 && ::equal(pldA[i->getLineA()], pldB[i->getLineB()], false))
1073 1074 1075 1076 1077
                {
                    (*i).bAEqB = true;
                    (*i).bBEqC = true;
                }

1078 1079
                (*i3).setLineA(-1);
                (*i3).setLineC(-1);
1080 1081 1082 1083 1084 1085 1086 1087 1088
                (*i3).bAEqC = false;
                i3A = i;
                i3C = i;
                ++i3A;
                ++i3C;
                lineA = l + 1;
                lineC = l + 1;
            }
        }
1089
        else if(line > lineB && line > lineC && (*i3).getLineB() != -1 && (*i3).bBEqC && !(*i3).bAEqC)
1090 1091 1092 1093 1094
        {
            // Empty space for B and C. B matches C, but not A. Move B & C up.
            Diff3LineList::iterator i = lineB > lineC ? i3B : i3C;
            int l = lineB > lineC ? lineB : lineC;

1095 1096
            if(pManualDiffHelpList->isValidMove( i->getLineA(), (*i3).getLineB(), 1, 2) &&
               pManualDiffHelpList->isValidMove( i->getLineA(), (*i3).getLineC(), 1, 3))
Michael Reeves's avatar
Michael Reeves committed
1097
            {
1098 1099
                (*i).setLineB((*i3).getLineB());
                (*i).setLineC((*i3).getLineC());
1100 1101
                (*i).bBEqC = true;

1102
                if(i->getLineA() != -1 && ::equal(pldA[i->getLineA()], pldB[i->getLineB()], false))
1103 1104 1105 1106 1107
                {
                    (*i).bAEqB = true;
                    (*i).bAEqC = true;
                }

1108 1109
                (*i3).setLineB(-1);
                (*i3).setLineC(-1);
1110 1111 1112 1113 1114 1115 1116
                (*i3).bBEqC = false;
                i3B = i;
                i3C = i;
                ++i3B;
                ++i3C;
                lineB = l + 1;
                lineC = l + 1;
Michael Reeves's avatar
Michael Reeves committed
1117
            }
1118
        }
Michael Reeves's avatar
Michael Reeves committed
1119

1120
        if((*i3).getLineA() != -1)
1121 1122 1123 1124 1125
        {
            lineA = line + 1;
            i3A = i3;
            ++i3A;
        }
1126
        if((*i3).getLineB() != -1)
1127 1128 1129
        {
            lineB = line + 1;
            i3B = i3;
Joachim Eibl's avatar
Joachim Eibl committed
1130
            ++i3B;
1131
        }
1132
        if((*i3).getLineC() != -1)
1133 1134 1135
        {
            lineC = line + 1;
            i3C = i3;
Joachim Eibl's avatar
Joachim Eibl committed
1136
            ++i3C;
1137 1138
        }
    }
1139

1140
    d3ll.removeAll(d3l_empty);
1141

1142
    /*
1143 1144 1145 1146 1147 1148

   Diff3LineList::iterator it = d3ll.begin();
   int li=0;
   for( ; it!=d3ll.end(); ++it, ++li )
   {
      printf( "%4d %4d %4d %4d  A%c=B A%c=C B%c=C\n",
1149
         li, (*it).getLineA(), (*it).getLineB(), (*it).getLineC(),
1150 1151 1152 1153
         (*it).bAEqB ? '=' : '!', (*it).bAEqC ? '=' : '!', (*it).bBEqC ? '=' : '!' );

   }
*/
Joachim Eibl's avatar
Joachim Eibl committed
1154 1155
}

1156
void DiffBufferInfo::init(Diff3LineList* pD3ll, const Diff3LineVector* pD3lv,
1157
                          const LineData* pldA, LineRef sizeA, const LineData* pldB, LineRef sizeB, const LineData* pldC, LineRef sizeC)
1158
{
1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171
    m_pDiff3LineList = pD3ll;
    m_pDiff3LineVector = pD3lv;
    m_pLineDataA = pldA;
    m_pLineDataB = pldB;
    m_pLineDataC = pldC;
    m_sizeA = sizeA;
    m_sizeB = sizeB;
    m_sizeC = sizeC;
    Diff3LineList::iterator i3 = pD3ll->begin();
    for(; i3 != pD3ll->end(); ++i3)
    {
        i3->m_pDiffBufferInfo = this;
    }
Joachim Eibl's avatar
Joachim Eibl committed
1172 1173
}

Joachim Eibl's avatar
0.9.80  
Joachim Eibl committed
1174
void calcWhiteDiff3Lines(
1175
    Diff3LineList& d3ll, const LineData* pldA, const LineData* pldB, const LineData* pldC)
1176
{
1177 1178 1179 1180
    Diff3LineList::iterator i3 = d3ll.begin();

    for(; i3 != d3ll.end(); ++i3)
    {
1181 1182 1183
        i3->bWhiteLineA = ((*i3).getLineA() == -1 || pldA == nullptr || pldA[(*i3).getLineA()].whiteLine() || pldA[(*i3).getLineA()].bContainsPureComment);
        i3->bWhiteLineB = ((*i3).getLineB() == -1 || pldB == nullptr || pldB[(*i3).getLineB()].whiteLine() || pldB[(*i3).getLineB()].bContainsPureComment);
        i3->bWhiteLineC = ((*i3).getLineC() == -1 || pldC == nullptr || pldC[(*i3).getLineC()].whiteLine() || pldC[(*i3).getLineC()].bContainsPureComment);
1184
    }
Joachim Eibl's avatar
Joachim Eibl committed
1185 1186
}

1187
inline bool equal(QChar c1, QChar c2, bool /*bStrict*/)
1188
{
1189
    // If bStrict then white space doesn't match
Joachim Eibl's avatar
0.9.80  
Joachim Eibl committed
1190

1191 1192
    //if ( bStrict &&  ( c1==' ' || c1=='\t' ) )
    //   return false;
Joachim Eibl's avatar
0.9.80  
Joachim Eibl committed
1193

1194
    return c1 == c2;
Joachim Eibl's avatar
0.9.80  
Joachim Eibl committed
1195 1196 1197 1198
}

// My own diff-invention:
template <class T>
1199
void calcDiff(const T* p1, LineRef size1, const T* p2, LineRef size2, DiffList& diffList, int match, int maxSearchRange)
1200
{
1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224
    diffList.clear();

    const T* p1start = p1;
    const T* p2start = p2;
    const T* p1end = p1 + size1;
    const T* p2end = p2 + size2;
    for(;;)
    {
        int nofEquals = 0;
        while(p1 != p1end && p2 != p2end && equal(*p1, *p2, false))
        {
            ++p1;
            ++p2;
            ++nofEquals;
        }

        bool bBestValid = false;
        int bestI1 = 0;
        int bestI2 = 0;
        int i1 = 0;
        int i2 = 0;
        for(i1 = 0;; ++i1)
        {
            if(&p1[i1] == p1end || (bBestValid && i1 >= bestI1 + bestI2))
1225
            {
1226
                break;
1227
            }
1228
            for(i2 = 0; i2 < maxSearchRange; ++i2)
1229
            {
1230 1231 1232 1233 1234 1235 1236 1237
                if(&p2[i2] == p2end || (bBestValid && i1 + i2 >= bestI1 + bestI2))
                {
                    break;
                }
                else if(equal(p2[i2], p1