toys/posix/find.c

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