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

#ifndef DIFF_H
#define DIFF_H

#include "common.h"
#include "fileaccess.h"
17
#include "options.h"
18
#include "gnudiff_diff.h"
19
#include "SourceData.h"
20 21 22
#include "Logging.h"

#include <QList>
Joachim Eibl's avatar
0.9.93  
Joachim Eibl committed
23

Michael Reeves's avatar
Michael Reeves committed
24 25 26 27 28 29 30 31 32 33 34 35
//enum must be sequential with no gaps to allow loop interiation of values
enum e_SrcSelector
{
   Min = -1,
   Invalid=-1,
   None=0,
   A = 1,
   B = 2,
   C = 3,
   Max=C
};

36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55
enum e_MergeDetails
{
   eDefault,
   eNoChange,
   eBChanged,
   eCChanged,
   eBCChanged,         // conflict
   eBCChangedAndEqual, // possible conflict
   eBDeleted,
   eCDeleted,
   eBCDeleted,         // possible conflict

   eBChanged_CDeleted, // conflict
   eCChanged_BDeleted, // conflict
   eBAdded,
   eCAdded,
   eBCAdded,           // conflict
   eBCAddedAndEqual    // possible conflict
};

Joachim Eibl's avatar
Joachim Eibl committed
56 57
// Each range with matching elements is followed by a range with differences on either side.
// Then again range of matching elements should follow.
Michael Reeves's avatar
Michael Reeves committed
58
class Diff
Joachim Eibl's avatar
Joachim Eibl committed
59
{
Michael Reeves's avatar
Michael Reeves committed
60
  public:
61
    LineCount nofEquals;
Michael Reeves's avatar
Michael Reeves committed
62 63 64 65

    qint64 diff1;
    qint64 diff2;

66
    Diff(LineCount eq, qint64 d1, qint64 d2)
Michael Reeves's avatar
Michael Reeves committed
67 68 69 70 71
    {
        nofEquals = eq;
        diff1 = d1;
        diff2 = d2;
    }
Joachim Eibl's avatar
Joachim Eibl committed
72 73 74 75
};

typedef std::list<Diff> DiffList;

Michael Reeves's avatar
Michael Reeves committed
76
class LineData
Joachim Eibl's avatar
Joachim Eibl committed
77
{
78
  private:
79 80 81 82
    const QChar* pLine = nullptr;
    const QChar* pFirstNonWhiteChar = nullptr;
    int mSize = 0;
    bool bContainsPureComment = false;
83 84

  public:
85 86 87 88 89 90 91 92
    inline int size() const { return mSize; }
    inline void setSize(const int newSize) { mSize = newSize; }

    inline void setFirstNonWhiteChar(const QChar* firstNonWhiteChar) { pFirstNonWhiteChar = firstNonWhiteChar;}
    inline const QChar* getFirstNonWhiteChar() const { return pFirstNonWhiteChar; }

    inline const QChar* getLine() const { return pLine; }
    inline void setLine(const QChar* line) { pLine = line;}
Michael Reeves's avatar
Michael Reeves committed
93 94
    int width(int tabSize) const; // Calcs width considering tabs.
    //int occurrences;
95
    bool whiteLine() const { return pFirstNonWhiteChar - pLine == mSize; }
96 97 98

    bool isPureComment() const { return bContainsPureComment; }
    void setPureComment(const bool bPureComment) { bContainsPureComment = bPureComment; }
Michael Reeves's avatar
Cleanup  
Michael Reeves committed
99 100

    static bool equal(const LineData& l1, const LineData& l2, bool bStrict);
Joachim Eibl's avatar
Joachim Eibl committed
101 102 103 104 105
};

class Diff3LineList;
class Diff3LineVector;

Michael Reeves's avatar
Michael Reeves committed
106
class DiffBufferInfo
Joachim Eibl's avatar
Joachim Eibl committed
107
{
Michael Reeves's avatar
Michael Reeves committed
108
  public:
Michael Reeves's avatar
Michael Reeves committed
109 110 111
    const QVector<LineData>* m_pLineDataA;
    const QVector<LineData>* m_pLineDataB;
    const QVector<LineData>* m_pLineDataC;
112 113 114
    LineCount m_sizeA;
    LineCount m_sizeB;
    LineCount m_sizeC;
Michael Reeves's avatar
Michael Reeves committed
115 116 117
    const Diff3LineList* m_pDiff3LineList;
    const Diff3LineVector* m_pDiff3LineVector;
    void init(Diff3LineList* d3ll, const Diff3LineVector* d3lv,
Michael Reeves's avatar
Michael Reeves committed
118
              const QVector<LineData>* pldA, LineCount sizeA, const QVector<LineData>* pldB, LineCount sizeB, const QVector<LineData>* pldC, LineCount sizeC);
Joachim Eibl's avatar
Joachim Eibl committed
119 120
};

Michael Reeves's avatar
Michael Reeves committed
121
class Diff3Line
Joachim Eibl's avatar
Joachim Eibl committed
122
{
123
  private:
Michael Reeves's avatar
Michael Reeves committed
124 125 126
    LineRef lineA;
    LineRef lineB;
    LineRef lineC;
127
  public:
Michael Reeves's avatar
Michael Reeves committed
128

Michael Reeves's avatar
Michael Reeves committed
129 130 131
    bool bAEqC = false; // These are true if equal or only white-space changes exist.
    bool bBEqC = false;
    bool bAEqB = false;
Michael Reeves's avatar
Michael Reeves committed
132

Michael Reeves's avatar
Michael Reeves committed
133 134 135
    bool bWhiteLineA  = false;
    bool bWhiteLineB  = false;
    bool bWhiteLineC  = false;
Michael Reeves's avatar
Michael Reeves committed
136

Michael Reeves's avatar
Michael Reeves committed
137 138 139
    DiffList* pFineAB = nullptr; // These are 0 only if completely equal or if either source doesn't exist.
    DiffList* pFineBC = nullptr;
    DiffList* pFineCA = nullptr;
Michael Reeves's avatar
Michael Reeves committed
140

Michael Reeves's avatar
Michael Reeves committed
141 142
    int linesNeededForDisplay = 1;    // Due to wordwrap
    int sumLinesNeededForDisplay = 0; // For fast conversion to m_diff3WrapLineVector
Michael Reeves's avatar
Michael Reeves committed
143

Michael Reeves's avatar
Michael Reeves committed
144
    DiffBufferInfo* m_pDiffBufferInfo = nullptr; // For convenience
Michael Reeves's avatar
Michael Reeves committed
145 146 147 148 149 150 151 152 153 154 155

    ~Diff3Line()
    {
        if(pFineAB != nullptr) delete pFineAB;
        if(pFineBC != nullptr) delete pFineBC;
        if(pFineCA != nullptr) delete pFineCA;
        pFineAB = nullptr;
        pFineBC = nullptr;
        pFineCA = nullptr;
    }

156 157 158 159
    LineRef getLineA() const { return lineA; }
    LineRef getLineB() const { return lineB; }
    LineRef getLineC() const { return lineC; }

Michael Reeves's avatar
Michael Reeves committed
160 161 162 163 164 165 166
    inline void setLineA(const LineRef& line) { lineA = line; }
    inline void setLineB(const LineRef& line) { lineB = line; }
    inline void setLineC(const LineRef& line) { lineC = line; }

    inline bool isEqualAB() const { return bAEqB; }
    inline bool isEqualAC() const { return bAEqC; }
    inline bool isEqualBC() const { return bBEqC; }
167

Michael Reeves's avatar
Michael Reeves committed
168 169 170 171 172
    bool operator==(const Diff3Line& d3l) const
    {
        return lineA == d3l.lineA && lineB == d3l.lineB && lineC == d3l.lineC && bAEqB == d3l.bAEqB && bAEqC == d3l.bAEqC && bBEqC == d3l.bBEqC;
    }

Michael Reeves's avatar
Michael Reeves committed
173
    const LineData* getLineData(e_SrcSelector src) const
Michael Reeves's avatar
Michael Reeves committed
174 175
    {
        Q_ASSERT(m_pDiffBufferInfo != nullptr);
Michael Reeves's avatar
Michael Reeves committed
176 177 178
        if(src == A && lineA >= 0) return &(*m_pDiffBufferInfo->m_pLineDataA)[lineA];
        if(src == B && lineB >= 0) return &(*m_pDiffBufferInfo->m_pLineDataB)[lineB];
        if(src == C && lineC >= 0) return &(*m_pDiffBufferInfo->m_pLineDataC)[lineC];
Michael Reeves's avatar
Michael Reeves committed
179 180
        return nullptr;
    }
Michael Reeves's avatar
Michael Reeves committed
181
    QString getString(const e_SrcSelector src) const
Michael Reeves's avatar
Michael Reeves committed
182 183 184
    {
        const LineData* pld = getLineData(src);
        if(pld)
185
            return QString(pld->getLine(), pld->size());
Michael Reeves's avatar
Michael Reeves committed
186 187 188
        else
            return QString();
    }
Michael Reeves's avatar
Michael Reeves committed
189
    LineRef getLineInFile(e_SrcSelector src) const
Michael Reeves's avatar
Michael Reeves committed
190
    {
Michael Reeves's avatar
Michael Reeves committed
191 192 193
        if(src == A) return lineA;
        if(src == B) return lineB;
        if(src == C) return lineC;
Michael Reeves's avatar
Michael Reeves committed
194 195
        return -1;
    }
196

Michael Reeves's avatar
Michael Reeves committed
197
    bool fineDiff(bool bTextsTotalEqual, const e_SrcSelector selector, const QVector<LineData>* v1, const QVector<LineData>* v2);
Michael Reeves's avatar
Michael Reeves committed
198
    void mergeOneLine(e_MergeDetails& mergeDetails, bool& bConflict, bool& bLineRemoved, e_SrcSelector& src, bool bTwoInputs) const;
199

Michael Reeves's avatar
Michael Reeves committed
200
    void getLineInfo(const e_SrcSelector winIdx, const bool isTriple, int& lineIdx,
Michael Reeves's avatar
Michael Reeves committed
201 202 203
        DiffList*& pFineDiff1, DiffList*& pFineDiff2, // return values
        int& changed, int& changed2) const;

204
  private:
Michael Reeves's avatar
Michael Reeves committed
205
    void setFineDiff(const e_SrcSelector selector, DiffList* pDiffList)
206
    {
Michael Reeves's avatar
Michael Reeves committed
207 208
        Q_ASSERT(selector == A || selector == B || selector == C);
        if(selector == A)
209 210 211 212 213
        {
            if(pFineAB != nullptr)
                delete pFineAB;
            pFineAB = pDiffList;
        }
Michael Reeves's avatar
Michael Reeves committed
214
        else if(selector == B)
215 216 217 218 219
        {
            if(pFineBC != nullptr)
                delete pFineBC;
            pFineBC = pDiffList;
        }
Michael Reeves's avatar
Michael Reeves committed
220
        else if(selector == C)
221 222 223 224 225 226
        {
            if(pFineCA)
                delete pFineCA;
            pFineCA = pDiffList;
        }
    }
Joachim Eibl's avatar
Joachim Eibl committed
227 228
};

Michael Reeves's avatar
Michael Reeves committed
229
class Diff3LineList : public std::list<Diff3Line>
Joachim Eibl's avatar
Joachim Eibl committed
230
{
231
  public:
Michael Reeves's avatar
Michael Reeves committed
232
    bool fineDiff(const e_SrcSelector selector, const QVector<LineData>* v1, const QVector<LineData>* v2);
233
    void calcDiff3LineVector(Diff3LineVector& d3lv);
Michael Reeves's avatar
Michael Reeves committed
234
    void calcWhiteDiff3Lines(const QVector<LineData>* pldA, const QVector<LineData>* pldB, const QVector<LineData>* pldC);
Michael Reeves's avatar
Michael Reeves committed
235
    //TODO: Add safety guards to prevent list from getting too large. Same problem as with QLinkedList.
236 237
    int size() const
    {
238 239
        if(std::list<Diff3Line>::size() > std::numeric_limits<int>::max())
        {
240
            qCDebug(kdiffMain) << "Diff3Line: List too large. size=" << std::list<Diff3Line>::size();
241
            Q_ASSERT(false); //Unsupported size
242 243 244
            return 0;
        }
        return (int)std::list<Diff3Line>::size();
245 246 247
    } //safe for small files same limit as exited with QLinkedList. This should ultimatly be removed.

    void debugLineCheck(const LineCount size, const e_SrcSelector srcSelector) const;
Joachim Eibl's avatar
Joachim Eibl committed
248
};
249

250
class Diff3LineVector : public QVector<Diff3Line*>
Joachim Eibl's avatar
Joachim Eibl committed
251 252
{
};
Joachim Eibl's avatar
0.9.86  
Joachim Eibl committed
253 254 255

class Diff3WrapLine
{
Michael Reeves's avatar
Michael Reeves committed
256 257 258 259 260
  public:
    Diff3Line* pD3L;
    int diff3LineIndex;
    int wrapLineOffset;
    int wrapLineLength;
Joachim Eibl's avatar
0.9.86  
Joachim Eibl committed
261 262
};

263
typedef QVector<Diff3WrapLine> Diff3WrapLineVector;
Joachim Eibl's avatar
0.9.86  
Joachim Eibl committed
264

Joachim Eibl's avatar
Joachim Eibl committed
265 266
class TotalDiffStatus
{
Michael Reeves's avatar
Michael Reeves committed
267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304
  public:
    inline void reset()
    {
        bBinaryAEqC = false;
        bBinaryBEqC = false;
        bBinaryAEqB = false;
        bTextAEqC = false;
        bTextBEqC = false;
        bTextAEqB = false;
        nofUnsolvedConflicts = 0;
        nofSolvedConflicts = 0;
        nofWhitespaceConflicts = 0;
    }

    inline int getUnsolvedConflicts() const { return nofUnsolvedConflicts; }
    inline void setUnsolvedConflicts(const int unsolved) { nofUnsolvedConflicts = unsolved; }

    inline int getSolvedConflicts() const { return nofSolvedConflicts; }
    inline void setSolvedConflicts(const int solved) { nofSolvedConflicts = solved; }

    inline int getWhitespaceConflicts() const { return nofWhitespaceConflicts; }
    inline void setWhitespaceConflicts(const int wintespace) { nofWhitespaceConflicts = wintespace; }

    inline int getNonWhitespaceConflicts() { return getUnsolvedConflicts() + getSolvedConflicts() - getWhitespaceConflicts(); }

    bool isBinaryEqualAC() const { return bBinaryAEqC; }
    bool isBinaryEqualBC() const { return bBinaryBEqC; }
    bool isBinaryEqualAB() const { return bBinaryAEqB; }

    bool bBinaryAEqC = false;
    bool bBinaryBEqC = false;
    bool bBinaryAEqB = false;

    bool bTextAEqC = false;
    bool bTextBEqC = false;
    bool bTextAEqB = false;

  private:
Michael Reeves's avatar
Michael Reeves committed
305 306 307
    int nofUnsolvedConflicts = 0;
    int nofSolvedConflicts = 0;
    int nofWhitespaceConflicts = 0;
Joachim Eibl's avatar
Joachim Eibl committed
308 309
};

310
class ManualDiffHelpList; // A list of corresponding ranges
Joachim Eibl's avatar
Joachim Eibl committed
311 312 313
// Three corresponding ranges. (Minimum size of a valid range is one line.)
class ManualDiffHelpEntry
{
314
  private:
Michael Reeves's avatar
Michael Reeves committed
315 316 317 318 319 320 321
    LineRef lineA1;
    LineRef lineA2;
    LineRef lineB1;
    LineRef lineB2;
    LineRef lineC1;
    LineRef lineC2;

Michael Reeves's avatar
Michael Reeves committed
322
  public:
Michael Reeves's avatar
Michael Reeves committed
323
    LineRef& firstLine(e_SrcSelector winIdx)
Michael Reeves's avatar
Michael Reeves committed
324
    {
Michael Reeves's avatar
Michael Reeves committed
325
        return winIdx == A ? lineA1 : (winIdx == B ? lineB1 : lineC1);
Michael Reeves's avatar
Michael Reeves committed
326
    }
Michael Reeves's avatar
Michael Reeves committed
327
    LineRef& lastLine(e_SrcSelector winIdx)
Michael Reeves's avatar
Michael Reeves committed
328
    {
Michael Reeves's avatar
Michael Reeves committed
329
        return winIdx == A ? lineA2 : (winIdx == B ? lineB2 : lineC2);
Michael Reeves's avatar
Michael Reeves committed
330
    }
Michael Reeves's avatar
Michael Reeves committed
331
    bool isLineInRange(LineRef line, e_SrcSelector winIdx)
Michael Reeves's avatar
Michael Reeves committed
332 333 334 335 336 337 338 339
    {
        return line >= 0 && line >= firstLine(winIdx) && line <= lastLine(winIdx);
    }
    bool operator==(const ManualDiffHelpEntry& r) const
    {
        return lineA1 == r.lineA1 && lineB1 == r.lineB1 && lineC1 == r.lineC1 &&
               lineA2 == r.lineA2 && lineB2 == r.lineB2 && lineC2 == r.lineC2;
    }
340 341

    int calcManualDiffFirstDiff3LineIdx(const Diff3LineVector& d3lv);
342

Michael Reeves's avatar
Michael Reeves committed
343 344
    void getRangeForUI(const e_SrcSelector winIdx, int *rangeLine1, int *rangeLine2) const {
        if(winIdx == A) {
345 346 347
            *rangeLine1 = lineA1;
            *rangeLine2 = lineA2;
        }
Michael Reeves's avatar
Michael Reeves committed
348
        if(winIdx == B) {
349 350 351
            *rangeLine1 = lineB1;
            *rangeLine2 = lineB2;
        }
Michael Reeves's avatar
Michael Reeves committed
352
        if(winIdx == C) {
353 354 355 356 357
            *rangeLine1 = lineC1;
            *rangeLine2 = lineC2;
        }
    }

Michael Reeves's avatar
Michael Reeves committed
358 359 360
    inline int getLine1(const e_SrcSelector winIdx) const { return winIdx == A ? lineA1 : winIdx == B ? lineB1 : lineC1;}
    inline int getLine2(const e_SrcSelector winIdx) const { return winIdx == A ? lineA2 : winIdx == B ? lineB2 : lineC2;}
    bool isValidMove(int line1, int line2, e_SrcSelector winIdx1, e_SrcSelector winIdx2) const;
Joachim Eibl's avatar
Joachim Eibl committed
361 362 363
};

// A list of corresponding ranges
364 365 366
class ManualDiffHelpList: public std::list<ManualDiffHelpEntry>
{
    public:
Michael Reeves's avatar
Michael Reeves committed
367 368
        bool isValidMove(int line1, int line2, e_SrcSelector winIdx1, e_SrcSelector winIdx2) const;
        void insertEntry(e_SrcSelector winIdx, LineRef firstLine, LineRef lastLine);
Michael Reeves's avatar
Michael Reeves committed
369

Michael Reeves's avatar
Michael Reeves committed
370
        bool runDiff(const QVector<LineData>* p1, LineRef size1, const QVector<LineData>* p2, LineRef size2, DiffList& diffList,
Michael Reeves's avatar
Michael Reeves committed
371
                     e_SrcSelector winIdx1, e_SrcSelector winIdx2,
Michael Reeves's avatar
Michael Reeves committed
372
                     Options* pOptions);
373
};
374

Joachim Eibl's avatar
0.9.80  
Joachim Eibl committed
375
void calcDiff3LineListUsingAB(
Michael Reeves's avatar
Michael Reeves committed
376 377
    const DiffList* pDiffListAB,
    Diff3LineList& d3ll);
Joachim Eibl's avatar
Joachim Eibl committed
378 379

void calcDiff3LineListUsingAC(
Michael Reeves's avatar
Michael Reeves committed
380 381
    const DiffList* pDiffListAC,
    Diff3LineList& d3ll);
Joachim Eibl's avatar
Joachim Eibl committed
382

Joachim Eibl's avatar
Joachim Eibl committed
383
void calcDiff3LineListUsingBC(
Michael Reeves's avatar
Michael Reeves committed
384 385
    const DiffList* pDiffListBC,
    Diff3LineList& d3ll);
Joachim Eibl's avatar
Joachim Eibl committed
386

Michael Reeves's avatar
Michael Reeves committed
387
void correctManualDiffAlignment(Diff3LineList& d3ll, ManualDiffHelpList* pManualDiffHelpList);
Joachim Eibl's avatar
Joachim Eibl committed
388

Michael Reeves's avatar
Michael Reeves committed
389
void calcDiff3LineListTrim(Diff3LineList& d3ll, const QVector<LineData>* pldA, const QVector<LineData>* pldB, const QVector<LineData>* pldC, ManualDiffHelpList* pManualDiffHelpList);
390

Joachim Eibl's avatar
Joachim Eibl committed
391

Joachim Eibl's avatar
0.9.80  
Joachim Eibl committed
392

393
bool fineDiff(
Michael Reeves's avatar
Michael Reeves committed
394 395
    Diff3LineList& diff3LineList,
    int selector,
Michael Reeves's avatar
Michael Reeves committed
396 397
    const QVector<LineData>* v1,
    const QVector<LineData>* v2);
Joachim Eibl's avatar
Joachim Eibl committed
398

Michael Reeves's avatar
Michael Reeves committed
399
inline bool isWhite(QChar c)
Joachim Eibl's avatar
Joachim Eibl committed
400
{
Michael Reeves's avatar
Michael Reeves committed
401
    return c == ' ' || c == '\t' || c == '\r';
Joachim Eibl's avatar
Joachim Eibl committed
402 403 404 405
}

/** Returns the number of equivalent spaces at position outPos.
*/
Michael Reeves's avatar
Michael Reeves committed
406
inline int tabber(int outPos, int tabSize)
Joachim Eibl's avatar
Joachim Eibl committed
407
{
Michael Reeves's avatar
Michael Reeves committed
408
    return tabSize - (outPos % tabSize);
Joachim Eibl's avatar
Joachim Eibl committed
409 410 411 412 413 414
}

/** Returns a line number where the linerange [line, line+nofLines] can
    be displayed best. If it fits into the currently visible range then
    the returned value is the current firstLine.
*/
Michael Reeves's avatar
Michael Reeves committed
415
int getBestFirstLine(int line, int nofLines, int firstLine, int visibleLines);
Joachim Eibl's avatar
Joachim Eibl committed
416 417 418 419 420 421

extern bool g_bIgnoreWhiteSpace;
extern bool g_bIgnoreTrivialMatches;
extern int g_bAutoSolve;

// Cursor conversions that consider g_tabSize.
Michael Reeves's avatar
Michael Reeves committed
422 423
int convertToPosInText(const QString& s, int posOnScreen, int tabSize);
int convertToPosOnScreen(const QString& s, int posInText, int tabSize);
Joachim Eibl's avatar
Joachim Eibl committed
424

Michael Reeves's avatar
Michael Reeves committed
425 426 427 428 429 430
enum e_CoordType
{
    eFileCoords,
    eD3LLineCoords,
    eWrapCoords
};
Joachim Eibl's avatar
Joachim Eibl committed
431

Michael Reeves's avatar
Michael Reeves committed
432
void calcTokenPos(const QString&, int posOnScreen, int& pos1, int& pos2, int tabSize);
Joachim Eibl's avatar
Joachim Eibl committed
433

Michael Reeves's avatar
Michael Reeves committed
434 435
QString calcHistorySortKey(const QString& keyOrder, QRegExp& matchedRegExpr, const QStringList& parenthesesGroupList);
bool findParenthesesGroups(const QString& s, QStringList& sl);
Joachim Eibl's avatar
Joachim Eibl committed
436
#endif