1/* patch.c - Apply a "universal" diff.
2 *
3 * Copyright 2007 Rob Landley <rob@landley.net>
4 *
5 * see http://opengroup.org/onlinepubs/9699919799/utilities/patch.html
6 * (But only does -u, because who still cares about "ed"?)
7 *
8 * TODO:
9 * -b backup
10 * -l treat all whitespace as a single space
11 * -N ignore already applied
12 * -d chdir first
13 * -D define wrap #ifdef and #ifndef around changes
14 * -o outfile output here instead of in place
15 * -r rejectfile write rejected hunks to this file
16 *
17 * -E remove empty files --remove-empty-files
18 * -f force (no questions asked)
19 * -F fuzz (number, default 2)
20 * [file] which file to patch
21
22USE_PATCH(NEWTOY(patch, USE_TOYBOX_DEBUG("x")"ulp#i:R", TOYFLAG_USR|TOYFLAG_BIN))
23
24config PATCH
25  bool "patch"
26  default y
27  help
28    usage: patch [-i file] [-p depth] [-Ru]
29
30    Apply a unified diff to one or more files.
31
32    -i	Input file (defaults=stdin)
33    -l	Loose match (ignore whitespace)
34    -p	Number of '/' to strip from start of file paths (default=all)
35    -R	Reverse patch.
36    -u	Ignored (only handles "unified" diffs)
37
38    This version of patch only handles unified diffs, and only modifies
39    a file when all all hunks to that file apply.  Patch prints failed
40    hunks to stderr, and exits with nonzero status if any hunks fail.
41
42    A file compared against /dev/null (or with a date <= the epoch) is
43    created/deleted as appropriate.
44*/
45
46#define FOR_patch
47#include "toys.h"
48
49GLOBALS(
50  char *infile;
51  long prefix;
52
53  struct double_list *current_hunk;
54  long oldline, oldlen, newline, newlen;
55  long linenum;
56  int context, state, filein, fileout, filepatch, hunknum;
57  char *tempname;
58)
59
60// Dispose of a line of input, either by writing it out or discarding it.
61
62// state < 2: just free
63// state = 2: write whole line to stderr
64// state = 3: write whole line to fileout
65// state > 3: write line+1 to fileout when *line != state
66
67#define PATCH_DEBUG (CFG_TOYBOX_DEBUG && (toys.optflags & 32))
68
69static void do_line(void *data)
70{
71  struct double_list *dlist = (struct double_list *)data;
72
73  if (TT.state>1 && *dlist->data != TT.state) {
74    char *s = dlist->data+(TT.state>3 ? 1 : 0);
75    int i = TT.state == 2 ? 2 : TT.fileout;
76
77    xwrite(i, s, strlen(s));
78    xwrite(i, "\n", 1);
79  }
80
81  if (PATCH_DEBUG) fprintf(stderr, "DO %d: %s\n", TT.state, dlist->data);
82
83  free(dlist->data);
84  free(data);
85}
86
87static void finish_oldfile(void)
88{
89  if (TT.tempname) replace_tempfile(TT.filein, TT.fileout, &TT.tempname);
90  TT.fileout = TT.filein = -1;
91}
92
93static void fail_hunk(void)
94{
95  if (!TT.current_hunk) return;
96
97  fprintf(stderr, "Hunk %d FAILED %ld/%ld.\n",
98      TT.hunknum, TT.oldline, TT.newline);
99  toys.exitval = 1;
100
101  // If we got to this point, we've seeked to the end.  Discard changes to
102  // this file and advance to next file.
103
104  TT.state = 2;
105  llist_traverse(TT.current_hunk, do_line);
106  TT.current_hunk = NULL;
107  delete_tempfile(TT.filein, TT.fileout, &TT.tempname);
108  TT.state = 0;
109}
110
111// Compare ignoring whitespace. Just returns
112static int loosecmp(char *aa, char *bb)
113{
114  int a = 0, b = 0;
115
116  for (;;) {
117    while (isspace(aa[a])) a++;
118    while (isspace(bb[b])) b++;
119    if (aa[a] != bb[b]) return 1;
120    if (!aa[a]) return 0;
121    a++, b++;
122  }
123}
124
125// Given a hunk of a unified diff, make the appropriate change to the file.
126// This does not use the location information, but instead treats a hunk
127// as a sort of regex.  Copies data from input to output until it finds
128// the change to be made, then outputs the changed data and returns.
129// (Finding EOF first is an error.)  This is a single pass operation, so
130// multiple hunks must occur in order in the file.
131
132static int apply_one_hunk(void)
133{
134  struct double_list *plist, *buf = NULL, *check;
135  int matcheof = 0, reverse = toys.optflags & FLAG_R, backwarn = 0;
136  int (*lcmp)(char *aa, char *bb);
137
138  lcmp = (toys.optflags & FLAG_l) ? (void *)loosecmp : (void *)strcmp;
139  dlist_terminate(TT.current_hunk);
140
141  // Match EOF if there aren't as many ending context lines as beginning
142  for (plist = TT.current_hunk; plist; plist = plist->next) {
143    if (plist->data[0]==' ') matcheof++;
144    else matcheof = 0;
145    if (PATCH_DEBUG) fprintf(stderr, "HUNK:%s\n", plist->data);
146  }
147  matcheof = matcheof < TT.context;
148
149  if (PATCH_DEBUG) fprintf(stderr,"MATCHEOF=%c\n", matcheof ? 'Y' : 'N');
150
151  // Loop through input data searching for this hunk.  Match all context
152  // lines and all lines to be removed until we've found the end of a
153  // complete hunk.
154  plist = TT.current_hunk;
155  buf = NULL;
156  if (TT.context) for (;;) {
157    char *data = get_line(TT.filein);
158
159    TT.linenum++;
160
161    // Figure out which line of hunk to compare with next.  (Skip lines
162    // of the hunk we'd be adding.)
163    while (plist && *plist->data == "+-"[reverse]) {
164      if (data && !lcmp(data, plist->data+1)) {
165        if (!backwarn) backwarn = TT.linenum;
166      }
167      plist = plist->next;
168    }
169
170    // Is this EOF?
171    if (!data) {
172      if (PATCH_DEBUG) fprintf(stderr, "INEOF\n");
173
174      // Does this hunk need to match EOF?
175      if (!plist && matcheof) break;
176
177      if (backwarn)
178        fprintf(stderr, "Possibly reversed hunk %d at %ld\n",
179            TT.hunknum, TT.linenum);
180
181      // File ended before we found a place for this hunk.
182      fail_hunk();
183      goto done;
184    } else if (PATCH_DEBUG) fprintf(stderr, "IN: %s\n", data);
185    check = dlist_add(&buf, data);
186
187    // Compare this line with next expected line of hunk.
188
189    // A match can fail because the next line doesn't match, or because
190    // we hit the end of a hunk that needed EOF, and this isn't EOF.
191
192    // If match failed, flush first line of buffered data and
193    // recheck buffered data for a new match until we find one or run
194    // out of buffer.
195
196    for (;;) {
197      if (!plist || lcmp(check->data, plist->data+1)) {
198        // Match failed.  Write out first line of buffered data and
199        // recheck remaining buffered data for a new match.
200
201        if (PATCH_DEBUG) {
202          int bug = 0;
203
204          if (!plist) fprintf(stderr, "NULL plist\n");
205          else {
206            while (plist->data[bug] == check->data[bug]) bug++;
207            fprintf(stderr, "NOT(%d:%d!=%d): %s\n", bug, plist->data[bug],
208              check->data[bug], plist->data);
209          }
210        }
211
212        TT.state = 3;
213        do_line(check = dlist_pop(&buf));
214        plist = TT.current_hunk;
215
216        // If we've reached the end of the buffer without confirming a
217        // match, read more lines.
218        if (!buf) break;
219        check = buf;
220      } else {
221        if (PATCH_DEBUG) fprintf(stderr, "MAYBE: %s\n", plist->data);
222        // This line matches.  Advance plist, detect successful match.
223        plist = plist->next;
224        if (!plist && !matcheof) goto out;
225        check = check->next;
226        if (check == buf) break;
227      }
228    }
229  }
230out:
231  // We have a match.  Emit changed data.
232  TT.state = "-+"[reverse];
233  llist_traverse(TT.current_hunk, do_line);
234  TT.current_hunk = NULL;
235  TT.state = 1;
236done:
237  if (buf) {
238    dlist_terminate(buf);
239    llist_traverse(buf, do_line);
240  }
241
242  return TT.state;
243}
244
245// Read a patch file and find hunks, opening/creating/deleting files.
246// Call apply_one_hunk() on each hunk.
247
248// state 0: Not in a hunk, look for +++.
249// state 1: Found +++ file indicator, look for @@
250// state 2: In hunk: counting initial context lines
251// state 3: In hunk: getting body
252
253void patch_main(void)
254{
255  int reverse = toys.optflags&FLAG_R, state = 0, patchlinenum = 0,
256    strip = 0;
257  char *oldname = NULL, *newname = NULL;
258
259  if (TT.infile) TT.filepatch = xopen(TT.infile, O_RDONLY);
260  TT.filein = TT.fileout = -1;
261
262  // Loop through the lines in the patch
263  for (;;) {
264    char *patchline;
265
266    patchline = get_line(TT.filepatch);
267    if (!patchline) break;
268
269    // Other versions of patch accept damaged patches,
270    // so we need to also.
271    if (strip || !patchlinenum++) {
272      int len = strlen(patchline);
273      if (patchline[len-1] == '\r') {
274        if (!strip) fprintf(stderr, "Removing DOS newlines\n");
275        strip = 1;
276        patchline[len-1]=0;
277      }
278    }
279    if (!*patchline) {
280      free(patchline);
281      patchline = xstrdup(" ");
282    }
283
284    // Are we assembling a hunk?
285    if (state >= 2) {
286      if (*patchline==' ' || *patchline=='+' || *patchline=='-') {
287        dlist_add(&TT.current_hunk, patchline);
288
289        if (*patchline != '+') TT.oldlen--;
290        if (*patchline != '-') TT.newlen--;
291
292        // Context line?
293        if (*patchline==' ' && state==2) TT.context++;
294        else state=3;
295
296        // If we've consumed all expected hunk lines, apply the hunk.
297
298        if (!TT.oldlen && !TT.newlen) state = apply_one_hunk();
299        continue;
300      }
301      dlist_terminate(TT.current_hunk);
302      fail_hunk();
303      state = 0;
304      continue;
305    }
306
307    // Open a new file?
308    if (!strncmp("--- ", patchline, 4) || !strncmp("+++ ", patchline, 4)) {
309      char *s, **name = &oldname;
310      int i;
311
312      if (*patchline == '+') {
313        name = &newname;
314        state = 1;
315      }
316
317      free(*name);
318      finish_oldfile();
319
320      // Trim date from end of filename (if any).  We don't care.
321      for (s = patchline+4; *s && *s!='\t'; s++)
322        if (*s=='\\' && s[1]) s++;
323      i = atoi(s);
324      if (i>1900 && i<=1970) *name = xstrdup("/dev/null");
325      else {
326        *s = 0;
327        *name = xstrdup(patchline+4);
328      }
329
330      // We defer actually opening the file because svn produces broken
331      // patches that don't signal they want to create a new file the
332      // way the patch man page says, so you have to read the first hunk
333      // and _guess_.
334
335    // Start a new hunk?  Usually @@ -oldline,oldlen +newline,newlen @@
336    // but a missing ,value means the value is 1.
337    } else if (state == 1 && !strncmp("@@ -", patchline, 4)) {
338      int i;
339      char *s = patchline+4;
340
341      // Read oldline[,oldlen] +newline[,newlen]
342
343      TT.oldlen = TT.newlen = 1;
344      TT.oldline = strtol(s, &s, 10);
345      if (*s == ',') TT.oldlen=strtol(s+1, &s, 10);
346      TT.newline = strtol(s+2, &s, 10);
347      if (*s == ',') TT.newlen = strtol(s+1, &s, 10);
348
349      TT.context = 0;
350      state = 2;
351
352      // If this is the first hunk, open the file.
353      if (TT.filein == -1) {
354        int oldsum, newsum, del = 0;
355        char *name;
356
357        oldsum = TT.oldline + TT.oldlen;
358        newsum = TT.newline + TT.newlen;
359
360        name = reverse ? oldname : newname;
361
362        // We're deleting oldname if new file is /dev/null (before -p)
363        // or if new hunk is empty (zero context) after patching
364        if (!strcmp(name, "/dev/null") || !(reverse ? oldsum : newsum))
365        {
366          name = reverse ? newname : oldname;
367          del++;
368        }
369
370        // handle -p path truncation.
371        for (i = 0, s = name; *s;) {
372          if ((toys.optflags & FLAG_p) && TT.prefix == i) break;
373          if (*s++ != '/') continue;
374          while (*s == '/') s++;
375          name = s;
376          i++;
377        }
378
379        if (del) {
380          printf("removing %s\n", name);
381          xunlink(name);
382          state = 0;
383        // If we've got a file to open, do so.
384        } else if (!(toys.optflags & FLAG_p) || i <= TT.prefix) {
385          // If the old file was null, we're creating a new one.
386          if ((!strcmp(oldname, "/dev/null") || !oldsum) && access(name, F_OK))
387          {
388            printf("creating %s\n", name);
389            if (mkpathat(AT_FDCWD, name, 0, 2))
390              perror_exit("mkpath %s", name);
391            TT.filein = xcreate(name, O_CREAT|O_EXCL|O_RDWR, 0666);
392          } else {
393            printf("patching %s\n", name);
394            TT.filein = xopen(name, O_RDONLY);
395          }
396          TT.fileout = copy_tempfile(TT.filein, name, &TT.tempname);
397          TT.linenum = 0;
398          TT.hunknum = 0;
399        }
400      }
401
402      TT.hunknum++;
403
404      continue;
405    }
406
407    // If we didn't continue above, discard this line.
408    free(patchline);
409  }
410
411  finish_oldfile();
412
413  if (CFG_TOYBOX_FREE) {
414    close(TT.filepatch);
415    free(oldname);
416    free(newname);
417  }
418}
419