joachim99@8: /***************************************************************************
joachim99@8:                           diff.cpp  -  description
joachim99@8:                              -------------------
joachim99@8:     begin                : Mon Mar 18 2002
joachim99@58:     copyright            : (C) 2002-2004 by Joachim Eibl
joachim99@8:     email                : joachim.eibl@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@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@8: #include <qfileinfo.h>
joachim99@8: #include <qdir.h>
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@58: int LineData::width() 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@8:          for(j %= g_tabSize; j<g_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@8:    if ( bStrict && g_bIgnoreTrivialMatches && (l1.occurances>=5 || l2.occurances>=5) )
joachim99@8:       return false;
joachim99@8: 
joachim99@8:    // Ignore white space diff
joachim99@8:    const char* p1 = l1.pLine;
joachim99@8:    const char* p1End = p1 + l1.size;
joachim99@8: 
joachim99@8:    const char* p2 = l2.pLine;
joachim99@8:    const char* 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@58: 
joachim99@58: 
joachim99@58: static bool isLineOrBufEnd( const char* 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@58: - 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@58: { 
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@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@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@58:    return m_fileAccess.absFilePath();
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@58:    
joachim99@58:    FileAccess f( m_tempInputFileName );
joachim99@58:    bool bSuccess = f.writeFile( encodeString(data, m_pOptionDialog), data.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@58:    
joachim99@58:    m_aliasName = i18n("From Clipboard");
joachim99@58:    m_fileAccess = FileAccess("");  // Effect: m_fileAccess.isValid() is false
joachim99@58: }
joachim99@58: 
joachim99@58: const LineData* SourceData::getLineDataForDiff() const 
joachim99@58: {
joachim99@58:    return m_lmppData.m_pBuf==0 ? &m_normalData.m_v[0] : &m_lmppData.m_v[0];
joachim99@58: }
joachim99@58: 
joachim99@58: const LineData* SourceData::getLineDataForDisplay() const
joachim99@58: {
joachim99@58:    return &m_normalData.m_v[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@58:    return getSizeBytes() == other.getSizeBytes() &&  memcmp( getBuf(), other.getBuf(), getSizeBytes() )==0;
joachim99@58: }
joachim99@58: 
joachim99@58: void SourceData::FileData::reset()
joachim99@58: {
joachim99@8:    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@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@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@58:    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@58: void SourceData::readAndPreprocess()
joachim99@58: {
joachim99@58:    QString fileNameIn1;
joachim99@58:    QString fileNameOut1;
joachim99@58:    QString fileNameIn2;
joachim99@58:    QString fileNameOut2;
joachim99@58:    
joachim99@58:    bool bTempFileFromClipboard = !m_fileAccess.isValid();
joachim99@58:       
joachim99@58:    // Detect the input for the preprocessing operations
joachim99@58:    if ( !bTempFileFromClipboard )
joachim99@58:    {
joachim99@58:       if ( m_fileAccess.isLocal() )
joachim99@58:       {
joachim99@58:          fileNameIn1 = m_fileAccess.absFilePath();
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@58:       
joachim99@58:          m_fileAccess.copyFile(m_tempInputFileName);
joachim99@58:          fileNameIn1 = m_tempInputFileName;
joachim99@58:       }
joachim99@58:    }
joachim99@58:    else // The input was set via setData(), probably from clipboard.
joachim99@58:    {
joachim99@58:       fileNameIn1 = m_tempInputFileName;
joachim99@58:    }
joachim99@58:       
joachim99@58:    m_normalData.reset();
joachim99@58:    m_lmppData.reset();
joachim99@58:    
joachim99@58:    FileAccess faIn(fileNameIn1);
joachim99@58:    int fileInSize = faIn.size();
joachim99@58:    
joachim99@58:    if ( fileInSize > 0 )
joachim99@58:    {  
joachim99@58: 
joachim99@58: #ifdef _WIN32
joachim99@58:       QString catCmd = "type";
joachim99@58:       fileNameIn1.replace( '/', "\\" );
joachim99@58: #else
joachim99@58:       QString catCmd = "cat";
joachim99@58: #endif
joachim99@58:       
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@58:          QString ppCmd = m_pOptionDialog->m_PreProcessorCmd;
joachim99@58:          fileNameOut1 = FileAccess::tempFileName();
joachim99@58:          QString cmd = catCmd + " \"" + fileNameIn1 + "\" | " + ppCmd  + " >\"" + fileNameOut1+"\"";
joachim99@58:          ::system( encodeString(cmd, m_pOptionDialog) );
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@58:                ).arg(cmd) );
joachim99@58:             m_pOptionDialog->m_PreProcessorCmd = "";
joachim99@58:             m_normalData.readFile( fileNameIn1 );
joachim99@58:          }
joachim99@58:       }
joachim99@58: 
joachim99@58:       // Internal Preprocessing: Uppercase-conversion   
joachim99@58:       bool bInternalPreprocessing = false;
joachim99@58:       if ( m_pOptionDialog->m_bUpCase )
joachim99@58:       {
joachim99@58:          int i;
joachim99@58:          char* pBuf = const_cast<char*>(m_normalData.m_pBuf);
joachim99@58:          for(i=0; i<m_normalData.m_size; ++i)
joachim99@58:          {
joachim99@58:             pBuf[i] = toupper(pBuf[i]);
joachim99@58:          }
joachim99@58:          
joachim99@58:          bInternalPreprocessing = true;
joachim99@58:       }
joachim99@58:       
joachim99@58:       // LineMatching Preprocessor
joachim99@58:       if ( ! m_pOptionDialog->m_LineMatchingPreProcessorCmd.isEmpty() )
joachim99@58:       {
joachim99@58:          if ( bInternalPreprocessing )  
joachim99@58:          {
joachim99@58:             // write data to file after internal preprocessing before running the external LMPP-cmd.
joachim99@58:             if ( !fileNameOut1.isEmpty() )
joachim99@58:             {
joachim99@58:                FileAccess::removeFile( fileNameOut1 );
joachim99@58:                fileNameOut1="";
joachim99@58:             }
joachim99@58:             
joachim99@58:             fileNameIn2 = FileAccess::tempFileName();
joachim99@58:             bool bSuccess = m_normalData.writeFile( fileNameIn2 );
joachim99@58:             if ( !bSuccess )
joachim99@58:             {
joachim99@58:                KMessageBox::error(m_pOptionDialog, i18n("Error writing temporary file: %1").arg(fileNameIn2) );
joachim99@58:             }
joachim99@58:          }
joachim99@58:          else
joachim99@58:          {
joachim99@58:             fileNameIn2 = fileNameOut1.isEmpty() ? fileNameIn1 : fileNameOut1;
joachim99@58:          }
joachim99@58:       
joachim99@58:          QString ppCmd = m_pOptionDialog->m_LineMatchingPreProcessorCmd;
joachim99@58:          fileNameOut2 = FileAccess::tempFileName();
joachim99@58:          QString cmd = catCmd + " \"" + fileNameIn2 + "\" | " + ppCmd  + " >\"" + fileNameOut2 + "\"";
joachim99@58:          ::system( encodeString(cmd, m_pOptionDialog) );
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@58:                    ).arg(cmd) );
joachim99@58:             m_pOptionDialog->m_LineMatchingPreProcessorCmd = "";
joachim99@58:             m_lmppData.readFile( fileNameIn2 );
joachim99@58:          }
joachim99@58:          FileAccess::removeFile( fileNameOut2 );
joachim99@58:          
joachim99@58:          if ( bInternalPreprocessing && !fileNameIn2.isEmpty() )
joachim99@58:          {
joachim99@58:             FileAccess::removeFile( fileNameIn2 );
joachim99@58:             fileNameIn2="";
joachim99@58:          }
joachim99@58:       }
joachim99@58:       else if ( m_pOptionDialog->m_bIgnoreComments )
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@58:    }            
joachim99@58:    
joachim99@58:    m_normalData.preprocess( m_pOptionDialog->m_bPreserveCarriageReturn );
joachim99@58:    m_lmppData.preprocess( false );
joachim99@58:    
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@58:          m_lmppData.m_v[i].pLine = m_lmppData.m_pBuf+m_lmppData.m_size;
joachim99@58:       }
joachim99@58:       
joachim99@58:       m_lmppData.m_vSize = m_normalData.m_vSize;
joachim99@58:    }
joachim99@58:    
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@58:       
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@58:       FileAccess::removeFile( m_tempInputFileName );
joachim99@58:       m_tempInputFileName = "";
joachim99@58:    }
joachim99@58:    
joachim99@58:    if ( !fileNameOut1.isEmpty() )
joachim99@58:    {
joachim99@58:       FileAccess::removeFile( fileNameOut1 );
joachim99@58:       fileNameOut1="";
joachim99@58:    }
joachim99@58: }
joachim99@58: 
joachim99@58: 
joachim99@8: /** Prepare the linedata vector for every input line.*/
joachim99@58: void SourceData::FileData::preprocess( bool bPreserveCR )
joachim99@8: {
joachim99@8:    const char* p = m_pBuf;
joachim99@8:    m_bIsText = true;
joachim99@8:    int lines = 1;
joachim99@8:    int i;
joachim99@8:    for( i=0; i<m_size; ++i )
joachim99@8:    {
joachim99@58:       if ( isLineOrBufEnd(p,i,m_size) )
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@8:    for( i=0; i<=m_size; ++i )
joachim99@8:    {
joachim99@58:       if ( isLineOrBufEnd( p, i, m_size ) )
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@51:    char* 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@51:       else if ( !isspace(p[i]) )
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@51:    char* p = (char*)m_pBuf;
joachim99@51:    bool bWithinComment=false;
joachim99@51:    int size = m_size;
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@8: 
joachim99@8:             ++i3;
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:       {
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@8:          else //if ( !(*i3b).bAEqB )
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: 
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@8:                {
joachim99@58:                   if ( (*i3).lineB != -1 )
joachim99@8:                      ++nofDisturbingLines;
joachim99@8:                   ++i3;
joachim99@8:                }
joachim99@8: 
joachim99@8:                if ( nofDisturbingLines>0 && nofDisturbingLines < d.nofEquals )
joachim99@8:                {
joachim99@8:                   // Move the disturbing lines up, out of sight.
joachim99@8:                   i3 = i3c;
joachim99@8: 
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: 
joachim99@8: 
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:                   //(*i3b).lineC = -1;
joachim99@8:                   (*i3c).lineB = lineB;
joachim99@8: 
joachim99@8:                   (*i3c).bBEqC = true;
joachim99@8: 
joachim99@8:                }
joachim99@8: 
joachim99@8:             }
joachim99@8: 
joachim99@8:             else if( i3b1==i3c  &&  !(*i3b).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@8:                if ( nofDisturbingLines>0 && nofDisturbingLines < d.nofEquals )
joachim99@8:                {
joachim99@8:                   // Move the disturbing lines up, out of sight.
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:                   }
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:                   //(*i3c).lineB = -1;
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@8:             // Take 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: 
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@8: // Fourth step
joachim99@58: void calcDiff3LineListTrim(
joachim99@58:    Diff3LineList& d3ll, const LineData* pldA, const LineData* pldB, const LineData* pldC
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@8:    int line=0;
joachim99@8:    int lineA=0;
joachim99@8:    int lineB=0;
joachim99@8:    int lineC=0;
joachim99@8: 
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@8:       if( line>lineA && (*i3).lineA != -1 && (*i3A).lineB!=-1 && (*i3A).bBEqC  &&
joachim99@8:           ::equal( pldA[(*i3).lineA], pldB[(*i3A).lineB], false ))
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@8:           ::equal( pldB[(*i3).lineB], pldA[(*i3B).lineA], false ))
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@8:           ::equal( pldC[(*i3).lineC], pldA[(*i3C).lineA], false ))
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@8:       if( line>lineA && (*i3).lineA != -1 && !(*i3).bAEqB && !(*i3).bAEqC )
joachim99@8:       {
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@8:       if( line>lineB && (*i3).lineB != -1 && !(*i3).bAEqB && !(*i3).bBEqC )
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@8:       if( line>lineC && (*i3).lineC != -1 && !(*i3).bAEqC && !(*i3).bBEqC )
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@8:          (*i).lineA = (*i3).lineA;
joachim99@8:          (*i).lineB = (*i3).lineB;
joachim99@8:          (*i).bAEqB = true;
joachim99@58: 
joachim99@8:          (*i3).lineA = -1;
joachim99@8:          (*i3).lineB = -1;
joachim99@8:          (*i3).bAEqB = false;
joachim99@8:          i3A = i;
joachim99@8:          i3B = i;
joachim99@8:          ++i3A;
joachim99@8:          ++i3B;
joachim99@8:          lineA=l+1;
joachim99@8:          lineB=l+1;
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@8:          (*i).lineA = (*i3).lineA;
joachim99@8:          (*i).lineC = (*i3).lineC;
joachim99@8:          (*i).bAEqC = true;
joachim99@58: 
joachim99@8:          (*i3).lineA = -1;
joachim99@8:          (*i3).lineC = -1;
joachim99@8:          (*i3).bAEqC = false;
joachim99@8:          i3A = i;
joachim99@8:          i3C = i;
joachim99@8:          ++i3A;
joachim99@8:          ++i3C;
joachim99@8:          lineA=l+1;
joachim99@8:          lineC=l+1;
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@8:          (*i).lineB = (*i3).lineB;
joachim99@8:          (*i).lineC = (*i3).lineC;
joachim99@8:          (*i).bBEqC = true;
joachim99@58: 
joachim99@8:          (*i3).lineB = -1;
joachim99@8:          (*i3).lineC = -1;
joachim99@8:          (*i3).bBEqC = false;
joachim99@8:          i3B = i;
joachim99@8:          i3C = i;
joachim99@8:          ++i3B;
joachim99@8:          ++i3C;
joachim99@8:          lineB=l+1;
joachim99@8:          lineC=l+1;
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@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@51:       i3->bWhiteLineA = ( (*i3).lineA == -1  ||  pldA[(*i3).lineA].whiteLine() || pldA[(*i3).lineA].bContainsPureComment );
joachim99@51:       i3->bWhiteLineB = ( (*i3).lineB == -1  ||  pldB[(*i3).lineB].whiteLine() || pldB[(*i3).lineB].bContainsPureComment );
joachim99@51:       i3->bWhiteLineC = ( (*i3).lineC == -1  ||  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@8:                "If it is reproducable 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@8:          "If it is reproducable 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@51: inline bool equal( char c1, char 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@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@8:          if ( v1[k1].size != v2[k2].size || memcmp( v1[k1].pLine, v2[k2].pLine, v1[k1].size)!=0 )
joachim99@8:          {
joachim99@8:             bTextsTotalEqual = false;
joachim99@8:             DiffList* pDiffList = new DiffList;
joachim99@8: //            std::cout << std::string( v1[k1].pLine, v1[k1].size ) << "\n";
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@8:       g_pProgressDialog->setSubCurrent(double(listIdx)/listSize);
joachim99@8:    }
joachim99@8: }
joachim99@8: 
joachim99@8: 
joachim99@8: // Convert the list to a vector of pointers
joachim99@8: void calcDiff3LineVector( const Diff3LineList& d3ll, Diff3LineVector& d3lv )
joachim99@8: {
joachim99@8:    d3lv.resize( d3ll.size() );
joachim99@8:    Diff3LineList::const_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: 
joachim99@8: #include "diff.moc"