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()
  57         {
  58         }
  59         void swap_sides(int index1, int index2);
  60 };
  61
  62 /**
  63  * @brief Relation from left side (0) to right side (1) of a DIFFRANGE
  64  *
  65  * Map lines from file1 to file2
  66  */
  67 class DiffMap
  68 {
  69 public:
  70         enum
  71         {
  72                 BAD_MAP_ENTRY = -999999999,
  73                 GHOST_MAP_ENTRY = 888888888
  74         };
  75
  76         std::vector<int> m_map;
  77
  78         // boilerplate ctr, copy ctr
  79         DiffMap() { }
  80         DiffMap(const DiffMap & src) : m_map(src.m_map) {}
  81         void InitDiffMap(int nlines);
  82 };
  83
  84 /**
  85  * @brief DIFFRANGE with links for chain of non-trivial entries
  86  *
  87  * Next and prev are array indices used by the owner (DiffList)
  88  */
  89 struct DiffRangeInfo: public DIFFRANGE
  90 {
  91         ptrdiff_t next; /**< link (array index) for doubly-linked chain of non-trivial DIFFRANGEs */
  92         ptrdiff_t prev; /**< link (array index) for doubly-linked chain of non-trivial DIFFRANGEs */
  93
  94         DiffRangeInfo() { InitLinks(); }
  95         explicit DiffRangeInfo(const DIFFRANGE & di) : DIFFRANGE(di) { InitLinks(); }
  96         void InitLinks() { next = prev = -1; }
  97 };
  98
  99 /**
 100  * @brief Class for storing differences in files (difflist).
 101  *
 102  * This class stores diffs in list and also offers diff-related
 103  * functions to e.g. check if linenumber is inside diff.
 104  *
 105  * There are two kinds of diffs:
 106  * - significant diffs are 'normal' diffs we want to merge and browse
 107  * - non-significant diffs are diffs ignored by linefilters
 108  *
 109  * The code assumes diff lists don't grow bigger than 32-bit int type's
 110  * range. And what a trouble we'd have if we have so many diffs...
 111  */
 112 class DiffList
 113 {
 114 public:
 115         DiffList();
 116         void Clear();
 117         int GetSize() const;
 118         int GetSignificantDiffs() const;
 119         void AddDiff(const DIFFRANGE & di);
 120         bool IsDiffSignificant(int nDiff) const;
 121         int GetSignificantIndex(int nDiff) const;
 122         bool GetDiff(int nDiff, DIFFRANGE & di) const;
 123         bool SetDiff(int nDiff, const DIFFRANGE & di);
 124         int LineRelDiff(int nLine, int nDiff) const;
 125         bool LineInDiff(int nLine, int nDiff) const;
 126         int LineToDiff(int nLine) const;
 127         bool GetPrevDiff(int nLine, int & nDiff) const;
 128         bool GetNextDiff(int nLine, int & nDiff) const;
 129         bool HasSignificantDiffs() const;
 130         int PrevSignificantDiffFromLine(int nLine) const;
 131         int NextSignificantDiffFromLine(int nLine) const;
 132         int FirstSignificantDiff() const;
 133         int NextSignificantDiff(int nDiff) const;
 134         int PrevSignificantDiff(int nDiff) const;
 135         int LastSignificantDiff() const;
 136         const DIFFRANGE * FirstSignificantDiffRange() const;
 137         const DIFFRANGE * LastSignificantDiffRange() const;
 138         int PrevSignificant3wayDiffFromLine(int nLine, int nDiffType) const;
 139         int NextSignificant3wayDiffFromLine(int nLine, int nDiffType) const;
 140         int FirstSignificant3wayDiff(int nDiffType) const;
 141         int NextSignificant3wayDiff(int nDiff, int nDiffType) const;
 142         int PrevSignificant3wayDiff(int nDiff, int nDiffType) const;
 143         int LastSignificant3wayDiff(int nDiffType) const;
 144         const DIFFRANGE * FirstSignificant3wayDiffRange(int nDiffType) const;
 145         const DIFFRANGE * LastSignificant3wayDiffRange(int nDiffType) const;
 146         int GetMergeableSrcIndex(int nDiff, int nDestIndex) const;
 147
 148         const DIFFRANGE * DiffRangeAt(int nDiff) const;
 149
 150         void ConstructSignificantChain(); // must be called after diff list is entirely populated
 151         void Swap(int index1, int index2);
 152         void GetExtraLinesCounts(int nFiles, int extras[3]);
 153
 154         std::vector<DiffRangeInfo>& GetDiffRangeInfoVector() { return m_diffs; }
 155
 156         void AppendDiffList(const DiffList& list, int offset[] = nullptr, int doffset = 0);
 157
 158 private:
 159         std::vector<DiffRangeInfo> m_diffs; /**< Difference list. */
 160         int m_firstSignificant; /**< Index of first significant diff in m_diffs */
 161         int m_lastSignificant; /**< Index of last significant diff in m_diffs */
 162         int m_firstSignificantLeftMiddle;
 163         int m_firstSignificantLeftRight;
 164         int m_firstSignificantMiddleRight;
 165         int m_firstSignificantLeftOnly;
 166         int m_firstSignificantMiddleOnly;
 167         int m_firstSignificantRightOnly;
 168         int m_firstSignificantConflict;
 169         int m_lastSignificantLeftMiddle;
 170         int m_lastSignificantLeftRight;
 171         int m_lastSignificantMiddleRight;
 172         int m_lastSignificantLeftOnly;
 173         int m_lastSignificantMiddleOnly;
 174         int m_lastSignificantRightOnly;
 175         int m_lastSignificantConflict;
 176 };
 177
 178 /**
 179  * @brief Returns count of items in diff list.
 180  * This function returns total amount of items (diffs) in list. So returned
 181  * count includes significant and non-significant diffs.
 182  * @note Use GetSignificantDiffs() to get count of non-ignored diffs.
 183  */
 184 inline int DiffList::GetSize() const
 185 {
 186         return (int) m_diffs.size();
 187 }
 188
 189 /**
 190  * @brief Check if diff-list contains significant diffs.
 191  * @return true if list has significant diffs, false otherwise.
 192  */
 193 inline bool DiffList::HasSignificantDiffs() const
 194 {
 195         return (m_firstSignificant != -1);
 196 }
 197
 198 /**
 199  * @brief Return index to first significant difference.
 200  * @return Index of first significant difference.
 201  */
 202 inline int DiffList::FirstSignificantDiff() const
 203 {
 204         return m_firstSignificant;
 205 }
 206
 207 /**
 208  * @brief Return index of next significant diff.
 209  * @param [in] nDiff Index to start looking for next diff.
 210  * @return Index of next significant difference.
 211  */
 212 inline int DiffList::NextSignificantDiff(int nDiff) const
 213 {
 214         return (int)m_diffs[nDiff].next;
 215 }
 216
 217 /**
 218  * @brief Return index of previous significant diff.
 219  * @param [in] nDiff Index to start looking for previous diff.
 220  * @return Index of previous significant difference.
 221  */
 222 inline int DiffList::PrevSignificantDiff(int nDiff) const
 223 {
 224         return (int)m_diffs[nDiff].prev;
 225 }
 226
 227 /**
 228  * @brief Return index to last significant diff.
 229  * @return Index of last significant difference.
 230  */
 231 inline int DiffList::LastSignificantDiff() const
 232 {
 233         return m_lastSignificant;
 234 }