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