editors/patch.c

   1 /* vi: set sw=4 ts=4:
   2  *
   3  * Apply a "universal" diff.
   4  * Adapted from toybox's patch implementation.
   5  *
   6  * Copyright 2007 Rob Landley <rob@landley.net>
   7  *
   8  * see http://www.opengroup.org/onlinepubs/009695399/utilities/patch.html
   9  * (But only does -u, because who still cares about "ed"?)
  10  *
  11  * TODO:
  12  * -b backup
  13  * -l treat all whitespace as a single space
  14  * -d chdir first
  15  * -D define wrap #ifdef and #ifndef around changes
  16  * -o outfile output here instead of in place
  17  * -r rejectfile write rejected hunks to this file
  18  *
  19  * -f force (no questions asked)
  20  * -F fuzz (number, default 2)
  21  * [file] which file to patch
  22  */
  23 //config:config PATCH
  24 //config:       bool "patch (9.4 kb)"
  25 //config:       default y
  26 //config:       help
  27 //config:       Apply a unified diff formatted patch.
  28
  29 //applet:IF_PATCH(APPLET(patch, BB_DIR_USR_BIN, BB_SUID_DROP))
  30
  31 //kbuild:lib-$(CONFIG_PATCH) += patch.o
  32
  33 //usage:#define patch_trivial_usage
  34 //usage:       "[OPTIONS] [ORIGFILE [PATCHFILE]]"
  35 //usage:#define patch_full_usage "\n\n"
  36 //usage:       "        -p N    Strip N leading components from file names"
  37 //usage:     "\n        -i DIFF Read DIFF instead of stdin"
  38 //usage:     "\n        -R      Reverse patch"
  39 //usage:     "\n        -N      Ignore already applied patches"
  40 //usage:     "\n        -E      Remove output files if they become empty"
  41 //usage:        IF_LONG_OPTS(
  42 //usage:     "\n        --dry-run       Don't actually change files"
  43 //usage:        )
  44 /* -u "interpret as unified diff" is supported but not documented: this info is not useful for --help */
  45 //usage:
  46 //usage:#define patch_example_usage
  47 //usage:       "$ patch -p1 < example.diff\n"
  48 //usage:       "$ patch -p0 -i example.diff"
  49
  50 #include "libbb.h"
  51
  52 #define PATCH_DEBUG  0
  53
  54 // libbb candidate?
  55
  56 struct double_list {
  57         struct double_list *next;
  58         struct double_list *prev;
  59         char *data;
  60 };
  61
  62 // Free all the elements of a linked list
  63 // Call freeit() on each element before freeing it.
  64 static void dlist_free(struct double_list *list, void (*freeit)(void *data))
  65 {
  66         while (list) {
  67                 void *pop = list;
  68                 list = list->next;
  69                 freeit(pop);
  70                 // Bail out also if list is circular.
  71                 if (list == pop) break;
  72         }
  73 }
  74
  75 // Add an entry before "list" element in (circular) doubly linked list
  76 static struct double_list *dlist_add(struct double_list **list, char *data)
  77 {
  78         struct double_list *llist;
  79         struct double_list *line = xmalloc(sizeof(*line));
  80
  81         line->data = data;
  82         llist = *list;
  83         if (llist) {
  84                 struct double_list *p;
  85                 line->next = llist;
  86                 p = line->prev = llist->prev;
  87                 // (list is circular, we assume p is never NULL)
  88                 p->next = line;
  89                 llist->prev = line;
  90         } else
  91                 *list = line->next = line->prev = line;
  92
  93         return line;
  94 }
  95
  96
  97 struct globals {
  98         char *infile;
  99         long prefix;
 100
 101         struct double_list *current_hunk;
 102
 103         long oldline, oldlen, newline, newlen;
 104         long linenum;
 105         int context, state, hunknum;
 106         int filein, fileout;
 107         char *tempname;
 108
 109         int exitval;
 110 };
 111 #define TT (*ptr_to_globals)
 112 #define INIT_TT() do { \
 113         SET_PTR_TO_GLOBALS(xzalloc(sizeof(TT))); \
 114 } while (0)
 115
 116
 117 #define FLAG_STR "Rup:i:NEfg"
 118 /* FLAG_REVERSE must be == 1! Code uses this fact. */
 119 #define FLAG_REVERSE  (1 << 0)
 120 #define FLAG_u        (1 << 1)
 121 #define FLAG_PATHLEN  (1 << 2)
 122 #define FLAG_INPUT    (1 << 3)
 123 #define FLAG_IGNORE   (1 << 4)
 124 #define FLAG_RMEMPTY  (1 << 5)
 125 #define FLAG_f_unused (1 << 6)
 126 #define FLAG_g_unused (1 << 7)
 127 #define FLAG_dry_run  ((1 << 8) * ENABLE_LONG_OPTS)
 128
 129
 130 // Dispose of a line of input, either by writing it out or discarding it.
 131
 132 // state < 2: just free
 133 // state = 2: write whole line to stderr
 134 // state = 3: write whole line to fileout
 135 // state > 3: write line+1 to fileout when *line != state
 136
 137 static void do_line(void *data)
 138 {
 139         struct double_list *dlist = data;
 140
 141         if (TT.state>1 && *dlist->data != TT.state)
 142                 fdprintf(TT.state == 2 ? 2 : TT.fileout,
 143                         "%s\n", dlist->data+(TT.state>3 ? 1 : 0));
 144
 145         if (PATCH_DEBUG) fdprintf(2, "DO %d: %s\n", TT.state, dlist->data);
 146
 147         free(dlist->data);
 148         free(dlist);
 149 }
 150
 151 static void finish_oldfile(void)
 152 {
 153         if (TT.tempname) {
 154                 // Copy the rest of the data and replace the original with the copy.
 155                 char *temp;
 156
 157                 if (TT.filein != -1) {
 158                         bb_copyfd_eof(TT.filein, TT.fileout);
 159                         xclose(TT.filein);
 160                 }
 161                 xclose(TT.fileout);
 162
 163                 if (!ENABLE_LONG_OPTS || TT.tempname[0]) { /* not --dry-run? */
 164                         temp = xstrdup(TT.tempname);
 165                         temp[strlen(temp) - 6] = '\0';
 166                         rename(TT.tempname, temp);
 167                         free(temp);
 168                         free(TT.tempname);
 169                 }
 170
 171                 TT.tempname = NULL;
 172         }
 173         TT.fileout = TT.filein = -1;
 174 }
 175
 176 static void fail_hunk(void)
 177 {
 178         if (!TT.current_hunk) return;
 179
 180         fdprintf(2, "Hunk %d FAILED %ld/%ld.\n", TT.hunknum, TT.oldline, TT.newline);
 181         TT.exitval = 1;
 182
 183         // If we got to this point, we've seeked to the end.  Discard changes to
 184         // this file and advance to next file.
 185
 186         TT.state = 2;
 187         TT.current_hunk->prev->next = NULL;
 188         dlist_free(TT.current_hunk, do_line);
 189         TT.current_hunk = NULL;
 190
 191         // Abort the copy and delete the temporary file.
 192         close(TT.filein);
 193         close(TT.fileout);
 194         if (!ENABLE_LONG_OPTS || TT.tempname[0]) { /* not --dry-run? */
 195                 unlink(TT.tempname);
 196                 free(TT.tempname);
 197         }
 198         TT.tempname = NULL;
 199
 200         TT.state = 0;
 201 }
 202
 203 // Given a hunk of a unified diff, make the appropriate change to the file.
 204 // This does not use the location information, but instead treats a hunk
 205 // as a sort of regex.  Copies data from input to output until it finds
 206 // the change to be made, then outputs the changed data and returns.
 207 // (Finding EOF first is an error.)  This is a single pass operation, so
 208 // multiple hunks must occur in order in the file.
 209
 210 static int apply_one_hunk(void)
 211 {
 212         struct double_list *plist, *buf = NULL, *check;
 213         int matcheof = 0, reverse = option_mask32 & FLAG_REVERSE, backwarn = 0;
 214         /* Do we try "dummy" revert to check whether
 215          * to silently skip this hunk? Used to implement -N.
 216          */
 217         int dummy_revert = 0;
 218
 219         // Break doubly linked list so we can use singly linked traversal function.
 220         TT.current_hunk->prev->next = NULL;
 221
 222         // Match EOF if there aren't as many ending context lines as beginning
 223         for (plist = TT.current_hunk; plist; plist = plist->next) {
 224                 if (plist->data[0]==' ') matcheof++;
 225                 else matcheof = 0;
 226                 if (PATCH_DEBUG) fdprintf(2, "HUNK:%s\n", plist->data);
 227         }
 228         matcheof = !matcheof || matcheof < TT.context;
 229
 230         if (PATCH_DEBUG) fdprintf(2,"MATCHEOF=%c\n", matcheof ? 'Y' : 'N');
 231
 232         // Loop through input data searching for this hunk.  Match all context
 233         // lines and all lines to be removed until we've found the end of a
 234         // complete hunk.
 235         plist = TT.current_hunk;
 236         buf = NULL;
 237         if (reverse ? TT.oldlen : TT.newlen) for (;;) {
 238 //FIXME: this performs 1-byte reads:
 239                 char *data = xmalloc_reads(TT.filein, NULL);
 240
 241                 TT.linenum++;
 242
 243                 // Figure out which line of hunk to compare with next.  (Skip lines
 244                 // of the hunk we'd be adding.)
 245                 while (plist && *plist->data == "+-"[reverse]) {
 246                         if (data && strcmp(data, plist->data+1) == 0) {
 247                                 if (!backwarn) {
 248                                         backwarn = TT.linenum;
 249                                         if (option_mask32 & FLAG_IGNORE) {
 250                                                 dummy_revert = 1;
 251                                                 reverse ^= 1;
 252                                                 continue;
 253                                         }
 254                                 }
 255                         }
 256                         plist = plist->next;
 257                 }
 258
 259                 // Is this EOF?
 260                 if (!data) {
 261                         if (PATCH_DEBUG) fdprintf(2, "INEOF\n");
 262
 263                         // Does this hunk need to match EOF?
 264                         if (!plist && matcheof) break;
 265
 266                         if (backwarn)
 267                                 fdprintf(2,"Possibly reversed hunk %d at %ld\n",
 268                                         TT.hunknum, TT.linenum);
 269
 270                         // File ended before we found a place for this hunk.
 271                         fail_hunk();
 272                         goto done;
 273                 }
 274
 275                 if (PATCH_DEBUG) fdprintf(2, "IN: %s\n", data);
 276                 check = dlist_add(&buf, data);
 277
 278                 // Compare this line with next expected line of hunk.
 279                 // todo: teach the strcmp() to ignore whitespace.
 280
 281                 // A match can fail because the next line doesn't match, or because
 282                 // we hit the end of a hunk that needed EOF, and this isn't EOF.
 283
 284                 // If match failed, flush first line of buffered data and
 285                 // recheck buffered data for a new match until we find one or run
 286                 // out of buffer.
 287
 288                 for (;;) {
 289                         while (plist && *plist->data == "+-"[reverse]) {
 290                                 if (strcmp(check->data, plist->data+1) == 0
 291                                  && !backwarn
 292                                 ) {
 293                                         backwarn = TT.linenum;
 294                                         if (option_mask32 & FLAG_IGNORE) {
 295                                                 dummy_revert = 1;
 296                                                 reverse ^= 1;
 297                                         }
 298                                 }
 299                                 plist = plist->next;
 300                         }
 301                         if (!plist || strcmp(check->data, plist->data+1)) {
 302                                 // Match failed.  Write out first line of buffered data and
 303                                 // recheck remaining buffered data for a new match.
 304
 305                                 if (PATCH_DEBUG)
 306                                         fdprintf(2, "NOT: %s\n", plist ? plist->data : "EOF");
 307
 308                                 TT.state = 3;
 309                                 check = buf;
 310                                 buf = buf->next;
 311                                 check->prev->next = buf;
 312                                 buf->prev = check->prev;
 313                                 do_line(check);
 314                                 plist = TT.current_hunk;
 315
 316                                 // If we've reached the end of the buffer without confirming a
 317                                 // match, read more lines.
 318                                 if (check == buf) {
 319                                         buf = NULL;
 320                                         break;
 321                                 }
 322                                 check = buf;
 323                         } else {
 324                                 if (PATCH_DEBUG)
 325                                         fdprintf(2, "MAYBE: %s\n", plist->data);
 326                                 // This line matches.  Advance plist, detect successful match.
 327                                 plist = plist->next;
 328                                 if (!plist && !matcheof) goto out;
 329                                 check = check->next;
 330                                 if (check == buf) break;
 331                         }
 332                 }
 333         }
 334 out:
 335         // We have a match.  Emit changed data.
 336         TT.state = "-+"[reverse ^ dummy_revert];
 337         dlist_free(TT.current_hunk, do_line);
 338         TT.current_hunk = NULL;
 339         TT.state = 1;
 340 done:
 341         if (buf) {
 342                 buf->prev->next = NULL;
 343                 dlist_free(buf, do_line);
 344         }
 345
 346         return TT.state;
 347 }
 348
 349 // Read a patch file and find hunks, opening/creating/deleting files.
 350 // Call apply_one_hunk() on each hunk.
 351
 352 // state 0: Not in a hunk, look for +++.
 353 // state 1: Found +++ file indicator, look for @@
 354 // state 2: In hunk: counting initial context lines
 355 // state 3: In hunk: getting body
 356 // Like GNU patch, we don't require a --- line before the +++, and
 357 // also allow the --- after the +++ line.
 358
 359 int patch_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
 360 int patch_main(int argc UNUSED_PARAM, char **argv)
 361 {
 362         int opts;
 363         int reverse, state = 0;
 364         char *oldname = NULL, *newname = NULL;
 365         char *opt_p, *opt_i;
 366         long oldlen = oldlen; /* for compiler */
 367         long newlen = newlen; /* for compiler */
 368
 369 #if ENABLE_LONG_OPTS
 370         static const char patch_longopts[] ALIGN1 =
 371                 "reverse\0"               No_argument       "R"
 372                 "unified\0"               No_argument       "u"
 373                 "strip\0"                 Required_argument "p"
 374                 "input\0"                 Required_argument "i"
 375                 "forward\0"               No_argument       "N"
 376 # if ENABLE_DESKTOP
 377                 "remove-empty-files\0"    No_argument       "E" /*ignored*/
 378                 /* "debug"                Required_argument "x" */
 379 # endif
 380                 /* "Assume user knows what [s]he is doing, do not ask any questions": */
 381                 "force\0"                 No_argument       "f" /*ignored*/
 382 # if ENABLE_DESKTOP
 383                 /* "Controls actions when a file is under RCS or SCCS control,
 384                  * and does not exist or is read-only and matches the default version,
 385                  * or when a file is under ClearCase control and does not exist..."
 386                  * IOW: rather obscure option.
 387                  * But Gentoo's portage does use -g0
 388                  */
 389                 "get\0"                   Required_argument "g" /*ignored*/
 390 # endif
 391                 "dry-run\0"               No_argument       "\xfd"
 392 # if ENABLE_DESKTOP
 393                 "backup-if-mismatch\0"    No_argument       "\xfe" /*ignored*/
 394                 "no-backup-if-mismatch\0" No_argument       "\xff" /*ignored*/
 395 # endif
 396                 ;
 397 #endif
 398
 399         INIT_TT();
 400
 401 #if ENABLE_LONG_OPTS
 402         opts = getopt32long(argv, FLAG_STR, patch_longopts, &opt_p, &opt_i);
 403 #else
 404         opts = getopt32(argv, FLAG_STR, &opt_p, &opt_i);
 405 #endif
 406         //bb_error_msg_and_die("opts:%x", opts);
 407
 408         argv += optind;
 409         reverse = opts & FLAG_REVERSE;
 410         TT.prefix = (opts & FLAG_PATHLEN) ? xatoi(opt_p) : 0; // can be negative!
 411         TT.filein = TT.fileout = -1;
 412         if (opts & FLAG_INPUT) {
 413                 xmove_fd(xopen_stdin(opt_i), STDIN_FILENO);
 414         } else {
 415                 if (argv[0] && argv[1]) {
 416                         xmove_fd(xopen_stdin(argv[1]), STDIN_FILENO);
 417                 }
 418         }
 419
 420         // Loop through the lines in the patch
 421         for(;;) {
 422                 char *patchline;
 423
 424                 patchline = xmalloc_fgetline(stdin);
 425                 if (!patchline) break;
 426
 427                 // Other versions of patch accept damaged patches,
 428                 // so we need to also.
 429                 if (!*patchline) {
 430                         free(patchline);
 431                         patchline = xstrdup(" ");
 432                 }
 433
 434                 // Are we assembling a hunk?
 435                 if (state >= 2) {
 436                         if (*patchline==' ' || *patchline=='+' || *patchline=='-') {
 437                                 dlist_add(&TT.current_hunk, patchline);
 438
 439                                 if (*patchline != '+') oldlen--;
 440                                 if (*patchline != '-') newlen--;
 441
 442                                 // Context line?
 443                                 if (*patchline==' ' && state==2) TT.context++;
 444                                 else state=3;
 445
 446                                 // If we've consumed all expected hunk lines, apply the hunk.
 447
 448                                 if (!oldlen && !newlen) state = apply_one_hunk();
 449                                 continue;
 450                         }
 451                         fail_hunk();
 452                         state = 0;
 453                         continue;
 454                 }
 455
 456                 // Open a new file?
 457                 if (is_prefixed_with(patchline, "--- ") || is_prefixed_with(patchline, "+++ ")) {
 458                         char *s, **name = reverse ? &newname : &oldname;
 459                         int i;
 460
 461                         if (*patchline == '+') {
 462                                 name = reverse ? &oldname : &newname;
 463                                 state = 1;
 464                         }
 465
 466                         finish_oldfile();
 467
 468                         if (!argv[0]) {
 469                                 free(*name);
 470                                 // Trim date from end of filename (if any).  We don't care.
 471                                 for (s = patchline+4; *s && *s!='\t'; s++)
 472                                         if (*s=='\\' && s[1]) s++;
 473                                 i = atoi(s);
 474                                 if (i>1900 && i<=1970)
 475                                         *name = xstrdup("/dev/null");
 476                                 else {
 477                                         *s = 0;
 478                                         *name = xstrdup(patchline+4);
 479                                 }
 480                         }
 481
 482                         // We defer actually opening the file because svn produces broken
 483                         // patches that don't signal they want to create a new file the
 484                         // way the patch man page says, so you have to read the first hunk
 485                         // and _guess_.
 486
 487                 // Start a new hunk?  Usually @@ -oldline,oldlen +newline,newlen @@
 488                 // but a missing ,value means the value is 1.
 489                 } else if (state == 1 && is_prefixed_with(patchline, "@@ -")) {
 490                         int i;
 491                         char *s = patchline+4;
 492
 493                         // Read oldline[,oldlen] +newline[,newlen]
 494
 495                         TT.oldlen = oldlen = TT.newlen = newlen = 1;
 496                         TT.oldline = strtol(s, &s, 10);
 497                         if (*s == ',') TT.oldlen = oldlen = strtol(s+1, &s, 10);
 498                         TT.newline = strtol(s+2, &s, 10);
 499                         if (*s == ',') TT.newlen = newlen = strtol(s+1, &s, 10);
 500
 501                         if (oldlen < 1 && newlen < 1)
 502                                 bb_error_msg_and_die("Really? %s", patchline);
 503
 504                         TT.context = 0;
 505                         state = 2;
 506
 507                         // If the --- line is missing or malformed, either oldname
 508                         // or (for -R) newname could be NULL -- but not both.  Like
 509                         // GNU patch, proceed based on the +++ line, and avoid SEGVs.
 510                         if (!oldname)
 511                                 oldname = xstrdup("MISSING_FILENAME");
 512                         if (!newname)
 513                                 newname = xstrdup("MISSING_FILENAME");
 514
 515                         // If this is the first hunk, open the file.
 516                         if (TT.filein == -1) {
 517                                 int oldsum, newsum, empty = 0;
 518                                 char *name;
 519
 520                                 oldsum = TT.oldline + oldlen;
 521                                 newsum = TT.newline + newlen;
 522
 523                                 name = reverse ? oldname : newname;
 524
 525                                 // We're deleting oldname if new file is /dev/null (before -p)
 526                                 // or if new hunk is empty (zero context) after patching
 527                                 if (strcmp(name, "/dev/null") == 0 || !(reverse ? oldsum : newsum)) {
 528                                         name = reverse ? newname : oldname;
 529                                         empty = 1;
 530                                 }
 531
 532                                 // Handle -p path truncation.
 533                                 for (i = 0, s = name; *s;) {
 534                                         if ((option_mask32 & FLAG_PATHLEN) && TT.prefix == i)
 535                                                 break;
 536                                         if (*s++ != '/')
 537                                                 continue;
 538                                         while (*s == '/')
 539                                                 s++;
 540                                         i++;
 541                                         name = s;
 542                                 }
 543                                 // If "patch FILE_TO_PATCH", completely ignore name from patch
 544                                 if (argv[0])
 545                                         name = argv[0];
 546
 547                                 if (empty) {
 548                                         // File is empty after the patches have been applied
 549                                         state = 0;
 550                                         if (option_mask32 & FLAG_RMEMPTY) {
 551                                                 // If flag -E or --remove-empty-files is set
 552                                                 printf("removing %s\n", name);
 553                                                 if (!(opts & FLAG_dry_run))
 554                                                         xunlink(name);
 555                                         } else {
 556                                                 printf("patching file %s\n", name);
 557                                                 if (!(opts & FLAG_dry_run))
 558                                                         xclose(xopen(name, O_WRONLY | O_TRUNC));
 559                                         }
 560                                 // If we've got a file to open, do so.
 561                                 } else if (!(option_mask32 & FLAG_PATHLEN) || i <= TT.prefix) {
 562                                         struct stat statbuf;
 563
 564                                         // If the old file was null, we're creating a new one.
 565                                         if (strcmp(oldname, "/dev/null") == 0 || !oldsum) {
 566                                                 printf("creating %s\n", name);
 567                                                 if (!(opts & FLAG_dry_run)) {
 568                                                         s = strrchr(name, '/');
 569                                                         if (s) {
 570                                                                 *s = '\0';
 571                                                                 bb_make_directory(name, -1, FILEUTILS_RECUR);
 572                                                                 *s = '/';
 573                                                         }
 574                                                         TT.filein = xopen(name, O_CREAT|O_EXCL|O_RDWR);
 575                                                 } else {
 576                                                         TT.filein = xopen("/dev/null", O_RDONLY);
 577                                                 }
 578                                         } else {
 579                                                 printf("patching file %s\n", name);
 580                                                 TT.filein = xopen(name, O_RDONLY);
 581                                         }
 582
 583                                         if (!(opts & FLAG_dry_run)) {
 584                                                 TT.tempname = xasprintf("%sXXXXXX", name);
 585                                                 TT.fileout = xmkstemp(TT.tempname);
 586                                                 // Set permissions of output file
 587                                                 fstat(TT.filein, &statbuf);
 588                                                 fchmod(TT.fileout, statbuf.st_mode);
 589                                         } else {
 590                                                 TT.tempname = (char*)"";
 591                                                 TT.fileout = xopen("/dev/null", O_WRONLY);
 592                                         }
 593                                         TT.linenum = 0;
 594                                         TT.hunknum = 0;
 595                                 }
 596                         }
 597
 598                         TT.hunknum++;
 599
 600                         continue;
 601                 }
 602
 603                 // If we didn't continue above, discard this line.
 604                 free(patchline);
 605         }
 606
 607         finish_oldfile();
 608
 609         if (ENABLE_FEATURE_CLEAN_UP) {
 610                 free(oldname);
 611                 free(newname);
 612         }
 613
 614         return TT.exitval;
 615 }