git-apply: when validating default names, check the final EOLN too
[git.git] / apply.c
1 /*
2  * apply.c
3  *
4  * Copyright (C) Linus Torvalds, 2005
5  *
6  * This applies patches on top of some (arbitrary) version of the SCM.
7  *
8  * NOTE! It does all its work in the index file, and only cares about
9  * the files in the working directory if you tell it to "merge" the
10  * patch apply.
11  *
12  * Even when merging it always takes the source from the index, and
13  * uses the working tree as a "branch" for a 3-way merge.
14  */
15 #include <ctype.h>
16
17 #include "cache.h"
18
19 // We default to the merge behaviour, since that's what most people would
20 // expect
21 static int merge_patch = 1;
22 static int diffstat = 0;
23 static int check = 1;
24 static const char apply_usage[] = "git-apply <patch>";
25
26 /*
27  * For "diff-stat" like behaviour, we keep track of the biggest change
28  * we've seen, and the longest filename. That allows us to do simple
29  * scaling.
30  */
31 static int max_change, max_len;
32
33 /*
34  * Various "current state", notably line numbers and what
35  * file (and how) we're patching right now.. The "is_xxxx"
36  * things are flags, where -1 means "don't know yet".
37  */
38 static int linenr = 1;
39
40 struct fragment {
41         unsigned long oldpos, oldlines;
42         unsigned long newpos, newlines;
43         const char *patch;
44         int size;
45         struct fragment *next;
46 };
47
48 struct patch {
49         char *new_name, *old_name, *def_name;
50         unsigned int old_mode, new_mode;
51         int is_rename, is_copy, is_new, is_delete;
52         int lines_added, lines_deleted;
53         struct fragment *fragments;
54         struct patch *next;
55 };
56
57 #define CHUNKSIZE (8192)
58 #define SLOP (16)
59
60 static void *read_patch_file(int fd, unsigned long *sizep)
61 {
62         unsigned long size = 0, alloc = CHUNKSIZE;
63         void *buffer = xmalloc(alloc);
64
65         for (;;) {
66                 int nr = alloc - size;
67                 if (nr < 1024) {
68                         alloc += CHUNKSIZE;
69                         buffer = xrealloc(buffer, alloc);
70                         nr = alloc - size;
71                 }
72                 nr = read(fd, buffer + size, nr);
73                 if (!nr)
74                         break;
75                 if (nr < 0) {
76                         if (errno == EAGAIN)
77                                 continue;
78                         die("git-apply: read returned %s", strerror(errno));
79                 }
80                 size += nr;
81         }
82         *sizep = size;
83
84         /*
85          * Make sure that we have some slop in the buffer
86          * so that we can do speculative "memcmp" etc, and
87          * see to it that it is NUL-filled.
88          */
89         if (alloc < size + SLOP)
90                 buffer = xrealloc(buffer, size + SLOP);
91         memset(buffer + size, 0, SLOP);
92         return buffer;
93 }
94
95 static unsigned long linelen(char *buffer, unsigned long size)
96 {
97         unsigned long len = 0;
98         while (size--) {
99                 len++;
100                 if (*buffer++ == '\n')
101                         break;
102         }
103         return len;
104 }
105
106 static int is_dev_null(const char *str)
107 {
108         return !memcmp("/dev/null", str, 9) && isspace(str[9]);
109 }
110
111 #define TERM_EXIST      1
112 #define TERM_SPACE      2
113 #define TERM_TAB        4
114
115 static int name_terminate(const char *name, int namelen, int c, int terminate)
116 {
117         if (c == ' ' && !(terminate & TERM_SPACE))
118                 return 0;
119         if (c == '\t' && !(terminate & TERM_TAB))
120                 return 0;
121
122         /*
123          * Do we want an existing name? Return false and
124          * continue if it's not there.
125          */
126         if (terminate & TERM_EXIST)
127                 return cache_name_pos(name, namelen) >= 0;
128
129         return 1;
130 }
131
132 static char * find_name(const char *line, char *def, int p_value, int terminate)
133 {
134         int len;
135         const char *start = line;
136         char *name;
137
138         for (;;) {
139                 char c = *line;
140
141                 if (isspace(c)) {
142                         if (c == '\n')
143                                 break;
144                         if (name_terminate(start, line-start, c, terminate))
145                                 break;
146                 }
147                 line++;
148                 if (c == '/' && !--p_value)
149                         start = line;
150         }
151         if (!start)
152                 return def;
153         len = line - start;
154         if (!len)
155                 return def;
156
157         /*
158          * Generally we prefer the shorter name, especially
159          * if the other one is just a variation of that with
160          * something else tacked on to the end (ie "file.orig"
161          * or "file~").
162          */
163         if (def) {
164                 int deflen = strlen(def);
165                 if (deflen < len && !strncmp(start, def, deflen))
166                         return def;
167         }
168
169         name = xmalloc(len + 1);
170         memcpy(name, start, len);
171         name[len] = 0;
172         free(def);
173         return name;
174 }
175
176 /*
177  * Get the name etc info from the --/+++ lines of a traditional patch header
178  *
179  * NOTE! This hardcodes "-p1" behaviour in filename detection.
180  *
181  * FIXME! The end-of-filename heuristics are kind of screwy. For existing
182  * files, we can happily check the index for a match, but for creating a
183  * new file we should try to match whatever "patch" does. I have no idea.
184  */
185 static void parse_traditional_patch(const char *first, const char *second, struct patch *patch)
186 {
187         int p_value = 1;
188         char *name;
189
190         first += 4;     // skip "--- "
191         second += 4;    // skip "+++ "
192         if (is_dev_null(first)) {
193                 patch->is_new = 1;
194                 patch->is_delete = 0;
195                 name = find_name(second, NULL, p_value, TERM_SPACE | TERM_TAB);
196                 patch->new_name = name;
197         } else if (is_dev_null(second)) {
198                 patch->is_new = 0;
199                 patch->is_delete = 1;
200                 name = find_name(first, NULL, p_value, TERM_EXIST | TERM_SPACE | TERM_TAB);
201                 patch->old_name = name;
202         } else {
203                 name = find_name(first, NULL, p_value, TERM_EXIST | TERM_SPACE | TERM_TAB);
204                 name = find_name(second, name, p_value, TERM_EXIST | TERM_SPACE | TERM_TAB);
205                 patch->old_name = patch->new_name = name;
206         }
207         if (!name)
208                 die("unable to find filename in patch at line %d", linenr);
209 }
210
211 static int gitdiff_hdrend(const char *line, struct patch *patch)
212 {
213         return -1;
214 }
215
216 /*
217  * We're anal about diff header consistency, to make
218  * sure that we don't end up having strange ambiguous
219  * patches floating around.
220  *
221  * As a result, gitdiff_{old|new}name() will check
222  * their names against any previous information, just
223  * to make sure..
224  */
225 static char *gitdiff_verify_name(const char *line, int isnull, char *orig_name, const char *oldnew)
226 {
227         int len;
228         const char *name;
229
230         if (!orig_name && !isnull)
231                 return find_name(line, NULL, 1, 0);
232
233         name = "/dev/null";
234         len = 9;
235         if (orig_name) {
236                 name = orig_name;
237                 len = strlen(name);
238                 if (isnull)
239                         die("git-apply: bad git-diff - expected /dev/null, got %s on line %d", name, linenr);
240         }
241
242         if (*name == '/')
243                 goto absolute_path;
244
245         for (;;) {
246                 char c = *line++;
247                 if (c == '\n')
248                         break;
249                 if (c != '/')
250                         continue;
251 absolute_path:
252                 if (memcmp(line, name, len) || line[len] != '\n')
253                         break;
254                 return orig_name;
255         }
256         die("git-apply: bad git-diff - inconsistent %s filename on line %d", oldnew, linenr);
257         return NULL;
258 }
259
260 static int gitdiff_oldname(const char *line, struct patch *patch)
261 {
262         patch->old_name = gitdiff_verify_name(line, patch->is_new, patch->old_name, "old");
263         return 0;
264 }
265
266 static int gitdiff_newname(const char *line, struct patch *patch)
267 {
268         patch->new_name = gitdiff_verify_name(line, patch->is_delete, patch->new_name, "new");
269         return 0;
270 }
271
272 static int gitdiff_oldmode(const char *line, struct patch *patch)
273 {
274         patch->old_mode = strtoul(line, NULL, 8);
275         return 0;
276 }
277
278 static int gitdiff_newmode(const char *line, struct patch *patch)
279 {
280         patch->new_mode = strtoul(line, NULL, 8);
281         return 0;
282 }
283
284 static int gitdiff_delete(const char *line, struct patch *patch)
285 {
286         patch->is_delete = 1;
287         patch->old_name = patch->def_name;
288         return gitdiff_oldmode(line, patch);
289 }
290
291 static int gitdiff_newfile(const char *line, struct patch *patch)
292 {
293         patch->is_new = 1;
294         patch->new_name = patch->def_name;
295         return gitdiff_newmode(line, patch);
296 }
297
298 static int gitdiff_copysrc(const char *line, struct patch *patch)
299 {
300         patch->is_copy = 1;
301         patch->old_name = find_name(line, NULL, 0, 0);
302         return 0;
303 }
304
305 static int gitdiff_copydst(const char *line, struct patch *patch)
306 {
307         patch->is_copy = 1;
308         patch->new_name = find_name(line, NULL, 0, 0);
309         return 0;
310 }
311
312 static int gitdiff_renamesrc(const char *line, struct patch *patch)
313 {
314         patch->is_rename = 1;
315         patch->old_name = find_name(line, NULL, 0, 0);
316         return 0;
317 }
318
319 static int gitdiff_renamedst(const char *line, struct patch *patch)
320 {
321         patch->is_rename = 1;
322         patch->new_name = find_name(line, NULL, 0, 0);
323         return 0;
324 }
325
326 static int gitdiff_similarity(const char *line, struct patch *patch)
327 {
328         return 0;
329 }
330
331 /*
332  * This is normal for a diff that doesn't change anything: we'll fall through
333  * into the next diff. Tell the parser to break out.
334  */
335 static int gitdiff_unrecognized(const char *line, struct patch *patch)
336 {
337         return -1;
338 }
339
340 static char *git_header_name(char *line)
341 {
342         int len;
343         char *name, *second;
344
345         /*
346          * Find the first '/'
347          */
348         name = line;
349         for (;;) {
350                 char c = *name++;
351                 if (c == '\n')
352                         return NULL;
353                 if (c == '/')
354                         break;
355         }
356
357         /*
358          * We don't accept absolute paths (/dev/null) as possibly valid
359          */
360         if (name == line+1)
361                 return NULL;
362
363         /*
364          * Accept a name only if it shows up twice, exactly the same
365          * form.
366          */
367         for (len = 0 ; ; len++) {
368                 char c = name[len];
369
370                 switch (c) {
371                 default:
372                         continue;
373                 case '\n':
374                         break;
375                 case '\t': case ' ':
376                         second = name+len;
377                         for (;;) {
378                                 char c = *second++;
379                                 if (c == '\n')
380                                         return NULL;
381                                 if (c == '/')
382                                         break;
383                         }
384                         if (second[len] == '\n' && !memcmp(name, second, len)) {
385                                 char *ret = xmalloc(len + 1);
386                                 memcpy(ret, name, len);
387                                 ret[len] = 0;
388                                 return ret;
389                         }
390                 }
391         }
392         return NULL;
393 }
394
395 /* Verify that we recognize the lines following a git header */
396 static int parse_git_header(char *line, int len, unsigned int size, struct patch *patch)
397 {
398         unsigned long offset;
399
400         /* A git diff has explicit new/delete information, so we don't guess */
401         patch->is_new = 0;
402         patch->is_delete = 0;
403
404         /*
405          * Some things may not have the old name in the
406          * rest of the headers anywhere (pure mode changes,
407          * or removing or adding empty files), so we get
408          * the default name from the header.
409          */
410         patch->def_name = git_header_name(line + strlen("diff --git "));
411
412         line += len;
413         size -= len;
414         linenr++;
415         for (offset = len ; size > 0 ; offset += len, size -= len, line += len, linenr++) {
416                 static const struct opentry {
417                         const char *str;
418                         int (*fn)(const char *, struct patch *);
419                 } optable[] = {
420                         { "@@ -", gitdiff_hdrend },
421                         { "--- ", gitdiff_oldname },
422                         { "+++ ", gitdiff_newname },
423                         { "old mode ", gitdiff_oldmode },
424                         { "new mode ", gitdiff_newmode },
425                         { "deleted file mode ", gitdiff_delete },
426                         { "new file mode ", gitdiff_newfile },
427                         { "copy from ", gitdiff_copysrc },
428                         { "copy to ", gitdiff_copydst },
429                         { "rename from ", gitdiff_renamesrc },
430                         { "rename to ", gitdiff_renamedst },
431                         { "similarity index ", gitdiff_similarity },
432                         { "", gitdiff_unrecognized },
433                 };
434                 int i;
435
436                 len = linelen(line, size);
437                 if (!len || line[len-1] != '\n')
438                         break;
439                 for (i = 0; i < sizeof(optable) / sizeof(optable[0]); i++) {
440                         const struct opentry *p = optable + i;
441                         int oplen = strlen(p->str);
442                         if (len < oplen || memcmp(p->str, line, oplen))
443                                 continue;
444                         if (p->fn(line + oplen, patch) < 0)
445                                 return offset;
446                         break;
447                 }
448         }
449
450         return offset;
451 }
452
453 static int parse_num(const char *line, unsigned long *p)
454 {
455         char *ptr;
456
457         if (!isdigit(*line))
458                 return 0;
459         *p = strtoul(line, &ptr, 10);
460         return ptr - line;
461 }
462
463 static int parse_range(const char *line, int len, int offset, const char *expect,
464                         unsigned long *p1, unsigned long *p2)
465 {
466         int digits, ex;
467
468         if (offset < 0 || offset >= len)
469                 return -1;
470         line += offset;
471         len -= offset;
472
473         digits = parse_num(line, p1);
474         if (!digits)
475                 return -1;
476
477         offset += digits;
478         line += digits;
479         len -= digits;
480
481         *p2 = *p1;
482         if (*line == ',') {
483                 digits = parse_num(line+1, p2);
484                 if (!digits)
485                         return -1;
486
487                 offset += digits+1;
488                 line += digits+1;
489                 len -= digits+1;
490         }
491
492         ex = strlen(expect);
493         if (ex > len)
494                 return -1;
495         if (memcmp(line, expect, ex))
496                 return -1;
497
498         return offset + ex;
499 }
500
501 /*
502  * Parse a unified diff fragment header of the
503  * form "@@ -a,b +c,d @@"
504  */
505 static int parse_fragment_header(char *line, int len, struct fragment *fragment)
506 {
507         int offset;
508
509         if (!len || line[len-1] != '\n')
510                 return -1;
511
512         /* Figure out the number of lines in a fragment */
513         offset = parse_range(line, len, 4, " +", &fragment->oldpos, &fragment->oldlines);
514         offset = parse_range(line, len, offset, " @@", &fragment->newpos, &fragment->newlines);
515
516         return offset;
517 }
518
519 static int find_header(char *line, unsigned long size, int *hdrsize, struct patch *patch)
520 {
521         unsigned long offset, len;
522
523         patch->is_rename = patch->is_copy = 0;
524         patch->is_new = patch->is_delete = -1;
525         patch->old_mode = patch->new_mode = 0;
526         patch->old_name = patch->new_name = NULL;
527         for (offset = 0; size > 0; offset += len, size -= len, line += len, linenr++) {
528                 unsigned long nextlen;
529
530                 len = linelen(line, size);
531                 if (!len)
532                         break;
533
534                 /* Testing this early allows us to take a few shortcuts.. */
535                 if (len < 6)
536                         continue;
537
538                 /*
539                  * Make sure we don't find any unconnected patch fragmants.
540                  * That's a sign that we didn't find a header, and that a
541                  * patch has become corrupted/broken up.
542                  */
543                 if (!memcmp("@@ -", line, 4)) {
544                         struct fragment dummy;
545                         if (parse_fragment_header(line, len, &dummy) < 0)
546                                 continue;
547                         error("patch fragment without header at line %d: %.*s", linenr, len-1, line);
548                 }
549
550                 if (size < len + 6)
551                         break;
552
553                 /*
554                  * Git patch? It might not have a real patch, just a rename
555                  * or mode change, so we handle that specially
556                  */
557                 if (!memcmp("diff --git ", line, 11)) {
558                         int git_hdr_len = parse_git_header(line, len, size, patch);
559                         if (git_hdr_len < 0)
560                                 continue;
561                         if (!patch->old_name && !patch->new_name)
562                                 die("git diff header lacks filename information");
563                         *hdrsize = git_hdr_len;
564                         return offset;
565                 }
566
567                 /** --- followed by +++ ? */
568                 if (memcmp("--- ", line,  4) || memcmp("+++ ", line + len, 4))
569                         continue;
570
571                 /*
572                  * We only accept unified patches, so we want it to
573                  * at least have "@@ -a,b +c,d @@\n", which is 14 chars
574                  * minimum
575                  */
576                 nextlen = linelen(line + len, size - len);
577                 if (size < nextlen + 14 || memcmp("@@ -", line + len + nextlen, 4))
578                         continue;
579
580                 /* Ok, we'll consider it a patch */
581                 parse_traditional_patch(line, line+len, patch);
582                 *hdrsize = len + nextlen;
583                 linenr += 2;
584                 return offset;
585         }
586         return -1;
587 }
588
589 /*
590  * Parse a unified diff. Note that this really needs
591  * to parse each fragment separately, since the only
592  * way to know the difference between a "---" that is
593  * part of a patch, and a "---" that starts the next
594  * patch is to look at the line counts..
595  */
596 static int parse_fragment(char *line, unsigned long size, struct patch *patch, struct fragment *fragment)
597 {
598         int added, deleted;
599         int len = linelen(line, size), offset;
600         unsigned long pos[4], oldlines, newlines;
601
602         offset = parse_fragment_header(line, len, fragment);
603         if (offset < 0)
604                 return -1;
605         oldlines = fragment->oldlines;
606         newlines = fragment->newlines;
607
608         if (patch->is_new < 0 && (pos[0] || oldlines))
609                 patch->is_new = 0;
610         if (patch->is_delete < 0 && (pos[1] || newlines))
611                 patch->is_delete = 0;
612
613         /* Parse the thing.. */
614         line += len;
615         size -= len;
616         linenr++;
617         added = deleted = 0;
618         for (offset = len; size > 0; offset += len, size -= len, line += len, linenr++) {
619                 if (!oldlines && !newlines)
620                         break;
621                 len = linelen(line, size);
622                 if (!len || line[len-1] != '\n')
623                         return -1;
624                 switch (*line) {
625                 default:
626                         return -1;
627                 case ' ':
628                         oldlines--;
629                         newlines--;
630                         break;
631                 case '-':
632                         deleted++;
633                         oldlines--;
634                         break;
635                 case '+':
636                         added++;
637                         newlines--;
638                         break;
639                 /* We allow "\ No newline at end of file" */
640                 case '\\':
641                         break;
642                 }
643         }
644         patch->lines_added += added;
645         patch->lines_deleted += deleted;
646         return offset;
647 }
648
649 static int parse_single_patch(char *line, unsigned long size, struct patch *patch)
650 {
651         unsigned long offset = 0;
652         struct fragment **fragp = &patch->fragments;
653
654         while (size > 4 && !memcmp(line, "@@ -", 4)) {
655                 struct fragment *fragment;
656                 int len;
657
658                 fragment = xmalloc(sizeof(*fragment));
659                 memset(fragment, 0, sizeof(*fragment));
660                 len = parse_fragment(line, size, patch, fragment);
661                 if (len <= 0)
662                         die("corrupt patch at line %d", linenr);
663
664                 fragment->patch = line;
665                 fragment->size = len;
666
667                 *fragp = fragment;
668                 fragp = &fragment->next;
669
670                 offset += len;
671                 line += len;
672                 size -= len;
673         }
674         return offset;
675 }
676
677 static int parse_chunk(char *buffer, unsigned long size, struct patch *patch)
678 {
679         int hdrsize, patchsize;
680         int offset = find_header(buffer, size, &hdrsize, patch);
681
682         if (offset < 0)
683                 return offset;
684
685         patchsize = parse_single_patch(buffer + offset + hdrsize, size - offset - hdrsize, patch);
686
687         return offset + hdrsize + patchsize;
688 }
689
690 const char pluses[] = "++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++";
691 const char minuses[]= "----------------------------------------------------------------------";
692
693 static void show_stats(struct patch *patch)
694 {
695         char *name = patch->old_name;
696         int len, max, add, del;
697
698         if (!name)
699                 name = patch->new_name;
700
701         /*
702          * "scale" the filename
703          */
704         len = strlen(name);
705         max = max_len;
706         if (max > 50)
707                 max = 50;
708         if (len > max)
709                 name += len - max;
710         len = max;
711
712         /*
713          * scale the add/delete
714          */
715         max = max_change;
716         if (max + len > 70)
717                 max = 70 - len;
718         
719         add = (patch->lines_added * max + max_change/2) / max_change;
720         del = (patch->lines_deleted * max + max_change/2) / max_change;
721         printf(" %-*s |%5d %.*s%.*s\n",
722                 len, name, patch->lines_added + patch->lines_deleted,
723                 add, pluses, del, minuses);
724 }
725
726 static void check_patch(struct patch *patch)
727 {
728         const char *old_name = patch->old_name;
729         const char *new_name = patch->new_name;
730
731         if (old_name) {
732                 if (cache_name_pos(old_name, strlen(old_name)) < 0)
733                         die("file %s does not exist", old_name);
734                 if (patch->is_new < 0)
735                         patch->is_new = 0;
736         }
737         if (new_name && (patch->is_new | patch->is_rename | patch->is_copy)) {
738                 if (cache_name_pos(new_name, strlen(new_name)) >= 0)
739                         die("file %s already exists", new_name);
740         }
741 }
742
743 static void apply_patch_list(struct patch *patch)
744 {
745         int files, adds, dels;
746
747         files = adds = dels = 0;
748         if (!patch)
749                 die("no patch found");
750         do {
751                 if (check)
752                         check_patch(patch);
753
754                 if (diffstat) {
755                         files++;
756                         adds += patch->lines_added;
757                         dels += patch->lines_deleted;
758                         show_stats(patch);
759                 }
760         } while ((patch = patch->next) != NULL);
761
762         if (diffstat)
763                 printf(" %d files changed, %d insertions(+), %d deletions(-)\n", files, adds, dels);
764 }
765
766 static void patch_stats(struct patch *patch)
767 {
768         int lines = patch->lines_added + patch->lines_deleted;
769
770         if (lines > max_change)
771                 max_change = lines;
772         if (patch->old_name) {
773                 int len = strlen(patch->old_name);
774                 if (len > max_len)
775                         max_len = len;
776         }
777         if (patch->new_name) {
778                 int len = strlen(patch->new_name);
779                 if (len > max_len)
780                         max_len = len;
781         }
782 }
783
784 static int apply_patch(int fd)
785 {
786         unsigned long offset, size;
787         char *buffer = read_patch_file(fd, &size);
788         struct patch *list = NULL, **listp = &list;
789
790         if (!buffer)
791                 return -1;
792         offset = 0;
793         while (size > 0) {
794                 struct patch *patch;
795                 int nr;
796
797                 patch = xmalloc(sizeof(*patch));
798                 memset(patch, 0, sizeof(*patch));
799                 nr = parse_chunk(buffer + offset, size, patch);
800                 if (nr < 0)
801                         break;
802                 patch_stats(patch);
803                 *listp = patch;
804                 listp = &patch->next;
805                 offset += nr;
806                 size -= nr;
807         }
808
809         apply_patch_list(list);
810
811         free(buffer);
812         return 0;
813 }
814
815 int main(int argc, char **argv)
816 {
817         int i;
818         int read_stdin = 1;
819
820         if (read_cache() < 0)
821                 die("unable to read index file");
822
823         for (i = 1; i < argc; i++) {
824                 const char *arg = argv[i];
825                 int fd;
826
827                 if (!strcmp(arg, "-")) {
828                         apply_patch(0);
829                         read_stdin = 0;
830                         continue;
831                 }
832                 if (!strcmp(arg, "--no-merge")) {
833                         merge_patch = 0;
834                         continue;
835                 }
836                 if (!strcmp(arg, "--stat")) {
837                         check = 0;
838                         diffstat = 1;
839                         continue;
840                 }
841                 fd = open(arg, O_RDONLY);
842                 if (fd < 0)
843                         usage(apply_usage);
844                 read_stdin = 0;
845                 apply_patch(fd);
846                 close(fd);
847         }
848         if (read_stdin)
849                 apply_patch(0);
850         return 0;
851 }