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