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