kdiff3/test/alignmenttest.cpp

0001 /*
0002   SPDX-FileCopyrightText: 2002-2007 Joachim Eibl, joachim.eibl at gmx.de
0003   SPDX-FileCopyrightText: 2018-2020 Michael Reeves reeves.87@gmail.com
0004   SPDX-License-Identifier: GPL-2.0-or-later
0005 */
0006 #include "diff.h"
0007 #include "gnudiff_diff.h"
0008 #include "LineRef.h"
0009 #include "options.h"
0010 #include "progress.h"
0011 #include "SourceData.h"
0012
0013 #include <iostream>
0014 #include <memory>
0015 #include <stdio.h>
0016
0017 #include <QDirIterator>
0018 #include <QRegularExpression>
0019 #include <QTextCodec>
0020 #include <QTextStream>
0021
0022
0023 #define i18n(s) s
0024
0025 bool verbose = false;
0026 std::unique_ptr<Options> gOptions = nullptr;
0027 ManualDiffHelpList m_manualDiffHelpList;
0028
0029 void printDiffList(const QString caption, const DiffList &diffList)
0030 {
0031    QTextStream out(stdout);
0032    DiffList::const_iterator i;
0033
0034    out << "Printing difflist " << caption << ":" << endl;
0035    out << "  nofEquals, diff1, diff2" << endl;
0036
0037    for(i = diffList.begin(); i != diffList.end(); i++)
0038    {
0039       out << "  " << i->numberOfEquals() << "," << i->diff1() << "," << i->diff2() << endl;
0040    }
0041 }
0042
0043 void printDiff3List(const Diff3LineList &diff3LineList,
0044                    const SourceData &sd1,
0045                    const SourceData &sd2,
0046                    const SourceData &sd3,
0047                    bool forceVerbosity=false)
0048 {
0049    const int columnsize = 30;
0050    const int linenumsize = 6;
0051    Diff3LineList::const_iterator i;
0052    for ( i=diff3LineList.begin(); i!=diff3LineList.end(); ++i )
0053    {
0054       QTextStream out(stdout);
0055       QString lineAText;
0056       QString lineBText;
0057       QString lineCText;
0058
0059       const Diff3Line& d3l = *i;
0060
0061       if(d3l.getLineA().isValid())
0062       {
0063          const LineData *pLineData = &sd1.getLineDataForDiff()->at(d3l.getLineA());
0064          lineAText = pLineData->getLine();
0065          lineAText.replace(QString("\r"), QString("\\r"));
0066          lineAText.replace(QString("\n"), QString("\\n"));
0067          lineAText = QString("%1 %2").arg(d3l.getLineA(), linenumsize).arg(lineAText.left(columnsize - linenumsize - 1));
0068       }
0069
0070       if(d3l.getLineB().isValid())
0071       {
0072          const LineData *pLineData = &sd2.getLineDataForDiff()->at(d3l.getLineB());
0073          lineBText = pLineData->getLine();
0074          lineBText.replace(QString("\r"), QString("\\r"));
0075          lineBText.replace(QString("\n"), QString("\\n"));
0076          lineBText = QString("%1 %2").arg(d3l.getLineB(), linenumsize).arg(lineBText.left(columnsize - linenumsize - 1));
0077       }
0078
0079       if(d3l.getLineC().isValid())
0080       {
0081          const LineData *pLineData = &sd3.getLineDataForDiff()->at(d3l.getLineC());
0082          lineCText = pLineData->getLine();
0083          lineCText.replace(QString("\r"), QString("\\r"));
0084          lineCText.replace(QString("\n"), QString("\\n"));
0085          lineCText = QString("%1 %2").arg(d3l.getLineC(), linenumsize).arg(lineCText.left(columnsize - linenumsize - 1));
0086       }
0087
0088       out << QString("%1 %2 %3").arg(lineAText, -columnsize)
0089                                 .arg(lineBText, -columnsize)
0090                                 .arg(lineCText, -columnsize);
0091       if(verbose || forceVerbosity)
0092       {
0093          out << " " << d3l.isEqualAB() << " " << d3l.isEqualBC() << " " << d3l.isEqualAC();
0094       }
0095
0096       out << endl;
0097    }
0098 }
0099
0100 void printDiff3List(QString caption,
0101                    const Diff3LineList &diff3LineList,
0102                    const SourceData &sd1,
0103                    const SourceData &sd2,
0104                    const SourceData &sd3,
0105                    bool forceVerbosity=false)
0106 {
0107    QTextStream out(stdout);
0108    out << "Printing diff3list " << caption << ":" << endl;
0109    printDiff3List(diff3LineList, sd1, sd2, sd3, forceVerbosity);
0110 }
0111
0112 void determineFileAlignment(SourceData &m_sd1, SourceData &m_sd2, SourceData &m_sd3, Diff3LineList &m_diff3LineList)
0113 {
0114    DiffList m_diffList12;
0115    DiffList m_diffList23;
0116    DiffList m_diffList13;
0117
0118    m_diff3LineList.clear();
0119
0120    // Run the diff.
0121    if ( m_sd3.isEmpty() )
0122    {
0123       m_manualDiffHelpList.runDiff(m_sd1.getLineDataForDiff(), m_sd1.getSizeLines(), m_sd2.getLineDataForDiff(), m_sd2.getSizeLines(), m_diffList12, e_SrcSelector::A, e_SrcSelector::B);
0124       m_diff3LineList.calcDiff3LineListUsingAB( &m_diffList12);
0125       m_diff3LineList.fineDiff(e_SrcSelector::A, m_sd1.getLineDataForDisplay(), m_sd2.getLineDataForDisplay(), IgnoreFlag::none);
0126    }
0127    else
0128    {
0129       m_manualDiffHelpList.runDiff(m_sd1.getLineDataForDiff(), m_sd1.getSizeLines(), m_sd2.getLineDataForDiff(), m_sd2.getSizeLines(), m_diffList12, e_SrcSelector::A, e_SrcSelector::B);
0130       m_manualDiffHelpList.runDiff(m_sd2.getLineDataForDiff(), m_sd2.getSizeLines(), m_sd3.getLineDataForDiff(), m_sd3.getSizeLines(), m_diffList23, e_SrcSelector::B, e_SrcSelector::C);
0131       m_manualDiffHelpList.runDiff(m_sd1.getLineDataForDiff(), m_sd1.getSizeLines(), m_sd3.getLineDataForDiff(), m_sd3.getSizeLines(), m_diffList13, e_SrcSelector::A, e_SrcSelector::C);
0132
0133       if (verbose)
0134       {
0135          printDiffList("m_diffList12", m_diffList12);
0136          printDiffList("m_diffList23", m_diffList23);
0137          printDiffList("m_diffList13", m_diffList13);
0138       }
0139
0140       m_diff3LineList.calcDiff3LineListUsingAB( &m_diffList12);
0141       if (verbose) printDiff3List("after calcDiff3LineListUsingAB", m_diff3LineList, m_sd1, m_sd2, m_sd3);
0142
0143       m_diff3LineList.calcDiff3LineListUsingAC( &m_diffList13);
0144       if (verbose) printDiff3List("after calcDiff3LineListUsingAC", m_diff3LineList, m_sd1, m_sd2, m_sd3);
0145
0146       m_diff3LineList.correctManualDiffAlignment(&m_manualDiffHelpList );
0147       m_diff3LineList.calcDiff3LineListTrim(m_sd1.getLineDataForDiff(), m_sd2.getLineDataForDiff(), m_sd3.getLineDataForDiff(), &m_manualDiffHelpList );
0148       if (verbose) printDiff3List("after 1st calcDiff3LineListTrim", m_diff3LineList, m_sd1, m_sd2, m_sd3);
0149
0150       if(gOptions->m_bDiff3AlignBC)
0151       {
0152          m_diff3LineList.calcDiff3LineListUsingBC( &m_diffList23);
0153          if (verbose) printDiff3List("after calcDiff3LineListUsingBC", m_diff3LineList, m_sd1, m_sd2, m_sd3);
0154          m_diff3LineList.correctManualDiffAlignment( &m_manualDiffHelpList );
0155          m_diff3LineList.calcDiff3LineListTrim(m_sd1.getLineDataForDiff(), m_sd2.getLineDataForDiff(), m_sd3.getLineDataForDiff(), &m_manualDiffHelpList );
0156          if (verbose) printDiff3List("after 2nd calcDiff3LineListTrim", m_diff3LineList, m_sd1, m_sd2, m_sd3);
0157       }
0158
0159       m_diff3LineList.fineDiff(e_SrcSelector::A, m_sd1.getLineDataForDisplay(), m_sd2.getLineDataForDisplay(), IgnoreFlag::none );
0160       m_diff3LineList.fineDiff(e_SrcSelector::B, m_sd2.getLineDataForDisplay(), m_sd3.getLineDataForDisplay(), IgnoreFlag::none );
0161       m_diff3LineList.fineDiff(e_SrcSelector::C, m_sd3.getLineDataForDisplay(), m_sd1.getLineDataForDisplay(), IgnoreFlag::none );
0162    }
0163    m_diff3LineList.calcWhiteDiff3Lines( m_sd1.getLineDataForDiff(), m_sd2.getLineDataForDiff(), m_sd3.getLineDataForDiff(), false);
0164 }
0165
0166 QString getLineFromSourceData(const SourceData &sd, int line)
0167 {
0168    const LineData *pLineData = &sd.getLineDataForDiff()->at(line);
0169    QString lineText = pLineData->getLine();
0170    lineText.replace(QString("\r"), QString("\\r"));
0171    lineText.replace(QString("\n"), QString("\\n"));
0172    return lineText;
0173 }
0174
0175
0176 void loadExpectedAlignmentFile(QString expectedResultFileName, Diff3LineList &expectedDiff3LineList)
0177 {
0178    Diff3Line d3l;
0179
0180    expectedDiff3LineList.clear();
0181
0182    QFile file(expectedResultFileName);
0183    QString line;
0184    if ( file.open(QIODevice::ReadOnly) )
0185    {
0186       QTextStream t( &file );
0187       while ( !t.atEnd() )
0188       {
0189          QStringList lst = t.readLine().split(QRegularExpression("\\s+"));
0190          d3l.setLineA(lst.at(0).toInt());
0191          d3l.setLineB(lst.at(1).toInt());
0192          d3l.setLineC(lst.at(2).toInt());
0193
0194          expectedDiff3LineList.push_back( d3l );
0195       }
0196       file.close();
0197    }
0198 }
0199
0200 void writeActualAlignmentFile(QString actualResultFileName, const Diff3LineList &actualDiff3LineList)
0201 {
0202    Diff3LineList::const_iterator p_d3l;
0203
0204    QFile file(actualResultFileName);
0205    if ( file.open(QIODevice::WriteOnly) )
0206    {
0207       {
0208          QTextStream t( &file );
0209
0210          for(p_d3l = actualDiff3LineList.begin(); p_d3l != actualDiff3LineList.end(); p_d3l++)
0211          {
0212             t << p_d3l->getLineA() << " " << p_d3l->getLineB() << " " << p_d3l->getLineC() << endl;
0213          }
0214       }
0215       file.close();
0216    }
0217 }
0218
0219 bool dataIsConsistent(LineRef line1, QString &line1Text, LineRef line2, QString &line2Text, bool equal)
0220 {
0221    bool consistent = false;
0222
0223    if(!line1.isValid() || line2.isValid())
0224    {
0225       consistent = !equal;
0226    }
0227    else
0228    {
0229       /* If the equal boolean is true the line content must be the same,
0230        * if the line content is different the boolean should be false,
0231        * but other than that we can't be sure:
0232        * - if the line content is the same the boolean may not be true because
0233        *   GNU diff may have put that line as a removal in the first file and
0234        *   an addition in the second.
0235        * - also the comparison this test does between lines considers all
0236        *   whitespace equal, while GNU diff doesn't (for instance U+0020 vs U+00A0)
0237        */
0238       if(equal)
0239       {
0240          consistent = (line1Text == line2Text);
0241       }
0242       else if (line1Text != line2Text)
0243       {
0244          consistent = !equal;
0245       }
0246       else
0247       {
0248          consistent = true;
0249       }
0250
0251    }
0252    return consistent;
0253 }
0254
0255 bool runTest(QString file1, QString file2, QString file3, QString expectedResultFile, QString actualResultFile, int maxLength)
0256 {
0257    gOptions = std::make_unique < Options();
0258    Diff3LineList actualDiff3LineList, expectedDiff3LineList;
0259    QTextCodec *p_codec = QTextCodec::codecForName("UTF-8");
0260    QTextStream out(stdout);
0261
0262    gOptions->m_bIgnoreCase = false;
0263    gOptions->m_bDiff3AlignBC = true;
0264
0265    SourceData m_sd1, m_sd2, m_sd3;
0266
0267    QString msgprefix = "Running test with ";
0268    QString filepattern = QString(file1).replace("_base.", "_*.");
0269    QString msgsuffix = QString("...%1").arg("", maxLength - filepattern.length());
0270    out << msgprefix << filepattern << msgsuffix;
0271    if(verbose)
0272    {
0273       out << endl;
0274    }
0275    out.flush();
0276
0277    m_sd1.setFilename(file1);
0278    m_sd1.readAndPreprocess(p_codec, false);
0279
0280    m_sd2.setFilename(file2);
0281    m_sd2.readAndPreprocess(p_codec, false);
0282
0283    m_sd3.setFilename(file3);
0284    m_sd3.readAndPreprocess(p_codec, false);
0285
0286    determineFileAlignment(m_sd1, m_sd2, m_sd3, actualDiff3LineList);
0287
0288    loadExpectedAlignmentFile(expectedResultFile, expectedDiff3LineList);
0289
0290    Diff3LineList::iterator p_actual = actualDiff3LineList.begin();
0291    Diff3LineList::iterator p_expected = expectedDiff3LineList.begin();
0292    bool equal = true;
0293    bool sequenceError = false;
0294    bool consistencyError = false;
0295
0296    equal = (actualDiff3LineList.size() == expectedDiff3LineList.size());
0297
0298    int latestLineA = -1;
0299    int latestLineB = -1;
0300    int latestLineC = -1;
0301    while(equal && (p_actual != actualDiff3LineList.end()))
0302    {
0303       /* Check if all line numbers are in sequence */
0304       if(p_actual->getLineA().isValid())
0305       {
0306          if(p_actual->getLineA() <= latestLineA)
0307          {
0308             sequenceError = true;
0309          }
0310          else
0311          {
0312             latestLineA = p_actual->getLineA();
0313          }
0314       }
0315       if(p_actual->getLineB().isValid())
0316       {
0317          if(p_actual->getLineB() <= latestLineB)
0318          {
0319             sequenceError = true;
0320          }
0321          else
0322          {
0323             latestLineB = p_actual->getLineB();
0324          }
0325       }
0326       if(p_actual->getLineC().isValid())
0327       {
0328          if(p_actual->getLineC() <= latestLineC)
0329          {
0330             sequenceError = true;
0331          }
0332          else
0333          {
0334             latestLineC = p_actual->getLineC();
0335          }
0336       }
0337
0338       /* Check if the booleans that indicate if lines are equal are consistent with the content of the lines */
0339       QString lineAText = (!p_actual->getLineA().isValid()) ? "" : getLineFromSourceData(m_sd1, p_actual->getLineA()).simplified().replace(" ", "");
0340       QString lineBText = (!p_actual->getLineB().isValid()) ? "" : getLineFromSourceData(m_sd2, p_actual->getLineB()).simplified().replace(" ", "");
0341       QString lineCText = (!p_actual->getLineC().isValid()) ? "" : getLineFromSourceData(m_sd3, p_actual->getLineC()).simplified().replace(" ", "");
0342
0343       if(!dataIsConsistent(p_actual->getLineA(), lineAText, p_actual->getLineB(), lineBText, p_actual->isEqualAB()))
0344       {
0345          if(verbose) out << "inconsistency: line " << p_actual->getLineA() << " of A vs line " << p_actual->getLineB() << " of B" << endl;
0346          consistencyError = true;
0347       }
0348       if(!dataIsConsistent(p_actual->getLineB(), lineBText, p_actual->getLineC(), lineCText, p_actual->isEqualBC()))
0349       {
0350          if(verbose) out << "inconsistency: line " << p_actual->getLineB() << " of B vs line " << p_actual->getLineC() << " of C" << endl;
0351          consistencyError = true;
0352       }
0353       if(!dataIsConsistent(p_actual->getLineA(), lineAText, p_actual->getLineC(), lineCText, p_actual->isEqualAC()))
0354       {
0355          if(verbose) out << "inconsistency: line " << p_actual->getLineA() << " of A vs line " << p_actual->getLineC() << " of C" << endl;
0356          consistencyError = true;
0357       }
0358
0359       /* Check if the actual output of the algorithm is equal to the expected output */
0360       equal = (p_actual->getLineA() == p_expected->getLineA()) &&
0361               (p_actual->getLineB() == p_expected->getLineB()) &&
0362               (p_actual->getLineC() == p_expected->getLineC());
0363       p_actual++;
0364       p_expected++;
0365    }
0366
0367    if(sequenceError)
0368    {
0369       out << "NOK" << endl;
0370
0371       out << "Actual result has incorrectly sequenced line numbers:" << endl;
0372       out << "----------------------------------------------------------------------------------------------" << endl;
0373       printDiff3List(actualDiff3LineList, m_sd1, m_sd2, m_sd3);
0374    }
0375    else if(consistencyError)
0376    {
0377       out << "NOK" << endl;
0378
0379       out << "Actual result has inconsistent equality booleans:" << endl;
0380       out << "----------------------------------------------------------------------------------------------" << endl;
0381       printDiff3List(actualDiff3LineList, m_sd1, m_sd2, m_sd3, true);
0382    }
0383    else if(equal)
0384    {
0385       out << "OK" << endl;
0386    }
0387    else
0388    {
0389       out << "NOK" << endl;
0390
0391       writeActualAlignmentFile(actualResultFile, actualDiff3LineList);
0392
0393       out << "Actual result (written to " << actualResultFile << "):" << endl;
0394       out << "----------------------------------------------------------------------------------------------" << endl;
0395       printDiff3List(actualDiff3LineList, m_sd1, m_sd2, m_sd3);
0396       out << "----------------------------------------------------------------------------------------------" << endl;
0397       out << "Expected result:" << endl;
0398       out << "----------------------------------------------------------------------------------------------" << endl;
0399       printDiff3List(expectedDiff3LineList, m_sd1, m_sd2, m_sd3);
0400       out << "----------------------------------------------------------------------------------------------" << endl;
0401    }
0402
0403    return equal;
0404 }
0405
0406
0407 QStringList gettestdatafiles(QString testdir)
0408 {
0409    QStringList baseFilePaths;
0410    QTextStream out(stdout);
0411    QStringList nameFilter;
0412    nameFilter << "*_base.*";
0413
0414    QDir testdatadir(testdir);
0415
0416    QStringList baseFileNames = testdatadir.entryList(nameFilter, QDir::Files, QDir::Name);
0417    QListIterator<QString> file_it(baseFileNames);
0418    while(file_it.hasNext())
0419    {
0420       baseFilePaths.append(testdir + "/" + file_it.next());
0421    }
0422    out << testdir << ": " << baseFilePaths.size() << " files" << endl;
0423
0424
0425    QStringList subdirs = testdatadir.entryList(QDir::Dirs | QDir::NoDotAndDotDot, QDir::Name);
0426    QListIterator<QString> dir_it(subdirs);
0427
0428    while (dir_it.hasNext())
0429    {
0430       QString subdir = dir_it.next();
0431       QStringList subdirBaseFilePaths = gettestdatafiles(testdir + "/" + subdir);
0432
0433       baseFilePaths.append(subdirBaseFilePaths);
0434    }
0435
0436    return baseFilePaths;
0437 }
0438
0439
0440 int main(int argc, char *argv[])
0441 {
0442    bool allOk = true;
0443    int maxLength = 0;
0444    QTextStream out(stdout);
0445    QDir testdatadir("testdata");
0446
0447    /* Print data at various steps in the algorithm to get an idea where to look for the root cause of a failing test */
0448    if((argc == 2) && (!strcmp(argv[1], "-v")))
0449    {
0450       verbose = true;
0451    }
0452
0453    QStringList baseFiles = gettestdatafiles("testdata");
0454    QListIterator<QString> it(baseFiles);
0455
0456    for (int i = 0; i < baseFiles.size(); i++)
0457    {
0458       maxLength = std::max(baseFiles.at(i).length(), maxLength);
0459    }
0460    maxLength += testdatadir.path().length() + 1;
0461
0462    while (it.hasNext())
0463    {
0464       QString fileName = it.next();
0465
0466       QRegularExpression baseFileRegExp("(.*)_base\\.(.*)");
0467       QRegularExpressionMatch match = baseFileRegExp.match(fileName);
0468
0469       QString prefix = match.captured(1);
0470       QString suffix = match.captured(2);
0471
0472       QString contrib1FileName(prefix + "_contrib1." + suffix);
0473       QString contrib2FileName(prefix + "_contrib2." + suffix);
0474       QString expectedResultFileName(prefix + "_expected_result." + suffix);
0475       QString actualResultFileName(prefix + "_actual_result." + suffix);
0476
0477       if(QFile(contrib1FileName).exists() &&
0478          QFile(contrib2FileName).exists() &&
0479          QFile(expectedResultFileName).exists())
0480       {
0481          bool ok = runTest(fileName, contrib1FileName, contrib2FileName, expectedResultFileName, actualResultFileName, maxLength);
0482
0483          allOk = allOk && ok;
0484       }
0485       else
0486       {
0487          out << "Skipping " << fileName << " " << contrib1FileName << " " << contrib2FileName << " " << expectedResultFileName << " " << endl;
0488       }
0489    }
0490
0491    out << (allOk ? "All OK" : "Not all OK") << endl;
0492
0493    return allOk ? 0 : -1;
0494 }