8095026d33ba3583f428a0008c6c20a30c8e6769
   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 */
   9#include "cache.h"
  10#include "lockfile.h"
  11#include "cache-tree.h"
  12#include "quote.h"
  13#include "blob.h"
  14#include "delta.h"
  15#include "builtin.h"
  16#include "string-list.h"
  17#include "dir.h"
  18#include "diff.h"
  19#include "parse-options.h"
  20#include "xdiff-interface.h"
  21#include "ll-merge.h"
  22#include "rerere.h"
  23
  24enum ws_error_action {
  25        nowarn_ws_error,
  26        warn_on_ws_error,
  27        die_on_ws_error,
  28        correct_ws_error
  29};
  30
  31
  32enum ws_ignore {
  33        ignore_ws_none,
  34        ignore_ws_change
  35};
  36
  37/*
  38 * We need to keep track of how symlinks in the preimage are
  39 * manipulated by the patches.  A patch to add a/b/c where a/b
  40 * is a symlink should not be allowed to affect the directory
  41 * the symlink points at, but if the same patch removes a/b,
  42 * it is perfectly fine, as the patch removes a/b to make room
  43 * to create a directory a/b so that a/b/c can be created.
  44 *
  45 * See also "struct string_list symlink_changes" in "struct
  46 * apply_state".
  47 */
  48#define SYMLINK_GOES_AWAY 01
  49#define SYMLINK_IN_RESULT 02
  50
  51struct apply_state {
  52        const char *prefix;
  53        int prefix_length;
  54
  55        /* These control what gets looked at and modified */
  56        int apply; /* this is not a dry-run */
  57        int cached; /* apply to the index only */
  58        int check; /* preimage must match working tree, don't actually apply */
  59        int check_index; /* preimage must match the indexed version */
  60        int update_index; /* check_index && apply */
  61
  62        /* These control cosmetic aspect of the output */
  63        int diffstat; /* just show a diffstat, and don't actually apply */
  64        int numstat; /* just show a numeric diffstat, and don't actually apply */
  65        int summary; /* just report creation, deletion, etc, and don't actually apply */
  66
  67        /* These boolean parameters control how the apply is done */
  68        int allow_overlap;
  69        int apply_in_reverse;
  70        int apply_with_reject;
  71        int apply_verbosely;
  72        int no_add;
  73        int threeway;
  74        int unidiff_zero;
  75        int unsafe_paths;
  76
  77        /* Other non boolean parameters */
  78        const char *fake_ancestor;
  79        const char *patch_input_file;
  80        int line_termination;
  81        struct strbuf root;
  82        int p_value;
  83        int p_value_known;
  84        unsigned int p_context;
  85
  86        /* Exclude and include path parameters */
  87        struct string_list limit_by_name;
  88        int has_include;
  89
  90        /* Various "current state" */
  91        int linenr; /* current line number */
  92        struct string_list symlink_changes; /* we have to track symlinks */
  93
  94        /*
  95         * For "diff-stat" like behaviour, we keep track of the biggest change
  96         * we've seen, and the longest filename. That allows us to do simple
  97         * scaling.
  98         */
  99        int max_change;
 100        int max_len;
 101
 102        /*
 103         * Records filenames that have been touched, in order to handle
 104         * the case where more than one patches touch the same file.
 105         */
 106        struct string_list fn_table;
 107
 108        /* These control whitespace errors */
 109        enum ws_error_action ws_error_action;
 110        enum ws_ignore ws_ignore_action;
 111        const char *whitespace_option;
 112        int whitespace_error;
 113        int squelch_whitespace_errors;
 114        int applied_after_fixing_ws;
 115};
 116
 117static int newfd = -1;
 118
 119static const char * const apply_usage[] = {
 120        N_("git apply [<options>] [<patch>...]"),
 121        NULL
 122};
 123
 124static void parse_whitespace_option(struct apply_state *state, const char *option)
 125{
 126        if (!option) {
 127                state->ws_error_action = warn_on_ws_error;
 128                return;
 129        }
 130        if (!strcmp(option, "warn")) {
 131                state->ws_error_action = warn_on_ws_error;
 132                return;
 133        }
 134        if (!strcmp(option, "nowarn")) {
 135                state->ws_error_action = nowarn_ws_error;
 136                return;
 137        }
 138        if (!strcmp(option, "error")) {
 139                state->ws_error_action = die_on_ws_error;
 140                return;
 141        }
 142        if (!strcmp(option, "error-all")) {
 143                state->ws_error_action = die_on_ws_error;
 144                state->squelch_whitespace_errors = 0;
 145                return;
 146        }
 147        if (!strcmp(option, "strip") || !strcmp(option, "fix")) {
 148                state->ws_error_action = correct_ws_error;
 149                return;
 150        }
 151        die(_("unrecognized whitespace option '%s'"), option);
 152}
 153
 154static void parse_ignorewhitespace_option(struct apply_state *state,
 155                                          const char *option)
 156{
 157        if (!option || !strcmp(option, "no") ||
 158            !strcmp(option, "false") || !strcmp(option, "never") ||
 159            !strcmp(option, "none")) {
 160                state->ws_ignore_action = ignore_ws_none;
 161                return;
 162        }
 163        if (!strcmp(option, "change")) {
 164                state->ws_ignore_action = ignore_ws_change;
 165                return;
 166        }
 167        die(_("unrecognized whitespace ignore option '%s'"), option);
 168}
 169
 170static void set_default_whitespace_mode(struct apply_state *state)
 171{
 172        if (!state->whitespace_option && !apply_default_whitespace)
 173                state->ws_error_action = (state->apply ? warn_on_ws_error : nowarn_ws_error);
 174}
 175
 176/*
 177 * This represents one "hunk" from a patch, starting with
 178 * "@@ -oldpos,oldlines +newpos,newlines @@" marker.  The
 179 * patch text is pointed at by patch, and its byte length
 180 * is stored in size.  leading and trailing are the number
 181 * of context lines.
 182 */
 183struct fragment {
 184        unsigned long leading, trailing;
 185        unsigned long oldpos, oldlines;
 186        unsigned long newpos, newlines;
 187        /*
 188         * 'patch' is usually borrowed from buf in apply_patch(),
 189         * but some codepaths store an allocated buffer.
 190         */
 191        const char *patch;
 192        unsigned free_patch:1,
 193                rejected:1;
 194        int size;
 195        int linenr;
 196        struct fragment *next;
 197};
 198
 199/*
 200 * When dealing with a binary patch, we reuse "leading" field
 201 * to store the type of the binary hunk, either deflated "delta"
 202 * or deflated "literal".
 203 */
 204#define binary_patch_method leading
 205#define BINARY_DELTA_DEFLATED   1
 206#define BINARY_LITERAL_DEFLATED 2
 207
 208/*
 209 * This represents a "patch" to a file, both metainfo changes
 210 * such as creation/deletion, filemode and content changes represented
 211 * as a series of fragments.
 212 */
 213struct patch {
 214        char *new_name, *old_name, *def_name;
 215        unsigned int old_mode, new_mode;
 216        int is_new, is_delete;  /* -1 = unknown, 0 = false, 1 = true */
 217        int rejected;
 218        unsigned ws_rule;
 219        int lines_added, lines_deleted;
 220        int score;
 221        unsigned int is_toplevel_relative:1;
 222        unsigned int inaccurate_eof:1;
 223        unsigned int is_binary:1;
 224        unsigned int is_copy:1;
 225        unsigned int is_rename:1;
 226        unsigned int recount:1;
 227        unsigned int conflicted_threeway:1;
 228        unsigned int direct_to_threeway:1;
 229        struct fragment *fragments;
 230        char *result;
 231        size_t resultsize;
 232        char old_sha1_prefix[41];
 233        char new_sha1_prefix[41];
 234        struct patch *next;
 235
 236        /* three-way fallback result */
 237        struct object_id threeway_stage[3];
 238};
 239
 240static void free_fragment_list(struct fragment *list)
 241{
 242        while (list) {
 243                struct fragment *next = list->next;
 244                if (list->free_patch)
 245                        free((char *)list->patch);
 246                free(list);
 247                list = next;
 248        }
 249}
 250
 251static void free_patch(struct patch *patch)
 252{
 253        free_fragment_list(patch->fragments);
 254        free(patch->def_name);
 255        free(patch->old_name);
 256        free(patch->new_name);
 257        free(patch->result);
 258        free(patch);
 259}
 260
 261static void free_patch_list(struct patch *list)
 262{
 263        while (list) {
 264                struct patch *next = list->next;
 265                free_patch(list);
 266                list = next;
 267        }
 268}
 269
 270/*
 271 * A line in a file, len-bytes long (includes the terminating LF,
 272 * except for an incomplete line at the end if the file ends with
 273 * one), and its contents hashes to 'hash'.
 274 */
 275struct line {
 276        size_t len;
 277        unsigned hash : 24;
 278        unsigned flag : 8;
 279#define LINE_COMMON     1
 280#define LINE_PATCHED    2
 281};
 282
 283/*
 284 * This represents a "file", which is an array of "lines".
 285 */
 286struct image {
 287        char *buf;
 288        size_t len;
 289        size_t nr;
 290        size_t alloc;
 291        struct line *line_allocated;
 292        struct line *line;
 293};
 294
 295static uint32_t hash_line(const char *cp, size_t len)
 296{
 297        size_t i;
 298        uint32_t h;
 299        for (i = 0, h = 0; i < len; i++) {
 300                if (!isspace(cp[i])) {
 301                        h = h * 3 + (cp[i] & 0xff);
 302                }
 303        }
 304        return h;
 305}
 306
 307/*
 308 * Compare lines s1 of length n1 and s2 of length n2, ignoring
 309 * whitespace difference. Returns 1 if they match, 0 otherwise
 310 */
 311static int fuzzy_matchlines(const char *s1, size_t n1,
 312                            const char *s2, size_t n2)
 313{
 314        const char *last1 = s1 + n1 - 1;
 315        const char *last2 = s2 + n2 - 1;
 316        int result = 0;
 317
 318        /* ignore line endings */
 319        while ((*last1 == '\r') || (*last1 == '\n'))
 320                last1--;
 321        while ((*last2 == '\r') || (*last2 == '\n'))
 322                last2--;
 323
 324        /* skip leading whitespaces, if both begin with whitespace */
 325        if (s1 <= last1 && s2 <= last2 && isspace(*s1) && isspace(*s2)) {
 326                while (isspace(*s1) && (s1 <= last1))
 327                        s1++;
 328                while (isspace(*s2) && (s2 <= last2))
 329                        s2++;
 330        }
 331        /* early return if both lines are empty */
 332        if ((s1 > last1) && (s2 > last2))
 333                return 1;
 334        while (!result) {
 335                result = *s1++ - *s2++;
 336                /*
 337                 * Skip whitespace inside. We check for whitespace on
 338                 * both buffers because we don't want "a b" to match
 339                 * "ab"
 340                 */
 341                if (isspace(*s1) && isspace(*s2)) {
 342                        while (isspace(*s1) && s1 <= last1)
 343                                s1++;
 344                        while (isspace(*s2) && s2 <= last2)
 345                                s2++;
 346                }
 347                /*
 348                 * If we reached the end on one side only,
 349                 * lines don't match
 350                 */
 351                if (
 352                    ((s2 > last2) && (s1 <= last1)) ||
 353                    ((s1 > last1) && (s2 <= last2)))
 354                        return 0;
 355                if ((s1 > last1) && (s2 > last2))
 356                        break;
 357        }
 358
 359        return !result;
 360}
 361
 362static void add_line_info(struct image *img, const char *bol, size_t len, unsigned flag)
 363{
 364        ALLOC_GROW(img->line_allocated, img->nr + 1, img->alloc);
 365        img->line_allocated[img->nr].len = len;
 366        img->line_allocated[img->nr].hash = hash_line(bol, len);
 367        img->line_allocated[img->nr].flag = flag;
 368        img->nr++;
 369}
 370
 371/*
 372 * "buf" has the file contents to be patched (read from various sources).
 373 * attach it to "image" and add line-based index to it.
 374 * "image" now owns the "buf".
 375 */
 376static void prepare_image(struct image *image, char *buf, size_t len,
 377                          int prepare_linetable)
 378{
 379        const char *cp, *ep;
 380
 381        memset(image, 0, sizeof(*image));
 382        image->buf = buf;
 383        image->len = len;
 384
 385        if (!prepare_linetable)
 386                return;
 387
 388        ep = image->buf + image->len;
 389        cp = image->buf;
 390        while (cp < ep) {
 391                const char *next;
 392                for (next = cp; next < ep && *next != '\n'; next++)
 393                        ;
 394                if (next < ep)
 395                        next++;
 396                add_line_info(image, cp, next - cp, 0);
 397                cp = next;
 398        }
 399        image->line = image->line_allocated;
 400}
 401
 402static void clear_image(struct image *image)
 403{
 404        free(image->buf);
 405        free(image->line_allocated);
 406        memset(image, 0, sizeof(*image));
 407}
 408
 409/* fmt must contain _one_ %s and no other substitution */
 410static void say_patch_name(FILE *output, const char *fmt, struct patch *patch)
 411{
 412        struct strbuf sb = STRBUF_INIT;
 413
 414        if (patch->old_name && patch->new_name &&
 415            strcmp(patch->old_name, patch->new_name)) {
 416                quote_c_style(patch->old_name, &sb, NULL, 0);
 417                strbuf_addstr(&sb, " => ");
 418                quote_c_style(patch->new_name, &sb, NULL, 0);
 419        } else {
 420                const char *n = patch->new_name;
 421                if (!n)
 422                        n = patch->old_name;
 423                quote_c_style(n, &sb, NULL, 0);
 424        }
 425        fprintf(output, fmt, sb.buf);
 426        fputc('\n', output);
 427        strbuf_release(&sb);
 428}
 429
 430#define SLOP (16)
 431
 432static void read_patch_file(struct strbuf *sb, int fd)
 433{
 434        if (strbuf_read(sb, fd, 0) < 0)
 435                die_errno("git apply: failed to read");
 436
 437        /*
 438         * Make sure that we have some slop in the buffer
 439         * so that we can do speculative "memcmp" etc, and
 440         * see to it that it is NUL-filled.
 441         */
 442        strbuf_grow(sb, SLOP);
 443        memset(sb->buf + sb->len, 0, SLOP);
 444}
 445
 446static unsigned long linelen(const char *buffer, unsigned long size)
 447{
 448        unsigned long len = 0;
 449        while (size--) {
 450                len++;
 451                if (*buffer++ == '\n')
 452                        break;
 453        }
 454        return len;
 455}
 456
 457static int is_dev_null(const char *str)
 458{
 459        return skip_prefix(str, "/dev/null", &str) && isspace(*str);
 460}
 461
 462#define TERM_SPACE      1
 463#define TERM_TAB        2
 464
 465static int name_terminate(const char *name, int namelen, int c, int terminate)
 466{
 467        if (c == ' ' && !(terminate & TERM_SPACE))
 468                return 0;
 469        if (c == '\t' && !(terminate & TERM_TAB))
 470                return 0;
 471
 472        return 1;
 473}
 474
 475/* remove double slashes to make --index work with such filenames */
 476static char *squash_slash(char *name)
 477{
 478        int i = 0, j = 0;
 479
 480        if (!name)
 481                return NULL;
 482
 483        while (name[i]) {
 484                if ((name[j++] = name[i++]) == '/')
 485                        while (name[i] == '/')
 486                                i++;
 487        }
 488        name[j] = '\0';
 489        return name;
 490}
 491
 492static char *find_name_gnu(struct apply_state *state,
 493                           const char *line,
 494                           const char *def,
 495                           int p_value)
 496{
 497        struct strbuf name = STRBUF_INIT;
 498        char *cp;
 499
 500        /*
 501         * Proposed "new-style" GNU patch/diff format; see
 502         * http://marc.info/?l=git&m=112927316408690&w=2
 503         */
 504        if (unquote_c_style(&name, line, NULL)) {
 505                strbuf_release(&name);
 506                return NULL;
 507        }
 508
 509        for (cp = name.buf; p_value; p_value--) {
 510                cp = strchr(cp, '/');
 511                if (!cp) {
 512                        strbuf_release(&name);
 513                        return NULL;
 514                }
 515                cp++;
 516        }
 517
 518        strbuf_remove(&name, 0, cp - name.buf);
 519        if (state->root.len)
 520                strbuf_insert(&name, 0, state->root.buf, state->root.len);
 521        return squash_slash(strbuf_detach(&name, NULL));
 522}
 523
 524static size_t sane_tz_len(const char *line, size_t len)
 525{
 526        const char *tz, *p;
 527
 528        if (len < strlen(" +0500") || line[len-strlen(" +0500")] != ' ')
 529                return 0;
 530        tz = line + len - strlen(" +0500");
 531
 532        if (tz[1] != '+' && tz[1] != '-')
 533                return 0;
 534
 535        for (p = tz + 2; p != line + len; p++)
 536                if (!isdigit(*p))
 537                        return 0;
 538
 539        return line + len - tz;
 540}
 541
 542static size_t tz_with_colon_len(const char *line, size_t len)
 543{
 544        const char *tz, *p;
 545
 546        if (len < strlen(" +08:00") || line[len - strlen(":00")] != ':')
 547                return 0;
 548        tz = line + len - strlen(" +08:00");
 549
 550        if (tz[0] != ' ' || (tz[1] != '+' && tz[1] != '-'))
 551                return 0;
 552        p = tz + 2;
 553        if (!isdigit(*p++) || !isdigit(*p++) || *p++ != ':' ||
 554            !isdigit(*p++) || !isdigit(*p++))
 555                return 0;
 556
 557        return line + len - tz;
 558}
 559
 560static size_t date_len(const char *line, size_t len)
 561{
 562        const char *date, *p;
 563
 564        if (len < strlen("72-02-05") || line[len-strlen("-05")] != '-')
 565                return 0;
 566        p = date = line + len - strlen("72-02-05");
 567
 568        if (!isdigit(*p++) || !isdigit(*p++) || *p++ != '-' ||
 569            !isdigit(*p++) || !isdigit(*p++) || *p++ != '-' ||
 570            !isdigit(*p++) || !isdigit(*p++))   /* Not a date. */
 571                return 0;
 572
 573        if (date - line >= strlen("19") &&
 574            isdigit(date[-1]) && isdigit(date[-2]))     /* 4-digit year */
 575                date -= strlen("19");
 576
 577        return line + len - date;
 578}
 579
 580static size_t short_time_len(const char *line, size_t len)
 581{
 582        const char *time, *p;
 583
 584        if (len < strlen(" 07:01:32") || line[len-strlen(":32")] != ':')
 585                return 0;
 586        p = time = line + len - strlen(" 07:01:32");
 587
 588        /* Permit 1-digit hours? */
 589        if (*p++ != ' ' ||
 590            !isdigit(*p++) || !isdigit(*p++) || *p++ != ':' ||
 591            !isdigit(*p++) || !isdigit(*p++) || *p++ != ':' ||
 592            !isdigit(*p++) || !isdigit(*p++))   /* Not a time. */
 593                return 0;
 594
 595        return line + len - time;
 596}
 597
 598static size_t fractional_time_len(const char *line, size_t len)
 599{
 600        const char *p;
 601        size_t n;
 602
 603        /* Expected format: 19:41:17.620000023 */
 604        if (!len || !isdigit(line[len - 1]))
 605                return 0;
 606        p = line + len - 1;
 607
 608        /* Fractional seconds. */
 609        while (p > line && isdigit(*p))
 610                p--;
 611        if (*p != '.')
 612                return 0;
 613
 614        /* Hours, minutes, and whole seconds. */
 615        n = short_time_len(line, p - line);
 616        if (!n)
 617                return 0;
 618
 619        return line + len - p + n;
 620}
 621
 622static size_t trailing_spaces_len(const char *line, size_t len)
 623{
 624        const char *p;
 625
 626        /* Expected format: ' ' x (1 or more)  */
 627        if (!len || line[len - 1] != ' ')
 628                return 0;
 629
 630        p = line + len;
 631        while (p != line) {
 632                p--;
 633                if (*p != ' ')
 634                        return line + len - (p + 1);
 635        }
 636
 637        /* All spaces! */
 638        return len;
 639}
 640
 641static size_t diff_timestamp_len(const char *line, size_t len)
 642{
 643        const char *end = line + len;
 644        size_t n;
 645
 646        /*
 647         * Posix: 2010-07-05 19:41:17
 648         * GNU: 2010-07-05 19:41:17.620000023 -0500
 649         */
 650
 651        if (!isdigit(end[-1]))
 652                return 0;
 653
 654        n = sane_tz_len(line, end - line);
 655        if (!n)
 656                n = tz_with_colon_len(line, end - line);
 657        end -= n;
 658
 659        n = short_time_len(line, end - line);
 660        if (!n)
 661                n = fractional_time_len(line, end - line);
 662        end -= n;
 663
 664        n = date_len(line, end - line);
 665        if (!n) /* No date.  Too bad. */
 666                return 0;
 667        end -= n;
 668
 669        if (end == line)        /* No space before date. */
 670                return 0;
 671        if (end[-1] == '\t') {  /* Success! */
 672                end--;
 673                return line + len - end;
 674        }
 675        if (end[-1] != ' ')     /* No space before date. */
 676                return 0;
 677
 678        /* Whitespace damage. */
 679        end -= trailing_spaces_len(line, end - line);
 680        return line + len - end;
 681}
 682
 683static char *find_name_common(struct apply_state *state,
 684                              const char *line,
 685                              const char *def,
 686                              int p_value,
 687                              const char *end,
 688                              int terminate)
 689{
 690        int len;
 691        const char *start = NULL;
 692
 693        if (p_value == 0)
 694                start = line;
 695        while (line != end) {
 696                char c = *line;
 697
 698                if (!end && isspace(c)) {
 699                        if (c == '\n')
 700                                break;
 701                        if (name_terminate(start, line-start, c, terminate))
 702                                break;
 703                }
 704                line++;
 705                if (c == '/' && !--p_value)
 706                        start = line;
 707        }
 708        if (!start)
 709                return squash_slash(xstrdup_or_null(def));
 710        len = line - start;
 711        if (!len)
 712                return squash_slash(xstrdup_or_null(def));
 713
 714        /*
 715         * Generally we prefer the shorter name, especially
 716         * if the other one is just a variation of that with
 717         * something else tacked on to the end (ie "file.orig"
 718         * or "file~").
 719         */
 720        if (def) {
 721                int deflen = strlen(def);
 722                if (deflen < len && !strncmp(start, def, deflen))
 723                        return squash_slash(xstrdup(def));
 724        }
 725
 726        if (state->root.len) {
 727                char *ret = xstrfmt("%s%.*s", state->root.buf, len, start);
 728                return squash_slash(ret);
 729        }
 730
 731        return squash_slash(xmemdupz(start, len));
 732}
 733
 734static char *find_name(struct apply_state *state,
 735                       const char *line,
 736                       char *def,
 737                       int p_value,
 738                       int terminate)
 739{
 740        if (*line == '"') {
 741                char *name = find_name_gnu(state, line, def, p_value);
 742                if (name)
 743                        return name;
 744        }
 745
 746        return find_name_common(state, line, def, p_value, NULL, terminate);
 747}
 748
 749static char *find_name_traditional(struct apply_state *state,
 750                                   const char *line,
 751                                   char *def,
 752                                   int p_value)
 753{
 754        size_t len;
 755        size_t date_len;
 756
 757        if (*line == '"') {
 758                char *name = find_name_gnu(state, line, def, p_value);
 759                if (name)
 760                        return name;
 761        }
 762
 763        len = strchrnul(line, '\n') - line;
 764        date_len = diff_timestamp_len(line, len);
 765        if (!date_len)
 766                return find_name_common(state, line, def, p_value, NULL, TERM_TAB);
 767        len -= date_len;
 768
 769        return find_name_common(state, line, def, p_value, line + len, 0);
 770}
 771
 772static int count_slashes(const char *cp)
 773{
 774        int cnt = 0;
 775        char ch;
 776
 777        while ((ch = *cp++))
 778                if (ch == '/')
 779                        cnt++;
 780        return cnt;
 781}
 782
 783/*
 784 * Given the string after "--- " or "+++ ", guess the appropriate
 785 * p_value for the given patch.
 786 */
 787static int guess_p_value(struct apply_state *state, const char *nameline)
 788{
 789        char *name, *cp;
 790        int val = -1;
 791
 792        if (is_dev_null(nameline))
 793                return -1;
 794        name = find_name_traditional(state, nameline, NULL, 0);
 795        if (!name)
 796                return -1;
 797        cp = strchr(name, '/');
 798        if (!cp)
 799                val = 0;
 800        else if (state->prefix) {
 801                /*
 802                 * Does it begin with "a/$our-prefix" and such?  Then this is
 803                 * very likely to apply to our directory.
 804                 */
 805                if (!strncmp(name, state->prefix, state->prefix_length))
 806                        val = count_slashes(state->prefix);
 807                else {
 808                        cp++;
 809                        if (!strncmp(cp, state->prefix, state->prefix_length))
 810                                val = count_slashes(state->prefix) + 1;
 811                }
 812        }
 813        free(name);
 814        return val;
 815}
 816
 817/*
 818 * Does the ---/+++ line have the POSIX timestamp after the last HT?
 819 * GNU diff puts epoch there to signal a creation/deletion event.  Is
 820 * this such a timestamp?
 821 */
 822static int has_epoch_timestamp(const char *nameline)
 823{
 824        /*
 825         * We are only interested in epoch timestamp; any non-zero
 826         * fraction cannot be one, hence "(\.0+)?" in the regexp below.
 827         * For the same reason, the date must be either 1969-12-31 or
 828         * 1970-01-01, and the seconds part must be "00".
 829         */
 830        const char stamp_regexp[] =
 831                "^(1969-12-31|1970-01-01)"
 832                " "
 833                "[0-2][0-9]:[0-5][0-9]:00(\\.0+)?"
 834                " "
 835                "([-+][0-2][0-9]:?[0-5][0-9])\n";
 836        const char *timestamp = NULL, *cp, *colon;
 837        static regex_t *stamp;
 838        regmatch_t m[10];
 839        int zoneoffset;
 840        int hourminute;
 841        int status;
 842
 843        for (cp = nameline; *cp != '\n'; cp++) {
 844                if (*cp == '\t')
 845                        timestamp = cp + 1;
 846        }
 847        if (!timestamp)
 848                return 0;
 849        if (!stamp) {
 850                stamp = xmalloc(sizeof(*stamp));
 851                if (regcomp(stamp, stamp_regexp, REG_EXTENDED)) {
 852                        warning(_("Cannot prepare timestamp regexp %s"),
 853                                stamp_regexp);
 854                        return 0;
 855                }
 856        }
 857
 858        status = regexec(stamp, timestamp, ARRAY_SIZE(m), m, 0);
 859        if (status) {
 860                if (status != REG_NOMATCH)
 861                        warning(_("regexec returned %d for input: %s"),
 862                                status, timestamp);
 863                return 0;
 864        }
 865
 866        zoneoffset = strtol(timestamp + m[3].rm_so + 1, (char **) &colon, 10);
 867        if (*colon == ':')
 868                zoneoffset = zoneoffset * 60 + strtol(colon + 1, NULL, 10);
 869        else
 870                zoneoffset = (zoneoffset / 100) * 60 + (zoneoffset % 100);
 871        if (timestamp[m[3].rm_so] == '-')
 872                zoneoffset = -zoneoffset;
 873
 874        /*
 875         * YYYY-MM-DD hh:mm:ss must be from either 1969-12-31
 876         * (west of GMT) or 1970-01-01 (east of GMT)
 877         */
 878        if ((zoneoffset < 0 && memcmp(timestamp, "1969-12-31", 10)) ||
 879            (0 <= zoneoffset && memcmp(timestamp, "1970-01-01", 10)))
 880                return 0;
 881
 882        hourminute = (strtol(timestamp + 11, NULL, 10) * 60 +
 883                      strtol(timestamp + 14, NULL, 10) -
 884                      zoneoffset);
 885
 886        return ((zoneoffset < 0 && hourminute == 1440) ||
 887                (0 <= zoneoffset && !hourminute));
 888}
 889
 890/*
 891 * Get the name etc info from the ---/+++ lines of a traditional patch header
 892 *
 893 * FIXME! The end-of-filename heuristics are kind of screwy. For existing
 894 * files, we can happily check the index for a match, but for creating a
 895 * new file we should try to match whatever "patch" does. I have no idea.
 896 */
 897static void parse_traditional_patch(struct apply_state *state,
 898                                    const char *first,
 899                                    const char *second,
 900                                    struct patch *patch)
 901{
 902        char *name;
 903
 904        first += 4;     /* skip "--- " */
 905        second += 4;    /* skip "+++ " */
 906        if (!state->p_value_known) {
 907                int p, q;
 908                p = guess_p_value(state, first);
 909                q = guess_p_value(state, second);
 910                if (p < 0) p = q;
 911                if (0 <= p && p == q) {
 912                        state->p_value = p;
 913                        state->p_value_known = 1;
 914                }
 915        }
 916        if (is_dev_null(first)) {
 917                patch->is_new = 1;
 918                patch->is_delete = 0;
 919                name = find_name_traditional(state, second, NULL, state->p_value);
 920                patch->new_name = name;
 921        } else if (is_dev_null(second)) {
 922                patch->is_new = 0;
 923                patch->is_delete = 1;
 924                name = find_name_traditional(state, first, NULL, state->p_value);
 925                patch->old_name = name;
 926        } else {
 927                char *first_name;
 928                first_name = find_name_traditional(state, first, NULL, state->p_value);
 929                name = find_name_traditional(state, second, first_name, state->p_value);
 930                free(first_name);
 931                if (has_epoch_timestamp(first)) {
 932                        patch->is_new = 1;
 933                        patch->is_delete = 0;
 934                        patch->new_name = name;
 935                } else if (has_epoch_timestamp(second)) {
 936                        patch->is_new = 0;
 937                        patch->is_delete = 1;
 938                        patch->old_name = name;
 939                } else {
 940                        patch->old_name = name;
 941                        patch->new_name = xstrdup_or_null(name);
 942                }
 943        }
 944        if (!name)
 945                die(_("unable to find filename in patch at line %d"), state->linenr);
 946}
 947
 948static int gitdiff_hdrend(struct apply_state *state,
 949                          const char *line,
 950                          struct patch *patch)
 951{
 952        return -1;
 953}
 954
 955/*
 956 * We're anal about diff header consistency, to make
 957 * sure that we don't end up having strange ambiguous
 958 * patches floating around.
 959 *
 960 * As a result, gitdiff_{old|new}name() will check
 961 * their names against any previous information, just
 962 * to make sure..
 963 */
 964#define DIFF_OLD_NAME 0
 965#define DIFF_NEW_NAME 1
 966
 967static void gitdiff_verify_name(struct apply_state *state,
 968                                const char *line,
 969                                int isnull,
 970                                char **name,
 971                                int side)
 972{
 973        if (!*name && !isnull) {
 974                *name = find_name(state, line, NULL, state->p_value, TERM_TAB);
 975                return;
 976        }
 977
 978        if (*name) {
 979                int len = strlen(*name);
 980                char *another;
 981                if (isnull)
 982                        die(_("git apply: bad git-diff - expected /dev/null, got %s on line %d"),
 983                            *name, state->linenr);
 984                another = find_name(state, line, NULL, state->p_value, TERM_TAB);
 985                if (!another || memcmp(another, *name, len + 1))
 986                        die((side == DIFF_NEW_NAME) ?
 987                            _("git apply: bad git-diff - inconsistent new filename on line %d") :
 988                            _("git apply: bad git-diff - inconsistent old filename on line %d"), state->linenr);
 989                free(another);
 990        } else {
 991                /* expect "/dev/null" */
 992                if (memcmp("/dev/null", line, 9) || line[9] != '\n')
 993                        die(_("git apply: bad git-diff - expected /dev/null on line %d"), state->linenr);
 994        }
 995}
 996
 997static int gitdiff_oldname(struct apply_state *state,
 998                           const char *line,
 999                           struct patch *patch)
1000{
1001        gitdiff_verify_name(state, line,
1002                            patch->is_new, &patch->old_name,
1003                            DIFF_OLD_NAME);
1004        return 0;
1005}
1006
1007static int gitdiff_newname(struct apply_state *state,
1008                           const char *line,
1009                           struct patch *patch)
1010{
1011        gitdiff_verify_name(state, line,
1012                            patch->is_delete, &patch->new_name,
1013                            DIFF_NEW_NAME);
1014        return 0;
1015}
1016
1017static int gitdiff_oldmode(struct apply_state *state,
1018                           const char *line,
1019                           struct patch *patch)
1020{
1021        patch->old_mode = strtoul(line, NULL, 8);
1022        return 0;
1023}
1024
1025static int gitdiff_newmode(struct apply_state *state,
1026                           const char *line,
1027                           struct patch *patch)
1028{
1029        patch->new_mode = strtoul(line, NULL, 8);
1030        return 0;
1031}
1032
1033static int gitdiff_delete(struct apply_state *state,
1034                          const char *line,
1035                          struct patch *patch)
1036{
1037        patch->is_delete = 1;
1038        free(patch->old_name);
1039        patch->old_name = xstrdup_or_null(patch->def_name);
1040        return gitdiff_oldmode(state, line, patch);
1041}
1042
1043static int gitdiff_newfile(struct apply_state *state,
1044                           const char *line,
1045                           struct patch *patch)
1046{
1047        patch->is_new = 1;
1048        free(patch->new_name);
1049        patch->new_name = xstrdup_or_null(patch->def_name);
1050        return gitdiff_newmode(state, line, patch);
1051}
1052
1053static int gitdiff_copysrc(struct apply_state *state,
1054                           const char *line,
1055                           struct patch *patch)
1056{
1057        patch->is_copy = 1;
1058        free(patch->old_name);
1059        patch->old_name = find_name(state, line, NULL, state->p_value ? state->p_value - 1 : 0, 0);
1060        return 0;
1061}
1062
1063static int gitdiff_copydst(struct apply_state *state,
1064                           const char *line,
1065                           struct patch *patch)
1066{
1067        patch->is_copy = 1;
1068        free(patch->new_name);
1069        patch->new_name = find_name(state, line, NULL, state->p_value ? state->p_value - 1 : 0, 0);
1070        return 0;
1071}
1072
1073static int gitdiff_renamesrc(struct apply_state *state,
1074                             const char *line,
1075                             struct patch *patch)
1076{
1077        patch->is_rename = 1;
1078        free(patch->old_name);
1079        patch->old_name = find_name(state, line, NULL, state->p_value ? state->p_value - 1 : 0, 0);
1080        return 0;
1081}
1082
1083static int gitdiff_renamedst(struct apply_state *state,
1084                             const char *line,
1085                             struct patch *patch)
1086{
1087        patch->is_rename = 1;
1088        free(patch->new_name);
1089        patch->new_name = find_name(state, line, NULL, state->p_value ? state->p_value - 1 : 0, 0);
1090        return 0;
1091}
1092
1093static int gitdiff_similarity(struct apply_state *state,
1094                              const char *line,
1095                              struct patch *patch)
1096{
1097        unsigned long val = strtoul(line, NULL, 10);
1098        if (val <= 100)
1099                patch->score = val;
1100        return 0;
1101}
1102
1103static int gitdiff_dissimilarity(struct apply_state *state,
1104                                 const char *line,
1105                                 struct patch *patch)
1106{
1107        unsigned long val = strtoul(line, NULL, 10);
1108        if (val <= 100)
1109                patch->score = val;
1110        return 0;
1111}
1112
1113static int gitdiff_index(struct apply_state *state,
1114                         const char *line,
1115                         struct patch *patch)
1116{
1117        /*
1118         * index line is N hexadecimal, "..", N hexadecimal,
1119         * and optional space with octal mode.
1120         */
1121        const char *ptr, *eol;
1122        int len;
1123
1124        ptr = strchr(line, '.');
1125        if (!ptr || ptr[1] != '.' || 40 < ptr - line)
1126                return 0;
1127        len = ptr - line;
1128        memcpy(patch->old_sha1_prefix, line, len);
1129        patch->old_sha1_prefix[len] = 0;
1130
1131        line = ptr + 2;
1132        ptr = strchr(line, ' ');
1133        eol = strchrnul(line, '\n');
1134
1135        if (!ptr || eol < ptr)
1136                ptr = eol;
1137        len = ptr - line;
1138
1139        if (40 < len)
1140                return 0;
1141        memcpy(patch->new_sha1_prefix, line, len);
1142        patch->new_sha1_prefix[len] = 0;
1143        if (*ptr == ' ')
1144                patch->old_mode = strtoul(ptr+1, NULL, 8);
1145        return 0;
1146}
1147
1148/*
1149 * This is normal for a diff that doesn't change anything: we'll fall through
1150 * into the next diff. Tell the parser to break out.
1151 */
1152static int gitdiff_unrecognized(struct apply_state *state,
1153                                const char *line,
1154                                struct patch *patch)
1155{
1156        return -1;
1157}
1158
1159/*
1160 * Skip p_value leading components from "line"; as we do not accept
1161 * absolute paths, return NULL in that case.
1162 */
1163static const char *skip_tree_prefix(struct apply_state *state,
1164                                    const char *line,
1165                                    int llen)
1166{
1167        int nslash;
1168        int i;
1169
1170        if (!state->p_value)
1171                return (llen && line[0] == '/') ? NULL : line;
1172
1173        nslash = state->p_value;
1174        for (i = 0; i < llen; i++) {
1175                int ch = line[i];
1176                if (ch == '/' && --nslash <= 0)
1177                        return (i == 0) ? NULL : &line[i + 1];
1178        }
1179        return NULL;
1180}
1181
1182/*
1183 * This is to extract the same name that appears on "diff --git"
1184 * line.  We do not find and return anything if it is a rename
1185 * patch, and it is OK because we will find the name elsewhere.
1186 * We need to reliably find name only when it is mode-change only,
1187 * creation or deletion of an empty file.  In any of these cases,
1188 * both sides are the same name under a/ and b/ respectively.
1189 */
1190static char *git_header_name(struct apply_state *state,
1191                             const char *line,
1192                             int llen)
1193{
1194        const char *name;
1195        const char *second = NULL;
1196        size_t len, line_len;
1197
1198        line += strlen("diff --git ");
1199        llen -= strlen("diff --git ");
1200
1201        if (*line == '"') {
1202                const char *cp;
1203                struct strbuf first = STRBUF_INIT;
1204                struct strbuf sp = STRBUF_INIT;
1205
1206                if (unquote_c_style(&first, line, &second))
1207                        goto free_and_fail1;
1208
1209                /* strip the a/b prefix including trailing slash */
1210                cp = skip_tree_prefix(state, first.buf, first.len);
1211                if (!cp)
1212                        goto free_and_fail1;
1213                strbuf_remove(&first, 0, cp - first.buf);
1214
1215                /*
1216                 * second points at one past closing dq of name.
1217                 * find the second name.
1218                 */
1219                while ((second < line + llen) && isspace(*second))
1220                        second++;
1221
1222                if (line + llen <= second)
1223                        goto free_and_fail1;
1224                if (*second == '"') {
1225                        if (unquote_c_style(&sp, second, NULL))
1226                                goto free_and_fail1;
1227                        cp = skip_tree_prefix(state, sp.buf, sp.len);
1228                        if (!cp)
1229                                goto free_and_fail1;
1230                        /* They must match, otherwise ignore */
1231                        if (strcmp(cp, first.buf))
1232                                goto free_and_fail1;
1233                        strbuf_release(&sp);
1234                        return strbuf_detach(&first, NULL);
1235                }
1236
1237                /* unquoted second */
1238                cp = skip_tree_prefix(state, second, line + llen - second);
1239                if (!cp)
1240                        goto free_and_fail1;
1241                if (line + llen - cp != first.len ||
1242                    memcmp(first.buf, cp, first.len))
1243                        goto free_and_fail1;
1244                return strbuf_detach(&first, NULL);
1245
1246        free_and_fail1:
1247                strbuf_release(&first);
1248                strbuf_release(&sp);
1249                return NULL;
1250        }
1251
1252        /* unquoted first name */
1253        name = skip_tree_prefix(state, line, llen);
1254        if (!name)
1255                return NULL;
1256
1257        /*
1258         * since the first name is unquoted, a dq if exists must be
1259         * the beginning of the second name.
1260         */
1261        for (second = name; second < line + llen; second++) {
1262                if (*second == '"') {
1263                        struct strbuf sp = STRBUF_INIT;
1264                        const char *np;
1265
1266                        if (unquote_c_style(&sp, second, NULL))
1267                                goto free_and_fail2;
1268
1269                        np = skip_tree_prefix(state, sp.buf, sp.len);
1270                        if (!np)
1271                                goto free_and_fail2;
1272
1273                        len = sp.buf + sp.len - np;
1274                        if (len < second - name &&
1275                            !strncmp(np, name, len) &&
1276                            isspace(name[len])) {
1277                                /* Good */
1278                                strbuf_remove(&sp, 0, np - sp.buf);
1279                                return strbuf_detach(&sp, NULL);
1280                        }
1281
1282                free_and_fail2:
1283                        strbuf_release(&sp);
1284                        return NULL;
1285                }
1286        }
1287
1288        /*
1289         * Accept a name only if it shows up twice, exactly the same
1290         * form.
1291         */
1292        second = strchr(name, '\n');
1293        if (!second)
1294                return NULL;
1295        line_len = second - name;
1296        for (len = 0 ; ; len++) {
1297                switch (name[len]) {
1298                default:
1299                        continue;
1300                case '\n':
1301                        return NULL;
1302                case '\t': case ' ':
1303                        /*
1304                         * Is this the separator between the preimage
1305                         * and the postimage pathname?  Again, we are
1306                         * only interested in the case where there is
1307                         * no rename, as this is only to set def_name
1308                         * and a rename patch has the names elsewhere
1309                         * in an unambiguous form.
1310                         */
1311                        if (!name[len + 1])
1312                                return NULL; /* no postimage name */
1313                        second = skip_tree_prefix(state, name + len + 1,
1314                                                  line_len - (len + 1));
1315                        if (!second)
1316                                return NULL;
1317                        /*
1318                         * Does len bytes starting at "name" and "second"
1319                         * (that are separated by one HT or SP we just
1320                         * found) exactly match?
1321                         */
1322                        if (second[len] == '\n' && !strncmp(name, second, len))
1323                                return xmemdupz(name, len);
1324                }
1325        }
1326}
1327
1328/* Verify that we recognize the lines following a git header */
1329static int parse_git_header(struct apply_state *state,
1330                            const char *line,
1331                            int len,
1332                            unsigned int size,
1333                            struct patch *patch)
1334{
1335        unsigned long offset;
1336
1337        /* A git diff has explicit new/delete information, so we don't guess */
1338        patch->is_new = 0;
1339        patch->is_delete = 0;
1340
1341        /*
1342         * Some things may not have the old name in the
1343         * rest of the headers anywhere (pure mode changes,
1344         * or removing or adding empty files), so we get
1345         * the default name from the header.
1346         */
1347        patch->def_name = git_header_name(state, line, len);
1348        if (patch->def_name && state->root.len) {
1349                char *s = xstrfmt("%s%s", state->root.buf, patch->def_name);
1350                free(patch->def_name);
1351                patch->def_name = s;
1352        }
1353
1354        line += len;
1355        size -= len;
1356        state->linenr++;
1357        for (offset = len ; size > 0 ; offset += len, size -= len, line += len, state->linenr++) {
1358                static const struct opentry {
1359                        const char *str;
1360                        int (*fn)(struct apply_state *, const char *, struct patch *);
1361                } optable[] = {
1362                        { "@@ -", gitdiff_hdrend },
1363                        { "--- ", gitdiff_oldname },
1364                        { "+++ ", gitdiff_newname },
1365                        { "old mode ", gitdiff_oldmode },
1366                        { "new mode ", gitdiff_newmode },
1367                        { "deleted file mode ", gitdiff_delete },
1368                        { "new file mode ", gitdiff_newfile },
1369                        { "copy from ", gitdiff_copysrc },
1370                        { "copy to ", gitdiff_copydst },
1371                        { "rename old ", gitdiff_renamesrc },
1372                        { "rename new ", gitdiff_renamedst },
1373                        { "rename from ", gitdiff_renamesrc },
1374                        { "rename to ", gitdiff_renamedst },
1375                        { "similarity index ", gitdiff_similarity },
1376                        { "dissimilarity index ", gitdiff_dissimilarity },
1377                        { "index ", gitdiff_index },
1378                        { "", gitdiff_unrecognized },
1379                };
1380                int i;
1381
1382                len = linelen(line, size);
1383                if (!len || line[len-1] != '\n')
1384                        break;
1385                for (i = 0; i < ARRAY_SIZE(optable); i++) {
1386                        const struct opentry *p = optable + i;
1387                        int oplen = strlen(p->str);
1388                        if (len < oplen || memcmp(p->str, line, oplen))
1389                                continue;
1390                        if (p->fn(state, line + oplen, patch) < 0)
1391                                return offset;
1392                        break;
1393                }
1394        }
1395
1396        return offset;
1397}
1398
1399static int parse_num(const char *line, unsigned long *p)
1400{
1401        char *ptr;
1402
1403        if (!isdigit(*line))
1404                return 0;
1405        *p = strtoul(line, &ptr, 10);
1406        return ptr - line;
1407}
1408
1409static int parse_range(const char *line, int len, int offset, const char *expect,
1410                       unsigned long *p1, unsigned long *p2)
1411{
1412        int digits, ex;
1413
1414        if (offset < 0 || offset >= len)
1415                return -1;
1416        line += offset;
1417        len -= offset;
1418
1419        digits = parse_num(line, p1);
1420        if (!digits)
1421                return -1;
1422
1423        offset += digits;
1424        line += digits;
1425        len -= digits;
1426
1427        *p2 = 1;
1428        if (*line == ',') {
1429                digits = parse_num(line+1, p2);
1430                if (!digits)
1431                        return -1;
1432
1433                offset += digits+1;
1434                line += digits+1;
1435                len -= digits+1;
1436        }
1437
1438        ex = strlen(expect);
1439        if (ex > len)
1440                return -1;
1441        if (memcmp(line, expect, ex))
1442                return -1;
1443
1444        return offset + ex;
1445}
1446
1447static void recount_diff(const char *line, int size, struct fragment *fragment)
1448{
1449        int oldlines = 0, newlines = 0, ret = 0;
1450
1451        if (size < 1) {
1452                warning("recount: ignore empty hunk");
1453                return;
1454        }
1455
1456        for (;;) {
1457                int len = linelen(line, size);
1458                size -= len;
1459                line += len;
1460
1461                if (size < 1)
1462                        break;
1463
1464                switch (*line) {
1465                case ' ': case '\n':
1466                        newlines++;
1467                        /* fall through */
1468                case '-':
1469                        oldlines++;
1470                        continue;
1471                case '+':
1472                        newlines++;
1473                        continue;
1474                case '\\':
1475                        continue;
1476                case '@':
1477                        ret = size < 3 || !starts_with(line, "@@ ");
1478                        break;
1479                case 'd':
1480                        ret = size < 5 || !starts_with(line, "diff ");
1481                        break;
1482                default:
1483                        ret = -1;
1484                        break;
1485                }
1486                if (ret) {
1487                        warning(_("recount: unexpected line: %.*s"),
1488                                (int)linelen(line, size), line);
1489                        return;
1490                }
1491                break;
1492        }
1493        fragment->oldlines = oldlines;
1494        fragment->newlines = newlines;
1495}
1496
1497/*
1498 * Parse a unified diff fragment header of the
1499 * form "@@ -a,b +c,d @@"
1500 */
1501static int parse_fragment_header(const char *line, int len, struct fragment *fragment)
1502{
1503        int offset;
1504
1505        if (!len || line[len-1] != '\n')
1506                return -1;
1507
1508        /* Figure out the number of lines in a fragment */
1509        offset = parse_range(line, len, 4, " +", &fragment->oldpos, &fragment->oldlines);
1510        offset = parse_range(line, len, offset, " @@", &fragment->newpos, &fragment->newlines);
1511
1512        return offset;
1513}
1514
1515static int find_header(struct apply_state *state,
1516                       const char *line,
1517                       unsigned long size,
1518                       int *hdrsize,
1519                       struct patch *patch)
1520{
1521        unsigned long offset, len;
1522
1523        patch->is_toplevel_relative = 0;
1524        patch->is_rename = patch->is_copy = 0;
1525        patch->is_new = patch->is_delete = -1;
1526        patch->old_mode = patch->new_mode = 0;
1527        patch->old_name = patch->new_name = NULL;
1528        for (offset = 0; size > 0; offset += len, size -= len, line += len, state->linenr++) {
1529                unsigned long nextlen;
1530
1531                len = linelen(line, size);
1532                if (!len)
1533                        break;
1534
1535                /* Testing this early allows us to take a few shortcuts.. */
1536                if (len < 6)
1537                        continue;
1538
1539                /*
1540                 * Make sure we don't find any unconnected patch fragments.
1541                 * That's a sign that we didn't find a header, and that a
1542                 * patch has become corrupted/broken up.
1543                 */
1544                if (!memcmp("@@ -", line, 4)) {
1545                        struct fragment dummy;
1546                        if (parse_fragment_header(line, len, &dummy) < 0)
1547                                continue;
1548                        die(_("patch fragment without header at line %d: %.*s"),
1549                            state->linenr, (int)len-1, line);
1550                }
1551
1552                if (size < len + 6)
1553                        break;
1554
1555                /*
1556                 * Git patch? It might not have a real patch, just a rename
1557                 * or mode change, so we handle that specially
1558                 */
1559                if (!memcmp("diff --git ", line, 11)) {
1560                        int git_hdr_len = parse_git_header(state, line, len, size, patch);
1561                        if (git_hdr_len <= len)
1562                                continue;
1563                        if (!patch->old_name && !patch->new_name) {
1564                                if (!patch->def_name)
1565                                        die(Q_("git diff header lacks filename information when removing "
1566                                               "%d leading pathname component (line %d)",
1567                                               "git diff header lacks filename information when removing "
1568                                               "%d leading pathname components (line %d)",
1569                                               state->p_value),
1570                                            state->p_value, state->linenr);
1571                                patch->old_name = xstrdup(patch->def_name);
1572                                patch->new_name = xstrdup(patch->def_name);
1573                        }
1574                        if (!patch->is_delete && !patch->new_name)
1575                                die("git diff header lacks filename information "
1576                                    "(line %d)", state->linenr);
1577                        patch->is_toplevel_relative = 1;
1578                        *hdrsize = git_hdr_len;
1579                        return offset;
1580                }
1581
1582                /* --- followed by +++ ? */
1583                if (memcmp("--- ", line,  4) || memcmp("+++ ", line + len, 4))
1584                        continue;
1585
1586                /*
1587                 * We only accept unified patches, so we want it to
1588                 * at least have "@@ -a,b +c,d @@\n", which is 14 chars
1589                 * minimum ("@@ -0,0 +1 @@\n" is the shortest).
1590                 */
1591                nextlen = linelen(line + len, size - len);
1592                if (size < nextlen + 14 || memcmp("@@ -", line + len + nextlen, 4))
1593                        continue;
1594
1595                /* Ok, we'll consider it a patch */
1596                parse_traditional_patch(state, line, line+len, patch);
1597                *hdrsize = len + nextlen;
1598                state->linenr += 2;
1599                return offset;
1600        }
1601        return -1;
1602}
1603
1604static void record_ws_error(struct apply_state *state,
1605                            unsigned result,
1606                            const char *line,
1607                            int len,
1608                            int linenr)
1609{
1610        char *err;
1611
1612        if (!result)
1613                return;
1614
1615        state->whitespace_error++;
1616        if (state->squelch_whitespace_errors &&
1617            state->squelch_whitespace_errors < state->whitespace_error)
1618                return;
1619
1620        err = whitespace_error_string(result);
1621        fprintf(stderr, "%s:%d: %s.\n%.*s\n",
1622                state->patch_input_file, linenr, err, len, line);
1623        free(err);
1624}
1625
1626static void check_whitespace(struct apply_state *state,
1627                             const char *line,
1628                             int len,
1629                             unsigned ws_rule)
1630{
1631        unsigned result = ws_check(line + 1, len - 1, ws_rule);
1632
1633        record_ws_error(state, result, line + 1, len - 2, state->linenr);
1634}
1635
1636/*
1637 * Parse a unified diff. Note that this really needs to parse each
1638 * fragment separately, since the only way to know the difference
1639 * between a "---" that is part of a patch, and a "---" that starts
1640 * the next patch is to look at the line counts..
1641 */
1642static int parse_fragment(struct apply_state *state,
1643                          const char *line,
1644                          unsigned long size,
1645                          struct patch *patch,
1646                          struct fragment *fragment)
1647{
1648        int added, deleted;
1649        int len = linelen(line, size), offset;
1650        unsigned long oldlines, newlines;
1651        unsigned long leading, trailing;
1652
1653        offset = parse_fragment_header(line, len, fragment);
1654        if (offset < 0)
1655                return -1;
1656        if (offset > 0 && patch->recount)
1657                recount_diff(line + offset, size - offset, fragment);
1658        oldlines = fragment->oldlines;
1659        newlines = fragment->newlines;
1660        leading = 0;
1661        trailing = 0;
1662
1663        /* Parse the thing.. */
1664        line += len;
1665        size -= len;
1666        state->linenr++;
1667        added = deleted = 0;
1668        for (offset = len;
1669             0 < size;
1670             offset += len, size -= len, line += len, state->linenr++) {
1671                if (!oldlines && !newlines)
1672                        break;
1673                len = linelen(line, size);
1674                if (!len || line[len-1] != '\n')
1675                        return -1;
1676                switch (*line) {
1677                default:
1678                        return -1;
1679                case '\n': /* newer GNU diff, an empty context line */
1680                case ' ':
1681                        oldlines--;
1682                        newlines--;
1683                        if (!deleted && !added)
1684                                leading++;
1685                        trailing++;
1686                        if (!state->apply_in_reverse &&
1687                            state->ws_error_action == correct_ws_error)
1688                                check_whitespace(state, line, len, patch->ws_rule);
1689                        break;
1690                case '-':
1691                        if (state->apply_in_reverse &&
1692                            state->ws_error_action != nowarn_ws_error)
1693                                check_whitespace(state, line, len, patch->ws_rule);
1694                        deleted++;
1695                        oldlines--;
1696                        trailing = 0;
1697                        break;
1698                case '+':
1699                        if (!state->apply_in_reverse &&
1700                            state->ws_error_action != nowarn_ws_error)
1701                                check_whitespace(state, line, len, patch->ws_rule);
1702                        added++;
1703                        newlines--;
1704                        trailing = 0;
1705                        break;
1706
1707                /*
1708                 * We allow "\ No newline at end of file". Depending
1709                 * on locale settings when the patch was produced we
1710                 * don't know what this line looks like. The only
1711                 * thing we do know is that it begins with "\ ".
1712                 * Checking for 12 is just for sanity check -- any
1713                 * l10n of "\ No newline..." is at least that long.
1714                 */
1715                case '\\':
1716                        if (len < 12 || memcmp(line, "\\ ", 2))
1717                                return -1;
1718                        break;
1719                }
1720        }
1721        if (oldlines || newlines)
1722                return -1;
1723        if (!deleted && !added)
1724                return -1;
1725
1726        fragment->leading = leading;
1727        fragment->trailing = trailing;
1728
1729        /*
1730         * If a fragment ends with an incomplete line, we failed to include
1731         * it in the above loop because we hit oldlines == newlines == 0
1732         * before seeing it.
1733         */
1734        if (12 < size && !memcmp(line, "\\ ", 2))
1735                offset += linelen(line, size);
1736
1737        patch->lines_added += added;
1738        patch->lines_deleted += deleted;
1739
1740        if (0 < patch->is_new && oldlines)
1741                return error(_("new file depends on old contents"));
1742        if (0 < patch->is_delete && newlines)
1743                return error(_("deleted file still has contents"));
1744        return offset;
1745}
1746
1747/*
1748 * We have seen "diff --git a/... b/..." header (or a traditional patch
1749 * header).  Read hunks that belong to this patch into fragments and hang
1750 * them to the given patch structure.
1751 *
1752 * The (fragment->patch, fragment->size) pair points into the memory given
1753 * by the caller, not a copy, when we return.
1754 */
1755static int parse_single_patch(struct apply_state *state,
1756                              const char *line,
1757                              unsigned long size,
1758                              struct patch *patch)
1759{
1760        unsigned long offset = 0;
1761        unsigned long oldlines = 0, newlines = 0, context = 0;
1762        struct fragment **fragp = &patch->fragments;
1763
1764        while (size > 4 && !memcmp(line, "@@ -", 4)) {
1765                struct fragment *fragment;
1766                int len;
1767
1768                fragment = xcalloc(1, sizeof(*fragment));
1769                fragment->linenr = state->linenr;
1770                len = parse_fragment(state, line, size, patch, fragment);
1771                if (len <= 0)
1772                        die(_("corrupt patch at line %d"), state->linenr);
1773                fragment->patch = line;
1774                fragment->size = len;
1775                oldlines += fragment->oldlines;
1776                newlines += fragment->newlines;
1777                context += fragment->leading + fragment->trailing;
1778
1779                *fragp = fragment;
1780                fragp = &fragment->next;
1781
1782                offset += len;
1783                line += len;
1784                size -= len;
1785        }
1786
1787        /*
1788         * If something was removed (i.e. we have old-lines) it cannot
1789         * be creation, and if something was added it cannot be
1790         * deletion.  However, the reverse is not true; --unified=0
1791         * patches that only add are not necessarily creation even
1792         * though they do not have any old lines, and ones that only
1793         * delete are not necessarily deletion.
1794         *
1795         * Unfortunately, a real creation/deletion patch do _not_ have
1796         * any context line by definition, so we cannot safely tell it
1797         * apart with --unified=0 insanity.  At least if the patch has
1798         * more than one hunk it is not creation or deletion.
1799         */
1800        if (patch->is_new < 0 &&
1801            (oldlines || (patch->fragments && patch->fragments->next)))
1802                patch->is_new = 0;
1803        if (patch->is_delete < 0 &&
1804            (newlines || (patch->fragments && patch->fragments->next)))
1805                patch->is_delete = 0;
1806
1807        if (0 < patch->is_new && oldlines)
1808                die(_("new file %s depends on old contents"), patch->new_name);
1809        if (0 < patch->is_delete && newlines)
1810                die(_("deleted file %s still has contents"), patch->old_name);
1811        if (!patch->is_delete && !newlines && context)
1812                fprintf_ln(stderr,
1813                           _("** warning: "
1814                             "file %s becomes empty but is not deleted"),
1815                           patch->new_name);
1816
1817        return offset;
1818}
1819
1820static inline int metadata_changes(struct patch *patch)
1821{
1822        return  patch->is_rename > 0 ||
1823                patch->is_copy > 0 ||
1824                patch->is_new > 0 ||
1825                patch->is_delete ||
1826                (patch->old_mode && patch->new_mode &&
1827                 patch->old_mode != patch->new_mode);
1828}
1829
1830static char *inflate_it(const void *data, unsigned long size,
1831                        unsigned long inflated_size)
1832{
1833        git_zstream stream;
1834        void *out;
1835        int st;
1836
1837        memset(&stream, 0, sizeof(stream));
1838
1839        stream.next_in = (unsigned char *)data;
1840        stream.avail_in = size;
1841        stream.next_out = out = xmalloc(inflated_size);
1842        stream.avail_out = inflated_size;
1843        git_inflate_init(&stream);
1844        st = git_inflate(&stream, Z_FINISH);
1845        git_inflate_end(&stream);
1846        if ((st != Z_STREAM_END) || stream.total_out != inflated_size) {
1847                free(out);
1848                return NULL;
1849        }
1850        return out;
1851}
1852
1853/*
1854 * Read a binary hunk and return a new fragment; fragment->patch
1855 * points at an allocated memory that the caller must free, so
1856 * it is marked as "->free_patch = 1".
1857 */
1858static struct fragment *parse_binary_hunk(struct apply_state *state,
1859                                          char **buf_p,
1860                                          unsigned long *sz_p,
1861                                          int *status_p,
1862                                          int *used_p)
1863{
1864        /*
1865         * Expect a line that begins with binary patch method ("literal"
1866         * or "delta"), followed by the length of data before deflating.
1867         * a sequence of 'length-byte' followed by base-85 encoded data
1868         * should follow, terminated by a newline.
1869         *
1870         * Each 5-byte sequence of base-85 encodes up to 4 bytes,
1871         * and we would limit the patch line to 66 characters,
1872         * so one line can fit up to 13 groups that would decode
1873         * to 52 bytes max.  The length byte 'A'-'Z' corresponds
1874         * to 1-26 bytes, and 'a'-'z' corresponds to 27-52 bytes.
1875         */
1876        int llen, used;
1877        unsigned long size = *sz_p;
1878        char *buffer = *buf_p;
1879        int patch_method;
1880        unsigned long origlen;
1881        char *data = NULL;
1882        int hunk_size = 0;
1883        struct fragment *frag;
1884
1885        llen = linelen(buffer, size);
1886        used = llen;
1887
1888        *status_p = 0;
1889
1890        if (starts_with(buffer, "delta ")) {
1891                patch_method = BINARY_DELTA_DEFLATED;
1892                origlen = strtoul(buffer + 6, NULL, 10);
1893        }
1894        else if (starts_with(buffer, "literal ")) {
1895                patch_method = BINARY_LITERAL_DEFLATED;
1896                origlen = strtoul(buffer + 8, NULL, 10);
1897        }
1898        else
1899                return NULL;
1900
1901        state->linenr++;
1902        buffer += llen;
1903        while (1) {
1904                int byte_length, max_byte_length, newsize;
1905                llen = linelen(buffer, size);
1906                used += llen;
1907                state->linenr++;
1908                if (llen == 1) {
1909                        /* consume the blank line */
1910                        buffer++;
1911                        size--;
1912                        break;
1913                }
1914                /*
1915                 * Minimum line is "A00000\n" which is 7-byte long,
1916                 * and the line length must be multiple of 5 plus 2.
1917                 */
1918                if ((llen < 7) || (llen-2) % 5)
1919                        goto corrupt;
1920                max_byte_length = (llen - 2) / 5 * 4;
1921                byte_length = *buffer;
1922                if ('A' <= byte_length && byte_length <= 'Z')
1923                        byte_length = byte_length - 'A' + 1;
1924                else if ('a' <= byte_length && byte_length <= 'z')
1925                        byte_length = byte_length - 'a' + 27;
1926                else
1927                        goto corrupt;
1928                /* if the input length was not multiple of 4, we would
1929                 * have filler at the end but the filler should never
1930                 * exceed 3 bytes
1931                 */
1932                if (max_byte_length < byte_length ||
1933                    byte_length <= max_byte_length - 4)
1934                        goto corrupt;
1935                newsize = hunk_size + byte_length;
1936                data = xrealloc(data, newsize);
1937                if (decode_85(data + hunk_size, buffer + 1, byte_length))
1938                        goto corrupt;
1939                hunk_size = newsize;
1940                buffer += llen;
1941                size -= llen;
1942        }
1943
1944        frag = xcalloc(1, sizeof(*frag));
1945        frag->patch = inflate_it(data, hunk_size, origlen);
1946        frag->free_patch = 1;
1947        if (!frag->patch)
1948                goto corrupt;
1949        free(data);
1950        frag->size = origlen;
1951        *buf_p = buffer;
1952        *sz_p = size;
1953        *used_p = used;
1954        frag->binary_patch_method = patch_method;
1955        return frag;
1956
1957 corrupt:
1958        free(data);
1959        *status_p = -1;
1960        error(_("corrupt binary patch at line %d: %.*s"),
1961              state->linenr-1, llen-1, buffer);
1962        return NULL;
1963}
1964
1965/*
1966 * Returns:
1967 *   -1 in case of error,
1968 *   the length of the parsed binary patch otherwise
1969 */
1970static int parse_binary(struct apply_state *state,
1971                        char *buffer,
1972                        unsigned long size,
1973                        struct patch *patch)
1974{
1975        /*
1976         * We have read "GIT binary patch\n"; what follows is a line
1977         * that says the patch method (currently, either "literal" or
1978         * "delta") and the length of data before deflating; a
1979         * sequence of 'length-byte' followed by base-85 encoded data
1980         * follows.
1981         *
1982         * When a binary patch is reversible, there is another binary
1983         * hunk in the same format, starting with patch method (either
1984         * "literal" or "delta") with the length of data, and a sequence
1985         * of length-byte + base-85 encoded data, terminated with another
1986         * empty line.  This data, when applied to the postimage, produces
1987         * the preimage.
1988         */
1989        struct fragment *forward;
1990        struct fragment *reverse;
1991        int status;
1992        int used, used_1;
1993
1994        forward = parse_binary_hunk(state, &buffer, &size, &status, &used);
1995        if (!forward && !status)
1996                /* there has to be one hunk (forward hunk) */
1997                return error(_("unrecognized binary patch at line %d"), state->linenr-1);
1998        if (status)
1999                /* otherwise we already gave an error message */
2000                return status;
2001
2002        reverse = parse_binary_hunk(state, &buffer, &size, &status, &used_1);
2003        if (reverse)
2004                used += used_1;
2005        else if (status) {
2006                /*
2007                 * Not having reverse hunk is not an error, but having
2008                 * a corrupt reverse hunk is.
2009                 */
2010                free((void*) forward->patch);
2011                free(forward);
2012                return status;
2013        }
2014        forward->next = reverse;
2015        patch->fragments = forward;
2016        patch->is_binary = 1;
2017        return used;
2018}
2019
2020static void prefix_one(struct apply_state *state, char **name)
2021{
2022        char *old_name = *name;
2023        if (!old_name)
2024                return;
2025        *name = xstrdup(prefix_filename(state->prefix, state->prefix_length, *name));
2026        free(old_name);
2027}
2028
2029static void prefix_patch(struct apply_state *state, struct patch *p)
2030{
2031        if (!state->prefix || p->is_toplevel_relative)
2032                return;
2033        prefix_one(state, &p->new_name);
2034        prefix_one(state, &p->old_name);
2035}
2036
2037/*
2038 * include/exclude
2039 */
2040
2041static void add_name_limit(struct apply_state *state,
2042                           const char *name,
2043                           int exclude)
2044{
2045        struct string_list_item *it;
2046
2047        it = string_list_append(&state->limit_by_name, name);
2048        it->util = exclude ? NULL : (void *) 1;
2049}
2050
2051static int use_patch(struct apply_state *state, struct patch *p)
2052{
2053        const char *pathname = p->new_name ? p->new_name : p->old_name;
2054        int i;
2055
2056        /* Paths outside are not touched regardless of "--include" */
2057        if (0 < state->prefix_length) {
2058                int pathlen = strlen(pathname);
2059                if (pathlen <= state->prefix_length ||
2060                    memcmp(state->prefix, pathname, state->prefix_length))
2061                        return 0;
2062        }
2063
2064        /* See if it matches any of exclude/include rule */
2065        for (i = 0; i < state->limit_by_name.nr; i++) {
2066                struct string_list_item *it = &state->limit_by_name.items[i];
2067                if (!wildmatch(it->string, pathname, 0, NULL))
2068                        return (it->util != NULL);
2069        }
2070
2071        /*
2072         * If we had any include, a path that does not match any rule is
2073         * not used.  Otherwise, we saw bunch of exclude rules (or none)
2074         * and such a path is used.
2075         */
2076        return !state->has_include;
2077}
2078
2079
2080/*
2081 * Read the patch text in "buffer" that extends for "size" bytes; stop
2082 * reading after seeing a single patch (i.e. changes to a single file).
2083 * Create fragments (i.e. patch hunks) and hang them to the given patch.
2084 * Return the number of bytes consumed, so that the caller can call us
2085 * again for the next patch.
2086 */
2087static int parse_chunk(struct apply_state *state, char *buffer, unsigned long size, struct patch *patch)
2088{
2089        int hdrsize, patchsize;
2090        int offset = find_header(state, buffer, size, &hdrsize, patch);
2091
2092        if (offset < 0)
2093                return offset;
2094
2095        prefix_patch(state, patch);
2096
2097        if (!use_patch(state, patch))
2098                patch->ws_rule = 0;
2099        else
2100                patch->ws_rule = whitespace_rule(patch->new_name
2101                                                 ? patch->new_name
2102                                                 : patch->old_name);
2103
2104        patchsize = parse_single_patch(state,
2105                                       buffer + offset + hdrsize,
2106                                       size - offset - hdrsize,
2107                                       patch);
2108
2109        if (!patchsize) {
2110                static const char git_binary[] = "GIT binary patch\n";
2111                int hd = hdrsize + offset;
2112                unsigned long llen = linelen(buffer + hd, size - hd);
2113
2114                if (llen == sizeof(git_binary) - 1 &&
2115                    !memcmp(git_binary, buffer + hd, llen)) {
2116                        int used;
2117                        state->linenr++;
2118                        used = parse_binary(state, buffer + hd + llen,
2119                                            size - hd - llen, patch);
2120                        if (used < 0)
2121                                return -1;
2122                        if (used)
2123                                patchsize = used + llen;
2124                        else
2125                                patchsize = 0;
2126                }
2127                else if (!memcmp(" differ\n", buffer + hd + llen - 8, 8)) {
2128                        static const char *binhdr[] = {
2129                                "Binary files ",
2130                                "Files ",
2131                                NULL,
2132                        };
2133                        int i;
2134                        for (i = 0; binhdr[i]; i++) {
2135                                int len = strlen(binhdr[i]);
2136                                if (len < size - hd &&
2137                                    !memcmp(binhdr[i], buffer + hd, len)) {
2138                                        state->linenr++;
2139                                        patch->is_binary = 1;
2140                                        patchsize = llen;
2141                                        break;
2142                                }
2143                        }
2144                }
2145
2146                /* Empty patch cannot be applied if it is a text patch
2147                 * without metadata change.  A binary patch appears
2148                 * empty to us here.
2149                 */
2150                if ((state->apply || state->check) &&
2151                    (!patch->is_binary && !metadata_changes(patch)))
2152                        die(_("patch with only garbage at line %d"), state->linenr);
2153        }
2154
2155        return offset + hdrsize + patchsize;
2156}
2157
2158#define swap(a,b) myswap((a),(b),sizeof(a))
2159
2160#define myswap(a, b, size) do {         \
2161        unsigned char mytmp[size];      \
2162        memcpy(mytmp, &a, size);                \
2163        memcpy(&a, &b, size);           \
2164        memcpy(&b, mytmp, size);                \
2165} while (0)
2166
2167static void reverse_patches(struct patch *p)
2168{
2169        for (; p; p = p->next) {
2170                struct fragment *frag = p->fragments;
2171
2172                swap(p->new_name, p->old_name);
2173                swap(p->new_mode, p->old_mode);
2174                swap(p->is_new, p->is_delete);
2175                swap(p->lines_added, p->lines_deleted);
2176                swap(p->old_sha1_prefix, p->new_sha1_prefix);
2177
2178                for (; frag; frag = frag->next) {
2179                        swap(frag->newpos, frag->oldpos);
2180                        swap(frag->newlines, frag->oldlines);
2181                }
2182        }
2183}
2184
2185static const char pluses[] =
2186"++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++";
2187static const char minuses[]=
2188"----------------------------------------------------------------------";
2189
2190static void show_stats(struct apply_state *state, struct patch *patch)
2191{
2192        struct strbuf qname = STRBUF_INIT;
2193        char *cp = patch->new_name ? patch->new_name : patch->old_name;
2194        int max, add, del;
2195
2196        quote_c_style(cp, &qname, NULL, 0);
2197
2198        /*
2199         * "scale" the filename
2200         */
2201        max = state->max_len;
2202        if (max > 50)
2203                max = 50;
2204
2205        if (qname.len > max) {
2206                cp = strchr(qname.buf + qname.len + 3 - max, '/');
2207                if (!cp)
2208                        cp = qname.buf + qname.len + 3 - max;
2209                strbuf_splice(&qname, 0, cp - qname.buf, "...", 3);
2210        }
2211
2212        if (patch->is_binary) {
2213                printf(" %-*s |  Bin\n", max, qname.buf);
2214                strbuf_release(&qname);
2215                return;
2216        }
2217
2218        printf(" %-*s |", max, qname.buf);
2219        strbuf_release(&qname);
2220
2221        /*
2222         * scale the add/delete
2223         */
2224        max = max + state->max_change > 70 ? 70 - max : state->max_change;
2225        add = patch->lines_added;
2226        del = patch->lines_deleted;
2227
2228        if (state->max_change > 0) {
2229                int total = ((add + del) * max + state->max_change / 2) / state->max_change;
2230                add = (add * max + state->max_change / 2) / state->max_change;
2231                del = total - add;
2232        }
2233        printf("%5d %.*s%.*s\n", patch->lines_added + patch->lines_deleted,
2234                add, pluses, del, minuses);
2235}
2236
2237static int read_old_data(struct stat *st, const char *path, struct strbuf *buf)
2238{
2239        switch (st->st_mode & S_IFMT) {
2240        case S_IFLNK:
2241                if (strbuf_readlink(buf, path, st->st_size) < 0)
2242                        return error(_("unable to read symlink %s"), path);
2243                return 0;
2244        case S_IFREG:
2245                if (strbuf_read_file(buf, path, st->st_size) != st->st_size)
2246                        return error(_("unable to open or read %s"), path);
2247                convert_to_git(path, buf->buf, buf->len, buf, 0);
2248                return 0;
2249        default:
2250                return -1;
2251        }
2252}
2253
2254/*
2255 * Update the preimage, and the common lines in postimage,
2256 * from buffer buf of length len. If postlen is 0 the postimage
2257 * is updated in place, otherwise it's updated on a new buffer
2258 * of length postlen
2259 */
2260
2261static void update_pre_post_images(struct image *preimage,
2262                                   struct image *postimage,
2263                                   char *buf,
2264                                   size_t len, size_t postlen)
2265{
2266        int i, ctx, reduced;
2267        char *new, *old, *fixed;
2268        struct image fixed_preimage;
2269
2270        /*
2271         * Update the preimage with whitespace fixes.  Note that we
2272         * are not losing preimage->buf -- apply_one_fragment() will
2273         * free "oldlines".
2274         */
2275        prepare_image(&fixed_preimage, buf, len, 1);
2276        assert(postlen
2277               ? fixed_preimage.nr == preimage->nr
2278               : fixed_preimage.nr <= preimage->nr);
2279        for (i = 0; i < fixed_preimage.nr; i++)
2280                fixed_preimage.line[i].flag = preimage->line[i].flag;
2281        free(preimage->line_allocated);
2282        *preimage = fixed_preimage;
2283
2284        /*
2285         * Adjust the common context lines in postimage. This can be
2286         * done in-place when we are shrinking it with whitespace
2287         * fixing, but needs a new buffer when ignoring whitespace or
2288         * expanding leading tabs to spaces.
2289         *
2290         * We trust the caller to tell us if the update can be done
2291         * in place (postlen==0) or not.
2292         */
2293        old = postimage->buf;
2294        if (postlen)
2295                new = postimage->buf = xmalloc(postlen);
2296        else
2297                new = old;
2298        fixed = preimage->buf;
2299
2300        for (i = reduced = ctx = 0; i < postimage->nr; i++) {
2301                size_t l_len = postimage->line[i].len;
2302                if (!(postimage->line[i].flag & LINE_COMMON)) {
2303                        /* an added line -- no counterparts in preimage */
2304                        memmove(new, old, l_len);
2305                        old += l_len;
2306                        new += l_len;
2307                        continue;
2308                }
2309
2310                /* a common context -- skip it in the original postimage */
2311                old += l_len;
2312
2313                /* and find the corresponding one in the fixed preimage */
2314                while (ctx < preimage->nr &&
2315                       !(preimage->line[ctx].flag & LINE_COMMON)) {
2316                        fixed += preimage->line[ctx].len;
2317                        ctx++;
2318                }
2319
2320                /*
2321                 * preimage is expected to run out, if the caller
2322                 * fixed addition of trailing blank lines.
2323                 */
2324                if (preimage->nr <= ctx) {
2325                        reduced++;
2326                        continue;
2327                }
2328
2329                /* and copy it in, while fixing the line length */
2330                l_len = preimage->line[ctx].len;
2331                memcpy(new, fixed, l_len);
2332                new += l_len;
2333                fixed += l_len;
2334                postimage->line[i].len = l_len;
2335                ctx++;
2336        }
2337
2338        if (postlen
2339            ? postlen < new - postimage->buf
2340            : postimage->len < new - postimage->buf)
2341                die("BUG: caller miscounted postlen: asked %d, orig = %d, used = %d",
2342                    (int)postlen, (int) postimage->len, (int)(new - postimage->buf));
2343
2344        /* Fix the length of the whole thing */
2345        postimage->len = new - postimage->buf;
2346        postimage->nr -= reduced;
2347}
2348
2349static int line_by_line_fuzzy_match(struct image *img,
2350                                    struct image *preimage,
2351                                    struct image *postimage,
2352                                    unsigned long try,
2353                                    int try_lno,
2354                                    int preimage_limit)
2355{
2356        int i;
2357        size_t imgoff = 0;
2358        size_t preoff = 0;
2359        size_t postlen = postimage->len;
2360        size_t extra_chars;
2361        char *buf;
2362        char *preimage_eof;
2363        char *preimage_end;
2364        struct strbuf fixed;
2365        char *fixed_buf;
2366        size_t fixed_len;
2367
2368        for (i = 0; i < preimage_limit; i++) {
2369                size_t prelen = preimage->line[i].len;
2370                size_t imglen = img->line[try_lno+i].len;
2371
2372                if (!fuzzy_matchlines(img->buf + try + imgoff, imglen,
2373                                      preimage->buf + preoff, prelen))
2374                        return 0;
2375                if (preimage->line[i].flag & LINE_COMMON)
2376                        postlen += imglen - prelen;
2377                imgoff += imglen;
2378                preoff += prelen;
2379        }
2380
2381        /*
2382         * Ok, the preimage matches with whitespace fuzz.
2383         *
2384         * imgoff now holds the true length of the target that
2385         * matches the preimage before the end of the file.
2386         *
2387         * Count the number of characters in the preimage that fall
2388         * beyond the end of the file and make sure that all of them
2389         * are whitespace characters. (This can only happen if
2390         * we are removing blank lines at the end of the file.)
2391         */
2392        buf = preimage_eof = preimage->buf + preoff;
2393        for ( ; i < preimage->nr; i++)
2394                preoff += preimage->line[i].len;
2395        preimage_end = preimage->buf + preoff;
2396        for ( ; buf < preimage_end; buf++)
2397                if (!isspace(*buf))
2398                        return 0;
2399
2400        /*
2401         * Update the preimage and the common postimage context
2402         * lines to use the same whitespace as the target.
2403         * If whitespace is missing in the target (i.e.
2404         * if the preimage extends beyond the end of the file),
2405         * use the whitespace from the preimage.
2406         */
2407        extra_chars = preimage_end - preimage_eof;
2408        strbuf_init(&fixed, imgoff + extra_chars);
2409        strbuf_add(&fixed, img->buf + try, imgoff);
2410        strbuf_add(&fixed, preimage_eof, extra_chars);
2411        fixed_buf = strbuf_detach(&fixed, &fixed_len);
2412        update_pre_post_images(preimage, postimage,
2413                               fixed_buf, fixed_len, postlen);
2414        return 1;
2415}
2416
2417static int match_fragment(struct apply_state *state,
2418                          struct image *img,
2419                          struct image *preimage,
2420                          struct image *postimage,
2421                          unsigned long try,
2422                          int try_lno,
2423                          unsigned ws_rule,
2424                          int match_beginning, int match_end)
2425{
2426        int i;
2427        char *fixed_buf, *buf, *orig, *target;
2428        struct strbuf fixed;
2429        size_t fixed_len, postlen;
2430        int preimage_limit;
2431
2432        if (preimage->nr + try_lno <= img->nr) {
2433                /*
2434                 * The hunk falls within the boundaries of img.
2435                 */
2436                preimage_limit = preimage->nr;
2437                if (match_end && (preimage->nr + try_lno != img->nr))
2438                        return 0;
2439        } else if (state->ws_error_action == correct_ws_error &&
2440                   (ws_rule & WS_BLANK_AT_EOF)) {
2441                /*
2442                 * This hunk extends beyond the end of img, and we are
2443                 * removing blank lines at the end of the file.  This
2444                 * many lines from the beginning of the preimage must
2445                 * match with img, and the remainder of the preimage
2446                 * must be blank.
2447                 */
2448                preimage_limit = img->nr - try_lno;
2449        } else {
2450                /*
2451                 * The hunk extends beyond the end of the img and
2452                 * we are not removing blanks at the end, so we
2453                 * should reject the hunk at this position.
2454                 */
2455                return 0;
2456        }
2457
2458        if (match_beginning && try_lno)
2459                return 0;
2460
2461        /* Quick hash check */
2462        for (i = 0; i < preimage_limit; i++)
2463                if ((img->line[try_lno + i].flag & LINE_PATCHED) ||
2464                    (preimage->line[i].hash != img->line[try_lno + i].hash))
2465                        return 0;
2466
2467        if (preimage_limit == preimage->nr) {
2468                /*
2469                 * Do we have an exact match?  If we were told to match
2470                 * at the end, size must be exactly at try+fragsize,
2471                 * otherwise try+fragsize must be still within the preimage,
2472                 * and either case, the old piece should match the preimage
2473                 * exactly.
2474                 */
2475                if ((match_end
2476                     ? (try + preimage->len == img->len)
2477                     : (try + preimage->len <= img->len)) &&
2478                    !memcmp(img->buf + try, preimage->buf, preimage->len))
2479                        return 1;
2480        } else {
2481                /*
2482                 * The preimage extends beyond the end of img, so
2483                 * there cannot be an exact match.
2484                 *
2485                 * There must be one non-blank context line that match
2486                 * a line before the end of img.
2487                 */
2488                char *buf_end;
2489
2490                buf = preimage->buf;
2491                buf_end = buf;
2492                for (i = 0; i < preimage_limit; i++)
2493                        buf_end += preimage->line[i].len;
2494
2495                for ( ; buf < buf_end; buf++)
2496                        if (!isspace(*buf))
2497                                break;
2498                if (buf == buf_end)
2499                        return 0;
2500        }
2501
2502        /*
2503         * No exact match. If we are ignoring whitespace, run a line-by-line
2504         * fuzzy matching. We collect all the line length information because
2505         * we need it to adjust whitespace if we match.
2506         */
2507        if (state->ws_ignore_action == ignore_ws_change)
2508                return line_by_line_fuzzy_match(img, preimage, postimage,
2509                                                try, try_lno, preimage_limit);
2510
2511        if (state->ws_error_action != correct_ws_error)
2512                return 0;
2513
2514        /*
2515         * The hunk does not apply byte-by-byte, but the hash says
2516         * it might with whitespace fuzz. We weren't asked to
2517         * ignore whitespace, we were asked to correct whitespace
2518         * errors, so let's try matching after whitespace correction.
2519         *
2520         * While checking the preimage against the target, whitespace
2521         * errors in both fixed, we count how large the corresponding
2522         * postimage needs to be.  The postimage prepared by
2523         * apply_one_fragment() has whitespace errors fixed on added
2524         * lines already, but the common lines were propagated as-is,
2525         * which may become longer when their whitespace errors are
2526         * fixed.
2527         */
2528
2529        /* First count added lines in postimage */
2530        postlen = 0;
2531        for (i = 0; i < postimage->nr; i++) {
2532                if (!(postimage->line[i].flag & LINE_COMMON))
2533                        postlen += postimage->line[i].len;
2534        }
2535
2536        /*
2537         * The preimage may extend beyond the end of the file,
2538         * but in this loop we will only handle the part of the
2539         * preimage that falls within the file.
2540         */
2541        strbuf_init(&fixed, preimage->len + 1);
2542        orig = preimage->buf;
2543        target = img->buf + try;
2544        for (i = 0; i < preimage_limit; i++) {
2545                size_t oldlen = preimage->line[i].len;
2546                size_t tgtlen = img->line[try_lno + i].len;
2547                size_t fixstart = fixed.len;
2548                struct strbuf tgtfix;
2549                int match;
2550
2551                /* Try fixing the line in the preimage */
2552                ws_fix_copy(&fixed, orig, oldlen, ws_rule, NULL);
2553
2554                /* Try fixing the line in the target */
2555                strbuf_init(&tgtfix, tgtlen);
2556                ws_fix_copy(&tgtfix, target, tgtlen, ws_rule, NULL);
2557
2558                /*
2559                 * If they match, either the preimage was based on
2560                 * a version before our tree fixed whitespace breakage,
2561                 * or we are lacking a whitespace-fix patch the tree
2562                 * the preimage was based on already had (i.e. target
2563                 * has whitespace breakage, the preimage doesn't).
2564                 * In either case, we are fixing the whitespace breakages
2565                 * so we might as well take the fix together with their
2566                 * real change.
2567                 */
2568                match = (tgtfix.len == fixed.len - fixstart &&
2569                         !memcmp(tgtfix.buf, fixed.buf + fixstart,
2570                                             fixed.len - fixstart));
2571
2572                /* Add the length if this is common with the postimage */
2573                if (preimage->line[i].flag & LINE_COMMON)
2574                        postlen += tgtfix.len;
2575
2576                strbuf_release(&tgtfix);
2577                if (!match)
2578                        goto unmatch_exit;
2579
2580                orig += oldlen;
2581                target += tgtlen;
2582        }
2583
2584
2585        /*
2586         * Now handle the lines in the preimage that falls beyond the
2587         * end of the file (if any). They will only match if they are
2588         * empty or only contain whitespace (if WS_BLANK_AT_EOL is
2589         * false).
2590         */
2591        for ( ; i < preimage->nr; i++) {
2592                size_t fixstart = fixed.len; /* start of the fixed preimage */
2593                size_t oldlen = preimage->line[i].len;
2594                int j;
2595
2596                /* Try fixing the line in the preimage */
2597                ws_fix_copy(&fixed, orig, oldlen, ws_rule, NULL);
2598
2599                for (j = fixstart; j < fixed.len; j++)
2600                        if (!isspace(fixed.buf[j]))
2601                                goto unmatch_exit;
2602
2603                orig += oldlen;
2604        }
2605
2606        /*
2607         * Yes, the preimage is based on an older version that still
2608         * has whitespace breakages unfixed, and fixing them makes the
2609         * hunk match.  Update the context lines in the postimage.
2610         */
2611        fixed_buf = strbuf_detach(&fixed, &fixed_len);
2612        if (postlen < postimage->len)
2613                postlen = 0;
2614        update_pre_post_images(preimage, postimage,
2615                               fixed_buf, fixed_len, postlen);
2616        return 1;
2617
2618 unmatch_exit:
2619        strbuf_release(&fixed);
2620        return 0;
2621}
2622
2623static int find_pos(struct apply_state *state,
2624                    struct image *img,
2625                    struct image *preimage,
2626                    struct image *postimage,
2627                    int line,
2628                    unsigned ws_rule,
2629                    int match_beginning, int match_end)
2630{
2631        int i;
2632        unsigned long backwards, forwards, try;
2633        int backwards_lno, forwards_lno, try_lno;
2634
2635        /*
2636         * If match_beginning or match_end is specified, there is no
2637         * point starting from a wrong line that will never match and
2638         * wander around and wait for a match at the specified end.
2639         */
2640        if (match_beginning)
2641                line = 0;
2642        else if (match_end)
2643                line = img->nr - preimage->nr;
2644
2645        /*
2646         * Because the comparison is unsigned, the following test
2647         * will also take care of a negative line number that can
2648         * result when match_end and preimage is larger than the target.
2649         */
2650        if ((size_t) line > img->nr)
2651                line = img->nr;
2652
2653        try = 0;
2654        for (i = 0; i < line; i++)
2655                try += img->line[i].len;
2656
2657        /*
2658         * There's probably some smart way to do this, but I'll leave
2659         * that to the smart and beautiful people. I'm simple and stupid.
2660         */
2661        backwards = try;
2662        backwards_lno = line;
2663        forwards = try;
2664        forwards_lno = line;
2665        try_lno = line;
2666
2667        for (i = 0; ; i++) {
2668                if (match_fragment(state, img, preimage, postimage,
2669                                   try, try_lno, ws_rule,
2670                                   match_beginning, match_end))
2671                        return try_lno;
2672
2673        again:
2674                if (backwards_lno == 0 && forwards_lno == img->nr)
2675                        break;
2676
2677                if (i & 1) {
2678                        if (backwards_lno == 0) {
2679                                i++;
2680                                goto again;
2681                        }
2682                        backwards_lno--;
2683                        backwards -= img->line[backwards_lno].len;
2684                        try = backwards;
2685                        try_lno = backwards_lno;
2686                } else {
2687                        if (forwards_lno == img->nr) {
2688                                i++;
2689                                goto again;
2690                        }
2691                        forwards += img->line[forwards_lno].len;
2692                        forwards_lno++;
2693                        try = forwards;
2694                        try_lno = forwards_lno;
2695                }
2696
2697        }
2698        return -1;
2699}
2700
2701static void remove_first_line(struct image *img)
2702{
2703        img->buf += img->line[0].len;
2704        img->len -= img->line[0].len;
2705        img->line++;
2706        img->nr--;
2707}
2708
2709static void remove_last_line(struct image *img)
2710{
2711        img->len -= img->line[--img->nr].len;
2712}
2713
2714/*
2715 * The change from "preimage" and "postimage" has been found to
2716 * apply at applied_pos (counts in line numbers) in "img".
2717 * Update "img" to remove "preimage" and replace it with "postimage".
2718 */
2719static void update_image(struct apply_state *state,
2720                         struct image *img,
2721                         int applied_pos,
2722                         struct image *preimage,
2723                         struct image *postimage)
2724{
2725        /*
2726         * remove the copy of preimage at offset in img
2727         * and replace it with postimage
2728         */
2729        int i, nr;
2730        size_t remove_count, insert_count, applied_at = 0;
2731        char *result;
2732        int preimage_limit;
2733
2734        /*
2735         * If we are removing blank lines at the end of img,
2736         * the preimage may extend beyond the end.
2737         * If that is the case, we must be careful only to
2738         * remove the part of the preimage that falls within
2739         * the boundaries of img. Initialize preimage_limit
2740         * to the number of lines in the preimage that falls
2741         * within the boundaries.
2742         */
2743        preimage_limit = preimage->nr;
2744        if (preimage_limit > img->nr - applied_pos)
2745                preimage_limit = img->nr - applied_pos;
2746
2747        for (i = 0; i < applied_pos; i++)
2748                applied_at += img->line[i].len;
2749
2750        remove_count = 0;
2751        for (i = 0; i < preimage_limit; i++)
2752                remove_count += img->line[applied_pos + i].len;
2753        insert_count = postimage->len;
2754
2755        /* Adjust the contents */
2756        result = xmalloc(st_add3(st_sub(img->len, remove_count), insert_count, 1));
2757        memcpy(result, img->buf, applied_at);
2758        memcpy(result + applied_at, postimage->buf, postimage->len);
2759        memcpy(result + applied_at + postimage->len,
2760               img->buf + (applied_at + remove_count),
2761               img->len - (applied_at + remove_count));
2762        free(img->buf);
2763        img->buf = result;
2764        img->len += insert_count - remove_count;
2765        result[img->len] = '\0';
2766
2767        /* Adjust the line table */
2768        nr = img->nr + postimage->nr - preimage_limit;
2769        if (preimage_limit < postimage->nr) {
2770                /*
2771                 * NOTE: this knows that we never call remove_first_line()
2772                 * on anything other than pre/post image.
2773                 */
2774                REALLOC_ARRAY(img->line, nr);
2775                img->line_allocated = img->line;
2776        }
2777        if (preimage_limit != postimage->nr)
2778                memmove(img->line + applied_pos + postimage->nr,
2779                        img->line + applied_pos + preimage_limit,
2780                        (img->nr - (applied_pos + preimage_limit)) *
2781                        sizeof(*img->line));
2782        memcpy(img->line + applied_pos,
2783               postimage->line,
2784               postimage->nr * sizeof(*img->line));
2785        if (!state->allow_overlap)
2786                for (i = 0; i < postimage->nr; i++)
2787                        img->line[applied_pos + i].flag |= LINE_PATCHED;
2788        img->nr = nr;
2789}
2790
2791/*
2792 * Use the patch-hunk text in "frag" to prepare two images (preimage and
2793 * postimage) for the hunk.  Find lines that match "preimage" in "img" and
2794 * replace the part of "img" with "postimage" text.
2795 */
2796static int apply_one_fragment(struct apply_state *state,
2797                              struct image *img, struct fragment *frag,
2798                              int inaccurate_eof, unsigned ws_rule,
2799                              int nth_fragment)
2800{
2801        int match_beginning, match_end;
2802        const char *patch = frag->patch;
2803        int size = frag->size;
2804        char *old, *oldlines;
2805        struct strbuf newlines;
2806        int new_blank_lines_at_end = 0;
2807        int found_new_blank_lines_at_end = 0;
2808        int hunk_linenr = frag->linenr;
2809        unsigned long leading, trailing;
2810        int pos, applied_pos;
2811        struct image preimage;
2812        struct image postimage;
2813
2814        memset(&preimage, 0, sizeof(preimage));
2815        memset(&postimage, 0, sizeof(postimage));
2816        oldlines = xmalloc(size);
2817        strbuf_init(&newlines, size);
2818
2819        old = oldlines;
2820        while (size > 0) {
2821                char first;
2822                int len = linelen(patch, size);
2823                int plen;
2824                int added_blank_line = 0;
2825                int is_blank_context = 0;
2826                size_t start;
2827
2828                if (!len)
2829                        break;
2830
2831                /*
2832                 * "plen" is how much of the line we should use for
2833                 * the actual patch data. Normally we just remove the
2834                 * first character on the line, but if the line is
2835                 * followed by "\ No newline", then we also remove the
2836                 * last one (which is the newline, of course).
2837                 */
2838                plen = len - 1;
2839                if (len < size && patch[len] == '\\')
2840                        plen--;
2841                first = *patch;
2842                if (state->apply_in_reverse) {
2843                        if (first == '-')
2844                                first = '+';
2845                        else if (first == '+')
2846                                first = '-';
2847                }
2848
2849                switch (first) {
2850                case '\n':
2851                        /* Newer GNU diff, empty context line */
2852                        if (plen < 0)
2853                                /* ... followed by '\No newline'; nothing */
2854                                break;
2855                        *old++ = '\n';
2856                        strbuf_addch(&newlines, '\n');
2857                        add_line_info(&preimage, "\n", 1, LINE_COMMON);
2858                        add_line_info(&postimage, "\n", 1, LINE_COMMON);
2859                        is_blank_context = 1;
2860                        break;
2861                case ' ':
2862                        if (plen && (ws_rule & WS_BLANK_AT_EOF) &&
2863                            ws_blank_line(patch + 1, plen, ws_rule))
2864                                is_blank_context = 1;
2865                case '-':
2866                        memcpy(old, patch + 1, plen);
2867                        add_line_info(&preimage, old, plen,
2868                                      (first == ' ' ? LINE_COMMON : 0));
2869                        old += plen;
2870                        if (first == '-')
2871                                break;
2872                /* Fall-through for ' ' */
2873                case '+':
2874                        /* --no-add does not add new lines */
2875                        if (first == '+' && state->no_add)
2876                                break;
2877
2878                        start = newlines.len;
2879                        if (first != '+' ||
2880                            !state->whitespace_error ||
2881                            state->ws_error_action != correct_ws_error) {
2882                                strbuf_add(&newlines, patch + 1, plen);
2883                        }
2884                        else {
2885                                ws_fix_copy(&newlines, patch + 1, plen, ws_rule, &state->applied_after_fixing_ws);
2886                        }
2887                        add_line_info(&postimage, newlines.buf + start, newlines.len - start,
2888                                      (first == '+' ? 0 : LINE_COMMON));
2889                        if (first == '+' &&
2890                            (ws_rule & WS_BLANK_AT_EOF) &&
2891                            ws_blank_line(patch + 1, plen, ws_rule))
2892                                added_blank_line = 1;
2893                        break;
2894                case '@': case '\\':
2895                        /* Ignore it, we already handled it */
2896                        break;
2897                default:
2898                        if (state->apply_verbosely)
2899                                error(_("invalid start of line: '%c'"), first);
2900                        applied_pos = -1;
2901                        goto out;
2902                }
2903                if (added_blank_line) {
2904                        if (!new_blank_lines_at_end)
2905                                found_new_blank_lines_at_end = hunk_linenr;
2906                        new_blank_lines_at_end++;
2907                }
2908                else if (is_blank_context)
2909                        ;
2910                else
2911                        new_blank_lines_at_end = 0;
2912                patch += len;
2913                size -= len;
2914                hunk_linenr++;
2915        }
2916        if (inaccurate_eof &&
2917            old > oldlines && old[-1] == '\n' &&
2918            newlines.len > 0 && newlines.buf[newlines.len - 1] == '\n') {
2919                old--;
2920                strbuf_setlen(&newlines, newlines.len - 1);
2921        }
2922
2923        leading = frag->leading;
2924        trailing = frag->trailing;
2925
2926        /*
2927         * A hunk to change lines at the beginning would begin with
2928         * @@ -1,L +N,M @@
2929         * but we need to be careful.  -U0 that inserts before the second
2930         * line also has this pattern.
2931         *
2932         * And a hunk to add to an empty file would begin with
2933         * @@ -0,0 +N,M @@
2934         *
2935         * In other words, a hunk that is (frag->oldpos <= 1) with or
2936         * without leading context must match at the beginning.
2937         */
2938        match_beginning = (!frag->oldpos ||
2939                           (frag->oldpos == 1 && !state->unidiff_zero));
2940
2941        /*
2942         * A hunk without trailing lines must match at the end.
2943         * However, we simply cannot tell if a hunk must match end
2944         * from the lack of trailing lines if the patch was generated
2945         * with unidiff without any context.
2946         */
2947        match_end = !state->unidiff_zero && !trailing;
2948
2949        pos = frag->newpos ? (frag->newpos - 1) : 0;
2950        preimage.buf = oldlines;
2951        preimage.len = old - oldlines;
2952        postimage.buf = newlines.buf;
2953        postimage.len = newlines.len;
2954        preimage.line = preimage.line_allocated;
2955        postimage.line = postimage.line_allocated;
2956
2957        for (;;) {
2958
2959                applied_pos = find_pos(state, img, &preimage, &postimage, pos,
2960                                       ws_rule, match_beginning, match_end);
2961
2962                if (applied_pos >= 0)
2963                        break;
2964
2965                /* Am I at my context limits? */
2966                if ((leading <= state->p_context) && (trailing <= state->p_context))
2967                        break;
2968                if (match_beginning || match_end) {
2969                        match_beginning = match_end = 0;
2970                        continue;
2971                }
2972
2973                /*
2974                 * Reduce the number of context lines; reduce both
2975                 * leading and trailing if they are equal otherwise
2976                 * just reduce the larger context.
2977                 */
2978                if (leading >= trailing) {
2979                        remove_first_line(&preimage);
2980                        remove_first_line(&postimage);
2981                        pos--;
2982                        leading--;
2983                }
2984                if (trailing > leading) {
2985                        remove_last_line(&preimage);
2986                        remove_last_line(&postimage);
2987                        trailing--;
2988                }
2989        }
2990
2991        if (applied_pos >= 0) {
2992                if (new_blank_lines_at_end &&
2993                    preimage.nr + applied_pos >= img->nr &&
2994                    (ws_rule & WS_BLANK_AT_EOF) &&
2995                    state->ws_error_action != nowarn_ws_error) {
2996                        record_ws_error(state, WS_BLANK_AT_EOF, "+", 1,
2997                                        found_new_blank_lines_at_end);
2998                        if (state->ws_error_action == correct_ws_error) {
2999                                while (new_blank_lines_at_end--)
3000                                        remove_last_line(&postimage);
3001                        }
3002                        /*
3003                         * We would want to prevent write_out_results()
3004                         * from taking place in apply_patch() that follows
3005                         * the callchain led us here, which is:
3006                         * apply_patch->check_patch_list->check_patch->
3007                         * apply_data->apply_fragments->apply_one_fragment
3008                         */
3009                        if (state->ws_error_action == die_on_ws_error)
3010                                state->apply = 0;
3011                }
3012
3013                if (state->apply_verbosely && applied_pos != pos) {
3014                        int offset = applied_pos - pos;
3015                        if (state->apply_in_reverse)
3016                                offset = 0 - offset;
3017                        fprintf_ln(stderr,
3018                                   Q_("Hunk #%d succeeded at %d (offset %d line).",
3019                                      "Hunk #%d succeeded at %d (offset %d lines).",
3020                                      offset),
3021                                   nth_fragment, applied_pos + 1, offset);
3022                }
3023
3024                /*
3025                 * Warn if it was necessary to reduce the number
3026                 * of context lines.
3027                 */
3028                if ((leading != frag->leading) ||
3029                    (trailing != frag->trailing))
3030                        fprintf_ln(stderr, _("Context reduced to (%ld/%ld)"
3031                                             " to apply fragment at %d"),
3032                                   leading, trailing, applied_pos+1);
3033                update_image(state, img, applied_pos, &preimage, &postimage);
3034        } else {
3035                if (state->apply_verbosely)
3036                        error(_("while searching for:\n%.*s"),
3037                              (int)(old - oldlines), oldlines);
3038        }
3039
3040out:
3041        free(oldlines);
3042        strbuf_release(&newlines);
3043        free(preimage.line_allocated);
3044        free(postimage.line_allocated);
3045
3046        return (applied_pos < 0);
3047}
3048
3049static int apply_binary_fragment(struct apply_state *state,
3050                                 struct image *img,
3051                                 struct patch *patch)
3052{
3053        struct fragment *fragment = patch->fragments;
3054        unsigned long len;
3055        void *dst;
3056
3057        if (!fragment)
3058                return error(_("missing binary patch data for '%s'"),
3059                             patch->new_name ?
3060                             patch->new_name :
3061                             patch->old_name);
3062
3063        /* Binary patch is irreversible without the optional second hunk */
3064        if (state->apply_in_reverse) {
3065                if (!fragment->next)
3066                        return error("cannot reverse-apply a binary patch "
3067                                     "without the reverse hunk to '%s'",
3068                                     patch->new_name
3069                                     ? patch->new_name : patch->old_name);
3070                fragment = fragment->next;
3071        }
3072        switch (fragment->binary_patch_method) {
3073        case BINARY_DELTA_DEFLATED:
3074                dst = patch_delta(img->buf, img->len, fragment->patch,
3075                                  fragment->size, &len);
3076                if (!dst)
3077                        return -1;
3078                clear_image(img);
3079                img->buf = dst;
3080                img->len = len;
3081                return 0;
3082        case BINARY_LITERAL_DEFLATED:
3083                clear_image(img);
3084                img->len = fragment->size;
3085                img->buf = xmemdupz(fragment->patch, img->len);
3086                return 0;
3087        }
3088        return -1;
3089}
3090
3091/*
3092 * Replace "img" with the result of applying the binary patch.
3093 * The binary patch data itself in patch->fragment is still kept
3094 * but the preimage prepared by the caller in "img" is freed here
3095 * or in the helper function apply_binary_fragment() this calls.
3096 */
3097static int apply_binary(struct apply_state *state,
3098                        struct image *img,
3099                        struct patch *patch)
3100{
3101        const char *name = patch->old_name ? patch->old_name : patch->new_name;
3102        unsigned char sha1[20];
3103
3104        /*
3105         * For safety, we require patch index line to contain
3106         * full 40-byte textual SHA1 for old and new, at least for now.
3107         */
3108        if (strlen(patch->old_sha1_prefix) != 40 ||
3109            strlen(patch->new_sha1_prefix) != 40 ||
3110            get_sha1_hex(patch->old_sha1_prefix, sha1) ||
3111            get_sha1_hex(patch->new_sha1_prefix, sha1))
3112                return error("cannot apply binary patch to '%s' "
3113                             "without full index line", name);
3114
3115        if (patch->old_name) {
3116                /*
3117                 * See if the old one matches what the patch
3118                 * applies to.
3119                 */
3120                hash_sha1_file(img->buf, img->len, blob_type, sha1);
3121                if (strcmp(sha1_to_hex(sha1), patch->old_sha1_prefix))
3122                        return error("the patch applies to '%s' (%s), "
3123                                     "which does not match the "
3124                                     "current contents.",
3125                                     name, sha1_to_hex(sha1));
3126        }
3127        else {
3128                /* Otherwise, the old one must be empty. */
3129                if (img->len)
3130                        return error("the patch applies to an empty "
3131                                     "'%s' but it is not empty", name);
3132        }
3133
3134        get_sha1_hex(patch->new_sha1_prefix, sha1);
3135        if (is_null_sha1(sha1)) {
3136                clear_image(img);
3137                return 0; /* deletion patch */
3138        }
3139
3140        if (has_sha1_file(sha1)) {
3141                /* We already have the postimage */
3142                enum object_type type;
3143                unsigned long size;
3144                char *result;
3145
3146                result = read_sha1_file(sha1, &type, &size);
3147                if (!result)
3148                        return error("the necessary postimage %s for "
3149                                     "'%s' cannot be read",
3150                                     patch->new_sha1_prefix, name);
3151                clear_image(img);
3152                img->buf = result;
3153                img->len = size;
3154        } else {
3155                /*
3156                 * We have verified buf matches the preimage;
3157                 * apply the patch data to it, which is stored
3158                 * in the patch->fragments->{patch,size}.
3159                 */
3160                if (apply_binary_fragment(state, img, patch))
3161                        return error(_("binary patch does not apply to '%s'"),
3162                                     name);
3163
3164                /* verify that the result matches */
3165                hash_sha1_file(img->buf, img->len, blob_type, sha1);
3166                if (strcmp(sha1_to_hex(sha1), patch->new_sha1_prefix))
3167                        return error(_("binary patch to '%s' creates incorrect result (expecting %s, got %s)"),
3168                                name, patch->new_sha1_prefix, sha1_to_hex(sha1));
3169        }
3170
3171        return 0;
3172}
3173
3174static int apply_fragments(struct apply_state *state, struct image *img, struct patch *patch)
3175{
3176        struct fragment *frag = patch->fragments;
3177        const char *name = patch->old_name ? patch->old_name : patch->new_name;
3178        unsigned ws_rule = patch->ws_rule;
3179        unsigned inaccurate_eof = patch->inaccurate_eof;
3180        int nth = 0;
3181
3182        if (patch->is_binary)
3183                return apply_binary(state, img, patch);
3184
3185        while (frag) {
3186                nth++;
3187                if (apply_one_fragment(state, img, frag, inaccurate_eof, ws_rule, nth)) {
3188                        error(_("patch failed: %s:%ld"), name, frag->oldpos);
3189                        if (!state->apply_with_reject)
3190                                return -1;
3191                        frag->rejected = 1;
3192                }
3193                frag = frag->next;
3194        }
3195        return 0;
3196}
3197
3198static int read_blob_object(struct strbuf *buf, const unsigned char *sha1, unsigned mode)
3199{
3200        if (S_ISGITLINK(mode)) {
3201                strbuf_grow(buf, 100);
3202                strbuf_addf(buf, "Subproject commit %s\n", sha1_to_hex(sha1));
3203        } else {
3204                enum object_type type;
3205                unsigned long sz;
3206                char *result;
3207
3208                result = read_sha1_file(sha1, &type, &sz);
3209                if (!result)
3210                        return -1;
3211                /* XXX read_sha1_file NUL-terminates */
3212                strbuf_attach(buf, result, sz, sz + 1);
3213        }
3214        return 0;
3215}
3216
3217static int read_file_or_gitlink(const struct cache_entry *ce, struct strbuf *buf)
3218{
3219        if (!ce)
3220                return 0;
3221        return read_blob_object(buf, ce->sha1, ce->ce_mode);
3222}
3223
3224static struct patch *in_fn_table(struct apply_state *state, const char *name)
3225{
3226        struct string_list_item *item;
3227
3228        if (name == NULL)
3229                return NULL;
3230
3231        item = string_list_lookup(&state->fn_table, name);
3232        if (item != NULL)
3233                return (struct patch *)item->util;
3234
3235        return NULL;
3236}
3237
3238/*
3239 * item->util in the filename table records the status of the path.
3240 * Usually it points at a patch (whose result records the contents
3241 * of it after applying it), but it could be PATH_WAS_DELETED for a
3242 * path that a previously applied patch has already removed, or
3243 * PATH_TO_BE_DELETED for a path that a later patch would remove.
3244 *
3245 * The latter is needed to deal with a case where two paths A and B
3246 * are swapped by first renaming A to B and then renaming B to A;
3247 * moving A to B should not be prevented due to presence of B as we
3248 * will remove it in a later patch.
3249 */
3250#define PATH_TO_BE_DELETED ((struct patch *) -2)
3251#define PATH_WAS_DELETED ((struct patch *) -1)
3252
3253static int to_be_deleted(struct patch *patch)
3254{
3255        return patch == PATH_TO_BE_DELETED;
3256}
3257
3258static int was_deleted(struct patch *patch)
3259{
3260        return patch == PATH_WAS_DELETED;
3261}
3262
3263static void add_to_fn_table(struct apply_state *state, struct patch *patch)
3264{
3265        struct string_list_item *item;
3266
3267        /*
3268         * Always add new_name unless patch is a deletion
3269         * This should cover the cases for normal diffs,
3270         * file creations and copies
3271         */
3272        if (patch->new_name != NULL) {
3273                item = string_list_insert(&state->fn_table, patch->new_name);
3274                item->util = patch;
3275        }
3276
3277        /*
3278         * store a failure on rename/deletion cases because
3279         * later chunks shouldn't patch old names
3280         */
3281        if ((patch->new_name == NULL) || (patch->is_rename)) {
3282                item = string_list_insert(&state->fn_table, patch->old_name);
3283                item->util = PATH_WAS_DELETED;
3284        }
3285}
3286
3287static void prepare_fn_table(struct apply_state *state, struct patch *patch)
3288{
3289        /*
3290         * store information about incoming file deletion
3291         */
3292        while (patch) {
3293                if ((patch->new_name == NULL) || (patch->is_rename)) {
3294                        struct string_list_item *item;
3295                        item = string_list_insert(&state->fn_table, patch->old_name);
3296                        item->util = PATH_TO_BE_DELETED;
3297                }
3298                patch = patch->next;
3299        }
3300}
3301
3302static int checkout_target(struct index_state *istate,
3303                           struct cache_entry *ce, struct stat *st)
3304{
3305        struct checkout costate;
3306
3307        memset(&costate, 0, sizeof(costate));
3308        costate.base_dir = "";
3309        costate.refresh_cache = 1;
3310        costate.istate = istate;
3311        if (checkout_entry(ce, &costate, NULL) || lstat(ce->name, st))
3312                return error(_("cannot checkout %s"), ce->name);
3313        return 0;
3314}
3315
3316static struct patch *previous_patch(struct apply_state *state,
3317                                    struct patch *patch,
3318                                    int *gone)
3319{
3320        struct patch *previous;
3321
3322        *gone = 0;
3323        if (patch->is_copy || patch->is_rename)
3324                return NULL; /* "git" patches do not depend on the order */
3325
3326        previous = in_fn_table(state, patch->old_name);
3327        if (!previous)
3328                return NULL;
3329
3330        if (to_be_deleted(previous))
3331                return NULL; /* the deletion hasn't happened yet */
3332
3333        if (was_deleted(previous))
3334                *gone = 1;
3335
3336        return previous;
3337}
3338
3339static int verify_index_match(const struct cache_entry *ce, struct stat *st)
3340{
3341        if (S_ISGITLINK(ce->ce_mode)) {
3342                if (!S_ISDIR(st->st_mode))
3343                        return -1;
3344                return 0;
3345        }
3346        return ce_match_stat(ce, st, CE_MATCH_IGNORE_VALID|CE_MATCH_IGNORE_SKIP_WORKTREE);
3347}
3348
3349#define SUBMODULE_PATCH_WITHOUT_INDEX 1
3350
3351static int load_patch_target(struct apply_state *state,
3352                             struct strbuf *buf,
3353                             const struct cache_entry *ce,
3354                             struct stat *st,
3355                             const char *name,
3356                             unsigned expected_mode)
3357{
3358        if (state->cached || state->check_index) {
3359                if (read_file_or_gitlink(ce, buf))
3360                        return error(_("read of %s failed"), name);
3361        } else if (name) {
3362                if (S_ISGITLINK(expected_mode)) {
3363                        if (ce)
3364                                return read_file_or_gitlink(ce, buf);
3365                        else
3366                                return SUBMODULE_PATCH_WITHOUT_INDEX;
3367                } else if (has_symlink_leading_path(name, strlen(name))) {
3368                        return error(_("reading from '%s' beyond a symbolic link"), name);
3369                } else {
3370                        if (read_old_data(st, name, buf))
3371                                return error(_("read of %s failed"), name);
3372                }
3373        }
3374        return 0;
3375}
3376
3377/*
3378 * We are about to apply "patch"; populate the "image" with the
3379 * current version we have, from the working tree or from the index,
3380 * depending on the situation e.g. --cached/--index.  If we are
3381 * applying a non-git patch that incrementally updates the tree,
3382 * we read from the result of a previous diff.
3383 */
3384static int load_preimage(struct apply_state *state,
3385                         struct image *image,
3386                         struct patch *patch, struct stat *st,
3387                         const struct cache_entry *ce)
3388{
3389        struct strbuf buf = STRBUF_INIT;
3390        size_t len;
3391        char *img;
3392        struct patch *previous;
3393        int status;
3394
3395        previous = previous_patch(state, patch, &status);
3396        if (status)
3397                return error(_("path %s has been renamed/deleted"),
3398                             patch->old_name);
3399        if (previous) {
3400                /* We have a patched copy in memory; use that. */
3401                strbuf_add(&buf, previous->result, previous->resultsize);
3402        } else {
3403                status = load_patch_target(state, &buf, ce, st,
3404                                           patch->old_name, patch->old_mode);
3405                if (status < 0)
3406                        return status;
3407                else if (status == SUBMODULE_PATCH_WITHOUT_INDEX) {
3408                        /*
3409                         * There is no way to apply subproject
3410                         * patch without looking at the index.
3411                         * NEEDSWORK: shouldn't this be flagged
3412                         * as an error???
3413                         */
3414                        free_fragment_list(patch->fragments);
3415                        patch->fragments = NULL;
3416                } else if (status) {
3417                        return error(_("read of %s failed"), patch->old_name);
3418                }
3419        }
3420
3421        img = strbuf_detach(&buf, &len);
3422        prepare_image(image, img, len, !patch->is_binary);
3423        return 0;
3424}
3425
3426static int three_way_merge(struct image *image,
3427                           char *path,
3428                           const unsigned char *base,
3429                           const unsigned char *ours,
3430                           const unsigned char *theirs)
3431{
3432        mmfile_t base_file, our_file, their_file;
3433        mmbuffer_t result = { NULL };
3434        int status;
3435
3436        read_mmblob(&base_file, base);
3437        read_mmblob(&our_file, ours);
3438        read_mmblob(&their_file, theirs);
3439        status = ll_merge(&result, path,
3440                          &base_file, "base",
3441                          &our_file, "ours",
3442                          &their_file, "theirs", NULL);
3443        free(base_file.ptr);
3444        free(our_file.ptr);
3445        free(their_file.ptr);
3446        if (status < 0 || !result.ptr) {
3447                free(result.ptr);
3448                return -1;
3449        }
3450        clear_image(image);
3451        image->buf = result.ptr;
3452        image->len = result.size;
3453
3454        return status;
3455}
3456
3457/*
3458 * When directly falling back to add/add three-way merge, we read from
3459 * the current contents of the new_name.  In no cases other than that
3460 * this function will be called.
3461 */
3462static int load_current(struct apply_state *state,
3463                        struct image *image,
3464                        struct patch *patch)
3465{
3466        struct strbuf buf = STRBUF_INIT;
3467        int status, pos;
3468        size_t len;
3469        char *img;
3470        struct stat st;
3471        struct cache_entry *ce;
3472        char *name = patch->new_name;
3473        unsigned mode = patch->new_mode;
3474
3475        if (!patch->is_new)
3476                die("BUG: patch to %s is not a creation", patch->old_name);
3477
3478        pos = cache_name_pos(name, strlen(name));
3479        if (pos < 0)
3480                return error(_("%s: does not exist in index"), name);
3481        ce = active_cache[pos];
3482        if (lstat(name, &st)) {
3483                if (errno != ENOENT)
3484                        return error(_("%s: %s"), name, strerror(errno));
3485                if (checkout_target(&the_index, ce, &st))
3486                        return -1;
3487        }
3488        if (verify_index_match(ce, &st))
3489                return error(_("%s: does not match index"), name);
3490
3491        status = load_patch_target(state, &buf, ce, &st, name, mode);
3492        if (status < 0)
3493                return status;
3494        else if (status)
3495                return -1;
3496        img = strbuf_detach(&buf, &len);
3497        prepare_image(image, img, len, !patch->is_binary);
3498        return 0;
3499}
3500
3501static int try_threeway(struct apply_state *state,
3502                        struct image *image,
3503                        struct patch *patch,
3504                        struct stat *st,
3505                        const struct cache_entry *ce)
3506{
3507        unsigned char pre_sha1[20], post_sha1[20], our_sha1[20];
3508        struct strbuf buf = STRBUF_INIT;
3509        size_t len;
3510        int status;
3511        char *img;
3512        struct image tmp_image;
3513
3514        /* No point falling back to 3-way merge in these cases */
3515        if (patch->is_delete ||
3516            S_ISGITLINK(patch->old_mode) || S_ISGITLINK(patch->new_mode))
3517                return -1;
3518
3519        /* Preimage the patch was prepared for */
3520        if (patch->is_new)
3521                write_sha1_file("", 0, blob_type, pre_sha1);
3522        else if (get_sha1(patch->old_sha1_prefix, pre_sha1) ||
3523                 read_blob_object(&buf, pre_sha1, patch->old_mode))
3524                return error("repository lacks the necessary blob to fall back on 3-way merge.");
3525
3526        fprintf(stderr, "Falling back to three-way merge...\n");
3527
3528        img = strbuf_detach(&buf, &len);
3529        prepare_image(&tmp_image, img, len, 1);
3530        /* Apply the patch to get the post image */
3531        if (apply_fragments(state, &tmp_image, patch) < 0) {
3532                clear_image(&tmp_image);
3533                return -1;
3534        }
3535        /* post_sha1[] is theirs */
3536        write_sha1_file(tmp_image.buf, tmp_image.len, blob_type, post_sha1);
3537        clear_image(&tmp_image);
3538
3539        /* our_sha1[] is ours */
3540        if (patch->is_new) {
3541                if (load_current(state, &tmp_image, patch))
3542                        return error("cannot read the current contents of '%s'",
3543                                     patch->new_name);
3544        } else {
3545                if (load_preimage(state, &tmp_image, patch, st, ce))
3546                        return error("cannot read the current contents of '%s'",
3547                                     patch->old_name);
3548        }
3549        write_sha1_file(tmp_image.buf, tmp_image.len, blob_type, our_sha1);
3550        clear_image(&tmp_image);
3551
3552        /* in-core three-way merge between post and our using pre as base */
3553        status = three_way_merge(image, patch->new_name,
3554                                 pre_sha1, our_sha1, post_sha1);
3555        if (status < 0) {
3556                fprintf(stderr, "Failed to fall back on three-way merge...\n");
3557                return status;
3558        }
3559
3560        if (status) {
3561                patch->conflicted_threeway = 1;
3562                if (patch->is_new)
3563                        oidclr(&patch->threeway_stage[0]);
3564                else
3565                        hashcpy(patch->threeway_stage[0].hash, pre_sha1);
3566                hashcpy(patch->threeway_stage[1].hash, our_sha1);
3567                hashcpy(patch->threeway_stage[2].hash, post_sha1);
3568                fprintf(stderr, "Applied patch to '%s' with conflicts.\n", patch->new_name);
3569        } else {
3570                fprintf(stderr, "Applied patch to '%s' cleanly.\n", patch->new_name);
3571        }
3572        return 0;
3573}
3574
3575static int apply_data(struct apply_state *state, struct patch *patch,
3576                      struct stat *st, const struct cache_entry *ce)
3577{
3578        struct image image;
3579
3580        if (load_preimage(state, &image, patch, st, ce) < 0)
3581                return -1;
3582
3583        if (patch->direct_to_threeway ||
3584            apply_fragments(state, &image, patch) < 0) {
3585                /* Note: with --reject, apply_fragments() returns 0 */
3586                if (!state->threeway || try_threeway(state, &image, patch, st, ce) < 0)
3587                        return -1;
3588        }
3589        patch->result = image.buf;
3590        patch->resultsize = image.len;
3591        add_to_fn_table(state, patch);
3592        free(image.line_allocated);
3593
3594        if (0 < patch->is_delete && patch->resultsize)
3595                return error(_("removal patch leaves file contents"));
3596
3597        return 0;
3598}
3599
3600/*
3601 * If "patch" that we are looking at modifies or deletes what we have,
3602 * we would want it not to lose any local modification we have, either
3603 * in the working tree or in the index.
3604 *
3605 * This also decides if a non-git patch is a creation patch or a
3606 * modification to an existing empty file.  We do not check the state
3607 * of the current tree for a creation patch in this function; the caller
3608 * check_patch() separately makes sure (and errors out otherwise) that
3609 * the path the patch creates does not exist in the current tree.
3610 */
3611static int check_preimage(struct apply_state *state,
3612                          struct patch *patch,
3613                          struct cache_entry **ce,
3614                          struct stat *st)
3615{
3616        const char *old_name = patch->old_name;
3617        struct patch *previous = NULL;
3618        int stat_ret = 0, status;
3619        unsigned st_mode = 0;
3620
3621        if (!old_name)
3622                return 0;
3623
3624        assert(patch->is_new <= 0);
3625        previous = previous_patch(state, patch, &status);
3626
3627        if (status)
3628                return error(_("path %s has been renamed/deleted"), old_name);
3629        if (previous) {
3630                st_mode = previous->new_mode;
3631        } else if (!state->cached) {
3632                stat_ret = lstat(old_name, st);
3633                if (stat_ret && errno != ENOENT)
3634                        return error(_("%s: %s"), old_name, strerror(errno));
3635        }
3636
3637        if (state->check_index && !previous) {
3638                int pos = cache_name_pos(old_name, strlen(old_name));
3639                if (pos < 0) {
3640                        if (patch->is_new < 0)
3641                                goto is_new;
3642                        return error(_("%s: does not exist in index"), old_name);
3643                }
3644                *ce = active_cache[pos];
3645                if (stat_ret < 0) {
3646                        if (checkout_target(&the_index, *ce, st))
3647                                return -1;
3648                }
3649                if (!state->cached && verify_index_match(*ce, st))
3650                        return error(_("%s: does not match index"), old_name);
3651                if (state->cached)
3652                        st_mode = (*ce)->ce_mode;
3653        } else if (stat_ret < 0) {
3654                if (patch->is_new < 0)
3655                        goto is_new;
3656                return error(_("%s: %s"), old_name, strerror(errno));
3657        }
3658
3659        if (!state->cached && !previous)
3660                st_mode = ce_mode_from_stat(*ce, st->st_mode);
3661
3662        if (patch->is_new < 0)
3663                patch->is_new = 0;
3664        if (!patch->old_mode)
3665                patch->old_mode = st_mode;
3666        if ((st_mode ^ patch->old_mode) & S_IFMT)
3667                return error(_("%s: wrong type"), old_name);
3668        if (st_mode != patch->old_mode)
3669                warning(_("%s has type %o, expected %o"),
3670                        old_name, st_mode, patch->old_mode);
3671        if (!patch->new_mode && !patch->is_delete)
3672                patch->new_mode = st_mode;
3673        return 0;
3674
3675 is_new:
3676        patch->is_new = 1;
3677        patch->is_delete = 0;
3678        free(patch->old_name);
3679        patch->old_name = NULL;
3680        return 0;
3681}
3682
3683
3684#define EXISTS_IN_INDEX 1
3685#define EXISTS_IN_WORKTREE 2
3686
3687static int check_to_create(struct apply_state *state,
3688                           const char *new_name,
3689                           int ok_if_exists)
3690{
3691        struct stat nst;
3692
3693        if (state->check_index &&
3694            cache_name_pos(new_name, strlen(new_name)) >= 0 &&
3695            !ok_if_exists)
3696                return EXISTS_IN_INDEX;
3697        if (state->cached)
3698                return 0;
3699
3700        if (!lstat(new_name, &nst)) {
3701                if (S_ISDIR(nst.st_mode) || ok_if_exists)
3702                        return 0;
3703                /*
3704                 * A leading component of new_name might be a symlink
3705                 * that is going to be removed with this patch, but
3706                 * still pointing at somewhere that has the path.
3707                 * In such a case, path "new_name" does not exist as
3708                 * far as git is concerned.
3709                 */
3710                if (has_symlink_leading_path(new_name, strlen(new_name)))
3711                        return 0;
3712
3713                return EXISTS_IN_WORKTREE;
3714        } else if ((errno != ENOENT) && (errno != ENOTDIR)) {
3715                return error("%s: %s", new_name, strerror(errno));
3716        }
3717        return 0;
3718}
3719
3720static uintptr_t register_symlink_changes(struct apply_state *state,
3721                                          const char *path,
3722                                          uintptr_t what)
3723{
3724        struct string_list_item *ent;
3725
3726        ent = string_list_lookup(&state->symlink_changes, path);
3727        if (!ent) {
3728                ent = string_list_insert(&state->symlink_changes, path);
3729                ent->util = (void *)0;
3730        }
3731        ent->util = (void *)(what | ((uintptr_t)ent->util));
3732        return (uintptr_t)ent->util;
3733}
3734
3735static uintptr_t check_symlink_changes(struct apply_state *state, const char *path)
3736{
3737        struct string_list_item *ent;
3738
3739        ent = string_list_lookup(&state->symlink_changes, path);
3740        if (!ent)
3741                return 0;
3742        return (uintptr_t)ent->util;
3743}
3744
3745static void prepare_symlink_changes(struct apply_state *state, struct patch *patch)
3746{
3747        for ( ; patch; patch = patch->next) {
3748                if ((patch->old_name && S_ISLNK(patch->old_mode)) &&
3749                    (patch->is_rename || patch->is_delete))
3750                        /* the symlink at patch->old_name is removed */
3751                        register_symlink_changes(state, patch->old_name, SYMLINK_GOES_AWAY);
3752
3753                if (patch->new_name && S_ISLNK(patch->new_mode))
3754                        /* the symlink at patch->new_name is created or remains */
3755                        register_symlink_changes(state, patch->new_name, SYMLINK_IN_RESULT);
3756        }
3757}
3758
3759static int path_is_beyond_symlink_1(struct apply_state *state, struct strbuf *name)
3760{
3761        do {
3762                unsigned int change;
3763
3764                while (--name->len && name->buf[name->len] != '/')
3765                        ; /* scan backwards */
3766                if (!name->len)
3767                        break;
3768                name->buf[name->len] = '\0';
3769                change = check_symlink_changes(state, name->buf);
3770                if (change & SYMLINK_IN_RESULT)
3771                        return 1;
3772                if (change & SYMLINK_GOES_AWAY)
3773                        /*
3774                         * This cannot be "return 0", because we may
3775                         * see a new one created at a higher level.
3776                         */
3777                        continue;
3778
3779                /* otherwise, check the preimage */
3780                if (state->check_index) {
3781                        struct cache_entry *ce;
3782
3783                        ce = cache_file_exists(name->buf, name->len, ignore_case);
3784                        if (ce && S_ISLNK(ce->ce_mode))
3785                                return 1;
3786                } else {
3787                        struct stat st;
3788                        if (!lstat(name->buf, &st) && S_ISLNK(st.st_mode))
3789                                return 1;
3790                }
3791        } while (1);
3792        return 0;
3793}
3794
3795static int path_is_beyond_symlink(struct apply_state *state, const char *name_)
3796{
3797        int ret;
3798        struct strbuf name = STRBUF_INIT;
3799
3800        assert(*name_ != '\0');
3801        strbuf_addstr(&name, name_);
3802        ret = path_is_beyond_symlink_1(state, &name);
3803        strbuf_release(&name);
3804
3805        return ret;
3806}
3807
3808static void die_on_unsafe_path(struct patch *patch)
3809{
3810        const char *old_name = NULL;
3811        const char *new_name = NULL;
3812        if (patch->is_delete)
3813                old_name = patch->old_name;
3814        else if (!patch->is_new && !patch->is_copy)
3815                old_name = patch->old_name;
3816        if (!patch->is_delete)
3817                new_name = patch->new_name;
3818
3819        if (old_name && !verify_path(old_name))
3820                die(_("invalid path '%s'"), old_name);
3821        if (new_name && !verify_path(new_name))
3822                die(_("invalid path '%s'"), new_name);
3823}
3824
3825/*
3826 * Check and apply the patch in-core; leave the result in patch->result
3827 * for the caller to write it out to the final destination.
3828 */
3829static int check_patch(struct apply_state *state, struct patch *patch)
3830{
3831        struct stat st;
3832        const char *old_name = patch->old_name;
3833        const char *new_name = patch->new_name;
3834        const char *name = old_name ? old_name : new_name;
3835        struct cache_entry *ce = NULL;
3836        struct patch *tpatch;
3837        int ok_if_exists;
3838        int status;
3839
3840        patch->rejected = 1; /* we will drop this after we succeed */
3841
3842        status = check_preimage(state, patch, &ce, &st);
3843        if (status)
3844                return status;
3845        old_name = patch->old_name;
3846
3847        /*
3848         * A type-change diff is always split into a patch to delete
3849         * old, immediately followed by a patch to create new (see
3850         * diff.c::run_diff()); in such a case it is Ok that the entry
3851         * to be deleted by the previous patch is still in the working
3852         * tree and in the index.
3853         *
3854         * A patch to swap-rename between A and B would first rename A
3855         * to B and then rename B to A.  While applying the first one,
3856         * the presence of B should not stop A from getting renamed to
3857         * B; ask to_be_deleted() about the later rename.  Removal of
3858         * B and rename from A to B is handled the same way by asking
3859         * was_deleted().
3860         */
3861        if ((tpatch = in_fn_table(state, new_name)) &&
3862            (was_deleted(tpatch) || to_be_deleted(tpatch)))
3863                ok_if_exists = 1;
3864        else
3865                ok_if_exists = 0;
3866
3867        if (new_name &&
3868            ((0 < patch->is_new) || patch->is_rename || patch->is_copy)) {
3869                int err = check_to_create(state, new_name, ok_if_exists);
3870
3871                if (err && state->threeway) {
3872                        patch->direct_to_threeway = 1;
3873                } else switch (err) {
3874                case 0:
3875                        break; /* happy */
3876                case EXISTS_IN_INDEX:
3877                        return error(_("%s: already exists in index"), new_name);
3878                        break;
3879                case EXISTS_IN_WORKTREE:
3880                        return error(_("%s: already exists in working directory"),
3881                                     new_name);
3882                default:
3883                        return err;
3884                }
3885
3886                if (!patch->new_mode) {
3887                        if (0 < patch->is_new)
3888                                patch->new_mode = S_IFREG | 0644;
3889                        else
3890                                patch->new_mode = patch->old_mode;
3891                }
3892        }
3893
3894        if (new_name && old_name) {
3895                int same = !strcmp(old_name, new_name);
3896                if (!patch->new_mode)
3897                        patch->new_mode = patch->old_mode;
3898                if ((patch->old_mode ^ patch->new_mode) & S_IFMT) {
3899                        if (same)
3900                                return error(_("new mode (%o) of %s does not "
3901                                               "match old mode (%o)"),
3902                                        patch->new_mode, new_name,
3903                                        patch->old_mode);
3904                        else
3905                                return error(_("new mode (%o) of %s does not "
3906                                               "match old mode (%o) of %s"),
3907                                        patch->new_mode, new_name,
3908                                        patch->old_mode, old_name);
3909                }
3910        }
3911
3912        if (!state->unsafe_paths)
3913                die_on_unsafe_path(patch);
3914
3915        /*
3916         * An attempt to read from or delete a path that is beyond a
3917         * symbolic link will be prevented by load_patch_target() that
3918         * is called at the beginning of apply_data() so we do not
3919         * have to worry about a patch marked with "is_delete" bit
3920         * here.  We however need to make sure that the patch result
3921         * is not deposited to a path that is beyond a symbolic link
3922         * here.
3923         */
3924        if (!patch->is_delete && path_is_beyond_symlink(state, patch->new_name))
3925                return error(_("affected file '%s' is beyond a symbolic link"),
3926                             patch->new_name);
3927
3928        if (apply_data(state, patch, &st, ce) < 0)
3929                return error(_("%s: patch does not apply"), name);
3930        patch->rejected = 0;
3931        return 0;
3932}
3933
3934static int check_patch_list(struct apply_state *state, struct patch *patch)
3935{
3936        int err = 0;
3937
3938        prepare_symlink_changes(state, patch);
3939        prepare_fn_table(state, patch);
3940        while (patch) {
3941                if (state->apply_verbosely)
3942                        say_patch_name(stderr,
3943                                       _("Checking patch %s..."), patch);
3944                err |= check_patch(state, patch);
3945                patch = patch->next;
3946        }
3947        return err;
3948}
3949
3950/* This function tries to read the sha1 from the current index */
3951static int get_current_sha1(const char *path, unsigned char *sha1)
3952{
3953        int pos;
3954
3955        if (read_cache() < 0)
3956                return -1;
3957        pos = cache_name_pos(path, strlen(path));
3958        if (pos < 0)
3959                return -1;
3960        hashcpy(sha1, active_cache[pos]->sha1);
3961        return 0;
3962}
3963
3964static int preimage_sha1_in_gitlink_patch(struct patch *p, unsigned char sha1[20])
3965{
3966        /*
3967         * A usable gitlink patch has only one fragment (hunk) that looks like:
3968         * @@ -1 +1 @@
3969         * -Subproject commit <old sha1>
3970         * +Subproject commit <new sha1>
3971         * or
3972         * @@ -1 +0,0 @@
3973         * -Subproject commit <old sha1>
3974         * for a removal patch.
3975         */
3976        struct fragment *hunk = p->fragments;
3977        static const char heading[] = "-Subproject commit ";
3978        char *preimage;
3979
3980        if (/* does the patch have only one hunk? */
3981            hunk && !hunk->next &&
3982            /* is its preimage one line? */
3983            hunk->oldpos == 1 && hunk->oldlines == 1 &&
3984            /* does preimage begin with the heading? */
3985            (preimage = memchr(hunk->patch, '\n', hunk->size)) != NULL &&
3986            starts_with(++preimage, heading) &&
3987            /* does it record full SHA-1? */
3988            !get_sha1_hex(preimage + sizeof(heading) - 1, sha1) &&
3989            preimage[sizeof(heading) + 40 - 1] == '\n' &&
3990            /* does the abbreviated name on the index line agree with it? */
3991            starts_with(preimage + sizeof(heading) - 1, p->old_sha1_prefix))
3992                return 0; /* it all looks fine */
3993
3994        /* we may have full object name on the index line */
3995        return get_sha1_hex(p->old_sha1_prefix, sha1);
3996}
3997
3998/* Build an index that contains the just the files needed for a 3way merge */
3999static void build_fake_ancestor(struct patch *list, const char *filename)
4000{
4001        struct patch *patch;
4002        struct index_state result = { NULL };
4003        static struct lock_file lock;
4004
4005        /* Once we start supporting the reverse patch, it may be
4006         * worth showing the new sha1 prefix, but until then...
4007         */
4008        for (patch = list; patch; patch = patch->next) {
4009                unsigned char sha1[20];
4010                struct cache_entry *ce;
4011                const char *name;
4012
4013                name = patch->old_name ? patch->old_name : patch->new_name;
4014                if (0 < patch->is_new)
4015                        continue;
4016
4017                if (S_ISGITLINK(patch->old_mode)) {
4018                        if (!preimage_sha1_in_gitlink_patch(patch, sha1))
4019                                ; /* ok, the textual part looks sane */
4020                        else
4021                                die("sha1 information is lacking or useless for submodule %s",
4022                                    name);
4023                } else if (!get_sha1_blob(patch->old_sha1_prefix, sha1)) {
4024                        ; /* ok */
4025                } else if (!patch->lines_added && !patch->lines_deleted) {
4026                        /* mode-only change: update the current */
4027                        if (get_current_sha1(patch->old_name, sha1))
4028                                die("mode change for %s, which is not "
4029                                    "in current HEAD", name);
4030                } else
4031                        die("sha1 information is lacking or useless "
4032                            "(%s).", name);
4033
4034                ce = make_cache_entry(patch->old_mode, sha1, name, 0, 0);
4035                if (!ce)
4036                        die(_("make_cache_entry failed for path '%s'"), name);
4037                if (add_index_entry(&result, ce, ADD_CACHE_OK_TO_ADD))
4038                        die ("Could not add %s to temporary index", name);
4039        }
4040
4041        hold_lock_file_for_update(&lock, filename, LOCK_DIE_ON_ERROR);
4042        if (write_locked_index(&result, &lock, COMMIT_LOCK))
4043                die ("Could not write temporary index to %s", filename);
4044
4045        discard_index(&result);
4046}
4047
4048static void stat_patch_list(struct apply_state *state, struct patch *patch)
4049{
4050        int files, adds, dels;
4051
4052        for (files = adds = dels = 0 ; patch ; patch = patch->next) {
4053                files++;
4054                adds += patch->lines_added;
4055                dels += patch->lines_deleted;
4056                show_stats(state, patch);
4057        }
4058
4059        print_stat_summary(stdout, files, adds, dels);
4060}
4061
4062static void numstat_patch_list(struct apply_state *state,
4063                               struct patch *patch)
4064{
4065        for ( ; patch; patch = patch->next) {
4066                const char *name;
4067                name = patch->new_name ? patch->new_name : patch->old_name;
4068                if (patch->is_binary)
4069                        printf("-\t-\t");
4070                else
4071                        printf("%d\t%d\t", patch->lines_added, patch->lines_deleted);
4072                write_name_quoted(name, stdout, state->line_termination);
4073        }
4074}
4075
4076static void show_file_mode_name(const char *newdelete, unsigned int mode, const char *name)
4077{
4078        if (mode)
4079                printf(" %s mode %06o %s\n", newdelete, mode, name);
4080        else
4081                printf(" %s %s\n", newdelete, name);
4082}
4083
4084static void show_mode_change(struct patch *p, int show_name)
4085{
4086        if (p->old_mode && p->new_mode && p->old_mode != p->new_mode) {
4087                if (show_name)
4088                        printf(" mode change %06o => %06o %s\n",
4089                               p->old_mode, p->new_mode, p->new_name);
4090                else
4091                        printf(" mode change %06o => %06o\n",
4092                               p->old_mode, p->new_mode);
4093        }
4094}
4095
4096static void show_rename_copy(struct patch *p)
4097{
4098        const char *renamecopy = p->is_rename ? "rename" : "copy";
4099        const char *old, *new;
4100
4101        /* Find common prefix */
4102        old = p->old_name;
4103        new = p->new_name;
4104        while (1) {
4105                const char *slash_old, *slash_new;
4106                slash_old = strchr(old, '/');
4107                slash_new = strchr(new, '/');
4108                if (!slash_old ||
4109                    !slash_new ||
4110                    slash_old - old != slash_new - new ||
4111                    memcmp(old, new, slash_new - new))
4112                        break;
4113                old = slash_old + 1;
4114                new = slash_new + 1;
4115        }
4116        /* p->old_name thru old is the common prefix, and old and new
4117         * through the end of names are renames
4118         */
4119        if (old != p->old_name)
4120                printf(" %s %.*s{%s => %s} (%d%%)\n", renamecopy,
4121                       (int)(old - p->old_name), p->old_name,
4122                       old, new, p->score);
4123        else
4124                printf(" %s %s => %s (%d%%)\n", renamecopy,
4125                       p->old_name, p->new_name, p->score);
4126        show_mode_change(p, 0);
4127}
4128
4129static void summary_patch_list(struct patch *patch)
4130{
4131        struct patch *p;
4132
4133        for (p = patch; p; p = p->next) {
4134                if (p->is_new)
4135                        show_file_mode_name("create", p->new_mode, p->new_name);
4136                else if (p->is_delete)
4137                        show_file_mode_name("delete", p->old_mode, p->old_name);
4138                else {
4139                        if (p->is_rename || p->is_copy)
4140                                show_rename_copy(p);
4141                        else {
4142                                if (p->score) {
4143                                        printf(" rewrite %s (%d%%)\n",
4144                                               p->new_name, p->score);
4145                                        show_mode_change(p, 0);
4146                                }
4147                                else
4148                                        show_mode_change(p, 1);
4149                        }
4150                }
4151        }
4152}
4153
4154static void patch_stats(struct apply_state *state, struct patch *patch)
4155{
4156        int lines = patch->lines_added + patch->lines_deleted;
4157
4158        if (lines > state->max_change)
4159                state->max_change = lines;
4160        if (patch->old_name) {
4161                int len = quote_c_style(patch->old_name, NULL, NULL, 0);
4162                if (!len)
4163                        len = strlen(patch->old_name);
4164                if (len > state->max_len)
4165                        state->max_len = len;
4166        }
4167        if (patch->new_name) {
4168                int len = quote_c_style(patch->new_name, NULL, NULL, 0);
4169                if (!len)
4170                        len = strlen(patch->new_name);
4171                if (len > state->max_len)
4172                        state->max_len = len;
4173        }
4174}
4175
4176static void remove_file(struct apply_state *state, struct patch *patch, int rmdir_empty)
4177{
4178        if (state->update_index) {
4179                if (remove_file_from_cache(patch->old_name) < 0)
4180                        die(_("unable to remove %s from index"), patch->old_name);
4181        }
4182        if (!state->cached) {
4183                if (!remove_or_warn(patch->old_mode, patch->old_name) && rmdir_empty) {
4184                        remove_path(patch->old_name);
4185                }
4186        }
4187}
4188
4189static void add_index_file(struct apply_state *state,
4190                           const char *path,
4191                           unsigned mode,
4192                           void *buf,
4193                           unsigned long size)
4194{
4195        struct stat st;
4196        struct cache_entry *ce;
4197        int namelen = strlen(path);
4198        unsigned ce_size = cache_entry_size(namelen);
4199
4200        if (!state->update_index)
4201                return;
4202
4203        ce = xcalloc(1, ce_size);
4204        memcpy(ce->name, path, namelen);
4205        ce->ce_mode = create_ce_mode(mode);
4206        ce->ce_flags = create_ce_flags(0);
4207        ce->ce_namelen = namelen;
4208        if (S_ISGITLINK(mode)) {
4209                const char *s;
4210
4211                if (!skip_prefix(buf, "Subproject commit ", &s) ||
4212                    get_sha1_hex(s, ce->sha1))
4213                        die(_("corrupt patch for submodule %s"), path);
4214        } else {
4215                if (!state->cached) {
4216                        if (lstat(path, &st) < 0)
4217                                die_errno(_("unable to stat newly created file '%s'"),
4218                                          path);
4219                        fill_stat_cache_info(ce, &st);
4220                }
4221                if (write_sha1_file(buf, size, blob_type, ce->sha1) < 0)
4222                        die(_("unable to create backing store for newly created file %s"), path);
4223        }
4224        if (add_cache_entry(ce, ADD_CACHE_OK_TO_ADD) < 0)
4225                die(_("unable to add cache entry for %s"), path);
4226}
4227
4228static int try_create_file(const char *path, unsigned int mode, const char *buf, unsigned long size)
4229{
4230        int fd;
4231        struct strbuf nbuf = STRBUF_INIT;
4232
4233        if (S_ISGITLINK(mode)) {
4234                struct stat st;
4235                if (!lstat(path, &st) && S_ISDIR(st.st_mode))
4236                        return 0;
4237                return mkdir(path, 0777);
4238        }
4239
4240        if (has_symlinks && S_ISLNK(mode))
4241                /* Although buf:size is counted string, it also is NUL
4242                 * terminated.
4243                 */
4244                return symlink(buf, path);
4245
4246        fd = open(path, O_CREAT | O_EXCL | O_WRONLY, (mode & 0100) ? 0777 : 0666);
4247        if (fd < 0)
4248                return -1;
4249
4250        if (convert_to_working_tree(path, buf, size, &nbuf)) {
4251                size = nbuf.len;
4252                buf  = nbuf.buf;
4253        }
4254        write_or_die(fd, buf, size);
4255        strbuf_release(&nbuf);
4256
4257        if (close(fd) < 0)
4258                die_errno(_("closing file '%s'"), path);
4259        return 0;
4260}
4261
4262/*
4263 * We optimistically assume that the directories exist,
4264 * which is true 99% of the time anyway. If they don't,
4265 * we create them and try again.
4266 */
4267static void create_one_file(struct apply_state *state,
4268                            char *path,
4269                            unsigned mode,
4270                            const char *buf,
4271                            unsigned long size)
4272{
4273        if (state->cached)
4274                return;
4275        if (!try_create_file(path, mode, buf, size))
4276                return;
4277
4278        if (errno == ENOENT) {
4279                if (safe_create_leading_directories(path))
4280                        return;
4281                if (!try_create_file(path, mode, buf, size))
4282                        return;
4283        }
4284
4285        if (errno == EEXIST || errno == EACCES) {
4286                /* We may be trying to create a file where a directory
4287                 * used to be.
4288                 */
4289                struct stat st;
4290                if (!lstat(path, &st) && (!S_ISDIR(st.st_mode) || !rmdir(path)))
4291                        errno = EEXIST;
4292        }
4293
4294        if (errno == EEXIST) {
4295                unsigned int nr = getpid();
4296
4297                for (;;) {
4298                        char newpath[PATH_MAX];
4299                        mksnpath(newpath, sizeof(newpath), "%s~%u", path, nr);
4300                        if (!try_create_file(newpath, mode, buf, size)) {
4301                                if (!rename(newpath, path))
4302                                        return;
4303                                unlink_or_warn(newpath);
4304                                break;
4305                        }
4306                        if (errno != EEXIST)
4307                                break;
4308                        ++nr;
4309                }
4310        }
4311        die_errno(_("unable to write file '%s' mode %o"), path, mode);
4312}
4313
4314static void add_conflicted_stages_file(struct apply_state *state,
4315                                       struct patch *patch)
4316{
4317        int stage, namelen;
4318        unsigned ce_size, mode;
4319        struct cache_entry *ce;
4320
4321        if (!state->update_index)
4322                return;
4323        namelen = strlen(patch->new_name);
4324        ce_size = cache_entry_size(namelen);
4325        mode = patch->new_mode ? patch->new_mode : (S_IFREG | 0644);
4326
4327        remove_file_from_cache(patch->new_name);
4328        for (stage = 1; stage < 4; stage++) {
4329                if (is_null_oid(&patch->threeway_stage[stage - 1]))
4330                        continue;
4331                ce = xcalloc(1, ce_size);
4332                memcpy(ce->name, patch->new_name, namelen);
4333                ce->ce_mode = create_ce_mode(mode);
4334                ce->ce_flags = create_ce_flags(stage);
4335                ce->ce_namelen = namelen;
4336                hashcpy(ce->sha1, patch->threeway_stage[stage - 1].hash);
4337                if (add_cache_entry(ce, ADD_CACHE_OK_TO_ADD) < 0)
4338                        die(_("unable to add cache entry for %s"), patch->new_name);
4339        }
4340}
4341
4342static void create_file(struct apply_state *state, struct patch *patch)
4343{
4344        char *path = patch->new_name;
4345        unsigned mode = patch->new_mode;
4346        unsigned long size = patch->resultsize;
4347        char *buf = patch->result;
4348
4349        if (!mode)
4350                mode = S_IFREG | 0644;
4351        create_one_file(state, path, mode, buf, size);
4352
4353        if (patch->conflicted_threeway)
4354                add_conflicted_stages_file(state, patch);
4355        else
4356                add_index_file(state, path, mode, buf, size);
4357}
4358
4359/* phase zero is to remove, phase one is to create */
4360static void write_out_one_result(struct apply_state *state,
4361                                 struct patch *patch,
4362                                 int phase)
4363{
4364        if (patch->is_delete > 0) {
4365                if (phase == 0)
4366                        remove_file(state, patch, 1);
4367                return;
4368        }
4369        if (patch->is_new > 0 || patch->is_copy) {
4370                if (phase == 1)
4371                        create_file(state, patch);
4372                return;
4373        }
4374        /*
4375         * Rename or modification boils down to the same
4376         * thing: remove the old, write the new
4377         */
4378        if (phase == 0)
4379                remove_file(state, patch, patch->is_rename);
4380        if (phase == 1)
4381                create_file(state, patch);
4382}
4383
4384static int write_out_one_reject(struct apply_state *state, struct patch *patch)
4385{
4386        FILE *rej;
4387        char namebuf[PATH_MAX];
4388        struct fragment *frag;
4389        int cnt = 0;
4390        struct strbuf sb = STRBUF_INIT;
4391
4392        for (cnt = 0, frag = patch->fragments; frag; frag = frag->next) {
4393                if (!frag->rejected)
4394                        continue;
4395                cnt++;
4396        }
4397
4398        if (!cnt) {
4399                if (state->apply_verbosely)
4400                        say_patch_name(stderr,
4401                                       _("Applied patch %s cleanly."), patch);
4402                return 0;
4403        }
4404
4405        /* This should not happen, because a removal patch that leaves
4406         * contents are marked "rejected" at the patch level.
4407         */
4408        if (!patch->new_name)
4409                die(_("internal error"));
4410
4411        /* Say this even without --verbose */
4412        strbuf_addf(&sb, Q_("Applying patch %%s with %d reject...",
4413                            "Applying patch %%s with %d rejects...",
4414                            cnt),
4415                    cnt);
4416        say_patch_name(stderr, sb.buf, patch);
4417        strbuf_release(&sb);
4418
4419        cnt = strlen(patch->new_name);
4420        if (ARRAY_SIZE(namebuf) <= cnt + 5) {
4421                cnt = ARRAY_SIZE(namebuf) - 5;
4422                warning(_("truncating .rej filename to %.*s.rej"),
4423                        cnt - 1, patch->new_name);
4424        }
4425        memcpy(namebuf, patch->new_name, cnt);
4426        memcpy(namebuf + cnt, ".rej", 5);
4427
4428        rej = fopen(namebuf, "w");
4429        if (!rej)
4430                return error(_("cannot open %s: %s"), namebuf, strerror(errno));
4431
4432        /* Normal git tools never deal with .rej, so do not pretend
4433         * this is a git patch by saying --git or giving extended
4434         * headers.  While at it, maybe please "kompare" that wants
4435         * the trailing TAB and some garbage at the end of line ;-).
4436         */
4437        fprintf(rej, "diff a/%s b/%s\t(rejected hunks)\n",
4438                patch->new_name, patch->new_name);
4439        for (cnt = 1, frag = patch->fragments;
4440             frag;
4441             cnt++, frag = frag->next) {
4442                if (!frag->rejected) {
4443                        fprintf_ln(stderr, _("Hunk #%d applied cleanly."), cnt);
4444                        continue;
4445                }
4446                fprintf_ln(stderr, _("Rejected hunk #%d."), cnt);
4447                fprintf(rej, "%.*s", frag->size, frag->patch);
4448                if (frag->patch[frag->size-1] != '\n')
4449                        fputc('\n', rej);
4450        }
4451        fclose(rej);
4452        return -1;
4453}
4454
4455static int write_out_results(struct apply_state *state, struct patch *list)
4456{
4457        int phase;
4458        int errs = 0;
4459        struct patch *l;
4460        struct string_list cpath = STRING_LIST_INIT_DUP;
4461
4462        for (phase = 0; phase < 2; phase++) {
4463                l = list;
4464                while (l) {
4465                        if (l->rejected)
4466                                errs = 1;
4467                        else {
4468                                write_out_one_result(state, l, phase);
4469                                if (phase == 1) {
4470                                        if (write_out_one_reject(state, l))
4471                                                errs = 1;
4472                                        if (l->conflicted_threeway) {
4473                                                string_list_append(&cpath, l->new_name);
4474                                                errs = 1;
4475                                        }
4476                                }
4477                        }
4478                        l = l->next;
4479                }
4480        }
4481
4482        if (cpath.nr) {
4483                struct string_list_item *item;
4484
4485                string_list_sort(&cpath);
4486                for_each_string_list_item(item, &cpath)
4487                        fprintf(stderr, "U %s\n", item->string);
4488                string_list_clear(&cpath, 0);
4489
4490                rerere(0);
4491        }
4492
4493        return errs;
4494}
4495
4496static struct lock_file lock_file;
4497
4498#define INACCURATE_EOF  (1<<0)
4499#define RECOUNT         (1<<1)
4500
4501static int apply_patch(struct apply_state *state,
4502                       int fd,
4503                       const char *filename,
4504                       int options)
4505{
4506        size_t offset;
4507        struct strbuf buf = STRBUF_INIT; /* owns the patch text */
4508        struct patch *list = NULL, **listp = &list;
4509        int skipped_patch = 0;
4510
4511        state->patch_input_file = filename;
4512        read_patch_file(&buf, fd);
4513        offset = 0;
4514        while (offset < buf.len) {
4515                struct patch *patch;
4516                int nr;
4517
4518                patch = xcalloc(1, sizeof(*patch));
4519                patch->inaccurate_eof = !!(options & INACCURATE_EOF);
4520                patch->recount =  !!(options & RECOUNT);
4521                nr = parse_chunk(state, buf.buf + offset, buf.len - offset, patch);
4522                if (nr < 0) {
4523                        free_patch(patch);
4524                        break;
4525                }
4526                if (state->apply_in_reverse)
4527                        reverse_patches(patch);
4528                if (use_patch(state, patch)) {
4529                        patch_stats(state, patch);
4530                        *listp = patch;
4531                        listp = &patch->next;
4532                }
4533                else {
4534                        if (state->apply_verbosely)
4535                                say_patch_name(stderr, _("Skipped patch '%s'."), patch);
4536                        free_patch(patch);
4537                        skipped_patch++;
4538                }
4539                offset += nr;
4540        }
4541
4542        if (!list && !skipped_patch)
4543                die(_("unrecognized input"));
4544
4545        if (state->whitespace_error && (state->ws_error_action == die_on_ws_error))
4546                state->apply = 0;
4547
4548        state->update_index = state->check_index && state->apply;
4549        if (state->update_index && newfd < 0)
4550                newfd = hold_locked_index(&lock_file, 1);
4551
4552        if (state->check_index) {
4553                if (read_cache() < 0)
4554                        die(_("unable to read index file"));
4555        }
4556
4557        if ((state->check || state->apply) &&
4558            check_patch_list(state, list) < 0 &&
4559            !state->apply_with_reject)
4560                exit(1);
4561
4562        if (state->apply && write_out_results(state, list)) {
4563                if (state->apply_with_reject)
4564                        exit(1);
4565                /* with --3way, we still need to write the index out */
4566                return 1;
4567        }
4568
4569        if (state->fake_ancestor)
4570                build_fake_ancestor(list, state->fake_ancestor);
4571
4572        if (state->diffstat)
4573                stat_patch_list(state, list);
4574
4575        if (state->numstat)
4576                numstat_patch_list(state, list);
4577
4578        if (state->summary)
4579                summary_patch_list(list);
4580
4581        free_patch_list(list);
4582        strbuf_release(&buf);
4583        string_list_clear(&state->fn_table, 0);
4584        return 0;
4585}
4586
4587static void git_apply_config(void)
4588{
4589        git_config_get_string_const("apply.whitespace", &apply_default_whitespace);
4590        git_config_get_string_const("apply.ignorewhitespace", &apply_default_ignorewhitespace);
4591        git_config(git_default_config, NULL);
4592}
4593
4594static int option_parse_exclude(const struct option *opt,
4595                                const char *arg, int unset)
4596{
4597        struct apply_state *state = opt->value;
4598        add_name_limit(state, arg, 1);
4599        return 0;
4600}
4601
4602static int option_parse_include(const struct option *opt,
4603                                const char *arg, int unset)
4604{
4605        struct apply_state *state = opt->value;
4606        add_name_limit(state, arg, 0);
4607        state->has_include = 1;
4608        return 0;
4609}
4610
4611static int option_parse_p(const struct option *opt,
4612                          const char *arg,
4613                          int unset)
4614{
4615        struct apply_state *state = opt->value;
4616        state->p_value = atoi(arg);
4617        state->p_value_known = 1;
4618        return 0;
4619}
4620
4621static int option_parse_space_change(const struct option *opt,
4622                                     const char *arg, int unset)
4623{
4624        struct apply_state *state = opt->value;
4625        if (unset)
4626                state->ws_ignore_action = ignore_ws_none;
4627        else
4628                state->ws_ignore_action = ignore_ws_change;
4629        return 0;
4630}
4631
4632static int option_parse_whitespace(const struct option *opt,
4633                                   const char *arg, int unset)
4634{
4635        struct apply_state *state = opt->value;
4636        state->whitespace_option = arg;
4637        parse_whitespace_option(state, arg);
4638        return 0;
4639}
4640
4641static int option_parse_directory(const struct option *opt,
4642                                  const char *arg, int unset)
4643{
4644        struct apply_state *state = opt->value;
4645        strbuf_reset(&state->root);
4646        strbuf_addstr(&state->root, arg);
4647        strbuf_complete(&state->root, '/');
4648        return 0;
4649}
4650
4651static void init_apply_state(struct apply_state *state, const char *prefix)
4652{
4653        memset(state, 0, sizeof(*state));
4654        state->prefix = prefix;
4655        state->prefix_length = state->prefix ? strlen(state->prefix) : 0;
4656        state->apply = 1;
4657        state->line_termination = '\n';
4658        state->p_value = 1;
4659        state->p_context = UINT_MAX;
4660        state->squelch_whitespace_errors = 5;
4661        state->ws_error_action = warn_on_ws_error;
4662        state->ws_ignore_action = ignore_ws_none;
4663        state->linenr = 1;
4664        strbuf_init(&state->root, 0);
4665
4666        git_apply_config();
4667        if (apply_default_whitespace)
4668                parse_whitespace_option(state, apply_default_whitespace);
4669        if (apply_default_ignorewhitespace)
4670                parse_ignorewhitespace_option(state, apply_default_ignorewhitespace);
4671}
4672
4673static void clear_apply_state(struct apply_state *state)
4674{
4675        string_list_clear(&state->limit_by_name, 0);
4676        string_list_clear(&state->symlink_changes, 0);
4677        strbuf_release(&state->root);
4678
4679        /* &state->fn_table is cleared at the end of apply_patch() */
4680}
4681
4682static void check_apply_state(struct apply_state *state, int force_apply)
4683{
4684        int is_not_gitdir = !startup_info->have_repository;
4685
4686        if (state->apply_with_reject && state->threeway)
4687                die("--reject and --3way cannot be used together.");
4688        if (state->cached && state->threeway)
4689                die("--cached and --3way cannot be used together.");
4690        if (state->threeway) {
4691                if (is_not_gitdir)
4692                        die(_("--3way outside a repository"));
4693                state->check_index = 1;
4694        }
4695        if (state->apply_with_reject)
4696                state->apply = state->apply_verbosely = 1;
4697        if (!force_apply && (state->diffstat || state->numstat || state->summary || state->check || state->fake_ancestor))
4698                state->apply = 0;
4699        if (state->check_index && is_not_gitdir)
4700                die(_("--index outside a repository"));
4701        if (state->cached) {
4702                if (is_not_gitdir)
4703                        die(_("--cached outside a repository"));
4704                state->check_index = 1;
4705        }
4706        if (state->check_index)
4707                state->unsafe_paths = 0;
4708}
4709
4710int cmd_apply(int argc, const char **argv, const char *prefix)
4711{
4712        int i;
4713        int errs = 0;
4714        int force_apply = 0;
4715        int options = 0;
4716        int read_stdin = 1;
4717        struct apply_state state;
4718
4719        struct option builtin_apply_options[] = {
4720                { OPTION_CALLBACK, 0, "exclude", &state, N_("path"),
4721                        N_("don't apply changes matching the given path"),
4722                        0, option_parse_exclude },
4723                { OPTION_CALLBACK, 0, "include", &state, N_("path"),
4724                        N_("apply changes matching the given path"),
4725                        0, option_parse_include },
4726                { OPTION_CALLBACK, 'p', NULL, &state, N_("num"),
4727                        N_("remove <num> leading slashes from traditional diff paths"),
4728                        0, option_parse_p },
4729                OPT_BOOL(0, "no-add", &state.no_add,
4730                        N_("ignore additions made by the patch")),
4731                OPT_BOOL(0, "stat", &state.diffstat,
4732                        N_("instead of applying the patch, output diffstat for the input")),
4733                OPT_NOOP_NOARG(0, "allow-binary-replacement"),
4734                OPT_NOOP_NOARG(0, "binary"),
4735                OPT_BOOL(0, "numstat", &state.numstat,
4736                        N_("show number of added and deleted lines in decimal notation")),
4737                OPT_BOOL(0, "summary", &state.summary,
4738                        N_("instead of applying the patch, output a summary for the input")),
4739                OPT_BOOL(0, "check", &state.check,
4740                        N_("instead of applying the patch, see if the patch is applicable")),
4741                OPT_BOOL(0, "index", &state.check_index,
4742                        N_("make sure the patch is applicable to the current index")),
4743                OPT_BOOL(0, "cached", &state.cached,
4744                        N_("apply a patch without touching the working tree")),
4745                OPT_BOOL(0, "unsafe-paths", &state.unsafe_paths,
4746                        N_("accept a patch that touches outside the working area")),
4747                OPT_BOOL(0, "apply", &force_apply,
4748                        N_("also apply the patch (use with --stat/--summary/--check)")),
4749                OPT_BOOL('3', "3way", &state.threeway,
4750                         N_( "attempt three-way merge if a patch does not apply")),
4751                OPT_FILENAME(0, "build-fake-ancestor", &state.fake_ancestor,
4752                        N_("build a temporary index based on embedded index information")),
4753                /* Think twice before adding "--nul" synonym to this */
4754                OPT_SET_INT('z', NULL, &state.line_termination,
4755                        N_("paths are separated with NUL character"), '\0'),
4756                OPT_INTEGER('C', NULL, &state.p_context,
4757                                N_("ensure at least <n> lines of context match")),
4758                { OPTION_CALLBACK, 0, "whitespace", &state, N_("action"),
4759                        N_("detect new or modified lines that have whitespace errors"),
4760                        0, option_parse_whitespace },
4761                { OPTION_CALLBACK, 0, "ignore-space-change", &state, NULL,
4762                        N_("ignore changes in whitespace when finding context"),
4763                        PARSE_OPT_NOARG, option_parse_space_change },
4764                { OPTION_CALLBACK, 0, "ignore-whitespace", &state, NULL,
4765                        N_("ignore changes in whitespace when finding context"),
4766                        PARSE_OPT_NOARG, option_parse_space_change },
4767                OPT_BOOL('R', "reverse", &state.apply_in_reverse,
4768                        N_("apply the patch in reverse")),
4769                OPT_BOOL(0, "unidiff-zero", &state.unidiff_zero,
4770                        N_("don't expect at least one line of context")),
4771                OPT_BOOL(0, "reject", &state.apply_with_reject,
4772                        N_("leave the rejected hunks in corresponding *.rej files")),
4773                OPT_BOOL(0, "allow-overlap", &state.allow_overlap,
4774                        N_("allow overlapping hunks")),
4775                OPT__VERBOSE(&state.apply_verbosely, N_("be verbose")),
4776                OPT_BIT(0, "inaccurate-eof", &options,
4777                        N_("tolerate incorrectly detected missing new-line at the end of file"),
4778                        INACCURATE_EOF),
4779                OPT_BIT(0, "recount", &options,
4780                        N_("do not trust the line counts in the hunk headers"),
4781                        RECOUNT),
4782                { OPTION_CALLBACK, 0, "directory", &state, N_("root"),
4783                        N_("prepend <root> to all filenames"),
4784                        0, option_parse_directory },
4785                OPT_END()
4786        };
4787
4788        init_apply_state(&state, prefix);
4789
4790        argc = parse_options(argc, argv, state.prefix, builtin_apply_options,
4791                        apply_usage, 0);
4792
4793        check_apply_state(&state, force_apply);
4794
4795        for (i = 0; i < argc; i++) {
4796                const char *arg = argv[i];
4797                int fd;
4798
4799                if (!strcmp(arg, "-")) {
4800                        errs |= apply_patch(&state, 0, "<stdin>", options);
4801                        read_stdin = 0;
4802                        continue;
4803                } else if (0 < state.prefix_length)
4804                        arg = prefix_filename(state.prefix,
4805                                              state.prefix_length,
4806                                              arg);
4807
4808                fd = open(arg, O_RDONLY);
4809                if (fd < 0)
4810                        die_errno(_("can't open patch '%s'"), arg);
4811                read_stdin = 0;
4812                set_default_whitespace_mode(&state);
4813                errs |= apply_patch(&state, fd, arg, options);
4814                close(fd);
4815        }
4816        set_default_whitespace_mode(&state);
4817        if (read_stdin)
4818                errs |= apply_patch(&state, 0, "<stdin>", options);
4819        if (state.whitespace_error) {
4820                if (state.squelch_whitespace_errors &&
4821                    state.squelch_whitespace_errors < state.whitespace_error) {
4822                        int squelched =
4823                                state.whitespace_error - state.squelch_whitespace_errors;
4824                        warning(Q_("squelched %d whitespace error",
4825                                   "squelched %d whitespace errors",
4826                                   squelched),
4827                                squelched);
4828                }
4829                if (state.ws_error_action == die_on_ws_error)
4830                        die(Q_("%d line adds whitespace errors.",
4831                               "%d lines add whitespace errors.",
4832                               state.whitespace_error),
4833                            state.whitespace_error);
4834                if (state.applied_after_fixing_ws && state.apply)
4835                        warning("%d line%s applied after"
4836                                " fixing whitespace errors.",
4837                                state.applied_after_fixing_ws,
4838                                state.applied_after_fixing_ws == 1 ? "" : "s");
4839                else if (state.whitespace_error)
4840                        warning(Q_("%d line adds whitespace errors.",
4841                                   "%d lines add whitespace errors.",
4842                                   state.whitespace_error),
4843                                state.whitespace_error);
4844        }
4845
4846        if (state.update_index) {
4847                if (write_locked_index(&the_index, &lock_file, COMMIT_LOCK))
4848                        die(_("Unable to write new index file"));
4849        }
4850
4851        clear_apply_state(&state);
4852
4853        return !!errs;
4854}