joachim99@8: /***************************************************************************
joachim99@8:                           diff.cpp  -  description
joachim99@8:                              -------------------
joachim99@8:     begin                : Mon Mar 18 2002
joachim99@77:     copyright            : (C) 2002-2007 by Joachim Eibl
joachim99@69:     email                : joachim.eibl at gmx.de
joachim99@8:  ***************************************************************************/
joachim99@8: 
joachim99@8: /***************************************************************************
joachim99@8:  *                                                                         *
joachim99@8:  *   This program is free software; you can redistribute it and/or modify  *
joachim99@8:  *   it under the terms of the GNU General Public License as published by  *
joachim99@8:  *   the Free Software Foundation; either version 2 of the License, or     *
joachim99@8:  *   (at your option) any later version.                                   *
joachim99@8:  *                                                                         *
joachim99@8:  ***************************************************************************/
joachim99@8: 
joachim99@8: #include <stdio.h>
joachim99@77: #include <cstdlib>
joachim99@8: #include <iostream>
joachim99@8: 
joachim99@8: #include "diff.h"
joachim99@8: #include "fileaccess.h"
joachim99@58: #include "optiondialog.h"
joachim99@8: 
joachim99@8: #include <kmessagebox.h>
joachim99@8: #include <klocale.h>
joachim99@75: 
joachim99@75: #include <QFileInfo>
joachim99@75: #include <QDir>
joachim99@75: #include <QTextCodec>
joachim99@70: #include <QTextStream>
joachim99@75: #include <QProcess>
joachim99@8: 
joachim99@8: #include <map>
joachim99@8: #include <assert.h>
joachim99@8: #include <ctype.h>
joachim99@8: //using namespace std;
joachim99@8: 
joachim99@8: 
joachim99@69: int LineData::width(int tabSize) const
joachim99@8: {
joachim99@8:    int w=0;
joachim99@8:    int j=0;
joachim99@8:    for( int i=0; i<size; ++i )
joachim99@8:    {
joachim99@8:       if ( pLine[i]=='\t' )
joachim99@8:       {
joachim99@69:          for(j %= tabSize; j<tabSize; ++j)
joachim99@8:             ++w;
joachim99@8:          j=0;
joachim99@8:       }
joachim99@8:       else
joachim99@8:       {
joachim99@8:          ++w;
joachim99@8:          ++j;
joachim99@8:       }
joachim99@8:    }
joachim99@8:    return w;
joachim99@8: }
joachim99@8: 
joachim99@8: 
joachim99@8: // The bStrict flag is true during the test where a nonmatching area ends.
joachim99@8: // Then the equal()-function requires that the match has more than 2 nonwhite characters.
joachim99@8: // This is to avoid matches on trivial lines (e.g. with white space only).
joachim99@8: // This choice is good for C/C++.
joachim99@8: bool equal( const LineData& l1, const LineData& l2, bool bStrict )
joachim99@8: {
joachim99@8:    if ( l1.pLine==0 || l2.pLine==0) return false;
joachim99@8: 
joachim99@69:    if ( bStrict && g_bIgnoreTrivialMatches )//&& (l1.occurances>=5 || l2.occurances>=5) )
joachim99@8:       return false;
joachim99@8: 
joachim99@8:    // Ignore white space diff
joachim99@68:    const QChar* p1 = l1.pLine;
joachim99@68:    const QChar* p1End = p1 + l1.size;
joachim99@8: 
joachim99@68:    const QChar* p2 = l2.pLine;
joachim99@68:    const QChar* p2End = p2 + l2.size;
joachim99@8: 
joachim99@8:    if ( g_bIgnoreWhiteSpace )
joachim99@8:    {
joachim99@8:       int nonWhite = 0;
joachim99@8:       for(;;)
joachim99@8:       {
joachim99@8:          while( isWhite( *p1 ) && p1!=p1End ) ++p1;
joachim99@8:          while( isWhite( *p2 ) && p2!=p2End ) ++p2;
joachim99@8: 
joachim99@8:          if ( p1 == p1End  &&  p2 == p2End )
joachim99@8:          {
joachim99@8:             if ( bStrict && g_bIgnoreTrivialMatches )
joachim99@8:             {  // Then equality is not enough
joachim99@8:                return nonWhite>2;
joachim99@8:             }
joachim99@8:             else  // equality is enough
joachim99@8:                return true;
joachim99@8:          }
joachim99@8:          else if ( p1 == p1End || p2 == p2End )
joachim99@8:             return false;
joachim99@8: 
joachim99@8:          if( *p1 != *p2 )
joachim99@8:             return false;
joachim99@8:          ++p1;
joachim99@8:          ++p2;
joachim99@8:          ++nonWhite;
joachim99@8:       }
joachim99@8:    }
joachim99@8: 
joachim99@8:    else
joachim99@8:    {
joachim99@8:       if ( l1.size==l2.size && memcmp(p1, p2, l1.size)==0)
joachim99@8:          return true;
joachim99@8:       else
joachim99@8:          return false;
joachim99@8:    }
joachim99@8: }
joachim99@8: 
joachim99@8: 
joachim99@68: static bool isLineOrBufEnd( const QChar* p, int i, int size )
joachim99@8: {
joachim99@58:    return 
joachim99@58:       i>=size        // End of file
joachim99@58:       || p[i]=='\n'  // Normal end of line
joachim99@8: 
joachim99@58:       // No support for Mac-end of line yet, because incompatible with GNU-diff-routines.      
joachim99@58:       // || ( p[i]=='\r' && (i>=size-1 || p[i+1]!='\n') 
joachim99@58:       //                 && (i==0        || p[i-1]!='\n') )  // Special case: '\r' without '\n'
joachim99@58:       ;
joachim99@58: }
joachim99@8: 
joachim99@43: 
joachim99@58: /* Features of class SourceData:
joachim99@58: - Read a file (from the given URL) or accept data via a string.
joachim99@58: - Allocate and free buffers as necessary.
joachim99@58: - Run a preprocessor, when specified.
joachim99@58: - Run the line-matching preprocessor, when specified.
joachim99@68: - Run other preprocessing steps: Uppercase, ignore comments,
joachim99@58:                                  remove carriage return, ignore numbers.
joachim99@58: 
joachim99@58: Order of operation:
joachim99@58:  1. If data was given via a string then save it to a temp file. (see setData())
joachim99@58:  2. If the specified file is nonlocal (URL) copy it to a temp file.
joachim99@58:  3. If a preprocessor was specified, run the input file through it.
joachim99@58:  4. Read the output of the preprocessor.
joachim99@58:  5. If Uppercase was specified: Turn the read data to uppercase.
joachim99@58:  6. Write the result to a temp file.
joachim99@58:  7. If a line-matching preprocessor was specified, run the temp file through it.
joachim99@58:  8. Read the output of the line-matching preprocessor.
joachim99@58:  9. If ignore numbers was specified, strip the LMPP-output of all numbers.
joachim99@58: 10. If ignore comments was specified, strip the LMPP-output of comments.
joachim99@58: 
joachim99@58: Optimizations: Skip unneeded steps.
joachim99@58: */
joachim99@58: 
joachim99@58: SourceData::SourceData()
joachim99@68: {
joachim99@58:    m_pOptionDialog = 0;
joachim99@58:    reset();
joachim99@58: }
joachim99@58: 
joachim99@58: SourceData::~SourceData()
joachim99@58: {
joachim99@58:    reset();
joachim99@58: }
joachim99@8: 
joachim99@8: void SourceData::reset()
joachim99@8: {
joachim99@80:    m_pEncoding = 0;   
joachim99@66:    m_fileAccess = FileAccess();
joachim99@58:    m_normalData.reset();
joachim99@58:    m_lmppData.reset();
joachim99@58:    if ( !m_tempInputFileName.isEmpty() )
joachim99@58:    {
joachim99@58:       FileAccess::removeFile( m_tempInputFileName );
joachim99@58:       m_tempInputFileName = "";
joachim99@58:    }
joachim99@58: }
joachim99@58: 
joachim99@58: void SourceData::setFilename( const QString& filename )
joachim99@58: {
joachim99@58:    if (filename.isEmpty())
joachim99@58:    {
joachim99@58:       reset();
joachim99@58:    }
joachim99@58:    else
joachim99@58:    {
joachim99@58:       FileAccess fa( filename );
joachim99@58:       setFileAccess( fa );
joachim99@58:    }
joachim99@58: }
joachim99@58: 
joachim99@58: bool SourceData::isEmpty() 
joachim99@58: { 
joachim99@58:    return getFilename().isEmpty(); 
joachim99@58: }
joachim99@58: 
joachim99@58: bool SourceData::hasData() 
joachim99@58: { 
joachim99@58:    return m_normalData.m_pBuf != 0;
joachim99@58: }
joachim99@58: 
joachim99@66: bool SourceData::isValid()
joachim99@66: {
joachim99@66:    return isEmpty() || hasData();
joachim99@66: }
joachim99@66: 
joachim99@58: void SourceData::setOptionDialog( OptionDialog* pOptionDialog )
joachim99@58: {
joachim99@58:    m_pOptionDialog = pOptionDialog;
joachim99@58: }
joachim99@58: 
joachim99@58: QString SourceData::getFilename()
joachim99@58: {
joachim99@80:    return m_fileAccess.absoluteFilePath();
joachim99@58: }
joachim99@58: 
joachim99@58: QString SourceData::getAliasName()
joachim99@58: {
joachim99@58:    return m_aliasName.isEmpty() ? m_fileAccess.prettyAbsPath() : m_aliasName;
joachim99@58: }
joachim99@58: 
joachim99@58: void SourceData::setAliasName( const QString& name )
joachim99@58: {
joachim99@58:    m_aliasName = name;
joachim99@58: }
joachim99@58: 
joachim99@58: void SourceData::setFileAccess( const FileAccess& fileAccess )
joachim99@58: {
joachim99@58:    m_fileAccess = fileAccess;
joachim99@58:    m_aliasName = QString();
joachim99@58:    if ( !m_tempInputFileName.isEmpty() )
joachim99@58:    {
joachim99@58:       FileAccess::removeFile( m_tempInputFileName );
joachim99@58:       m_tempInputFileName = "";
joachim99@58:    }
joachim99@58: }
joachim99@58: 
joachim99@58: void SourceData::setData( const QString& data )
joachim99@58: {
joachim99@58:    // Create a temp file for preprocessing:
joachim99@58:    if ( m_tempInputFileName.isEmpty() )
joachim99@58:    {
joachim99@58:       m_tempInputFileName = FileAccess::tempFileName();
joachim99@58:    }
joachim99@68: 
joachim99@58:    FileAccess f( m_tempInputFileName );
joachim99@92:    QByteArray ba = QTextCodec::codecForName("UTF-8")->fromUnicode(data);
joachim99@92:    bool bSuccess = f.writeFile( ba.constData(), ba.length() );
joachim99@58:    if ( !bSuccess )
joachim99@58:    {
joachim99@58:       KMessageBox::error( m_pOptionDialog, i18n("Writing clipboard data to temp file failed.") );
joachim99@58:       return;
joachim99@58:    }
joachim99@68: 
joachim99@58:    m_aliasName = i18n("From Clipboard");
joachim99@58:    m_fileAccess = FileAccess("");  // Effect: m_fileAccess.isValid() is false
joachim99@58: }
joachim99@58: 
joachim99@68: const LineData* SourceData::getLineDataForDiff() const
joachim99@58: {
joachim99@69:    if ( m_lmppData.m_pBuf==0 )
joachim99@69:       return m_normalData.m_v.size()>0 ? &m_normalData.m_v[0] : 0;
joachim99@69:    else
joachim99@69:       return m_lmppData.m_v.size()>0   ? &m_lmppData.m_v[0]   : 0;
joachim99@58: }
joachim99@58: 
joachim99@58: const LineData* SourceData::getLineDataForDisplay() const
joachim99@58: {
joachim99@69:    return m_normalData.m_v.size()>0 ? &m_normalData.m_v[0] : 0;
joachim99@58: }
joachim99@58: 
joachim99@58: int  SourceData::getSizeLines() const
joachim99@58: {
joachim99@58:    return m_normalData.m_vSize;
joachim99@58: }
joachim99@58: 
joachim99@58: int SourceData::getSizeBytes() const
joachim99@58: {
joachim99@58:    return m_normalData.m_size;
joachim99@58: }
joachim99@58: 
joachim99@58: const char* SourceData::getBuf() const
joachim99@58: {
joachim99@58:    return m_normalData.m_pBuf;
joachim99@58: }
joachim99@58: 
joachim99@58: bool SourceData::isText()
joachim99@58: {
joachim99@58:    return m_normalData.m_bIsText;
joachim99@58: }
joachim99@58:  
joachim99@58: bool SourceData::isFromBuffer()
joachim99@58: {
joachim99@58:    return !m_fileAccess.isValid();
joachim99@58: }
joachim99@58: 
joachim99@58: 
joachim99@58: bool SourceData::isBinaryEqualWith( const SourceData& other ) const
joachim99@58: {
joachim99@77:    return m_fileAccess.exists() && other.m_fileAccess.exists() &&
joachim99@77:           getSizeBytes() == other.getSizeBytes() && 
joachim99@66:           ( getSizeBytes()==0 || memcmp( getBuf(), other.getBuf(), getSizeBytes() )==0 );
joachim99@58: }
joachim99@58: 
joachim99@58: void SourceData::FileData::reset()
joachim99@58: {
joachim99@69:    delete[] (char*)m_pBuf;
joachim99@8:    m_pBuf = 0;
joachim99@8:    m_v.clear();
joachim99@8:    m_size = 0;
joachim99@8:    m_vSize = 0;
joachim99@58:    m_bIsText = true;
joachim99@80:    m_eLineEndStyle = eLineEndStyleUndefined;
joachim99@8: }
joachim99@8: 
joachim99@58: bool SourceData::FileData::readFile( const QString& filename )
joachim99@58: {
joachim99@58:    reset();
joachim99@58:    if ( filename.isEmpty() )   { return true; }
joachim99@58: 
joachim99@58:    FileAccess fa( filename );
joachim99@58:    m_size = fa.sizeForReading();
joachim99@58:    char* pBuf;
joachim99@58:    m_pBuf = pBuf = new char[m_size+100];  // Alloc 100 byte extra: Savety hack, not nice but does no harm.
joachim99@68:                                 // Some extra bytes at the end of the buffer are needed by
joachim99@68:                                 // the diff algorithm. See also GnuDiff::diff_2_files().
joachim99@58:    bool bSuccess = fa.readFile( pBuf, m_size );
joachim99@58:    if ( !bSuccess )
joachim99@58:    {
joachim99@58:       delete pBuf;
joachim99@58:       m_pBuf = 0;
joachim99@58:       m_size = 0;
joachim99@58:    }
joachim99@58:    return bSuccess;
joachim99@58: }
joachim99@58: 
joachim99@58: bool SourceData::saveNormalDataAs( const QString& fileName )
joachim99@58: {
joachim99@58:    return m_normalData.writeFile( fileName );
joachim99@58: }
joachim99@58: 
joachim99@58: bool SourceData::FileData::writeFile( const QString& filename )
joachim99@58: {
joachim99@58:    if ( filename.isEmpty() )   { return true; }
joachim99@58: 
joachim99@58:    FileAccess fa( filename );
joachim99@58:    bool bSuccess = fa.writeFile(m_pBuf, m_size);
joachim99@58:    return bSuccess;
joachim99@58: }
joachim99@58: 
joachim99@58: void SourceData::FileData::copyBufFrom( const FileData& src )
joachim99@58: {
joachim99@58:    reset();
joachim99@68:    char* pBuf;
joachim99@58:    m_size = src.m_size;
joachim99@58:    m_pBuf = pBuf = new char[m_size+100];
joachim99@58:    memcpy( pBuf, src.m_pBuf, m_size );
joachim99@58: }
joachim99@58: 
joachim99@68: // Convert the input file from input encoding to output encoding and write it to the output file.
joachim99@68: static bool convertFileEncoding( const QString& fileNameIn, QTextCodec* pCodecIn,
joachim99@68:                                  const QString& fileNameOut, QTextCodec* pCodecOut )
joachim99@58: {
joachim99@68:    QFile in( fileNameIn );
joachim99@70:    if ( ! in.open(QIODevice::ReadOnly ) )
joachim99@68:       return false;
joachim99@68:    QTextStream inStream( &in );
joachim99@68:    inStream.setCodec( pCodecIn );
joachim99@75:    inStream.setAutoDetectUnicode( false );
joachim99@68: 
joachim99@68:    QFile out( fileNameOut );
joachim99@70:    if ( ! out.open( QIODevice::WriteOnly ) )
joachim99@68:       return false;
joachim99@68:    QTextStream outStream( &out );
joachim99@68:    outStream.setCodec( pCodecOut );
joachim99@68: 
joachim99@75:    QString data = inStream.readAll();
joachim99@68:    outStream << data;
joachim99@68: 
joachim99@68:    return true;
joachim99@68: }
joachim99@68: 
joachim99@75: static QTextCodec* detectEncoding( const char* buf, qint64 size, qint64& skipBytes )
joachim99@75: {
joachim99@75:    if (size>=2)
joachim99@75:    {
joachim99@75:       skipBytes = 2;
joachim99@75:       if (buf[0]=='\xFF' && buf[1]=='\xFE' )
joachim99@75:          return QTextCodec::codecForName( "UTF-16LE" );
joachim99@75: 
joachim99@75:       if (buf[0]=='\xFE' && buf[1]=='\xFF' )
joachim99@75:          return QTextCodec::codecForName( "UTF-16BE" );
joachim99@75:    }
joachim99@75:    if (size>=3)
joachim99@75:    {
joachim99@75:       skipBytes = 3;
joachim99@75:       if (buf[0]=='\xEF' && buf[1]=='\xBB' && buf[2]=='\xBF' )
joachim99@75:          return QTextCodec::codecForName( "UTF-8-BOM" );
joachim99@75:    }
joachim99@75:    skipBytes = 0;
joachim99@75:    return 0;
joachim99@75: }
joachim99@75: 
joachim99@75: QTextCodec* SourceData::detectEncoding( const QString& fileName, QTextCodec* pFallbackCodec )
joachim99@75: {
joachim99@75:    QFile f(fileName);
joachim99@75:    if ( f.open(QIODevice::ReadOnly) )
joachim99@75:    {
joachim99@75:       char buf[4];
joachim99@75:       qint64 size = f.read( buf, sizeof(buf) );
joachim99@75:       qint64 skipBytes = 0;
joachim99@75:       QTextCodec* pCodec = ::detectEncoding( buf, size, skipBytes );
joachim99@75:       if (pCodec)
joachim99@75:          return pCodec;
joachim99@75:    }
joachim99@75:    return pFallbackCodec;
joachim99@75: }
joachim99@75: 
joachim99@75: void SourceData::readAndPreprocess( QTextCodec* pEncoding, bool bAutoDetectUnicode )
joachim99@68: {
joachim99@68:    m_pEncoding = pEncoding;
joachim99@58:    QString fileNameIn1;
joachim99@58:    QString fileNameOut1;
joachim99@58:    QString fileNameIn2;
joachim99@58:    QString fileNameOut2;
joachim99@68: 
joachim99@58:    bool bTempFileFromClipboard = !m_fileAccess.isValid();
joachim99@68: 
joachim99@58:    // Detect the input for the preprocessing operations
joachim99@58:    if ( !bTempFileFromClipboard )
joachim99@58:    {
joachim99@58:       if ( m_fileAccess.isLocal() )
joachim99@58:       {
joachim99@80:          fileNameIn1 = m_fileAccess.absoluteFilePath();
joachim99@58:       }
joachim99@58:       else    // File is not local: create a temporary local copy:
joachim99@58:       {
joachim99@58:          if ( m_tempInputFileName.isEmpty() )  { m_tempInputFileName = FileAccess::tempFileName(); }
joachim99@68: 
joachim99@58:          m_fileAccess.copyFile(m_tempInputFileName);
joachim99@58:          fileNameIn1 = m_tempInputFileName;
joachim99@58:       }
joachim99@75:       if ( bAutoDetectUnicode )
joachim99@75:       {
joachim99@75:          m_pEncoding = detectEncoding( fileNameIn1, pEncoding );
joachim99@75:       }
joachim99@58:    }
joachim99@58:    else // The input was set via setData(), probably from clipboard.
joachim99@58:    {
joachim99@58:       fileNameIn1 = m_tempInputFileName;
joachim99@68:       m_pEncoding = QTextCodec::codecForName("UTF-8");
joachim99@58:    }
joachim99@75:    QTextCodec* pEncoding1 = m_pEncoding;
joachim99@75:    QTextCodec* pEncoding2 = m_pEncoding;
joachim99@68: 
joachim99@58:    m_normalData.reset();
joachim99@58:    m_lmppData.reset();
joachim99@68: 
joachim99@58:    FileAccess faIn(fileNameIn1);
joachim99@58:    int fileInSize = faIn.size();
joachim99@68: 
joachim99@66:    if ( faIn.exists() ) // fileInSize > 0 )
joachim99@68:    {
joachim99@58: 
joachim99@95: #if defined(_WIN32) || defined(Q_OS_OS2)
joachim99@58:       QString catCmd = "type";
joachim99@58:       fileNameIn1.replace( '/', "\\" );
joachim99@58: #else
joachim99@58:       QString catCmd = "cat";
joachim99@58: #endif
joachim99@68: 
joachim99@58:       // Run the first preprocessor
joachim99@58:       if ( m_pOptionDialog->m_PreProcessorCmd.isEmpty() )
joachim99@58:       {
joachim99@58:          // No preprocessing: Read the file directly:
joachim99@58:          m_normalData.readFile( fileNameIn1 );
joachim99@58:       }
joachim99@58:       else
joachim99@58:       {
joachim99@68:          QString fileNameInPP = fileNameIn1;
joachim99@68: 
joachim99@68:          if ( pEncoding1 != m_pOptionDialog->m_pEncodingPP )
joachim99@68:          {
joachim99@68:             // Before running the preprocessor convert to the format that the preprocessor expects.
joachim99@68:             fileNameInPP = FileAccess::tempFileName();
joachim99@68:             pEncoding1 = m_pOptionDialog->m_pEncodingPP;
joachim99@68:             convertFileEncoding( fileNameIn1, pEncoding, fileNameInPP, pEncoding1 );
joachim99@68:          }
joachim99@68: 
joachim99@58:          QString ppCmd = m_pOptionDialog->m_PreProcessorCmd;
joachim99@58:          fileNameOut1 = FileAccess::tempFileName();
joachim99@75: 
joachim99@75:          QProcess ppProcess;
joachim99@75:          ppProcess.setStandardInputFile( fileNameInPP );
joachim99@75:          ppProcess.setStandardOutputFile( fileNameOut1 );
joachim99@75:          ppProcess.start( ppCmd );
joachim99@75:          ppProcess.waitForFinished(-1);
joachim99@75:          //QString cmd = catCmd + " \"" + fileNameInPP + "\" | " + ppCmd  + " >\"" + fileNameOut1+"\"";
joachim99@75:          //::system( encodeString(cmd) );
joachim99@58:          bool bSuccess = m_normalData.readFile( fileNameOut1 );
joachim99@58:          if ( fileInSize >0 && ( !bSuccess || m_normalData.m_size==0 ) )
joachim99@58:          {
joachim99@58:             KMessageBox::error(m_pOptionDialog, 
joachim99@58:                i18n("Preprocessing possibly failed. Check this command:\n\n  %1"
joachim99@58:                   "\n\nThe preprocessing command will be disabled now."
joachim99@75:                ).arg(ppCmd) );
joachim99@58:             m_pOptionDialog->m_PreProcessorCmd = "";
joachim99@58:             m_normalData.readFile( fileNameIn1 );
joachim99@68:             pEncoding1 = m_pEncoding;
joachim99@68:          }
joachim99@68:          if (fileNameInPP != fileNameIn1)
joachim99@68:          {
joachim99@73:             FileAccess::removeTempFile( fileNameInPP );
joachim99@58:          }
joachim99@58:       }
joachim99@68: 
joachim99@58:       // LineMatching Preprocessor
joachim99@58:       if ( ! m_pOptionDialog->m_LineMatchingPreProcessorCmd.isEmpty() )
joachim99@58:       {
joachim99@66:          fileNameIn2 = fileNameOut1.isEmpty() ? fileNameIn1 : fileNameOut1;
joachim99@68:          QString fileNameInPP = fileNameIn2;
joachim99@68:          pEncoding2 = pEncoding1;
joachim99@68:          if ( pEncoding2 != m_pOptionDialog->m_pEncodingPP )
joachim99@68:          {
joachim99@75:             // Before running the preprocessor convert to the format that the preprocessor expects.
joachim99@68:             fileNameInPP = FileAccess::tempFileName();
joachim99@68:             pEncoding2 = m_pOptionDialog->m_pEncodingPP;
joachim99@68:             convertFileEncoding( fileNameIn2, pEncoding1, fileNameInPP, pEncoding2 );
joachim99@68:          }
joachim99@68: 
joachim99@58:          QString ppCmd = m_pOptionDialog->m_LineMatchingPreProcessorCmd;
joachim99@58:          fileNameOut2 = FileAccess::tempFileName();
joachim99@75:          QProcess ppProcess;
joachim99@75:          ppProcess.setStandardInputFile( fileNameInPP );
joachim99@75:          ppProcess.setStandardOutputFile( fileNameOut2 );
joachim99@75:          ppProcess.start( ppCmd );
joachim99@75:          ppProcess.waitForFinished(-1);
joachim99@75:          //QString cmd = catCmd + " \"" + fileNameInPP + "\" | " + ppCmd  + " >\"" + fileNameOut2 + "\"";
joachim99@75:          //::system( encodeString(cmd) );
joachim99@58:          bool bSuccess = m_lmppData.readFile( fileNameOut2 );
joachim99@58:          if ( FileAccess(fileNameIn2).size()>0 && ( !bSuccess || m_lmppData.m_size==0 ) )
joachim99@58:          {
joachim99@58:             KMessageBox::error(m_pOptionDialog, 
joachim99@58:                i18n("The line-matching-preprocessing possibly failed. Check this command:\n\n  %1"
joachim99@58:                     "\n\nThe line-matching-preprocessing command will be disabled now."
joachim99@75:                    ).arg(ppCmd) );
joachim99@58:             m_pOptionDialog->m_LineMatchingPreProcessorCmd = "";
joachim99@58:             m_lmppData.readFile( fileNameIn2 );
joachim99@58:          }
joachim99@73:          FileAccess::removeTempFile( fileNameOut2 );
joachim99@68:          if (fileNameInPP != fileNameIn2)
joachim99@68:          {
joachim99@73:             FileAccess::removeTempFile( fileNameInPP );
joachim99@68:          }
joachim99@58:       }
joachim99@66:       else if ( m_pOptionDialog->m_bIgnoreComments || m_pOptionDialog->m_bIgnoreCase )
joachim99@58:       {
joachim99@58:          // We need a copy of the normal data.
joachim99@58:          m_lmppData.copyBufFrom( m_normalData );
joachim99@58:       }
joachim99@58:       else
joachim99@58:       {  // We don't need any lmpp data at all.
joachim99@58:          m_lmppData.reset();
joachim99@58:       }
joachim99@68:    }
joachim99@68: 
joachim99@68:    m_normalData.preprocess( m_pOptionDialog->m_bPreserveCarriageReturn, pEncoding1 );
joachim99@68:    m_lmppData.preprocess( false, pEncoding2 );
joachim99@68: 
joachim99@58:    if ( m_lmppData.m_vSize < m_normalData.m_vSize )
joachim99@58:    {
joachim99@58:       // This probably is the fault of the LMPP-Command, but not worth reporting.
joachim99@58:       m_lmppData.m_v.resize( m_normalData.m_vSize );
joachim99@58:       for(int i=m_lmppData.m_vSize; i<m_normalData.m_vSize; ++i )
joachim99@58:       {  // Set all empty lines to point to the end of the buffer.
joachim99@68:          m_lmppData.m_v[i].pLine = m_lmppData.m_unicodeBuf.unicode()+m_lmppData.m_unicodeBuf.length();
joachim99@58:       }
joachim99@68: 
joachim99@58:       m_lmppData.m_vSize = m_normalData.m_vSize;
joachim99@58:    }
joachim99@66: 
joachim99@66:    // Internal Preprocessing: Uppercase-conversion   
joachim99@66:    if ( m_pOptionDialog->m_bIgnoreCase )
joachim99@66:    {
joachim99@66:       int i;
joachim99@68:       QChar* pBuf = const_cast<QChar*>(m_lmppData.m_unicodeBuf.unicode());
joachim99@68:       int ucSize = m_lmppData.m_unicodeBuf.length();
joachim99@68:       for(i=0; i<ucSize; ++i)
joachim99@66:       {
joachim99@75:          pBuf[i] = pBuf[i].toUpper();
joachim99@66:       }
joachim99@68:    }
joachim99@68: 
joachim99@58:    // Ignore comments
joachim99@58:    if ( m_pOptionDialog->m_bIgnoreComments )
joachim99@58:    {
joachim99@58:       m_lmppData.removeComments();
joachim99@58:       int vSize = min2(m_normalData.m_vSize, m_lmppData.m_vSize);
joachim99@58:       for(int i=0; i<vSize; ++i )
joachim99@58:       {
joachim99@58:          m_normalData.m_v[i].bContainsPureComment = m_lmppData.m_v[i].bContainsPureComment;
joachim99@58:       }
joachim99@58:    }
joachim99@68: 
joachim99@58:    // Remove unneeded temporary files. (A temp file from clipboard must not be deleted.)
joachim99@58:    if ( !bTempFileFromClipboard && !m_tempInputFileName.isEmpty() )
joachim99@58:    {
joachim99@73:       FileAccess::removeTempFile( m_tempInputFileName );
joachim99@58:       m_tempInputFileName = "";
joachim99@58:    }
joachim99@68: 
joachim99@58:    if ( !fileNameOut1.isEmpty() )
joachim99@58:    {
joachim99@73:       FileAccess::removeTempFile( fileNameOut1 );
joachim99@58:       fileNameOut1="";
joachim99@58:    }
joachim99@58: }
joachim99@58: 
joachim99@58: 
joachim99@8: /** Prepare the linedata vector for every input line.*/
joachim99@68: void SourceData::FileData::preprocess( bool bPreserveCR, QTextCodec* pEncoding )
joachim99@8: {
joachim99@68:    //m_unicodeBuf = decodeString( m_pBuf, m_size, eEncoding );
joachim99@68: 
joachim99@80:    qint64 i;
joachim99@80:    // detect line end style
joachim99@80:    m_eLineEndStyle = eLineEndStyleUndefined;
joachim99@80:    for( i=0; i<m_size; ++i )
joachim99@80:    {
joachim99@80:       if ( m_pBuf[i]=='\n' )
joachim99@80:       {
joachim99@80:          if ( i>0 && m_pBuf[i-1]=='\r' ||  // normal file
joachim99@80:               i>3 && m_pBuf[i-1]=='\0' && m_pBuf[i-2]=='\r' && m_pBuf[i-3]=='\0') // 16-bit unicode
joachim99@80:             m_eLineEndStyle = eLineEndStyleDos;
joachim99@80:          else
joachim99@80:             m_eLineEndStyle = eLineEndStyleUnix;
joachim99@80:          break;   // Only analyze first line
joachim99@80:       }
joachim99@80:    }
joachim99@75:    qint64 skipBytes = 0;
joachim99@75:    QTextCodec* pCodec = ::detectEncoding( m_pBuf, m_size, skipBytes );
joachim99@75:    if ( pCodec != pEncoding )
joachim99@75:       skipBytes=0;
joachim99@75: 
joachim99@75:    QByteArray ba = QByteArray::fromRawData( m_pBuf+skipBytes, m_size-skipBytes );
joachim99@70:    QTextStream ts( ba, QIODevice::ReadOnly );
joachim99@68:    ts.setCodec( pEncoding);
joachim99@75:    ts.setAutoDetectUnicode( false );
joachim99@75:    m_unicodeBuf = ts.readAll();
joachim99@75:    ba.clear();
joachim99@68: 
joachim99@68:    int ucSize = m_unicodeBuf.length();
joachim99@68:    const QChar* p = m_unicodeBuf.unicode();
joachim99@68: 
joachim99@8:    m_bIsText = true;
joachim99@8:    int lines = 1;
joachim99@68:    for( i=0; i<ucSize; ++i )
joachim99@8:    {
joachim99@68:       if ( isLineOrBufEnd(p,i,ucSize) )
joachim99@8:       {
joachim99@8:          ++lines;
joachim99@8:       }
joachim99@8:       if ( p[i]=='\0' )
joachim99@8:       {
joachim99@8:          m_bIsText = false;
joachim99@8:       }
joachim99@8:    }
joachim99@8: 
joachim99@8:    m_v.resize( lines+5 );
joachim99@8:    int lineIdx=0;
joachim99@8:    int lineLength=0;
joachim99@8:    bool bNonWhiteFound = false;
joachim99@8:    int whiteLength = 0;
joachim99@68:    for( i=0; i<=ucSize; ++i )
joachim99@8:    {
joachim99@68:       if ( isLineOrBufEnd( p, i, ucSize ) )
joachim99@8:       {
joachim99@8:          m_v[lineIdx].pLine = &p[ i-lineLength ];
joachim99@39:          while ( !bPreserveCR  &&  lineLength>0  &&  m_v[lineIdx].pLine[lineLength-1]=='\r'  )
joachim99@39:          {
joachim99@39:             --lineLength;
joachim99@39:          }
joachim99@43:          m_v[lineIdx].pFirstNonWhiteChar = m_v[lineIdx].pLine + min2(whiteLength,lineLength);
joachim99@8:          m_v[lineIdx].size = lineLength;
joachim99@8:          lineLength = 0;
joachim99@8:          bNonWhiteFound = false;
joachim99@8:          whiteLength = 0;
joachim99@8:          ++lineIdx;
joachim99@8:       }
joachim99@8:       else
joachim99@8:       {
joachim99@8:          ++lineLength;
joachim99@8: 
joachim99@8:          if ( ! bNonWhiteFound && isWhite( p[i] ) )
joachim99@8:             ++whiteLength;
joachim99@8:          else
joachim99@8:             bNonWhiteFound = true;
joachim99@8:       }
joachim99@8:    }
joachim99@8:    assert( lineIdx == lines );
joachim99@8: 
joachim99@8:    m_vSize = lines;
joachim99@8: }
joachim99@8: 
joachim99@51: 
joachim99@51: // Must not be entered, when within a comment.
joachim99@51: // Returns either at a newline-character p[i]=='\n' or when i==size.
joachim99@51: // A line that contains only comments is still "white".
joachim99@51: // Comments in white lines must remain, while comments in
joachim99@51: // non-white lines are overwritten with spaces.
joachim99@51: static void checkLineForComments(
joachim99@68:    QChar* p,   // pointer to start of buffer
joachim99@51:    int& i,    // index of current position (in, out)
joachim99@51:    int size,  // size of buffer
joachim99@51:    bool& bWhite,          // false if this line contains nonwhite characters (in, out)
joachim99@51:    bool& bCommentInLine,  // true if any comment is within this line (in, out)
joachim99@51:    bool& bStartsOpenComment  // true if the line ends within an comment (out)
joachim99@51:    )
joachim99@8: {
joachim99@51:    bStartsOpenComment = false;
joachim99@51:    for(; i<size; ++i )
joachim99@51:    {
joachim99@51:       // A single apostroph ' has prio over a double apostroph " (e.g. '"')
joachim99@51:       // (if not in a string)
joachim99@51:       if ( p[i]=='\'' )
joachim99@51:       {
joachim99@51:          bWhite = false;
joachim99@51:          ++i;
joachim99@58:          for( ; !isLineOrBufEnd(p,i,size) && p[i]!='\''; ++i)
joachim99@51:             ;
joachim99@51:          if (p[i]=='\'') ++i;
joachim99@51:       }
joachim99@51: 
joachim99@51:       // Strings have priority over comments: e.g. "/* Not a comment, but a string. */"
joachim99@51:       else if ( p[i]=='"' )
joachim99@51:       {
joachim99@51:          bWhite = false;
joachim99@51:          ++i;
joachim99@58:          for( ; !isLineOrBufEnd(p,i,size) && !(p[i]=='"' && p[i-1]!='\\'); ++i)
joachim99@51:             ;
joachim99@51:          if (p[i]=='"') ++i;
joachim99@51:       }
joachim99@51: 
joachim99@51:       // C++-comment
joachim99@51:       else if ( p[i]=='/' && i+1<size && p[i+1] =='/' )
joachim99@51:       {
joachim99@51:          int commentStart = i;
joachim99@51:          bCommentInLine = true;
joachim99@51:          i+=2;
joachim99@58:          for( ; !isLineOrBufEnd(p,i,size); ++i)
joachim99@51:             ;
joachim99@51:          if ( !bWhite )
joachim99@51:          {
joachim99@51:             memset( &p[commentStart], ' ', i-commentStart );
joachim99@51:          }
joachim99@51:          return;
joachim99@51:       }
joachim99@51: 
joachim99@51:       // C-comment
joachim99@51:       else if ( p[i]=='/' && i+1<size && p[i+1] =='*' )
joachim99@51:       {
joachim99@51:          int commentStart = i;
joachim99@51:          bCommentInLine = true;
joachim99@51:          i+=2;
joachim99@58:          for( ; !isLineOrBufEnd(p,i,size); ++i)
joachim99@51:          {
joachim99@51:             if ( i+1<size && p[i]=='*' && p[i+1]=='/')  // end of the comment
joachim99@51:             {
joachim99@51:                i+=2;
joachim99@51: 
joachim99@51:                // More comments in the line?
joachim99@51:                checkLineForComments( p, i, size, bWhite, bCommentInLine, bStartsOpenComment );
joachim99@51:                if ( !bWhite )
joachim99@51:                {
joachim99@51:                   memset( &p[commentStart], ' ', i-commentStart );
joachim99@51:                }
joachim99@51:                return;
joachim99@51:             }
joachim99@51:          }
joachim99@51:          bStartsOpenComment = true;
joachim99@51:          return;
joachim99@51:       }
joachim99@51: 
joachim99@51: 
joachim99@58:       if ( isLineOrBufEnd(p,i,size) )
joachim99@51:       {
joachim99@51:          return;
joachim99@51:       }
joachim99@70:       else if ( !p[i].isSpace() )
joachim99@51:       {
joachim99@51:          bWhite = false;
joachim99@51:       }
joachim99@51:    }
joachim99@51: }
joachim99@51: 
joachim99@51: // Modifies the input data, and replaces C/C++ comments with whitespace
joachim99@51: // when the line contains other data too. If the line contains only
joachim99@51: // a comment or white data, remember this in the flag bContainsPureComment.
joachim99@58: void SourceData::FileData::removeComments()
joachim99@51: {
joachim99@51:    int line=0;
joachim99@68:    QChar* p = const_cast<QChar*>(m_unicodeBuf.unicode());
joachim99@51:    bool bWithinComment=false;
joachim99@68:    int size = m_unicodeBuf.length();
joachim99@51:    for(int i=0; i<size; ++i )
joachim99@51:    {
joachim99@51: //      std::cout << "2        " << std::string(&p[i], m_v[line].size) << std::endl;
joachim99@51:       bool bWhite = true;
joachim99@51:       bool bCommentInLine = false;
joachim99@51: 
joachim99@51:       if ( bWithinComment )
joachim99@51:       {
joachim99@51:          int commentStart = i;
joachim99@51:          bCommentInLine = true;
joachim99@51: 
joachim99@58:          for( ; !isLineOrBufEnd(p,i,size); ++i)
joachim99@51:          {
joachim99@51:             if ( i+1<size && p[i]=='*' && p[i+1]=='/')  // end of the comment
joachim99@51:             {
joachim99@51:                i+=2;
joachim99@51: 
joachim99@51:                // More comments in the line?
joachim99@51:                checkLineForComments( p, i, size, bWhite, bCommentInLine, bWithinComment );
joachim99@51:                if ( !bWhite )
joachim99@51:                {
joachim99@51:                   memset( &p[commentStart], ' ', i-commentStart );
joachim99@51:                }
joachim99@51:                break;
joachim99@51:             }
joachim99@51:          }
joachim99@51:       }
joachim99@51:       else
joachim99@51:       {
joachim99@51:          checkLineForComments( p, i, size, bWhite, bCommentInLine, bWithinComment );
joachim99@51:       }
joachim99@51: 
joachim99@51:       // end of line
joachim99@58:       assert( isLineOrBufEnd(p,i,size));
joachim99@58:       m_v[line].bContainsPureComment = bCommentInLine && bWhite;
joachim99@51: /*      std::cout << line << " : " <<
joachim99@51:        ( bCommentInLine ?  "c" : " " ) <<
joachim99@51:        ( bWhite ? "w " : "  ") <<
joachim99@51:        std::string(pLD[line].pLine, pLD[line].size) << std::endl;*/
joachim99@51: 
joachim99@51:       ++line;
joachim99@51:    }
joachim99@51: }
joachim99@51: 
joachim99@8: 
joachim99@8: 
joachim99@8: // First step
joachim99@8: void calcDiff3LineListUsingAB(
joachim99@8:    const DiffList* pDiffListAB,
joachim99@8:    Diff3LineList& d3ll
joachim99@8:    )
joachim99@8: {
joachim99@8:    // First make d3ll for AB (from pDiffListAB)
joachim99@8: 
joachim99@8:    DiffList::const_iterator i=pDiffListAB->begin();
joachim99@8:    int lineA=0;
joachim99@8:    int lineB=0;
joachim99@8:    Diff d(0,0,0);
joachim99@8: 
joachim99@8:    for(;;)
joachim99@8:    {
joachim99@8:       if ( d.nofEquals==0 && d.diff1==0 && d.diff2==0 )
joachim99@8:       {
joachim99@8:          if ( i!=pDiffListAB->end() )
joachim99@8:          {
joachim99@8:             d=*i;
joachim99@8:             ++i;
joachim99@8:          }
joachim99@8:          else
joachim99@8:             break;
joachim99@8:       }
joachim99@8: 
joachim99@8:       Diff3Line d3l;
joachim99@8:       if( d.nofEquals>0 )
joachim99@8:       {
joachim99@8:          d3l.bAEqB = true;
joachim99@8:          d3l.lineA = lineA;
joachim99@8:          d3l.lineB = lineB;
joachim99@8:          --d.nofEquals;
joachim99@8:          ++lineA;
joachim99@8:          ++lineB;
joachim99@8:       }
joachim99@8:       else if ( d.diff1>0 && d.diff2>0 )
joachim99@8:       {
joachim99@8:          d3l.lineA = lineA;
joachim99@8:          d3l.lineB = lineB;
joachim99@8:          --d.diff1;
joachim99@8:          --d.diff2;
joachim99@8:          ++lineA;
joachim99@8:          ++lineB;
joachim99@8:       }
joachim99@8:       else if ( d.diff1>0 )
joachim99@8:       {
joachim99@8:          d3l.lineA = lineA;
joachim99@8:          --d.diff1;
joachim99@8:          ++lineA;
joachim99@8:       }
joachim99@8:       else if ( d.diff2>0 )
joachim99@8:       {
joachim99@8:          d3l.lineB = lineB;
joachim99@8:          --d.diff2;
joachim99@8:          ++lineB;
joachim99@8:       }
joachim99@8: 
joachim99@58:       d3ll.push_back( d3l );
joachim99@8:    }
joachim99@8: }
joachim99@8: 
joachim99@8: 
joachim99@8: // Second step
joachim99@58: void calcDiff3LineListUsingAC(
joachim99@8:    const DiffList* pDiffListAC,
joachim99@8:    Diff3LineList& d3ll
joachim99@8:    )
joachim99@8: {
joachim99@8:    ////////////////
joachim99@8:    // Now insert data from C using pDiffListAC
joachim99@8: 
joachim99@8:    DiffList::const_iterator i=pDiffListAC->begin();
joachim99@8:    Diff3LineList::iterator i3 = d3ll.begin();
joachim99@8:    int lineA=0;
joachim99@8:    int lineC=0;
joachim99@8:    Diff d(0,0,0);
joachim99@8: 
joachim99@8:    for(;;)
joachim99@8:    {
joachim99@8:       if ( d.nofEquals==0 && d.diff1==0 && d.diff2==0 )
joachim99@8:       {
joachim99@8:          if ( i!=pDiffListAC->end() )
joachim99@8:          {
joachim99@8:             d=*i;
joachim99@8:             ++i;
joachim99@8:          }
joachim99@8:          else
joachim99@8:             break;
joachim99@8:       }
joachim99@8: 
joachim99@8:       Diff3Line d3l;
joachim99@8:       if( d.nofEquals>0 )
joachim99@8:       {
joachim99@8:          // Find the corresponding lineA
joachim99@58:          while( (*i3).lineA!=lineA )
joachim99@69:             ++i3;
joachim99@8: 
joachim99@8:          (*i3).lineC = lineC;
joachim99@8:          (*i3).bAEqC = true;
joachim99@8:          (*i3).bBEqC = (*i3).bAEqB;
joachim99@58: 
joachim99@8:          --d.nofEquals;
joachim99@8:          ++lineA;
joachim99@8:          ++lineC;
joachim99@8:          ++i3;
joachim99@8:       }
joachim99@8:       else if ( d.diff1>0 && d.diff2>0 )
joachim99@8:       {
joachim99@8:          d3l.lineC = lineC;
joachim99@8:          d3ll.insert( i3, d3l );
joachim99@8:          --d.diff1;
joachim99@8:          --d.diff2;
joachim99@8:          ++lineA;
joachim99@8:          ++lineC;
joachim99@8:       }
joachim99@8:       else if ( d.diff1>0 )
joachim99@8:       {
joachim99@8:          --d.diff1;
joachim99@8:          ++lineA;
joachim99@8:       }
joachim99@8:       else if ( d.diff2>0 )
joachim99@8:       {
joachim99@8:          d3l.lineC = lineC;
joachim99@8:          d3ll.insert( i3, d3l );
joachim99@8:          --d.diff2;
joachim99@8:          ++lineC;
joachim99@8:       }
joachim99@8:    }
joachim99@8: }
joachim99@8: 
joachim99@8: // Third step
joachim99@58: void calcDiff3LineListUsingBC(
joachim99@8:    const DiffList* pDiffListBC,
joachim99@8:    Diff3LineList& d3ll
joachim99@8:    )
joachim99@8: {
joachim99@8:    ////////////////
joachim99@8:    // Now improve the position of data from C using pDiffListBC
joachim99@8:    // If a line from C equals a line from A then it is in the
joachim99@8:    // same Diff3Line already.
joachim99@8:    // If a line from C equals a line from B but not A, this
joachim99@8:    // information will be used here.
joachim99@8: 
joachim99@8:    DiffList::const_iterator i=pDiffListBC->begin();
joachim99@8:    Diff3LineList::iterator i3b = d3ll.begin();
joachim99@8:    Diff3LineList::iterator i3c = d3ll.begin();
joachim99@8:    int lineB=0;
joachim99@8:    int lineC=0;
joachim99@8:    Diff d(0,0,0);
joachim99@8: 
joachim99@8:    for(;;)
joachim99@8:    {
joachim99@8:       if ( d.nofEquals==0 && d.diff1==0 && d.diff2==0 )
joachim99@8:       {
joachim99@8:          if ( i!=pDiffListBC->end() )
joachim99@8:          {
joachim99@8:             d=*i;
joachim99@8:             ++i;
joachim99@8:          }
joachim99@8:          else
joachim99@8:             break;
joachim99@8:       }
joachim99@8: 
joachim99@8:       Diff3Line d3l;
joachim99@8:       if( d.nofEquals>0 )
joachim99@8:       {
joachim99@8:          // Find the corresponding lineB and lineC
joachim99@39:          while( i3b!=d3ll.end() && (*i3b).lineB!=lineB )
joachim99@8:             ++i3b;
joachim99@8: 
joachim99@8:          while( i3c!=d3ll.end() && (*i3c).lineC!=lineC )
joachim99@8:             ++i3c;
joachim99@8: 
joachim99@8:          assert(i3b!=d3ll.end());
joachim99@8:          assert(i3c!=d3ll.end());
joachim99@8: 
joachim99@8:          if ( i3b==i3c )
joachim99@8:          {
joachim99@8:             assert( (*i3b).lineC == lineC );
joachim99@8:             (*i3b).bBEqC = true;
joachim99@8:          }
joachim99@69:          else
joachim99@8:          {
joachim99@8:             // Is it possible to move this line up?
joachim99@8:             // Test if no other B's are used between i3c and i3b
joachim99@8: 
joachim99@8:             // First test which is before: i3c or i3b ?
joachim99@8:             Diff3LineList::iterator i3c1 = i3c;
joachim99@8:             Diff3LineList::iterator i3b1 = i3b;
joachim99@8:             while( i3c1!=i3b  &&  i3b1!=i3c )
joachim99@8:             {
joachim99@8:                assert(i3b1!=d3ll.end() || i3c1!=d3ll.end());
joachim99@8:                if( i3c1!=d3ll.end() ) ++i3c1;
joachim99@8:                if( i3b1!=d3ll.end() ) ++i3b1;
joachim99@8:             }
joachim99@8: 
joachim99@8:             if( i3c1==i3b  &&  !(*i3b).bAEqB ) // i3c before i3b
joachim99@8:             {
joachim99@8:                Diff3LineList::iterator i3 = i3c;
joachim99@8:                int nofDisturbingLines = 0;
joachim99@8:                while( i3 != i3b && i3!=d3ll.end() )
joachim99@8:                {
joachim99@58:                   if ( (*i3).lineB != -1 )
joachim99@8:                      ++nofDisturbingLines;
joachim99@8:                   ++i3;
joachim99@8:                }
joachim99@8: 
joachim99@69:                if ( nofDisturbingLines>0 )//&& nofDisturbingLines < d.nofEquals*d.nofEquals+4 )
joachim99@8:                {
joachim99@8:                   // Move the disturbing lines up, out of sight.
joachim99@8:                   i3 = i3c;
joachim99@8:                   while( i3 != i3b )
joachim99@8:                   {
joachim99@58:                      if ( (*i3).lineB != -1 )
joachim99@8:                      {
joachim99@8:                         Diff3Line d3l;
joachim99@8:                         d3l.lineB = (*i3).lineB;
joachim99@8:                         (*i3).lineB = -1;
joachim99@8:                         (*i3).bAEqB = false;
joachim99@8:                         (*i3).bBEqC = false;
joachim99@8:                         d3ll.insert( i3c, d3l );
joachim99@8:                      }
joachim99@8:                      ++i3;
joachim99@8:                   }
joachim99@8:                   nofDisturbingLines=0;
joachim99@8:                }
joachim99@8: 
joachim99@8:                if ( nofDisturbingLines == 0 )
joachim99@8:                {
joachim99@8:                   // Yes, the line from B can be moved.
joachim99@8:                   (*i3b).lineB = -1;   // This might leave an empty line: removed later.
joachim99@8:                   (*i3b).bAEqB = false;
joachim99@8:                   (*i3b).bAEqC = false;
joachim99@8:                   (*i3b).bBEqC = false;
joachim99@8:                   (*i3c).lineB = lineB;
joachim99@8:                   (*i3c).bBEqC = true;
joachim99@8:                }
joachim99@8:             }
joachim99@69:             else if( i3b1==i3c  &&  !(*i3c).bAEqC)
joachim99@8:             {
joachim99@8:                Diff3LineList::iterator i3 = i3b;
joachim99@8:                int nofDisturbingLines = 0;
joachim99@8:                while( i3 != i3c && i3!=d3ll.end() )
joachim99@8:                {
joachim99@58:                   if ( (*i3).lineC != -1 )
joachim99@8:                      ++nofDisturbingLines;
joachim99@8:                   ++i3;
joachim99@8:                }
joachim99@8: 
joachim99@69:                if ( nofDisturbingLines>0 )//&& nofDisturbingLines < d.nofEquals*d.nofEquals+4 )
joachim99@8:                {
joachim99@69:                   // Move the disturbing lines up.
joachim99@8:                   i3 = i3b;
joachim99@8:                   while( i3 != i3c )
joachim99@8:                   {
joachim99@58:                      if ( (*i3).lineC != -1 )
joachim99@8:                      {
joachim99@8:                         Diff3Line d3l;
joachim99@8:                         d3l.lineC = (*i3).lineC;
joachim99@8:                         (*i3).lineC = -1;
joachim99@8:                         (*i3).bAEqC = false;
joachim99@8:                         (*i3).bBEqC = false;
joachim99@8:                         d3ll.insert( i3b, d3l );
joachim99@8:                      }
joachim99@8:                      ++i3;
joachim99@8:                   }
joachim99@8:                   nofDisturbingLines=0;
joachim99@8:                }
joachim99@8: 
joachim99@8:                if ( nofDisturbingLines == 0 )
joachim99@8:                {
joachim99@8:                   // Yes, the line from C can be moved.
joachim99@8:                   (*i3c).lineC = -1;   // This might leave an empty line: removed later.
joachim99@8:                   (*i3c).bAEqC = false;
joachim99@8:                   (*i3c).bBEqC = false;
joachim99@8:                   (*i3b).lineC = lineC;
joachim99@8:                   (*i3b).bBEqC = true;
joachim99@8:                }
joachim99@8:             }
joachim99@8:          }
joachim99@58: 
joachim99@8:          --d.nofEquals;
joachim99@8:          ++lineB;
joachim99@8:          ++lineC;
joachim99@8:          ++i3b;
joachim99@8:          ++i3c;
joachim99@8:       }
joachim99@8:       else if ( d.diff1>0 )
joachim99@8:       {
joachim99@8:          Diff3LineList::iterator i3 = i3b;
joachim99@39:          while( (*i3).lineB!=lineB )
joachim99@8:             ++i3;
joachim99@8:          if( i3 != i3b  &&  (*i3).bAEqB==false )
joachim99@8:          {
joachim99@69:             // Take B from this line and move it up as far as possible
joachim99@8:             d3l.lineB = lineB;
joachim99@8:             d3ll.insert( i3b, d3l );
joachim99@8:             (*i3).lineB = -1;
joachim99@8:          }
joachim99@8:          else
joachim99@8:          {
joachim99@8:             i3b=i3;
joachim99@8:          }
joachim99@8:          --d.diff1;
joachim99@8:          ++lineB;
joachim99@8:          ++i3b;
joachim99@8: 
joachim99@8:          if( d.diff2>0 )
joachim99@8:          {
joachim99@8:             --d.diff2;
joachim99@8:             ++lineC;
joachim99@8:          }
joachim99@8:       }
joachim99@8:       else if ( d.diff2>0 )
joachim99@8:       {
joachim99@8:          --d.diff2;
joachim99@8:          ++lineC;
joachim99@8:       }
joachim99@8:    }
joachim99@8: /*
joachim99@8:    Diff3LineList::iterator it = d3ll.begin();
joachim99@8:    int li=0;
joachim99@8:    for( ; it!=d3ll.end(); ++it, ++li )
joachim99@8:    {
joachim99@58:       printf( "%4d %4d %4d %4d  A%c=B A%c=C B%c=C\n",
joachim99@58:          li, (*it).lineA, (*it).lineB, (*it).lineC,
joachim99@8:          (*it).bAEqB ? '=' : '!', (*it).bAEqC ? '=' : '!', (*it).bBEqC ? '=' : '!' );
joachim99@8:    }
joachim99@8:    printf("\n");*/
joachim99@8: }
joachim99@8: 
joachim99@8: #ifdef _WIN32
joachim99@8: using ::equal;
joachim99@8: #endif
joachim99@8: 
joachim99@69: // Test if the move would pass a barrier. Return true if not.
joachim99@69: static bool isValidMove( ManualDiffHelpList* pManualDiffHelpList, int line1, int line2, int winIdx1, int winIdx2 )
joachim99@69: {
joachim99@69:    if (line1>=0 && line2>=0)
joachim99@69:    {
joachim99@69:       ManualDiffHelpList::const_iterator i;
joachim99@69:       for( i = pManualDiffHelpList->begin(); i!=pManualDiffHelpList->end(); ++i )
joachim99@69:       {
joachim99@69:          const ManualDiffHelpEntry& mdhe = *i;
joachim99@69: 
joachim99@69:          // Barrier
joachim99@69:          int l1 = winIdx1 == 1 ? mdhe.lineA1 : winIdx1==2 ? mdhe.lineB1 : mdhe.lineC1 ;
joachim99@69:          int l2 = winIdx2 == 1 ? mdhe.lineA1 : winIdx2==2 ? mdhe.lineB1 : mdhe.lineC1 ;
joachim99@69: 
joachim99@69:          if ( l1>=0 && l2>=0 )
joachim99@69:          {
joachim99@69:             if ( line1>=l1 && line2<l2 || line1<l1 && line2>=l2 )
joachim99@69:                return false;
joachim99@69:             l1 = winIdx1 == 1 ? mdhe.lineA2 : winIdx1==2 ? mdhe.lineB2 : mdhe.lineC2 ;
joachim99@69:             l2 = winIdx2 == 1 ? mdhe.lineA2 : winIdx2==2 ? mdhe.lineB2 : mdhe.lineC2 ;
joachim99@69:             ++l1;
joachim99@69:             ++l2;
joachim99@69:             if ( line1>=l1 && line2<l2 || line1<l1 && line2>=l2 )
joachim99@69:                return false;
joachim99@69:          }
joachim99@69:       }
joachim99@69:    }
joachim99@69:    return true; // no barrier passed.
joachim99@69: }
joachim99@69: 
joachim99@69: void correctManualDiffAlignment( Diff3LineList& d3ll, ManualDiffHelpList* pManualDiffHelpList )
joachim99@69: {
joachim99@69:    if ( pManualDiffHelpList->empty() )
joachim99@69:       return;
joachim99@69: 
joachim99@69:    // If a line appears unaligned in comparison to the manual alignment, correct this.
joachim99@69: 
joachim99@69:    ManualDiffHelpList::iterator iMDHL;
joachim99@69:    for( iMDHL =  pManualDiffHelpList->begin(); iMDHL != pManualDiffHelpList->end(); ++iMDHL )
joachim99@69:    {
joachim99@69:       Diff3LineList::iterator i3 = d3ll.begin();
joachim99@69:       int winIdxPreferred = 0;
joachim99@69:       int missingWinIdx = 0;
joachim99@69:       int alignedSum = (iMDHL->lineA1<0?0:1) + (iMDHL->lineB1<0?0:1) + (iMDHL->lineC1<0?0:1);
joachim99@69:       if (alignedSum==2)
joachim99@69:       {
joachim99@69:          // If only A & B are aligned then let C rather be aligned with A
joachim99@69:          // If only A & C are aligned then let B rather be aligned with A
joachim99@69:          // If only B & C are aligned then let A rather be aligned with B
joachim99@69:          missingWinIdx = iMDHL->lineA1<0 ? 1 : (iMDHL->lineB1<0 ? 2 : 3 );
joachim99@69:          winIdxPreferred = missingWinIdx == 1 ? 2 : 1; 
joachim99@69:       }
joachim99@69:       else if (alignedSum<=1)
joachim99@69:       {
joachim99@69:          return;
joachim99@69:       }
joachim99@69: 
joachim99@69:       // At the first aligned line, move up the two other lines into new d3ls until the second input is aligned
joachim99@69:       // Then move up the third input until all three lines are aligned.
joachim99@69:       int wi=0;
joachim99@69:       for( ; i3!=d3ll.end(); ++i3 )
joachim99@69:       {
joachim99@69:          for ( wi=1; wi<=3; ++wi )
joachim99@69:          {
joachim99@69:             if ( i3->getLineInFile(wi) >= 0 && iMDHL->firstLine(wi) == i3->getLineInFile(wi) )
joachim99@69:                break;
joachim99@69:          }
joachim99@69:          if ( wi<=3 )
joachim99@69:             break;
joachim99@69:       }
joachim99@69: 
joachim99@69:       if (wi>=1 && wi <= 3)
joachim99@69:       {
joachim99@69:          // Found manual alignment for one source
joachim99@69:          Diff3LineList::iterator iDest = i3;
joachim99@69: 
joachim99@69:          // Move lines up until the next firstLine is found. Omit wi from move and search.
joachim99@69:          int wi2=0;
joachim99@69:          for( ; i3!=d3ll.end(); ++i3 )
joachim99@69:          {
joachim99@69:             for ( wi2=1; wi2<=3; ++wi2 )
joachim99@69:             {
joachim99@69:                if ( wi!=wi2 && i3->getLineInFile(wi2) >= 0 && iMDHL->firstLine(wi2) == i3->getLineInFile(wi2) )
joachim99@69:                   break;
joachim99@69:             }
joachim99@69:             if (wi2>3)
joachim99@69:             {  // Not yet found
joachim99@69:                // Move both others up
joachim99@69:                Diff3Line d3l;
joachim99@69:                // Move both up
joachim99@69:                if (wi==1) // Move B and C up
joachim99@69:                {
joachim99@69:                   d3l.bBEqC = i3->bBEqC;
joachim99@69:                   d3l.lineB = i3->lineB;
joachim99@69:                   d3l.lineC = i3->lineC;
joachim99@69:                   i3->lineB = -1;
joachim99@69:                   i3->lineC = -1;
joachim99@69:                }
joachim99@69:                if (wi==2) // Move A and C up
joachim99@69:                {
joachim99@69:                   d3l.bAEqC = i3->bAEqC;
joachim99@69:                   d3l.lineA = i3->lineA;
joachim99@69:                   d3l.lineC = i3->lineC;
joachim99@69:                   i3->lineA = -1;
joachim99@69:                   i3->lineC = -1;
joachim99@69:                }
joachim99@69:                if (wi==3) // Move A and B up
joachim99@69:                {
joachim99@69:                   d3l.bAEqB = i3->bAEqB;
joachim99@69:                   d3l.lineA = i3->lineA;
joachim99@69:                   d3l.lineB = i3->lineB;
joachim99@69:                   i3->lineA = -1;
joachim99@69:                   i3->lineB = -1;
joachim99@69:                }
joachim99@69:                i3->bAEqB = false;
joachim99@69:                i3->bAEqC = false;
joachim99@69:                i3->bBEqC = false;
joachim99@69:                d3ll.insert( iDest, d3l );
joachim99@69:             }
joachim99@69:             else 
joachim99@69:             {
joachim99@69:                // align the found line with the line we already have here
joachim99@69:                if ( i3 != iDest )
joachim99@69:                {
joachim99@69:                   if (wi2==1)
joachim99@69:                   {
joachim99@69:                      iDest->lineA = i3->lineA;
joachim99@69:                      i3->lineA = -1;
joachim99@69:                      i3->bAEqB = false;
joachim99@69:                      i3->bAEqC = false;                   
joachim99@69:                   }
joachim99@69:                   else if (wi2==2)
joachim99@69:                   {
joachim99@69:                      iDest->lineB = i3->lineB;
joachim99@69:                      i3->lineB = -1;
joachim99@69:                      i3->bAEqB = false;
joachim99@69:                      i3->bBEqC = false;                   
joachim99@69:                   }
joachim99@69:                   else if (wi2==3)
joachim99@69:                   {
joachim99@69:                      iDest->lineC = i3->lineC;
joachim99@69:                      i3->lineC = -1;
joachim99@69:                      i3->bBEqC = false;
joachim99@69:                      i3->bAEqC = false;                   
joachim99@69:                   }
joachim99@69:                }
joachim99@69: 
joachim99@69:                if ( missingWinIdx!=0 )
joachim99@69:                {
joachim99@69:                   for( ; i3!=d3ll.end(); ++i3 )
joachim99@69:                   {
joachim99@69:                      int wi3 = missingWinIdx;
joachim99@69:                      if ( i3->getLineInFile(wi3) >= 0 )
joachim99@69:                      {
joachim99@73:                         // not found, move the line before iDest
joachim99@73:                         Diff3Line d3l;
joachim99@73:                         if ( wi3==1 )
joachim99@69:                         {
joachim99@73:                            if (i3->bAEqB)  // Stop moving lines up if one equal is found.
joachim99@73:                               break;
joachim99@73:                            d3l.lineA = i3->lineA;
joachim99@73:                            i3->lineA = -1;
joachim99@73:                            i3->bAEqB = false;
joachim99@73:                            i3->bAEqC = false;
joachim99@69:                         }
joachim99@73:                         if ( wi3==2 )
joachim99@69:                         {
joachim99@73:                            if (i3->bAEqB)
joachim99@73:                               break;
joachim99@73:                            d3l.lineB = i3->lineB;
joachim99@73:                            i3->lineB = -1;
joachim99@73:                            i3->bAEqB = false;
joachim99@73:                            i3->bBEqC = false;
joachim99@69:                         }
joachim99@73:                         if ( wi3==3 )
joachim99@73:                         {
joachim99@73:                            if (i3->bAEqC)
joachim99@73:                               break;
joachim99@73:                            d3l.lineC = i3->lineC;
joachim99@73:                            i3->lineC = -1;
joachim99@73:                            i3->bAEqC = false;
joachim99@73:                            i3->bBEqC = false;
joachim99@73:                         }
joachim99@73:                         d3ll.insert( iDest, d3l );
joachim99@69:                      }
joachim99@69:                   } // for(), searching for wi3
joachim99@69:                }
joachim99@69:                break;
joachim99@69:             }
joachim99@69:          } // for(), searching for wi2
joachim99@69:       } // if, wi found
joachim99@69:    } // for (iMDHL)
joachim99@69: }
joachim99@69: 
joachim99@8: // Fourth step
joachim99@58: void calcDiff3LineListTrim(
joachim99@69:    Diff3LineList& d3ll, const LineData* pldA, const LineData* pldB, const LineData* pldC, ManualDiffHelpList* pManualDiffHelpList
joachim99@8:    )
joachim99@8: {
joachim99@8:    const Diff3Line d3l_empty;
joachim99@8:    d3ll.remove( d3l_empty );
joachim99@8: 
joachim99@8:    Diff3LineList::iterator i3 = d3ll.begin();
joachim99@8:    Diff3LineList::iterator i3A = d3ll.begin();
joachim99@8:    Diff3LineList::iterator i3B = d3ll.begin();
joachim99@8:    Diff3LineList::iterator i3C = d3ll.begin();
joachim99@8: 
joachim99@69:    int line=0;  // diff3line counters
joachim99@69:    int lineA=0; // 
joachim99@8:    int lineB=0;
joachim99@8:    int lineC=0;
joachim99@8: 
joachim99@69:    ManualDiffHelpList::iterator iMDHL = pManualDiffHelpList->begin();
joachim99@8:    // The iterator i3 and the variable line look ahead.
joachim99@8:    // The iterators i3A, i3B, i3C and corresponding lineA, lineB and lineC stop at empty lines, if found.
joachim99@8:    // If possible, then the texts from the look ahead will be moved back to the empty places.
joachim99@8: 
joachim99@8:    for( ; i3!=d3ll.end(); ++i3, ++line )
joachim99@8:    {
joachim99@69:       if ( iMDHL!=pManualDiffHelpList->end() )
joachim99@69:       {
joachim99@69:          if ( i3->lineA >= 0 && i3->lineA==iMDHL->lineA1 || 
joachim99@69:               i3->lineB >= 0 && i3->lineB==iMDHL->lineB1 || 
joachim99@69:               i3->lineC >= 0 && i3->lineC==iMDHL->lineC1 )
joachim99@69:          {
joachim99@69:             i3A = i3;
joachim99@69:             i3B = i3;
joachim99@69:             i3C = i3;
joachim99@69:             lineA = line;
joachim99@69:             lineB = line;
joachim99@69:             lineC = line;
joachim99@69:             ++iMDHL;
joachim99@69:          }
joachim99@69:       }
joachim99@69: 
joachim99@8:       if( line>lineA && (*i3).lineA != -1 && (*i3A).lineB!=-1 && (*i3A).bBEqC  &&
joachim99@69:           ::equal( pldA[(*i3).lineA], pldB[(*i3A).lineB], false ) &&
joachim99@69:           isValidMove( pManualDiffHelpList, (*i3).lineA, (*i3A).lineB, 1, 2 ) &&
joachim99@69:           isValidMove( pManualDiffHelpList, (*i3).lineA, (*i3A).lineC, 1, 3 ) )
joachim99@8:       {
joachim99@8:          // Empty space for A. A matches B and C in the empty line. Move it up.
joachim99@8:          (*i3A).lineA = (*i3).lineA;
joachim99@8:          (*i3A).bAEqB = true;
joachim99@8:          (*i3A).bAEqC = true;
joachim99@8:          (*i3).lineA = -1;
joachim99@8:          (*i3).bAEqB = false;
joachim99@8:          (*i3).bAEqC = false;
joachim99@8:          ++i3A;
joachim99@8:          ++lineA;
joachim99@8:       }
joachim99@8: 
joachim99@8:       if( line>lineB && (*i3).lineB != -1 && (*i3B).lineA!=-1 && (*i3B).bAEqC  &&
joachim99@69:           ::equal( pldB[(*i3).lineB], pldA[(*i3B).lineA], false ) &&
joachim99@69:           isValidMove( pManualDiffHelpList, (*i3).lineB, (*i3B).lineA, 2, 1 ) &&
joachim99@69:           isValidMove( pManualDiffHelpList, (*i3).lineB, (*i3B).lineC, 2, 3 ) )
joachim99@8:       {
joachim99@8:          // Empty space for B. B matches A and C in the empty line. Move it up.
joachim99@8:          (*i3B).lineB = (*i3).lineB;
joachim99@8:          (*i3B).bAEqB = true;
joachim99@8:          (*i3B).bBEqC = true;
joachim99@8:          (*i3).lineB = -1;
joachim99@8:          (*i3).bAEqB = false;
joachim99@8:          (*i3).bBEqC = false;
joachim99@8:          ++i3B;
joachim99@8:          ++lineB;
joachim99@8:       }
joachim99@8: 
joachim99@8:       if( line>lineC && (*i3).lineC != -1 && (*i3C).lineA!=-1 && (*i3C).bAEqB  &&
joachim99@69:           ::equal( pldC[(*i3).lineC], pldA[(*i3C).lineA], false )&&
joachim99@69:           isValidMove( pManualDiffHelpList, (*i3).lineC, (*i3C).lineA, 3, 1 ) &&
joachim99@69:           isValidMove( pManualDiffHelpList, (*i3).lineC, (*i3C).lineB, 3, 2 ) )
joachim99@8:       {
joachim99@8:          // Empty space for C. C matches A and B in the empty line. Move it up.
joachim99@8:          (*i3C).lineC = (*i3).lineC;
joachim99@8:          (*i3C).bAEqC = true;
joachim99@8:          (*i3C).bBEqC = true;
joachim99@8:          (*i3).lineC = -1;
joachim99@8:          (*i3).bAEqC = false;
joachim99@8:          (*i3).bBEqC = false;
joachim99@8:          ++i3C;
joachim99@8:          ++lineC;
joachim99@8:       }
joachim99@8: 
joachim99@69:       if( line>lineA && (*i3).lineA != -1 && !(*i3).bAEqB && !(*i3).bAEqC && 
joachim99@69:           isValidMove( pManualDiffHelpList, (*i3).lineA, (*i3A).lineB, 1, 2 ) &&
joachim99@69:           isValidMove( pManualDiffHelpList, (*i3).lineA, (*i3A).lineC, 1, 3 ) )      {
joachim99@8:          // Empty space for A. A doesn't match B or C. Move it up.
joachim99@8:          (*i3A).lineA = (*i3).lineA;
joachim99@8:          (*i3).lineA = -1;
joachim99@8:          ++i3A;
joachim99@8:          ++lineA;
joachim99@8:       }
joachim99@8: 
joachim99@69:       if( line>lineB && (*i3).lineB != -1 && !(*i3).bAEqB && !(*i3).bBEqC  &&
joachim99@69:           isValidMove( pManualDiffHelpList, (*i3).lineB, (*i3B).lineA, 2, 1 ) &&
joachim99@69:           isValidMove( pManualDiffHelpList, (*i3).lineB, (*i3B).lineC, 2, 3 ) )
joachim99@8:       {
joachim99@8:          // Empty space for B. B matches neither A nor C. Move B up.
joachim99@8:          (*i3B).lineB = (*i3).lineB;
joachim99@8:          (*i3).lineB = -1;
joachim99@8:          ++i3B;
joachim99@8:          ++lineB;
joachim99@8:       }
joachim99@8: 
joachim99@69:       if( line>lineC && (*i3).lineC != -1 && !(*i3).bAEqC && !(*i3).bBEqC &&
joachim99@69:           isValidMove( pManualDiffHelpList, (*i3).lineC, (*i3C).lineA, 3, 1 ) &&
joachim99@69:           isValidMove( pManualDiffHelpList, (*i3).lineC, (*i3C).lineB, 3, 2 ) )
joachim99@8:       {
joachim99@8:          // Empty space for C. C matches neither A nor B. Move C up.
joachim99@8:          (*i3C).lineC = (*i3).lineC;
joachim99@8:          (*i3).lineC = -1;
joachim99@8:          ++i3C;
joachim99@8:          ++lineC;
joachim99@8:       }
joachim99@8: 
joachim99@8:       if( line>lineA && line>lineB && (*i3).lineA != -1 && (*i3).bAEqB && !(*i3).bAEqC )
joachim99@8:       {
joachim99@8:          // Empty space for A and B. A matches B, but not C. Move A & B up.
joachim99@8:          Diff3LineList::iterator i = lineA > lineB ? i3A   : i3B;
joachim99@8:          int                     l = lineA > lineB ? lineA : lineB;
joachim99@8: 
joachim99@69:          if ( isValidMove( pManualDiffHelpList, i->lineC, (*i3).lineA, 3, 1 ) &&
joachim99@69:               isValidMove( pManualDiffHelpList, i->lineC, (*i3).lineB, 3, 2 ) )
joachim99@69:          {
joachim99@69:             (*i).lineA = (*i3).lineA;
joachim99@69:             (*i).lineB = (*i3).lineB;
joachim99@69:             (*i).bAEqB = true;
joachim99@58: 
joachim99@69:             (*i3).lineA = -1;
joachim99@69:             (*i3).lineB = -1;
joachim99@69:             (*i3).bAEqB = false;
joachim99@69:             i3A = i;
joachim99@69:             i3B = i;
joachim99@69:             ++i3A;
joachim99@69:             ++i3B;
joachim99@69:             lineA=l+1;
joachim99@69:             lineB=l+1;
joachim99@69:          }
joachim99@8:       }
joachim99@8:       else if( line>lineA && line>lineC && (*i3).lineA != -1 && (*i3).bAEqC && !(*i3).bAEqB )
joachim99@8:       {
joachim99@8:          // Empty space for A and C. A matches C, but not B. Move A & C up.
joachim99@8:          Diff3LineList::iterator i = lineA > lineC ? i3A   : i3C;
joachim99@8:          int                     l = lineA > lineC ? lineA : lineC;
joachim99@58: 
joachim99@69:          if ( isValidMove( pManualDiffHelpList, i->lineB, (*i3).lineA, 2, 1 ) &&
joachim99@69:               isValidMove( pManualDiffHelpList, i->lineB, (*i3).lineC, 2, 3 ) )
joachim99@69:          {
joachim99@69:             (*i).lineA = (*i3).lineA;
joachim99@69:             (*i).lineC = (*i3).lineC;
joachim99@69:             (*i).bAEqC = true;
joachim99@69: 
joachim99@69:             (*i3).lineA = -1;
joachim99@69:             (*i3).lineC = -1;
joachim99@69:             (*i3).bAEqC = false;
joachim99@69:             i3A = i;
joachim99@69:             i3C = i;
joachim99@69:             ++i3A;
joachim99@69:             ++i3C;
joachim99@69:             lineA=l+1;
joachim99@69:             lineC=l+1;
joachim99@69:          }
joachim99@8:       }
joachim99@8:       else if( line>lineB && line>lineC && (*i3).lineB != -1 && (*i3).bBEqC && !(*i3).bAEqC )
joachim99@8:       {
joachim99@8:          // Empty space for B and C. B matches C, but not A. Move B & C up.
joachim99@8:          Diff3LineList::iterator i = lineB > lineC ? i3B   : i3C;
joachim99@8:          int                     l = lineB > lineC ? lineB : lineC;
joachim99@58: 
joachim99@69:          if ( isValidMove( pManualDiffHelpList, i->lineA, (*i3).lineB, 1, 2 ) &&
joachim99@69:               isValidMove( pManualDiffHelpList, i->lineA, (*i3).lineC, 1, 3 ) )
joachim99@69:          {
joachim99@69:             (*i).lineB = (*i3).lineB;
joachim99@69:             (*i).lineC = (*i3).lineC;
joachim99@69:             (*i).bBEqC = true;
joachim99@69: 
joachim99@69:             (*i3).lineB = -1;
joachim99@69:             (*i3).lineC = -1;
joachim99@69:             (*i3).bBEqC = false;
joachim99@69:             i3B = i;
joachim99@69:             i3C = i;
joachim99@69:             ++i3B;
joachim99@69:             ++i3C;
joachim99@69:             lineB=l+1;
joachim99@69:             lineC=l+1;
joachim99@69:          }
joachim99@8:       }
joachim99@8: 
joachim99@8:       if ( (*i3).lineA != -1 )
joachim99@8:       {
joachim99@8:          lineA = line+1;
joachim99@8:          i3A = i3;
joachim99@8:          ++i3A;
joachim99@8:       }
joachim99@8:       if ( (*i3).lineB != -1 )
joachim99@8:       {
joachim99@8:          lineB = line+1;
joachim99@8:          i3B = i3;
joachim99@8:          ++i3B;
joachim99@8:       }
joachim99@8:       if ( (*i3).lineC != -1 )
joachim99@8:       {
joachim99@8:          lineC = line+1;
joachim99@8:          i3C = i3;
joachim99@8:          ++i3C;
joachim99@8:       }
joachim99@8:    }
joachim99@8: 
joachim99@8:    d3ll.remove( d3l_empty );
joachim99@8: 
joachim99@8: /*
joachim99@8: 
joachim99@8:    Diff3LineList::iterator it = d3ll.begin();
joachim99@8:    int li=0;
joachim99@8:    for( ; it!=d3ll.end(); ++it, ++li )
joachim99@8:    {
joachim99@58:       printf( "%4d %4d %4d %4d  A%c=B A%c=C B%c=C\n",
joachim99@58:          li, (*it).lineA, (*it).lineB, (*it).lineC,
joachim99@8:          (*it).bAEqB ? '=' : '!', (*it).bAEqC ? '=' : '!', (*it).bBEqC ? '=' : '!' );
joachim99@8: 
joachim99@8:    }
joachim99@8: */
joachim99@8: }
joachim99@8: 
joachim99@69: void DiffBufferInfo::init( Diff3LineList* pD3ll, const Diff3LineVector* pD3lv,
joachim99@69:    const LineData* pldA, int sizeA, const LineData* pldB, int sizeB, const LineData* pldC, int sizeC )
joachim99@69: {
joachim99@69:    m_pDiff3LineList = pD3ll;
joachim99@69:    m_pDiff3LineVector = pD3lv;
joachim99@69:    m_pLineDataA = pldA;
joachim99@69:    m_pLineDataB = pldB;
joachim99@69:    m_pLineDataC = pldC;
joachim99@69:    m_sizeA = sizeA;
joachim99@69:    m_sizeB = sizeB;
joachim99@69:    m_sizeC = sizeC;
joachim99@69:    Diff3LineList::iterator i3 = pD3ll->begin();
joachim99@69:    for( ; i3!=pD3ll->end(); ++i3 )
joachim99@69:    {
joachim99@69:       i3->m_pDiffBufferInfo = this;
joachim99@69:    }
joachim99@69: }
joachim99@69: 
joachim99@51: void calcWhiteDiff3Lines(
joachim99@58:    Diff3LineList& d3ll, const LineData* pldA, const LineData* pldB, const LineData* pldC
joachim99@8:    )
joachim99@8: {
joachim99@8:    Diff3LineList::iterator i3 = d3ll.begin();
joachim99@8: 
joachim99@8:    for( ; i3!=d3ll.end(); ++i3 )
joachim99@8:    {
joachim99@69:       i3->bWhiteLineA = ( (*i3).lineA == -1  ||  pldA==0 ||  pldA[(*i3).lineA].whiteLine() || pldA[(*i3).lineA].bContainsPureComment );
joachim99@69:       i3->bWhiteLineB = ( (*i3).lineB == -1  ||  pldB==0 ||  pldB[(*i3).lineB].whiteLine() || pldB[(*i3).lineB].bContainsPureComment );
joachim99@69:       i3->bWhiteLineC = ( (*i3).lineC == -1  ||  pldC==0 ||  pldC[(*i3).lineC].whiteLine() || pldC[(*i3).lineC].bContainsPureComment );
joachim99@8:    }
joachim99@8: }
joachim99@8: 
joachim99@8: // Just make sure that all input lines are in the output too, exactly once.
joachim99@8: void debugLineCheck( Diff3LineList& d3ll, int size, int idx )
joachim99@8: {
joachim99@8:    Diff3LineList::iterator it = d3ll.begin();
joachim99@8:    int i=0;
joachim99@8: 
joachim99@8:    for ( it = d3ll.begin(); it!= d3ll.end(); ++it )
joachim99@8:    {
joachim99@53:       int l=0;
joachim99@8:       if      (idx==1) l=(*it).lineA;
joachim99@8:       else if (idx==2) l=(*it).lineB;
joachim99@8:       else if (idx==3) l=(*it).lineC;
joachim99@8:       else assert(false);
joachim99@8: 
joachim99@8:       if ( l!=-1 )
joachim99@8:       {
joachim99@8:          if( l!=i )
joachim99@8:          {
joachim99@8:             KMessageBox::error(0, i18n(
joachim99@8:                "Data loss error:\n"
joachim99@97:                "If it is reproducible please contact the author.\n"
joachim99@51:                ), i18n("Severe Internal Error") );
joachim99@8:             assert(false);
joachim99@8:             std::cerr << "Severe Internal Error.\n";
joachim99@8:             ::exit(-1);
joachim99@8:          }
joachim99@8:          ++i;
joachim99@8:       }
joachim99@8:    }
joachim99@8: 
joachim99@8:    if( size!=i )
joachim99@8:    {
joachim99@8:       KMessageBox::error(0, i18n(
joachim99@8:          "Data loss error:\n"
joachim99@97:          "If it is reproducible please contact the author.\n"
joachim99@51:          ), i18n("Severe Internal Error") );
joachim99@8:       assert(false);
joachim99@8:       std::cerr << "Severe Internal Error.\n";
joachim99@8:       ::exit(-1);
joachim99@8:    }
joachim99@8: }
joachim99@8: 
joachim99@68: inline bool equal( QChar c1, QChar c2, bool /*bStrict*/ )
joachim99@51: {
joachim99@51:    // If bStrict then white space doesn't match
joachim99@51: 
joachim99@51:    //if ( bStrict &&  ( c1==' ' || c1=='\t' ) )
joachim99@51:    //   return false;
joachim99@51: 
joachim99@51:    return c1==c2;
joachim99@51: }
joachim99@51: 
joachim99@51: 
joachim99@51: // My own diff-invention:
joachim99@51: template <class T>
joachim99@51: void calcDiff( const T* p1, int size1, const T* p2, int size2, DiffList& diffList, int match, int maxSearchRange )
joachim99@51: {
joachim99@51:    diffList.clear();
joachim99@51: 
joachim99@51:    const T* p1start = p1;
joachim99@51:    const T* p2start = p2;
joachim99@51:    const T* p1end=p1+size1;
joachim99@51:    const T* p2end=p2+size2;
joachim99@51:    for(;;)
joachim99@51:    {
joachim99@51:       int nofEquals = 0;
joachim99@51:       while( p1!=p1end &&  p2!=p2end && equal(*p1, *p2, false) )
joachim99@51:       {
joachim99@51:          ++p1;
joachim99@51:          ++p2;
joachim99@51:          ++nofEquals;
joachim99@51:       }
joachim99@51: 
joachim99@51:       bool bBestValid=false;
joachim99@51:       int bestI1=0;
joachim99@51:       int bestI2=0;
joachim99@51:       int i1=0;
joachim99@51:       int i2=0;
joachim99@51:       for( i1=0; ; ++i1 )
joachim99@51:       {
joachim99@51:          if ( &p1[i1]==p1end || ( bBestValid && i1>= bestI1+bestI2))
joachim99@51:          {
joachim99@51:             break;
joachim99@51:          }
joachim99@51:          for(i2=0;i2<maxSearchRange;++i2)
joachim99@51:          {
joachim99@51:             if( &p2[i2]==p2end ||  ( bBestValid && i1+i2>=bestI1+bestI2) )
joachim99@51:             {
joachim99@51:                break;
joachim99@51:             }
joachim99@51:             else if(  equal( p2[i2], p1[i1], true ) &&
joachim99@51:                       ( match==1 ||  abs(i1-i2)<3  || ( &p2[i2+1]==p2end  &&  &p1[i1+1]==p1end ) ||
joachim99@51:                          ( &p2[i2+1]!=p2end  &&  &p1[i1+1]!=p1end  && equal( p2[i2+1], p1[i1+1], false ))
joachim99@51:                       )
joachim99@51:                    )
joachim99@51:             {
joachim99@51:                if ( i1+i2 < bestI1+bestI2 || bBestValid==false )
joachim99@51:                {
joachim99@51:                   bestI1 = i1;
joachim99@51:                   bestI2 = i2;
joachim99@51:                   bBestValid = true;
joachim99@51:                   break;
joachim99@51:                }
joachim99@51:             }
joachim99@51:          }
joachim99@51:       }
joachim99@51: 
joachim99@51:       // The match was found using the strict search. Go back if there are non-strict
joachim99@51:       // matches.
joachim99@51:       while( bestI1>=1 && bestI2>=1 && equal( p1[bestI1-1], p2[bestI2-1], false ) )
joachim99@51:       {
joachim99@51:          --bestI1;
joachim99@51:          --bestI2;
joachim99@51:       }
joachim99@51: 
joachim99@51: 
joachim99@51:       bool bEndReached = false;
joachim99@51:       if (bBestValid)
joachim99@51:       {
joachim99@51:          // continue somehow
joachim99@51:          Diff d(nofEquals, bestI1, bestI2);
joachim99@51:          diffList.push_back( d );
joachim99@51: 
joachim99@51:          p1 += bestI1;
joachim99@51:          p2 += bestI2;
joachim99@51:       }
joachim99@51:       else
joachim99@51:       {
joachim99@51:          // Nothing else to match.
joachim99@51:          Diff d(nofEquals, p1end-p1, p2end-p2);
joachim99@51:          diffList.push_back( d );
joachim99@51: 
joachim99@51:          bEndReached = true; //break;
joachim99@51:       }
joachim99@51: 
joachim99@51:       // Sometimes the algorithm that chooses the first match unfortunately chooses
joachim99@51:       // a match where later actually equal parts don't match anymore.
joachim99@51:       // A different match could be achieved, if we start at the end.
joachim99@51:       // Do it, if it would be a better match.
joachim99@51:       int nofUnmatched = 0;
joachim99@51:       const T* pu1 = p1-1;
joachim99@51:       const T* pu2 = p2-1;
joachim99@51:       while ( pu1>=p1start && pu2>=p2start && equal( *pu1, *pu2, false ) )
joachim99@51:       {
joachim99@51:          ++nofUnmatched;
joachim99@51:          --pu1;
joachim99@51:          --pu2;
joachim99@51:       }
joachim99@51: 
joachim99@51:       Diff d = diffList.back();
joachim99@51:       if ( nofUnmatched > 0 )
joachim99@51:       {
joachim99@51:          // We want to go backwards the nofUnmatched elements and redo
joachim99@51:          // the matching
joachim99@51:          d = diffList.back();
joachim99@51:          Diff origBack = d;
joachim99@51:          diffList.pop_back();
joachim99@51: 
joachim99@51:          while (  nofUnmatched > 0 )
joachim99@51:          {
joachim99@51:             if ( d.diff1 > 0  &&  d.diff2 > 0 )
joachim99@51:             {
joachim99@51:                --d.diff1;
joachim99@51:                --d.diff2;
joachim99@51:                --nofUnmatched;
joachim99@51:             }
joachim99@51:             else if ( d.nofEquals > 0 )
joachim99@51:             {
joachim99@51:                --d.nofEquals;
joachim99@51:                --nofUnmatched;
joachim99@51:             }
joachim99@51: 
joachim99@51:             if ( d.nofEquals==0 && (d.diff1==0 || d.diff2==0) &&  nofUnmatched>0 )
joachim99@51:             {
joachim99@51:                if ( diffList.empty() )
joachim99@51:                   break;
joachim99@51:                d.nofEquals += diffList.back().nofEquals;
joachim99@51:                d.diff1 += diffList.back().diff1;
joachim99@51:                d.diff2 += diffList.back().diff2;
joachim99@51:                diffList.pop_back();
joachim99@51:                bEndReached = false;
joachim99@51:             }
joachim99@51:          }
joachim99@51: 
joachim99@51:          if ( bEndReached )
joachim99@51:             diffList.push_back( origBack );
joachim99@51:          else
joachim99@51:          {
joachim99@51: 
joachim99@51:             p1 = pu1 + 1 + nofUnmatched;
joachim99@51:             p2 = pu2 + 1 + nofUnmatched;
joachim99@51:             diffList.push_back( d );
joachim99@51:          }
joachim99@51:       }
joachim99@51:       if ( bEndReached )
joachim99@51:          break;
joachim99@51:    }
joachim99@51: 
joachim99@51: #ifndef NDEBUG
joachim99@51:    // Verify difflist
joachim99@51:    {
joachim99@51:       int l1=0;
joachim99@51:       int l2=0;
joachim99@51:       DiffList::iterator i;
joachim99@51:       for( i = diffList.begin(); i!=diffList.end(); ++i )
joachim99@51:       {
joachim99@51:          l1+= i->nofEquals + i->diff1;
joachim99@51:          l2+= i->nofEquals + i->diff2;
joachim99@51:       }
joachim99@51: 
joachim99@51:       //if( l1!=p1-p1start || l2!=p2-p2start )
joachim99@51:       if( l1!=size1 || l2!=size2 )
joachim99@51:          assert( false );
joachim99@51:    }
joachim99@51: #endif
joachim99@51: }
joachim99@8: 
joachim99@8: void fineDiff(
joachim99@8:    Diff3LineList& diff3LineList,
joachim99@8:    int selector,
joachim99@58:    const LineData* v1,
joachim99@58:    const LineData* v2,
joachim99@8:    bool& bTextsTotalEqual
joachim99@8:    )
joachim99@8: {
joachim99@8:    // Finetuning: Diff each line with deltas
joachim99@66:    ProgressProxy pp;
joachim99@51:    int maxSearchLength=500;
joachim99@8:    Diff3LineList::iterator i;
joachim99@8:    int k1=0;
joachim99@8:    int k2=0;
joachim99@8:    bTextsTotalEqual = true;
joachim99@8:    int listSize = diff3LineList.size();
joachim99@8:    int listIdx = 0;
joachim99@8:    for( i= diff3LineList.begin(); i!= diff3LineList.end(); ++i)
joachim99@8:    {
joachim99@8:       if      (selector==1){ k1=i->lineA; k2=i->lineB; }
joachim99@8:       else if (selector==2){ k1=i->lineB; k2=i->lineC; }
joachim99@8:       else if (selector==3){ k1=i->lineC; k2=i->lineA; }
joachim99@8:       else assert(false);
joachim99@8:       if( k1==-1 && k2!=-1  ||  k1!=-1 && k2==-1 ) bTextsTotalEqual=false;
joachim99@8:       if( k1!=-1 && k2!=-1 )
joachim99@8:       {
joachim99@68:          if ( v1[k1].size != v2[k2].size || memcmp( v1[k1].pLine, v2[k2].pLine, v1[k1].size<<1)!=0 )
joachim99@8:          {
joachim99@8:             bTextsTotalEqual = false;
joachim99@8:             DiffList* pDiffList = new DiffList;
joachim99@8:             calcDiff( v1[k1].pLine, v1[k1].size, v2[k2].pLine, v2[k2].size, *pDiffList, 2, maxSearchLength );
joachim99@8: 
joachim99@8:             // Optimize the diff list.
joachim99@8:             DiffList::iterator dli;
joachim99@58:             bool bUsefulFineDiff = false;
joachim99@8:             for( dli = pDiffList->begin(); dli!=pDiffList->end(); ++dli)
joachim99@8:             {
joachim99@58:                if( dli->nofEquals >= 4 )
joachim99@58:                {
joachim99@58:                   bUsefulFineDiff = true;
joachim99@58:                   break;
joachim99@58:                }
joachim99@58:             }
joachim99@58: 
joachim99@58:             for( dli = pDiffList->begin(); dli!=pDiffList->end(); ++dli)
joachim99@58:             {
joachim99@58:                if( dli->nofEquals < 4  &&  (dli->diff1>0 || dli->diff2>0) 
joachim99@58:                   && !( bUsefulFineDiff && dli==pDiffList->begin() )
joachim99@58:                )
joachim99@8:                {
joachim99@8:                   dli->diff1 += dli->nofEquals;
joachim99@8:                   dli->diff2 += dli->nofEquals;
joachim99@8:                   dli->nofEquals = 0;
joachim99@8:                }
joachim99@8:             }
joachim99@8: 
joachim99@8:             if      (selector==1){ delete (*i).pFineAB; (*i).pFineAB = pDiffList; }
joachim99@8:             else if (selector==2){ delete (*i).pFineBC; (*i).pFineBC = pDiffList; }
joachim99@8:             else if (selector==3){ delete (*i).pFineCA; (*i).pFineCA = pDiffList; }
joachim99@8:             else assert(false);
joachim99@8:          }
joachim99@51: 
joachim99@51:          if ( (v1[k1].bContainsPureComment || v1[k1].whiteLine()) && (v2[k2].bContainsPureComment || v2[k2].whiteLine()))
joachim99@51:          {
joachim99@51:             if      (selector==1){ i->bAEqB = true; }
joachim99@51:             else if (selector==2){ i->bBEqC = true; }
joachim99@51:             else if (selector==3){ i->bAEqC = true; }
joachim99@51:             else assert(false);
joachim99@51:          }
joachim99@8:       }
joachim99@8:       ++listIdx;
joachim99@66:       pp.setCurrent(double(listIdx)/listSize);
joachim99@8:    }
joachim99@8: }
joachim99@8: 
joachim99@8: 
joachim99@8: // Convert the list to a vector of pointers
joachim99@66: void calcDiff3LineVector( Diff3LineList& d3ll, Diff3LineVector& d3lv )
joachim99@8: {
joachim99@8:    d3lv.resize( d3ll.size() );
joachim99@66:    Diff3LineList::iterator i;
joachim99@8:    int j=0;
joachim99@8:    for( i= d3ll.begin(); i!= d3ll.end(); ++i, ++j)
joachim99@8:    {
joachim99@8:       d3lv[j] = &(*i);
joachim99@8:    }
joachim99@58:    assert( j==(int)d3lv.size() );
joachim99@8: }
joachim99@8: 
joachim99@8: