1/* find.c - Search directories for matching files.
2 *
3 * Copyright 2014 Rob Landley <rob@landley.net>
4 *
5 * See http://pubs.opengroup.org/onlinepubs/9699919799/utilities/find.c
6 *
7 * Our "unspecified" behavior for no paths is to use "."
8 * Parentheses can only stack 4096 deep
9 * Not treating two {} as an error, but only using last
10 *
11 * TODO: -empty (dirs too!)
12
13USE_FIND(NEWTOY(find, "?^HL[-HL]", TOYFLAG_USR|TOYFLAG_BIN))
14
15config FIND
16  bool "find"
17  default y
18  help
19    usage: find [-HL] [DIR...] [<options>]
20
21    Search directories for matching files.
22    Default: search "." match all -print all matches.
23
24    -H  Follow command line symlinks         -L  Follow all symlinks
25
26    Match filters:
27    -name  PATTERN  filename with wildcards   -iname      case insensitive -name
28    -path  PATTERN  path name with wildcards  -ipath      case insensitive -path
29    -user  UNAME    belongs to user UNAME     -nouser     user ID not known
30    -group GROUP    belongs to group GROUP    -nogroup    group ID not known
31    -perm  [-/]MODE permissions (-=min /=any) -prune      ignore contents of dir
32    -size  N[c]     512 byte blocks (c=bytes) -xdev       only this filesystem
33    -links N        hardlink count            -atime N[u] accessed N units ago
34    -ctime N[u]     created N units ago       -mtime N[u] modified N units ago
35    -newer FILE     newer mtime than FILE     -mindepth # at least # dirs down
36    -depth          ignore contents of dir    -maxdepth # at most # dirs down
37    -inum  N        inode number N            -empty      empty files and dirs
38    -type [bcdflps] (block, char, dir, file, symlink, pipe, socket)
39
40    Numbers N may be prefixed by a - (less than) or + (greater than). Units for
41    -Xtime are d (days, default), h (hours), m (minutes), or s (seconds).
42
43    Combine matches with:
44    !, -a, -o, ( )    not, and, or, group expressions
45
46    Actions:
47    -print   Print match with newline  -print0    Print match with null
48    -exec    Run command with path     -execdir   Run command in file's dir
49    -ok      Ask before exec           -okdir     Ask before execdir
50    -delete  Remove matching file/dir
51
52    Commands substitute "{}" with matched file. End with ";" to run each file,
53    or "+" (next argument after "{}") to collect and run with multiple files.
54*/
55
56#define FOR_find
57#include "toys.h"
58
59GLOBALS(
60  char **filter;
61  struct double_list *argdata;
62  int topdir, xdev, depth;
63  time_t now;
64  long max_bytes;
65)
66
67struct execdir_data {
68  struct execdir_data *next;
69
70  int namecount;
71  struct double_list *names;
72};
73
74// None of this can go in TT because you can have more than one -exec
75struct exec_range {
76  char *next, *prev;  // layout compatible with struct double_list
77
78  int dir, plus, arglen, argsize, curly;
79  char **argstart;
80  struct execdir_data exec, *execdir;
81};
82
83// Perform pending -exec (if any)
84static int flush_exec(struct dirtree *new, struct exec_range *aa)
85{
86  struct execdir_data *bb = aa->execdir ? aa->execdir : &aa->exec;
87  char **newargs;
88  int rc, revert = 0;
89
90  if (!bb->namecount) return 0;
91
92  dlist_terminate(bb->names);
93
94  // switch to directory for -execdir, or back to top if we have an -execdir
95  // _and_ a normal -exec, or are at top of tree in -execdir
96  if (TT.topdir != -1) {
97    if (aa->dir && new && new->parent) {
98      revert++;
99      rc = fchdir(new->parent->dirfd);
100    } else rc = fchdir(TT.topdir);
101    if (rc) {
102      perror_msg_raw(revert ? new->name : ".");
103
104      return rc;
105    }
106  }
107
108  // execdir: accumulated execs in this directory's children.
109  newargs = xmalloc(sizeof(char *)*(aa->arglen+bb->namecount+1));
110  if (aa->curly < 0) {
111    memcpy(newargs, aa->argstart, sizeof(char *)*aa->arglen);
112    newargs[aa->arglen] = 0;
113  } else {
114    int pos = aa->curly, rest = aa->arglen - aa->curly;
115    struct double_list *dl;
116
117    // Collate argument list
118    memcpy(newargs, aa->argstart, sizeof(char *)*pos);
119    for (dl = bb->names; dl; dl = dl->next) newargs[pos++] = dl->data;
120    rest = aa->arglen - aa->curly - 1;
121    memcpy(newargs+pos, aa->argstart+aa->curly+1, sizeof(char *)*rest);
122    newargs[pos+rest] = 0;
123  }
124
125  rc = xrun(newargs);
126
127  llist_traverse(bb->names, llist_free_double);
128  bb->names = 0;
129  bb->namecount = 0;
130
131  if (revert) revert = fchdir(TT.topdir);
132
133  return rc;
134}
135
136// Return numeric value with explicit sign
137static int compare_numsign(long val, long units, char *str)
138{
139  char sign = 0;
140  long myval;
141
142  if (*str == '+' || *str == '-') sign = *(str++);
143  else if (!isdigit(*str)) error_exit("%s not [+-]N", str);
144  myval = atolx(str);
145  if (units && isdigit(str[strlen(str)-1])) myval *= units;
146
147  if (sign == '+') return val > myval;
148  if (sign == '-') return val < myval;
149  return val == myval;
150}
151
152static void do_print(struct dirtree *new, char c)
153{
154  char *s=dirtree_path(new, 0);
155
156  xprintf("%s%c", s, c);
157  free(s);
158}
159
160// Descend or ascend -execdir + directory level
161static void execdir(struct dirtree *new, int flush)
162{
163  struct double_list *dl;
164  struct exec_range *aa;
165  struct execdir_data *bb;
166
167  if (new && TT.topdir == -1) return;
168
169  for (dl = TT.argdata; dl; dl = dl->next) {
170    if (dl->prev != (void *)1) continue;
171    aa = (void *)dl;
172    if (!aa->plus || (new && !aa->dir)) continue;
173
174    if (flush) {
175
176      // Flush pending "-execdir +" instances for this dir
177      // or flush everything for -exec at top
178      toys.exitval |= flush_exec(new, aa);
179
180      // pop per-directory struct
181      if ((bb = aa->execdir)) {
182        aa->execdir = bb->next;
183        free(bb);
184      }
185    } else if (aa->dir) {
186
187      // Push new per-directory struct for -execdir/okdir + codepath. (Can't
188      // use new->extra because command line may have multiple -execdir)
189      bb = xzalloc(sizeof(struct execdir_data));
190      bb->next = aa->execdir;
191      aa->execdir = bb;
192    }
193  }
194}
195
196// Call this with 0 for first pass argument parsing and syntax checking (which
197// populates argdata). Later commands traverse argdata (in order) when they
198// need "do once" results.
199static int do_find(struct dirtree *new)
200{
201  int pcount = 0, print = 0, not = 0, active = !!new, test = active, recurse;
202  struct double_list *argdata = TT.argdata;
203  char *s, **ss;
204
205  recurse = DIRTREE_COMEAGAIN|(DIRTREE_SYMFOLLOW*!!(toys.optflags&FLAG_L));
206
207  // skip . and .. below topdir, handle -xdev and -depth
208  if (new) {
209    if (new->parent) {
210      if (!dirtree_notdotdot(new)) return 0;
211      if (TT.xdev && new->st.st_dev != new->parent->st.st_dev) recurse = 0;
212    }
213
214    if (S_ISDIR(new->st.st_mode)) {
215      // Descending into new directory
216      if (!new->again) {
217        struct dirtree *n;
218
219        for (n = new->parent; n; n = n->parent) {
220          if (n->st.st_ino==new->st.st_ino && n->st.st_dev==new->st.st_dev) {
221            error_msg("'%s': loop detected", s = dirtree_path(new, 0));
222            free(s);
223
224            return 0;
225          }
226        }
227
228        if (TT.depth) {
229          execdir(new, 0);
230
231          return recurse;
232        }
233      // Done with directory (COMEAGAIN call)
234      } else {
235        execdir(new, 1);
236        recurse = 0;
237        if (!TT.depth) return 0;
238      }
239    }
240  }
241
242  // pcount: parentheses stack depth (using toybuf bytes, 4096 max depth)
243  // test: result of most recent test
244  // active: if 0 don't perform tests
245  // not: a pending ! applies to this test (only set if performing tests)
246  // print: saw one of print/ok/exec, no need for default -print
247
248  if (TT.filter) for (ss = TT.filter; *ss; ss++) {
249    int check = active && test;
250
251    s = *ss;
252
253    // handle ! ( ) using toybuf as a stack
254    if (*s != '-') {
255      if (s[1]) goto error;
256
257      if (*s == '!') {
258        // Don't invert if we're not making a decision
259        if (check) not = !not;
260
261      // Save old "not" and "active" on toybuf stack.
262      // Deactivate this parenthetical if !test
263      // Note: test value should never change while !active
264      } else if (*s == '(') {
265        if (pcount == sizeof(toybuf)) goto error;
266        toybuf[pcount++] = not+(active<<1);
267        if (!check) active = 0;
268        not = 0;
269
270      // Pop status, apply deferred not to test
271      } else if (*s == ')') {
272        if (--pcount < 0) goto error;
273        // Pop active state, apply deferred not (which was only set if checking)
274        active = (toybuf[pcount]>>1)&1;
275        if (active && (toybuf[pcount]&1)) test = !test;
276        not = 0;
277      } else goto error;
278
279      continue;
280    } else s++;
281
282    if (!strcmp(s, "xdev")) TT.xdev = 1;
283    else if (!strcmp(s, "delete")) {
284      // Delete forces depth first
285      TT.depth = 1;
286      if (new && check)
287        test = !unlinkat(dirtree_parentfd(new), new->name,
288          S_ISDIR(new->st.st_mode) ? AT_REMOVEDIR : 0);
289    } else if (!strcmp(s, "depth")) TT.depth = 1;
290    else if (!strcmp(s, "o") || !strcmp(s, "or")) {
291      if (not) goto error;
292      if (active) {
293        if (!test) test = 1;
294        else active = 0;     // decision has been made until next ")"
295      }
296    } else if (!strcmp(s, "not")) {
297      if (check) not = !not;
298      continue;
299    // Mostly ignore NOP argument
300    } else if (!strcmp(s, "a") || !strcmp(s, "and") || !strcmp(s, "noleaf")) {
301      if (not) goto error;
302
303    } else if (!strcmp(s, "print") || !strcmp("print0", s)) {
304      print++;
305      if (check) do_print(new, s[5] ? 0 : '\n');
306
307    } else if (!strcmp(s, "nouser")) {
308      if (check) if (bufgetpwuid(new->st.st_uid)) test = 0;
309    } else if (!strcmp(s, "nogroup")) {
310      if (check) if (bufgetgrgid(new->st.st_gid)) test = 0;
311    } else if (!strcmp(s, "prune")) {
312      if (check && S_ISDIR(new->st.st_mode) && !TT.depth) recurse = 0;
313
314    // Remaining filters take an argument
315    } else {
316      if (!strcmp(s, "name") || !strcmp(s, "iname")
317        || !strcmp(s, "path") || !strcmp(s, "ipath"))
318      {
319        int i = (*s == 'i');
320        char *arg = ss[1], *path = 0, *name = new ? new->name : arg;
321
322        // Handle path expansion and case flattening
323        if (new && s[i] == 'p') name = path = dirtree_path(new, 0);
324        if (i) {
325          if ((check || !new) && name) name = strlower(name);
326          if (!new) dlist_add(&TT.argdata, name);
327          else arg = ((struct double_list *)llist_pop(&argdata))->data;
328        }
329
330        if (check) {
331          test = !fnmatch(arg, name, FNM_PATHNAME*(s[i] == 'p'));
332          if (i) free(name);
333        }
334        free(path);
335      } else if (!strcmp(s, "perm")) {
336        if (check) {
337          char *m = ss[1];
338          int match_min = *m == '-',
339              match_any = *m == '/';
340          mode_t m1 = string_to_mode(m+(match_min || match_any), 0),
341                 m2 = new->st.st_mode & 07777;
342
343          if (match_min || match_any) m2 &= m1;
344          test = match_any ? !m1 || m2 : m1 == m2;
345        }
346      } else if (!strcmp(s, "type")) {
347        if (check) {
348          int types[] = {S_IFBLK, S_IFCHR, S_IFDIR, S_IFLNK, S_IFIFO,
349                         S_IFREG, S_IFSOCK}, i = stridx("bcdlpfs", *ss[1]);
350
351          if (i<0) error_exit("bad -type '%c'", *ss[1]);
352          if ((new->st.st_mode & S_IFMT) != types[i]) test = 0;
353        }
354
355      } else if (strchr("acm", *s)
356        && (!strcmp(s+1, "time") || !strcmp(s+1, "min")))
357      {
358        if (check) {
359          char *copy = ss[1];
360          time_t thyme = (int []){new->st.st_atime, new->st.st_ctime,
361                                  new->st.st_mtime}[stridx("acm", *s)];
362          int len = strlen(copy), uu, units = (s[1]=='m') ? 60 : 86400;
363
364          if (len && -1!=(uu = stridx("dhms",tolower(copy[len-1])))) {
365            copy = xstrdup(copy);
366            copy[--len] = 0;
367            units = (int []){86400, 3600, 60, 1}[uu];
368          }
369          test = compare_numsign(TT.now - thyme, units, copy);
370          if (copy != ss[1]) free(copy);
371        }
372      } else if (!strcmp(s, "size")) {
373        if (check)
374          test = compare_numsign(new->st.st_size, 512, ss[1]);
375      } else if (!strcmp(s, "links")) {
376        if (check) test = compare_numsign(new->st.st_nlink, 0, ss[1]);
377      } else if (!strcmp(s, "inum")) {
378        if (check)
379          test = compare_numsign(new->st.st_ino, 0, ss[1]);
380      } else if (!strcmp(s, "mindepth") || !strcmp(s, "maxdepth")) {
381        if (check) {
382          struct dirtree *dt = new;
383          int i = 0, d = atolx(ss[1]);
384
385          while ((dt = dt->parent)) i++;
386          if (s[1] == 'i') {
387            test = i >= d;
388            if (i == d && not) recurse = 0;
389          } else {
390            test = i <= d;
391            if (i == d && !not) recurse = 0;
392          }
393        }
394      } else if (!strcmp(s, "user") || !strcmp(s, "group")
395              || !strcmp(s, "newer"))
396      {
397        struct {
398          void *next, *prev;
399          union {
400            uid_t uid;
401            gid_t gid;
402            struct timespec tm;
403          } u;
404        } *udl;
405
406        if (!new) {
407          if (ss[1]) {
408            udl = xmalloc(sizeof(*udl));
409            dlist_add_nomalloc(&TT.argdata, (void *)udl);
410
411            if (*s == 'u') udl->u.uid = xgetuid(ss[1]);
412            else if (*s == 'g') udl->u.gid = xgetgid(ss[1]);
413            else {
414              struct stat st;
415
416              xstat(ss[1], &st);
417              udl->u.tm = st.st_mtim;
418            }
419          }
420        } else {
421          udl = (void *)llist_pop(&argdata);
422          if (check) {
423            if (*s == 'u') test = new->st.st_uid == udl->u.uid;
424            else if (*s == 'g') test = new->st.st_gid == udl->u.gid;
425            else {
426              test = new->st.st_mtim.tv_sec > udl->u.tm.tv_sec;
427              if (new->st.st_mtim.tv_sec == udl->u.tm.tv_sec)
428                test = new->st.st_mtim.tv_nsec > udl->u.tm.tv_nsec;
429            }
430          }
431        }
432      } else if (!strcmp(s, "exec") || !strcmp("ok", s)
433              || !strcmp(s, "execdir") || !strcmp(s, "okdir"))
434      {
435        struct exec_range *aa;
436
437        print++;
438
439        // Initial argument parsing pass
440        if (!new) {
441          int len;
442
443          // catch "-exec" with no args and "-exec \;"
444          if (!ss[1] || !strcmp(ss[1], ";")) error_exit("'%s' needs 1 arg", s);
445
446          dlist_add_nomalloc(&TT.argdata, (void *)(aa = xzalloc(sizeof(*aa))));
447          aa->argstart = ++ss;
448          aa->curly = -1;
449
450          // Record command line arguments to -exec
451          for (len = 0; ss[len]; len++) {
452            if (!strcmp(ss[len], ";")) break;
453            else if (!strcmp(ss[len], "{}")) {
454              aa->curly = len;
455              if (ss[len+1] && !strcmp(ss[len+1], "+")) {
456                aa->plus++;
457                len++;
458                break;
459              }
460            } else aa->argsize += sizeof(char *) + strlen(ss[len]) + 1;
461          }
462          if (!ss[len]) error_exit("-exec without %s",
463            aa->curly!=-1 ? "\\;" : "{}");
464          ss += len;
465          aa->arglen = len;
466          aa->dir = !!strchr(s, 'd');
467          if (TT.topdir == -1) TT.topdir = xopenro(".");
468
469        // collect names and execute commands
470        } else {
471          char *name, *ss1 = ss[1];
472          struct execdir_data *bb;
473
474          // Grab command line exec argument list
475          aa = (void *)llist_pop(&argdata);
476          ss += aa->arglen + 1;
477
478          if (!check) goto cont;
479          // name is always a new malloc, so we can always free it.
480          name = aa->dir ? xstrdup(new->name) : dirtree_path(new, 0);
481
482          if (*s == 'o') {
483            fprintf(stderr, "[%s] %s", ss1, name);
484            if (!(test = yesno(0))) {
485              free(name);
486              goto cont;
487            }
488          }
489
490          // Add next name to list (global list without -dir, local with)
491          bb = aa->execdir ? aa->execdir : &aa->exec;
492          dlist_add(&bb->names, name);
493          bb->namecount++;
494
495          // -exec + collates and saves result in exitval
496          if (aa->plus) {
497            // Mark entry so COMEAGAIN can call flush_exec() in parent.
498            // This is never a valid pointer value for prev to have otherwise
499            // Done here vs argument parsing pass so it's after dlist_terminate
500            aa->prev = (void *)1;
501
502            // Flush if the child's environment space gets too large.
503            // An insanely long path (>2 gigs) could wrap the counter and
504            // defeat this test, which could potentially trigger OOM killer.
505            if ((aa->plus += sizeof(char *)+strlen(name)+1) > TT.max_bytes) {
506              aa->plus = 1;
507              toys.exitval |= flush_exec(new, aa);
508            }
509          } else test = flush_exec(new, aa);
510        }
511
512        // Argument consumed, skip the check.
513        goto cont;
514      } else goto error;
515
516      // This test can go at the end because we do a syntax checking
517      // pass first. Putting it here gets the error message (-unknown
518      // vs -known noarg) right.
519      if (!*++ss) error_exit("'%s' needs 1 arg", --s);
520    }
521cont:
522    // Apply pending "!" to result
523    if (active && not) test = !test;
524    not = 0;
525  }
526
527  if (new) {
528    // If there was no action, print
529    if (!print && test) do_print(new, '\n');
530
531    if (S_ISDIR(new->st.st_mode)) execdir(new, 0);
532
533  } else dlist_terminate(TT.argdata);
534
535  return recurse;
536
537error:
538  error_exit("bad arg '%s'", *ss);
539}
540
541void find_main(void)
542{
543  int i, len;
544  char **ss = toys.optargs;
545
546  TT.topdir = -1;
547  TT.max_bytes = sysconf(_SC_ARG_MAX) - environ_bytes();
548
549  // Distinguish paths from filters
550  for (len = 0; toys.optargs[len]; len++)
551    if (strchr("-!(", *toys.optargs[len])) break;
552  TT.filter = toys.optargs+len;
553
554  // use "." if no paths
555  if (!len) {
556    ss = (char *[]){"."};
557    len = 1;
558  }
559
560  // first pass argument parsing, verify args match up, handle "evaluate once"
561  TT.now = time(0);
562  do_find(0);
563
564  // Loop through paths
565  for (i = 0; i < len; i++)
566    dirtree_flagread(ss[i], DIRTREE_SYMFOLLOW*!!(toys.optflags&(FLAG_H|FLAG_L)),
567      do_find);
568
569  execdir(0, 1);
570
571  if (CFG_TOYBOX_FREE) {
572    close(TT.topdir);
573    llist_traverse(TT.argdata, free);
574  }
575}
576