Src/MergeDocDiffSync.cpp

   1 /**
   2  * @file  MergeDocDiffSync.cpp
   3  *
   4  * @brief Code to layout diff blocks, to find matching lines, and insert ghost lines
   5  *
   6  */
   7
   8 #include "StdAfx.h"
   9 #include <vector>
  10 #include "MergeDoc.h"
  11
  12 #include "Merge.h"
  13 #include "DiffList.h"
  14 #include "stringdiffs.h"
  15
  16 #ifdef _DEBUG
  17 #define new DEBUG_NEW
  18 #undef THIS_FILE
  19 static char THIS_FILE[] = __FILE__;
  20 #endif
  21
  22 using std::vector;
  23
  24 /**
  25  * @brief Divide diff blocks to match lines in diff blocks.
  26  */
  27 void CMergeDoc::AdjustDiffBlocks()
  28 {
  29         int nDiff;
  30         int nDiffCount = m_diffList.GetSize();
  31
  32         // Go through and do our best to line up lines within each diff block
  33         // between left side and right side
  34         DiffList newDiffList;
  35         newDiffList.Clear();
  36         for (nDiff = 0; nDiff < nDiffCount; nDiff++)
  37         {
  38                 const DIFFRANGE & diffrange = *m_diffList.DiffRangeAt(nDiff);
  39                 // size map correctly (it will hold one entry for each left-side line
  40                 int nlines0 = diffrange.end[0] - diffrange.begin[0] + 1;
  41                 int nlines1 = diffrange.end[1] - diffrange.begin[1] + 1;
  42                 if (nlines0>0 && nlines1>0)
  43                 {
  44                         // Call worker to do all lines in block
  45                         int lo0 = 0, hi0 = nlines0-1;
  46                         int lo1 = 0, hi1 = nlines1-1;
  47                         DiffMap diffmap;
  48                         diffmap.InitDiffMap(nlines0);
  49                         AdjustDiffBlock(diffmap, diffrange, lo0, hi0, lo1, hi1);
  50
  51                         // divide diff blocks
  52                         DIFFRANGE dr;
  53                         int line0, line1, lineend0;
  54                         for (line0 = 0, line1 = 0; line0 < nlines0;)
  55                         {
  56                                 const int map_line0 = diffmap.m_map[line0];
  57                                 if (map_line0 == DiffMap::GHOST_MAP_ENTRY ||
  58                                                 map_line0 == DiffMap::BAD_MAP_ENTRY)
  59                                 {
  60                                         for (lineend0 = line0; lineend0 < nlines0; lineend0++)
  61                                         {
  62                                                 if (map_line0 != DiffMap::GHOST_MAP_ENTRY &&
  63                                                                 map_line0 != DiffMap::BAD_MAP_ENTRY)
  64                                                         break;
  65                                         }
  66                                         dr.begin[0]  = diffrange.begin[0] + line0;
  67                                         dr.begin[1]  = diffrange.begin[1] + line1;
  68                                         dr.end[0]    = diffrange.begin[0] + lineend0 - 1;
  69                                         dr.end[1]    = dr.begin[1] - 1;
  70                                         dr.blank[0]  = dr.blank[1] = -1;
  71                                         dr.op        = OP_DIFF;
  72                                         newDiffList.AddDiff(dr);
  73                                         line0 = lineend0;
  74                                 }
  75                                 else
  76                                 {
  77                                         if (map_line0 > line1)
  78                                         {
  79                                                 dr.begin[0]  = diffrange.begin[0] + line0;
  80                                                 dr.begin[1]  = diffrange.begin[1] + line1;
  81                                                 dr.end[0]    = dr.begin[0] - 1;
  82                                                 dr.end[1]    = diffrange.begin[1] + map_line0 - 1;
  83                                                 dr.blank[0]  = dr.blank[1] = -1;
  84                                                 dr.op        = OP_DIFF;
  85                                                 newDiffList.AddDiff(dr);
  86                                                 line1 = map_line0;
  87                                         }
  88
  89                                         for (lineend0 = line0 + 1; lineend0 < nlines0; lineend0++)
  90                                         {
  91                                                 if (map_line0 != diffmap.m_map[lineend0 - 1] + 1)
  92                                                         break;
  93                                         }
  94                                         dr.begin[0]  = diffrange.begin[0] + line0;
  95                                         dr.begin[1]  = diffrange.begin[1] + line1;
  96                                         dr.end[0]    = diffrange.begin[0] + lineend0 - 1;
  97                                         dr.end[1]    = diffrange.begin[1] + diffmap.m_map[lineend0 - 1];
  98                                         dr.blank[0]  = dr.blank[1] = -1;
  99                                         dr.op        = diffrange.op == OP_TRIVIAL ? OP_TRIVIAL : OP_DIFF;
 100                                         newDiffList.AddDiff(dr);
 101                                         line0 = lineend0;
 102                                         line1 = diffmap.m_map[lineend0 - 1] + 1;
 103                                 }
 104                         }
 105                         if (line1 <= hi1)
 106                         {
 107                                 dr.begin[0]  = diffrange.begin[0] + line0;
 108                                 dr.begin[1]  = diffrange.begin[1] + line1;
 109                                 dr.end[0]    = dr.begin[0] - 1;
 110                                 dr.end[1]    = diffrange.begin[1] + hi1;
 111                                 dr.blank[0]  = dr.blank[1] = -1;
 112                                 dr.op        = diffrange.op == OP_TRIVIAL ? OP_TRIVIAL : OP_DIFF;
 113                                 newDiffList.AddDiff(dr);
 114                         }
 115                 }
 116                 else
 117                 {
 118                         newDiffList.AddDiff(diffrange);
 119                 }
 120         }
 121
 122         // recreate m_diffList
 123         m_diffList.Clear();
 124         nDiffCount = newDiffList.GetSize();
 125         for (nDiff = 0; nDiff < nDiffCount; nDiff++)
 126                 m_diffList.AddDiff(*newDiffList.DiffRangeAt(nDiff));
 127 }
 128
 129 /**
 130  * @brief Return cost of making strings equal
 131  *
 132  * The cost of making them equal is the measure of their dissimilarity
 133  * which is their Levenshtein distance.
 134  */
 135 int CMergeDoc::GetMatchCost(const String &sLine0, const String &sLine1)
 136 {
 137         DIFFOPTIONS diffOptions = {0};
 138         m_diffWrapper.GetOptions(&diffOptions);
 139
 140         String str[2];
 141         str[0] = sLine0;
 142         str[1] = sLine1;
 143
 144         // Options that affect comparison
 145         bool casitive = !diffOptions.bIgnoreCase;
 146         int xwhite = diffOptions.nIgnoreWhitespace;
 147         int breakType = GetBreakType(); // whitespace only or include punctuation
 148         bool byteColoring = GetByteColoringOption();
 149
 150         std::vector<wdiff> worddiffs;
 151         sd_ComputeWordDiffs(2, str, casitive, xwhite, breakType, byteColoring, &worddiffs);
 152
 153         int nDiffLenSum = 0;
 154         for (std::vector<wdiff>::const_iterator it = worddiffs.begin(); it != worddiffs.end(); ++it)
 155         {
 156                 nDiffLenSum += it->end[0] - it->begin[0] + 1;
 157         }
 158
 159         return -static_cast<int>(sLine0.length() - nDiffLenSum);
 160 }
 161
 162 /**
 163  * @brief Map lines from left to right for specified range in diff block, as best we can
 164  * Map left side range [lo0;hi0] to right side range [lo1;hi1]
 165  * (ranges include ends)
 166  *
 167  * Algorithm:
 168  * Find best match, and use that to split problem into two parts (above & below match)
 169  * and call ourselves recursively to solve each smaller problem
 170  */
 171 void CMergeDoc::AdjustDiffBlock(DiffMap & diffMap, const DIFFRANGE & diffrange, int lo0, int hi0, int lo1, int hi1)
 172 {
 173         // Map & lo & hi numbers are all relative to this block
 174         // We need to know offsets to find actual line strings from buffer
 175         int offset0 = diffrange.begin[0];
 176         int offset1 = diffrange.begin[1];
 177
 178         // # of lines on left and right
 179         int lines0 = hi0 - lo0 + 1;
 180         int lines1 = hi1 - lo1 + 1;
 181
 182
 183         ASSERT(lines0 > 0 && lines1 > 0);
 184
 185         // shortcut special case
 186         if (lines0 == 1 && lines1 == 1)
 187         {
 188                 diffMap.m_map[lo0] = hi1;
 189                 return;
 190         }
 191
 192         // Bail out if range is large
 193         if (lines0 > 15 || lines1 > 15)
 194         {
 195                 // Do simple 1:1 mapping
 196                 // but try to stay within original block
 197                 // Cannot be outside both sides, so just test for outside one side
 198                 int tlo=0, thi=0;
 199                 if (lo1 < 0)
 200                 {
 201                         // right side is off the bottom
 202                         // so put it as close to bottom as possible
 203                         tlo = hi1 - (hi0-lo0);
 204                         thi = hi1;
 205                 }
 206                 else
 207                 {
 208                         // put it as close to top as possible
 209                         tlo = lo1;
 210                         thi = lo1 + (hi0-lo0);
 211                 }
 212
 213                 for (int w=0; w<lines0; ++w)
 214                 {
 215                         if (w < lines1)
 216                                 diffMap.m_map[w] = w + tlo;
 217                         else
 218                                 diffMap.m_map[w] = DiffMap::GHOST_MAP_ENTRY;
 219                 }
 220                 return;
 221         }
 222
 223         // Find best fit
 224         int ibest=-1, isavings=0x7fffffff, itarget=-1;
 225         CString sLine0, sLine1;
 226         for (int i=lo0; i<=hi0; ++i)
 227         {
 228                 m_ptBuf[0]->GetLine(offset0 + i, sLine0);
 229                 for (int j=lo1; j<=hi1; ++j)
 230                 {
 231                         m_ptBuf[1]->GetLine(offset1 + j, sLine1);
 232                         int savings = GetMatchCost((LPCTSTR)sLine0, (LPCTSTR)sLine1);
 233                         // TODO
 234                         // Need to penalize assignments that push us outside the box
 235                         // further than is required
 236                         if (savings < isavings)
 237                         {
 238                                 ibest = i;
 239                                 itarget = j;
 240                                 isavings = savings;
 241                         }
 242                 }
 243         }
 244         // I think we have to find at least one
 245         // because cost (Levenshtein distance) is less than or equal to maxlen
 246         // so cost is always nonnegative
 247         ASSERT(ibest >= 0);
 248
 249         ASSERT(diffMap.m_map[ibest] == DiffMap::BAD_MAP_ENTRY);
 250
 251         diffMap.m_map[ibest] = itarget;
 252
 253         // Half of the remaining problem is below our match
 254         if (lo0 < ibest)
 255         {
 256                 if (lo1 < itarget)
 257                 {
 258                         AdjustDiffBlock(diffMap, diffrange, lo0, ibest-1, lo1, itarget-1);
 259                 }
 260                 else
 261                 {
 262                         // No target space for the ones below our match
 263                         for (int x = lo0; x < ibest; ++x)
 264                         {
 265                                 diffMap.m_map[x] = DiffMap::GHOST_MAP_ENTRY;
 266                         }
 267                 }
 268         }
 269
 270         // Half of the remaining problem is above our match
 271         if (hi0 > ibest)
 272         {
 273                 if (itarget < hi1)
 274                 {
 275                         AdjustDiffBlock(diffMap, diffrange, ibest + 1, hi0,
 276                                         itarget + 1, hi1);
 277                 }
 278                 else
 279                 {
 280                         // No target space for the ones above our match
 281                         for (int x = ibest + 1; x <= hi0; ++x)
 282                         {
 283                                 diffMap.m_map[x] = DiffMap::GHOST_MAP_ENTRY;
 284                         }
 285                 }
 286         }
 287 }