Src/MovedBlocks.cpp

   1 // SPDX-License-Identifier: GPL-2.0-or-later
   2 /**
   3  * @file  MovedBlocks.cpp
   4  *
   5  * @brief Moved block detection code.
   6  */
   7
   8 #include "pch.h"
   9 #include <map>
  10 #include <cassert>
  11 #include "diff.h"
  12
  13 class IntSet
  14 {
  15 public:
  16         void Add(int val) { m_map[val] = 1; }
  17         void Remove(int val) { m_map.erase(val); }
  18         size_t count() const { return m_map.size(); }
  19         bool isPresent(int val) const { return m_map.find(val) != m_map.end(); }
  20         int getSingle() const { return m_map.begin()->first; }
  21 private:
  22         std::map<int, int> m_map;
  23 };
  24
  25 /**
  26  * @brief  Set of equivalent lines
  27  * This uses diffutils line numbers, which are counted from the prefix
  28  */
  29 struct EqGroup
  30 {
  31         IntSet m_lines0; // equivalent lines on side#0
  32         IntSet m_lines1; // equivalent lines on side#1
  33
  34         bool isPerfectMatch() const { return m_lines0.count()==1 && m_lines1.count()==1; }
  35 };
  36
  37
  38 /** @brief  Maps equivalency code to equivalency group */
  39 class CodeToGroupMap
  40 {
  41 public:
  42         std::map<int, EqGroup *> m_map;
  43         /** @brief Add a line to the appropriate equivalency group */
  44         void Add(int lineno, int eqcode, int nside)
  45         {
  46                 EqGroup *pgroup = find(eqcode);
  47                 if (pgroup == nullptr)
  48                 {
  49                         pgroup = new EqGroup;
  50                         m_map[eqcode] = pgroup;
  51                 }
  52                 if (nside)
  53                         pgroup->m_lines1.Add(lineno);
  54                 else
  55                         pgroup->m_lines0.Add(lineno);
  56         }
  57
  58         /** @brief Return the appropriate equivalency group */
  59         EqGroup * find(int eqcode)
  60         {
  61                 std::map<int, EqGroup *>::const_iterator it = m_map.find(eqcode);
  62                 return it != m_map.end() ? it->second : nullptr;
  63         }
  64
  65         ~CodeToGroupMap()
  66         {
  67                 std::map<int, EqGroup *>::const_iterator pos = m_map.begin();
  68                 while (pos != m_map.end())
  69                         delete pos++->second;
  70         }
  71 };
  72
  73 static bool isLineInDiffBlock(int nside, int lineno, change *script)
  74 {
  75         change *p = nullptr;
  76         for (change *e = script; e; e = p)
  77         {
  78                 p = e->link;
  79                 if (nside == 0)
  80                 {
  81                         if (e->line0 <= lineno && lineno < e->line0 + e->deleted)
  82                                 return true;
  83                 }
  84                 else
  85                 {
  86                         if (e->line1 <= lineno && lineno < e->line1 + e->inserted)
  87                                 return true;
  88                 }
  89         }
  90         return false;
  91 }
  92
  93 /*
  94  WinMerge moved block code
  95  This is called by diffutils code, by diff_2_files routine (in ANALYZE.C)
  96  read_files earlier computed the hash chains ("equivs" file variable) and freed them,
  97  but the equivs numerics are still available in each line
  98
  99  match1 set by scan from line0 to deleted
 100  match0 set by scan from line1 to inserted
 101
 102 */
 103 extern "C" void moved_block_analysis(struct change ** pscript, struct file_data fd[])
 104 {
 105         // Hash all altered lines
 106         CodeToGroupMap map;
 107
 108         struct change * script = *pscript;
 109         struct change *p,*e;
 110         for (e = script; e; e = p)
 111         {
 112                 p = e->link;
 113                 int i=0;
 114                 for (i = e->line0; i - (e->line0) < (e->deleted); ++i)
 115                         map.Add(i, fd[0].equivs[i], 0);
 116                 for (i = e->line1; i - (e->line1) < (e->inserted); ++i)
 117                         map.Add(i, fd[1].equivs[i], 1);
 118         }
 119
 120
 121         // Scan through diff blocks, finding moved sections from left side
 122         // and splitting them out
 123         // That is, we actually fragment diff blocks as we find moved sections
 124         for (e = script; e; e = p)
 125         {
 126                 // scan down block for a match
 127                 p = e->link;
 128                 EqGroup * pgroup = nullptr;
 129                 int i=0;
 130                 for (i=e->line0; i-(e->line0) < (e->deleted); ++i)
 131                 {
 132                         EqGroup * tempgroup = map.find(fd[0].equivs[i]);
 133                         if (tempgroup->isPerfectMatch())
 134                         {
 135                                 pgroup = tempgroup;
 136                                 break;
 137                         }
 138                 }
 139
 140                 // if no match, go to next diff block
 141                 if (pgroup == nullptr)
 142                         continue;
 143
 144                 // found a match
 145                 int j = pgroup->m_lines1.getSingle();
 146                 // Ok, now our moved block is the single line i,j
 147
 148                 // extend moved block upward as far as possible
 149                 int i1 = i-1;
 150                 int j1 = j-1;
 151                 for ( ; i1>=e->line0; --i1, --j1)
 152                 {
 153                         EqGroup * pgroup0 = map.find(fd[0].equivs[i1]);
 154                         EqGroup * pgroup1 = map.find(fd[1].equivs[j1]);
 155                         if (pgroup0 != pgroup1 || !isLineInDiffBlock(1, j1, script))
 156                                 break;
 157 //                      pgroup0->m_lines0.Remove(i1); // commented out this line although I'm not sure what this line means because this line causes the bug sf.net#2174
 158 //                      pgroup1->m_lines1.Remove(j1);
 159                 }
 160                 ++i1;
 161                 ++j1;
 162                 // Ok, now our moved block is i1->i, j1->j
 163
 164                 // extend moved block downward as far as possible
 165                 int i2 = i+1;
 166                 int j2 = j+1;
 167                 for ( ; i2-(e->line0) < (e->deleted); ++i2,++j2)
 168                 {
 169                         EqGroup * pgroup0 = map.find(fd[0].equivs[i2]);
 170                         EqGroup * pgroup1 = map.find(fd[1].equivs[j2]);
 171                         if (pgroup0 != pgroup1 || !isLineInDiffBlock(1, j2, script))
 172                                 break;
 173 //                      pgroup0->m_lines0.Remove(i2); // commented out this line although I'm not sure what this line means because this line causes the bug sf.net#2174
 174 //                      pgroup1->m_lines1.Remove(j2);
 175                 }
 176                 --i2;
 177                 --j2;
 178                 // Ok, now our moved block is i1->i2,j1->j2
 179
 180                 assert(i2-i1 >= 0);
 181                 assert(i2-i1 == j2-j1);
 182
 183                 int prefix = i1 - (e->line0);
 184                 if (prefix)
 185                 {
 186                         // break e (current change) into two pieces
 187                         // first part is the prefix, before the moved part
 188                         // that stays in e
 189                         // second part is the moved part & anything after it
 190                         // that goes in newob
 191                         // leave the right side (e->inserted) on e
 192                         // so no right side on newob
 193                         // newob will be the moved part only, later after we split off any suffix from it
 194                         struct change *newob = (struct change *) xmalloc (sizeof (struct change));
 195                         *newob = {};
 196
 197                         newob->line0 = i1;
 198                         newob->line1 = e->line1 + e->inserted;
 199                         newob->inserted = 0;
 200                         newob->deleted = e->deleted - prefix;
 201                         newob->link = e->link;
 202                         newob->match0 = -1;
 203                         newob->match1 = -1;
 204
 205                         e->deleted = prefix;
 206                         e->link = newob;
 207
 208                         // now make e point to the moved part (& any suffix)
 209                         e = newob;
 210                 }
 211                 // now e points to a moved diff chunk with no prefix, but maybe a suffix
 212
 213                 e->match1 = j1;
 214
 215                 int suffix = (e->deleted) - (i2-(e->line0)) - 1;
 216                 if (suffix)
 217                 {
 218                         // break off any suffix from e
 219                         // newob will be the suffix, and will get all the right side
 220                         struct change *newob = (struct change *) xmalloc (sizeof (struct change));
 221                         *newob = {};
 222
 223                         newob->line0 = i2+1;
 224                         newob->line1 = e->line1;
 225                         newob->inserted = e->inserted;
 226                         newob->deleted = suffix;
 227                         newob->link = e->link;
 228                         newob->match0 = -1;
 229                         newob->match1 = -1;
 230
 231                         e->inserted = 0;
 232                         e->deleted -= suffix;
 233                         e->link = newob;
 234
 235                         p = newob; // next block to scan
 236                 }
 237         }
 238
 239         // Scan through diff blocks, finding moved sections from right side
 240         // and splitting them out
 241         // That is, we actually fragment diff blocks as we find moved sections
 242         for (e = script; e; e = p)
 243         {
 244                 // scan down block for a match
 245                 p = e->link;
 246                 EqGroup * pgroup = nullptr;
 247                 int j=0;
 248                 for (j=e->line1; j-(e->line1) < (e->inserted); ++j)
 249                 {
 250                         EqGroup * tempgroup = map.find(fd[1].equivs[j]);
 251                         if (tempgroup->isPerfectMatch())
 252                         {
 253                                 pgroup = tempgroup;
 254                                 break;
 255                         }
 256                 }
 257
 258                 // if no match, go to next diff block
 259                 if (pgroup == nullptr)
 260                         continue;
 261
 262                 // found a match
 263                 int i = pgroup->m_lines0.getSingle();
 264                 // Ok, now our moved block is the single line i,j
 265
 266                 // extend moved block upward as far as possible
 267                 int i1 = i-1;
 268                 int j1 = j-1;
 269                 for ( ; j1>=e->line1; --i1, --j1)
 270                 {
 271                         EqGroup * pgroup0 = map.find(fd[0].equivs[i1]);
 272                         EqGroup * pgroup1 = map.find(fd[1].equivs[j1]);
 273                         if (pgroup0 != pgroup1 || !isLineInDiffBlock(0, i1, script))
 274                                 break;
 275 //                      pgroup0->m_lines0.Remove(i1); // commented out this line although I'm not sure what this line means because this line causes the bug sf.net#2174
 276 //                      pgroup1->m_lines1.Remove(j1);
 277                 }
 278                 ++i1;
 279                 ++j1;
 280                 // Ok, now our moved block is i1->i, j1->j
 281
 282                 // extend moved block downward as far as possible
 283                 int i2 = i+1;
 284                 int j2 = j+1;
 285                 for ( ; j2-(e->line1) < (e->inserted); ++i2,++j2)
 286                 {
 287                         EqGroup * pgroup0 = map.find(fd[0].equivs[i2]);
 288                         EqGroup * pgroup1 = map.find(fd[1].equivs[j2]);
 289                         if (pgroup0 != pgroup1 || !isLineInDiffBlock(0, i2, script))
 290                                 break;
 291 //                      pgroup0->m_lines0.Remove(i2); // commented out this line although I'm not sure what this line means because this line causes the bug sf.net#2174
 292 //                      pgroup1->m_lines1.Remove(j2);
 293                 }
 294                 --i2;
 295                 --j2;
 296                 // Ok, now our moved block is i1->i2,j1->j2
 297
 298                 assert(i2-i1 >= 0);
 299                 assert(i2-i1 == j2-j1);
 300
 301                 int prefix = j1 - (e->line1);
 302                 if (prefix)
 303                 {
 304                         // break e (current change) into two pieces
 305                         // first part is the prefix, before the moved part
 306                         // that stays in e
 307                         // second part is the moved part & anything after it
 308                         // that goes in newob
 309                         // leave the left side (e->deleted) on e
 310                         // so no right side on newob
 311                         // newob will be the moved part only, later after we split off any suffix from it
 312                         struct change *newob = (struct change *) xmalloc (sizeof (struct change));
 313                         *newob = {};
 314
 315                         newob->line0 = e->line0 + e->deleted;
 316                         newob->line1 = j1;
 317                         newob->inserted = e->inserted - prefix;
 318                         newob->deleted = 0;
 319                         newob->link = e->link;
 320                         newob->match0 = -1;
 321                         newob->match1 = -1;
 322
 323                         e->inserted = prefix;
 324                         e->link = newob;
 325
 326                         // now make e point to the moved part (& any suffix)
 327                         e = newob;
 328                 }
 329                 // now e points to a moved diff chunk with no prefix, but maybe a suffix
 330
 331                 e->match0 = i1;
 332
 333                 int suffix = (e->inserted) - (j2-(e->line1)) - 1;
 334                 if (suffix)
 335                 {
 336                         // break off any suffix from e
 337                         // newob will be the suffix, and will get all the left side
 338                         struct change *newob = (struct change *) xmalloc (sizeof (struct change));
 339                         *newob = {};
 340
 341                         newob->line0 = e->line0;
 342                         newob->line1 = j2+1;
 343                         newob->inserted = suffix;
 344                         newob->deleted = e->deleted;
 345                         newob->link = e->link;
 346                         newob->match0 = -1;
 347                         newob->match1 = e->match1;
 348
 349                         e->inserted -= suffix;
 350                         e->deleted = 0;
 351                         e->match1 = -1;
 352                         e->link = newob;
 353
 354                         p = newob; // next block to scan
 355                 }
 356         }
 357
 358 }