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 /* A 'cut-point' is a location in the merger where it is reasonable
83 * the change the mode of display - between displaying the merger
84 * and displaying the separate streams.
85 * A 'conflict' can only be displayed as separate stream so when
86 * one is found, we need to find a preceeding and trailing cut-point
87 * and enlarge the conflict to that range.
88 * A suitable location is one where all three streams are at a line-end.
90 static int is_cutpoint(struct merge m,
91 struct file af, struct file bf, struct file cf)
93 return ((m.a == 0 || ends_line(af.list[m.a-1])) &&
94 (m.b == 0 || ends_line(bf.list[m.b-1])) &&
95 (m.c == 0 || ends_line(cf.list[m.c-1])));
98 static int isolate_conflicts(struct file af, struct file bf, struct file cf,
99 struct csl *csl1, struct csl *csl2, int words,
100 struct merge *m, int show_wiggles)
102 /* A conflict indicates that something is definitely wrong
103 * and so we need to be a bit suspicious of nearby apparent matches.
104 * To display a conflict effectively we expands it's effect to
105 * include any Extraneous, Unmatched, Changed or AlreadyApplied text.
106 * Also, unless 'words', we need to include any partial lines
107 * in the Unchanged text that forms the border of a conflict.
109 * A Changed text may also border a conflict, but it can
110 * only border one conflict (where as an Unchanged can border
111 * a preceeding and a following conflict).
112 * The 'new' section of a Changed text appears in the
113 * conflict as does any part of the original before
116 * If 'show_wiggles' is set we treat wiggles like conflicts.
117 * A 'wiggle' is implied by any Extraneous text being ignored,
118 * or any line that has both Changed and Unmatched content.
119 * (Unmatched content where nothing is changed is common and not
120 * really a 'wiggle').
122 * A hunk header is never considered part of a conflict. It
123 * thereby can serve as a separator between conflicts.
125 * We need to ensure there is adequate context for the conflict.
126 * So ensure there are at least 3 newlines in Extraneous or
127 * Unchanged on both sides of a Conflict - but don't go so far
128 * as including a hunk header.
129 * If there are 3, and they are all in 'Unchanged' sections, then
130 * that much context is not really needed - reduce it a bit.
137 for (i = 0; m[i].type != End; i++) {
138 if (m[i].type == Changed)
140 if (m[i].type == Unmatched)
142 if (m[i].type == Conflict ||
143 (show_wiggles && ((changed && unmatched)
144 || m[i].type == Extraneous))) {
145 /* We have a conflict (or wiggle) here.
146 * First search backwards for an Unchanged marking
147 * things as in_conflict. Then find the
148 * cut-point in the Unchanged. If there isn't one,
151 * Then search forward doing the same thing.
155 m[i].in_conflict = 1;
158 if (m[j].type == Extraneous &&
159 bf.list[m[j].b].start[0] == '\0')
160 /* hunk header - not conflict any more */
162 if (!m[j].in_conflict) {
163 m[j].in_conflict = 1;
165 } else if (m[j].type == Changed) {
166 /* This can no longer form a border */
168 /* We merge these conflicts and stop searching */
172 if (m[j].type == Extraneous) {
173 for (k = m[j].bl; k > 0; k--)
174 if (ends_line(bf.list[m[j].b+k-1]))
178 if (m[j].type == Unchanged || m[j].type == Changed) {
179 /* If we find enough newlines in this section,
180 * then we only really need 1, but would rather
181 * it wasn't the first one. 'firstk' allows us
182 * to track which newline we actually use
184 int firstk = m[j].al;
189 /* need to find the last line-break, which
190 * might be after the last newline, if there
191 * is one, or might be at the start
193 for (k = m[j].al; k > 0; k--)
194 if (ends_line(af.list[m[j].a+k-1])) {
195 if (firstk == m[j].al)
205 else if (is_cutpoint(m[j], af,bf,cf))
208 /* no start-of-line found... */
210 if (m[j].hi > 0 && m[j].type == Changed) {
211 /* this can only work if start is
212 * also a line break */
213 if (is_cutpoint(m[j], af,bf,cf))
223 /* now the forward search */
225 for (j = i+1; m[j].type != End; j++) {
226 if (m[j].type == Extraneous &&
227 bf.list[m[j].b].start[0] == '\0')
228 /* hunk header - not conflict any more */
230 m[j].in_conflict = 1;
231 if (m[j].type == Extraneous) {
232 for (k = 0; k < m[j].bl; k++)
233 if (ends_line(bf.list[m[j].b+k]))
236 if (m[j].type == Unchanged || m[j].type == Changed) {
242 /* need to find a line-break, which might be at
243 * the very beginning, or might be after the
244 * first newline - if there is one
246 if (is_cutpoint(m[j], af,bf,cf))
249 /* If we find enough newlines in this section,
250 * then we only really need 1, but would rather
251 * it wasn't the first one. 'firstk' allows us
252 * to track which newline we actually use
255 for (k = 0 ; k < m[j].al ; k++)
256 if (ends_line(af.list[m[j].a+k])) {
268 /* no start-of-line found */
271 if (m[j].lo <= m[j].al+1 && m[j].type == Changed) {
272 /* this can only work if the end is a line break */
273 if (is_cutpoint(m[j+1], af,bf,cf))
278 if (m[j].lo < m[j].al+1)
284 if (ends_line(af.list[m[i].a+m[i].al-1])) {
292 struct ci make_merger(struct file af, struct file bf, struct file cf,
293 struct csl *csl1, struct csl *csl2, int words,
294 int ignore_already, int show_wiggles)
296 /* find the wiggles and conflicts between csl1 and csl2
301 int wiggle_found = 0;
303 rv.conflicts = rv.wiggles = rv.ignored = 0;
305 for (i = 0; csl1[i].len; i++)
308 for (i = 0; csl2[i].len; i++)
311 /* maybe a bit of slack at each end */
314 rv.merger = xmalloc(sizeof(struct merge)*l);
316 a = b = c = c1 = c2 = 0;
320 match1 = (a >= csl1[c1].a && b >= csl1[c1].b); /* c1 doesn't match */
321 match2 = (b >= csl2[c2].a && c >= csl2[c2].b);
326 rv.merger[i].c1 = c1;
327 rv.merger[i].c2 = c2;
328 rv.merger[i].in_conflict = 0;
330 if (!match1 && match2) {
331 /* This is either Unmatched or Extraneous - probably both.
332 * If the match2 is a hunk-header Extraneous, it must
333 * align with an end-of-line in 'a', so adjust endpoint
335 int newa = csl1[c1].a;
336 if (bf.list[b].start && bf.list[b].start[0] == '\0') {
338 !ends_line(af.list[newa-1]))
340 while (newa < af.elcnt && !(newa == 0 || ends_line(af.list[newa-1])))
344 /* some unmatched text */
345 rv.merger[i].type = Unmatched;
346 rv.merger[i].al = newa - a;
353 assert(b < csl1[c1].b);
354 /* some Extraneous text */
355 /* length is min of unmatched on left
356 * and matched on right.
357 * However a hunk-header must be an
358 * Extraneous section by itself, so if this
359 * start with one, the length is 1, and if
360 * there is one in the middle, only take the
361 * text up to there for now.
363 rv.merger[i].type = Extraneous;
367 csl2[c2].len - (b-csl2[c2].a));
368 if (bf.list[b].start[0] == '\0')
370 for (j = b; j < newb; j++) {
371 if (bf.list[j].start[0] == '\0') {
372 if (wiggle_found > 1)
381 rv.merger[i].bl = newb - b;
383 } else if (match1 && !match2) {
385 * if 'c' is currently at a suitable cut-point, then
386 * we can look for a triple-cut-point for start.
387 * Also, if csl2[c2].b isn't in a conflict, and is
388 * a suitable cut-point, then we could make a
389 * triple-cut-point for end of a conflict.
392 rv.merger[i].type = Changed;
393 rv.merger[i].bl = min(csl1[c1].b+csl1[c1].len, csl2[c2].a) - b;
394 rv.merger[i].al = rv.merger[i].bl;
395 rv.merger[i].cl = csl2[c2].b - c;
396 } else if (match1 && match2) {
397 /* Some unchanged text
399 rv.merger[i].type = Unchanged;
401 min(csl1[c1].len - (b-csl1[c1].b),
402 csl2[c2].len - (b-csl2[c2].a));
403 rv.merger[i].al = rv.merger[i].cl =
406 /* must be a conflict.
407 * Move a and c to next match, and b to closest of the two
409 rv.merger[i].type = Conflict;
410 rv.merger[i].al = csl1[c1].a - a;
411 rv.merger[i].cl = csl2[c2].b - c;
412 rv.merger[i].bl = min(csl1[c1].b, csl2[c2].a) - b;
413 if (ignore_already &&
414 check_alreadyapplied(af, cf, &rv.merger[i]))
417 a += rv.merger[i].al;
418 b += rv.merger[i].bl;
419 c += rv.merger[i].cl;
422 while (csl1[c1].a + csl1[c1].len <= a && csl1[c1].len)
424 assert(csl1[c1].b + csl1[c1].len >= b);
425 while (csl2[c2].b + csl2[c2].len <= c && csl2[c2].len)
427 assert(csl2[c2].a + csl2[c2].len >= b);
428 if (csl1[c1].len == 0 && csl2[c2].len == 0 &&
429 a == csl1[c1].a && b == csl1[c1].b &&
430 b == csl2[c2].a && c == csl2[c2].b)
433 rv.merger[i].type = End;
434 rv.merger[i].in_conflict = 0;
436 rv.conflicts = isolate_conflicts(af, bf, cf, csl1, csl2, words,
437 rv.merger, show_wiggles);
443 static void printrange(FILE *out, struct file *f, int start, int len)
446 printword(out, f->list[start]);
452 struct ci print_merge2(FILE *out, struct file *a, struct file *b, struct file *c,
453 struct csl *c1, struct csl *c2,
454 int words, int ignore_already, int show_wiggles)
456 struct ci rv = make_merger(*a, *b, *c, c1, c2,
457 words, ignore_already, show_wiggles);
460 for (m = rv.merger; m->type != End ; m++) {
463 printf("[%s: %d-%d,%d-%d,%d-%d%s(%d,%d)]\n",
464 m->type==Unmatched ? "Unmatched" :
465 m->type==Unchanged ? "Unchanged" :
466 m->type==Extraneous ? "Extraneous" :
467 m->type==Changed ? "Changed" :
468 m->type==AlreadyApplied ? "AlreadyApplied" :
469 m->type==Conflict ? "Conflict":"unknown",
473 m->in_conflict ? " in_conflict" : "",
476 while (m->in_conflict) {
477 /* need to print from 'hi' to 'lo' of next
478 * Unchanged which is < it's hi
480 int found_conflict = 0;
482 if (m->type == Unchanged || m->type == Changed)
487 if (m->type == Unchanged)
488 printrange(out, a, m->a+m->lo, m->hi - m->lo);
491 for (cm = m; cm->in_conflict; cm++) {
492 printf("{%s: %d-%d,%d-%d,%d-%d%s(%d,%d)}\n",
493 cm->type==Unmatched?"Unmatched":
494 cm->type==Unchanged?"Unchanged":
495 cm->type==Extraneous?"Extraneous":
496 cm->type==Changed?"Changed":
497 cm->type==AlreadyApplied?"AlreadyApplied":
498 cm->type==Conflict?"Conflict":"unknown",
499 cm->a, cm->a+cm->al-1,
500 cm->b, cm->b+cm->bl-1,
501 cm->c, cm->c+cm->cl-1,
502 cm->in_conflict ? " in_conflict" : "",
504 if ((cm->type == Unchanged || cm->type == Changed)
505 && cm != m && cm->lo < cm->hi)
509 fputs(words ? "<<<---" : "<<<<<<<\n", out);
510 for (cm = m; cm->in_conflict; cm++) {
511 if (cm->type == Conflict)
513 if ((cm->type == Unchanged || cm->type == Changed)
514 && cm != m && cm->lo < cm->hi) {
515 printrange(out, a, cm->a, cm->lo);
518 printrange(out, a, cm->a+st1, cm->al-st1);
521 fputs(words ? "|||" : "|||||||\n", out);
523 for (cm = m; cm->in_conflict; cm++) {
524 if ((cm->type == Unchanged || cm->type == Changed)
525 && cm != m && cm->lo < cm->hi) {
526 printrange(out, b, cm->b, cm->lo);
529 printrange(out, b, cm->b+st1, cm->bl-st1);
532 fputs(words ? "===" : "=======\n", out);
534 for (cm = m; cm->in_conflict; cm++) {
535 if (cm->type == Unchanged &&
536 cm != m && cm->lo < cm->hi) {
537 printrange(out, c, cm->c, cm->lo);
540 if (cm->type == Changed)
541 st1 = 0; /* All of result of change must be printed */
542 printrange(out, c, cm->c+st1, cm->cl-st1);
545 if (!found_conflict) {
546 /* This section was wiggled in successfully,
547 * but full conflict display was requested.
548 * So now print out the wiggled result as well.
550 fputs(words ? "&&&" : "&&&&&&&\n", out);
552 for (cm = m; cm->in_conflict; cm++) {
554 if ((cm->type == Unchanged || cm->type == Changed)
555 && cm != m && cm->lo < cm->hi)
561 printrange(out, a, cm->a+st1,
562 last ? cm->lo : cm->al-st1);
567 printrange(out, c, cm->c+st1,
568 last ? cm->lo : cm->cl-st1);
579 fputs(words ? "--->>>" : ">>>>>>>\n", out);
581 if (m->in_conflict && m->type == Unchanged
583 printrange(out, a, m->a+m->lo, m->hi-m->lo);
588 /* there is always some non-conflict after a conflict,
589 * unless we hit the end
595 printf("<<%s: %d-%d,%d-%d,%d-%d%s(%d,%d)>>\n",
596 m->type==Unmatched?"Unmatched":
597 m->type==Unchanged?"Unchanged":
598 m->type==Extraneous?"Extraneous":
599 m->type==Changed?"Changed":
600 m->type==AlreadyApplied?"AlreadyApplied":
601 m->type==Conflict?"Conflict":"unknown",
605 m->in_conflict ? " in_conflict" : "",
613 printrange(out, a, m->a, m->al);
618 printrange(out, c, m->c, m->cl);