src/TortoiseMerge/MovedBlocks.cpp

   1 // TortoiseGitMerge - a Diff/Patch program
   2
   3 // Copyright (C) 2010-2013 - 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                 if (m_arBaseFile.GetCount() <= (baseLine+tempdiff->original_length))
 188                         return NULL;
 189                 for(int i = 0; i < tempdiff->original_length; ++i, ++baseLine)
 190                 {
 191                         const CString &sCurrentBaseLine = m_arBaseFile.GetAt(baseLine);
 192                         if (dwIgnoreWS)
 193                                 map.Add(baseLine, GetTrimmedString(sCurrentBaseLine, dwIgnoreWS), 0);
 194                         else
 195                                 map.Add(baseLine, sCurrentBaseLine, 0);
 196                 }
 197                 yourLine = (LONG)tempdiff->modified_start;
 198                 if (m_arYourFile.GetCount() <= (yourLine+tempdiff->modified_length))
 199                         return NULL;
 200                 for(int i = 0; i < tempdiff->modified_length; ++i, ++yourLine)
 201                 {
 202                         const CString &sCurrentYourLine = m_arYourFile.GetAt(yourLine);
 203                         if(dwIgnoreWS)
 204                                 map.Add(yourLine, GetTrimmedString(sCurrentYourLine, dwIgnoreWS), 1);
 205                         else
 206                                 map.Add(yourLine, sCurrentYourLine, 1);
 207                 }
 208         }
 209         for(tempdiff = diffYourBase; tempdiff; tempdiff = tempdiff->next)
 210         {
 211         // Scan through diff blocks, finding moved sections from left side
 212         // and splitting them out
 213         // That is, we actually fragment diff blocks as we find moved sections
 214                 if(tempdiff->type != svn_diff__type_diff_modified)
 215                         continue;
 216
 217                 EquivalencyGroup * pGroup = NULL;
 218
 219                 int i;
 220                 for(i = (int)tempdiff->original_start; (i - tempdiff->original_start)< tempdiff->original_length; ++i)
 221                 {
 222                         EquivalencyGroup * group = ExtractGroup(map, m_arBaseFile.GetAt(i), dwIgnoreWS);
 223                         if(group->IsPerfectMatch())
 224                         {
 225                                 pGroup = group;
 226                                 break;
 227                         }
 228                 }
 229                 if(!pGroup) // if no match
 230                         continue;
 231                 // found a match
 232                 int j = pGroup->m_LinesRight.GetSingle();
 233                 // Ok, now our moved block is the single line (i, j)
 234
 235                 // extend moved block upward as far as possible
 236                 int i1 = i - 1;
 237                 int j1 = j - 1;
 238                 for(; (i1 >= tempdiff->original_start) && (j1>=0) && (i1>=0); --i1, --j1)
 239                 {
 240                         EquivalencyGroup * pGroup0 = ExtractGroup(map, m_arBaseFile.GetAt(i1), dwIgnoreWS);
 241                         EquivalencyGroup * pGroup1 = ExtractGroup(map, m_arYourFile.GetAt(j1), dwIgnoreWS);
 242                         if(pGroup1 != pGroup0)
 243                                 break;
 244                         pGroup0->m_LinesLeft.Remove(i1);
 245                         pGroup1->m_LinesRight.Remove(j1);
 246                 }
 247                 ++i1;
 248                 ++j1;
 249                 // Ok, now our moved block is (i1..i, j1..j)
 250
 251                 // extend moved block downward as far as possible
 252
 253                 int i2 = i + 1;
 254                 int j2 = j + 1;
 255                 for(; ((i2-tempdiff->original_start) < tempdiff->original_length)&&(j2>=0); ++i2, ++j2)
 256                 {
 257                         if(i2 >= m_arBaseFile.GetCount() || j2 >= m_arYourFile.GetCount())
 258                                 break;
 259                         EquivalencyGroup * pGroup0 = ExtractGroup(map, m_arBaseFile.GetAt(i2), dwIgnoreWS);
 260                         EquivalencyGroup * pGroup1 = ExtractGroup(map, m_arYourFile.GetAt(j2), dwIgnoreWS);
 261                         if(pGroup1 != pGroup0)
 262                                 break;
 263                         pGroup0->m_LinesLeft.Remove(i2);
 264                         pGroup1->m_LinesRight.Remove(j2);
 265                 }
 266                 --i2;
 267                 --j2;
 268                 // Ok, now our moved block is (i1..i2,j1..j2)
 269                 tsvn_svn_diff_t_extension * newTail = CreateDiffExtension(tempdiff, pool);
 270                 if(head == NULL)
 271                 {
 272                         head = newTail;
 273                         tail = head;
 274                 }
 275                 else
 276                 {
 277                         tail->next = newTail;
 278                         tail = newTail;
 279                 }
 280
 281                 int prefix = i1 - (int)tempdiff->original_start;
 282                 if(prefix)
 283                 {
 284                         // break tempdiff (current change) into two pieces
 285                         // first part is the prefix, before the moved part
 286                         // that stays in tempdiff
 287                         // second part is the moved part & anything after it
 288                         // that goes in newob
 289                         // leave the left side (tempdiff->original_length) on tempdiff
 290                         // so no right side on newob
 291                         // newob will be the moved part only, later after we split off any suffix from it
 292                         svn_diff_t * newob = (svn_diff_t *)apr_palloc(pool, sizeof(svn_diff_t));
 293                         memset(newob, 0, sizeof(*newob));
 294
 295                         tail->base = newob;
 296                         newob->type = svn_diff__type_diff_modified;
 297                         newob->original_start = i1;
 298                         newob->modified_start = tempdiff->modified_start + tempdiff->modified_length;
 299                         newob->modified_length = 0;
 300                         newob->original_length = tempdiff->original_length - prefix;
 301                         newob->next = tempdiff->next;
 302
 303                         tempdiff->original_length = prefix;
 304                         tempdiff->next = newob;
 305
 306                         // now make tempdiff point to the moved part (& any suffix)
 307                         tempdiff = newob;
 308                 }
 309
 310                 tail->moved_to = j1;
 311
 312                 apr_off_t suffix = (tempdiff->original_length) - (i2- (tempdiff->original_start)) - 1;
 313                 if (suffix)
 314                 {
 315                         // break off any suffix from tempdiff
 316                         // newob will be the suffix, and will get all the right side
 317                         svn_diff_t * newob = (svn_diff_t *) apr_palloc(pool, sizeof (*newob));
 318                         memset(newob, 0, sizeof(*newob));
 319                         newob->type = svn_diff__type_diff_modified;
 320
 321                         newob->original_start = i2 + 1;
 322                         newob->modified_start = tempdiff->modified_start;
 323                         newob->modified_length = tempdiff->modified_length;
 324                         newob->original_length = suffix;
 325                         newob->next = tempdiff->next;
 326
 327                         tempdiff->modified_length = 0;
 328                         tempdiff->original_length -= suffix;
 329                         tempdiff->next = newob;
 330                 }
 331         }
 332         // Scan through diff blocks, finding moved sections from right side
 333         // and splitting them out
 334         // That is, we actually fragment diff blocks as we find moved sections
 335         tsvn_svn_diff_t_extension * existing = head;
 336         tail = NULL;
 337         for(tempdiff = diffYourBase; tempdiff; tempdiff = tempdiff->next)
 338         {
 339                 // scan down block for a match
 340                 if(tempdiff->type != svn_diff__type_diff_modified)
 341                         continue;
 342
 343                 EquivalencyGroup * pGroup = NULL;
 344                 int j = 0;
 345                 for(j = (int)tempdiff->modified_start; (j - tempdiff->modified_start) < tempdiff->modified_length; ++j)
 346                 {
 347                         EquivalencyGroup * group = ExtractGroup(map, m_arYourFile.GetAt(j), dwIgnoreWS);
 348                         if(group->IsPerfectMatch())
 349                         {
 350                                 pGroup = group;
 351                                 break;
 352                         }
 353                 }
 354
 355                 // if no match, go to next diff block
 356                 if (!pGroup)
 357                 {
 358                         AdjustExistingAndTail(tempdiff, existing, tail);
 359                         continue;
 360                 }
 361
 362                 // found a match
 363                 int i = pGroup->m_LinesLeft.GetSingle();
 364                 if (i == 0)
 365                         continue;
 366                 // Ok, now our moved block is the single line (i,j)
 367
 368                 // extend moved block upward as far as possible
 369                 int i1 = i-1;
 370                 int j1 = j-1;
 371                 for ( ; (j1>=tempdiff->modified_start) && (j1>=0) && (i1>=0); --i1, --j1)
 372                 {
 373                         EquivalencyGroup * pGroup0 = ExtractGroup(map, m_arBaseFile.GetAt(i1), dwIgnoreWS);
 374                         EquivalencyGroup * pGroup1 = ExtractGroup(map, m_arYourFile.GetAt(j1), dwIgnoreWS);
 375                         if (pGroup0 != pGroup1)
 376                                 break;
 377                         pGroup0->m_LinesLeft.Remove(i1);
 378                         pGroup1->m_LinesRight.Remove(j1);
 379                 }
 380                 ++i1;
 381                 ++j1;
 382                 // Ok, now our moved block is (i1..i,j1..j)
 383
 384                 // extend moved block downward as far as possible
 385                 int i2 = i+1;
 386                 int j2 = j+1;
 387                 for ( ; (j2-(tempdiff->modified_start) < tempdiff->modified_length) && (i2>=0); ++i2,++j2)
 388                 {
 389                         if(i2 >= m_arBaseFile.GetCount() || j2 >= m_arYourFile.GetCount())
 390                                 break;
 391                         EquivalencyGroup * pGroup0 = ExtractGroup(map, m_arBaseFile.GetAt(i2), dwIgnoreWS);
 392                         EquivalencyGroup * pGroup1 = ExtractGroup(map, m_arYourFile.GetAt(j2), dwIgnoreWS);
 393                         if (pGroup0 != pGroup1)
 394                                 break;
 395                         pGroup0->m_LinesLeft.Remove(i2);
 396                         pGroup1->m_LinesRight.Remove(j2);
 397                 }
 398                 --i2;
 399                 --j2;
 400                 // Ok, now our moved block is (i1..i2,j1..j2)
 401                 tsvn_svn_diff_t_extension * newTail = NULL;
 402                 if(existing && existing->base == tempdiff)
 403                 {
 404                         newTail = existing;
 405                 }
 406                 else
 407                 {
 408                         newTail = CreateDiffExtension(tempdiff, pool);
 409                         if(head == NULL)
 410                         {
 411                                 head = newTail;
 412                         }
 413                         else if(tail)
 414                         {
 415                                 newTail->next = tail->next;
 416                                 tail->next = newTail;
 417                         }
 418                 }
 419                 tail = newTail;
 420
 421                 apr_off_t prefix = j1 - (tempdiff->modified_start);
 422                 if (prefix)
 423                 {
 424                         // break tempdiff (current change) into two pieces
 425                         // first part is the prefix, before the moved part
 426                         // that stays in tempdiff
 427                         // second part is the moved part & anything after it
 428                         // that goes in newob
 429                         // leave the left side (tempdiff->original_length) on tempdiff
 430                         // so no right side on newob
 431                         // newob will be the moved part only, later after we split off any suffix from it
 432                         svn_diff_t * newob = (svn_diff_t *) apr_palloc(pool, sizeof (*newob));
 433                         memset(newob, 0, sizeof(*newob));
 434                         newob->type = svn_diff__type_diff_modified;
 435
 436                         if(existing == newTail)
 437                         {
 438                                 newTail = CreateDiffExtension(newob, pool);
 439                                 newTail->next = tail->next;
 440                                 tail->next = newTail;
 441                                 tail = newTail;
 442                         }
 443                         tail->base = newob;
 444                         newob->original_start = tempdiff->original_start + tempdiff->original_length;
 445                         newob->modified_start = j1;
 446                         newob->modified_length = tempdiff->modified_length - prefix;
 447                         newob->original_length = 0;
 448                         newob->next = tempdiff->next;
 449
 450                         tempdiff->modified_length = prefix;
 451                         tempdiff->next = newob;
 452
 453                         // now make tempdiff point to the moved part (& any suffix)
 454                         tempdiff = newob;
 455                 }
 456                 // now tempdiff points to a moved diff chunk with no prefix, but maybe a suffix
 457
 458                 tail->moved_from = i1;
 459
 460                 apr_off_t suffix = (tempdiff->modified_length) - (j2-(tempdiff->modified_start)) - 1;
 461                 if (suffix)
 462                 {
 463                         // break off any suffix from tempdiff
 464                         // newob will be the suffix, and will get all the left side
 465                         svn_diff_t * newob = (svn_diff_t *) apr_palloc(pool, sizeof (*newob));
 466                         memset(newob, 0, sizeof(*newob));
 467                         tsvn_svn_diff_t_extension * eNewOb = CreateDiffExtension(newob, pool);
 468
 469                         newob->type = svn_diff__type_diff_modified;
 470                         newob->original_start = tempdiff->original_start;
 471                         newob->modified_start = j2+1;
 472                         newob->modified_length = suffix;
 473                         newob->original_length = tempdiff->original_length;
 474                         newob->next = tempdiff->next;
 475                         eNewOb->moved_from = -1;
 476                         eNewOb->moved_to = tail->moved_to;
 477
 478                         tempdiff->modified_length -= suffix;
 479                         tempdiff->original_length = 0;
 480                         tail->moved_to = -1;
 481                         tempdiff->next = newob;
 482                         eNewOb->next = tail->next;
 483                         tail->next = eNewOb;
 484                         existing = tail = eNewOb;
 485                 }
 486                 AdjustExistingAndTail(tempdiff, existing, tail);
 487         }
 488         return head;
 489 }