1 /* Merge a patch
2
3 Copyright (C) 2009-2012 Free Software Foundation, Inc.
4 Written by Andreas Gruenbacher <agruen@gnu.org>, 2009.
5
6 This program is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
10
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>. */
18
19 #define XTERN extern
20 #include <common.h>
21 #include <minmax.h>
22 #include <xalloc.h>
23 #include <inp.h>
24 #include <pch.h>
25 #include <util.h>
26
27 static lin count_context_lines (void);
28 static bool context_matches_file (lin, lin);
29 static void compute_changes (lin, lin, lin, lin, char *, char *);
30
31 #define OFFSET lin
32 #define EQUAL_IDX(x, y) (context_matches_file (x, y))
33 #include "bestmatch.h"
34
35 #define XVECREF_YVECREF_EQUAL(ctxt, x, y) (context_matches_file (x, y))
36 #define OFFSET lin
37 #define EXTRA_CONTEXT_FIELDS \
38 char *xchar; \
39 char *ychar;
40 #define NOTE_DELETE(ctxt, xoff) ctxt->xchar[xoff] = '-';
41 #define NOTE_INSERT(ctxt, yoff) ctxt->ychar[yoff] = '+';
42 #define USE_HEURISTIC 1
43 #include "diffseq.h"
44
45 static lin
locate_merge(lin * matched)46 locate_merge (lin *matched)
47 {
48 lin first_guess = pch_first () + in_offset;
49 lin pat_lines = pch_ptrn_lines ();
50 lin context_lines = count_context_lines ();
51 lin max_where = input_lines - pat_lines + context_lines + 1;
52 lin min_where = last_frozen_line + 1;
53 lin max_pos_offset = max_where - first_guess;
54 lin max_neg_offset = first_guess - min_where;
55 lin max_offset = (max_pos_offset < max_neg_offset
56 ? max_neg_offset : max_pos_offset);
57 lin where = first_guess, max_matched = 0;
58 lin min, max;
59 lin offset;
60 bool match_until_eof;
61
62 /* Note: we need to preserve patch's property that it applies hunks at the
63 best match closest to their original position in the file. It is
64 common for hunks to apply equally well in several places in a file.
65 Applying at the first best match would be a lot easier.
66 */
67
68 if (context_lines == 0)
69 goto out; /* locate_hunk() already tried that */
70
71 /* Allow at most CONTEXT_LINES lines to be replaced (replacing counts
72 as insert + delete), and require the remaining MIN lines to match. */
73 max = 2 * context_lines;
74 min = pat_lines - context_lines;
75
76 if (debug & 1)
77 {
78 char numbuf0[LINENUM_LENGTH_BOUND + 1];
79 char numbuf1[LINENUM_LENGTH_BOUND + 1];
80 say ("locating merge: min=%s max=%s ",
81 format_linenum (numbuf0, min),
82 format_linenum (numbuf1, max));
83 }
84
85 /* Hunks from the start or end of the file have less context. Anchor them
86 to the start or end, trying to make up for this disadvantage. */
87 offset = pch_suffix_context () - pch_prefix_context ();
88 if (offset > 0 && pch_first () <= 1)
89 max_pos_offset = 0;
90 match_until_eof = offset < 0;
91
92 /* Do not try lines <= 0. */
93 if (first_guess <= max_neg_offset)
94 max_neg_offset = first_guess - 1;
95
96 for (offset = 0; offset <= max_offset; offset++)
97 {
98 if (offset <= max_pos_offset)
99 {
100 lin guess = first_guess + offset;
101 lin last;
102 lin changes;
103
104 changes = bestmatch (1, pat_lines + 1, guess, input_lines + 1,
105 match_until_eof ? input_lines - guess + 1 : min,
106 max, &last);
107 if (changes <= max && max_matched < last - guess)
108 {
109 max_matched = last - guess;
110 where = guess;
111 if (changes == 0)
112 break;
113 min = last - guess;
114 max = changes - 1;
115 }
116 }
117 if (0 < offset && offset <= max_neg_offset)
118 {
119 lin guess = first_guess - offset;
120 lin last;
121 lin changes;
122
123 changes = bestmatch (1, pat_lines + 1, guess, input_lines + 1,
124 match_until_eof ? input_lines - guess + 1 : min,
125 max, &last);
126 if (changes <= max && max_matched < last - guess)
127 {
128 max_matched = last - guess;
129 where = guess;
130 if (changes == 0)
131 break;
132 min = last - guess;
133 max = changes - 1;
134 }
135 }
136 }
137 if (debug & 1)
138 {
139 char numbuf0[LINENUM_LENGTH_BOUND + 1];
140 char numbuf1[LINENUM_LENGTH_BOUND + 1];
141 char numbuf2[LINENUM_LENGTH_BOUND + 1];
142 say ("where=%s matched=%s changes=%s\n",
143 format_linenum (numbuf0, where),
144 format_linenum (numbuf1, max_matched),
145 format_linenum (numbuf2, max + 1));
146 }
147
148 out:
149 *matched = max_matched;
150 if (where < min_where)
151 where = min_where;
152 return where;
153 }
154
155 static void
print_linerange(lin from,lin to)156 print_linerange (lin from, lin to)
157 {
158 char numbuf0[LINENUM_LENGTH_BOUND + 1];
159 char numbuf1[LINENUM_LENGTH_BOUND + 1];
160
161 if (to <= from)
162 printf ("%s",
163 format_linenum (numbuf0, from));
164 else
165 printf ("%s-%s",
166 format_linenum (numbuf0, from),
167 format_linenum (numbuf1, to));
168 }
169
170 static void
merge_result(bool * first_result,int hunk,char const * what,lin from,lin to)171 merge_result (bool *first_result, int hunk, char const *what, lin from, lin to)
172 {
173 static char const *last_what;
174
175 if (*first_result && what)
176 {
177 printf ("Hunk #%d %s at ", hunk, what);
178 last_what = what;
179 }
180 else if (! what)
181 {
182 if (! *first_result)
183 {
184 fputs (".\n", stdout);
185 fflush (stdout);
186 last_what = 0;
187 }
188 return;
189 }
190 else if (last_what == what)
191 fputs (",", stdout);
192 else
193 printf (", %s at ", what);
194 print_linerange (from + out_offset, to + out_offset);
195 *first_result = false;
196 }
197
198 bool
merge_hunk(int hunk,struct outstate * outstate,lin where,bool * somefailed)199 merge_hunk (int hunk, struct outstate *outstate, lin where, bool *somefailed)
200 {
201 bool applies_cleanly;
202 bool first_result = true;
203 bool already_applied;
204 FILE *fp = outstate->ofp;
205 lin old = 1;
206 lin firstold = pch_ptrn_lines ();
207 lin new = firstold + 1;
208 lin firstnew = pch_end ();
209 lin in;
210 lin firstin;
211 char *oldin;
212 lin matched;
213 lin lastwhere;
214
215 /* Convert '!' markers into '-' and '+' to simplify things here. */
216 pch_normalize (UNI_DIFF);
217
218 assert (pch_char (firstnew + 1) == '^');
219 while (pch_char (new) == '=' || pch_char (new) == '\n')
220 new++;
221
222 if (where)
223 {
224 applies_cleanly = true;
225 matched = pch_ptrn_lines ();
226 }
227 else
228 {
229 where = locate_merge (&matched);
230 applies_cleanly = false;
231 }
232
233 in = firstold + 2;
234 oldin = xmalloc (in + matched + 1);
235 memset (oldin, ' ', in + matched);
236 oldin[0] = '*';
237 oldin[in - 1] = '=';
238 oldin[in + matched] = '^';
239 compute_changes (old, in - 1, where, where + matched,
240 oldin + old, oldin + in);
241
242 if (debug & 2)
243 {
244 char numbuf0[LINENUM_LENGTH_BOUND + 1];
245 char numbuf1[LINENUM_LENGTH_BOUND + 1];
246 lin n;
247
248 fputc ('\n', stderr);
249 for (n = 0; n <= in + matched; n++)
250 {
251 fprintf (stderr, "%s %c",
252 format_linenum (numbuf0, n),
253 oldin[n]);
254 if (n == 0)
255 fprintf(stderr, " %s,%s\n",
256 format_linenum (numbuf0, pch_first()),
257 format_linenum (numbuf1, pch_ptrn_lines()));
258 else if (n <= firstold)
259 fprintf (stderr, " |%.*s",
260 (int) pch_line_len (n), pfetch (n));
261 else if (n == in - 1)
262 fprintf(stderr, " %s,%s\n",
263 format_linenum (numbuf0, where),
264 format_linenum (numbuf1, matched));
265 else if (n >= in && n < in + matched)
266 {
267 size_t size;
268 const char *line;
269
270 line = ifetch (where + n - in, false, &size);
271 fprintf (stderr, " |%.*s",
272 (int) size, line);
273 }
274 else
275 fputc('\n', stderr);
276 }
277 fflush (stderr);
278 }
279
280 if (last_frozen_line < where - 1)
281 if (! copy_till (outstate, where - 1))
282 return false;
283
284 for (;;)
285 {
286 firstold = old;
287 firstnew = new;
288 firstin = in;
289
290 if (pch_char (old) == '-' || pch_char (new) == '+')
291 {
292 lin lines;
293
294 while (pch_char (old) == '-')
295 {
296 if (oldin[old] == '-' || oldin[in] == '+')
297 goto conflict;
298 else if (oldin[old] == ' ')
299 {
300 assert (oldin[in] == ' ');
301 in++;
302 }
303 old++;
304 }
305 if (oldin[old] == '-' || oldin[in] == '+')
306 goto conflict;
307 while (pch_char (new) == '+')
308 new++;
309
310 lines = new - firstnew;
311 if (verbosity == VERBOSE
312 || ((verbosity != SILENT) && ! applies_cleanly))
313 merge_result (&first_result, hunk, "merged",
314 where, where + lines - 1);
315 last_frozen_line += (old - firstold);
316 where += (old - firstold);
317 out_offset += new - firstnew;
318
319 if (firstnew < new)
320 {
321 while (firstnew < new)
322 {
323 outstate->after_newline = pch_write_line (firstnew, fp);
324 firstnew++;
325 }
326 outstate->zero_output = false;
327 }
328 }
329 else if (pch_char (old) == ' ')
330 {
331 if (oldin[old] == '-')
332 {
333 while (pch_char (old) == ' ')
334 {
335 if (oldin[old] != '-')
336 break;
337 if (pch_char (new) == '+')
338 goto conflict;
339 else
340 assert (pch_char (new) == ' ');
341 old++;
342 new++;
343 }
344 if (pch_char (old) == '-' || pch_char (new) == '+')
345 goto conflict;
346 }
347 else if (oldin[in] == '+')
348 {
349 while (oldin[in] == '+')
350 in++;
351
352 /* Take these lines from the input file. */
353 where += in - firstin;
354 if (! copy_till (outstate, where - 1))
355 return false;
356 }
357 else if (oldin[old] == ' ')
358 {
359 while (pch_char (old) == ' '
360 && oldin[old] == ' '
361 && pch_char (new) == ' '
362 && oldin[in] == ' ')
363 {
364 old++;
365 new++;
366 in++;
367 }
368
369 /* Take these lines from the input file. */
370 where += (in - firstin);
371 if (! copy_till (outstate, where - 1))
372 return false;
373 }
374 }
375 else
376 {
377 assert (pch_char (old) == '=' && pch_char (new) == '^');
378 /* Nothing more left to merge. */
379 break;
380 }
381 continue;
382
383 conflict:
384 /* Find the end of the conflict. */
385 for (;;)
386 {
387 if (pch_char (old) == '-')
388 {
389 while (oldin[in] == '+')
390 in++;
391 if (oldin[old] == ' ')
392 {
393 assert (oldin[in] == ' ');
394 in++;
395 }
396 old++;
397 }
398 else if (oldin[old] == '-')
399 {
400 while (pch_char (new) == '+')
401 new++;
402 if (pch_char (old) == ' ')
403 {
404 assert (pch_char (new) == ' ');
405 new++;
406 }
407 old++;
408 }
409 else if (pch_char (new) == '+')
410 while (pch_char (new) == '+')
411 new++;
412 else if (oldin[in] == '+')
413 while (oldin[in] == '+')
414 in++;
415 else
416 break;
417 }
418 assert (((pch_char (old) == ' ' && pch_char (new) == ' ')
419 || (pch_char (old) == '=' && pch_char (new) == '^'))
420 && ((oldin[old] == ' ' && oldin[in] == ' ')
421 || (oldin[old] == '=' && oldin[in] == '^')));
422
423 /* Output common prefix lines. */
424 for (lastwhere = where;
425 firstin < in && firstnew < new
426 && context_matches_file (firstnew, lastwhere);
427 firstin++, firstnew++, lastwhere++)
428 /* do nothing */ ;
429 already_applied = (firstin == in && firstnew == new);
430 if (already_applied)
431 merge_result (&first_result, hunk, "already applied",
432 where, lastwhere - 1);
433 if (conflict_style == MERGE_DIFF3)
434 {
435 lin common_prefix = lastwhere - where;
436
437 /* Forget about common prefix lines. */
438 firstin -= common_prefix;
439 firstnew -= common_prefix;
440 lastwhere -= common_prefix;
441 }
442 if (where != lastwhere)
443 {
444 where = lastwhere;
445 if (! copy_till (outstate, where - 1))
446 return false;
447 }
448
449 if (! already_applied)
450 {
451 lin common_suffix = 0;
452 lin lines;
453
454 if (conflict_style == MERGE_MERGE)
455 {
456 /* Remember common suffix lines. */
457 for (lastwhere = where + (in - firstin);
458 firstin < in && firstnew < new
459 && context_matches_file (new - 1, lastwhere - 1);
460 in--, new--, lastwhere--, common_suffix++)
461 /* do nothing */ ;
462 }
463
464 lines = 3 + (in - firstin) + (new - firstnew);
465 if (conflict_style == MERGE_DIFF3)
466 lines += 1 + (old - firstold);
467 merge_result (&first_result, hunk, "NOT MERGED",
468 where, where + lines - 1);
469 out_offset += lines - (in - firstin);
470
471 fputs (outstate->after_newline + "\n<<<<<<<\n", fp);
472 outstate->after_newline = true;
473 if (firstin < in)
474 {
475 where += (in - firstin);
476 if (! copy_till (outstate, where - 1))
477 return false;
478 }
479
480 if (conflict_style == MERGE_DIFF3)
481 {
482 fputs (outstate->after_newline + "\n|||||||\n", fp);
483 outstate->after_newline = true;
484 while (firstold < old)
485 {
486 outstate->after_newline = pch_write_line (firstold, fp);
487 firstold++;
488 }
489 }
490
491 fputs (outstate->after_newline + "\n=======\n", fp);
492 outstate->after_newline = true;
493 while (firstnew < new)
494 {
495 outstate->after_newline = pch_write_line (firstnew, fp);
496 firstnew++;
497 }
498 fputs (outstate->after_newline + "\n>>>>>>>\n", fp);
499 outstate->after_newline = true;
500 outstate->zero_output = false;
501 if (ferror (fp))
502 write_fatal ();
503
504 /* Output common suffix lines. */
505 if (common_suffix)
506 {
507 where += common_suffix;
508 if (! copy_till (outstate, where - 1))
509 return false;
510 in += common_suffix;
511 new += common_suffix;
512 }
513 *somefailed = true;
514 }
515 }
516 merge_result (&first_result, 0, 0, 0, 0);
517
518 assert (last_frozen_line == where - 1);
519 free (oldin);
520 return true;
521 }
522
523 static lin
count_context_lines(void)524 count_context_lines (void)
525 {
526 lin old;
527 lin lastold = pch_ptrn_lines ();
528 lin context;
529
530 for (context = 0, old = 1; old <= lastold; old++)
531 if (pch_char (old) == ' ')
532 context++;
533 return context;
534 }
535
536 static bool
context_matches_file(lin old,lin where)537 context_matches_file (lin old, lin where)
538 {
539 size_t size;
540 const char *line;
541
542 line = ifetch (where, false, &size);
543 return size &&
544 (canonicalize_ws ?
545 similar (pfetch (old), pch_line_len (old), line, size) :
546 (size == pch_line_len (old) &&
547 memcmp (line, pfetch (old), size) == 0));
548 }
549
550 static void
compute_changes(lin xmin,lin xmax,lin ymin,lin ymax,char * xchar,char * ychar)551 compute_changes (lin xmin, lin xmax, lin ymin, lin ymax,
552 char *xchar, char *ychar)
553 {
554 struct context ctxt;
555 lin diags;
556
557 ctxt.xchar = xchar - xmin;
558 ctxt.ychar = ychar - ymin;
559
560 diags = xmax + ymax + 3;
561 ctxt.fdiag = xmalloc (2 * diags * sizeof (*ctxt.fdiag));
562 ctxt.bdiag = ctxt.fdiag + diags;
563 ctxt.fdiag += ymax + 1;
564 ctxt.bdiag += ymax + 1;
565
566 ctxt.heuristic = true;
567
568 compareseq (xmin, xmax, ymin, ymax, false, &ctxt);
569
570 ctxt.fdiag -= ymax + 1;
571 free (ctxt.fdiag);
572 }
573