Src/MergeDocDiffSync.cpp

   1 /**
   2  * @file  MergeDocDiffSync.cpp
   3  *
   4  * @brief Code to layout diff blocks, to find matching lines, and insert ghost lines
   5  *
   6  */
   7
   8 #include "StdAfx.h"
   9 #include <vector>
  10 #include "MergeDoc.h"
  11
  12 #include "Merge.h"
  13 #include "DiffList.h"
  14 #include "stringdiffs.h"
  15
  16 #ifdef _DEBUG
  17 #define new DEBUG_NEW
  18 #endif
  19
  20 using std::vector;
  21
  22 static void
  23 ValidateDiffMap(const DiffMap& diffmap)
  24 {
  25         for (const auto& line : diffmap.m_map)
  26                 assert(line != DiffMap::BAD_MAP_ENTRY);
  27 }
  28
  29 template <int npanes>
  30 static void
  31 ValidateVirtualLineToRealLineMap(
  32         const std::vector<std::array<int, npanes>>& vlines,
  33         const std::array<int, npanes>& nlines)
  34 {
  35         int line[npanes]{};
  36         for (const auto& v : vlines)
  37         {
  38                 for (int pane = 0; pane < npanes; ++pane)
  39                 {
  40                         if (v[pane] != DiffMap::GHOST_MAP_ENTRY)
  41                         {
  42                                 assert(line[pane] == v[pane]);
  43                                 ++line[pane];
  44                         }
  45                 }
  46         }
  47         for (int pane = 0; pane < npanes; ++pane)
  48                 assert(line[pane] == nlines[pane]);
  49 }
  50
  51 template <int npanes>
  52 static void
  53 PrintVirtualLineToRealLineMap(
  54         const String& name,
  55         const std::vector<std::array<int, npanes>>& vlines)
  56 {
  57         OutputDebugString((_T("[") + name + _T("]\n")).c_str());
  58         for (size_t i = 0; i < vlines.size(); ++i)
  59         {
  60                 String str = strutils::format(_T("vline%d: "), static_cast<int>(i));
  61                 std::vector<String> ary;
  62                 for (int j = 0; j < npanes; ++j)
  63                         ary.push_back(vlines[i][j] == DiffMap::GHOST_MAP_ENTRY ? _T("-----") : strutils::format(_T("%5d"), vlines[i][j]));
  64                 str += strutils::join(ary.begin(), ary.end(), _T(",")) + _T("\n");
  65                 OutputDebugString(str.c_str());
  66         }
  67 }
  68
  69 #ifdef _DEBUG
  70 static void
  71 PrintWordDiffList(int nPanes, const std::vector<WordDiff>& worddiffs)
  72 {
  73         String lines = _T("[word-diff list]\n");
  74         for (size_t i = 0; i < worddiffs.size(); ++i)
  75         {
  76                 lines += strutils::format(_T("worddiff[%d] "), i);
  77                 for (int j = 0; j < nPanes; ++j)
  78                 {
  79                         lines += strutils::format(_T("pane:%d (line:%d,col:%d)-(line:%d,col:%d) "),
  80                                         j, worddiffs[i].beginline[j], worddiffs[i].begin[j], worddiffs[i].endline[j], worddiffs[i].end[j]);
  81                 }
  82                 lines += _T("\n");
  83         }
  84         OutputDebugString(lines.c_str());
  85 }
  86 #endif
  87
  88 /**
  89  * @brief Create map from virtual line to real line.
  90  */
  91 static std::vector<std::array<int, 2>>
  92 CreateVirtualLineToRealLineMap(
  93         const DiffMap& diffmap, int nlines0, int nlines1)
  94 {
  95         std::vector<std::array<int, 2>> vlines;
  96         int line0 = 0, line1 = 0;
  97         while (line0 < nlines0)
  98         {
  99                 const int map_line0 = diffmap.m_map[line0];
 100                 if (map_line0 == DiffMap::GHOST_MAP_ENTRY || map_line0 == DiffMap::BAD_MAP_ENTRY)
 101                 {
 102                         vlines.push_back({ line0++, DiffMap::GHOST_MAP_ENTRY });
 103                 }
 104                 else
 105                 {
 106                         while (line1 < map_line0)
 107                                 vlines.push_back({ DiffMap::GHOST_MAP_ENTRY, line1++ });
 108                         vlines.push_back({ line0++, line1++ });
 109                 }
 110         }
 111         while (line1 < nlines1)
 112                 vlines.push_back({ DiffMap::GHOST_MAP_ENTRY, line1++ });
 113         ValidateVirtualLineToRealLineMap(vlines, std::array<int, 2>{ nlines0, nlines1 });
 114 #ifdef _DEBUG
 115         PrintVirtualLineToRealLineMap(_T("vline"), vlines);
 116 #endif
 117         return vlines;
 118 }
 119
 120 /**
 121  * @brief Create map from virtual line to real line. (3-way)
 122  */
 123 static std::vector<std::array<int, 3>>
 124 CreateVirtualLineToRealLineMap3way(
 125         const DiffMap& diffmap01, const DiffMap& diffmap12, const DiffMap& diffmap20,
 126         int nlines0, int nlines1, int nlines2)
 127 {
 128         std::vector<std::array<int, 2>> vlines01 = CreateVirtualLineToRealLineMap(diffmap01, nlines0, nlines1);
 129         std::vector<std::array<int, 2>> vlines12 = CreateVirtualLineToRealLineMap(diffmap12, nlines1, nlines2);
 130         std::vector<std::array<int, 2>> vlines20 = CreateVirtualLineToRealLineMap(diffmap20, nlines2, nlines0);
 131         std::vector<std::array<int, 3>> vlines;
 132         size_t i01 = 0, i12 = 0, i20 = 0;
 133         int line0 = 0, line1 = 0, line2 = 0;
 134         bool is_vlines20_usable = true;
 135         // 1.
 136         for (line1 = 0; line1 < nlines1; ++line1)
 137         {
 138                 size_t i01b = i01;
 139                 size_t i12b = i12;
 140                 size_t i20b = i20;
 141                 // 1.1
 142                 for (; i01 < vlines01.size(); ++i01)
 143                         if (vlines01[i01][1] == line1)
 144                                 break;
 145                 for (; i12 < vlines12.size(); ++i12)
 146                         if (vlines12[i12][0] == line1)
 147                                 break;
 148                 assert(i01 < vlines01.size() && i12 < vlines12.size());
 149                 // 1.2
 150                 bool used_vlines20 = false;
 151                 if (is_vlines20_usable)
 152                 {
 153                         if (vlines12[i12][1] != DiffMap::GHOST_MAP_ENTRY && vlines01[i01][0] != DiffMap::GHOST_MAP_ENTRY)
 154                         {
 155                                 // 1.2.1
 156                                 line2 = vlines12[i12][1];
 157                                 line0 = vlines01[i01][0];
 158                                 size_t i20tmp;
 159                                 for (i20tmp = i20b; i20tmp < vlines20.size(); ++i20tmp)
 160                                         if (vlines20[i20tmp][0] == line2 && vlines20[i20tmp][1] == line0)
 161                                                 break;
 162                                 if (i20tmp < vlines20.size())
 163                                 {
 164                                         // 1.2.1.1
 165                                         for (; i20 < i20tmp; ++i20)
 166                                                 vlines.push_back({ vlines20[i20][1], DiffMap::GHOST_MAP_ENTRY, vlines20[i20][0] });
 167                                         ++i20;
 168                                         used_vlines20 = true;
 169                                 }
 170                                 else
 171                                 {
 172                                         // 1.2.1.2
 173                                         is_vlines20_usable = false;
 174                                 }
 175                         }
 176                         else
 177                         {
 178                                 // 1.2.2
 179                                 is_vlines20_usable = false;
 180                         }
 181                 }
 182                 // 1.3
 183                 if (!used_vlines20)
 184                 {
 185                         size_t i01tmp, i12tmp;
 186                         for (i01tmp = i01b, i12tmp = i12b; i01tmp < i01 && i12tmp < i12; ++i01tmp, ++i12tmp)
 187                                 vlines.push_back({ vlines01[i01tmp][0], DiffMap::GHOST_MAP_ENTRY, vlines12[i12tmp][1] });
 188                         if (i01 - i01b < i12 - i12b)
 189                         {
 190                                 // 1.3.1
 191                                 for (; i12tmp < i12; ++i12tmp)
 192                                         vlines.push_back({ DiffMap::GHOST_MAP_ENTRY, DiffMap::GHOST_MAP_ENTRY, vlines12[i12tmp][1] });
 193                         }
 194                         else if (i01 - i01b > i12 - i12b)
 195                         {
 196                                 // 1.3.2
 197                                 for (; i01tmp < i01; ++i01tmp)
 198                                         vlines.push_back({ vlines01[i01tmp][0], DiffMap::GHOST_MAP_ENTRY, DiffMap::GHOST_MAP_ENTRY });
 199                         }
 200                 }
 201                 vlines.push_back({ vlines01[i01++][0], line1, vlines12[i12++][1]});
 202         }
 203         // 2.
 204         if (i01 < vlines01.size() || i12 < vlines12.size())
 205         {
 206                 if (is_vlines20_usable)
 207                 {
 208                         // 2.1
 209                         for (; i20 < vlines20.size(); ++i20)
 210                                 vlines.push_back({ vlines20[i20][1], DiffMap::GHOST_MAP_ENTRY, vlines20[i20][0] });
 211                 }
 212                 else
 213                 {
 214                         // 2.2
 215                         for (; i01 < vlines01.size() && i12 < vlines12.size(); ++i01, ++i12)
 216                                 vlines.push_back({ vlines01[i01][0], DiffMap::GHOST_MAP_ENTRY, vlines12[i12][1] });
 217                         if (vlines01.size() - i01 < vlines12.size() - i12)
 218                         {
 219                                 // 2.2.1
 220                                 for (; i12 < vlines12.size(); ++i12)
 221                                         vlines.push_back({ DiffMap::GHOST_MAP_ENTRY, DiffMap::GHOST_MAP_ENTRY, vlines12[i12][1] });
 222                         }
 223                         else if (vlines01.size() - i01 > vlines12.size() - i12)
 224                         {
 225                                 // 2.2.2
 226                                 for (; i01 < vlines01.size(); ++i01)
 227                                         vlines.push_back({ vlines01[i01][0], DiffMap::GHOST_MAP_ENTRY, DiffMap::GHOST_MAP_ENTRY });
 228                         }
 229                 }
 230         }
 231         ValidateVirtualLineToRealLineMap(vlines, std::array<int, 3>{ nlines0, nlines1, nlines2 });
 232 #ifdef _DEBUG
 233         PrintVirtualLineToRealLineMap(_T("vline01"), vlines01);
 234         PrintVirtualLineToRealLineMap(_T("vline12"), vlines12);
 235         PrintVirtualLineToRealLineMap(_T("vline20"), vlines20);
 236         PrintVirtualLineToRealLineMap(_T("vline3way"), vlines);
 237 #endif
 238         return vlines;
 239 }
 240
 241 OP_TYPE CMergeDoc::ComputeOpType3way(
 242         const std::vector<std::array<int, 3>>& vlines, size_t index,
 243         const DIFFRANGE& diffrange, const DIFFOPTIONS& diffOptions)
 244 {
 245         if (vlines[index][0] != DiffMap::GHOST_MAP_ENTRY &&
 246             vlines[index][1] == DiffMap::GHOST_MAP_ENTRY &&
 247             vlines[index][2] == DiffMap::GHOST_MAP_ENTRY)
 248         {
 249                 return OP_1STONLY;
 250         }
 251         else if (vlines[index][0] == DiffMap::GHOST_MAP_ENTRY &&
 252              vlines[index][1] != DiffMap::GHOST_MAP_ENTRY &&
 253                      vlines[index][2] == DiffMap::GHOST_MAP_ENTRY)
 254         {
 255                 return OP_2NDONLY;
 256         }
 257         else if (vlines[index][0] == DiffMap::GHOST_MAP_ENTRY &&
 258                  vlines[index][1] == DiffMap::GHOST_MAP_ENTRY &&
 259                  vlines[index][2] != DiffMap::GHOST_MAP_ENTRY)
 260         {
 261                 return OP_3RDONLY;
 262         }
 263
 264         int line0 = diffrange.begin[0] + vlines[index][0];
 265         int line1 = diffrange.begin[1] + vlines[index][1];
 266         int line2 = diffrange.begin[2] + vlines[index][2];
 267
 268         if (vlines[index][0] != DiffMap::GHOST_MAP_ENTRY &&
 269             vlines[index][1] != DiffMap::GHOST_MAP_ENTRY &&
 270             vlines[index][2] == DiffMap::GHOST_MAP_ENTRY)
 271         {
 272                 String strLine0(m_ptBuf[0]->GetLineChars(line0), m_ptBuf[0]->GetFullLineLength(line0));
 273                 String strLine1(m_ptBuf[1]->GetLineChars(line1), m_ptBuf[1]->GetFullLineLength(line1));
 274                 if (strdiff::Compare(strLine0, strLine1,
 275                         !diffOptions.bIgnoreCase, !diffOptions.bIgnoreEol,
 276                         diffOptions.nIgnoreWhitespace, diffOptions.bIgnoreNumbers) == 0)
 277                         return OP_3RDONLY;
 278                 return OP_DIFF;
 279         }
 280         else if (vlines[index][0] != DiffMap::GHOST_MAP_ENTRY &&
 281                  vlines[index][1] == DiffMap::GHOST_MAP_ENTRY &&
 282                  vlines[index][2] != DiffMap::GHOST_MAP_ENTRY)
 283         {
 284                 String strLine0(m_ptBuf[0]->GetLineChars(line0), m_ptBuf[0]->GetFullLineLength(line0));
 285                 String strLine2(m_ptBuf[2]->GetLineChars(line2), m_ptBuf[2]->GetFullLineLength(line2));
 286                 if (strdiff::Compare(strLine0, strLine2,
 287                         !diffOptions.bIgnoreCase, !diffOptions.bIgnoreEol,
 288                         diffOptions.nIgnoreWhitespace, diffOptions.bIgnoreNumbers) == 0)
 289                         return OP_2NDONLY;
 290                 return OP_DIFF;
 291         }
 292         else if (vlines[index][0] == DiffMap::GHOST_MAP_ENTRY &&
 293                  vlines[index][1] != DiffMap::GHOST_MAP_ENTRY &&
 294                  vlines[index][2] != DiffMap::GHOST_MAP_ENTRY)
 295         {
 296                 String strLine1(m_ptBuf[1]->GetLineChars(line1), m_ptBuf[1]->GetFullLineLength(line1));
 297                 String strLine2(m_ptBuf[2]->GetLineChars(line2), m_ptBuf[2]->GetFullLineLength(line2));
 298                 if (strdiff::Compare(strLine1, strLine2,
 299                         !diffOptions.bIgnoreCase, !diffOptions.bIgnoreEol,
 300                         diffOptions.nIgnoreWhitespace, diffOptions.bIgnoreNumbers) == 0)
 301                         return OP_1STONLY;
 302                 return OP_DIFF;
 303         }
 304         else
 305         {
 306                 String strLine0(m_ptBuf[0]->GetLineChars(line0), m_ptBuf[0]->GetFullLineLength(line0));
 307                 String strLine1(m_ptBuf[1]->GetLineChars(line1), m_ptBuf[1]->GetFullLineLength(line1));
 308                 String strLine2(m_ptBuf[2]->GetLineChars(line2), m_ptBuf[2]->GetFullLineLength(line2));
 309                 if (strdiff::Compare(strLine0, strLine1,
 310                         !diffOptions.bIgnoreCase, !diffOptions.bIgnoreEol,
 311                         diffOptions.nIgnoreWhitespace, diffOptions.bIgnoreNumbers) == 0)
 312                         return OP_3RDONLY;
 313                 if (strdiff::Compare(strLine0, strLine2,
 314                         !diffOptions.bIgnoreCase, !diffOptions.bIgnoreEol,
 315                         diffOptions.nIgnoreWhitespace, diffOptions.bIgnoreNumbers) == 0)
 316                         return OP_2NDONLY;
 317                 if (strdiff::Compare(strLine1, strLine2,
 318                         !diffOptions.bIgnoreCase, !diffOptions.bIgnoreEol,
 319                         diffOptions.nIgnoreWhitespace, diffOptions.bIgnoreNumbers) == 0)
 320                         return OP_1STONLY;
 321                 return OP_DIFF;
 322         }
 323 }
 324
 325 /**
 326  * @brief Divide diff blocks to match lines in diff blocks.
 327  */
 328 void CMergeDoc::AdjustDiffBlocks()
 329 {
 330         int nDiff;
 331         int nDiffCount = m_diffList.GetSize();
 332
 333         // Go through and do our best to line up lines within each diff block
 334         // between left side and right side
 335         DiffList newDiffList;
 336         newDiffList.Clear();
 337         for (nDiff = 0; nDiff < nDiffCount; nDiff++)
 338         {
 339                 const DIFFRANGE & diffrange = *m_diffList.DiffRangeAt(nDiff);
 340                 // size map correctly (it will hold one entry for each left-side line
 341                 int nlines0 = diffrange.end[0] - diffrange.begin[0] + 1;
 342                 int nlines1 = diffrange.end[1] - diffrange.begin[1] + 1;
 343                 if (nlines0>0 && nlines1>0)
 344                 {
 345                         // Call worker to do all lines in block
 346                         int lo0 = 0, hi0 = nlines0-1;
 347                         int lo1 = 0, hi1 = nlines1-1;
 348                         const std::vector<WordDiff> worddiffs = GetWordDiffArrayInRange(diffrange.begin, diffrange.end);
 349 #ifdef _DEBUG
 350                         PrintWordDiffList(2, worddiffs);
 351 #endif
 352                         DiffMap diffmap;
 353                         diffmap.InitDiffMap(nlines0);
 354                         AdjustDiffBlock(diffmap, diffrange, worddiffs, 0, 1, lo0, hi0, lo1, hi1);
 355                         ValidateDiffMap(diffmap);
 356                         std::vector<std::array<int, 2>> vlines = CreateVirtualLineToRealLineMap(diffmap, nlines0, nlines1);
 357
 358                         // divide diff blocks
 359                         int line0 = 0, line1 = 0;
 360                         for (size_t i = 0; i < vlines.size();)
 361                         {
 362                                 DIFFRANGE dr;
 363                                 size_t ib = i;
 364                                 if ((vlines[i][0] != DiffMap::GHOST_MAP_ENTRY) &&
 365                                         (vlines[i][1] != DiffMap::GHOST_MAP_ENTRY))
 366                                 {
 367                                         while (i < vlines.size() &&
 368                                                 (vlines[i][0] != DiffMap::GHOST_MAP_ENTRY) &&
 369                                                 (vlines[i][1] != DiffMap::GHOST_MAP_ENTRY))
 370                                         {
 371                                                 line0++;
 372                                                 line1++;
 373                                                 i++;
 374                                         }
 375                                         dr.begin[0]  = diffrange.begin[0] + vlines[ib][0];
 376                                         dr.begin[1]  = diffrange.begin[1] + vlines[ib][1];
 377                                         dr.end[0]    = diffrange.begin[0] + vlines[i - 1][0];
 378                                         dr.end[1]    = diffrange.begin[1] + vlines[i - 1][1];
 379                                         dr.blank[0]  = dr.blank[1] = -1;
 380                                         dr.op        = diffrange.op;
 381                                         newDiffList.AddDiff(dr);
 382                                 }
 383                                 else if ((vlines[i][0] == DiffMap::GHOST_MAP_ENTRY) &&
 384                                          (vlines[i][1] != DiffMap::GHOST_MAP_ENTRY))
 385                                 {
 386                                         while (i < vlines.size() &&
 387                                              (vlines[i][0] == DiffMap::GHOST_MAP_ENTRY) &&
 388                                              (vlines[i][1] != DiffMap::GHOST_MAP_ENTRY))
 389                                         {
 390                                                 line1++;
 391                                                 i++;
 392                                         }
 393                                         dr.begin[0]  = diffrange.begin[0] + line0;
 394                                         dr.begin[1]  = diffrange.begin[1] + vlines[ib][1];
 395                                         dr.end[0]    = diffrange.begin[0] + line0 - 1;
 396                                         dr.end[1]    = diffrange.begin[1] + vlines[i - 1][1];
 397                                         dr.blank[0]  = dr.blank[1] = -1;
 398                                         dr.op        = diffrange.op;
 399                                         newDiffList.AddDiff(dr);
 400                                 }
 401                                 else if ((vlines[i][0] != DiffMap::GHOST_MAP_ENTRY) &&
 402                                          (vlines[i][1] == DiffMap::GHOST_MAP_ENTRY))
 403                                 {
 404                                         while (i < vlines.size() &&
 405                                              (vlines[i][0] != DiffMap::GHOST_MAP_ENTRY) &&
 406                                              (vlines[i][1] == DiffMap::GHOST_MAP_ENTRY))
 407                                         {
 408                                                 line0++;
 409                                                 i++;
 410                                         }
 411                                         dr.begin[0]  = diffrange.begin[0] + vlines[ib][0];
 412                                         dr.begin[1]  = diffrange.begin[1] + line1;
 413                                         dr.end[0]    = diffrange.begin[0] + vlines[i - 1][0];
 414                                         dr.end[1]    = diffrange.begin[1] + line1 - 1;
 415                                         dr.blank[0]  = dr.blank[1] = -1;
 416                                         dr.op        = diffrange.op;
 417                                         newDiffList.AddDiff(dr);
 418                                 }
 419                                 else
 420                                 {
 421                                         assert(0);
 422                                 }
 423                         }
 424                 }
 425                 else
 426                 {
 427                         newDiffList.AddDiff(diffrange);
 428                 }
 429         }
 430
 431         // recreate m_diffList
 432         m_diffList.Clear();
 433         nDiffCount = newDiffList.GetSize();
 434         for (nDiff = 0; nDiff < nDiffCount; nDiff++)
 435                 m_diffList.AddDiff(*newDiffList.DiffRangeAt(nDiff));
 436 }
 437
 438 /**
 439  * @brief Divide diff blocks to match lines in diff blocks. (3-way)
 440  */
 441 void CMergeDoc::AdjustDiffBlocks3way()
 442 {
 443         int nDiff;
 444         int nDiffCount = m_diffList.GetSize();
 445
 446         // Go through and do our best to line up lines within each diff block
 447         // between left side and right side
 448         DiffList newDiffList;
 449         newDiffList.Clear();
 450         for (nDiff = 0; nDiff < nDiffCount; nDiff++)
 451         {
 452                 const DIFFRANGE & diffrange = *m_diffList.DiffRangeAt(nDiff);
 453                 // size map correctly (it will hold one entry for each left-side line
 454                 int nlines0 = diffrange.end[0] - diffrange.begin[0] + 1;
 455                 int nlines1 = diffrange.end[1] - diffrange.begin[1] + 1;
 456                 int nlines2 = diffrange.end[2] - diffrange.begin[2] + 1;
 457                 if ((nlines0 > 0) + (nlines1 > 0) + (nlines2 > 0) > 1)
 458                 {
 459                         // Call worker to do all lines in block
 460                         int lo0 = 0, hi0 = nlines0 - 1;
 461                         int lo1 = 0, hi1 = nlines1 - 1;
 462                         int lo2 = 0, hi2 = nlines2 - 1;
 463                         const std::vector<WordDiff> worddiffs01 = GetWordDiffArrayInRange(diffrange.begin, diffrange.end, 0, 1);
 464                         const std::vector<WordDiff> worddiffs12 = GetWordDiffArrayInRange(diffrange.begin, diffrange.end, 1, 2);
 465                         const std::vector<WordDiff> worddiffs20 = GetWordDiffArrayInRange(diffrange.begin, diffrange.end, 2, 0);
 466                         DiffMap diffmap01, diffmap12, diffmap20;
 467                         diffmap01.InitDiffMap(nlines0);
 468                         diffmap12.InitDiffMap(nlines1);
 469                         diffmap20.InitDiffMap(nlines2);
 470                         AdjustDiffBlock(diffmap01, diffrange, worddiffs01, 0, 1, lo0, hi0, lo1, hi1);
 471                         AdjustDiffBlock(diffmap12, diffrange, worddiffs12, 1, 2, lo1, hi1, lo2, hi2);
 472                         AdjustDiffBlock(diffmap20, diffrange, worddiffs20, 2, 0, lo2, hi2, lo0, hi0);
 473                         ValidateDiffMap(diffmap01);
 474                         ValidateDiffMap(diffmap12);
 475                         ValidateDiffMap(diffmap20);
 476                         std::vector<std::array<int, 3>> vlines = CreateVirtualLineToRealLineMap3way(diffmap01, diffmap12, diffmap20, nlines0, nlines1, nlines2);
 477
 478                         DIFFOPTIONS diffOptions = {0};
 479                         m_diffWrapper.GetOptions(&diffOptions);
 480                         std::vector<OP_TYPE> opary(vlines.size());
 481                         for (size_t i = 0; i < vlines.size(); ++i)
 482                                 opary[i] = (diffrange.op == OP_TRIVIAL) ?
 483                                         OP_TRIVIAL :
 484                                         ComputeOpType3way(vlines, i, diffrange, diffOptions);
 485                         // divide diff blocks
 486                         int line0 = 0, line1 = 0, line2 = 0;
 487                         for (size_t i = 0; i < vlines.size();)
 488                         {
 489                                 DIFFRANGE dr;
 490                                 size_t ib = i;
 491                                 OP_TYPE op = opary[i];
 492                                 if ((vlines[i][0] != DiffMap::GHOST_MAP_ENTRY) &&
 493                                         (vlines[i][1] != DiffMap::GHOST_MAP_ENTRY) &&
 494                                         (vlines[i][2] != DiffMap::GHOST_MAP_ENTRY))
 495                                 {
 496                                         while (i < vlines.size() &&
 497                                                 (vlines[i][0] != DiffMap::GHOST_MAP_ENTRY) &&
 498                                                 (vlines[i][1] != DiffMap::GHOST_MAP_ENTRY) &&
 499                                                 (vlines[i][2] != DiffMap::GHOST_MAP_ENTRY) &&
 500                                                 op == opary[i])
 501                                         {
 502                                                 line0++;
 503                                                 line1++;
 504                                                 line2++;
 505                                                 i++;
 506                                         }
 507                                         dr.begin[0]  = diffrange.begin[0] + vlines[ib][0];
 508                                         dr.begin[1]  = diffrange.begin[1] + vlines[ib][1];
 509                                         dr.begin[2]  = diffrange.begin[2] + vlines[ib][2];
 510                                         dr.end[0]    = diffrange.begin[0] + vlines[i - 1][0];
 511                                         dr.end[1]    = diffrange.begin[1] + vlines[i - 1][1];
 512                                         dr.end[2]    = diffrange.begin[2] + vlines[i - 1][2];
 513                                         dr.blank[0]  = dr.blank[1] = dr.blank[2] = -1;
 514                                         dr.op        = op;
 515                                         newDiffList.AddDiff(dr);
 516                                 }
 517                                 else if ((vlines[i][0] == DiffMap::GHOST_MAP_ENTRY) &&
 518                                          (vlines[i][1] != DiffMap::GHOST_MAP_ENTRY) &&
 519                                          (vlines[i][2] != DiffMap::GHOST_MAP_ENTRY))
 520                                 {
 521                                         while (i < vlines.size() &&
 522                                              (vlines[i][0] == DiffMap::GHOST_MAP_ENTRY) &&
 523                                              (vlines[i][1] != DiffMap::GHOST_MAP_ENTRY) &&
 524                                              (vlines[i][2] != DiffMap::GHOST_MAP_ENTRY) &&
 525                                                  op == opary[i])
 526                                         {
 527                                                 line1++;
 528                                                 line2++;
 529                                                 i++;
 530                                         }
 531                                         dr.begin[0]  = diffrange.begin[0] + line0;
 532                                         dr.begin[1]  = diffrange.begin[1] + vlines[ib][1];
 533                                         dr.begin[2]  = diffrange.begin[2] + vlines[ib][2];
 534                                         dr.end[0]    = diffrange.begin[0] + line0 - 1;
 535                                         dr.end[1]    = diffrange.begin[1] + vlines[i - 1][1];
 536                                         dr.end[2]    = diffrange.begin[2] + vlines[i - 1][2];
 537                                         dr.blank[0]  = dr.blank[1] = dr.blank[2] = -1;
 538                                         dr.op        = op;
 539                                         newDiffList.AddDiff(dr);
 540                                 }
 541                                 else if ((vlines[i][0] != DiffMap::GHOST_MAP_ENTRY) &&
 542                                          (vlines[i][1] == DiffMap::GHOST_MAP_ENTRY) &&
 543                                          (vlines[i][2] != DiffMap::GHOST_MAP_ENTRY))
 544                                 {
 545                                         while (i < vlines.size() &&
 546                                              (vlines[i][0] != DiffMap::GHOST_MAP_ENTRY) &&
 547                                              (vlines[i][1] == DiffMap::GHOST_MAP_ENTRY) &&
 548                                              (vlines[i][2] != DiffMap::GHOST_MAP_ENTRY) &&
 549                                                  op == opary[i])
 550                                         {
 551                                                 line0++;
 552                                                 line2++;
 553                                                 i++;
 554                                         }
 555                                         dr.begin[0]  = diffrange.begin[0] + vlines[ib][0];
 556                                         dr.begin[1]  = diffrange.begin[1] + line1;
 557                                         dr.begin[2]  = diffrange.begin[2] + vlines[ib][2];
 558                                         dr.end[0]    = diffrange.begin[0] + vlines[i - 1][0];
 559                                         dr.end[1]    = diffrange.begin[1] + line1 - 1;
 560                                         dr.end[2]    = diffrange.begin[2] + vlines[i - 1][2];
 561                                         dr.blank[0]  = dr.blank[1] = dr.blank[2] = -1;
 562                                         dr.op        = op;
 563                                         newDiffList.AddDiff(dr);
 564                                 }
 565                                 else if ((vlines[i][0] != DiffMap::GHOST_MAP_ENTRY) &&
 566                                          (vlines[i][1] != DiffMap::GHOST_MAP_ENTRY) &&
 567                                          (vlines[i][2] == DiffMap::GHOST_MAP_ENTRY))
 568                                 {
 569                                         while (i < vlines.size() &&
 570                                              (vlines[i][0] != DiffMap::GHOST_MAP_ENTRY) &&
 571                                              (vlines[i][1] != DiffMap::GHOST_MAP_ENTRY) &&
 572                                              (vlines[i][2] == DiffMap::GHOST_MAP_ENTRY) &&
 573                                                  op == opary[i])
 574                                         {
 575                                                 line0++;
 576                                                 line1++;
 577                                                 i++;
 578                                         }
 579                                         dr.begin[0]  = diffrange.begin[0] + vlines[ib][0];
 580                                         dr.begin[1]  = diffrange.begin[1] + vlines[ib][1];
 581                                         dr.begin[2]  = diffrange.begin[2] + line2;
 582                                         dr.end[0]    = diffrange.begin[0] + vlines[i - 1][0];
 583                                         dr.end[1]    = diffrange.begin[1] + vlines[i - 1][1];
 584                                         dr.end[2]    = diffrange.begin[2] + line2 - 1;
 585                                         dr.blank[0]  = dr.blank[1] = dr.blank[2] = -1;
 586                                         dr.op        = op;
 587                                         newDiffList.AddDiff(dr);
 588                                 }
 589                                 else if ((vlines[i][0] != DiffMap::GHOST_MAP_ENTRY) &&
 590                                          (vlines[i][1] == DiffMap::GHOST_MAP_ENTRY) &&
 591                                          (vlines[i][2] == DiffMap::GHOST_MAP_ENTRY))
 592                                 {
 593                                         while (i < vlines.size() &&
 594                                              (vlines[i][0] != DiffMap::GHOST_MAP_ENTRY) &&
 595                                              (vlines[i][1] == DiffMap::GHOST_MAP_ENTRY) &&
 596                                          (vlines[i][2] == DiffMap::GHOST_MAP_ENTRY) &&
 597                                                  op == opary[i])
 598                                         {
 599                                                 line0++;
 600                                                 i++;
 601                                         }
 602                                         dr.begin[0]  = diffrange.begin[0] + vlines[ib][0];
 603                                         dr.begin[1]  = diffrange.begin[1] + line1;
 604                                         dr.begin[2]  = diffrange.begin[2] + line2;
 605                                         dr.end[0]    = diffrange.begin[0] + vlines[i - 1][0];
 606                                         dr.end[1]    = diffrange.begin[1] + line1 - 1;
 607                                         dr.end[2]    = diffrange.begin[2] + line2 - 1;
 608                                         dr.blank[0]  = dr.blank[1] = dr.blank[2] = -1;
 609                                         dr.op        = op;
 610                                         newDiffList.AddDiff(dr);
 611                                 }
 612                                 else if ((vlines[i][0] == DiffMap::GHOST_MAP_ENTRY) &&
 613                                          (vlines[i][1] != DiffMap::GHOST_MAP_ENTRY) &&
 614                                          (vlines[i][2] == DiffMap::GHOST_MAP_ENTRY))
 615                                 {
 616                                         while (i < vlines.size() &&
 617                                              (vlines[i][0] == DiffMap::GHOST_MAP_ENTRY) &&
 618                                              (vlines[i][1] != DiffMap::GHOST_MAP_ENTRY) &&
 619                                              (vlines[i][2] == DiffMap::GHOST_MAP_ENTRY) &&
 620                                                  op == opary[i])
 621                                         {
 622                                                 line1++;
 623                                                 i++;
 624                                         }
 625                                         dr.begin[0]  = diffrange.begin[0] + line0;
 626                                         dr.begin[1]  = diffrange.begin[1] + vlines[ib][1];
 627                                         dr.begin[2]  = diffrange.begin[2] + line2;
 628                                         dr.end[0]    = diffrange.begin[0] + line0 - 1;
 629                                         dr.end[1]    = diffrange.begin[1] + vlines[i - 1][1];
 630                                         dr.end[2]    = diffrange.begin[2] + line2 - 1;
 631                                         dr.blank[0]  = dr.blank[1] = dr.blank[2] = -1;
 632                                         dr.op        = op;
 633                                         newDiffList.AddDiff(dr);
 634                                 }
 635                                 else if ((vlines[i][0] == DiffMap::GHOST_MAP_ENTRY) &&
 636                                          (vlines[i][1] == DiffMap::GHOST_MAP_ENTRY) &&
 637                                          (vlines[i][2] != DiffMap::GHOST_MAP_ENTRY))
 638                                 {
 639                                         while (i < vlines.size() &&
 640                                              (vlines[i][0] == DiffMap::GHOST_MAP_ENTRY) &&
 641                                              (vlines[i][1] == DiffMap::GHOST_MAP_ENTRY) &&
 642                                              (vlines[i][2] != DiffMap::GHOST_MAP_ENTRY) &&
 643                                                  op == opary[i])
 644                                         {
 645                                                 line2++;
 646                                                 i++;
 647                                         }
 648                                         dr.begin[0]  = diffrange.begin[0] + line0;
 649                                         dr.begin[1]  = diffrange.begin[1] + line1;
 650                                         dr.begin[2]  = diffrange.begin[2] + vlines[ib][2];
 651                                         dr.end[0]    = diffrange.begin[0] + line0 - 1;
 652                                         dr.end[1]    = diffrange.begin[1] + line1 - 1;
 653                                         dr.end[2]    = diffrange.begin[2] + vlines[i - 1][2];
 654                                         dr.blank[0]  = dr.blank[1] = dr.blank[2] = -1;
 655                                         dr.op        = op;
 656                                         newDiffList.AddDiff(dr);
 657                                 }
 658                                 else
 659                                 {
 660                                         assert(0);
 661                                 }
 662                         }
 663                 }
 664                 else
 665                 {
 666                         newDiffList.AddDiff(diffrange);
 667                 }
 668         }
 669
 670         // recreate m_diffList
 671         m_diffList.Clear();
 672         nDiffCount = newDiffList.GetSize();
 673         for (nDiff = 0; nDiff < nDiffCount; nDiff++)
 674                 m_diffList.AddDiff(*newDiffList.DiffRangeAt(nDiff));
 675 }
 676
 677 /**
 678  * @brief Return cost of making strings equal
 679  *
 680  * The cost of making them equal is the measure of their dissimilarity
 681  * which is their Levenshtein distance.
 682  */
 683 int CMergeDoc::GetMatchCost(const DIFFRANGE& dr, int i0, int i1, int line0, int line1, const std::vector<WordDiff>& worddiffs)
 684 {
 685         int matchlen = 0;
 686         WordDiff dummyWordDiff(0, 0, dr.begin[0], dr.begin[0], 0, 0, dr.begin[1], dr.begin[1]);
 687         WordDiff& prevWordDiff = dummyWordDiff;
 688         for (size_t i = 0; i < worddiffs.size(); ++i)
 689         {
 690                 if ((prevWordDiff.endline[0] <= line0 && line0 <= worddiffs[i].beginline[0]) &&
 691                     (prevWordDiff.endline[1] <= line1 && line1 <= worddiffs[i].beginline[1]) &&
 692                         (line0 - prevWordDiff.endline[0] == line1 - prevWordDiff.endline[1]))
 693                 {
 694                         if (line0 == worddiffs[i].beginline[0])
 695                         {
 696                                 matchlen += worddiffs[i].begin[0] - ((prevWordDiff.endline[0] == line0) ? prevWordDiff.end[0] : 0);
 697                         }
 698                         else /* line0 < worddiffs[i].beginline[0] */
 699                         {
 700                                 matchlen += m_ptBuf[i0]->GetFullLineLength(line0) - ((prevWordDiff.endline[0] == line0) ? prevWordDiff.end[0] : 0);
 701                         }
 702                 }
 703                 prevWordDiff = worddiffs[i];
 704         }
 705         if (worddiffs.empty())
 706         {
 707                 if (line0 - dr.begin[i0] == line1 - dr.begin[i1])
 708                         matchlen += m_ptBuf[i0]->GetFullLineLength(line0);
 709         }
 710         else
 711         {
 712                 if (prevWordDiff.endline[0] <= line0 && prevWordDiff.endline[1] <= line1 &&
 713                     (line0 - prevWordDiff.endline[0] == line1 - prevWordDiff.endline[1]))
 714                 {
 715                         matchlen += m_ptBuf[i0]->GetFullLineLength(line0) - ((prevWordDiff.endline[0] == line0) ? prevWordDiff.end[0] : 0);
 716                 }
 717         }
 718 /*
 719 #ifdef _DEBUG
 720         String str = strutils::format(_T("pane%d,%d line%5d,%5d match len: %d\n"), i0, i1, line0, line1, matchlen);
 721         OutputDebugString(str.c_str());
 722 #endif
 723 */
 724         return -matchlen;
 725 }
 726
 727 /**
 728  * @brief Map lines from left to right for specified range in diff block, as best we can
 729  * Map left side range [lo0;hi0] to right side range [lo1;hi1]
 730  * (ranges include ends)
 731  *
 732  * Algorithm:
 733  * Find best match, and use that to split problem into two parts (above & below match)
 734  * and call ourselves recursively to solve each smaller problem
 735  */
 736 void CMergeDoc::AdjustDiffBlock(DiffMap & diffMap, const DIFFRANGE & diffrange, const std::vector<WordDiff>& worddiffs, int i0, int i1, int lo0, int hi0, int lo1, int hi1)
 737 {
 738         // Map & lo & hi numbers are all relative to this block
 739         // We need to know offsets to find actual line strings from buffer
 740         int offset0 = diffrange.begin[i0];
 741         int offset1 = diffrange.begin[i1];
 742
 743         // # of lines on left and right
 744         int lines0 = hi0 - lo0 + 1;
 745         int lines1 = hi1 - lo1 + 1;
 746
 747         // shortcut special case
 748         if (lines0 == 0)
 749         {
 750                 return;
 751         }
 752         if (lines1 == 0)
 753         {
 754                 for (int w=0; w<lines0; ++w)
 755                         diffMap.m_map[w] = DiffMap::GHOST_MAP_ENTRY;
 756                 return;
 757         }
 758         if (lines0 == 1 && lines1 == 1)
 759         {
 760                 diffMap.m_map[lo0] = hi1;
 761                 return;
 762         }
 763
 764         // Bail out if range is large
 765         auto tooManyCharacters = [&](int pane, int start, int end)
 766         {
 767                 size_t charCount = 0;
 768                 const int charCountMax = 4096;
 769                 for (int i = start; i <= end; ++i)
 770                 {
 771                         charCount += m_ptBuf[pane]->GetLineLength(i);
 772                         if (charCount > charCountMax)
 773                                 return true;
 774                 }
 775                 return false;
 776         };
 777         if (tooManyCharacters(i0, offset0 + lo0, offset0 + hi0) || tooManyCharacters(i1, offset1 + lo1, offset1 + hi1))
 778         {
 779                 // Do simple 1:1 mapping
 780                 // but try to stay within original block
 781                 // Cannot be outside both sides, so just test for outside one side
 782                 int tlo=0, thi=0;
 783                 if (lo1 < 0)
 784                 {
 785                         // right side is off the bottom
 786                         // so put it as close to bottom as possible
 787                         tlo = hi1 - (hi0-lo0);
 788                         thi = hi1;
 789                 }
 790                 else
 791                 {
 792                         // put it as close to top as possible
 793                         tlo = lo1;
 794                         thi = lo1 + (hi0-lo0);
 795                 }
 796
 797                 for (int w=0; w<lines0; ++w)
 798                 {
 799                         if (w < lines1)
 800                                 diffMap.m_map[w] = w + tlo;
 801                         else
 802                                 diffMap.m_map[w] = DiffMap::GHOST_MAP_ENTRY;
 803                 }
 804                 return;
 805         }
 806
 807         // Find best fit
 808         int ibest=-1, isavings=0x7fffffff, itarget=-1;
 809         for (int i=lo0; i<=hi0; ++i)
 810         {
 811                 for (int j=lo1; j<=hi1; ++j)
 812                 {
 813                         int savings = GetMatchCost(diffrange, i0, i1, offset0 + i, offset1 + j, worddiffs);
 814                         // TODO
 815                         // Need to penalize assignments that push us outside the box
 816                         // further than is required
 817                         if (savings < isavings)
 818                         {
 819                                 ibest = i;
 820                                 itarget = j;
 821                                 isavings = savings;
 822                         }
 823                 }
 824         }
 825         // I think we have to find at least one
 826         // because cost (Levenshtein distance) is less than or equal to maxlen
 827         // so cost is always nonnegative
 828         ASSERT(ibest >= 0);
 829
 830         ASSERT(diffMap.m_map[ibest] == DiffMap::BAD_MAP_ENTRY);
 831
 832         diffMap.m_map[ibest] = itarget;
 833
 834         // Half of the remaining problem is below our match
 835         if (lo0 < ibest)
 836         {
 837                 if (lo1 < itarget)
 838                 {
 839                         AdjustDiffBlock(diffMap, diffrange, worddiffs, i0, i1, lo0, ibest-1, lo1, itarget-1);
 840                 }
 841                 else
 842                 {
 843                         // No target space for the ones below our match
 844                         for (int x = lo0; x < ibest; ++x)
 845                         {
 846                                 diffMap.m_map[x] = DiffMap::GHOST_MAP_ENTRY;
 847                         }
 848                 }
 849         }
 850
 851         // Half of the remaining problem is above our match
 852         if (hi0 > ibest)
 853         {
 854                 if (itarget < hi1)
 855                 {
 856                         AdjustDiffBlock(diffMap, diffrange, worddiffs, i0, i1, ibest + 1, hi0,
 857                                         itarget + 1, hi1);
 858                 }
 859                 else
 860                 {
 861                         // No target space for the ones above our match
 862                         for (int x = ibest + 1; x <= hi0; ++x)
 863                         {
 864                                 diffMap.m_map[x] = DiffMap::GHOST_MAP_ENTRY;
 865                         }
 866                 }
 867         }
 868 }