2 * wiggle - apply rejected patches
4 * Copyright (C) 2005 Neil Brown <neilb@cse.unsw.edu.au>
5 * Copyright (C) 2010-2013 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.
22 * Email: <neilb@suse.de>
29 * Second attempt at merging....
31 * We want to create a mergelist which identifies 'orig' and 'after'
32 * sections (from a and c) and conflicts (which are ranges of a,b,c which
34 * It is also helpful to differentiate 'orig' sections that aren't
35 * matched in 'b' with orig sections that are.
36 * To help with highlighting, it will be useful to know where
37 * the conflicts match the csl lists.
39 * This can all be achieved with a list of (a,b,c,c1,c1) 5-tuples.
40 * If two consecutive differ in more than one of a,b,c, it is a
42 * If only 'a' differ, it is un-matched original.
43 * If only 'b' differ, it is matched, unchanged original
44 * If only 'c' differ, it is 1
47 static inline int min(int a, int b)
52 static int check_alreadyapplied(struct file af, struct file cf,
58 for (i = 0; i < m->al; i++) {
59 if (af.list[m->a+i].len != cf.list[m->c+i].len)
61 if (strncmp(af.list[m->a+i].start,
62 cf.list[m->c+i].start,
63 af.list[m->a+i].len) != 0)
67 printf("already applied %d,%d,%d - %d,%d,%d\n",
68 m->a, m->b, m->c, m->al, m->bl, m->cl);
69 printf(" %.10s - %.10s\n", af.list[m->a].start,
72 m->type = AlreadyApplied;
76 /* A 'cut-point' is a location in the merger where it is reasonable
77 * the change the mode of display - between displaying the merger
78 * and displaying the separate streams.
79 * A 'conflict' can only be displayed as separate stream so when
80 * one is found, we need to find a preceding and trailing cut-point
81 * and enlarge the conflict to that range.
82 * A suitable location is one where all three streams are at a line-end.
84 static int is_cutpoint(struct merge m,
85 struct file af, struct file bf, struct file cf)
87 return ((m.a == 0 || ends_line(af.list[m.a-1])) &&
88 (m.b == 0 || ends_line(bf.list[m.b-1])) &&
89 (m.c == 0 || ends_line(cf.list[m.c-1])));
92 int isolate_conflicts(struct file af, struct file bf, struct file cf,
93 struct csl *csl1, struct csl *csl2, int words,
94 struct merge *m, int show_wiggles,
97 /* A Conflict indicates that something is definitely wrong
98 * and so we need to be a bit suspicious of nearby apparent matches.
99 * To display a conflict effectively we expands its effect to
100 * include any Extraneous, Unmatched, Changed or AlreadyApplied text.
101 * Also, unless 'words', we need to include any partial lines
102 * in the Unchanged text that forms the border of a conflict.
104 * A Changed text may also border a conflict, but it can
105 * only border one conflict (where as an Unchanged can border
106 * a preceding and a following conflict).
107 * The 'new' section of a Changed text appears in the
108 * conflict as does any part of the original before
111 * A hunk header (Extraneous) is never considered part of a
112 * conflict. It thereby can serve as a separator between
115 * Extended conflicts are marked by setting ->in_conflict in
116 * the "struct merge". This is '1' for an Unchanged, Changed,
117 * or (Extraneous) hunk header which borders the conflict,
118 * '2' for a merger which is truly in conflict, and '3' for
119 * a merger which is causing a 'wiggle'.
120 * When in_conflict == 1, the 'lo' and 'hi' fields indicate
121 * how much of the 'a' file is included in the conflict, the rest
122 * being part of the clean result.
123 * Elements in af from m->a to m->a+m->lo are in the preceding
124 * conflict, from m->a+m->lo to m->a+m->hi are clean, and
125 * m->a+m->hi to m->a+m->al are in the following conflict.
127 * We need to ensure there is adequate context for the conflict.
128 * So ensure there are at least 3 newlines in Extraneous or
129 * Unchanged on both sides of a Conflict - but don't go so far
130 * as including a hunk header.
131 * If there are 3, and they are all in 'Unchanged' sections, then
132 * that much context is not really needed - reduce it a bit.
134 * If a wiggle is adjacent to a conflict then:
135 * - if show_wiggles is set, we just merge them
136 * - if it is not set, we still want to count the wiggle.
139 int cnt = 0, wiggles = 0;
145 for (i = 0; m[i].type != End; i++)
146 m[i].in_conflict = 0;
148 for (i = 0; m[i].type != End; i++) {
149 /* The '3' here is a count of newlines. Once we find
150 * that many newlines of the particular type, we have escaped.
152 if (m[i].type == Changed)
154 if (m[i].type == Unmatched)
156 if (m[i].type == Extraneous && bf.list[m[i].b].start[0])
157 /* hunk headers don't imply wiggles, other
158 * extraneous text does.
162 if (m[i].type != Unchanged && changed && (unmatched || extraneous)) {
169 if ((m[i].type == Conflict) ||
170 (show_wiggles && in_wiggle)) {
171 /* We have a conflict or wiggle here.
172 * First search backwards for an Unchanged marking
173 * things as in_conflict. Then find the
174 * cut-point in the Unchanged. If there isn't one,
177 * Then search forward doing the same thing.
180 m[i].in_conflict = m[i].type == Conflict ? 2 : 3;
185 if (m[j].type == Extraneous &&
186 bf.list[m[j].b].start[0] == '\0')
187 /* hunk header - not conflict any more */
189 if (m[j].in_conflict > 1)
190 /* Merge the conflicts */
192 if (!m[j].in_conflict) {
193 m[j].in_conflict = 1;
196 /* Following must set m[j].hi, or set
199 if (m[j].type == Extraneous) {
200 for (k = m[j].bl; k > 0; k--)
201 if (ends_line(bf.list[m[j].b+k-1]))
205 if (m[j].type != Unchanged &&
206 m[j].type != Changed) {
207 if (m[j].type == Conflict)
208 m[j].in_conflict = 2;
210 m[j].in_conflict = m[i].in_conflict;
213 /* If we find enough newlines in this section,
214 * then we only really need 1, but would rather
215 * it wasn't the first one. 'firstk' allows us
216 * to track which newline we actually use
223 /* need to find the last line-break, which
224 * might be after the last newline, if there
225 * is one, or might be at the start
227 for (k = m[j].al; k > 0; k--)
228 if (ends_line(af.list[m[j].a+k-1])) {
229 if (firstk > m[j].al)
241 else if (is_cutpoint(m[j], af,bf,cf))
244 /* no start-of-line found... */
247 (m[j].type == Changed)) {
248 /* this can only work if start is
249 * also a line break */
250 if (is_cutpoint(m[j], af,bf,cf))
257 m[j].in_conflict = m[i].in_conflict;
260 /* now the forward search */
262 for (j = i+1; m[j].type != End; j++) {
263 if (m[j].type == Extraneous &&
264 bf.list[m[j].b].start[0] == '\0')
265 /* hunk header - not conflict any more */
267 if (m[j].type == Extraneous) {
268 for (k = 0; k < m[j].bl; k++)
269 if (ends_line(bf.list[m[j].b+k]))
272 if (m[j].type != Unchanged &&
273 m[j].type != Changed) {
274 if (m[j].type == Conflict)
275 m[j].in_conflict = 2;
277 m[j].in_conflict = m[i].in_conflict;
280 m[j].in_conflict = 1;
286 /* need to find a line-break, which might be at
287 * the very beginning, or might be after the
288 * first newline - if there is one
290 if (is_cutpoint(m[j], af,bf,cf))
293 /* If we find enough newlines in this section,
294 * then we only really need 1, but would rather
295 * it wasn't the first one. 'firstk' allows us
296 * to track which newline we actually use
299 for (k = 0 ; k < m[j].al ; k++)
300 if (ends_line(af.list[m[j].a+k])) {
311 /* Hit end of file, pretend we found 3 newlines. */
315 m[j+1].type == Unmatched) {
316 /* If this Unmatched exceeds 3 lines, just stop here */
319 for (p = 0; p < m[j+1].al ; p++)
320 if (ends_line(af.list[m[j+1].a+p])) {
331 /* no start-of-line found */
334 if (m[j].lo <= m[j].al+1 &&
335 (m[j].type == Changed)) {
336 /* this can only work if the end is a line break */
337 if (is_cutpoint(m[j+1], af,bf,cf))
342 if (m[j].lo < m[j].al+1)
344 m[j].in_conflict = m[i].in_conflict;
346 if (m[j-1].in_conflict == 1)
349 /* A hunk header bordered the conflict */
352 /* If any of the merges are Changed or Conflict,
353 * then this really is a Conflict or Wiggle.
354 * If not they are just Unchanged, Unmatched,
355 * Extraneous or AlreadyApplied, and so don't
357 * Note that the first/last merges (in_conflict==1)
358 * can be Changed and so much be check separately.
360 if (m[j].type == Changed)
362 for (j = i-1; j >= 0 && m[j].in_conflict > 1; j--)
363 if (m[j].type == Changed || m[j].type == Conflict)
365 if (j >= 0 && m[j].type == Changed)
367 /* False alarm, no real conflict/wiggle here as
368 * nothing changed. */
371 if (m[j].in_conflict == 1) {
374 m[j].in_conflict = 0;
378 m[j++].in_conflict = 0;
380 if (m[i].type == End)
383 for (k = 1; k < m[i].al; k++)
384 if (words || ends_line(af.list[m[i].a+k])) {
395 /* Now count the conflicts and wiggles */
396 for (i = 0; m[i].type != End; i++) {
397 int true_conflict = 0;
398 if (!m[i].in_conflict)
401 for (j = i; m[j].type != End && m[j].in_conflict; j++) {
402 if (m[j].in_conflict == 2)
405 m[j].in_conflict == 1) {
407 if (!m[j+1].in_conflict)
423 struct ci make_merger(struct file af, struct file bf, struct file cf,
424 struct csl *csl1, struct csl *csl2, int words,
425 int ignore_already, int show_wiggles)
427 /* find the wiggles and conflicts between csl1 and csl2
432 int header_checked = -1;
433 int header_found = 0;
435 rv.conflicts = rv.wiggles = rv.ignored = 0;
437 for (i = 0; csl1[i].len; i++)
440 for (i = 0; csl2[i].len; i++)
443 /* maybe a bit of slack at each end */
446 rv.merger = xmalloc(sizeof(struct merge)*l);
448 a = b = c = c1 = c2 = 0;
452 match1 = (a >= csl1[c1].a && b >= csl1[c1].b); /* c1 doesn't match */
453 match2 = (b >= csl2[c2].a && c >= csl2[c2].b);
455 if (header_checked != c2) {
456 /* Check if there is a hunk header in this range */
459 for (j = b; j < csl2[c2].a + csl2[c2].len; j++)
460 if (bf.list[j].start[0] == '\0') {
469 rv.merger[i].c1 = c1;
470 rv.merger[i].c2 = c2;
471 rv.merger[i].in_conflict = 0;
473 if (!match1 && match2) {
474 /* This is either Unmatched or Extraneous - probably both.
475 * If the match2 has a hunk-header Extraneous, it must
476 * align with an end-of-line in 'a', so adjust endpoint
478 int newa = csl1[c1].a;
479 if (header_found >= 0) {
481 !ends_line(af.list[newa-1]))
484 if (a == newa && b == csl1[c1].b)
487 /* some unmatched text */
488 rv.merger[i].type = Unmatched;
489 rv.merger[i].al = newa - a;
494 assert(b < csl1[c1].b);
495 /* some Extraneous text */
496 /* length is min of unmatched on left
497 * and matched on right.
498 * However a hunk-header must be an
499 * Extraneous section by itself, so if this
500 * start with one, the length is 1, and if
501 * there is one in the middle, only take the
502 * text up to there for now.
504 rv.merger[i].type = Extraneous;
508 csl2[c2].len - (b-csl2[c2].a));
509 if (header_found == b) {
512 } else if (header_found > b && header_found < newb) {
518 rv.merger[i].bl = newb - b;
520 } else if (match1 && !match2) {
522 * if 'c' is currently at a suitable cut-point, then
523 * we can look for a triple-cut-point for start.
524 * Also, if csl2[c2].b isn't in a conflict, and is
525 * a suitable cut-point, then we could make a
526 * triple-cut-point for end of a conflict.
529 rv.merger[i].type = Changed;
530 rv.merger[i].bl = min(csl1[c1].b+csl1[c1].len, csl2[c2].a) - b;
531 rv.merger[i].al = rv.merger[i].bl;
532 rv.merger[i].cl = csl2[c2].b - c;
533 } else if (match1 && match2) {
534 /* Some unchanged text
536 rv.merger[i].type = Unchanged;
538 min(csl1[c1].len - (b-csl1[c1].b),
539 csl2[c2].len - (b-csl2[c2].a));
540 rv.merger[i].al = rv.merger[i].cl =
543 /* must be a conflict.
544 * Move a and c to next match, and b to closest of the two
546 rv.merger[i].type = Conflict;
547 rv.merger[i].al = csl1[c1].a - a;
548 rv.merger[i].cl = csl2[c2].b - c;
549 rv.merger[i].bl = min(csl1[c1].b, csl2[c2].a) - b;
550 if (ignore_already &&
551 check_alreadyapplied(af, cf, &rv.merger[i]))
553 else if (rv.merger[i].bl == 0 &&
555 /* As the 'before' stream is empty, this
556 * could look like Unmatched in the
557 * original, and an insertion in the
558 * diff. Reporting it like that is
559 * probably more useful that as a full
561 * Leave the type for the insertion as
562 * Conflict (not Changed) as there is some
563 * real uncertainty here, but allow the
564 * original to become Unmatched.
568 rv.merger[i].oldtype = rv.merger[i].type;
569 a += rv.merger[i].al;
570 b += rv.merger[i].bl;
571 c += rv.merger[i].cl;
574 while (csl1[c1].a + csl1[c1].len <= a && csl1[c1].len)
576 assert(csl1[c1].b + csl1[c1].len >= b);
577 while (csl2[c2].b + csl2[c2].len <= c && csl2[c2].len)
579 assert(csl2[c2].a + csl2[c2].len >= b);
580 if (csl1[c1].len == 0 && csl2[c2].len == 0 &&
581 a == csl1[c1].a && b == csl1[c1].b &&
582 b == csl2[c2].a && c == csl2[c2].b)
585 rv.merger[i].type = End;
586 rv.merger[i].oldtype = End;
590 rv.merger[i].c1 = c1;
591 rv.merger[i].c2 = c2;
592 rv.merger[i].in_conflict = 0;
595 /* Now revert any AlreadyApplied that aren't bounded by
596 * Unchanged or Changed.
598 for (i = 0; rv.merger[i].type != End; i++) {
599 if (rv.merger[i].type != AlreadyApplied)
601 if (i > 0 && rv.merger[i-1].type != Unchanged &&
602 rv.merger[i-1].type != Changed)
603 rv.merger[i].type = Conflict;
604 if (rv.merger[i+1].type != Unchanged &&
605 rv.merger[i+1].type != Changed &&
606 rv.merger[i+1].type != End)
607 rv.merger[i].type = Conflict;
609 rv.conflicts = isolate_conflicts(af, bf, cf, csl1, csl2, words,
610 rv.merger, show_wiggles, &rv.wiggles);
614 static int printrange(FILE *out, struct file *f, int start, int len,
619 struct elmnt e = f->list[start];
621 if (e.start[e.plen-1] == '\n' &&
631 int print_merge(FILE *out, struct file *a, struct file *b, struct file *c,
632 int words, struct merge *merger,
633 struct merge *mpos, int streampos, int offsetpos)
638 int offset = INT_MAX;
640 for (m = merger; m->type != End ; m++) {
643 printf("[%s: %d-%d,%d-%d,%d-%d%s(%d,%d)]\n",
644 m->type==Unmatched ? "Unmatched" :
645 m->type==Unchanged ? "Unchanged" :
646 m->type==Extraneous ? "Extraneous" :
647 m->type==Changed ? "Changed" :
648 m->type==AlreadyApplied ? "AlreadyApplied" :
649 m->type==Conflict ? "Conflict":"unknown",
653 m->in_conflict ? " in_conflict" : "",
656 while (m->in_conflict) {
657 /* need to print from 'hi' to 'lo' of next
658 * Unchanged which is < it's hi
660 int found_conflict = 0;
662 if (m->in_conflict == 1)
668 if (m->in_conflict == 1 && m->type == Unchanged)
669 lineno += printrange(out, a, m->a+m->lo, m->hi - m->lo, offset - m->lo);
674 for (cm = m; cm->in_conflict; cm++) {
675 printf("{%s: %d-%d,%d-%d,%d-%d%s(%d,%d)}\n",
676 cm->type==Unmatched?"Unmatched":
677 cm->type==Unchanged?"Unchanged":
678 cm->type==Extraneous?"Extraneous":
679 cm->type==Changed?"Changed":
680 cm->type==AlreadyApplied?"AlreadyApplied":
681 cm->type==Conflict?"Conflict":"unknown",
682 cm->a, cm->a+cm->al-1,
683 cm->b, cm->b+cm->bl-1,
684 cm->c, cm->c+cm->cl-1,
685 cm->in_conflict ? " in_conflict" : "",
687 if (cm->in_conflict == 1 && cm != m)
691 if (m->in_conflict == 1 &&
692 m[1].in_conflict == 1) {
693 /* Nothing between two conflicts */
698 fputs(words ? "<<<---" : "<<<<<<< found\n", out);
701 for (cm = m; cm->in_conflict; cm++) {
702 if (cm == mpos && streampos == 0)
704 if (cm->type == Conflict)
706 if (cm->in_conflict == 1 && cm != m) {
707 lineno += printrange(out, a, cm->a, cm->lo, offset);
710 lineno += printrange(out, a, cm->a+st1, cm->al-st1, offset-st1);
712 if (cm == mpos && streampos == 0)
715 if (cm == mpos && streampos == 0)
717 fputs(words ? "|||" : "||||||| expected\n", out);
721 for (cm = m; cm->in_conflict; cm++) {
722 if (cm == mpos && streampos == 1)
724 if (cm->in_conflict == 1 && cm != m) {
725 lineno += printrange(out, a, cm->a, cm->lo, offset);
728 lineno += printrange(out, b, cm->b+st1, cm->bl-st1, offset-st1);
730 if (cm == mpos && streampos == 1)
733 if (cm == mpos && streampos == 1)
735 fputs(words ? "===" : "=======\n", out);
739 for (cm = m; cm->in_conflict; cm++) {
740 if (cm == mpos && streampos == 2)
742 if (cm->in_conflict == 1 && cm != m) {
743 if (cm->type == Unchanged)
744 lineno += printrange(out, a, cm->a, cm->lo, offset);
746 lineno += printrange(out, c, cm->c, cm->cl, offset);
749 if (cm->type == Changed)
750 st1 = 0; /* All of result of change must be printed */
751 lineno += printrange(out, c, cm->c+st1, cm->cl-st1, offset-st1);
753 if (cm == mpos && streampos == 2)
756 if (cm == mpos && streampos == 2)
758 if (!found_conflict) {
759 /* This section was wiggled in successfully,
760 * but full conflict display was requested.
761 * So now print out the wiggled result as well.
763 fputs(words ? "&&&" : "&&&&&&& resolution\n", out);
767 for (cm = m; cm->in_conflict; cm++) {
769 if (cm->in_conflict == 1 && cm != m)
775 lineno += printrange(out, a, cm->a+st1,
776 last ? cm->lo : cm->al-st1, offset-st1);
781 lineno += printrange(out, c, cm->c,
782 last ? cm->lo : cm->cl, offset);
793 fputs(words ? "--->>>" : ">>>>>>> replacement\n", out);
797 if (m->in_conflict == 1 && m[1].in_conflict == 0) {
798 /* End of a conflict, no conflict follows */
801 if (m->type == Unchanged)
802 lineno += printrange(out, a, m->a+m->lo, m->hi-m->lo, offset-m->lo);
809 /* there is always some non-conflict after a conflict,
810 * unless we hit the end
816 printf("<<%s: %d-%d,%d-%d,%d-%d%s(%d,%d)>>\n",
817 m->type==Unmatched?"Unmatched":
818 m->type==Unchanged?"Unchanged":
819 m->type==Extraneous?"Extraneous":
820 m->type==Changed?"Changed":
821 m->type==AlreadyApplied?"AlreadyApplied":
822 m->type==Conflict?"Conflict":"unknown",
826 m->in_conflict ? " in_conflict" : "",
836 lineno += printrange(out, a, m->a, m->al, offset);
841 lineno += printrange(out, c, m->c, m->cl, offset);
853 int save_merge(struct file a, struct file b, struct file c,
854 struct merge *merger, char *file, int backup)
856 char *replacename = xmalloc(strlen(file) + 20);
857 char *orignew = xmalloc(strlen(file) + 20);
862 strcpy(replacename, file);
863 strcat(replacename, "XXXXXX");
864 strcpy(orignew, file);
865 strcat(orignew, ".porig");
867 fd = mkstemp(replacename);
872 outfile = fdopen(fd, "w");
873 lineno = print_merge(outfile, &a, &b, &c, 0, merger,
876 if (backup && rename(file, orignew) != 0)
878 else if (rename(replacename, file) != 0)
884 return err < 0 ? err : lineno;
887 int save_tmp_merge(struct file a, struct file b, struct file c,
888 struct merge *merger, char **filep,
889 struct merge *mpos, int streampos, int offsetpos)
898 dir = getenv("TMPDIR");
902 asprintf(&fname, "%s/wiggle-tmp-XXXXXX", dir);
906 base = strrchr(dir, '/');
911 asprintf(&fname, "%.*stmp-XXXXXX-%s", (int)(base-dir), dir, base);
912 suffix = strlen(base)+1;
914 fd = mkstemps(fname, suffix);
921 outfile = fdopen(fd, "w");
922 lineno = print_merge(outfile, &a, &b, &c, 0, merger,
923 mpos, streampos, offsetpos);