| author | Jun Wu <quark@fb.com> |
| Wed, 07 Mar 2018 14:45:31 -0800 | |
| changeset 36820 | f33a87cf60cc |
| parent 36763 | 90f8fe72446c |
| child 36822 | 882657a9f768 |
| permissions | -rw-r--r-- |
| 36671 | 1 |
/* |
2 |
* LibXDiff by Davide Libenzi ( File Differential Library ) |
|
3 |
* Copyright (C) 2003 Davide Libenzi |
|
4 |
* |
|
5 |
* This library is free software; you can redistribute it and/or |
|
6 |
* modify it under the terms of the GNU Lesser General Public |
|
7 |
* License as published by the Free Software Foundation; either |
|
8 |
* version 2.1 of the License, or (at your option) any later version. |
|
9 |
* |
|
10 |
* This library is distributed in the hope that it will be useful, |
|
11 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of |
|
12 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
|
13 |
* Lesser General Public License for more details. |
|
14 |
* |
|
15 |
* You should have received a copy of the GNU Lesser General Public |
|
16 |
* License along with this library; if not, see |
|
17 |
* <http://www.gnu.org/licenses/>. |
|
18 |
* |
|
19 |
* Davide Libenzi <davidel@xmailserver.org> |
|
20 |
* |
|
21 |
*/ |
|
22 |
||
23 |
#include "xinclude.h" |
|
24 |
||
25 |
||
26 |
||
27 |
#define XDL_MAX_COST_MIN 256 |
|
28 |
#define XDL_HEUR_MIN_COST 256 |
|
29 |
#define XDL_LINE_MAX (long)((1UL << (CHAR_BIT * sizeof(long) - 1)) - 1) |
|
30 |
#define XDL_SNAKE_CNT 20 |
|
31 |
#define XDL_K_HEUR 4 |
|
32 |
||
|
36723
1f9bbd1d6b8a
xdiff: fix builds on Windows
Matt Harbison <matt_harbison@yahoo.com>
parents:
36674
diff
changeset
|
33 |
/* VC 2008 doesn't know about the inline keyword. */ |
|
1f9bbd1d6b8a
xdiff: fix builds on Windows
Matt Harbison <matt_harbison@yahoo.com>
parents:
36674
diff
changeset
|
34 |
#if defined(_MSC_VER) |
|
1f9bbd1d6b8a
xdiff: fix builds on Windows
Matt Harbison <matt_harbison@yahoo.com>
parents:
36674
diff
changeset
|
35 |
#define inline __forceinline |
|
1f9bbd1d6b8a
xdiff: fix builds on Windows
Matt Harbison <matt_harbison@yahoo.com>
parents:
36674
diff
changeset
|
36 |
#endif |
| 36671 | 37 |
|
38 |
||
39 |
typedef struct s_xdpsplit { |
|
40 |
long i1, i2; |
|
41 |
int min_lo, min_hi; |
|
42 |
} xdpsplit_t; |
|
43 |
||
44 |
||
45 |
||
46 |
||
47 |
static long xdl_split(unsigned long const *ha1, long off1, long lim1, |
|
48 |
unsigned long const *ha2, long off2, long lim2, |
|
49 |
long *kvdf, long *kvdb, int need_min, xdpsplit_t *spl, |
|
50 |
xdalgoenv_t *xenv); |
|
51 |
static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, long chg2); |
|
52 |
||
53 |
||
54 |
||
55 |
||
56 |
||
57 |
/* |
|
58 |
* See "An O(ND) Difference Algorithm and its Variations", by Eugene Myers. |
|
59 |
* Basically considers a "box" (off1, off2, lim1, lim2) and scan from both |
|
60 |
* the forward diagonal starting from (off1, off2) and the backward diagonal |
|
61 |
* starting from (lim1, lim2). If the K values on the same diagonal crosses |
|
62 |
* returns the furthest point of reach. We might end up having to expensive |
|
63 |
* cases using this algorithm is full, so a little bit of heuristic is needed |
|
64 |
* to cut the search and to return a suboptimal point. |
|
65 |
*/ |
|
66 |
static long xdl_split(unsigned long const *ha1, long off1, long lim1, |
|
67 |
unsigned long const *ha2, long off2, long lim2, |
|
68 |
long *kvdf, long *kvdb, int need_min, xdpsplit_t *spl, |
|
69 |
xdalgoenv_t *xenv) { |
|
70 |
long dmin = off1 - lim2, dmax = lim1 - off2; |
|
71 |
long fmid = off1 - off2, bmid = lim1 - lim2; |
|
72 |
long odd = (fmid - bmid) & 1; |
|
73 |
long fmin = fmid, fmax = fmid; |
|
74 |
long bmin = bmid, bmax = bmid; |
|
75 |
long ec, d, i1, i2, prev1, best, dd, v, k; |
|
76 |
||
77 |
/* |
|
78 |
* Set initial diagonal values for both forward and backward path. |
|
79 |
*/ |
|
80 |
kvdf[fmid] = off1; |
|
81 |
kvdb[bmid] = lim1; |
|
82 |
||
83 |
for (ec = 1;; ec++) { |
|
84 |
int got_snake = 0; |
|
85 |
||
86 |
/* |
|
87 |
* We need to extent the diagonal "domain" by one. If the next |
|
88 |
* values exits the box boundaries we need to change it in the |
|
89 |
* opposite direction because (max - min) must be a power of two. |
|
90 |
* Also we initialize the external K value to -1 so that we can |
|
91 |
* avoid extra conditions check inside the core loop. |
|
92 |
*/ |
|
93 |
if (fmin > dmin) |
|
94 |
kvdf[--fmin - 1] = -1; |
|
95 |
else |
|
96 |
++fmin; |
|
97 |
if (fmax < dmax) |
|
98 |
kvdf[++fmax + 1] = -1; |
|
99 |
else |
|
100 |
--fmax; |
|
101 |
||
102 |
for (d = fmax; d >= fmin; d -= 2) { |
|
103 |
if (kvdf[d - 1] >= kvdf[d + 1]) |
|
104 |
i1 = kvdf[d - 1] + 1; |
|
105 |
else |
|
106 |
i1 = kvdf[d + 1]; |
|
107 |
prev1 = i1; |
|
108 |
i2 = i1 - d; |
|
109 |
for (; i1 < lim1 && i2 < lim2 && ha1[i1] == ha2[i2]; i1++, i2++); |
|
110 |
if (i1 - prev1 > xenv->snake_cnt) |
|
111 |
got_snake = 1; |
|
112 |
kvdf[d] = i1; |
|
113 |
if (odd && bmin <= d && d <= bmax && kvdb[d] <= i1) { |
|
114 |
spl->i1 = i1; |
|
115 |
spl->i2 = i2; |
|
116 |
spl->min_lo = spl->min_hi = 1; |
|
117 |
return ec; |
|
118 |
} |
|
119 |
} |
|
120 |
||
121 |
/* |
|
122 |
* We need to extent the diagonal "domain" by one. If the next |
|
123 |
* values exits the box boundaries we need to change it in the |
|
124 |
* opposite direction because (max - min) must be a power of two. |
|
125 |
* Also we initialize the external K value to -1 so that we can |
|
126 |
* avoid extra conditions check inside the core loop. |
|
127 |
*/ |
|
128 |
if (bmin > dmin) |
|
129 |
kvdb[--bmin - 1] = XDL_LINE_MAX; |
|
130 |
else |
|
131 |
++bmin; |
|
132 |
if (bmax < dmax) |
|
133 |
kvdb[++bmax + 1] = XDL_LINE_MAX; |
|
134 |
else |
|
135 |
--bmax; |
|
136 |
||
137 |
for (d = bmax; d >= bmin; d -= 2) { |
|
138 |
if (kvdb[d - 1] < kvdb[d + 1]) |
|
139 |
i1 = kvdb[d - 1]; |
|
140 |
else |
|
141 |
i1 = kvdb[d + 1] - 1; |
|
142 |
prev1 = i1; |
|
143 |
i2 = i1 - d; |
|
144 |
for (; i1 > off1 && i2 > off2 && ha1[i1 - 1] == ha2[i2 - 1]; i1--, i2--); |
|
145 |
if (prev1 - i1 > xenv->snake_cnt) |
|
146 |
got_snake = 1; |
|
147 |
kvdb[d] = i1; |
|
148 |
if (!odd && fmin <= d && d <= fmax && i1 <= kvdf[d]) { |
|
149 |
spl->i1 = i1; |
|
150 |
spl->i2 = i2; |
|
151 |
spl->min_lo = spl->min_hi = 1; |
|
152 |
return ec; |
|
153 |
} |
|
154 |
} |
|
155 |
||
156 |
if (need_min) |
|
157 |
continue; |
|
158 |
||
159 |
/* |
|
160 |
* If the edit cost is above the heuristic trigger and if |
|
161 |
* we got a good snake, we sample current diagonals to see |
|
162 |
* if some of the, have reached an "interesting" path. Our |
|
163 |
* measure is a function of the distance from the diagonal |
|
164 |
* corner (i1 + i2) penalized with the distance from the |
|
165 |
* mid diagonal itself. If this value is above the current |
|
166 |
* edit cost times a magic factor (XDL_K_HEUR) we consider |
|
167 |
* it interesting. |
|
168 |
*/ |
|
169 |
if (got_snake && ec > xenv->heur_min) { |
|
170 |
for (best = 0, d = fmax; d >= fmin; d -= 2) { |
|
171 |
dd = d > fmid ? d - fmid: fmid - d; |
|
172 |
i1 = kvdf[d]; |
|
173 |
i2 = i1 - d; |
|
174 |
v = (i1 - off1) + (i2 - off2) - dd; |
|
175 |
||
176 |
if (v > XDL_K_HEUR * ec && v > best && |
|
177 |
off1 + xenv->snake_cnt <= i1 && i1 < lim1 && |
|
178 |
off2 + xenv->snake_cnt <= i2 && i2 < lim2) { |
|
179 |
for (k = 1; ha1[i1 - k] == ha2[i2 - k]; k++) |
|
180 |
if (k == xenv->snake_cnt) { |
|
181 |
best = v; |
|
182 |
spl->i1 = i1; |
|
183 |
spl->i2 = i2; |
|
184 |
break; |
|
185 |
} |
|
186 |
} |
|
187 |
} |
|
188 |
if (best > 0) { |
|
189 |
spl->min_lo = 1; |
|
190 |
spl->min_hi = 0; |
|
191 |
return ec; |
|
192 |
} |
|
193 |
||
194 |
for (best = 0, d = bmax; d >= bmin; d -= 2) { |
|
195 |
dd = d > bmid ? d - bmid: bmid - d; |
|
196 |
i1 = kvdb[d]; |
|
197 |
i2 = i1 - d; |
|
198 |
v = (lim1 - i1) + (lim2 - i2) - dd; |
|
199 |
||
200 |
if (v > XDL_K_HEUR * ec && v > best && |
|
201 |
off1 < i1 && i1 <= lim1 - xenv->snake_cnt && |
|
202 |
off2 < i2 && i2 <= lim2 - xenv->snake_cnt) { |
|
203 |
for (k = 0; ha1[i1 + k] == ha2[i2 + k]; k++) |
|
204 |
if (k == xenv->snake_cnt - 1) { |
|
205 |
best = v; |
|
206 |
spl->i1 = i1; |
|
207 |
spl->i2 = i2; |
|
208 |
break; |
|
209 |
} |
|
210 |
} |
|
211 |
} |
|
212 |
if (best > 0) { |
|
213 |
spl->min_lo = 0; |
|
214 |
spl->min_hi = 1; |
|
215 |
return ec; |
|
216 |
} |
|
217 |
} |
|
218 |
||
219 |
/* |
|
220 |
* Enough is enough. We spent too much time here and now we collect |
|
221 |
* the furthest reaching path using the (i1 + i2) measure. |
|
222 |
*/ |
|
223 |
if (ec >= xenv->mxcost) { |
|
224 |
long fbest, fbest1, bbest, bbest1; |
|
225 |
||
226 |
fbest = fbest1 = -1; |
|
227 |
for (d = fmax; d >= fmin; d -= 2) { |
|
228 |
i1 = XDL_MIN(kvdf[d], lim1); |
|
229 |
i2 = i1 - d; |
|
230 |
if (lim2 < i2) |
|
231 |
i1 = lim2 + d, i2 = lim2; |
|
232 |
if (fbest < i1 + i2) { |
|
233 |
fbest = i1 + i2; |
|
234 |
fbest1 = i1; |
|
235 |
} |
|
236 |
} |
|
237 |
||
238 |
bbest = bbest1 = XDL_LINE_MAX; |
|
239 |
for (d = bmax; d >= bmin; d -= 2) { |
|
240 |
i1 = XDL_MAX(off1, kvdb[d]); |
|
241 |
i2 = i1 - d; |
|
242 |
if (i2 < off2) |
|
243 |
i1 = off2 + d, i2 = off2; |
|
244 |
if (i1 + i2 < bbest) { |
|
245 |
bbest = i1 + i2; |
|
246 |
bbest1 = i1; |
|
247 |
} |
|
248 |
} |
|
249 |
||
250 |
if ((lim1 + lim2) - bbest < fbest - (off1 + off2)) { |
|
251 |
spl->i1 = fbest1; |
|
252 |
spl->i2 = fbest - fbest1; |
|
253 |
spl->min_lo = 1; |
|
254 |
spl->min_hi = 0; |
|
255 |
} else { |
|
256 |
spl->i1 = bbest1; |
|
257 |
spl->i2 = bbest - bbest1; |
|
258 |
spl->min_lo = 0; |
|
259 |
spl->min_hi = 1; |
|
260 |
} |
|
261 |
return ec; |
|
262 |
} |
|
263 |
} |
|
264 |
} |
|
265 |
||
266 |
||
267 |
/* |
|
268 |
* Rule: "Divide et Impera". Recursively split the box in sub-boxes by calling |
|
269 |
* the box splitting function. Note that the real job (marking changed lines) |
|
270 |
* is done in the two boundary reaching checks. |
|
271 |
*/ |
|
272 |
int xdl_recs_cmp(diffdata_t *dd1, long off1, long lim1, |
|
273 |
diffdata_t *dd2, long off2, long lim2, |
|
274 |
long *kvdf, long *kvdb, int need_min, xdalgoenv_t *xenv) { |
|
275 |
unsigned long const *ha1 = dd1->ha, *ha2 = dd2->ha; |
|
276 |
||
277 |
/* |
|
278 |
* Shrink the box by walking through each diagonal snake (SW and NE). |
|
279 |
*/ |
|
280 |
for (; off1 < lim1 && off2 < lim2 && ha1[off1] == ha2[off2]; off1++, off2++); |
|
281 |
for (; off1 < lim1 && off2 < lim2 && ha1[lim1 - 1] == ha2[lim2 - 1]; lim1--, lim2--); |
|
282 |
||
283 |
/* |
|
284 |
* If one dimension is empty, then all records on the other one must |
|
285 |
* be obviously changed. |
|
286 |
*/ |
|
287 |
if (off1 == lim1) { |
|
288 |
char *rchg2 = dd2->rchg; |
|
289 |
long *rindex2 = dd2->rindex; |
|
290 |
||
291 |
for (; off2 < lim2; off2++) |
|
292 |
rchg2[rindex2[off2]] = 1; |
|
293 |
} else if (off2 == lim2) { |
|
294 |
char *rchg1 = dd1->rchg; |
|
295 |
long *rindex1 = dd1->rindex; |
|
296 |
||
297 |
for (; off1 < lim1; off1++) |
|
298 |
rchg1[rindex1[off1]] = 1; |
|
299 |
} else { |
|
300 |
xdpsplit_t spl; |
|
301 |
spl.i1 = spl.i2 = 0; |
|
302 |
||
303 |
/* |
|
304 |
* Divide ... |
|
305 |
*/ |
|
306 |
if (xdl_split(ha1, off1, lim1, ha2, off2, lim2, kvdf, kvdb, |
|
307 |
need_min, &spl, xenv) < 0) { |
|
308 |
||
309 |
return -1; |
|
310 |
} |
|
311 |
||
312 |
/* |
|
313 |
* ... et Impera. |
|
314 |
*/ |
|
315 |
if (xdl_recs_cmp(dd1, off1, spl.i1, dd2, off2, spl.i2, |
|
316 |
kvdf, kvdb, spl.min_lo, xenv) < 0 || |
|
317 |
xdl_recs_cmp(dd1, spl.i1, lim1, dd2, spl.i2, lim2, |
|
318 |
kvdf, kvdb, spl.min_hi, xenv) < 0) { |
|
319 |
||
320 |
return -1; |
|
321 |
} |
|
322 |
} |
|
323 |
||
324 |
return 0; |
|
325 |
} |
|
326 |
||
327 |
||
328 |
int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, |
|
329 |
xdfenv_t *xe) { |
|
330 |
long ndiags; |
|
331 |
long *kvd, *kvdf, *kvdb; |
|
332 |
xdalgoenv_t xenv; |
|
333 |
diffdata_t dd1, dd2; |
|
334 |
||
335 |
if (xdl_prepare_env(mf1, mf2, xpp, xe) < 0) { |
|
336 |
||
337 |
return -1; |
|
338 |
} |
|
339 |
||
340 |
/* |
|
341 |
* Allocate and setup K vectors to be used by the differential algorithm. |
|
342 |
* One is to store the forward path and one to store the backward path. |
|
343 |
*/ |
|
344 |
ndiags = xe->xdf1.nreff + xe->xdf2.nreff + 3; |
|
345 |
if (!(kvd = (long *) xdl_malloc((2 * ndiags + 2) * sizeof(long)))) { |
|
346 |
||
347 |
xdl_free_env(xe); |
|
348 |
return -1; |
|
349 |
} |
|
350 |
kvdf = kvd; |
|
351 |
kvdb = kvdf + ndiags; |
|
352 |
kvdf += xe->xdf2.nreff + 1; |
|
353 |
kvdb += xe->xdf2.nreff + 1; |
|
354 |
||
355 |
xenv.mxcost = xdl_bogosqrt(ndiags); |
|
356 |
if (xenv.mxcost < XDL_MAX_COST_MIN) |
|
357 |
xenv.mxcost = XDL_MAX_COST_MIN; |
|
358 |
xenv.snake_cnt = XDL_SNAKE_CNT; |
|
359 |
xenv.heur_min = XDL_HEUR_MIN_COST; |
|
360 |
||
361 |
dd1.nrec = xe->xdf1.nreff; |
|
362 |
dd1.ha = xe->xdf1.ha; |
|
363 |
dd1.rchg = xe->xdf1.rchg; |
|
364 |
dd1.rindex = xe->xdf1.rindex; |
|
365 |
dd2.nrec = xe->xdf2.nreff; |
|
366 |
dd2.ha = xe->xdf2.ha; |
|
367 |
dd2.rchg = xe->xdf2.rchg; |
|
368 |
dd2.rindex = xe->xdf2.rindex; |
|
369 |
||
370 |
if (xdl_recs_cmp(&dd1, 0, dd1.nrec, &dd2, 0, dd2.nrec, |
|
371 |
kvdf, kvdb, (xpp->flags & XDF_NEED_MINIMAL) != 0, &xenv) < 0) { |
|
372 |
||
373 |
xdl_free(kvd); |
|
374 |
xdl_free_env(xe); |
|
375 |
return -1; |
|
376 |
} |
|
377 |
||
378 |
xdl_free(kvd); |
|
379 |
||
380 |
return 0; |
|
381 |
} |
|
382 |
||
383 |
||
384 |
static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, long chg2) { |
|
385 |
xdchange_t *xch; |
|
386 |
||
387 |
if (!(xch = (xdchange_t *) xdl_malloc(sizeof(xdchange_t)))) |
|
388 |
return NULL; |
|
389 |
||
390 |
xch->next = xscr; |
|
391 |
xch->i1 = i1; |
|
392 |
xch->i2 = i2; |
|
393 |
xch->chg1 = chg1; |
|
394 |
xch->chg2 = chg2; |
|
395 |
xch->ignore = 0; |
|
396 |
||
397 |
return xch; |
|
398 |
} |
|
399 |
||
400 |
||
401 |
static int recs_match(xrecord_t *rec1, xrecord_t *rec2, long flags) |
|
402 |
{ |
|
403 |
return (rec1->ha == rec2->ha && |
|
404 |
xdl_recmatch(rec1->ptr, rec1->size, |
|
405 |
rec2->ptr, rec2->size, |
|
406 |
flags)); |
|
407 |
} |
|
408 |
||
409 |
/* |
|
410 |
* If a line is indented more than this, get_indent() just returns this value. |
|
411 |
* This avoids having to do absurd amounts of work for data that are not |
|
412 |
* human-readable text, and also ensures that the output of get_indent fits within |
|
413 |
* an int. |
|
414 |
*/ |
|
415 |
#define MAX_INDENT 200 |
|
416 |
||
417 |
/* |
|
418 |
* Return the amount of indentation of the specified line, treating TAB as 8 |
|
419 |
* columns. Return -1 if line is empty or contains only whitespace. Clamp the |
|
420 |
* output value at MAX_INDENT. |
|
421 |
*/ |
|
422 |
static int get_indent(xrecord_t *rec) |
|
423 |
{ |
|
424 |
long i; |
|
425 |
int ret = 0; |
|
426 |
||
427 |
for (i = 0; i < rec->size; i++) { |
|
428 |
char c = rec->ptr[i]; |
|
429 |
||
430 |
if (!XDL_ISSPACE(c)) |
|
431 |
return ret; |
|
432 |
else if (c == ' ') |
|
433 |
ret += 1; |
|
434 |
else if (c == '\t') |
|
435 |
ret += 8 - ret % 8; |
|
436 |
/* ignore other whitespace characters */ |
|
437 |
||
438 |
if (ret >= MAX_INDENT) |
|
439 |
return MAX_INDENT; |
|
440 |
} |
|
441 |
||
442 |
/* The line contains only whitespace. */ |
|
443 |
return -1; |
|
444 |
} |
|
445 |
||
446 |
/* |
|
447 |
* If more than this number of consecutive blank rows are found, just return this |
|
448 |
* value. This avoids requiring O(N^2) work for pathological cases, and also |
|
449 |
* ensures that the output of score_split fits in an int. |
|
450 |
*/ |
|
451 |
#define MAX_BLANKS 20 |
|
452 |
||
453 |
/* Characteristics measured about a hypothetical split position. */ |
|
454 |
struct split_measurement { |
|
455 |
/* |
|
456 |
* Is the split at the end of the file (aside from any blank lines)? |
|
457 |
*/ |
|
458 |
int end_of_file; |
|
459 |
||
460 |
/* |
|
461 |
* How much is the line immediately following the split indented (or -1 if |
|
462 |
* the line is blank): |
|
463 |
*/ |
|
464 |
int indent; |
|
465 |
||
466 |
/* |
|
467 |
* How many consecutive lines above the split are blank? |
|
468 |
*/ |
|
469 |
int pre_blank; |
|
470 |
||
471 |
/* |
|
472 |
* How much is the nearest non-blank line above the split indented (or -1 |
|
473 |
* if there is no such line)? |
|
474 |
*/ |
|
475 |
int pre_indent; |
|
476 |
||
477 |
/* |
|
478 |
* How many lines after the line following the split are blank? |
|
479 |
*/ |
|
480 |
int post_blank; |
|
481 |
||
482 |
/* |
|
483 |
* How much is the nearest non-blank line after the line following the |
|
484 |
* split indented (or -1 if there is no such line)? |
|
485 |
*/ |
|
486 |
int post_indent; |
|
487 |
}; |
|
488 |
||
489 |
struct split_score { |
|
490 |
/* The effective indent of this split (smaller is preferred). */ |
|
491 |
int effective_indent; |
|
492 |
||
493 |
/* Penalty for this split (smaller is preferred). */ |
|
494 |
int penalty; |
|
495 |
}; |
|
496 |
||
497 |
/* |
|
498 |
* Fill m with information about a hypothetical split of xdf above line split. |
|
499 |
*/ |
|
500 |
static void measure_split(const xdfile_t *xdf, long split, |
|
501 |
struct split_measurement *m) |
|
502 |
{ |
|
503 |
long i; |
|
504 |
||
505 |
if (split >= xdf->nrec) { |
|
506 |
m->end_of_file = 1; |
|
507 |
m->indent = -1; |
|
508 |
} else { |
|
509 |
m->end_of_file = 0; |
|
510 |
m->indent = get_indent(xdf->recs[split]); |
|
511 |
} |
|
512 |
||
513 |
m->pre_blank = 0; |
|
514 |
m->pre_indent = -1; |
|
515 |
for (i = split - 1; i >= 0; i--) { |
|
516 |
m->pre_indent = get_indent(xdf->recs[i]); |
|
517 |
if (m->pre_indent != -1) |
|
518 |
break; |
|
519 |
m->pre_blank += 1; |
|
520 |
if (m->pre_blank == MAX_BLANKS) { |
|
521 |
m->pre_indent = 0; |
|
522 |
break; |
|
523 |
} |
|
524 |
} |
|
525 |
||
526 |
m->post_blank = 0; |
|
527 |
m->post_indent = -1; |
|
528 |
for (i = split + 1; i < xdf->nrec; i++) { |
|
529 |
m->post_indent = get_indent(xdf->recs[i]); |
|
530 |
if (m->post_indent != -1) |
|
531 |
break; |
|
532 |
m->post_blank += 1; |
|
533 |
if (m->post_blank == MAX_BLANKS) { |
|
534 |
m->post_indent = 0; |
|
535 |
break; |
|
536 |
} |
|
537 |
} |
|
538 |
} |
|
539 |
||
540 |
/* |
|
541 |
* The empirically-determined weight factors used by score_split() below. |
|
542 |
* Larger values means that the position is a less favorable place to split. |
|
543 |
* |
|
544 |
* Note that scores are only ever compared against each other, so multiplying |
|
545 |
* all of these weight/penalty values by the same factor wouldn't change the |
|
546 |
* heuristic's behavior. Still, we need to set that arbitrary scale *somehow*. |
|
547 |
* In practice, these numbers are chosen to be large enough that they can be |
|
548 |
* adjusted relative to each other with sufficient precision despite using |
|
549 |
* integer math. |
|
550 |
*/ |
|
551 |
||
552 |
/* Penalty if there are no non-blank lines before the split */ |
|
553 |
#define START_OF_FILE_PENALTY 1 |
|
554 |
||
555 |
/* Penalty if there are no non-blank lines after the split */ |
|
556 |
#define END_OF_FILE_PENALTY 21 |
|
557 |
||
558 |
/* Multiplier for the number of blank lines around the split */ |
|
559 |
#define TOTAL_BLANK_WEIGHT (-30) |
|
560 |
||
561 |
/* Multiplier for the number of blank lines after the split */ |
|
562 |
#define POST_BLANK_WEIGHT 6 |
|
563 |
||
564 |
/* |
|
565 |
* Penalties applied if the line is indented more than its predecessor |
|
566 |
*/ |
|
567 |
#define RELATIVE_INDENT_PENALTY (-4) |
|
568 |
#define RELATIVE_INDENT_WITH_BLANK_PENALTY 10 |
|
569 |
||
570 |
/* |
|
571 |
* Penalties applied if the line is indented less than both its predecessor and |
|
572 |
* its successor |
|
573 |
*/ |
|
574 |
#define RELATIVE_OUTDENT_PENALTY 24 |
|
575 |
#define RELATIVE_OUTDENT_WITH_BLANK_PENALTY 17 |
|
576 |
||
577 |
/* |
|
578 |
* Penalties applied if the line is indented less than its predecessor but not |
|
579 |
* less than its successor |
|
580 |
*/ |
|
581 |
#define RELATIVE_DEDENT_PENALTY 23 |
|
582 |
#define RELATIVE_DEDENT_WITH_BLANK_PENALTY 17 |
|
583 |
||
584 |
/* |
|
585 |
* We only consider whether the sum of the effective indents for splits are |
|
586 |
* less than (-1), equal to (0), or greater than (+1) each other. The resulting |
|
587 |
* value is multiplied by the following weight and combined with the penalty to |
|
588 |
* determine the better of two scores. |
|
589 |
*/ |
|
590 |
#define INDENT_WEIGHT 60 |
|
591 |
||
592 |
/* |
|
593 |
* Compute a badness score for the hypothetical split whose measurements are |
|
594 |
* stored in m. The weight factors were determined empirically using the tools and |
|
595 |
* corpus described in |
|
596 |
* |
|
597 |
* https://github.com/mhagger/diff-slider-tools |
|
598 |
* |
|
599 |
* Also see that project if you want to improve the weights based on, for example, |
|
600 |
* a larger or more diverse corpus. |
|
601 |
*/ |
|
602 |
static void score_add_split(const struct split_measurement *m, struct split_score *s) |
|
603 |
{ |
|
604 |
/* |
|
605 |
* A place to accumulate penalty factors (positive makes this index more |
|
606 |
* favored): |
|
607 |
*/ |
|
608 |
int post_blank, total_blank, indent, any_blanks; |
|
609 |
||
610 |
if (m->pre_indent == -1 && m->pre_blank == 0) |
|
611 |
s->penalty += START_OF_FILE_PENALTY; |
|
612 |
||
613 |
if (m->end_of_file) |
|
614 |
s->penalty += END_OF_FILE_PENALTY; |
|
615 |
||
616 |
/* |
|
617 |
* Set post_blank to the number of blank lines following the split, |
|
618 |
* including the line immediately after the split: |
|
619 |
*/ |
|
620 |
post_blank = (m->indent == -1) ? 1 + m->post_blank : 0; |
|
621 |
total_blank = m->pre_blank + post_blank; |
|
622 |
||
623 |
/* Penalties based on nearby blank lines: */ |
|
624 |
s->penalty += TOTAL_BLANK_WEIGHT * total_blank; |
|
625 |
s->penalty += POST_BLANK_WEIGHT * post_blank; |
|
626 |
||
627 |
if (m->indent != -1) |
|
628 |
indent = m->indent; |
|
629 |
else |
|
630 |
indent = m->post_indent; |
|
631 |
||
632 |
any_blanks = (total_blank != 0); |
|
633 |
||
634 |
/* Note that the effective indent is -1 at the end of the file: */ |
|
635 |
s->effective_indent += indent; |
|
636 |
||
637 |
if (indent == -1) { |
|
638 |
/* No additional adjustments needed. */ |
|
639 |
} else if (m->pre_indent == -1) { |
|
640 |
/* No additional adjustments needed. */ |
|
641 |
} else if (indent > m->pre_indent) { |
|
642 |
/* |
|
643 |
* The line is indented more than its predecessor. |
|
644 |
*/ |
|
645 |
s->penalty += any_blanks ? |
|
646 |
RELATIVE_INDENT_WITH_BLANK_PENALTY : |
|
647 |
RELATIVE_INDENT_PENALTY; |
|
648 |
} else if (indent == m->pre_indent) { |
|
649 |
/* |
|
650 |
* The line has the same indentation level as its predecessor. |
|
651 |
* No additional adjustments needed. |
|
652 |
*/ |
|
653 |
} else { |
|
654 |
/* |
|
655 |
* The line is indented less than its predecessor. It could be |
|
656 |
* the block terminator of the previous block, but it could |
|
657 |
* also be the start of a new block (e.g., an "else" block, or |
|
658 |
* maybe the previous block didn't have a block terminator). |
|
659 |
* Try to distinguish those cases based on what comes next: |
|
660 |
*/ |
|
661 |
if (m->post_indent != -1 && m->post_indent > indent) { |
|
662 |
/* |
|
663 |
* The following line is indented more. So it is likely |
|
664 |
* that this line is the start of a block. |
|
665 |
*/ |
|
666 |
s->penalty += any_blanks ? |
|
667 |
RELATIVE_OUTDENT_WITH_BLANK_PENALTY : |
|
668 |
RELATIVE_OUTDENT_PENALTY; |
|
669 |
} else { |
|
670 |
/* |
|
671 |
* That was probably the end of a block. |
|
672 |
*/ |
|
673 |
s->penalty += any_blanks ? |
|
674 |
RELATIVE_DEDENT_WITH_BLANK_PENALTY : |
|
675 |
RELATIVE_DEDENT_PENALTY; |
|
676 |
} |
|
677 |
} |
|
678 |
} |
|
679 |
||
680 |
static int score_cmp(struct split_score *s1, struct split_score *s2) |
|
681 |
{ |
|
682 |
/* -1 if s1.effective_indent < s2->effective_indent, etc. */ |
|
683 |
int cmp_indents = ((s1->effective_indent > s2->effective_indent) - |
|
684 |
(s1->effective_indent < s2->effective_indent)); |
|
685 |
||
686 |
return INDENT_WEIGHT * cmp_indents + (s1->penalty - s2->penalty); |
|
687 |
} |
|
688 |
||
689 |
/* |
|
690 |
* Represent a group of changed lines in an xdfile_t (i.e., a contiguous group |
|
691 |
* of lines that was inserted or deleted from the corresponding version of the |
|
692 |
* file). We consider there to be such a group at the beginning of the file, at |
|
693 |
* the end of the file, and between any two unchanged lines, though most such |
|
694 |
* groups will usually be empty. |
|
695 |
* |
|
696 |
* If the first line in a group is equal to the line following the group, then |
|
697 |
* the group can be slid down. Similarly, if the last line in a group is equal |
|
698 |
* to the line preceding the group, then the group can be slid up. See |
|
699 |
* group_slide_down() and group_slide_up(). |
|
700 |
* |
|
701 |
* Note that loops that are testing for changed lines in xdf->rchg do not need |
|
702 |
* index bounding since the array is prepared with a zero at position -1 and N. |
|
703 |
*/ |
|
704 |
struct xdlgroup { |
|
705 |
/* |
|
706 |
* The index of the first changed line in the group, or the index of |
|
707 |
* the unchanged line above which the (empty) group is located. |
|
708 |
*/ |
|
709 |
long start; |
|
710 |
||
711 |
/* |
|
712 |
* The index of the first unchanged line after the group. For an empty |
|
713 |
* group, end is equal to start. |
|
714 |
*/ |
|
715 |
long end; |
|
716 |
}; |
|
717 |
||
718 |
/* |
|
719 |
* Initialize g to point at the first group in xdf. |
|
720 |
*/ |
|
721 |
static void group_init(xdfile_t *xdf, struct xdlgroup *g) |
|
722 |
{ |
|
723 |
g->start = g->end = 0; |
|
724 |
while (xdf->rchg[g->end]) |
|
725 |
g->end++; |
|
726 |
} |
|
727 |
||
728 |
/* |
|
729 |
* Move g to describe the next (possibly empty) group in xdf and return 0. If g |
|
730 |
* is already at the end of the file, do nothing and return -1. |
|
731 |
*/ |
|
732 |
static inline int group_next(xdfile_t *xdf, struct xdlgroup *g) |
|
733 |
{ |
|
734 |
if (g->end == xdf->nrec) |
|
735 |
return -1; |
|
736 |
||
737 |
g->start = g->end + 1; |
|
738 |
for (g->end = g->start; xdf->rchg[g->end]; g->end++) |
|
739 |
; |
|
740 |
||
741 |
return 0; |
|
742 |
} |
|
743 |
||
744 |
/* |
|
745 |
* Move g to describe the previous (possibly empty) group in xdf and return 0. |
|
746 |
* If g is already at the beginning of the file, do nothing and return -1. |
|
747 |
*/ |
|
748 |
static inline int group_previous(xdfile_t *xdf, struct xdlgroup *g) |
|
749 |
{ |
|
750 |
if (g->start == 0) |
|
751 |
return -1; |
|
752 |
||
753 |
g->end = g->start - 1; |
|
754 |
for (g->start = g->end; xdf->rchg[g->start - 1]; g->start--) |
|
755 |
; |
|
756 |
||
757 |
return 0; |
|
758 |
} |
|
759 |
||
760 |
/* |
|
761 |
* If g can be slid toward the end of the file, do so, and if it bumps into a |
|
762 |
* following group, expand this group to include it. Return 0 on success or -1 |
|
763 |
* if g cannot be slid down. |
|
764 |
*/ |
|
765 |
static int group_slide_down(xdfile_t *xdf, struct xdlgroup *g, long flags) |
|
766 |
{ |
|
767 |
if (g->end < xdf->nrec && |
|
768 |
recs_match(xdf->recs[g->start], xdf->recs[g->end], flags)) { |
|
769 |
xdf->rchg[g->start++] = 0; |
|
770 |
xdf->rchg[g->end++] = 1; |
|
771 |
||
772 |
while (xdf->rchg[g->end]) |
|
773 |
g->end++; |
|
774 |
||
775 |
return 0; |
|
776 |
} else { |
|
777 |
return -1; |
|
778 |
} |
|
779 |
} |
|
780 |
||
781 |
/* |
|
782 |
* If g can be slid toward the beginning of the file, do so, and if it bumps |
|
783 |
* into a previous group, expand this group to include it. Return 0 on success |
|
784 |
* or -1 if g cannot be slid up. |
|
785 |
*/ |
|
786 |
static int group_slide_up(xdfile_t *xdf, struct xdlgroup *g, long flags) |
|
787 |
{ |
|
788 |
if (g->start > 0 && |
|
789 |
recs_match(xdf->recs[g->start - 1], xdf->recs[g->end - 1], flags)) { |
|
790 |
xdf->rchg[--g->start] = 1; |
|
791 |
xdf->rchg[--g->end] = 0; |
|
792 |
||
793 |
while (xdf->rchg[g->start - 1]) |
|
794 |
g->start--; |
|
795 |
||
796 |
return 0; |
|
797 |
} else { |
|
798 |
return -1; |
|
799 |
} |
|
800 |
} |
|
801 |
||
802 |
static void xdl_bug(const char *msg) |
|
803 |
{ |
|
804 |
fprintf(stderr, "BUG: %s\n", msg); |
|
805 |
exit(1); |
|
806 |
} |
|
807 |
||
808 |
/* |
|
|
36674
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
809 |
* For indentation heuristic, skip searching for better slide position after |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
810 |
* checking MAX_BORING lines without finding an improvement. This defends the |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
811 |
* indentation heuristic logic against pathological cases. The value is not |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
812 |
* picked scientifically but should be good enough. |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
813 |
*/ |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
814 |
#define MAX_BORING 100 |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
815 |
|
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
816 |
/* |
| 36671 | 817 |
* Move back and forward change groups for a consistent and pretty diff output. |
818 |
* This also helps in finding joinable change groups and reducing the diff |
|
819 |
* size. |
|
820 |
*/ |
|
821 |
int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags) { |
|
822 |
struct xdlgroup g, go; |
|
823 |
long earliest_end, end_matching_other; |
|
824 |
long groupsize; |
|
825 |
||
826 |
group_init(xdf, &g); |
|
827 |
group_init(xdfo, &go); |
|
828 |
||
829 |
while (1) { |
|
830 |
/* If the group is empty in the to-be-compacted file, skip it: */ |
|
831 |
if (g.end == g.start) |
|
832 |
goto next; |
|
833 |
||
834 |
/* |
|
835 |
* Now shift the change up and then down as far as possible in |
|
836 |
* each direction. If it bumps into any other changes, merge them. |
|
837 |
*/ |
|
838 |
do { |
|
839 |
groupsize = g.end - g.start; |
|
840 |
||
841 |
/* |
|
842 |
* Keep track of the last "end" index that causes this |
|
843 |
* group to align with a group of changed lines in the |
|
844 |
* other file. -1 indicates that we haven't found such |
|
845 |
* a match yet: |
|
846 |
*/ |
|
847 |
end_matching_other = -1; |
|
848 |
||
849 |
/* Shift the group backward as much as possible: */ |
|
850 |
while (!group_slide_up(xdf, &g, flags)) |
|
851 |
if (group_previous(xdfo, &go)) |
|
852 |
xdl_bug("group sync broken sliding up"); |
|
853 |
||
854 |
/* |
|
855 |
* This is this highest that this group can be shifted. |
|
856 |
* Record its end index: |
|
857 |
*/ |
|
858 |
earliest_end = g.end; |
|
859 |
||
860 |
if (go.end > go.start) |
|
861 |
end_matching_other = g.end; |
|
862 |
||
863 |
/* Now shift the group forward as far as possible: */ |
|
864 |
while (1) { |
|
865 |
if (group_slide_down(xdf, &g, flags)) |
|
866 |
break; |
|
867 |
if (group_next(xdfo, &go)) |
|
868 |
xdl_bug("group sync broken sliding down"); |
|
869 |
||
870 |
if (go.end > go.start) |
|
871 |
end_matching_other = g.end; |
|
872 |
} |
|
873 |
} while (groupsize != g.end - g.start); |
|
874 |
||
875 |
/* |
|
876 |
* If the group can be shifted, then we can possibly use this |
|
877 |
* freedom to produce a more intuitive diff. |
|
878 |
* |
|
879 |
* The group is currently shifted as far down as possible, so the |
|
880 |
* heuristics below only have to handle upwards shifts. |
|
881 |
*/ |
|
882 |
||
883 |
if (g.end == earliest_end) { |
|
884 |
/* no shifting was possible */ |
|
885 |
} else if (end_matching_other != -1) { |
|
886 |
/* |
|
887 |
* Move the possibly merged group of changes back to line |
|
888 |
* up with the last group of changes from the other file |
|
889 |
* that it can align with. |
|
890 |
*/ |
|
891 |
while (go.end == go.start) { |
|
892 |
if (group_slide_up(xdf, &g, flags)) |
|
893 |
xdl_bug("match disappeared"); |
|
894 |
if (group_previous(xdfo, &go)) |
|
895 |
xdl_bug("group sync broken sliding to match"); |
|
896 |
} |
|
897 |
} else if (flags & XDF_INDENT_HEURISTIC) { |
|
898 |
/* |
|
899 |
* Indent heuristic: a group of pure add/delete lines |
|
900 |
* implies two splits, one between the end of the "before" |
|
901 |
* context and the start of the group, and another between |
|
902 |
* the end of the group and the beginning of the "after" |
|
903 |
* context. Some splits are aesthetically better and some |
|
904 |
* are worse. We compute a badness "score" for each split, |
|
905 |
* and add the scores for the two splits to define a |
|
906 |
* "score" for each position that the group can be shifted |
|
907 |
* to. Then we pick the shift with the lowest score. |
|
908 |
*/ |
|
909 |
long shift, best_shift = -1; |
|
910 |
struct split_score best_score; |
|
911 |
||
|
36674
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
912 |
/* |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
913 |
* This is O(N * MAX_BLANKS) (N = shift-able lines). |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
914 |
* Even with MAX_BLANKS bounded to a small value, a |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
915 |
* large N could still make this loop take several |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
916 |
* times longer than the main diff algorithm. The |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
917 |
* "boring" value is to help cut down N to something |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
918 |
* like (MAX_BORING + groupsize). |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
919 |
* |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
920 |
* Scan from bottom to top. So we can exit the loop |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
921 |
* without compromising the assumption "for a same best |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
922 |
* score, pick the bottommost shift". |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
923 |
*/ |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
924 |
int boring = 0; |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
925 |
for (shift = g.end; shift >= earliest_end; shift--) { |
| 36671 | 926 |
struct split_measurement m; |
927 |
struct split_score score = {0, 0}; |
|
|
36674
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
928 |
int cmp; |
| 36671 | 929 |
|
930 |
measure_split(xdf, shift, &m); |
|
931 |
score_add_split(&m, &score); |
|
932 |
measure_split(xdf, shift - groupsize, &m); |
|
933 |
score_add_split(&m, &score); |
|
|
36674
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
934 |
|
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
935 |
if (best_shift == -1) { |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
936 |
cmp = -1; |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
937 |
} else { |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
938 |
cmp = score_cmp(&score, &best_score); |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
939 |
} |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
940 |
if (cmp < 0) { |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
941 |
boring = 0; |
| 36671 | 942 |
best_score.effective_indent = score.effective_indent; |
943 |
best_score.penalty = score.penalty; |
|
944 |
best_shift = shift; |
|
|
36674
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
945 |
} else { |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
946 |
boring += 1; |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
947 |
if (boring >= MAX_BORING) |
|
c420792217c8
xdiff: reduce indent heuristic overhead
Jun Wu <quark@fb.com>
parents:
36673
diff
changeset
|
948 |
break; |
| 36671 | 949 |
} |
950 |
} |
|
951 |
||
952 |
while (g.end > best_shift) { |
|
953 |
if (group_slide_up(xdf, &g, flags)) |
|
954 |
xdl_bug("best shift unreached"); |
|
955 |
if (group_previous(xdfo, &go)) |
|
956 |
xdl_bug("group sync broken sliding to blank line"); |
|
957 |
} |
|
958 |
} |
|
959 |
||
960 |
next: |
|
961 |
/* Move past the just-processed group: */ |
|
962 |
if (group_next(xdf, &g)) |
|
963 |
break; |
|
964 |
if (group_next(xdfo, &go)) |
|
965 |
xdl_bug("group sync broken moving to next group"); |
|
966 |
} |
|
967 |
||
968 |
if (!group_next(xdfo, &go)) |
|
969 |
xdl_bug("group sync broken at end of file"); |
|
970 |
||
971 |
return 0; |
|
972 |
} |
|
973 |
||
974 |
||
975 |
int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) { |
|
976 |
xdchange_t *cscr = NULL, *xch; |
|
977 |
char *rchg1 = xe->xdf1.rchg, *rchg2 = xe->xdf2.rchg; |
|
978 |
long i1, i2, l1, l2; |
|
979 |
||
980 |
/* |
|
981 |
* Trivial. Collects "groups" of changes and creates an edit script. |
|
982 |
*/ |
|
983 |
for (i1 = xe->xdf1.nrec, i2 = xe->xdf2.nrec; i1 >= 0 || i2 >= 0; i1--, i2--) |
|
984 |
if (rchg1[i1 - 1] || rchg2[i2 - 1]) { |
|
985 |
for (l1 = i1; rchg1[i1 - 1]; i1--); |
|
986 |
for (l2 = i2; rchg2[i2 - 1]; i2--); |
|
987 |
||
988 |
if (!(xch = xdl_add_change(cscr, i1, i2, l1 - i1, l2 - i2))) { |
|
989 |
xdl_free_script(cscr); |
|
990 |
return -1; |
|
991 |
} |
|
992 |
cscr = xch; |
|
993 |
} |
|
994 |
||
995 |
*xscr = cscr; |
|
996 |
||
997 |
return 0; |
|
998 |
} |
|
999 |
||
1000 |
||
1001 |
void xdl_free_script(xdchange_t *xscr) { |
|
1002 |
xdchange_t *xch; |
|
1003 |
||
1004 |
while ((xch = xscr) != NULL) { |
|
1005 |
xscr = xscr->next; |
|
1006 |
xdl_free(xch); |
|
1007 |
} |
|
1008 |
} |
|
1009 |
||
| 36763 | 1010 |
|
1011 |
/* |
|
1012 |
* Starting at the passed change atom, find the latest change atom to be included |
|
1013 |
* inside the differential hunk according to the specified configuration. |
|
1014 |
* Also advance xscr if the first changes must be discarded. |
|
1015 |
*/ |
|
1016 |
xdchange_t *xdl_get_hunk(xdchange_t **xscr, xdemitconf_t const *xecfg) |
|
1017 |
{ |
|
1018 |
xdchange_t *xch, *xchp, *lxch; |
|
1019 |
long max_common = 0; |
|
1020 |
long max_ignorable = 0; |
|
1021 |
unsigned long ignored = 0; /* number of ignored blank lines */ |
|
1022 |
||
1023 |
/* remove ignorable changes that are too far before other changes */ |
|
1024 |
for (xchp = *xscr; xchp && xchp->ignore; xchp = xchp->next) { |
|
1025 |
xch = xchp->next; |
|
1026 |
||
1027 |
if (xch == NULL || |
|
1028 |
xch->i1 - (xchp->i1 + xchp->chg1) >= max_ignorable) |
|
1029 |
*xscr = xch; |
|
1030 |
} |
|
1031 |
||
1032 |
if (*xscr == NULL) |
|
1033 |
return NULL; |
|
1034 |
||
1035 |
lxch = *xscr; |
|
1036 |
||
1037 |
for (xchp = *xscr, xch = xchp->next; xch; xchp = xch, xch = xch->next) { |
|
1038 |
long distance = xch->i1 - (xchp->i1 + xchp->chg1); |
|
1039 |
if (distance > max_common) |
|
1040 |
break; |
|
1041 |
||
1042 |
if (distance < max_ignorable && (!xch->ignore || lxch == xchp)) { |
|
1043 |
lxch = xch; |
|
1044 |
ignored = 0; |
|
1045 |
} else if (distance < max_ignorable && xch->ignore) { |
|
1046 |
ignored += xch->chg2; |
|
1047 |
} else if (lxch != xchp && |
|
1048 |
xch->i1 + ignored - (lxch->i1 + lxch->chg1) > max_common) { |
|
1049 |
break; |
|
1050 |
} else if (!xch->ignore) { |
|
1051 |
lxch = xch; |
|
1052 |
ignored = 0; |
|
1053 |
} else { |
|
1054 |
ignored += xch->chg2; |
|
1055 |
} |
|
1056 |
} |
|
1057 |
||
1058 |
return lxch; |
|
1059 |
} |
|
1060 |
||
1061 |
||
| 36671 | 1062 |
static int xdl_call_hunk_func(xdfenv_t *xe, xdchange_t *xscr, xdemitcb_t *ecb, |
1063 |
xdemitconf_t const *xecfg) |
|
1064 |
{ |
|
|
36820
f33a87cf60cc
xdiff: add a preprocessing step that trims files
Jun Wu <quark@fb.com>
parents:
36763
diff
changeset
|
1065 |
long p = xe->nprefix, s = xe->nsuffix; |
| 36671 | 1066 |
xdchange_t *xch, *xche; |
| 36763 | 1067 |
|
1068 |
if (!xecfg->hunk_func) |
|
1069 |
return -1; |
|
1070 |
||
| 36673 | 1071 |
if ((xecfg->flags & XDL_EMIT_BDIFFHUNK) != 0) { |
1072 |
long i1 = 0, i2 = 0, n1 = xe->xdf1.nrec, n2 = xe->xdf2.nrec; |
|
1073 |
for (xch = xscr; xch; xch = xche->next) { |
|
1074 |
xche = xdl_get_hunk(&xch, xecfg); |
|
1075 |
if (!xch) |
|
1076 |
break; |
|
|
36820
f33a87cf60cc
xdiff: add a preprocessing step that trims files
Jun Wu <quark@fb.com>
parents:
36763
diff
changeset
|
1077 |
if (xch != xche) |
|
f33a87cf60cc
xdiff: add a preprocessing step that trims files
Jun Wu <quark@fb.com>
parents:
36763
diff
changeset
|
1078 |
xdl_bug("xch != xche"); |
|
f33a87cf60cc
xdiff: add a preprocessing step that trims files
Jun Wu <quark@fb.com>
parents:
36763
diff
changeset
|
1079 |
xch->i1 += p; |
|
f33a87cf60cc
xdiff: add a preprocessing step that trims files
Jun Wu <quark@fb.com>
parents:
36763
diff
changeset
|
1080 |
xch->i2 += p; |
| 36673 | 1081 |
if (xch->i1 > i1 || xch->i2 > i2) { |
1082 |
if (xecfg->hunk_func(i1, xch->i1, i2, xch->i2, ecb->priv) < 0) |
|
1083 |
return -1; |
|
1084 |
} |
|
1085 |
i1 = xche->i1 + xche->chg1; |
|
1086 |
i2 = xche->i2 + xche->chg2; |
|
1087 |
} |
|
|
36820
f33a87cf60cc
xdiff: add a preprocessing step that trims files
Jun Wu <quark@fb.com>
parents:
36763
diff
changeset
|
1088 |
if (xecfg->hunk_func(i1, n1 + p + s, i2, n2 + p + s, |
|
f33a87cf60cc
xdiff: add a preprocessing step that trims files
Jun Wu <quark@fb.com>
parents:
36763
diff
changeset
|
1089 |
ecb->priv) < 0) |
| 36671 | 1090 |
return -1; |
| 36673 | 1091 |
} else { |
1092 |
for (xch = xscr; xch; xch = xche->next) { |
|
1093 |
xche = xdl_get_hunk(&xch, xecfg); |
|
1094 |
if (!xch) |
|
1095 |
break; |
|
|
36820
f33a87cf60cc
xdiff: add a preprocessing step that trims files
Jun Wu <quark@fb.com>
parents:
36763
diff
changeset
|
1096 |
if (xecfg->hunk_func(xch->i1 + p, |
|
f33a87cf60cc
xdiff: add a preprocessing step that trims files
Jun Wu <quark@fb.com>
parents:
36763
diff
changeset
|
1097 |
xche->i1 + xche->chg1 - xch->i1, |
|
f33a87cf60cc
xdiff: add a preprocessing step that trims files
Jun Wu <quark@fb.com>
parents:
36763
diff
changeset
|
1098 |
xch->i2 + p, |
|
f33a87cf60cc
xdiff: add a preprocessing step that trims files
Jun Wu <quark@fb.com>
parents:
36763
diff
changeset
|
1099 |
xche->i2 + xche->chg2 - xch->i2, |
| 36673 | 1100 |
ecb->priv) < 0) |
1101 |
return -1; |
|
1102 |
} |
|
| 36671 | 1103 |
} |
1104 |
return 0; |
|
1105 |
} |
|
1106 |
||
1107 |
int xdl_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, |
|
1108 |
xdemitconf_t const *xecfg, xdemitcb_t *ecb) { |
|
1109 |
xdchange_t *xscr; |
|
1110 |
xdfenv_t xe; |
|
1111 |
||
1112 |
if (xdl_do_diff(mf1, mf2, xpp, &xe) < 0) { |
|
1113 |
||
1114 |
return -1; |
|
1115 |
} |
|
1116 |
if (xdl_change_compact(&xe.xdf1, &xe.xdf2, xpp->flags) < 0 || |
|
1117 |
xdl_change_compact(&xe.xdf2, &xe.xdf1, xpp->flags) < 0 || |
|
1118 |
xdl_build_script(&xe, &xscr) < 0) { |
|
1119 |
||
1120 |
xdl_free_env(&xe); |
|
1121 |
return -1; |
|
1122 |
} |
|
1123 |
||
| 36763 | 1124 |
if (xdl_call_hunk_func(&xe, xscr, ecb, xecfg) < 0) { |
| 36671 | 1125 |
xdl_free_script(xscr); |
| 36673 | 1126 |
xdl_free_env(&xe); |
1127 |
return -1; |
|
| 36671 | 1128 |
} |
| 36673 | 1129 |
xdl_free_script(xscr); |
| 36671 | 1130 |
xdl_free_env(&xe); |
1131 |
||
1132 |
return 0; |
|
1133 |
} |