2 * @file MergeDocDiffSync.cpp
4 * @brief Code to layout diff blocks, to find matching lines, and insert ghost lines
14 #include "stringdiffs.h"
23 * @brief Divide diff blocks to match lines in diff blocks.
25 void CMergeDoc::AdjustDiffBlocks()
28 int nDiffCount = m_diffList.GetSize();
30 // Go through and do our best to line up lines within each diff block
31 // between left side and right side
34 for (nDiff = 0; nDiff < nDiffCount; nDiff++)
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)
42 // Call worker to do all lines in block
43 int lo0 = 0, hi0 = nlines0-1;
44 int lo1 = 0, hi1 = nlines1-1;
46 diffmap.InitDiffMap(nlines0);
47 AdjustDiffBlock(diffmap, diffrange, lo0, hi0, lo1, hi1);
51 int line0, line1, lineend0;
52 for (line0 = 0, line1 = 0; line0 < nlines0;)
54 const int map_line0 = diffmap.m_map[line0];
55 if (map_line0 == DiffMap::GHOST_MAP_ENTRY ||
56 map_line0 == DiffMap::BAD_MAP_ENTRY)
58 for (lineend0 = line0; lineend0 < nlines0; lineend0++)
60 const int map_lineend0 = diffmap.m_map[lineend0];
61 if (map_lineend0 != DiffMap::GHOST_MAP_ENTRY &&
62 map_lineend0 != DiffMap::BAD_MAP_ENTRY)
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;
71 newDiffList.AddDiff(dr);
76 if (map_line0 > line1)
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;
84 newDiffList.AddDiff(dr);
88 for (lineend0 = line0 + 1; lineend0 < nlines0; lineend0++)
90 if (map_line0 != diffmap.m_map[lineend0 - 1] + 1)
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);
101 line1 = diffmap.m_map[lineend0 - 1] + 1;
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);
117 newDiffList.AddDiff(diffrange);
121 // recreate m_diffList
123 nDiffCount = newDiffList.GetSize();
124 for (nDiff = 0; nDiff < nDiffCount; nDiff++)
125 m_diffList.AddDiff(*newDiffList.DiffRangeAt(nDiff));
129 * @brief Return cost of making strings equal
131 * The cost of making them equal is the measure of their dissimilarity
132 * which is their Levenshtein distance.
134 int CMergeDoc::GetMatchCost(const String &sLine0, const String &sLine1)
136 DIFFOPTIONS diffOptions = {0};
137 m_diffWrapper.GetOptions(&diffOptions);
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();
150 std::vector<strdiff::wdiff> worddiffs = strdiff::ComputeWordDiffs(2, str, casitive, eolSensitive, xwhite, breakType, byteColoring);
153 for (std::vector<strdiff::wdiff>::const_iterator it = worddiffs.begin(); it != worddiffs.end(); ++it)
155 nDiffLenSum += it->end[0] - it->begin[0] + 1;
158 return -static_cast<int>(sLine0.length() - nDiffLenSum);
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)
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
170 void CMergeDoc::AdjustDiffBlock(DiffMap & diffMap, const DIFFRANGE & diffrange, int lo0, int hi0, int lo1, int hi1)
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];
177 // # of lines on left and right
178 int lines0 = hi0 - lo0 + 1;
179 int lines1 = hi1 - lo1 + 1;
182 ASSERT(lines0 > 0 && lines1 > 0);
184 // shortcut special case
185 if (lines0 == 1 && lines1 == 1)
187 diffMap.m_map[lo0] = hi1;
191 // Bail out if range is large
192 if (lines0 > 15 || lines1 > 15)
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
200 // right side is off the bottom
201 // so put it as close to bottom as possible
202 tlo = hi1 - (hi0-lo0);
207 // put it as close to top as possible
209 thi = lo1 + (hi0-lo0);
212 for (int w=0; w<lines0; ++w)
215 diffMap.m_map[w] = w + tlo;
217 diffMap.m_map[w] = DiffMap::GHOST_MAP_ENTRY;
223 int ibest=-1, isavings=0x7fffffff, itarget=-1;
224 CString sLine0, sLine1;
225 for (int i=lo0; i<=hi0; ++i)
227 m_ptBuf[0]->GetLine(offset0 + i, sLine0);
228 for (int j=lo1; j<=hi1; ++j)
230 m_ptBuf[1]->GetLine(offset1 + j, sLine1);
231 int savings = GetMatchCost((LPCTSTR)sLine0, (LPCTSTR)sLine1);
233 // Need to penalize assignments that push us outside the box
234 // further than is required
235 if (savings < isavings)
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
248 ASSERT(diffMap.m_map[ibest] == DiffMap::BAD_MAP_ENTRY);
250 diffMap.m_map[ibest] = itarget;
252 // Half of the remaining problem is below our match
257 AdjustDiffBlock(diffMap, diffrange, lo0, ibest-1, lo1, itarget-1);
261 // No target space for the ones below our match
262 for (int x = lo0; x < ibest; ++x)
264 diffMap.m_map[x] = DiffMap::GHOST_MAP_ENTRY;
269 // Half of the remaining problem is above our match
274 AdjustDiffBlock(diffMap, diffrange, ibest + 1, hi0,
279 // No target space for the ones above our match
280 for (int x = ibest + 1; x <= hi0; ++x)
282 diffMap.m_map[x] = DiffMap::GHOST_MAP_ENTRY;