Src/DiffList.cpp

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /**
   3  * @file  DiffList.cpp
   4  *
   5  * @brief Implementation file for DiffList class
   6  */
   7
   8 #include "pch.h"
   9 #include "DiffList.h"
  10 #include <cassert>
  11 #include <string>
  12 #include <sstream>
  13 #include <algorithm>
  14
  15 using std::swap;
  16 using std::vector;
  17
  18 /**
  19  * @brief Swap diff sides.
  20  */
  21 void DIFFRANGE::swap_sides(int index1, int index2)
  22 {
  23         swap(begin[index1], begin[index2]);
  24         swap(end[index1], end[index2]);
  25         swap(blank[index1], blank[index2]);
  26 }
  27
  28 /**
  29  * @brief Initialize DiffMap.
  30  * @param [in] nlines Lines to add to the list.
  31  */
  32 void DiffMap::InitDiffMap(int nlines)
  33 {
  34         // sentry value so we can check later that we set them all
  35         m_map.assign(nlines, BAD_MAP_ENTRY);
  36 }
  37
  38
  39 /**
  40  * @brief Default constructor, initialises difflist to 64 items.
  41  */
  42 DiffList::DiffList()
  43 : m_firstSignificant(-1)
  44 , m_lastSignificant(-1)
  45 , m_firstSignificantLeftMiddle(-1)
  46 , m_firstSignificantLeftRight(-1)
  47 , m_firstSignificantMiddleRight(-1)
  48 , m_firstSignificantLeftOnly(-1)
  49 , m_firstSignificantMiddleOnly(-1)
  50 , m_firstSignificantRightOnly(-1)
  51 , m_firstSignificantConflict(-1)
  52 , m_lastSignificantLeftMiddle(-1)
  53 , m_lastSignificantLeftRight(-1)
  54 , m_lastSignificantMiddleRight(-1)
  55 , m_lastSignificantLeftOnly(-1)
  56 , m_lastSignificantMiddleOnly(-1)
  57 , m_lastSignificantRightOnly(-1)
  58 , m_lastSignificantConflict(-1)
  59 {
  60         m_diffs.reserve(64); // Reserve some initial space to avoid allocations.
  61 }
  62
  63 /**
  64  * @brief Removes all diffs from list.
  65  */
  66 void DiffList::Clear()
  67 {
  68         m_diffs.clear();
  69         m_firstSignificant = -1;
  70         m_lastSignificant = -1;
  71         m_firstSignificantLeftMiddle = -1;
  72         m_firstSignificantLeftRight = -1;
  73         m_firstSignificantMiddleRight = -1;
  74         m_firstSignificantLeftOnly = -1;
  75         m_firstSignificantMiddleOnly = -1;
  76         m_firstSignificantRightOnly = -1;
  77         m_firstSignificantConflict = -1;
  78         m_lastSignificantLeftMiddle = -1;
  79         m_lastSignificantLeftRight = -1;
  80         m_lastSignificantMiddleRight = -1;
  81         m_lastSignificantLeftOnly = -1;
  82         m_lastSignificantMiddleOnly = -1;
  83         m_lastSignificantRightOnly = -1;
  84         m_lastSignificantConflict = -1;
  85 }
  86
  87 /**
  88  * @brief Returns count of significant diffs in the list.
  89  * This function returns total count of significant diffs in list. So returned
  90  * count doesn't include non-significant diffs.
  91  * @return Count of significant differences.
  92  */
  93 int DiffList::GetSignificantDiffs() const
  94 {
  95         int nSignificants = 0;
  96         const int nDiffCount = (int) m_diffs.size();
  97
  98         for (int i = 0; i < nDiffCount; i++)
  99         {
 100                 const DIFFRANGE * dfi = DiffRangeAt(i);
 101                 if (dfi->op != OP_TRIVIAL)
 102                 {
 103                         ++nSignificants;
 104                 }
 105         }
 106         return nSignificants;
 107 }
 108
 109 /**
 110  * @brief Adds given diff to end of the list.
 111  * Adds given difference to end of the list (append).
 112  * @param [in] di Difference to add.
 113  */
 114 void DiffList::AddDiff(const DIFFRANGE & di)
 115 {
 116         DiffRangeInfo dri(di);
 117
 118         // Allocate memory for new items exponentially
 119         if (m_diffs.size() == m_diffs.capacity())
 120                 m_diffs.reserve(m_diffs.size() * 2);
 121         m_diffs.push_back(dri);
 122 }
 123
 124 /**
 125  * @brief Checks if diff in given list index is significant or not.
 126  * @param [in] nDiff Index of DIFFRANGE to check.
 127  * @return true if diff is significant, false if not.
 128  */
 129 bool DiffList::IsDiffSignificant(int nDiff) const
 130 {
 131         const DIFFRANGE * dfi = DiffRangeAt(nDiff);
 132         if (dfi->op != OP_TRIVIAL)
 133                 return true;
 134         else
 135                 return false;
 136 }
 137
 138 /**
 139  * @brief Get significant difference index of the diff.
 140  * This function returns the index of diff when only significant differences
 141  * are calculated.
 142  * @param [in] nDiff Index of difference to check.
 143  * @return Significant difference index of the diff.
 144  */
 145 int DiffList::GetSignificantIndex(int nDiff) const
 146 {
 147         int significants = -1;
 148
 149         for (int i = 0; i <= nDiff; i++)
 150         {
 151                 const DIFFRANGE * dfi = DiffRangeAt(i);
 152                 if (dfi->op != OP_TRIVIAL)
 153                 {
 154                         ++significants;
 155                 }
 156         }
 157         return significants;
 158 }
 159
 160 /**
 161  * @brief Returns copy of DIFFRANGE from diff-list.
 162  * @param [in] nDiff Index of DIFFRANGE to return.
 163  * @param [out] di DIFFRANGE returned (empty if error)
 164  * @return true if DIFFRANGE found from given index.
 165  */
 166 bool DiffList::GetDiff(int nDiff, DIFFRANGE & di) const
 167 {
 168         const DIFFRANGE * dfi = DiffRangeAt(nDiff);
 169         if (dfi == nullptr)
 170         {
 171                 DIFFRANGE empty;
 172                 di = empty;
 173                 return false;
 174         }
 175         di = *dfi;
 176         return true;
 177 }
 178
 179 /**
 180  * @brief Return constant pointer to requested diff.
 181  * This function returns constant pointer to DIFFRANGE at given index.
 182  * @param [in] nDiff Index of DIFFRANGE to return.
 183  * @return Constant pointer to DIFFRANGE.
 184  */
 185 const DIFFRANGE * DiffList::DiffRangeAt(int nDiff) const
 186 {
 187         if (nDiff >= 0 && nDiff < (int) m_diffs.size())
 188         {
 189                 return &m_diffs[nDiff];
 190         }
 191         else
 192         {
 193                 assert(false);
 194                 return nullptr;
 195         }
 196 }
 197
 198 /**
 199  * @brief Replaces diff in list in given index with given diff.
 200  * @param [in] nDiff Index (0-based) of diff to be replaced
 201  * @param [in] di Diff to put in list.
 202  * @return true if index was valid and diff put to list.
 203  */
 204 bool DiffList::SetDiff(int nDiff, const DIFFRANGE & di)
 205 {
 206         if (nDiff < (int) m_diffs.size())
 207         {
 208                 m_diffs[nDiff] = DiffRangeInfo(di);
 209                 return true;
 210         }
 211         else
 212                 return false;
 213 }
 214
 215 /**
 216  * @brief Checks if line is before, inside or after diff
 217  * @param [in] nLine Linenumber to text buffer (not "real" number)
 218  * @param [in] nDiff Index to diff table
 219  * @return -1 if line is before diff, 0 if line is in diff and
 220  * 1 if line is after diff.
 221  */
 222 int DiffList::LineRelDiff(int nLine, int nDiff) const
 223 {
 224         const DIFFRANGE * dfi = DiffRangeAt(nDiff);
 225         if (static_cast<int>(nLine) < dfi->dbegin)
 226                 return -1;
 227         else if (static_cast<int>(nLine) > dfi->dend)
 228                 return 1;
 229         else
 230                 return 0;
 231 }
 232
 233 /**
 234  * @brief Checks if line is inside given diff
 235  * @param [in] nLine Linenumber to text buffer (not "real" number)
 236  * @param [in] nDiff Index to diff table
 237  * @return true if line is inside given difference.
 238  */
 239 bool DiffList::LineInDiff(int nLine, int nDiff) const
 240 {
 241         const DIFFRANGE * dfi = DiffRangeAt(nDiff);
 242         if (static_cast<int>(nLine) >= dfi->dbegin && static_cast<int>(nLine) <= dfi->dend)
 243                 return true;
 244         else
 245                 return false;
 246 }
 247
 248 /**
 249  * @brief Returns diff index for given line.
 250  * @param [in] nLine Linenumber, 0-based.
 251  * @return Index to diff table, -1 if line is not inside any diff.
 252  */
 253 int DiffList::LineToDiff(int nLine) const
 254 {
 255         const int nDiffCount = static_cast<int>(m_diffs.size());
 256         if (nDiffCount == 0)
 257                 return -1;
 258
 259         // First check line is not before first or after last diff
 260         if (nLine < DiffRangeAt(0)->dbegin)
 261                 return -1;
 262         if (nLine > DiffRangeAt(nDiffCount-1)->dend)
 263                 return -1;
 264
 265         // Use binary search to search for a diff.
 266         int left = 0; // Left limit
 267         int right = nDiffCount - 1; // Right limit
 268
 269         while (left <= right)
 270         {
 271                 int middle = (left + right) / 2; // Compared item
 272                 int result = LineRelDiff(nLine, middle);
 273                 switch (result)
 274                 {
 275                 case -1: // Line is before diff in file
 276                         right = middle - 1;
 277                         break;
 278                 case 0: // Line is in diff
 279                         return middle;
 280                         break;
 281                 case 1: // Line is after diff in file
 282                         left = middle + 1;
 283                         break;
 284                 default:
 285                         {
 286                         std::stringstream s;
 287                         s << "Invalid return value " << result << " from LineRelDiff(): -1, 0 or 1 expected!";
 288                         throw s.str();
 289                         }
 290                 }
 291         }
 292         return -1;
 293 }
 294
 295 /**
 296  * @brief Return previous diff from given line.
 297  * @param [in] nLine First line searched.
 298  * @param [out] nDiff Index of diff found.
 299  * @return true if line is inside diff, false otherwise.
 300  */
 301 bool DiffList::GetPrevDiff(int nLine, int & nDiff) const
 302 {
 303         bool bInDiff = true;
 304         int numDiff = LineToDiff(nLine);
 305
 306         // Line not inside diff
 307         if (nDiff == -1)
 308         {
 309                 bInDiff = false;
 310                 const int size = (int) m_diffs.size();
 311                 for (int i = (int) size - 1; i >= 0 ; i--)
 312                 {
 313                         if ((int)DiffRangeAt(i)->dend <= nLine)
 314                         {
 315                                 numDiff = i;
 316                                 break;
 317                         }
 318                 }
 319         }
 320         nDiff = numDiff;
 321         return bInDiff;
 322 }
 323
 324 /**
 325  * @brief Return next difference from given line.
 326  * This function finds next difference from given line. If line is inside
 327  * difference, that difference is returned. If next difference is not found
 328  * param @p nDiff is set to -1.
 329  * @param [in] nLine First line searched.
 330  * @param [out] nDiff Index of diff found.
 331  * @return true if line is inside diff, false otherwise.
 332  */
 333 bool DiffList::GetNextDiff(int nLine, int & nDiff) const
 334 {
 335         bool bInDiff = true;
 336         int numDiff = LineToDiff(nLine);
 337
 338         // Line not inside diff
 339         if (numDiff == -1)
 340         {
 341                 bInDiff = false;
 342                 const int nDiffCount = (int) m_diffs.size();
 343                 for (int i = 0; i < nDiffCount; i++)
 344                 {
 345                         if ((int)DiffRangeAt(i)->dbegin >= nLine)
 346                         {
 347                                 numDiff = i;
 348                                 break;
 349                         }
 350                 }
 351         }
 352         nDiff = numDiff;
 353         return bInDiff;
 354 }
 355
 356 /**
 357  * @brief Return previous diff index from given line.
 358  * @param [in] nLine First line searched.
 359  * @return Index for next difference or -1 if no difference is found.
 360  */
 361 int DiffList::PrevSignificantDiffFromLine(int nLine) const
 362 {
 363         int nDiff = -1;
 364         const int size = (int) m_diffs.size();
 365
 366         for (int i = size - 1; i >= 0 ; i--)
 367         {
 368                 const DIFFRANGE * dfi = DiffRangeAt(i);
 369                 if (dfi->op != OP_TRIVIAL && dfi->dend <= static_cast<int>(nLine))
 370                 {
 371                         nDiff = i;
 372                         break;
 373                 }
 374         }
 375         return nDiff;
 376 }
 377
 378 /**
 379  * @brief Return next diff index from given line.
 380  * @param [in] nLine First line searched.
 381  * @return Index for previous difference or -1 if no difference is found.
 382  */
 383 int DiffList::NextSignificantDiffFromLine(int nLine) const
 384 {
 385         int nDiff = -1;
 386         const int nDiffCount = static_cast<int>(m_diffs.size());
 387
 388         for (int i = 0; i < nDiffCount; i++)
 389         {
 390                 const DIFFRANGE * dfi = DiffRangeAt(i);
 391                 if (dfi->op != OP_TRIVIAL && dfi->dbegin >= static_cast<int>(nLine))
 392                 {
 393                         nDiff = i;
 394                         break;
 395                 }
 396         }
 397         return nDiff;
 398 }
 399
 400 /**
 401  * @brief Construct the doubly-linked chain of significant differences
 402  */
 403 void DiffList::ConstructSignificantChain()
 404 {
 405         m_firstSignificant = -1;
 406         m_lastSignificant = -1;
 407         m_firstSignificantLeftMiddle = -1;
 408         m_firstSignificantLeftRight = -1;
 409         m_firstSignificantMiddleRight = -1;
 410         m_firstSignificantConflict = -1;
 411         m_lastSignificantLeftMiddle = -1;
 412         m_lastSignificantLeftRight = -1;
 413         m_lastSignificantMiddleRight = -1;
 414         m_lastSignificantConflict = -1;
 415         ptrdiff_t prev = -1;
 416         const ptrdiff_t size = (int) m_diffs.size();
 417
 418         // must be called after diff list is entirely populated
 419     for (int i = 0; i < size; ++i)
 420         {
 421                 if (m_diffs[i].op == OP_TRIVIAL)
 422                 {
 423                         m_diffs[i].prev = -1;
 424                         m_diffs[i].next = -1;
 425                 }
 426                 else
 427                 {
 428                         m_diffs[i].prev = prev;
 429                         if (prev != -1)
 430                                 m_diffs[prev].next = (size_t) i;
 431                         prev = i;
 432                         if (m_firstSignificant == -1)
 433                                 m_firstSignificant = i;
 434                         m_lastSignificant = i;
 435                         if (m_diffs[i].op != OP_TRIVIAL && m_diffs[i].op != OP_3RDONLY)
 436                         {
 437                                 if (m_firstSignificantLeftMiddle == -1)
 438                                         m_firstSignificantLeftMiddle = i;
 439                                 m_lastSignificantLeftMiddle = i;
 440                         }
 441                         if (m_diffs[i].op != OP_TRIVIAL && m_diffs[i].op != OP_2NDONLY)
 442                         {
 443                                 if (m_firstSignificantLeftRight == -1)
 444                                         m_firstSignificantLeftRight = i;
 445                                 m_lastSignificantLeftRight = i;
 446                         }
 447                         if (m_diffs[i].op != OP_TRIVIAL && m_diffs[i].op != OP_1STONLY)
 448                         {
 449                                 if (m_firstSignificantMiddleRight == -1)
 450                                         m_firstSignificantMiddleRight = i;
 451                                 m_lastSignificantMiddleRight = i;
 452                         }
 453                         if (m_diffs[i].op == OP_1STONLY)
 454                         {
 455                                 if (m_firstSignificantLeftOnly == -1)
 456                                         m_firstSignificantLeftOnly = i;
 457                                 m_lastSignificantLeftOnly = i;
 458                         }
 459                         if (m_diffs[i].op == OP_2NDONLY)
 460                         {
 461                                 if (m_firstSignificantMiddleOnly == -1)
 462                                         m_firstSignificantMiddleOnly = i;
 463                                 m_lastSignificantMiddleOnly = i;
 464                         }
 465                         if (m_diffs[i].op == OP_3RDONLY)
 466                         {
 467                                 if (m_firstSignificantRightOnly == -1)
 468                                         m_firstSignificantRightOnly = i;
 469                                 m_lastSignificantRightOnly = i;
 470                         }
 471                         if (m_diffs[i].op == OP_DIFF)
 472                         {
 473                                 if (m_firstSignificantConflict == -1)
 474                                         m_firstSignificantConflict = i;
 475                                 m_lastSignificantConflict = i;
 476                         }
 477                 }
 478         }
 479 }
 480
 481
 482 /**
 483  * @brief Return pointer to first significant diff.
 484  * @return Constant pointer to first significant difference.
 485  */
 486 const DIFFRANGE * DiffList::FirstSignificantDiffRange() const
 487 {
 488         if (m_firstSignificant == -1)
 489                 return nullptr;
 490         return DiffRangeAt(m_firstSignificant);
 491 }
 492
 493 /**
 494  * @brief Return pointer to last significant diff.
 495  * @return Constant pointer to last significant difference.
 496  */
 497 const DIFFRANGE * DiffList::LastSignificantDiffRange() const
 498 {
 499         if (m_lastSignificant == -1)
 500                 return nullptr;
 501         return DiffRangeAt(m_lastSignificant);
 502 }
 503
 504 /**
 505 <<<<<<< .mine
 506  * @brief Return previous diff index from given line.
 507  * @param [in] nLine First line searched.
 508  * @return Index for next difference or -1 if no difference is found.
 509  */
 510 int DiffList::PrevSignificant3wayDiffFromLine(int nLine, int nDiffType) const
 511 {
 512         for (int i = static_cast<int>(m_diffs.size()) - 1; i >= 0 ; i--)
 513         {
 514                 const DIFFRANGE * dfi = DiffRangeAt(i);
 515                 switch (nDiffType)
 516                 {
 517                 case THREEWAYDIFFTYPE_LEFTMIDDLE:
 518                         if (dfi->op != OP_TRIVIAL && dfi->op != OP_3RDONLY && dfi->dend <= static_cast<int>(nLine))
 519                                 return i;
 520                         break;
 521                 case THREEWAYDIFFTYPE_LEFTRIGHT:
 522                         if (dfi->op != OP_TRIVIAL && dfi->op != OP_2NDONLY && dfi->dend <= static_cast<int>(nLine))
 523                                 return i;
 524                         break;
 525                 case THREEWAYDIFFTYPE_MIDDLERIGHT:
 526                         if (dfi->op != OP_TRIVIAL && dfi->op != OP_1STONLY && dfi->dend <= static_cast<int>(nLine))
 527                                 return i;
 528                         break;
 529                 case THREEWAYDIFFTYPE_LEFTONLY:
 530                         if (dfi->op == OP_1STONLY && dfi->dend <= static_cast<int>(nLine))
 531                                 return i;
 532                         break;
 533                 case THREEWAYDIFFTYPE_MIDDLEONLY:
 534                         if (dfi->op == OP_2NDONLY && dfi->dend <= static_cast<int>(nLine))
 535                                 return i;
 536                         break;
 537                 case THREEWAYDIFFTYPE_RIGHTONLY:
 538                         if (dfi->op == OP_3RDONLY && dfi->dend <= static_cast<int>(nLine))
 539                                 return i;
 540                         break;
 541                 case THREEWAYDIFFTYPE_CONFLICT:
 542                         if (dfi->op == OP_DIFF && dfi->dend <= nLine)
 543                                 return i;
 544                         break;
 545                 }
 546         }
 547         return -1;
 548 }
 549
 550 /**
 551  * @brief Return next diff index from given line.
 552  * @param [in] nLine First line searched.
 553  * @return Index for previous difference or -1 if no difference is found.
 554  */
 555 int DiffList::NextSignificant3wayDiffFromLine(int nLine, int nDiffType) const
 556 {
 557         const int nDiffCount = static_cast<int>(m_diffs.size());
 558
 559         for (int i = 0; i < nDiffCount; i++)
 560         {
 561                 const DIFFRANGE * dfi = DiffRangeAt(i);
 562                 switch (nDiffType)
 563                 {
 564                 case THREEWAYDIFFTYPE_LEFTMIDDLE:
 565                         if (dfi->op != OP_TRIVIAL && dfi->op != OP_3RDONLY && dfi->dbegin >= static_cast<int>(nLine))
 566                                 return i;
 567                         break;
 568                 case THREEWAYDIFFTYPE_LEFTRIGHT:
 569                         if (dfi->op != OP_TRIVIAL && dfi->op != OP_2NDONLY && dfi->dbegin >= static_cast<int>(nLine))
 570                                 return i;
 571                         break;
 572                 case THREEWAYDIFFTYPE_MIDDLERIGHT:
 573                         if (dfi->op != OP_TRIVIAL && dfi->op != OP_1STONLY && dfi->dbegin >= static_cast<int>(nLine))
 574                                 return i;
 575                         break;
 576                 case THREEWAYDIFFTYPE_LEFTONLY:
 577                         if (dfi->op == OP_1STONLY && dfi->dbegin >= static_cast<int>(nLine))
 578                                 return i;
 579                         break;
 580                 case THREEWAYDIFFTYPE_MIDDLEONLY:
 581                         if (dfi->op == OP_2NDONLY && dfi->dbegin >= static_cast<int>(nLine))
 582                                 return i;
 583                         break;
 584                 case THREEWAYDIFFTYPE_RIGHTONLY:
 585                         if (dfi->op == OP_3RDONLY && dfi->dbegin >= static_cast<int>(nLine))
 586                                 return i;
 587                         break;
 588                 case THREEWAYDIFFTYPE_CONFLICT:
 589                         if (dfi->op == OP_DIFF && dfi->dbegin >= nLine)
 590                                 return i;
 591                         break;
 592                 }
 593         }
 594         return -1;
 595 }
 596
 597 /**
 598  * @brief Return index to first significant difference.
 599  * @return Index of first significant difference.
 600  */
 601 int DiffList::FirstSignificant3wayDiff(int nDiffType) const
 602 {
 603         switch (nDiffType)
 604         {
 605         case THREEWAYDIFFTYPE_LEFTMIDDLE:
 606                 return m_firstSignificantLeftMiddle;
 607         case THREEWAYDIFFTYPE_LEFTRIGHT:
 608                 return m_firstSignificantLeftRight;
 609         case THREEWAYDIFFTYPE_MIDDLERIGHT:
 610                 return m_firstSignificantMiddleRight;
 611         case THREEWAYDIFFTYPE_LEFTONLY:
 612                 return m_firstSignificantLeftOnly;
 613         case THREEWAYDIFFTYPE_MIDDLEONLY:
 614                 return m_firstSignificantLeftOnly;
 615         case THREEWAYDIFFTYPE_RIGHTONLY:
 616                 return m_firstSignificantRightOnly;
 617         case THREEWAYDIFFTYPE_CONFLICT:
 618                 return m_firstSignificantConflict;
 619         }
 620         return -1;
 621 }
 622
 623 /**
 624  * @brief Return index of next significant diff.
 625  * @param [in] nDiff Index to start looking for next diff.
 626  * @return Index of next significant difference.
 627  */
 628 int DiffList::NextSignificant3wayDiff(int nDiff, int nDiffType) const
 629 {
 630         while (m_diffs[nDiff].next != -1)
 631         {
 632                 nDiff = static_cast<int>(m_diffs[nDiff].next);
 633                 switch (nDiffType)
 634                 {
 635                 case THREEWAYDIFFTYPE_LEFTMIDDLE:
 636                         if (m_diffs[nDiff].op != OP_3RDONLY)
 637                                 return nDiff;
 638                         break;
 639                 case THREEWAYDIFFTYPE_LEFTRIGHT:
 640                         if (m_diffs[nDiff].op != OP_2NDONLY)
 641                                 return nDiff;
 642                         break;
 643                 case THREEWAYDIFFTYPE_MIDDLERIGHT:
 644                         if (m_diffs[nDiff].op != OP_1STONLY)
 645                                 return nDiff;
 646                         break;
 647                 case THREEWAYDIFFTYPE_LEFTONLY:
 648                         if (m_diffs[nDiff].op == OP_1STONLY)
 649                                 return nDiff;
 650                         break;
 651                 case THREEWAYDIFFTYPE_MIDDLEONLY:
 652                         if (m_diffs[nDiff].op == OP_2NDONLY)
 653                                 return nDiff;
 654                         break;
 655                 case THREEWAYDIFFTYPE_RIGHTONLY:
 656                         if (m_diffs[nDiff].op == OP_3RDONLY)
 657                                 return nDiff;
 658                         break;
 659                 case THREEWAYDIFFTYPE_CONFLICT:
 660                         if (m_diffs[nDiff].op == OP_DIFF)
 661                                 return nDiff;
 662                         break;
 663                 }
 664         }
 665         return -1;
 666 }
 667
 668 /**
 669  * @brief Return index of previous significant diff.
 670  * @param [in] nDiff Index to start looking for previous diff.
 671  * @return Index of previous significant difference.
 672  */
 673 int DiffList::PrevSignificant3wayDiff(int nDiff, int nDiffType) const
 674 {
 675         while (m_diffs[nDiff].prev != -1)
 676         {
 677                 nDiff = static_cast<int>(m_diffs[nDiff].prev);
 678                 switch (nDiffType)
 679                 {
 680                 case THREEWAYDIFFTYPE_LEFTMIDDLE:
 681                         if (m_diffs[nDiff].op != OP_3RDONLY)
 682                                 return nDiff;
 683                         break;
 684                 case THREEWAYDIFFTYPE_LEFTRIGHT:
 685                         if (m_diffs[nDiff].op != OP_2NDONLY)
 686                                 return nDiff;
 687                         break;
 688                 case THREEWAYDIFFTYPE_MIDDLERIGHT:
 689                         if (m_diffs[nDiff].op != OP_1STONLY)
 690                                 return nDiff;
 691                         break;
 692                 case THREEWAYDIFFTYPE_LEFTONLY:
 693                         if (m_diffs[nDiff].op == OP_1STONLY)
 694                                 return nDiff;
 695                         break;
 696                 case THREEWAYDIFFTYPE_MIDDLEONLY:
 697                         if (m_diffs[nDiff].op == OP_2NDONLY)
 698                                 return nDiff;
 699                         break;
 700                 case THREEWAYDIFFTYPE_RIGHTONLY:
 701                         if (m_diffs[nDiff].op == OP_3RDONLY)
 702                                 return nDiff;
 703                         break;
 704                 case THREEWAYDIFFTYPE_CONFLICT:
 705                         if (m_diffs[nDiff].op == OP_DIFF)
 706                                 return nDiff;
 707                         break;
 708                 }
 709         }
 710         return -1;
 711 }
 712
 713 /**
 714  * @brief Return index to last significant diff.
 715  * @return Index of last significant difference.
 716  */
 717 int DiffList::LastSignificant3wayDiff(int nDiffType) const
 718 {
 719         switch (nDiffType)
 720         {
 721         case THREEWAYDIFFTYPE_LEFTMIDDLE:
 722                 return m_lastSignificantLeftMiddle;
 723         case THREEWAYDIFFTYPE_LEFTRIGHT:
 724                 return m_lastSignificantLeftRight;
 725         case THREEWAYDIFFTYPE_MIDDLERIGHT:
 726                 return m_lastSignificantMiddleRight;
 727         case THREEWAYDIFFTYPE_LEFTONLY:
 728                 return m_lastSignificantLeftOnly;
 729         case THREEWAYDIFFTYPE_MIDDLEONLY:
 730                 return m_lastSignificantLeftOnly;
 731         case THREEWAYDIFFTYPE_RIGHTONLY:
 732                 return m_lastSignificantRightOnly;
 733         case THREEWAYDIFFTYPE_CONFLICT:
 734                 return m_lastSignificantRightOnly;
 735         }
 736         return -1;
 737 }
 738
 739 /**
 740  * @brief Return pointer to first significant diff.
 741  * @return Constant pointer to first significant difference.
 742  */
 743 const DIFFRANGE * DiffList::FirstSignificant3wayDiffRange(int nDiffType) const
 744 {
 745         switch (nDiffType)
 746         {
 747         case THREEWAYDIFFTYPE_LEFTMIDDLE:
 748                 if (m_firstSignificantLeftMiddle == -1) return nullptr;
 749                 return DiffRangeAt(m_firstSignificantLeftMiddle);
 750         case THREEWAYDIFFTYPE_LEFTRIGHT:
 751                 if (m_firstSignificantLeftRight == -1) return nullptr;
 752                 return DiffRangeAt(m_firstSignificantLeftRight);
 753         case THREEWAYDIFFTYPE_MIDDLERIGHT:
 754                 if (m_firstSignificantMiddleRight == -1) return nullptr;
 755                 return DiffRangeAt(m_firstSignificantMiddleRight);
 756         case THREEWAYDIFFTYPE_LEFTONLY:
 757                 if (m_firstSignificantLeftOnly == -1) return nullptr;
 758                 return DiffRangeAt(m_firstSignificantLeftOnly);
 759         case THREEWAYDIFFTYPE_MIDDLEONLY:
 760                 if (m_firstSignificantMiddleOnly == -1) return nullptr;
 761                 return DiffRangeAt(m_firstSignificantMiddleOnly);
 762         case THREEWAYDIFFTYPE_RIGHTONLY:
 763                 if (m_firstSignificantRightOnly == -1) return nullptr;
 764                 return DiffRangeAt(m_firstSignificantRightOnly);
 765         case THREEWAYDIFFTYPE_CONFLICT:
 766                 if (m_firstSignificantConflict == -1) return nullptr;
 767                 return DiffRangeAt(m_firstSignificantConflict);
 768         }
 769         return nullptr;
 770 }
 771
 772 /**
 773  * @brief Return pointer to last significant diff.
 774  * @return Constant pointer to last significant difference.
 775  */
 776 const DIFFRANGE * DiffList::LastSignificant3wayDiffRange(int nDiffType) const
 777 {
 778         switch (nDiffType)
 779         {
 780         case THREEWAYDIFFTYPE_LEFTMIDDLE:
 781                 if (m_lastSignificantLeftMiddle == -1) return nullptr;
 782                 return DiffRangeAt(m_lastSignificantLeftMiddle);
 783         case THREEWAYDIFFTYPE_LEFTRIGHT:
 784                 if (m_lastSignificantLeftRight == -1) return nullptr;
 785                 return DiffRangeAt(m_lastSignificantLeftRight);
 786         case THREEWAYDIFFTYPE_MIDDLERIGHT:
 787                 if (m_lastSignificantMiddleRight == -1) return nullptr;
 788                 return DiffRangeAt(m_lastSignificantMiddleRight);
 789         case THREEWAYDIFFTYPE_LEFTONLY:
 790                 if (m_lastSignificantLeftOnly == -1) return nullptr;
 791                 return DiffRangeAt(m_lastSignificantLeftOnly);
 792         case THREEWAYDIFFTYPE_MIDDLEONLY:
 793                 if (m_lastSignificantMiddleOnly == -1) return nullptr;
 794                 return DiffRangeAt(m_lastSignificantMiddleOnly);
 795         case THREEWAYDIFFTYPE_RIGHTONLY:
 796                 if (m_lastSignificantRightOnly == -1) return nullptr;
 797                 return DiffRangeAt(m_lastSignificantRightOnly);
 798         case THREEWAYDIFFTYPE_CONFLICT:
 799                 if (m_lastSignificantConflict == -1) return nullptr;
 800                 return DiffRangeAt(m_lastSignificantConflict);
 801         }
 802         return nullptr;
 803 }
 804
 805 /**
 806  * @brief Swap sides of diffrange
 807  */
 808 void DiffList::Swap(int index1, int index2)
 809 {
 810         vector<DiffRangeInfo>::iterator iter = m_diffs.begin();
 811         vector<DiffRangeInfo>::const_iterator iterEnd = m_diffs.end();
 812         while (iter != iterEnd)
 813         {
 814                 (*iter).swap_sides(index1, index2);
 815                 ++iter;
 816         }
 817 }
 818
 819 /**
 820  * @brief Count number of lines to add to sides (because of synch).
 821  * @param [out] nLeftLines Number of lines to add to left side.
 822  * @param [out] nRightLines Number of lines to add to right side.
 823  */
 824 void DiffList::GetExtraLinesCounts(int nFiles, int extras[3])
 825 {
 826         extras[0]=0;
 827         extras[1]=0;
 828         extras[2]=0;
 829         const int nDiffCount = GetSize();
 830
 831         for (int nDiff = 0; nDiff < nDiffCount; ++nDiff)
 832         {
 833                 DIFFRANGE curDiff;
 834                 GetDiff(nDiff, curDiff);
 835
 836                 // this guarantees that all the diffs are synchronized
 837                 assert(curDiff.begin[0]+extras[0] == curDiff.begin[1]+extras[1]);
 838                 assert(nFiles<3 || curDiff.begin[0]+extras[0] == curDiff.begin[2]+extras[2]);
 839                 int nline[3] = { 0,0,0 };
 840                 int nmaxline = 0;
 841                 int file;
 842                 for (file = 0; file < nFiles; file++)
 843                 {
 844                         nline[file] = curDiff.end[file]-curDiff.begin[file]+1;
 845                         nmaxline = std::max(nmaxline, nline[file]);
 846                 }
 847                 for (file = 0; file < nFiles; file++)
 848                         extras[file] += nmaxline - nline[file];
 849         }
 850 }
 851
 852 void DiffList::AppendDiffList(const DiffList& list, int offset[] /*= nullptr*/, int doffset /*= 0*/)
 853 {
 854         for (std::vector<DiffRangeInfo>::const_iterator it = list.m_diffs.begin(); it != list.m_diffs.end(); ++it)
 855         {
 856                 DiffRangeInfo dr = *it;
 857                 for (int file = 0; file < 3; ++file)
 858                 {
 859                         if (offset != nullptr)
 860                         {
 861                                 dr.begin[file] += offset[file];
 862                                 dr.end[file] += offset[file];
 863                         }
 864                         if (doffset != 0)
 865                                 dr.blank[file] += doffset;
 866                 }
 867                 if (doffset != 0)
 868                 {
 869                         dr.dbegin += doffset;
 870                         dr.dend += doffset;
 871                 }
 872                 AddDiff(dr);
 873         }
 874 }
 875
 876 int DiffList::GetMergeableSrcIndex(int nDiff, int nDestIndex) const
 877 {
 878         const DIFFRANGE *pdr = DiffRangeAt(nDiff);
 879         switch (nDestIndex)
 880         {
 881         case 0:
 882         case 2:
 883                 if (pdr->op == OP_2NDONLY)
 884                         return 1;
 885                 return -1;
 886         case 1:
 887                 if (pdr->op == OP_1STONLY || pdr->op == OP_2NDONLY)
 888                         return 0;
 889                 else if (pdr->op == OP_3RDONLY)
 890                         return 2;
 891                 return -1;
 892         default:
 893                 return -1;
 894         }
 895 }