* wiggle - apply rejected patches
*
* Copyright (C) 2003 Neil Brown <neilb@cse.unsw.edu.au>
- * Copyright (C) 2011 Neil Brown <neilb@suse.de>
+ * Copyright (C) 2011-2013 Neil Brown <neilb@suse.de>
+ * Copyright (C) 2014-2020 Neil Brown <neil@brown.name>
*
*
* This program is free software; you can redistribute it and/or modify
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software Foundation, Inc.,
- * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
+ * along with this program.
*
* Author: Neil Brown
- * Email: <neilb@suse.de>
+ * Email: <neil@brown.name>
*/
/*
int klo, khi, k;
int f;
- struct v *valloc = xmalloc(sizeof(struct v)*((ahi-alo)+(bhi-blo)+5));
+ 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;
(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;
}
(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);
}
-/* Join two csl lists together.
- * Simply allocate new space and copy everything in.
- */
-static struct csl *csl_join(struct csl *c1, struct csl *c2)
-{
- struct csl *c, *cd, *rv;
- int cnt;
-
- if (c1 == NULL)
- return c2;
- if (c2 == NULL)
- return c1;
-
- cnt = 1; /* the sentinal */
- for (c = c1; c->len; c++)
- cnt++;
- for (c = c2; c->len; c++)
- cnt++;
- cd = rv = xmalloc(sizeof(*rv)*cnt);
- for (c = c1; c->len; c++)
- *cd++ = *c;
- for (c = c2; c->len; c++)
- *cd++ = *c;
- cd->len = 0;
- free(c1);
- free(c2);
- return rv;
-}
-
/*
* 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 comparision on only interesting words is
+ * Doing a best-fit comparison on only interesting words is
* much faster than on all words, and is nearly as good
*/
return orig;
rv.elcnt = cnt;
- rv.list = xmalloc(cnt*sizeof(struct elmnt));
+ rv.list = wiggle_xmalloc(cnt*sizeof(struct elmnt));
cnt = 0;
for (i = 0; i < orig.elcnt; i++)
if (!is_skipped(orig.list[i]))
}
}
-struct csl *pdiff(struct file a, struct file b, int chunks)
+struct csl *wiggle_pdiff(struct file a, struct file b, int chunks)
{
struct csl *csl1, *csl2;
- struct best *best = xmalloc(sizeof(struct best)*(chunks+1));
+ struct best *best = wiggle_xmalloc(sizeof(struct best)*(chunks+1));
int i;
struct file asmall, bsmall;
+ int xmin;
asmall = reduce(a);
bsmall = reduce(b);
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) {
- csl2 = diff_partial(a, b,
- best[i].xlo, best[i].xhi,
- best[i].ylo, best[i].yhi);
- csl1 = csl_join(csl1, csl2);
+ /* 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 = xmalloc(sizeof(*csl1));
+ csl1 = wiggle_xmalloc(sizeof(*csl1));
csl1->len = 0;
csl1->a = a.elcnt;
csl1->b = b.elcnt;