src/TortoiseMerge/MovedBlocks.cpp

   1 // TortoiseGitMerge - a Diff/Patch program
   2
   3 // Copyright (C) 2010-2012 - TortoiseSVN
   4
   5 // This program is free software; you can redistribute it and/or
   6 // modify it under the terms of the GNU General Public License
   7 // as published by the Free Software Foundation; either version 2
   8 // of the License, or (at your option) any later version.
   9
  10 // This program is distributed in the hope that it will be useful,
  11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 // GNU General Public License for more details.
  14
  15 // You should have received a copy of the GNU General Public License
  16 // along with this program; if not, write to the Free Software Foundation,
  17 // 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 //
  19 #include "stdafx.h"
  20 #include "diff.h"
  21 #include "MovedBlocks.h"
  22 #include "DiffData.h"
  23 #include <set>
  24 #include <map>
  25
  26 // This file implements moved blocks detection algorithm, based
  27 // on WinMerges(http:\\winmerge.org) one
  28
  29 class IntSet
  30 {
  31 public:
  32         void Add(int val);
  33         void Remove(int val);
  34         int Count() const;
  35         bool IsPresent(int val) const;
  36         int GetSingle() const;
  37 private:
  38         std::set<int>           m_set;
  39 };
  40
  41 struct EquivalencyGroup
  42 {
  43         IntSet m_LinesLeft;  // equivalent lines on left pane
  44         IntSet m_LinesRight; // equivalent lines on right pane
  45
  46         bool IsPerfectMatch() const;
  47 };
  48
  49 class LineToGroupMap : public std::map<CString, EquivalencyGroup*>
  50 {
  51 public:
  52         void Add(int lineno, const CString &line, int nside);
  53         EquivalencyGroup *find(const CString &line) const;
  54         ~LineToGroupMap();
  55 };
  56
  57 void IntSet::Add(int val)
  58 {
  59         m_set.insert(val);
  60 }
  61
  62 void IntSet::Remove(int val)
  63 {
  64         m_set.erase(val);
  65 }
  66
  67 int IntSet::Count() const
  68 {
  69         return (int)m_set.size();
  70 }
  71
  72 bool IntSet::IsPresent(int val) const
  73 {
  74         return m_set.find(val) != m_set.end();
  75 }
  76
  77 int IntSet::GetSingle() const
  78 {
  79         if (!m_set.empty())
  80         {
  81                 return *m_set.cbegin();
  82         }
  83         return 0;
  84 }
  85
  86 bool EquivalencyGroup::IsPerfectMatch() const
  87 {
  88         return (m_LinesLeft.Count() == 1)&&(m_LinesRight.Count() == 1);
  89 }
  90
  91 void LineToGroupMap::Add(int lineno, const CString &line, int nside)
  92 {
  93         EquivalencyGroup *pGroup = NULL;
  94         auto it = __super::find(line);
  95         if ( it == cend() )
  96         {
  97                 pGroup = new EquivalencyGroup;
  98                 insert(std::pair<CString, EquivalencyGroup*>(line, pGroup));
  99         }
 100         else
 101                 pGroup = it->second;
 102         if(nside)
 103         {
 104                 pGroup->m_LinesRight.Add(lineno);
 105         }
 106         else
 107         {
 108                 pGroup->m_LinesLeft.Add(lineno);
 109         }
 110 }
 111
 112 EquivalencyGroup *LineToGroupMap::find(const CString &line) const
 113 {
 114         EquivalencyGroup *pGroup = NULL;
 115         auto it = __super::find(line);
 116         if ( it != cend() )
 117                 pGroup = it->second;
 118         return pGroup;
 119 }
 120
 121 LineToGroupMap::~LineToGroupMap()
 122 {
 123         for (auto it = cbegin(); it != cend(); ++it)
 124         {
 125                 delete it->second;
 126         }
 127 }
 128
 129 tsvn_svn_diff_t_extension * CreateDiffExtension(svn_diff_t * base, apr_pool_t * pool)
 130 {
 131         tsvn_svn_diff_t_extension * ext = (tsvn_svn_diff_t_extension *)apr_palloc(pool, sizeof(tsvn_svn_diff_t_extension));
 132         ext->next = NULL;
 133         ext->moved_to = -1;
 134         ext->moved_from = -1;
 135         ext->base = base;
 136         return ext;
 137 }
 138
 139 void AdjustExistingAndTail(svn_diff_t * tempdiff, tsvn_svn_diff_t_extension *& existing, tsvn_svn_diff_t_extension *& tail)
 140 {
 141         if(existing && existing->base == tempdiff)
 142         {
 143                 if(tail && tail != existing)
 144                 {
 145                         tail->next = existing;
 146                 }
 147                 tail = existing;
 148                 existing = existing->next;
 149         }
 150 }
 151
 152 CString GetTrimmedString(const CString& s1, DWORD dwIgnoreWS)
 153 {
 154         if(dwIgnoreWS == 1)
 155         {
 156                 CString s2 = s1;
 157                 s2.Remove(' ');
 158                 s2.Remove('\t');
 159                 return s2;
 160         }
 161         else if(dwIgnoreWS == 2)
 162                 return CString(s1).TrimLeft(_T(" \t"));
 163         return CString(s1).TrimRight(_T(" \t"));
 164 }
 165
 166 EquivalencyGroup * ExtractGroup(const LineToGroupMap & map, const CString & line, DWORD dwIgnoreWS)
 167 {
 168         if (dwIgnoreWS)
 169                 return map.find(GetTrimmedString(line, dwIgnoreWS));
 170         return map.find(line);
 171 }
 172
 173 tsvn_svn_diff_t_extension * CDiffData::MovedBlocksDetect(svn_diff_t * diffYourBase, DWORD dwIgnoreWS, apr_pool_t * pool)
 174 {
 175         LineToGroupMap map;
 176         tsvn_svn_diff_t_extension * head = NULL;
 177         tsvn_svn_diff_t_extension * tail = NULL;
 178         svn_diff_t * tempdiff = diffYourBase;
 179         LONG baseLine = 0;
 180         LONG yourLine = 0;
 181         for(;tempdiff; tempdiff = tempdiff->next) // fill map
 182         {
 183                 if(tempdiff->type != svn_diff__type_diff_modified)
 184                         continue;
 185
 186                 baseLine = (LONG)tempdiff->original_start;
 187                 for(int i = 0; i < tempdiff->original_length; ++i, ++baseLine)
 188                 {
 189                         const CString &sCurrentBaseLine = m_arBaseFile.GetAt(baseLine);
 190                         if (dwIgnoreWS)
 191                                 map.Add(baseLine, GetTrimmedString(sCurrentBaseLine, dwIgnoreWS), 0);
 192                         else
 193                                 map.Add(baseLine, sCurrentBaseLine, 0);
 194                 }
 195                 yourLine = (LONG)tempdiff->modified_start;
 196                 for(int i = 0; i < tempdiff->modified_length; ++i, ++yourLine)
 197                 {
 198                         const CString &sCurrentYourLine = m_arYourFile.GetAt(yourLine);
 199                         if(dwIgnoreWS)
 200                                 map.Add(yourLine, GetTrimmedString(sCurrentYourLine, dwIgnoreWS), 1);
 201                         else
 202                                 map.Add(yourLine, sCurrentYourLine, 1);
 203                 }
 204         }
 205         for(tempdiff = diffYourBase; tempdiff; tempdiff = tempdiff->next)
 206         {
 207         // Scan through diff blocks, finding moved sections from left side
 208         // and splitting them out
 209         // That is, we actually fragment diff blocks as we find moved sections
 210                 if(tempdiff->type != svn_diff__type_diff_modified)
 211                         continue;
 212
 213                 EquivalencyGroup * pGroup = NULL;
 214
 215                 int i;
 216                 for(i = (int)tempdiff->original_start; (i - tempdiff->original_start)< tempdiff->original_length; ++i)
 217                 {
 218                         EquivalencyGroup * group = ExtractGroup(map, m_arBaseFile.GetAt(i), dwIgnoreWS);
 219                         if(group->IsPerfectMatch())
 220                         {
 221                                 pGroup = group;
 222                                 break;
 223                         }
 224                 }
 225                 if(!pGroup) // if no match
 226                         continue;
 227                 // found a match
 228                 int j = pGroup->m_LinesRight.GetSingle();
 229                 // Ok, now our moved block is the single line (i, j)
 230
 231                 // extend moved block upward as far as possible
 232                 int i1 = i - 1;
 233                 int j1 = j - 1;
 234                 for(; (i1 >= tempdiff->original_start) && (j1>=0) && (i1>=0); --i1, --j1)
 235                 {
 236                         EquivalencyGroup * pGroup0 = ExtractGroup(map, m_arBaseFile.GetAt(i1), dwIgnoreWS);
 237                         EquivalencyGroup * pGroup1 = ExtractGroup(map, m_arYourFile.GetAt(j1), dwIgnoreWS);
 238                         if(pGroup1 != pGroup0)
 239                                 break;
 240                         pGroup0->m_LinesLeft.Remove(i1);
 241                         pGroup1->m_LinesRight.Remove(j1);
 242                 }
 243                 ++i1;
 244                 ++j1;
 245                 // Ok, now our moved block is (i1..i, j1..j)
 246
 247                 // extend moved block downward as far as possible
 248
 249                 int i2 = i + 1;
 250                 int j2 = j + 1;
 251                 for(; ((i2-tempdiff->original_start) < tempdiff->original_length)&&(j2>=0); ++i2, ++j2)
 252                 {
 253                         if(i2 >= m_arBaseFile.GetCount() || j2 >= m_arYourFile.GetCount())
 254                                 break;
 255                         EquivalencyGroup * pGroup0 = ExtractGroup(map, m_arBaseFile.GetAt(i2), dwIgnoreWS);
 256                         EquivalencyGroup * pGroup1 = ExtractGroup(map, m_arYourFile.GetAt(j2), dwIgnoreWS);
 257                         if(pGroup1 != pGroup0)
 258                                 break;
 259                         pGroup0->m_LinesLeft.Remove(i2);
 260                         pGroup1->m_LinesRight.Remove(j2);
 261                 }
 262                 --i2;
 263                 --j2;
 264                 // Ok, now our moved block is (i1..i2,j1..j2)
 265                 tsvn_svn_diff_t_extension * newTail = CreateDiffExtension(tempdiff, pool);
 266                 if(head == NULL)
 267                 {
 268                         head = newTail;
 269                         tail = head;
 270                 }
 271                 else
 272                 {
 273                         tail->next = newTail;
 274                         tail = newTail;
 275                 }
 276
 277                 int prefix = i1 - (int)tempdiff->original_start;
 278                 if(prefix)
 279                 {
 280                         // break tempdiff (current change) into two pieces
 281                         // first part is the prefix, before the moved part
 282                         // that stays in tempdiff
 283                         // second part is the moved part & anything after it
 284                         // that goes in newob
 285                         // leave the left side (tempdiff->original_length) on tempdiff
 286                         // so no right side on newob
 287                         // newob will be the moved part only, later after we split off any suffix from it
 288                         svn_diff_t * newob = (svn_diff_t *)apr_palloc(pool, sizeof(svn_diff_t));
 289                         memset(newob, 0, sizeof(*newob));
 290
 291                         tail->base = newob;
 292                         newob->type = svn_diff__type_diff_modified;
 293                         newob->original_start = i1;
 294                         newob->modified_start = tempdiff->modified_start + tempdiff->modified_length;
 295                         newob->modified_length = 0;
 296                         newob->original_length = tempdiff->original_length - prefix;
 297                         newob->next = tempdiff->next;
 298
 299                         tempdiff->original_length = prefix;
 300                         tempdiff->next = newob;
 301
 302                         // now make tempdiff point to the moved part (& any suffix)
 303                         tempdiff = newob;
 304                 }
 305
 306                 tail->moved_to = j1;
 307
 308                 apr_off_t suffix = (tempdiff->original_length) - (i2- (tempdiff->original_start)) - 1;
 309                 if (suffix)
 310                 {
 311                         // break off any suffix from tempdiff
 312                         // newob will be the suffix, and will get all the right side
 313                         svn_diff_t * newob = (svn_diff_t *) apr_palloc(pool, sizeof (*newob));
 314                         memset(newob, 0, sizeof(*newob));
 315                         newob->type = svn_diff__type_diff_modified;
 316
 317                         newob->original_start = i2 + 1;
 318                         newob->modified_start = tempdiff->modified_start;
 319                         newob->modified_length = tempdiff->modified_length;
 320                         newob->original_length = suffix;
 321                         newob->next = tempdiff->next;
 322
 323                         tempdiff->modified_length = 0;
 324                         tempdiff->original_length -= suffix;
 325                         tempdiff->next = newob;
 326                 }
 327         }
 328         // Scan through diff blocks, finding moved sections from right side
 329         // and splitting them out
 330         // That is, we actually fragment diff blocks as we find moved sections
 331         tsvn_svn_diff_t_extension * existing = head;
 332         tail = NULL;
 333         for(tempdiff = diffYourBase; tempdiff; tempdiff = tempdiff->next)
 334         {
 335                 // scan down block for a match
 336                 if(tempdiff->type != svn_diff__type_diff_modified)
 337                         continue;
 338
 339                 EquivalencyGroup * pGroup = NULL;
 340                 int j = 0;
 341                 for(j = (int)tempdiff->modified_start; (j - tempdiff->modified_start) < tempdiff->modified_length; ++j)
 342                 {
 343                         EquivalencyGroup * group = ExtractGroup(map, m_arYourFile.GetAt(j), dwIgnoreWS);
 344                         if(group->IsPerfectMatch())
 345                         {
 346                                 pGroup = group;
 347                                 break;
 348                         }
 349                 }
 350
 351                 // if no match, go to next diff block
 352                 if (!pGroup)
 353                 {
 354                         AdjustExistingAndTail(tempdiff, existing, tail);
 355                         continue;
 356                 }
 357
 358                 // found a match
 359                 int i = pGroup->m_LinesLeft.GetSingle();
 360                 if (i == 0)
 361                         continue;
 362                 // Ok, now our moved block is the single line (i,j)
 363
 364                 // extend moved block upward as far as possible
 365                 int i1 = i-1;
 366                 int j1 = j-1;
 367                 for ( ; (j1>=tempdiff->modified_start) && (j1>=0) && (i1>=0); --i1, --j1)
 368                 {
 369                         EquivalencyGroup * pGroup0 = ExtractGroup(map, m_arBaseFile.GetAt(i1), dwIgnoreWS);
 370                         EquivalencyGroup * pGroup1 = ExtractGroup(map, m_arYourFile.GetAt(j1), dwIgnoreWS);
 371                         if (pGroup0 != pGroup1)
 372                                 break;
 373                         pGroup0->m_LinesLeft.Remove(i1);
 374                         pGroup1->m_LinesRight.Remove(j1);
 375                 }
 376                 ++i1;
 377                 ++j1;
 378                 // Ok, now our moved block is (i1..i,j1..j)
 379
 380                 // extend moved block downward as far as possible
 381                 int i2 = i+1;
 382                 int j2 = j+1;
 383                 for ( ; (j2-(tempdiff->modified_start) < tempdiff->modified_length) && (i2>=0); ++i2,++j2)
 384                 {
 385                         if(i2 >= m_arBaseFile.GetCount() || j2 >= m_arYourFile.GetCount())
 386                                 break;
 387                         EquivalencyGroup * pGroup0 = ExtractGroup(map, m_arBaseFile.GetAt(i2), dwIgnoreWS);
 388                         EquivalencyGroup * pGroup1 = ExtractGroup(map, m_arYourFile.GetAt(j2), dwIgnoreWS);
 389                         if (pGroup0 != pGroup1)
 390                                 break;
 391                         pGroup0->m_LinesLeft.Remove(i2);
 392                         pGroup1->m_LinesRight.Remove(j2);
 393                 }
 394                 --i2;
 395                 --j2;
 396                 // Ok, now our moved block is (i1..i2,j1..j2)
 397                 tsvn_svn_diff_t_extension * newTail = NULL;
 398                 if(existing && existing->base == tempdiff)
 399                 {
 400                         newTail = existing;
 401                 }
 402                 else
 403                 {
 404                         newTail = CreateDiffExtension(tempdiff, pool);
 405                         if(head == NULL)
 406                         {
 407                                 head = newTail;
 408                         }
 409                         else if(tail)
 410                         {
 411                                 newTail->next = tail->next;
 412                                 tail->next = newTail;
 413                         }
 414                 }
 415                 tail = newTail;
 416
 417                 apr_off_t prefix = j1 - (tempdiff->modified_start);
 418                 if (prefix)
 419                 {
 420                         // break tempdiff (current change) into two pieces
 421                         // first part is the prefix, before the moved part
 422                         // that stays in tempdiff
 423                         // second part is the moved part & anything after it
 424                         // that goes in newob
 425                         // leave the left side (tempdiff->original_length) on tempdiff
 426                         // so no right side on newob
 427                         // newob will be the moved part only, later after we split off any suffix from it
 428                         svn_diff_t * newob = (svn_diff_t *) apr_palloc(pool, sizeof (*newob));
 429                         memset(newob, 0, sizeof(*newob));
 430                         newob->type = svn_diff__type_diff_modified;
 431
 432                         if(existing == newTail)
 433                         {
 434                                 newTail = CreateDiffExtension(newob, pool);
 435                                 newTail->next = tail->next;
 436                                 tail->next = newTail;
 437                                 tail = newTail;
 438                         }
 439                         tail->base = newob;
 440                         newob->original_start = tempdiff->original_start + tempdiff->original_length;
 441                         newob->modified_start = j1;
 442                         newob->modified_length = tempdiff->modified_length - prefix;
 443                         newob->original_length = 0;
 444                         newob->next = tempdiff->next;
 445
 446                         tempdiff->modified_length = prefix;
 447                         tempdiff->next = newob;
 448
 449                         // now make tempdiff point to the moved part (& any suffix)
 450                         tempdiff = newob;
 451                 }
 452                 // now tempdiff points to a moved diff chunk with no prefix, but maybe a suffix
 453
 454                 tail->moved_from = i1;
 455
 456                 apr_off_t suffix = (tempdiff->modified_length) - (j2-(tempdiff->modified_start)) - 1;
 457                 if (suffix)
 458                 {
 459                         // break off any suffix from tempdiff
 460                         // newob will be the suffix, and will get all the left side
 461                         svn_diff_t * newob = (svn_diff_t *) apr_palloc(pool, sizeof (*newob));
 462                         memset(newob, 0, sizeof(*newob));
 463                         tsvn_svn_diff_t_extension * eNewOb = CreateDiffExtension(newob, pool);
 464
 465                         newob->type = svn_diff__type_diff_modified;
 466                         newob->original_start = tempdiff->original_start;
 467                         newob->modified_start = j2+1;
 468                         newob->modified_length = suffix;
 469                         newob->original_length = tempdiff->original_length;
 470                         newob->next = tempdiff->next;
 471                         eNewOb->moved_from = -1;
 472                         eNewOb->moved_to = tail->moved_to;
 473
 474                         tempdiff->modified_length -= suffix;
 475                         tempdiff->original_length = 0;
 476                         tail->moved_to = -1;
 477                         tempdiff->next = newob;
 478                         eNewOb->next = tail->next;
 479                         tail->next = eNewOb;
 480                         existing = tail = eNewOb;
 481                 }
 482                 AdjustExistingAndTail(tempdiff, existing, tail);
 483         }
 484         return head;
 485 }