/* * wiggle - apply rejected patches * * Copyright (C) 2003 Neil Brown * Copyright (C) 2011-2013 Neil Brown * Copyright (C) 2014-2020 Neil Brown * * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program. * * Author: Neil Brown * Email: */ /* * Find the best match for a patch against a file. A patch is a * sequence of chunks each of which is expected to match a particular * locality of the file. So we expect big gaps between where chunks * match, but only small gaps within chunks. * * The matching algorithm is similar to that in diff.c, so you should * understand that first. However it takes fewer shortcuts and * analyses cost in a more detailed way. * * We walk the whole matrix in a breadth first fashion following a * 'front' on which x+y is constant. Along this front we examine each * diagonal. For each point we calculate a 'value' for the match so * far. This will be in some particular chunk. For each chunk we * separately record the best value found so far, and where it was. * To choose a new value for each point we calculate based on the * previous value on each neighbouring diagonal and on this diagonal. * * This can result is a set of 'best' matches for each chunk which are * not in the same order that the chunks initially were. This * probably isn't desired, so we choose a 'best' best match and * recurse on each side of it. * * The quality of a match is a somewhat complex function that is * roughly 3 times the number of matching symbols minus the number * of replaced, added, or deleted. This seems to work. * * For any point, the best possible score using that point * is a complete diagonal to the nearest edge. We ignore points * which cannot contibute to a better overall score. * * As this is a fairly expensive search we remove uninteresting * symbols before searching. Specifically we only keep alphanumeric * (plus '_') strings. Spaces and punctuation is ignored. This should * contain enough information to achieve a reliable match while scanning * many fewer symbols. */ #include #include #include "wiggle.h" /* This structure keeps track of the current match at each point. * It holds the start of the match as x,k where k is the * diagonal, so y = x-k. * Also the length of the match so far. * If l == 0, there is no match. */ struct v { int x, y; /* location of start of match */ int val; /* value of match from x,y to here */ int k; /* diagonal of last match - if val > 0 */ int inmatch; /* 1 if last point was a match */ int c; /* chunk number */ }; /* * Here we must determine the 'value' of a partial match. * The input parameters are: * length - the total number of symbols matched * errs - the total number of insertions or deletions * dif - the absolute difference between number of insertions and deletions. * * In general we want length to be high, errs to be low, and dif to be low. * Particular questions that must be answered include: * - When does adding an extra symbol after a small gap improve the match * - When does a match become so bad that we would rather start again. * * We would like symmetry in our answers so that a good sequence with * an out-rider on one end is evaluated the same as a good sequence * with an out-rider on the other end. * * However to do this we cannot really use the value of the good * sequence to weigh in the out-riders favour as in the case of a * leading outrider, we do not yet know the value of the good * sequence. * * First, we need an arbitrary number, X, to say "Given a single * symbol, after X errors, we forget that symbol". 5 seems a good * number. * * Next we need to understand how replacements compare to insertions * or deletions. Probably a replacement is the same cost as an * insertion or deletion. Finally, a few large stretches are better * then lots of little ones, so the number of disjoint stretches * should be kept low. * * So: * The first match sets the value to 6. * Each consecutive match adds 3 * A non-consecutive match which value is still +ve adds 2 * Each non-match subtracts one unless it is the other half of a replacement. * A value of 0 causes us to forget where we are and start again. * * We need to not only assess the value at a particular location, but * also assess the maximum value we could get if all remaining symbols * matched, to help exclude parts of the matrix. The value of that * possibility is 6 times the number of remaining symbols, -1 if we * just had a match. */ /* dir == 0 for match, 1 for k increase, -1 for k decrease */ static inline void update_value(struct v *v, int dir, int k, int x) { if (dir == 0) { if (v->val <= 0) { v->x = x-1; v->y = x-k-1; v->inmatch = 0; v->val = 4; } v->val += 2+v->inmatch; v->inmatch = 1; v->k = k; } else if (v->val > 0) { v->inmatch = 0; if (dir * (v->k - k) > 0) { /* other half of replacement */ } else { v->val -= 1; } } } /* Calculate the best possible value that this 'struct v' * could reach if there are 'max' symbols remaining * that could possibly be matches. */ static inline int best_val(struct v *v, int max) { if (v->val <= 0) return 4+max*3-1; else return max*3-1+v->inmatch+v->val; } struct best { int xlo, ylo; int xhi, yhi; int val; }; static inline int min(int a, int b) { return a < b ? a : b; } static void find_best(struct file *a, struct file *b, int alo, int ahi, int blo, int bhi, struct best *best) { int klo, khi, k; int f; struct v *valloc = wiggle_xmalloc(sizeof(struct v)*((ahi-alo)+(bhi-blo)+5)); struct v *v = valloc + (bhi-alo+2); k = klo = khi = alo-blo; f = alo+blo; /* front that moves forward */ v[k].val = 0; v[k].c = -1; while (f < ahi+bhi) { int x, y; f++; for (k = klo+1; k <= khi-1 ; k += 2) { struct v vnew, vnew2; x = (k+f)/2; y = x-k; /* first consider the diagonal - if possible * it is always preferred */ if (match(&a->list[x-1], &b->list[y-1])) { vnew = v[k]; update_value(&v[k], 0, k, x); if (v[k].c < 0) abort(); if (v[k].val > best[v[k].c].val) { int chunk = v[k].c; best[chunk].xlo = v[k].x; best[chunk].ylo = v[k].y; best[chunk].xhi = x; best[chunk].yhi = y; best[chunk].val = v[k].val; } } else { /* First consider a y-step: adding a * symbol from B */ vnew = v[k+1]; update_value(&vnew, -1, k, x); /* might cross a chunk boundary */ if (b->list[y-1].len && b->list[y-1].start[0] == 0) { vnew.c = atoi(b->list[y-1].start+1); vnew.val = 0; } /* Not consider an x-step: deleting * a symbol. This cannot be a chunk * boundary as there aren't any in 'A' */ vnew2 = v[k-1]; update_value(&vnew2, 1, k, x); /* Now choose the best. */ if (vnew2.val > vnew.val) v[k] = vnew2; else v[k] = vnew; } } /* extend or contract range */ klo--; v[klo] = v[klo+1]; x = (klo+f)/2; y = x-klo; update_value(&v[klo], -1, klo, x); if (y <= bhi && b->list[y-1].len && b->list[y-1].start[0] == 0) { v[klo].c = atoi(b->list[y-1].start+1); v[klo].val = 0; } while (klo+2 < (ahi-bhi) && (y > bhi || (best_val(&v[klo], min(ahi-x, bhi-y)) < best[v[klo].c].val && best_val(&v[klo+1], min(ahi-x, bhi-y+1)) < best[v[klo+1].c].val ) )) { klo += 2; x = (klo+f)/2; y = x-klo; } khi++; v[khi] = v[khi-1]; x = (khi+f)/2; y = x - khi; update_value(&v[khi], -1, khi, x); while (khi-2 > (ahi-bhi) && (x > ahi || (v[khi].c >= 0 && best_val(&v[khi], min(ahi-x, bhi-y)) < best[v[khi].c].val && best_val(&v[khi-1], min(ahi-x+1, bhi-y)) < best[v[khi].c].val ) )) { khi -= 2; x = (khi+f)/2; y = x - khi; } } free(valloc); } /* * Reduce a file by discarding less interesting words * Words that end with a newline are interesting (so all words * in line-mode are interesting) and words that start with * and alphanumeric are interesting. This excludes spaces and * special characters in word mode * Doing a best-fit comparison on only interesting words is * much faster than on all words, and is nearly as good */ static inline int is_skipped(struct elmnt e) { return !(ends_line(e) || isalnum(e.start[0]) || e.start[0] == '_'); } static struct file reduce(struct file orig) { int cnt = 0; int i; struct file rv; for (i = 0; i < orig.elcnt; i++) if (!is_skipped(orig.list[i])) cnt++; if (cnt == orig.elcnt) return orig; rv.elcnt = cnt; rv.list = wiggle_xmalloc(cnt*sizeof(struct elmnt)); cnt = 0; for (i = 0; i < orig.elcnt; i++) if (!is_skipped(orig.list[i])) rv.list[cnt++] = orig.list[i]; return rv; } /* Given a list of best matches between a1 and b1 which are * subsets of a2 and b2, convert that list to indexes into a2/b2 * * When we find the location in a2/b2, we expand to include all * immediately surrounding words which were skipped */ static void remap(struct best *best, int cnt, struct file a1, struct file b1, struct file a2, struct file b2) { int b; int pa, pb; /* pointers into the a2 and b2 arrays */ pa = pb = 0; if (a1.elcnt == 0 && a2.elcnt == 0) return; for (b = 1; b < cnt; b++) if (best[b].val > 0) { while (pa < a2.elcnt && a2.list[pa].start != a1.list[best[b].xlo].start) pa++; if (pa == a2.elcnt) abort(); while (pb < b2.elcnt && b2.list[pb].start != b1.list[best[b].ylo].start) pb++; if (pb == b2.elcnt) abort(); /* pa,pb is the start of this best bit. Step * backward over ignored words */ while (pa > 0 && is_skipped(a2.list[pa-1])) pa--; while (pb > 0 && is_skipped(b2.list[pb-1])) pb--; if (pa <= 0) pa = 1; if (pb <= 0) pb = 1; best[b].xlo = pa; best[b].ylo = pb; while (pa < a2.elcnt && (pa == 0 || (a2.list[pa-1].start != a1.list[best[b].xhi-1].start))) pa++; if (pa == a2.elcnt && best[b].xhi != a1.elcnt) abort(); while (pb < b2.elcnt && (pb == 0 || (b2.list[pb-1].start != b1.list[best[b].yhi-1].start))) pb++; if (pb == b2.elcnt && best[b].yhi != b1.elcnt) abort(); /* pa,pb is now the end of the best bit. * Step pa,pb forward over ignored words. */ while (pa < a2.elcnt && is_skipped(a2.list[pa])) pa++; while (pb < b2.elcnt && is_skipped(b2.list[pb])) pb++; best[b].xhi = pa; best[b].yhi = pb; } } static void find_best_inorder(struct file *a, struct file *b, int alo, int ahi, int blo, int bhi, struct best *best, int bestlo, int besthi) { /* make sure the best matches we find are inorder. * If they aren't we find a overall best, and * recurse either side of that */ int i; int bad = 0; int bestval, bestpos = 0; for (i = bestlo; i < besthi; i++) best[i].val = 0; find_best(a, b, alo, ahi, blo, bhi, best); for (i = bestlo + 1; i < besthi; i++) if (best[i-1].val > 0 && best[i].val > 0 && best[i-1].xhi >= best[i].xlo) bad = 1; if (!bad) return; bestval = 0; for (i = bestlo; i < besthi; i++) if (best[i].val > bestval) { bestval = best[i].val; bestpos = i; } if (bestpos > bestlo) { /* move top down below chunk marker */ int y = best[bestpos].ylo; while (b->list[y].start[0]) y--; find_best_inorder(a, b, alo, best[bestpos].xlo, blo, y, best, bestlo, bestpos); } if (bestpos < besthi-1) { /* move bottom up to chunk marker */ int y = best[bestpos].yhi; while (b->list[y].start[0]) y++; find_best_inorder(a, b, best[bestpos].xhi, ahi, y, bhi, best, bestpos+1, besthi); } } struct csl *wiggle_pdiff(struct file a, struct file b, int chunks) { struct csl *csl1, *csl2; struct best *best = wiggle_xmalloc(sizeof(struct best)*(chunks+1)); int i; struct file asmall, bsmall; int xmin; asmall = reduce(a); bsmall = reduce(b); for (i = 0; i < chunks+1; i++) best[i].val = 0; find_best_inorder(&asmall, &bsmall, 0, asmall.elcnt, 0, bsmall.elcnt, best, 1, chunks+1); remap(best, chunks+1, asmall, bsmall, a, b); if (asmall.list != a.list) free(asmall.list); if (bsmall.list != b.list) free(bsmall.list); csl1 = NULL; xmin = 0; for (i = 1; i <= chunks; i++) if (best[i].val > 0) { /* If we there are any newlines in the hunk before * ylo, then extend xlo back that many newlines if * possible and wiggle_diff_partial the extended regions. */ int lines = 0; int ylo = best[i].ylo; int yhi; while (ylo > 0 && b.list[ylo-1].start[0]) { ylo--; lines += !!ends_line(b.list[ylo]); } if (lines) { int xlo = best[i].xlo; while (lines && xlo > xmin) { xlo--; lines -= !!ends_line(a.list[xlo]); } while (xlo > xmin && !ends_line(a.list[xlo-1])) xlo--; csl2 = wiggle_diff_partial(a, b, xlo, best[i].xlo, ylo, best[i].ylo); csl1 = wiggle_csl_join(csl1, csl2); } /* Now wiggle_diff_partial the good bit of the hunk with the * good match */ csl2 = wiggle_diff_partial(a, b, best[i].xlo, best[i].xhi, best[i].ylo, best[i].yhi); csl1 = wiggle_csl_join(csl1, csl2); /* Now if there are newlines at the end of the * hunk that weren't matched, find as many in * original and wiggle_diff_partial those bits */ lines = 0; yhi = best[i].yhi; while (yhi < b.elcnt && b.list[yhi].start[0]) { lines += !!ends_line(b.list[yhi]); yhi++; } xmin = best[i].xhi; if (lines) { int xhi = best[i].xhi; int xmax = a.elcnt; if (i < chunks) xmax = best[i+1].xlo; while (lines && xhi < xmax) { lines -= !!ends_line(a.list[xhi]); xhi++; } csl2 = wiggle_diff_partial(a, b, best[i].xhi, xhi, best[i].yhi, yhi); csl1 = wiggle_csl_join(csl1, csl2); xmin = xhi; } } else { /* FIXME we just lost a hunk!! */; } if (csl1) { for (csl2 = csl1; csl2->len; csl2++) ; csl2->a = a.elcnt; csl2->b = b.elcnt; } else { csl1 = wiggle_xmalloc(sizeof(*csl1)); csl1->len = 0; csl1->a = a.elcnt; csl1->b = b.elcnt; } free(best); return csl1; }