Src/DiffList.h

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /**
   3  * @file  DiffList.h
   4  *
   5  * @brief Declaration file for DiffList class
   6  */
   7 #pragma once
   8
   9 #include <vector>
  10 #include <cstring>
  11
  12 /**
  13  * @brief Operations in diffranges.
  14  * DIFFRANGE structs op-member can have these values
  15  */
  16 enum OP_TYPE
  17 {
  18         OP_NONE = 0,
  19         OP_1STONLY,
  20         OP_2NDONLY,
  21         OP_3RDONLY,
  22         OP_DIFF,
  23         OP_TRIVIAL
  24 };
  25
  26 enum
  27 {
  28         THREEWAYDIFFTYPE_LEFTMIDDLE  = 0,
  29         THREEWAYDIFFTYPE_LEFTRIGHT,
  30         THREEWAYDIFFTYPE_MIDDLERIGHT,
  31         THREEWAYDIFFTYPE_LEFTONLY,
  32         THREEWAYDIFFTYPE_MIDDLEONLY,
  33         THREEWAYDIFFTYPE_RIGHTONLY,
  34         THREEWAYDIFFTYPE_CONFLICT,
  35 };
  36
  37 /**
  38  * @brief One difference defined by linenumbers.
  39  *
  40  * This struct defines one set of different lines "diff".
  41  * @p begin0, @p end0, @p begin1 & @p end1 are linenumbers
  42  * in original files. Other struct members point to linenumbers
  43  * calculated by WinMerge after adding empty lines to make diffs
  44  * be in line in screen.
  45  *
  46  * @note @p blank0 & @p blank1 are -1 if there are no blank lines
  47  */
  48 struct DIFFRANGE
  49 {
  50         int begin[3] = {};           /**< First diff line in original file1,2,3 */
  51         int end[3] = {};             /**< Last diff line in original file1,2,3 */
  52         int dbegin = 0;              /**< Synchronised (ghost lines added) first diff line in file1,2,3 */
  53         int dend = 0;                /**< Synchronised (ghost lines added) last diff line in file1,2,3 */
  54         int blank[3] = {-1, -1, -1}; /**< Number of blank lines in file1,2,3 */
  55         OP_TYPE op = OP_NONE;        /**< Operation done with this diff */
  56         DIFFRANGE() = default;
  57         void swap_sides(int index1, int index2);
  58 };
  59
  60 /**
  61  * @brief Relation from left side (0) to right side (1) of a DIFFRANGE
  62  *
  63  * Map lines from file1 to file2
  64  */
  65 class DiffMap
  66 {
  67 public:
  68         enum
  69         {
  70                 BAD_MAP_ENTRY = -999999999,
  71                 GHOST_MAP_ENTRY = 888888888
  72         };
  73
  74         std::vector<int> m_map;
  75
  76         DiffMap() = default;
  77         void InitDiffMap(int nlines);
  78 };
  79
  80 /**
  81  * @brief DIFFRANGE with links for chain of non-trivial entries
  82  *
  83  * Next and prev are array indices used by the owner (DiffList)
  84  */
  85 struct DiffRangeInfo: public DIFFRANGE
  86 {
  87         ptrdiff_t next; /**< link (array index) for doubly-linked chain of non-trivial DIFFRANGEs */
  88         ptrdiff_t prev; /**< link (array index) for doubly-linked chain of non-trivial DIFFRANGEs */
  89
  90         DiffRangeInfo() { InitLinks(); }
  91         explicit DiffRangeInfo(const DIFFRANGE & di) : DIFFRANGE(di) { InitLinks(); }
  92         void InitLinks() { next = prev = -1; }
  93 };
  94
  95 /**
  96  * @brief Class for storing differences in files (difflist).
  97  *
  98  * This class stores diffs in list and also offers diff-related
  99  * functions to e.g. check if linenumber is inside diff.
 100  *
 101  * There are two kinds of diffs:
 102  * - significant diffs are 'normal' diffs we want to merge and browse
 103  * - non-significant diffs are diffs ignored by linefilters
 104  *
 105  * The code assumes diff lists don't grow bigger than 32-bit int type's
 106  * range. And what a trouble we'd have if we have so many diffs...
 107  */
 108 class DiffList
 109 {
 110 public:
 111         DiffList();
 112         void Clear();
 113         int GetSize() const;
 114         int GetSignificantDiffs() const;
 115         void AddDiff(const DIFFRANGE & di);
 116         bool IsDiffSignificant(int nDiff) const;
 117         int GetSignificantIndex(int nDiff) const;
 118         bool GetDiff(int nDiff, DIFFRANGE & di) const;
 119         bool SetDiff(int nDiff, const DIFFRANGE & di);
 120         int LineRelDiff(int nLine, int nDiff) const;
 121         bool LineInDiff(int nLine, int nDiff) const;
 122         int LineToDiff(int nLine) const;
 123         bool GetPrevDiff(int nLine, int & nDiff) const;
 124         bool GetNextDiff(int nLine, int & nDiff) const;
 125         bool HasSignificantDiffs() const;
 126         int PrevSignificantDiffFromLine(int nLine) const;
 127         int NextSignificantDiffFromLine(int nLine) const;
 128         int FirstSignificantDiff() const;
 129         int NextSignificantDiff(int nDiff) const;
 130         int PrevSignificantDiff(int nDiff) const;
 131         int LastSignificantDiff() const;
 132         const DIFFRANGE * FirstSignificantDiffRange() const;
 133         const DIFFRANGE * LastSignificantDiffRange() const;
 134         int PrevSignificant3wayDiffFromLine(int nLine, int nDiffType) const;
 135         int NextSignificant3wayDiffFromLine(int nLine, int nDiffType) const;
 136         int FirstSignificant3wayDiff(int nDiffType) const;
 137         int NextSignificant3wayDiff(int nDiff, int nDiffType) const;
 138         int PrevSignificant3wayDiff(int nDiff, int nDiffType) const;
 139         int LastSignificant3wayDiff(int nDiffType) const;
 140         const DIFFRANGE * FirstSignificant3wayDiffRange(int nDiffType) const;
 141         const DIFFRANGE * LastSignificant3wayDiffRange(int nDiffType) const;
 142         int GetMergeableSrcIndex(int nDiff, int nDestIndex) const;
 143
 144         const DIFFRANGE * DiffRangeAt(int nDiff) const;
 145
 146         void ConstructSignificantChain(); // must be called after diff list is entirely populated
 147         void Swap(int index1, int index2);
 148         void GetExtraLinesCounts(int nFiles, int extras[3]);
 149
 150         std::vector<DiffRangeInfo>& GetDiffRangeInfoVector() { return m_diffs; }
 151
 152         void AppendDiffList(const DiffList& list, const int offset[] = nullptr, int doffset = 0);
 153
 154 private:
 155         std::vector<DiffRangeInfo> m_diffs; /**< Difference list. */
 156         int m_firstSignificant; /**< Index of first significant diff in m_diffs */
 157         int m_lastSignificant; /**< Index of last significant diff in m_diffs */
 158         int m_firstSignificantLeftMiddle;
 159         int m_firstSignificantLeftRight;
 160         int m_firstSignificantMiddleRight;
 161         int m_firstSignificantLeftOnly;
 162         int m_firstSignificantMiddleOnly;
 163         int m_firstSignificantRightOnly;
 164         int m_firstSignificantConflict;
 165         int m_lastSignificantLeftMiddle;
 166         int m_lastSignificantLeftRight;
 167         int m_lastSignificantMiddleRight;
 168         int m_lastSignificantLeftOnly;
 169         int m_lastSignificantMiddleOnly;
 170         int m_lastSignificantRightOnly;
 171         int m_lastSignificantConflict;
 172 };
 173
 174 /**
 175  * @brief Returns count of items in diff list.
 176  * This function returns total amount of items (diffs) in list. So returned
 177  * count includes significant and non-significant diffs.
 178  * @note Use GetSignificantDiffs() to get count of non-ignored diffs.
 179  */
 180 inline int DiffList::GetSize() const
 181 {
 182         return (int) m_diffs.size();
 183 }
 184
 185 /**
 186  * @brief Check if diff-list contains significant diffs.
 187  * @return true if list has significant diffs, false otherwise.
 188  */
 189 inline bool DiffList::HasSignificantDiffs() const
 190 {
 191         return (m_firstSignificant != -1);
 192 }
 193
 194 /**
 195  * @brief Return index to first significant difference.
 196  * @return Index of first significant difference.
 197  */
 198 inline int DiffList::FirstSignificantDiff() const
 199 {
 200         return m_firstSignificant;
 201 }
 202
 203 /**
 204  * @brief Return index of next significant diff.
 205  * @param [in] nDiff Index to start looking for next diff.
 206  * @return Index of next significant difference.
 207  */
 208 inline int DiffList::NextSignificantDiff(int nDiff) const
 209 {
 210         return (int)m_diffs[nDiff].next;
 211 }
 212
 213 /**
 214  * @brief Return index of previous significant diff.
 215  * @param [in] nDiff Index to start looking for previous diff.
 216  * @return Index of previous significant difference.
 217  */
 218 inline int DiffList::PrevSignificantDiff(int nDiff) const
 219 {
 220         return (int)m_diffs[nDiff].prev;
 221 }
 222
 223 /**
 224  * @brief Return index to last significant diff.
 225  * @return Index of last significant difference.
 226  */
 227 inline int DiffList::LastSignificantDiff() const
 228 {
 229         return m_lastSignificant;
 230 }