Src/MovedBlocks.cpp

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