2 * wiggle - apply rejected patches
4 * Copyright (C) 2005 Neil Brown <neilb@cse.unsw.edu.au>
5 * Copyright (C) 2010 Neil Brown <neilb@suse.de>
8 * This program is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or
11 * (at your option) any later version.
13 * This program is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
18 * You should have received a copy of the GNU General Public License
19 * along with this program; if not, write to the Free Software Foundation, Inc.,
20 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
23 * Email: <neilb@suse.de>
30 * Second attempt at merging....
32 * We want to create a mergelist which identifies 'orig' and 'after'
33 * sections (from a and c) and conflicts (which are ranges of a,b,c which
35 * It is also helpful to differentiate 'orig' sections that aren't
36 * matched in 'b' with orig sections that are.
37 * To help with highlighting, it will be useful to know where
38 * the conflicts match the csl lists.
40 * This can all be achieved with a list of (a,b,c,c1,c1) 5-tuples.
41 * If two consecutive differ in more than one of a,b,c, it is a
43 * If only 'a' differ, it is un-matched original.
44 * If only 'b' differ, it is matched, unchanged original
45 * If only 'c' differ, it is 1
48 static inline int min(int a, int b)
52 static inline void assert(int a)
58 static int check_alreadyapplied(struct file af, struct file cf,
64 for (i = 0; i < m->al; i++) {
65 if (af.list[m->a+i].len != cf.list[m->c+i].len)
67 if (strncmp(af.list[m->a+i].start,
68 cf.list[m->c+i].start,
69 af.list[m->a+i].len) != 0)
73 printf("already applied %d,%d,%d - %d,%d,%d\n",
74 m->a, m->b, m->c, m->al, m->bl, m->cl);
75 printf(" %.10s - %.10s\n", af.list[m->a].start,
78 m->type = AlreadyApplied;
82 static int isolate_conflicts(struct file af, struct file bf, struct file cf,
83 struct csl *csl1, struct csl *csl2, int words,
86 /* A conflict indicates that something is definitely wrong
87 * and so we need to be a bit suspicious of nearby apparent matches.
88 * To display a conflict effectively we expands it's effect to
89 * include any Extraneous, Unmatched, Changed or AlreadyApplied text.
90 * Also, unless 'words', we need to include any partial lines
91 * in the Unchanged text that forms the border of a conflict.
93 * A Changed text may also border a conflict, but it can
94 * only border one conflict (where as an Unchanged can border
95 * a preceeding and a following conflict).
96 * The 'new' section of a Changed text appears in the
97 * conflict as does any part of the original before
104 for (i = 0; m[i].type != End; i++)
105 if (m[i].type == Conflict) {
106 /* We have a conflict here.
107 * First search backwards for an Unchanged marking
108 * things as in_conflict. Then find the
109 * cut-point in the Unchanged. If there isn't one,
112 * Then search forward doing the same thing.
115 m[i].in_conflict = 1;
118 if (!m[j].in_conflict) {
119 m[j].in_conflict = 1;
121 } else if (m[j].type == Changed) {
122 /* This can no longer form a border */
124 /* We merge these conflicts and stop searching */
129 if (m[j].type == Unchanged || m[j].type == Changed) {
134 /* need to find the last line-break, which
135 * might be after the last newline, if there
136 * is one, or might be at the start
138 for (k = m[j].al; k > 0; k--)
139 if (ends_line(af.list[m[j].a+k-1]))
143 else if ((m[j].a == 0 || ends_line(af.list[m[j].a-1])) &&
144 (m[j].b == 0 || ends_line(bf.list[m[j].b-1])) &&
145 (m[j].c == 0 || ends_line(cf.list[m[j].c-1])))
148 /* no start-of-line found... */
150 if (m[j].hi > 0 && m[j].type == Changed) {
151 /* this can only work if start is also a line break */
152 if ((m[j].a == 0 || ends_line(af.list[m[j].a-1])) &&
153 (m[j].b == 0 || ends_line(bf.list[m[j].b-1])) &&
154 (m[j].c == 0 || ends_line(cf.list[m[j].c-1])))
164 if (j >= 0 && m[j].in_conflict && m[j].type == Unchanged &&
165 m[j].hi == m[j].lo) {
166 /* nothing to separate conflicts, merge them */
172 /* now the forward search */
173 for (j = i+1; m[j].type != End; j++) {
174 m[j].in_conflict = 1;
175 if (m[j].type == Unchanged || m[j].type == Changed) {
181 /* need to find a line-break, which might be at
182 * the very beginning, or might be after the
183 * first newline - if there is one
185 if ((m[j].a == 0 || ends_line(af.list[m[j].a-1])) &&
186 (m[j].b == 0 || ends_line(bf.list[m[j].b-1])) &&
187 (m[j].c == 0 || ends_line(cf.list[m[j].c-1])))
190 for (k = 0 ; k < m[j].al ; k++)
191 if (ends_line(af.list[m[j].a+k]))
196 /* no start-of-line found */
199 if (m[j].lo <= m[j].al+1 && m[j].type == Changed) {
200 /* this can only work if the end is a line break */
201 if (ends_line(af.list[m[j].a+m[j].al-1]) &&
202 ends_line(bf.list[m[j].b+m[j].bl-1]) &&
203 ends_line(cf.list[m[j].c+m[j].cl-1]))
208 if (m[j].lo < m[j].al+1)
217 struct ci make_merger(struct file af, struct file bf, struct file cf,
218 struct csl *csl1, struct csl *csl2, int words,
221 /* find the wiggles and conflicts between csl1 and csl2
226 int wiggle_found = 0;
228 rv.conflicts = rv.wiggles = rv.ignored = 0;
230 for (i = 0; csl1[i].len; i++)
233 for (i = 0; csl2[i].len; i++)
236 /* maybe a bit of slack at each end */
239 rv.merger = xmalloc(sizeof(struct merge)*l);
241 a = b = c = c1 = c2 = 0;
245 match1 = (a >= csl1[c1].a && b >= csl1[c1].b); /* c1 doesn't match */
246 match2 = (b >= csl2[c2].a && c >= csl2[c2].b);
251 rv.merger[i].c1 = c1;
252 rv.merger[i].c2 = c2;
253 rv.merger[i].in_conflict = 0;
255 if (!match1 && match2) {
256 if (a < csl1[c1].a) {
257 /* some unmatched text */
258 rv.merger[i].type = Unmatched;
259 rv.merger[i].al = csl1[c1].a - a;
266 assert(b < csl1[c1].b);
267 /* some Extraneous text */
268 /* length is min of unmatched on left
269 * and matched on right
271 rv.merger[i].type = Extraneous;
276 csl2[c2].len - (b-csl2[c2].a));
277 newb = b+rv.merger[i].bl;
278 for (j = b; j < newb; j++) {
279 if (bf.list[j].start[0] == '\0') {
280 if (wiggle_found > 1)
287 } else if (match1 && !match2) {
289 * if 'c' is currently at a suitable cut-point, then
290 * we can look for a triple-cut-point for start.
291 * Also, if csl2[c2].b isn't in a conflict, and is
292 * a suitable cut-point, then we could make a
293 * triple-cut-point for end of a conflict.
296 rv.merger[i].type = Changed;
297 rv.merger[i].bl = min(csl1[c1].b+csl1[c1].len, csl2[c2].a) - b;
298 rv.merger[i].al = rv.merger[i].bl;
299 rv.merger[i].cl = csl2[c2].b - c;
300 } else if (match1 && match2) {
301 /* Some unchanged text
303 rv.merger[i].type = Unchanged;
305 min(csl1[c1].len - (b-csl1[c1].b),
306 csl2[c2].len - (b-csl2[c2].a));
307 rv.merger[i].al = rv.merger[i].cl =
310 /* must be a conflict.
311 * Move a and c to next match, and b to closest of the two
313 rv.merger[i].type = Conflict;
314 rv.merger[i].al = csl1[c1].a - a;
315 rv.merger[i].cl = csl2[c2].b - c;
316 rv.merger[i].bl = min(csl1[c1].b, csl2[c2].a) - b;
317 if (ignore_already &&
318 check_alreadyapplied(af, cf, &rv.merger[i]))
321 a += rv.merger[i].al;
322 b += rv.merger[i].bl;
323 c += rv.merger[i].cl;
326 while (csl1[c1].a + csl1[c1].len <= a && csl1[c1].len)
328 assert(csl1[c1].b + csl1[c1].len >= b);
329 while (csl2[c2].b + csl2[c2].len <= c && csl2[c2].len)
331 assert(csl2[c2].a + csl2[c2].len >= b);
332 if (csl1[c1].len == 0 && csl2[c2].len == 0 &&
333 a == csl1[c1].a && b == csl1[c1].b &&
334 b == csl2[c2].a && c == csl2[c2].b)
337 rv.merger[i].type = End;
338 rv.merger[i].in_conflict = 0;
339 rv.conflicts = isolate_conflicts(af, bf, cf, csl1, csl2, words, rv.merger);
345 static void printrange(FILE *out, struct file *f, int start, int len)
348 printword(out, f->list[start]);
354 struct ci print_merge2(FILE *out, struct file *a, struct file *b, struct file *c,
355 struct csl *c1, struct csl *c2,
356 int words, int ignore_already)
358 struct ci rv = make_merger(*a, *b, *c, c1, c2,
359 words, ignore_already);
362 for (m = rv.merger; m->type != End ; m++) {
367 if (getenv("WiggleVerbose"))
373 printf("[%s: %d-%d,%d-%d,%d-%d%s(%d,%d)]\n",
374 m->type==Unmatched ? "Unmatched" :
375 m->type==Unchanged ? "Unchanged" :
376 m->type==Extraneous ? "Extraneous" :
377 m->type==Changed ? "Changed" :
378 m->type==AlreadyApplied ? "AlreadyApplied" :
379 m->type==Conflict ? "Conflict":"unknown",
383 m->in_conflict ? " in_conflict" : "",
386 while (m->in_conflict) {
387 /* need to print from 'hi' to 'lo' of next
388 * Unchanged which is < it's hi
391 if (m->type == Unchanged || m->type == Changed)
396 if (m->type == Unchanged)
397 printrange(out, a, m->a+m->lo, m->hi - m->lo);
401 for (cm = m; cm->in_conflict; cm++) {
402 printf("{%s: %d-%d,%d-%d,%d-%d%s(%d,%d)}\n",
403 cm->type==Unmatched?"Unmatched":
404 cm->type==Unchanged?"Unchanged":
405 cm->type==Extraneous?"Extraneous":
406 cm->type==Changed?"Changed":
407 cm->type==AlreadyApplied?"AlreadyApplied":
408 cm->type==Conflict?"Conflict":"unknown",
409 cm->a, cm->a+cm->al-1,
410 cm->b, cm->b+cm->bl-1,
411 cm->c, cm->c+cm->cl-1,
412 cm->in_conflict ? " in_conflict" : "",
414 if ((cm->type == Unchanged || cm->type == Changed) && cm != m && cm->lo < cm->hi)
419 fputs(words ? "<<<---" : "<<<<<<<\n", out);
420 for (cm = m; cm->in_conflict; cm++) {
421 if ((cm->type == Unchanged || cm->type == Changed) && cm != m && cm->lo < cm->hi) {
422 printrange(out, a, cm->a, cm->lo);
425 printrange(out, a, cm->a+st1, cm->al-st1);
428 fputs(words ? "|||" : "|||||||\n", out);
430 for (cm = m; cm->in_conflict; cm++) {
431 if ((cm->type == Unchanged || cm->type == Changed) && cm != m && cm->lo < cm->hi) {
432 printrange(out, b, cm->b, cm->lo);
435 printrange(out, b, cm->b+st1, cm->bl-st1);
438 fputs(words ? "===" : "=======\n", out);
440 for (cm = m; cm->in_conflict; cm++) {
441 if (cm->type == Unchanged && cm != m && cm->lo < cm->hi) {
442 printrange(out, c, cm->c, cm->lo);
445 if (cm->type == Changed)
446 st1 = 0; /* All of result of change must be printed */
447 printrange(out, c, cm->c+st1, cm->cl-st1);
450 fputs(words ? "--->>>" : ">>>>>>>\n", out);
452 if (m->in_conflict && m->type == Unchanged
454 printrange(out, a, m->a+m->lo, m->hi-m->lo);
459 /* there is always some non-conflict after a conflict,
460 * unless we hit the end
466 printf("<<%s: %d-%d,%d-%d,%d-%d%s(%d,%d)>>\n",
467 m->type==Unmatched?"Unmatched":
468 m->type==Unchanged?"Unchanged":
469 m->type==Extraneous?"Extraneous":
470 m->type==Changed?"Changed":
471 m->type==AlreadyApplied?"AlreadyApplied":
472 m->type==Conflict?"Conflict":"unknown",
476 m->in_conflict ? " in_conflict" : "",
484 printrange(out, a, m->a, m->al);
489 printrange(out, c, m->c, m->cl);