File indexing completed on 2024-04-21 05:42:29

0001 // clang-format off
0002 /*
0003  *  This file is part of KDiff3.
0004  *
0005  * SPDX-FileCopyrightText: 2002-2011 Joachim Eibl, joachim.eibl at gmx.de
0006  * SPDX-FileCopyrightText: 2018-2020 Michael Reeves reeves.87@gmail.com
0007  * SPDX-License-Identifier: GPL-2.0-or-later
0008 */
0009 // clang-format on
0010 
0011 #include "diff.h"
0012 #include <QtGlobal>
0013 
0014 #include "gnudiff_diff.h"
0015 #include "Logging.h"
0016 #include "options.h"
0017 #include "ProgressProxy.h"
0018 #include "Utils.h"
0019 
0020 #include <algorithm>           // for min
0021 #include <cstdlib>
0022 #include <ctype.h>
0023 #include <exception>
0024 #include <memory>
0025 #include <optional>
0026 #include <utility>             // for swap
0027 
0028 #ifndef AUTOTEST
0029 #include <KLocalizedString>
0030 #include <KMessageBox>
0031 #endif
0032 
0033 #include <QRegularExpression>
0034 #include <QSharedPointer>
0035 #include <QTextStream>
0036 
0037 extern std::unique_ptr<Options> gOptions;
0038 
0039 constexpr bool g_bIgnoreWhiteSpace = true;
0040 
0041 QSharedPointer<DiffBufferInfo> Diff3Line::m_pDiffBufferInfo = QSharedPointer<DiffBufferInfo>::create();
0042 
0043 qint32 LineData::width(qint32 tabSize) const
0044 {
0045     const QString pLine = getLine();
0046     qint32 w = 0;
0047     qint32 j = 0;
0048     for(QtSizeType i = 0; i < size(); ++i)
0049     {
0050         if(pLine[i] == '\t')
0051         {
0052             for(j %= tabSize; j < tabSize; ++j)
0053                 ++w;
0054             j = 0;
0055         }
0056         else
0057         {
0058             ++w;
0059             ++j;
0060         }
0061     }
0062     return w;
0063 }
0064 
0065 class StringIter {
0066     QString::const_iterator ptr;
0067     QString::const_iterator end;
0068 
0069 public:
0070     StringIter(QString const& s)
0071         : ptr(s.begin())
0072         , end(s.end())
0073     {}
0074 
0075     bool hasPeek() const {
0076         return ptr < end;
0077     }
0078 
0079     std::optional<QChar> tryPeek() const {
0080         if (ptr < end) {
0081             return *ptr;
0082         } else {
0083             return {};
0084         }
0085     }
0086 
0087     void next() {
0088         assert(ptr < end);
0089         ptr++;
0090     }
0091 };
0092 
0093 /*
0094     Implement support for g_bIgnoreWhiteSpace
0095 */
0096 bool LineData::equal(const LineData& l1, const LineData& l2)
0097 {
0098     if(l1.getLine() == nullptr || l2.getLine() == nullptr) return false;
0099 
0100     if(g_bIgnoreWhiteSpace)
0101     {
0102         // Ignore white space diff
0103         const QString line1 = l1.getLine(), line2 = l2.getLine();
0104         StringIter p1{line1};
0105         StringIter p2{line2};
0106 
0107         for(; ; p1.next(), p2.next())
0108         {
0109             // Advance to the next non-whitespace character or EOL.
0110             while (p1.hasPeek() && isspace(p1.tryPeek()->toLatin1())) {
0111                 p1.next();
0112             }
0113             while (p2.hasPeek() && isspace(p2.tryPeek()->toLatin1())) {
0114                 p2.next();
0115             }
0116 
0117             // If the two strings differ outside of whitespace, or either ends earlier, return false.
0118             if(p1.tryPeek() != p2.tryPeek())
0119                 return false;
0120 
0121             // If both strings end together, return true.
0122             if (!p1.hasPeek() && !p2.hasPeek()) {
0123                 return true;
0124             }
0125 
0126             // Test remaining characters.
0127         }
0128     }
0129     else
0130     {
0131         const QString line1 = l1.getLine(), line2 = l2.getLine();
0132         return (l1.size() == l2.size() && QString::compare(line1, line2) == 0);
0133     }
0134 }
0135 
0136 // First step
0137 void Diff3LineList::calcDiff3LineListUsingAB(const DiffList* pDiffListAB)
0138 {
0139     // First make d3ll for AB (from pDiffListAB)
0140 
0141     LineRef lineA = 0;
0142     LineRef lineB = 0;
0143 
0144     qCInfo(kdiffMain) << "Enter: calcDiff3LineListUsingAB";
0145     for(Diff d: *pDiffListAB)
0146     {
0147         while(d.numberOfEquals() > 0)
0148         {
0149             Diff3Line d3l;
0150 
0151             d3l.bAEqB = true;
0152             d3l.setLineA(lineA);
0153             d3l.setLineB(lineB);
0154             d.adjustNumberOfEquals(-1);
0155             ++lineA;
0156             ++lineB;
0157 
0158             qCDebug(kdiffCore) << "lineA = " << d3l.getLineA() << ", lineB = " << d3l.getLineB() ;
0159             push_back(d3l);
0160         }
0161 
0162         while(d.diff1() > 0 && d.diff2() > 0)
0163         {
0164             Diff3Line d3l;
0165 
0166             d3l.setLineA(lineA);
0167             d3l.setLineB(lineB);
0168             d.adjustDiff1(-1);
0169             d.adjustDiff2(-1);
0170             ++lineA;
0171             ++lineB;
0172 
0173             qCDebug(kdiffCore) << "lineA = " << d3l.getLineA() << ", lineB = " << d3l.getLineB() ;
0174             push_back(d3l);
0175         }
0176 
0177         while(d.diff1() > 0)
0178         {
0179             Diff3Line d3l;
0180 
0181             d3l.setLineA(lineA);
0182             d.adjustDiff1(-1);
0183             ++lineA;
0184 
0185             qCDebug(kdiffCore) << "lineA = " << d3l.getLineA() << ", lineB = " << d3l.getLineB() ;
0186             push_back(d3l);
0187         }
0188 
0189         while(d.diff2() > 0)
0190         {
0191             Diff3Line d3l;
0192 
0193             d3l.setLineB(lineB);
0194             d.adjustDiff2(-1);
0195             ++lineB;
0196 
0197             qCDebug(kdiffCore) << "lineA = " << d3l.getLineA() << ", lineB = " << d3l.getLineB() ;
0198             push_back(d3l);
0199         }
0200     }
0201     qCInfo(kdiffMain) << "Leave: calcDiff3LineListUsingAB" ;
0202 }
0203 
0204 // Second step
0205 void Diff3LineList::calcDiff3LineListUsingAC(const DiffList* pDiffListAC)
0206 {
0207     ////////////////
0208     // Now insert data from C using pDiffListAC
0209 
0210     Diff3LineList::iterator i3 = begin();
0211     LineRef lineA = 0;
0212     LineRef lineC = 0;
0213 
0214     for(Diff d: *pDiffListAC)
0215     {
0216         assert(d.diff1() <= limits<LineType>::max() && d.diff2() <= limits<LineType>::max());
0217 
0218         while(d.numberOfEquals() > 0)
0219         {
0220             Diff3Line d3l;
0221 
0222             // Find the corresponding lineA
0223             while(i3->getLineA() != lineA && i3 != end())
0224                 ++i3;
0225             assert(i3 != end());
0226 
0227             i3->setLineC(lineC);
0228             i3->bAEqC = true;
0229             i3->bBEqC = i3->isEqualAB();
0230 
0231             d.adjustNumberOfEquals(-1);
0232             ++lineA;
0233             ++lineC;
0234             ++i3;
0235         }
0236         assert(i3 != end() || (d.diff1() == 0 && d.diff2() == 0));
0237 
0238         while(d.diff1() > 0 && d.diff2() > 0)
0239         {
0240             Diff3Line d3l;
0241 
0242             d3l.setLineC(lineC);
0243             insert(i3, d3l);
0244             d.adjustDiff1(-1);
0245             d.adjustDiff2(-1);
0246             ++lineA;
0247             ++lineC;
0248         }
0249 
0250         lineA += (LineRef)d.diff1();
0251 
0252         while(d.diff2() > 0)
0253         {
0254             Diff3Line d3l;
0255 
0256             d3l.setLineC(lineC);
0257             insert(i3, d3l);
0258             d.adjustDiff2(-1);
0259             ++lineC;
0260         }
0261     }
0262 }
0263 
0264 // Third step
0265 void Diff3LineList::calcDiff3LineListUsingBC(const DiffList* pDiffListBC)
0266 {
0267     ////////////////
0268     // Now improve the position of data from C using pDiffListBC
0269     // If a line from C equals a line from A then it is in the
0270     // same Diff3Line already.
0271     // If a line from C equals a line from B but not A, this
0272     // information will be used here.
0273 
0274     Diff3LineList::iterator i3b = begin();
0275     Diff3LineList::iterator i3c = begin();
0276     LineRef lineB = 0;
0277     LineRef lineC = 0;
0278 
0279     for(Diff d: *pDiffListBC)
0280     {
0281         while(d.numberOfEquals() > 0)
0282         {
0283             Diff3Line d3l;
0284             // Find the corresponding lineB and lineC
0285             while(i3b != end() && i3b->getLineB() != lineB)
0286                 ++i3b;
0287 
0288             while(i3c != end() && i3c->getLineC() != lineC)
0289                 ++i3c;
0290 
0291             assert(i3b != end());
0292             assert(i3c != end());
0293 
0294             if(i3b == i3c)
0295             {
0296                 assert(i3b->getLineC() == lineC);
0297                 i3b->bBEqC = true;
0298             }
0299             else
0300             {
0301                 // Is it possible to move this line up?
0302                 // Test if no other B's are used between i3c and i3b
0303 
0304                 // First test which is before: i3c or i3b ?
0305                 Diff3LineList::iterator i3c1 = i3c;
0306                 Diff3LineList::iterator i3b1 = i3b;
0307                 while(i3c1 != i3b && i3b1 != i3c)
0308                 {
0309                     assert(i3b1 != end() || i3c1 != end());
0310                     if(i3c1 != end()) ++i3c1;
0311                     if(i3b1 != end()) ++i3b1;
0312                 }
0313 
0314                 if(i3c1 == i3b && !i3b->isEqualAB()) // i3c before i3b
0315                 {
0316                     Diff3LineList::iterator i3 = i3c;
0317                     quint32 nofDisturbingLines = 0;
0318                     while(i3 != i3b && i3 != end())
0319                     {
0320                         if(i3->getLineB().isValid())
0321                             ++nofDisturbingLines;
0322                         ++i3;
0323                     }
0324 
0325                     if(nofDisturbingLines > 0)
0326                     {
0327                         Diff3LineList::iterator i3_last_equal_A = end();
0328 
0329                         i3 = i3c;
0330                         while(i3 != i3b)
0331                         {
0332                             if(i3->isEqualAB())
0333                             {
0334                                 i3_last_equal_A = i3;
0335                             }
0336                             ++i3;
0337                         }
0338 
0339                         /* If i3_last_equal_A isn't still set to d3ll.end(), then
0340                         * we've found a line in A that is equal to one in B
0341                         * somewhere between i3c and i3b
0342                         */
0343                         bool before_or_on_equal_line_in_A = (i3_last_equal_A != end());
0344 
0345                         // Move the disturbing lines up, out of sight.
0346                         i3 = i3c;
0347                         while(i3 != i3b)
0348                         {
0349                             if(i3->getLineB().isValid() ||
0350                             (before_or_on_equal_line_in_A && i3->getLineA().isValid()))
0351                             {
0352                                 d3l.setLineB(i3->getLineB());
0353                                 i3->setLineB(LineRef::invalid);
0354 
0355                                 // Move A along if it matched B
0356                                 if(before_or_on_equal_line_in_A)
0357                                 {
0358                                     d3l.setLineA(i3->getLineA());
0359                                     d3l.bAEqB = i3->isEqualAB();
0360                                     i3->setLineA(LineRef::invalid);
0361                                     i3->bAEqC = false;
0362                                 }
0363 
0364                                 i3->bAEqB = false;
0365                                 i3->bBEqC = false;
0366                                 insert(i3c, d3l);
0367                             }
0368 
0369                             if(i3 == i3_last_equal_A)
0370                             {
0371                                 before_or_on_equal_line_in_A = false;
0372                             }
0373 
0374                             ++i3;
0375                         }
0376                         //Not currently needed as we get here everytime nofDisturbingLines > 0
0377                         //nofDisturbingLines = 0;
0378                     }
0379 
0380                     // Was checking if nofDisturbingLines == 0 which would always be true. See above.
0381                     // Yes, the line from B can be moved.
0382                     i3b->setLineB(LineRef::invalid); // This might leave an empty line: removed later.
0383                     i3b->bAEqB = false;
0384                     i3b->bBEqC = false;
0385                     i3c->setLineB(lineB);
0386                     i3c->bBEqC = true;
0387                     i3c->bAEqB = i3c->isEqualAC();
0388                 }
0389                 else if(i3b1 == i3c && !i3c->isEqualAC())
0390                 {
0391                     Diff3LineList::iterator i3 = i3b;
0392                     quint32 nofDisturbingLines = 0;
0393                     while(i3 != i3c && i3 != end())
0394                     {
0395                         if(i3->getLineC().isValid())
0396                             ++nofDisturbingLines;
0397                         ++i3;
0398                     }
0399 
0400                     if(nofDisturbingLines > 0)
0401                     {
0402                         Diff3LineList::iterator i3_last_equal_A = end();
0403 
0404                         i3 = i3b;
0405                         while(i3 != i3c)
0406                         {
0407                             if(i3->isEqualAC())
0408                             {
0409                                 i3_last_equal_A = i3;
0410                             }
0411                             ++i3;
0412                         }
0413 
0414                         /* If i3_last_equal_A isn't still set to d3ll.end(), then
0415                         * we've found a line in A that is equal to one in C
0416                         * somewhere between i3b and i3c
0417                         */
0418                         bool before_or_on_equal_line_in_A = (i3_last_equal_A != end());
0419 
0420                         // Move the disturbing lines up.
0421                         i3 = i3b;
0422                         while(i3 != i3c)
0423                         {
0424                             if(i3->getLineC().isValid() ||
0425                             (before_or_on_equal_line_in_A && i3->getLineA().isValid()))
0426                             {
0427                                 d3l.setLineC(i3->getLineC());
0428                                 i3->setLineC(LineRef::invalid);
0429 
0430                                 // Move A along if it matched C
0431                                 if(before_or_on_equal_line_in_A)
0432                                 {
0433                                     d3l.setLineA(i3->getLineA());
0434                                     d3l.bAEqC = i3->isEqualAC();
0435                                     i3->setLineA(LineRef::invalid);
0436                                     i3->bAEqB = false;
0437                                 }
0438 
0439                                 i3->bAEqC = false;
0440                                 i3->bBEqC = false;
0441                                 insert(i3b, d3l);
0442                             }
0443 
0444                             if(i3 == i3_last_equal_A)
0445                             {
0446                                 before_or_on_equal_line_in_A = false;
0447                             }
0448 
0449                             ++i3;
0450                         }
0451                         //Not currently needed as we get here everytime nofDisturbingLines > 0
0452                         //nofDisturbingLines = 0;
0453                     }
0454 
0455                     // Only do this if nofDisturbingLines == 0 currently always true
0456                     // Yes, the line from C can be moved.
0457                     i3c->setLineC(LineRef::invalid); // This might leave an empty line: removed later.
0458                     i3c->bAEqC = false;
0459                     i3c->bBEqC = false;
0460                     i3b->setLineC(lineC);
0461                     i3b->bBEqC = true;
0462                     i3b->bAEqC = i3b->isEqualAB();
0463                 }
0464             }
0465 
0466             d.adjustNumberOfEquals(-1);
0467             ++lineB;
0468             ++lineC;
0469             ++i3b;
0470             ++i3c;
0471         }
0472 
0473         while(d.diff1() > 0)
0474         {
0475             Diff3Line d3l;
0476             Diff3LineList::iterator i3 = i3b;
0477 
0478             while(i3->getLineB() != lineB)
0479                 ++i3;
0480             if(i3 != i3b && !i3->isEqualAB())
0481             {
0482                 // Take B from this line and move it up as far as possible
0483                 d3l.setLineB(lineB);
0484                 insert(i3b, d3l);
0485                 i3->setLineB(LineRef::invalid);
0486             }
0487             else
0488             {
0489                 i3b = i3;
0490             }
0491             d.adjustDiff1(-1);
0492             ++lineB;
0493             ++i3b;
0494 
0495             if(d.diff2() > 0)
0496             {
0497                 d.adjustDiff2(-1);
0498                 ++lineC;
0499             }
0500         }
0501 
0502         lineC += (LineRef)d.diff2();
0503     }
0504     /*
0505    Diff3LineList::iterator it = d3ll.begin();
0506    qint32 li=0;
0507    for( ; it!=d3ll.end(); ++it, ++li )
0508    {
0509       printf( "%4d %4d %4d %4d  A%c=B A%c=C B%c=C\n",
0510          li, it->getLineA(), it->getLineB(), it->getLineC(),
0511          it->isEqualAB() ? '=' : '!', it->isEqualAC() ? '=' : '!', it->isEqualBC() ? '=' : '!' );
0512    }
0513    printf("\n");*/
0514 }
0515 
0516 // Test if the move would pass a barrier. Return true if not.
0517 bool ManualDiffHelpList::isValidMove(LineRef line1, LineRef line2, e_SrcSelector winIdx1, e_SrcSelector winIdx2) const
0518 {
0519     if(line1.isValid() && line2.isValid())
0520     {
0521         for(const ManualDiffHelpEntry& mdhe: *this)
0522         {
0523             if(!mdhe.isValidMove(line1, line2, winIdx1, winIdx2)) return false;
0524         }
0525     }
0526     return true; // no barrier passed.
0527 }
0528 
0529 void ManualDiffHelpList::insertEntry(e_SrcSelector winIdx, LineRef firstLine, LineRef lastLine)
0530 {
0531     // The manual diff help list must be sorted and compact.
0532     // "Compact" means that upper items can't be empty if lower items contain data.
0533 
0534     // First insert the new item without regarding compactness.
0535     // If the new item overlaps with previous items then the previous items will be removed.
0536 
0537     ManualDiffHelpEntry mdhe(winIdx, firstLine, lastLine);
0538 
0539     ManualDiffHelpList::iterator i;
0540     for(i = begin(); i != end(); ++i)
0541     {
0542         LineRef& l1 = i->firstLine(winIdx);
0543         LineRef& l2 = i->lastLine(winIdx);
0544         if(l1.isValid() && l2.isValid())
0545         {
0546             if((firstLine <= l1 && lastLine >= l1) || (firstLine <= l2 && lastLine >= l2))
0547             {
0548                 // overlap
0549                 l1.invalidate();
0550                 l2.invalidate();
0551             }
0552             else if(firstLine < l1 && lastLine < l1)
0553             {
0554                 // insert before this position
0555                 insert(i, mdhe);
0556                 break;
0557             }
0558         }
0559     }
0560     if(i == end())
0561     {
0562         insert(i, mdhe);
0563     }
0564 
0565     // Now make the list compact
0566     for(i = begin(); i != end();)
0567     {
0568         ManualDiffHelpList::iterator next = std::next(i);
0569         if(next != end())
0570         {
0571             for(e_SrcSelector wIdx = e_SrcSelector::A; wIdx != e_SrcSelector::Invalid; wIdx = nextSelector(wIdx))
0572             {
0573                 if(!i->firstLine(wIdx).isValid() && next->firstLine(wIdx).isValid())
0574                 {
0575                     std::swap(i->firstLine(wIdx), next->firstLine(wIdx));
0576                     std::swap(i->lastLine(wIdx), next->lastLine(wIdx));
0577                 }
0578             }
0579         }
0580         //Delete completely empty entries
0581         if(*i == ManualDiffHelpEntry())
0582             erase(i);
0583         i = next;
0584     }
0585 }
0586 
0587 bool ManualDiffHelpEntry::isValidMove(LineRef line1, LineRef line2, e_SrcSelector winIdx1, e_SrcSelector winIdx2) const
0588 {
0589     // Barrier
0590     LineRef l1 = winIdx1 == e_SrcSelector::A ? lineA1 : winIdx1 == e_SrcSelector::B ? lineB1 : lineC1;
0591     LineRef l2 = winIdx2 == e_SrcSelector::A ? lineA1 : winIdx2 == e_SrcSelector::B ? lineB1 : lineC1;
0592 
0593     if(l1.isValid() && l2.isValid())
0594     {
0595         if((line1 >= l1 && line2 < l2) || (line1 < l1 && line2 >= l2))
0596             return false;
0597         l1 = winIdx1 == e_SrcSelector::A ? lineA2 : winIdx1 == e_SrcSelector::B ? lineB2 : lineC2;
0598         l2 = winIdx2 == e_SrcSelector::A ? lineA2 : winIdx2 == e_SrcSelector::B ? lineB2 : lineC2;
0599         ++l1;
0600         ++l2;
0601         if((line1 >= l1 && line2 < l2) || (line1 < l1 && line2 >= l2))
0602             return false;
0603     }
0604 
0605     return true;
0606 }
0607 
0608 qint32 ManualDiffHelpEntry::calcManualDiffFirstDiff3LineIdx(const Diff3LineVector& d3lv)
0609 {
0610     QtSizeType i;
0611     for(i = 0; i < d3lv.size(); ++i)
0612     {
0613         const Diff3Line* d3l = d3lv[i];
0614         if((lineA1.isValid() && lineA1 == d3l->getLineA()) ||
0615            (lineB1.isValid() && lineB1 == d3l->getLineB()) ||
0616            (lineC1.isValid() && lineC1 == d3l->getLineC()))
0617             return SafeInt<qint32>(i);
0618     }
0619     return -1;
0620 }
0621 
0622 void DiffList::runDiff(const std::shared_ptr<LineDataVector>& p1, const size_t index1, LineRef size1, const std::shared_ptr<LineDataVector>& p2, const size_t index2, LineRef size2)
0623 {
0624     ProgressScope pp;
0625     static GnuDiff gnuDiff; // All values are initialized with zeros.
0626 
0627     ProgressProxy::setCurrent(0);
0628 
0629     clear();
0630     if(p1->empty() || (*p1)[index1].getBuffer() == nullptr || p2->empty() || (*p2)[index2].getBuffer() == nullptr || size1 == 0 || size2 == 0)
0631     {
0632         if(!p1->empty() && !p2->empty() && (*p1)[index1].getBuffer() == nullptr && (*p2)[index2].getBuffer() == nullptr && size1 == size2)
0633             push_back(Diff(size1, 0, 0));
0634         else
0635         {
0636             push_back(Diff(0, size1, size2));
0637         }
0638     }
0639     else
0640     {
0641         assert((size_t)size1 < p1->size() && (size_t)size2 < p2->size());
0642 
0643         GnuDiff::comparison comparisonInput;
0644         memset(&comparisonInput, 0, sizeof(comparisonInput));
0645         comparisonInput.parent = nullptr;
0646         comparisonInput.file[0].buffer = (*p1)[index1].getBuffer()->unicode() + (*p1)[index1].getOffset();                                         //ptr to buffer
0647         comparisonInput.file[0].buffered = ((*p1)[index1 + size1 - 1].getOffset() + (*p1)[index1 + size1 - 1].size() - (*p1)[index1].getOffset()); // size of buffer
0648         comparisonInput.file[1].buffer = (*p2)[index2].getBuffer()->unicode() + (*p2)[index2].getOffset();                                         //ptr to buffer
0649         comparisonInput.file[1].buffered = ((*p2)[index2 + size2 - 1].getOffset() + (*p2)[index2 + size2 - 1].size() - (*p2)[index2].getOffset()); // size of buffer
0650 
0651         gnuDiff.ignore_white_space = GnuDiff::IGNORE_ALL_SPACE; // I think nobody needs anything else ...
0652         gnuDiff.bIgnoreWhiteSpace = true;
0653         gnuDiff.bIgnoreNumbers = gOptions->m_bIgnoreNumbers;
0654         gnuDiff.minimal = gOptions->m_bTryHard;
0655         gnuDiff.ignore_case = false;
0656         GnuDiff::change* script = gnuDiff.diff_2_files(&comparisonInput);
0657 
0658         LineRef equalLinesAtStart = (LineRef)comparisonInput.file[0].prefix_lines;
0659         LineRef currentLine1 = 0;
0660         LineRef currentLine2 = 0;
0661         GnuDiff::change* p = nullptr;
0662         for(GnuDiff::change* e = script; e; e = p)
0663         {
0664             Diff d((LineType)(e->line0 - currentLine1), e->deleted, e->inserted);
0665             assert(d.numberOfEquals() == e->line1 - currentLine2);
0666 
0667             currentLine1 += LineRef((quint64)d.numberOfEquals() + d.diff1());
0668             currentLine2 += LineRef((quint64)d.numberOfEquals() + d.diff2());
0669             assert(currentLine1 <= size1 && currentLine2 <= size2);
0670             push_back(d);
0671 
0672             p = e->link;
0673             free(e);
0674         }
0675 
0676         if(empty())
0677         {
0678             qint32 numofEquals = std::min(size1, size2);
0679             Diff d(numofEquals, size1 - numofEquals, size2 - numofEquals);
0680 
0681             push_back(d);
0682         }
0683         else
0684         {
0685             front().adjustNumberOfEquals(equalLinesAtStart);
0686             currentLine1 += equalLinesAtStart;
0687             currentLine2 += equalLinesAtStart;
0688 
0689             LineType nofEquals = std::min(size1 - currentLine1, size2 - currentLine2);
0690             if(nofEquals == 0)
0691             {
0692                 back().adjustDiff1(size1 - currentLine1);
0693                 back().adjustDiff2(size2 - currentLine2);
0694             }
0695             else
0696             {
0697                 Diff d(nofEquals, size1 - currentLine1 - nofEquals, size2 - currentLine2 - nofEquals);
0698                 push_back(d);
0699             }
0700         }
0701     }
0702 #ifndef NDEBUG
0703     verify(size1, size2);
0704 #endif
0705     ProgressProxy::setCurrent(1);
0706 }
0707 
0708 #ifndef NDEBUG
0709 // Verify difflist
0710 void DiffList::verify(const LineRef size1, const LineRef size2)
0711 {
0712     LineRef l1 = 0;
0713     LineRef l2 = 0;
0714 
0715     for(const Diff& curDiff: *this)
0716     {
0717         assert(curDiff.numberOfEquals() >= 0);
0718         assert(curDiff.diff1() <= limits<LineType>::max() && curDiff.diff2() <= limits<LineType>::max());
0719         l1 += curDiff.numberOfEquals() + LineRef(curDiff.diff1());
0720         l2 += curDiff.numberOfEquals() + LineRef(curDiff.diff2());
0721     }
0722 
0723     assert(l1 == size1 && l2 == size2);
0724 }
0725 #endif
0726 
0727 void ManualDiffHelpList::runDiff(const std::shared_ptr<LineDataVector>& p1, LineRef size1, const std::shared_ptr<LineDataVector>& p2, LineRef size2, DiffList& diffList,
0728                                  e_SrcSelector winIdx1, e_SrcSelector winIdx2)
0729 {
0730     diffList.clear();
0731     DiffList diffList2;
0732 
0733     qint32 l1begin = 0;
0734     qint32 l2begin = 0;
0735 
0736     for(const ManualDiffHelpEntry& mdhe: *this)
0737     {
0738         LineRef l1end = mdhe.getLine1(winIdx1);
0739         LineRef l2end = mdhe.getLine1(winIdx2);
0740 
0741         if(l1end.isValid() && l2end.isValid())
0742         {
0743             diffList2.runDiff(p1, l1begin, l1end - l1begin, p2, l2begin, l2end - l2begin);
0744             diffList.splice(diffList.end(), diffList2);
0745             l1begin = l1end;
0746             l2begin = l2end;
0747 
0748             l1end = mdhe.getLine2(winIdx1);
0749             l2end = mdhe.getLine2(winIdx2);
0750 
0751             if(l1end.isValid() && l2end.isValid())
0752             {
0753                 ++l1end; // point to line after last selected line
0754                 ++l2end;
0755                 diffList2.runDiff(p1, l1begin, l1end - l1begin, p2, l2begin, l2end - l2begin);
0756                 diffList.splice(diffList.end(), diffList2);
0757                 l1begin = l1end;
0758                 l2begin = l2end;
0759             }
0760         }
0761     }
0762     diffList2.runDiff(p1, l1begin, size1 - l1begin, p2, l2begin, size2 - l2begin);
0763     diffList.splice(diffList.end(), diffList2);
0764 }
0765 
0766 void Diff3LineList::correctManualDiffAlignment(ManualDiffHelpList* pManualDiffHelpList)
0767 {
0768     if(pManualDiffHelpList->empty())
0769         return;
0770 
0771     // If a line appears unaligned in comparison to the manual alignment, correct this.
0772 
0773     ManualDiffHelpList::iterator iMDHL;
0774     for(iMDHL = pManualDiffHelpList->begin(); iMDHL != pManualDiffHelpList->end(); ++iMDHL)
0775     {
0776         Diff3LineList::iterator i3 = begin();
0777         e_SrcSelector missingWinIdx = e_SrcSelector::None;
0778         qint32 alignedSum = (!iMDHL->getLine1(e_SrcSelector::A).isValid() ? 0 : 1) + (!iMDHL->getLine1(e_SrcSelector::B).isValid() ? 0 : 1) + (!iMDHL->getLine1(e_SrcSelector::C).isValid() ? 0 : 1);
0779         if(alignedSum == 2)
0780         {
0781             // If only A & B are aligned then let C rather be aligned with A
0782             // If only A & C are aligned then let B rather be aligned with A
0783             // If only B & C are aligned then let A rather be aligned with B
0784             missingWinIdx = !iMDHL->getLine1(e_SrcSelector::A).isValid() ? e_SrcSelector::A : (!iMDHL->getLine1(e_SrcSelector::B).isValid() ? e_SrcSelector::B : e_SrcSelector::C);
0785         }
0786         else if(alignedSum <= 1)
0787         {
0788             return;
0789         }
0790 
0791         // At the first aligned line, move up the two other lines into new d3ls until the second input is aligned
0792         // Then move up the third input until all three lines are aligned.
0793         e_SrcSelector wi = e_SrcSelector::None;
0794         for(; i3 != end(); ++i3)
0795         {
0796             for(wi = e_SrcSelector::A; wi != e_SrcSelector::Invalid; wi=nextSelector(wi))
0797             {
0798                 if(i3->getLineInFile(wi).isValid() && iMDHL->firstLine(wi) == i3->getLineInFile(wi))
0799                     break;
0800             }
0801             if(wi != e_SrcSelector::Invalid)
0802                 break;
0803         }
0804 
0805         if(wi >= e_SrcSelector::A && wi <= e_SrcSelector::Max)
0806         {
0807             // Found manual alignment for one source
0808             Diff3LineList::iterator iDest = i3;
0809 
0810             // Move lines up until the next firstLine is found. Omit wi from move and search.
0811             e_SrcSelector wi2 = e_SrcSelector::None;
0812             for(; i3 != end(); ++i3)
0813             {
0814                 for(wi2 = e_SrcSelector::A; wi2 != e_SrcSelector::Invalid; wi2 = nextSelector(wi2))
0815                 {
0816                     if(wi != wi2 && i3->getLineInFile(wi2).isValid() && iMDHL->firstLine(wi2) == i3->getLineInFile(wi2))
0817                         break;
0818                 }
0819                 if(wi2 == e_SrcSelector::Invalid)
0820                 { // Not yet found
0821                     // Move both others up
0822                     Diff3Line d3l;
0823                     // Move both up
0824                     if(wi == e_SrcSelector::A) // Move B and C up
0825                     {
0826                         d3l.bBEqC = i3->isEqualBC();
0827                         d3l.setLineB(i3->getLineB());
0828                         d3l.setLineC(i3->getLineC());
0829                         i3->setLineB(LineRef::invalid);
0830                         i3->setLineC(LineRef::invalid);
0831                     }
0832                     if(wi == e_SrcSelector::B) // Move A and C up
0833                     {
0834                         d3l.bAEqC = i3->isEqualAC();
0835                         d3l.setLineA(i3->getLineA());
0836                         d3l.setLineC(i3->getLineC());
0837                         i3->setLineA(LineRef::invalid);
0838                         i3->setLineC(LineRef::invalid);
0839                     }
0840                     if(wi == e_SrcSelector::C) // Move A and B up
0841                     {
0842                         d3l.bAEqB = i3->isEqualAB();
0843                         d3l.setLineA(i3->getLineA());
0844                         d3l.setLineB(i3->getLineB());
0845                         i3->setLineA(LineRef::invalid);
0846                         i3->setLineB(LineRef::invalid);
0847                     }
0848                     i3->bAEqB = false;
0849                     i3->bAEqC = false;
0850                     i3->bBEqC = false;
0851                     insert(iDest, d3l);
0852                 }
0853                 else
0854                 {
0855                     // align the found line with the line we already have here
0856                     if(i3 != iDest)
0857                     {
0858                         if(wi2 == e_SrcSelector::A)
0859                         {
0860                             iDest->setLineA(i3->getLineA());
0861                             i3->setLineA(LineRef::invalid);
0862                             i3->bAEqB = false;
0863                             i3->bAEqC = false;
0864                         }
0865                         else if(wi2 == e_SrcSelector::B)
0866                         {
0867                             iDest->setLineB(i3->getLineB());
0868                             i3->setLineB(LineRef::invalid);
0869                             i3->bAEqB = false;
0870                             i3->bBEqC = false;
0871                         }
0872                         else if(wi2 == e_SrcSelector::C)
0873                         {
0874                             iDest->setLineC(i3->getLineC());
0875                             i3->setLineC(LineRef::invalid);
0876                             i3->bBEqC = false;
0877                             i3->bAEqC = false;
0878                         }
0879                     }
0880 
0881                     if(missingWinIdx != e_SrcSelector::None)
0882                     {
0883                         for(; i3 != end(); ++i3)
0884                         {
0885                             e_SrcSelector wi3 = missingWinIdx;
0886                             if(i3->getLineInFile(wi3).isValid())
0887                             {
0888                                 // not found, move the line before iDest
0889                                 Diff3Line d3l;
0890                                 if(wi3 == e_SrcSelector::A)
0891                                 {
0892                                     if(i3->isEqualAB()) // Stop moving lines up if one equal is found.
0893                                         break;
0894                                     d3l.setLineA(i3->getLineA());
0895                                     i3->setLineA(LineRef::invalid);
0896                                     i3->bAEqB = false;
0897                                     i3->bAEqC = false;
0898                                 }
0899                                 if(wi3 == e_SrcSelector::B)
0900                                 {
0901                                     if(i3->isEqualAB())
0902                                         break;
0903                                     d3l.setLineB(i3->getLineB());
0904                                     i3->setLineB(LineRef::invalid);
0905                                     i3->bAEqB = false;
0906                                     i3->bBEqC = false;
0907                                 }
0908                                 if(wi3 == e_SrcSelector::C)
0909                                 {
0910                                     if(i3->isEqualAC())
0911                                         break;
0912                                     d3l.setLineC(i3->getLineC());
0913                                     i3->setLineC(LineRef::invalid);
0914                                     i3->bAEqC = false;
0915                                     i3->bBEqC = false;
0916                                 }
0917                                 insert(iDest, d3l);
0918                             }
0919                         } // for(), searching for wi3
0920                     }
0921                     break;
0922                 }
0923             } // for(), searching for wi2
0924         }     // if, wi found
0925     }         // for (iMDHL)
0926 }
0927 
0928 // Fourth step
0929 void Diff3LineList::calcDiff3LineListTrim(
0930     const std::shared_ptr<LineDataVector> &pldA, const std::shared_ptr<LineDataVector> &pldB, const std::shared_ptr<LineDataVector> &pldC, ManualDiffHelpList* pManualDiffHelpList)
0931 {
0932     const Diff3Line d3l_empty;
0933     remove(d3l_empty);
0934 
0935     Diff3LineList::iterator lookAhead = begin();
0936     Diff3LineList::iterator i3A = begin();
0937     Diff3LineList::iterator i3B = begin();
0938     Diff3LineList::iterator i3C = begin();
0939 
0940     qint32 line = 0;  // diff3line counters
0941     qint32 lineA = 0; //
0942     qint32 lineB = 0;
0943     qint32 lineC = 0;
0944 
0945     ManualDiffHelpList::iterator iMDHL = pManualDiffHelpList->begin();
0946     // The iterator lookAhead is the variable line look ahead.
0947     // The iterators i3A, i3B, i3C and corresponding lineA, lineB and lineC stop at empty lines, if found.
0948     // If possible, then the texts from the look ahead will be moved back to the empty places.
0949 
0950     for(; lookAhead != end(); ++lookAhead, ++line)
0951     {
0952         if(iMDHL != pManualDiffHelpList->end())
0953         {
0954             if((lookAhead->getLineA().isValid() && lookAhead->getLineA() == iMDHL->getLine1(e_SrcSelector::A)) ||
0955                (lookAhead->getLineB().isValid() && lookAhead->getLineB() == iMDHL->getLine1(e_SrcSelector::B)) ||
0956                (lookAhead->getLineC().isValid() && lookAhead->getLineC() == iMDHL->getLine1(e_SrcSelector::C)))
0957             {
0958                 i3A = lookAhead;
0959                 i3B = lookAhead;
0960                 i3C = lookAhead;
0961                 lineA = line;
0962                 lineB = line;
0963                 lineC = line;
0964                 ++iMDHL;
0965             }
0966         }
0967 
0968         if(line > lineA && lookAhead->getLineA().isValid() && i3A->getLineB().isValid() && i3A->isEqualBC() &&
0969            LineData::equal((*pldA)[lookAhead->getLineA()], (*pldB)[i3A->getLineB()]) &&
0970            pManualDiffHelpList->isValidMove(lookAhead->getLineA(), i3A->getLineB(), e_SrcSelector::A, e_SrcSelector::B) &&
0971            pManualDiffHelpList->isValidMove(lookAhead->getLineA(), i3A->getLineC(), e_SrcSelector::A, e_SrcSelector::C))
0972         {
0973             // Empty space for A. A matches B and C in the empty line. Move it up.
0974             i3A->setLineA(lookAhead->getLineA());
0975             i3A->bAEqB = true;
0976             i3A->bAEqC = true;
0977 
0978             lookAhead->setLineA(LineRef::invalid);
0979             lookAhead->bAEqB = false;
0980             lookAhead->bAEqC = false;
0981             ++i3A;
0982             ++lineA;
0983         }
0984 
0985         if(line > lineB && lookAhead->getLineB().isValid() && i3B->getLineA().isValid() && i3B->isEqualAC() &&
0986            LineData::equal((*pldB)[lookAhead->getLineB()], (*pldA)[i3B->getLineA()]) &&
0987            pManualDiffHelpList->isValidMove(lookAhead->getLineB(), i3B->getLineA(), e_SrcSelector::B, e_SrcSelector::A) &&
0988            pManualDiffHelpList->isValidMove(lookAhead->getLineB(), i3B->getLineC(), e_SrcSelector::B, e_SrcSelector::C))
0989         {
0990             // Empty space for B. B matches A and C in the empty line. Move it up.
0991             i3B->setLineB(lookAhead->getLineB());
0992             i3B->bAEqB = true;
0993             i3B->bBEqC = true;
0994             lookAhead->setLineB(LineRef::invalid);
0995             lookAhead->bAEqB = false;
0996             lookAhead->bBEqC = false;
0997             ++i3B;
0998             ++lineB;
0999         }
1000 
1001         if(line > lineC && lookAhead->getLineC().isValid() && i3C->getLineA().isValid() && i3C->isEqualAB() &&
1002            LineData::equal((*pldC)[lookAhead->getLineC()], (*pldA)[i3C->getLineA()]) &&
1003            pManualDiffHelpList->isValidMove(lookAhead->getLineC(), i3C->getLineA(), e_SrcSelector::C, e_SrcSelector::A) &&
1004            pManualDiffHelpList->isValidMove(lookAhead->getLineC(), i3C->getLineB(), e_SrcSelector::C, e_SrcSelector::B))
1005         {
1006             // Empty space for C. C matches A and B in the empty line. Move it up.
1007             i3C->setLineC(lookAhead->getLineC());
1008             i3C->bAEqC = true;
1009             i3C->bBEqC = true;
1010             lookAhead->setLineC(LineRef::invalid);
1011             lookAhead->bAEqC = false;
1012             lookAhead->bBEqC = false;
1013             ++i3C;
1014             ++lineC;
1015         }
1016 
1017         if(line > lineA && lookAhead->getLineA().isValid() && !lookAhead->isEqualAB() && !lookAhead->isEqualAC() &&
1018            pManualDiffHelpList->isValidMove(lookAhead->getLineA(), i3A->getLineB(), e_SrcSelector::A, e_SrcSelector::B) &&
1019            pManualDiffHelpList->isValidMove(lookAhead->getLineA(), i3A->getLineC(), e_SrcSelector::A, e_SrcSelector::C))
1020         {
1021             // Empty space for A. A doesn't match B or C. Move it up.
1022             i3A->setLineA(lookAhead->getLineA());
1023             lookAhead->setLineA(LineRef::invalid);
1024 
1025             if(i3A->getLineB().isValid() && LineData::equal((*pldA)[i3A->getLineA()], (*pldB)[i3A->getLineB()]))
1026             {
1027                 i3A->bAEqB = true;
1028             }
1029             if((i3A->isEqualAB() && i3A->isEqualBC()) ||
1030                (i3A->getLineC().isValid() && LineData::equal((*pldA)[i3A->getLineA()], (*pldC)[i3A->getLineC()])))
1031             {
1032                 i3A->bAEqC = true;
1033             }
1034 
1035             ++i3A;
1036             ++lineA;
1037         }
1038 
1039         if(line > lineB && lookAhead->getLineB().isValid() && !lookAhead->isEqualAB() && !lookAhead->isEqualBC() &&
1040            pManualDiffHelpList->isValidMove(lookAhead->getLineB(), i3B->getLineA(), e_SrcSelector::B, e_SrcSelector::A) &&
1041            pManualDiffHelpList->isValidMove(lookAhead->getLineB(), i3B->getLineC(), e_SrcSelector::B, e_SrcSelector::C))
1042         {
1043             // Empty space for B. B matches neither A nor C. Move B up.
1044             i3B->setLineB(lookAhead->getLineB());
1045             lookAhead->setLineB(LineRef::invalid);
1046 
1047             if(i3B->getLineA().isValid() && LineData::equal((*pldA)[i3B->getLineA()], (*pldB)[i3B->getLineB()]))
1048             {
1049                 i3B->bAEqB = true;
1050             }
1051             if((i3B->isEqualAB() && i3B->isEqualAC()) ||
1052                (i3B->getLineC().isValid() && LineData::equal((*pldB)[i3B->getLineB()], (*pldC)[i3B->getLineC()])))
1053             {
1054                 i3B->bBEqC = true;
1055             }
1056 
1057             ++i3B;
1058             ++lineB;
1059         }
1060 
1061         if(line > lineC && lookAhead->getLineC().isValid() && !lookAhead->isEqualAC() && !lookAhead->isEqualBC() &&
1062            pManualDiffHelpList->isValidMove(lookAhead->getLineC(), i3C->getLineA(), e_SrcSelector::C, e_SrcSelector::A) &&
1063            pManualDiffHelpList->isValidMove(lookAhead->getLineC(), i3C->getLineB(), e_SrcSelector::C, e_SrcSelector::B))
1064         {
1065             // Empty space for C. C matches neither A nor B. Move C up.
1066             i3C->setLineC(lookAhead->getLineC());
1067             lookAhead->setLineC(LineRef::invalid);
1068 
1069             if(i3C->getLineA().isValid() && LineData::equal((*pldA)[i3C->getLineA()], (*pldC)[i3C->getLineC()]))
1070             {
1071                 i3C->bAEqC = true;
1072             }
1073             if((i3C->isEqualAC() && i3C->isEqualAB()) ||
1074                (i3C->getLineB().isValid() && LineData::equal((*pldB)[i3C->getLineB()], (*pldC)[i3C->getLineC()])))
1075             {
1076                 i3C->bBEqC = true;
1077             }
1078 
1079             ++i3C;
1080             ++lineC;
1081         }
1082 
1083         if(line > lineA && line > lineB && lookAhead->getLineA().isValid() && lookAhead->isEqualAB() && !lookAhead->isEqualAC())
1084         {
1085             // Empty space for A and B. A matches B, but not C. Move A & B up.
1086             Diff3LineList::iterator i = lineA > lineB ? i3A : i3B;
1087             qint32 l = lineA > lineB ? lineA : lineB;
1088 
1089             if(pManualDiffHelpList->isValidMove(i->getLineC(), lookAhead->getLineA(), e_SrcSelector::C, e_SrcSelector::A) &&
1090                pManualDiffHelpList->isValidMove(i->getLineC(), lookAhead->getLineB(), e_SrcSelector::C, e_SrcSelector::B))
1091             {
1092                 i->setLineA(lookAhead->getLineA());
1093                 i->setLineB(lookAhead->getLineB());
1094                 i->bAEqB = true;
1095 
1096                 if(i->getLineC().isValid() && LineData::equal((*pldA)[i->getLineA()], (*pldC)[i->getLineC()]))
1097                 {
1098                     i->bAEqC = true;
1099                     i->bBEqC = true;
1100                 }
1101 
1102                 lookAhead->setLineA(LineRef::invalid);
1103                 lookAhead->setLineB(LineRef::invalid);
1104                 lookAhead->bAEqB = false;
1105                 i3A = i;
1106                 i3B = i;
1107                 ++i3A;
1108                 ++i3B;
1109                 lineA = l + 1;
1110                 lineB = l + 1;
1111             }
1112         }
1113         else if(line > lineA && line > lineC && lookAhead->getLineA().isValid() && lookAhead->isEqualAC() && !lookAhead->isEqualAB())
1114         {
1115             // Empty space for A and C. A matches C, but not B. Move A & C up.
1116             Diff3LineList::iterator i = lineA > lineC ? i3A : i3C;
1117             qint32 l = lineA > lineC ? lineA : lineC;
1118 
1119             if(pManualDiffHelpList->isValidMove(i->getLineB(), lookAhead->getLineA(), e_SrcSelector::B, e_SrcSelector::A) &&
1120                pManualDiffHelpList->isValidMove(i->getLineB(), lookAhead->getLineC(), e_SrcSelector::B, e_SrcSelector::C))
1121             {
1122                 i->setLineA(lookAhead->getLineA());
1123                 i->setLineC(lookAhead->getLineC());
1124                 i->bAEqC = true;
1125 
1126                 if(i->getLineB().isValid() && LineData::equal((*pldA)[i->getLineA()], (*pldB)[i->getLineB()]))
1127                 {
1128                     i->bAEqB = true;
1129                     i->bBEqC = true;
1130                 }
1131 
1132                 lookAhead->setLineA(LineRef::invalid);
1133                 lookAhead->setLineC(LineRef::invalid);
1134                 lookAhead->bAEqC = false;
1135                 i3A = i;
1136                 i3C = i;
1137                 ++i3A;
1138                 ++i3C;
1139                 lineA = l + 1;
1140                 lineC = l + 1;
1141             }
1142         }
1143         else if(line > lineB && line > lineC && lookAhead->getLineB().isValid() && lookAhead->isEqualBC() && !lookAhead->isEqualAC())
1144         {
1145             // Empty space for B and C. B matches C, but not A. Move B & C up.
1146             Diff3LineList::iterator i = lineB > lineC ? i3B : i3C;
1147             qint32 l = lineB > lineC ? lineB : lineC;
1148             if(pManualDiffHelpList->isValidMove(i->getLineA(), lookAhead->getLineB(), e_SrcSelector::A, e_SrcSelector::B) &&
1149                pManualDiffHelpList->isValidMove(i->getLineA(), lookAhead->getLineC(), e_SrcSelector::A, e_SrcSelector::C))
1150             {
1151                 i->setLineB(lookAhead->getLineB());
1152                 i->setLineC(lookAhead->getLineC());
1153                 i->bBEqC = true;
1154 
1155                 if(i->getLineA().isValid() && LineData::equal((*pldA)[i->getLineA()], (*pldB)[i->getLineB()]))
1156                 {
1157                     i->bAEqB = true;
1158                     i->bAEqC = true;
1159                 }
1160 
1161                 lookAhead->setLineB(LineRef::invalid);
1162                 lookAhead->setLineC(LineRef::invalid);
1163                 lookAhead->bBEqC = false;
1164                 i3B = i;
1165                 i3C = i;
1166                 ++i3B;
1167                 ++i3C;
1168                 lineB = l + 1;
1169                 lineC = l + 1;
1170             }
1171         }
1172 
1173         if(lookAhead->getLineA().isValid())
1174         {
1175             lineA = line + 1;
1176             i3A = lookAhead;
1177             ++i3A;
1178         }
1179         if(lookAhead->getLineB().isValid())
1180         {
1181             lineB = line + 1;
1182             i3B = lookAhead;
1183             ++i3B;
1184         }
1185         if(lookAhead->getLineC().isValid())
1186         {
1187             lineC = line + 1;
1188             i3C = lookAhead;
1189             ++i3C;
1190         }
1191     }
1192 
1193     remove(d3l_empty);
1194 
1195     /*
1196 
1197    Diff3LineList::iterator it = d3ll.begin();
1198    qint32 li=0;
1199    for( ; it!=d3ll.end(); ++it, ++li )
1200    {
1201       printf( "%4d %4d %4d %4d  A%c=B A%c=C B%c=C\n",
1202          li, it->getLineA(), it->getLineB(), it->getLineC(),
1203          it->isEqualAB() ? '=' : '!', it->isEqualAC() ? '=' : '!', it->isEqualBC() ? '=' : '!' );
1204 
1205    }
1206 */
1207 }
1208 
1209 void DiffBufferInfo::init(Diff3LineList* pD3ll,
1210                           const std::shared_ptr<LineDataVector> &pldA, const std::shared_ptr<LineDataVector> &pldB, const std::shared_ptr<LineDataVector> &pldC)
1211 {
1212     m_pDiff3LineList = pD3ll;
1213     mLineDataA = pldA;
1214     mLineDataB = pldB;
1215     mLineDataC = pldC;
1216 }
1217 
1218 void Diff3LineList::calcWhiteDiff3Lines(
1219     const std::shared_ptr<LineDataVector> &pldA, const std::shared_ptr<LineDataVector> &pldB, const std::shared_ptr<LineDataVector> &pldC, const bool bIgnoreComments)
1220 {
1221     for(Diff3Line& diff3Line: *this)
1222     {
1223         diff3Line.bWhiteLineA = (!diff3Line.getLineA().isValid() || (*pldA)[diff3Line.getLineA()].whiteLine() || (bIgnoreComments && (*pldA)[diff3Line.getLineA()].isPureComment()));
1224         diff3Line.bWhiteLineB = (!diff3Line.getLineB().isValid() || (*pldB)[diff3Line.getLineB()].whiteLine() || (bIgnoreComments && (*pldB)[diff3Line.getLineB()].isPureComment()));
1225         diff3Line.bWhiteLineC = (!diff3Line.getLineC().isValid() || (*pldC)[diff3Line.getLineC()].whiteLine() || (bIgnoreComments && (*pldC)[diff3Line.getLineC()].isPureComment()));
1226     }
1227 }
1228 
1229 // My own diff-invention:
1230 /*
1231     Builds DiffList for scratch. Automaticly clears all previous data in list.
1232 */
1233 void DiffList::calcDiff(const QString& line1, const QString& line2, const qint32 maxSearchRange)
1234 {
1235     clear();
1236 
1237     const QChar* p1end = line1.constData() + line1.size();
1238     const QChar* p2end = line2.constData() + line2.size();
1239 
1240     QString::const_iterator p1 = line1.cbegin(), p2 = line2.cbegin();
1241 
1242     /*
1243         This loop should never reach the exit condition specified here. However it must have a hard wired
1244         stopping point to prevent runaway allocation if something unexpected happens.
1245         diffList is therefor hard capped at aprox 50 MB in size.
1246      */
1247     for(; size() * sizeof(Diff) + sizeof(DiffList) < (50 << 20);)
1248     {
1249         qint32 nofEquals = 0;
1250         while(p1 != line1.cend() && p2 != line2.cend() && *p1 == *p2)
1251         {
1252             ++p1;
1253             ++p2;
1254             ++nofEquals;
1255         }
1256 
1257         bool bBestValid = false;
1258         qint32 bestI1 = 0;
1259         qint32 bestI2 = 0;
1260         qint32 i1 = 0;
1261         qint32 i2 = 0;
1262 
1263         for(i1 = 0;; ++i1)
1264         {
1265             if(&p1[i1] == p1end || (bBestValid && i1 >= bestI1 + bestI2))
1266             {
1267                 break;
1268             }
1269             for(i2 = 0; i2 < maxSearchRange; ++i2)
1270             {
1271                 if (&p2[i2] == p2end || (bBestValid && i1 + i2 >= bestI1 + bestI2))
1272                 {
1273                     break;
1274                 }
1275                 else if(p2[i2] == p1[i1] &&
1276                         (abs(i1 - i2) < 3 || (&p2[i2 + 1] == p2end && &p1[i1 + 1] == p1end) ||
1277                          (&p2[i2 + 1] != p2end && &p1[i1 + 1] != p1end && p2[i2 + 1] == p1[i1 + 1])))
1278                 {
1279                     if(i1 + i2 < bestI1 + bestI2 || !bBestValid)
1280                     {
1281                         bestI1 = i1;
1282                         bestI2 = i2;
1283                         bBestValid = true;
1284                         break;
1285                     }
1286                 }
1287             }
1288             /*
1289                 Bail this should never happen.
1290                 Acts back stop against harder to detect overfollow issues.
1291             */
1292             if(Q_UNLIKELY(i1 == limits<decltype(i1)>::max()))
1293             {
1294                 assert(false);
1295                 throw std::range_error("Too many diffs");
1296             }
1297         }
1298 
1299         bool bEndReached = false;
1300         if(bBestValid)
1301         {
1302             // The match was found using the strict search. Go back if there are non-strict
1303             // matches.
1304             while(bestI1 >= 1 && bestI2 >= 1 && p1[bestI1 - 1] == p2[bestI2 - 1])
1305             {
1306                 --bestI1;
1307                 --bestI2;
1308             }
1309             // continue somehow
1310             Diff d(nofEquals, bestI1, bestI2);
1311             assert(nofEquals + bestI1 + bestI2 != 0);
1312             push_back(d);
1313 
1314             p1 += bestI1;
1315             p2 += bestI2;
1316         }
1317         else
1318         {
1319             // NOTE: Very consitantly entered with p1end == p1 and p2end == p2
1320             // Nothing else to match.
1321             Diff d(nofEquals, p1end - p1, p2end - p2);
1322             push_back(d);
1323 
1324             bEndReached = true; //break;
1325         }
1326 
1327         // Sometimes the algorithm that chooses the first match unfortunately chooses
1328         // a match where later actually equal parts don't match anymore.
1329         // A different match could be achieved, if we start at the end.
1330         // Do it, if it would be a better match.
1331         qint32 nofUnmatched = 0;
1332         QString::const_iterator pu1 = p1 - 1;
1333         QString::const_iterator pu2 = p2 - 1;
1334 
1335         while(pu1 >= line1.begin() && pu2 >= line2.begin() && *pu1 == *pu2)
1336         {
1337             ++nofUnmatched;
1338             --pu1;
1339             --pu2;
1340         }
1341 
1342         if(nofUnmatched > 0)
1343         {
1344             // We want to go backwards the nofUnmatched elements and redo
1345             // the matching
1346             Diff d = back();
1347             const Diff origBack = d;
1348             pop_back();
1349 
1350             while(nofUnmatched > 0)
1351             {
1352                 if(d.diff1() > 0 && d.diff2() > 0)
1353                 {
1354                     d.adjustDiff1(-1);
1355                     d.adjustDiff2(-1);
1356                     --nofUnmatched;
1357                 }
1358                 else if(d.numberOfEquals() > 0)
1359                 {
1360                     d.adjustNumberOfEquals(-1);
1361                     --nofUnmatched;
1362                 }
1363 
1364                 if(d.numberOfEquals() == 0 && (d.diff1() == 0 || d.diff2() == 0) && nofUnmatched > 0)
1365                 {
1366                     if(empty())
1367                         break;
1368                     d.adjustNumberOfEquals(back().numberOfEquals());
1369                     d.adjustDiff1(back().diff1());
1370                     d.adjustDiff2(back().diff2());
1371                     pop_back();
1372                     bEndReached = false;
1373                 }
1374             }
1375 
1376             if(bEndReached)
1377                 push_back(origBack);
1378             else
1379             {
1380 
1381                 p1 = pu1 + 1 + nofUnmatched;
1382                 p2 = pu2 + 1 + nofUnmatched;
1383                 push_back(d);
1384             }
1385         }
1386         if(bEndReached)
1387             break;
1388     }
1389 
1390     assert(size() * sizeof(Diff) + sizeof(DiffList) <= (50 << 20));
1391 
1392 #ifndef NDEBUG
1393     // Verify difflist
1394     {
1395 
1396         qint32 l1 = 0;
1397         qint32 l2 = 0;
1398 
1399         for(const Diff& theDiff: *this)
1400         {
1401             l1 += (theDiff.numberOfEquals() + theDiff.diff1());
1402             l2 += (theDiff.numberOfEquals() + theDiff.diff2());
1403         }
1404 
1405         assert(l1 == line1.size() && l2 == line2.size());
1406     }
1407 #endif // !NDEBUG
1408 }
1409 //Compute fineDiff
1410 void DiffList::optimize()
1411 {
1412     DiffList::iterator dli;
1413     bool bUsefulFineDiff = false;
1414     qint64 index = 0;
1415 
1416     for(const Diff& diff: *this)
1417     {
1418         if(diff.numberOfEquals() >= 4)
1419         {
1420             bUsefulFineDiff = true;
1421             break;
1422         }
1423     }
1424 
1425     for(Diff& diff: *this)
1426     {
1427         if(!bUsefulFineDiff || index <= 0)
1428             diff.refine();
1429 
1430         ++index;
1431     }
1432 }
1433 
1434 bool Diff3Line::fineDiff(bool inBTextsTotalEqual, const e_SrcSelector selector, const std::shared_ptr<LineDataVector> &v1, const std::shared_ptr<LineDataVector> &v2, const IgnoreFlags eIgnoreFlags)
1435 {
1436     LineRef k1 = 0;
1437     LineRef k2 = 0;
1438     qint32 maxSearchLength = 500;
1439     bool bTextsTotalEqual = inBTextsTotalEqual;
1440     bool bIgnoreComments = eIgnoreFlags & IgnoreFlag::ignoreComments;
1441     bool bIgnoreWhiteSpace = eIgnoreFlags & IgnoreFlag::ignoreWhiteSpace;
1442 
1443     assert(selector == e_SrcSelector::A || selector == e_SrcSelector::B || selector == e_SrcSelector::C);
1444 
1445     if(selector == e_SrcSelector::A)
1446     {
1447         k1 = getLineA();
1448         k2 = getLineB();
1449     }
1450     else if(selector == e_SrcSelector::B)
1451     {
1452         k1 = getLineB();
1453         k2 = getLineC();
1454     }
1455     else if(selector == e_SrcSelector::C)
1456     {
1457         k1 = getLineC();
1458         k2 = getLineA();
1459     }
1460 
1461     qCDebug(kdiffCore) << "k1 = " << k1 << ", k2 = " << k2;
1462     if((!k1.isValid() && k2.isValid()) || (k1.isValid() && !k2.isValid())) bTextsTotalEqual = false;
1463     if(k1.isValid() && k2.isValid())
1464     {
1465         assert(((unsigned long)k1) <= (*v1).size() && (*v1)[k1].getBuffer() != nullptr);
1466         assert(((unsigned long)k2) <= (*v2).size() && (*v2)[k2].getBuffer() != nullptr);
1467 
1468         if((*v1)[k1].size() != (*v2)[k2].size() || QString::compare((*v1)[k1].getLine(), (*v2)[k2].getLine()) != 0)
1469         {
1470             bTextsTotalEqual = false;
1471             auto pDiffList = std::make_shared<DiffList>();
1472             pDiffList->calcDiff((*v1)[k1].getLine(), (*v2)[k2].getLine(), maxSearchLength);
1473 
1474             // Optimize the diff list.
1475             pDiffList->optimize();
1476             setFineDiff(selector, pDiffList);
1477         }
1478         /*
1479             Override default euality for white lines and comments.
1480         */
1481         if(((bIgnoreComments && (*v1)[k1].isSkipable()) || (bIgnoreWhiteSpace && (*v1)[k1].whiteLine())) && ((bIgnoreComments && (*v2)[k2].isSkipable()) || (bIgnoreWhiteSpace && (*v2)[k2].whiteLine())))
1482         {
1483             if(selector == e_SrcSelector::A)
1484             {
1485                 bAEqB = true;
1486             }
1487             else if(selector == e_SrcSelector::B)
1488             {
1489                 bBEqC = true;
1490             }
1491             else if(selector == e_SrcSelector::C)
1492             {
1493                 bAEqC = true;
1494             }
1495         }
1496     }
1497 
1498     return bTextsTotalEqual;
1499 }
1500 
1501 void Diff3Line::getLineInfo(const e_SrcSelector winIdx, const bool isTriple, LineRef& lineIdx,
1502                             std::shared_ptr<const DiffList>& pFineDiff1, std::shared_ptr<const DiffList>& pFineDiff2, // return values
1503                             ChangeFlags& changed, ChangeFlags& changed2) const
1504 {
1505     changed = NoChange;
1506     changed2 = NoChange;
1507     bool bAEqualB = this->isEqualAB() || (bWhiteLineA && bWhiteLineB);
1508     bool bAEqualC = this->isEqualAC() || (bWhiteLineA && bWhiteLineC);
1509     bool bBEqualC = this->isEqualBC() || (bWhiteLineB && bWhiteLineC);
1510 
1511     assert(winIdx >= e_SrcSelector::A && winIdx <= e_SrcSelector::C);
1512     if(winIdx == e_SrcSelector::A)
1513     {
1514         lineIdx = getLineA();
1515         pFineDiff1 = pFineAB;
1516         pFineDiff2 = pFineCA;
1517 
1518         changed = ((!getLineB().isValid()) != (!lineIdx.isValid()) ? AChanged : NoChange) |
1519                    ((!getLineC().isValid()) != (!lineIdx.isValid()) && isTriple ? BChanged : NoChange);
1520         changed2 = (bAEqualB ? NoChange : AChanged) | (bAEqualC || !isTriple ? NoChange : BChanged);
1521     }
1522     else if(winIdx == e_SrcSelector::B)
1523     {
1524         lineIdx = getLineB();
1525         pFineDiff1 = pFineBC;
1526         pFineDiff2 = pFineAB;
1527         changed = ((!getLineC().isValid()) != (!lineIdx.isValid()) && isTriple ? AChanged : NoChange) |
1528                    ((!getLineA().isValid()) != (!lineIdx.isValid()) ? BChanged : NoChange);
1529         changed2 = (bBEqualC || !isTriple ? NoChange : AChanged) | (bAEqualB ? NoChange : BChanged);
1530     }
1531     else if(winIdx == e_SrcSelector::C)
1532     {
1533         lineIdx = getLineC();
1534         pFineDiff1 = pFineCA;
1535         pFineDiff2 = pFineBC;
1536         changed = ((!getLineA().isValid()) != (!lineIdx.isValid()) ? AChanged : NoChange) |
1537                    ((!getLineB().isValid()) != (!lineIdx.isValid()) ? BChanged : NoChange);
1538         changed2 = (bAEqualC ? NoChange : AChanged) | (bBEqualC ? NoChange : BChanged);
1539     }
1540 }
1541 
1542 bool Diff3LineList::fineDiff(const e_SrcSelector selector, const std::shared_ptr<LineDataVector> &v1, const std::shared_ptr<LineDataVector> &v2, const IgnoreFlags eIgnoreFlags)
1543 {
1544     // Finetuning: Diff each line with deltas
1545     ProgressScope pp;
1546     bool bTextsTotalEqual = true;
1547     size_t listSize = size();
1548     ProgressProxy::setMaxNofSteps(listSize);
1549 
1550     for(Diff3Line &diff: *this)
1551     {
1552         bTextsTotalEqual = diff.fineDiff(bTextsTotalEqual, selector, v1, v2, eIgnoreFlags);
1553         ProgressProxy::step();
1554     }
1555     return bTextsTotalEqual;
1556 }
1557 
1558 // Convert the list to a vector of pointers
1559 void Diff3LineList::calcDiff3LineVector(Diff3LineVector& d3lv)
1560 {
1561     d3lv.resize(SafeInt<QtSizeType>(size()));
1562     Diff3LineList::iterator i;
1563     QtSizeType j = 0;
1564     for(i = begin(); i != end(); ++i, ++j)
1565     {
1566         d3lv[j] = &(*i);
1567     }
1568     assert(j == d3lv.size());
1569 }
1570 
1571 // Just make sure that all input lines are in the output too, exactly once.
1572 void Diff3LineList::debugLineCheck(const LineType size, const e_SrcSelector srcSelector) const
1573 {
1574     //FIXME:Does not work when m_pOptions->m_bDiff3AlignBC is set.
1575     LineType i = 0;
1576 
1577     for(const Diff3Line &entry: *this)
1578     {
1579         LineRef line;
1580 
1581         assert(srcSelector == e_SrcSelector::A || srcSelector == e_SrcSelector::B || srcSelector == e_SrcSelector::C);
1582         if(srcSelector == e_SrcSelector::A)
1583             line = entry.getLineA();
1584         else if(srcSelector == e_SrcSelector::B)
1585             line = entry.getLineB();
1586         else if(srcSelector == e_SrcSelector::C)
1587             line = entry.getLineC();
1588 
1589         if(line.isValid())
1590         {
1591             if(line != i)
1592             {
1593                 #ifndef AUTOTEST
1594                 KMessageBox::error(nullptr, i18n("Data loss error:\n"
1595                                                  "If it is reproducible please contact the author.\n"),
1596                                    i18n("Severe Internal Error"));
1597                 #endif
1598 
1599                 qCCritical(kdiffMain) << "Severe Internal Error." << " line != i for srcSelector=" << (qint32)srcSelector << "\n";
1600                 ::exit(-1);
1601             }
1602             ++i;
1603         }
1604     }
1605 
1606     if(size != i)
1607     {
1608         #ifndef AUTOTEST
1609         KMessageBox::error(nullptr, i18n(
1610                                   "Data loss error:\n"
1611                                   "If it is reproducible please contact the author.\n"),
1612                            i18n("Severe Internal Error"));
1613         #endif
1614 
1615         qCCritical(kdiffMain) << "Severe Internal Error.: " << size << " != " << i << "\n";
1616         ::exit(-1);
1617     }
1618 }
1619 
1620 void Diff3LineList::findHistoryRange(const QRegularExpression& historyStart, bool bThreeFiles, HistoryRange& range) const
1621 {
1622     QString historyLead;
1623     // Search for start of history
1624     for(range.start = begin(), range.startIdx = 0; range.start != end(); ++range.start, ++range.startIdx)
1625     {
1626         if(historyStart.match(range.start->getString(e_SrcSelector::A)).hasMatch() &&
1627            historyStart.match(range.start->getString(e_SrcSelector::B)).hasMatch() &&
1628            (!bThreeFiles || historyStart.match(range.start->getString(e_SrcSelector::C)).hasMatch()))
1629         {
1630             historyLead = Utils::calcHistoryLead(range.start->getString(e_SrcSelector::A));
1631             break;
1632         }
1633     }
1634     // Search for end of history
1635     for(range.end = range.start, range.endIdx = range.startIdx; range.end != end(); ++range.end, ++range.endIdx)
1636     {
1637         const QString sA = range.end->getString(e_SrcSelector::A);
1638         const QString sB = range.end->getString(e_SrcSelector::B);
1639         const QString sC = range.end->getString(e_SrcSelector::C);
1640         if((!sA.isEmpty() && historyLead != Utils::calcHistoryLead(sA)) ||
1641            (!sB.isEmpty() && historyLead != Utils::calcHistoryLead(sB)) ||
1642            (bThreeFiles && !sC.isEmpty() && historyLead != Utils::calcHistoryLead(sC)))
1643         {
1644             break; // End of the history
1645         }
1646     }
1647 }
1648 
1649 void Diff3LineList::dump()
1650 {
1651     QTextStream out(stdout);
1652     quint32 i = 1;
1653     out << "---begin----\n";
1654     for(const Diff3Line &diffRec : *this)
1655     {
1656         out << "line = " << i<< "\n";
1657         out << "lineA = " << diffRec.getLineA()<< "\n";
1658         out << "lineB = " << diffRec.getLineB()<< "\n";
1659         out << "lineC = " << diffRec.getLineC()<< "\n";
1660 
1661         out << "isEqualAB = " << diffRec.isEqualAB()<< "\n";
1662         out << "isEqualAC = " << diffRec.isEqualAC()<< "\n";
1663         out << "isEqualBC = " << diffRec.isEqualBC()<< "\n";
1664         ++i;
1665     }
1666 
1667     out << "---end----\n";
1668 }