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