Src/Diff3.h

   1 #pragma once
   2
   3 #include <vector>
   4 #include <algorithm>
   5 #include "DiffList.h"
   6
   7 /* diff3 algorithm. It is almost the same as GNU diff3's algorithm */
   8 template<typename Element, typename Comp02Func>
   9 size_t Make3wayDiff(std::vector<Element>& diff3, const std::vector<Element>& diff10, const std::vector<Element>& diff12,
  10         Comp02Func cmpfunc, bool has_trivial_diffs)
  11 {
  12         const size_t diff10count = diff10.size();
  13         const size_t diff12count = diff12.size();
  14
  15         size_t diff10i = 0;
  16         size_t diff12i = 0;
  17
  18         Element dr3, dr10, dr12, dr10first, dr10last, dr12first, dr12last;
  19
  20         int linelast0 = 0;
  21         int linelast1 = 0;
  22         int linelast2 = 0;
  23
  24         bool firstDiffBlockIsDiff12;
  25
  26         for (;;)
  27         {
  28                 /*
  29                  * merge overlapped diff blocks
  30                  * diff10 is diff blocks between file1 and file0.
  31                  * diff12 is diff blocks between file1 and file2.
  32                  *
  33                  *                      diff12
  34                  *                 diff10            diff3
  35                  *                 |~~~|             |~~~|
  36                  * firstDiffBlock  |   |             |   |
  37                  *                 |   | |~~~|       |   |
  38                  *                 |___| |   |       |   |
  39                  *                       |   |   ->  |   |
  40                  *                 |~~~| |___|       |   |
  41                  * lastDiffBlock   |   |             |   |
  42                  *                 |___|             |___|
  43                  */
  44
  45                 if (diff10i >= diff10count)
  46                 {
  47                         if (diff12i >= diff12count)
  48                                 break;
  49
  50                         dr12last = dr12first = diff12[diff12i];
  51                         firstDiffBlockIsDiff12 = true;
  52                 }
  53                 else if (diff12i >= diff12count)
  54                 {
  55                         dr10last = dr10first = diff10[diff10i];
  56                         firstDiffBlockIsDiff12 = false;
  57                 }
  58                 else
  59                 {
  60                         dr10last = dr10first = diff10[diff10i];
  61                         dr12last = dr12first = diff12[diff12i];
  62                         firstDiffBlockIsDiff12 = (dr12first.begin[0] <= dr10first.begin[0]);
  63                 }
  64                 bool lastDiffBlockIsDiff12 = firstDiffBlockIsDiff12;
  65
  66                 size_t diff10itmp = diff10i;
  67                 size_t diff12itmp = diff12i;
  68                 for (;;)
  69                 {
  70                         if (diff10itmp >= diff10count || diff12itmp >= diff12count)
  71                                 break;
  72
  73                         dr10 = diff10[diff10itmp];
  74                         dr12 = diff12[diff12itmp];
  75
  76                         if (dr10.end[0] == dr12.end[0])
  77                         {
  78                                 diff10itmp++;
  79                                 lastDiffBlockIsDiff12 = true;
  80
  81                                 dr10last = dr10;
  82                                 dr12last = dr12;
  83                                 break;
  84                         }
  85
  86                         if (lastDiffBlockIsDiff12)
  87                         {
  88                                 if (std::max(dr12.begin[0], dr12.end[0]) < dr10.begin[0])
  89                                         break;
  90                         }
  91                         else
  92                         {
  93                                 if (std::max(dr10.begin[0], dr10.end[0]) < dr12.begin[0])
  94                                         break;
  95                         }
  96
  97                         if (dr12.end[0] > dr10.end[0])
  98                         {
  99                                 diff10itmp++;
 100                                 lastDiffBlockIsDiff12 = true;
 101                         }
 102                         else
 103                         {
 104                                 diff12itmp++;
 105                                 lastDiffBlockIsDiff12 = false;
 106                         }
 107
 108                         dr10last = dr10;
 109                         dr12last = dr12;
 110                 }
 111
 112                 if (lastDiffBlockIsDiff12)
 113                         diff12itmp++;
 114                 else
 115                         diff10itmp++;
 116
 117                 if (firstDiffBlockIsDiff12)
 118                 {
 119                         dr3.begin[1] = dr12first.begin[0];
 120                         dr3.begin[2] = dr12first.begin[1];
 121                         if (diff10itmp == diff10i)
 122                                 dr3.begin[0] = dr3.begin[1] - linelast1 + linelast0;
 123                         else
 124                                 dr3.begin[0] = dr3.begin[1] - dr10first.begin[0] + dr10first.begin[1];
 125                 }
 126                 else
 127                 {
 128                         dr3.begin[0] = dr10first.begin[1];
 129                         dr3.begin[1] = dr10first.begin[0];
 130                         if (diff12itmp == diff12i)
 131                                 dr3.begin[2] = dr3.begin[1] - linelast1 + linelast2;
 132                         else
 133                                 dr3.begin[2] = dr3.begin[1] - dr12first.begin[0] + dr12first.begin[1];
 134                 }
 135
 136                 if (lastDiffBlockIsDiff12)
 137                 {
 138                         dr3.end[1] = dr12last.end[0];
 139                         dr3.end[2] = dr12last.end[1];
 140                         if (diff10itmp == diff10i)
 141                                 dr3.end[0] = dr3.end[1] - linelast1 + linelast0;
 142                         else
 143                                 dr3.end[0] = dr3.end[1] - dr10last.end[0] + dr10last.end[1];
 144                 }
 145                 else
 146                 {
 147                         dr3.end[0] = dr10last.end[1];
 148                         dr3.end[1] = dr10last.end[0];
 149                         if (diff12itmp == diff12i)
 150                                 dr3.end[2] = dr3.end[1] - linelast1 + linelast2;
 151                         else
 152                                 dr3.end[2] = dr3.end[1] - dr12last.end[0] + dr12last.end[1];
 153                 }
 154
 155                 linelast0 = dr3.end[0] + 1;
 156                 linelast1 = dr3.end[1] + 1;
 157                 linelast2 = dr3.end[2] + 1;
 158
 159                 if (diff10i == diff10itmp)
 160                         dr3.op = OP_3RDONLY;
 161                 else if (diff12i == diff12itmp)
 162                         dr3.op = OP_1STONLY;
 163                 else
 164                 {
 165                         if (!cmpfunc(dr3))
 166                                 dr3.op = OP_DIFF;
 167                         else
 168                                 dr3.op = OP_2NDONLY;
 169                 }
 170
 171                 if (has_trivial_diffs)
 172                 {
 173                         bool bTrivialDiff10 = true;
 174                         bool bTrivialDiff12 = true;
 175                         size_t i;
 176
 177                         for (i = diff10i; i < diff10itmp; i++)
 178                         {
 179                                 dr10 = diff10.at(i);
 180                                 if (dr10.op != OP_TRIVIAL)
 181                                 {
 182                                         bTrivialDiff10 = false;
 183                                         break;
 184                                 }
 185                         }
 186
 187                         for (i = diff12i; i < diff12itmp; i++)
 188                         {
 189                                 dr12 = diff12.at(i);
 190                                 if (dr12.op != OP_TRIVIAL)
 191                                 {
 192                                         bTrivialDiff12 = false;
 193                                         break;
 194                                 }
 195                         }
 196
 197                         if (bTrivialDiff10 && bTrivialDiff12)
 198                                 dr3.op = OP_TRIVIAL;
 199                 }
 200
 201                 diff10i = diff10itmp;
 202                 diff12i = diff12itmp;
 203
 204                 diff3.push_back(dr3);
 205         }
 206
 207         size_t cnt = diff3.size();
 208         if (cnt)
 209         {
 210                 for (size_t i = 0; i != (cnt - 1); i++)
 211                 {
 212                         Element& dr3r = diff3[i];
 213                         Element& dr3next = diff3[i + 1];
 214                         for (int j = 0; j < 3; j++)
 215                         {
 216                                 if (dr3r.end[j] >= dr3next.begin[j])
 217                                         dr3r.end[j] = dr3next.begin[j] - 1;
 218                         }
 219                 }
 220         }
 221
 222         return cnt;
 223 }