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