findutils/find.c

   1 /* vi: set sw=4 ts=4: */
   2 /*
   3  * Mini find implementation for busybox
   4  *
   5  * Copyright (C) 1999-2004 by Erik Andersen <andersen@codepoet.org>
   6  *
   7  * Reworked by David Douthitt <n9ubh@callsign.net> and
   8  *  Matt Kraai <kraai@alumni.carnegiemellon.edu>.
   9  *
  10  * Licensed under the GPL version 2, see the file LICENSE in this tarball.
  11  */
  12
  13 /* findutils-4.1.20:
  14  *
  15  * # find file.txt -exec 'echo {}' '{}  {}' ';'
  16  * find: echo file.txt: No such file or directory
  17  * # find file.txt -exec 'echo' '{}  {}' '; '
  18  * find: missing argument to `-exec'
  19  * # find file.txt -exec 'echo {}' '{}  {}' ';' junk
  20  * find: paths must precede expression
  21  * # find file.txt -exec 'echo {}' '{}  {}' ';' junk ';'
  22  * find: paths must precede expression
  23  * # find file.txt -exec 'echo' '{}  {}' ';'
  24  * file.txt  file.txt
  25  * (strace: execve("/bin/echo", ["echo", "file.txt  file.txt"], [ 30 vars ]))
  26  * # find file.txt -exec 'echo' '{}  {}' ';' -print -exec pwd ';'
  27  * file.txt  file.txt
  28  * file.txt
  29  * /tmp
  30  * # find -name '*.c' -o -name '*.h'
  31  * [shows files, *.c and *.h intermixed]
  32  * # find file.txt -name '*f*' -o -name '*t*'
  33  * file.txt
  34  * # find file.txt -name '*z*' -o -name '*t*'
  35  * file.txt
  36  * # find file.txt -name '*f*' -o -name '*z*'
  37  * file.txt
  38  *
  39  * # find t z -name '*t*' -print -o -name '*z*'
  40  * t
  41  * # find t z t z -name '*t*' -o -name '*z*' -print
  42  * z
  43  * z
  44  * # find t z t z '(' -name '*t*' -o -name '*z*' ')' -o -print
  45  * (no output)
  46  */
  47
  48 #include "busybox.h"
  49 #include <fnmatch.h>
  50
  51 USE_FEATURE_FIND_XDEV(static dev_t *xdev_dev;)
  52 USE_FEATURE_FIND_XDEV(static int xdev_count;)
  53
  54 typedef int (*action_fp)(const char *fileName, struct stat *statbuf, void *);
  55
  56 typedef struct {
  57         action_fp f;
  58 } action;
  59 #define ACTS(name, arg...) typedef struct { action a; arg; } action_##name;
  60 #define ACTF(name)         static int func_##name(const char *fileName, struct stat *statbuf, action_##name* ap)
  61                         ACTS(print)
  62                         ACTS(name,  char *pattern;)
  63 USE_FEATURE_FIND_PRINT0(ACTS(print0))
  64 USE_FEATURE_FIND_TYPE(  ACTS(type,  int type_mask;))
  65 USE_FEATURE_FIND_PERM(  ACTS(perm,  char perm_char; int perm_mask;))
  66 USE_FEATURE_FIND_MTIME( ACTS(mtime, char mtime_char; int mtime_days;))
  67 USE_FEATURE_FIND_MMIN(  ACTS(mmin,  char mmin_char; int mmin_mins;))
  68 USE_FEATURE_FIND_NEWER( ACTS(newer, time_t newer_mtime;))
  69 USE_FEATURE_FIND_INUM(  ACTS(inum,  ino_t inode_num;))
  70 USE_FEATURE_FIND_EXEC(  ACTS(exec,  char **exec_argv; int *subst_count; int exec_argc;))
  71 USE_DESKTOP(            ACTS(paren, action ***subexpr;))
  72 USE_DESKTOP(            ACTS(size,  off_t size;))
  73 USE_DESKTOP(            ACTS(prune))
  74
  75 static action ***actions;
  76 static int need_print = 1;
  77
  78 static inline int one_char(const char* str, char c)
  79 {
  80         return (str[0] == c && str[1] == '\0');
  81 }
  82
  83
  84 static int count_subst(const char *str)
  85 {
  86         int count = 0;
  87         while ((str = strstr(str, "{}"))) {
  88                 count++;
  89                 str++;
  90         }
  91         return count;
  92 }
  93
  94
  95 static char* subst(const char *src, int count, const char* filename)
  96 {
  97         char *buf, *dst, *end;
  98         int flen = strlen(filename);
  99         /* we replace each '{}' with filename: growth by strlen-2 */
 100         buf = dst = xmalloc(strlen(src) + count*(flen-2) + 1);
 101         while ((end = strstr(src, "{}"))) {
 102                 memcpy(dst, src, end - src);
 103                 dst += end - src;
 104                 src = end + 2;
 105                 memcpy(dst, filename, flen);
 106                 dst += flen;
 107         }
 108         strcpy(dst, src);
 109         return buf;
 110 }
 111
 112
 113 static int exec_actions(action ***appp, const char *fileName, struct stat *statbuf)
 114 {
 115         int cur_group;
 116         int cur_action;
 117         int rc = TRUE;
 118         action **app, *ap;
 119
 120         cur_group = -1;
 121         while ((app = appp[++cur_group])) {
 122                 cur_action = -1;
 123                 do {
 124                         ap = app[++cur_action];
 125                 } while (ap && (rc = ap->f(fileName, statbuf, ap)));
 126                 if (!ap) {
 127                         /* all actions in group were successful */
 128                         break;
 129                 }
 130         }
 131         return rc;
 132 }
 133
 134
 135 ACTF(name)
 136 {
 137         const char *tmp = strrchr(fileName, '/');
 138         if (tmp == NULL)
 139                 tmp = fileName;
 140         else
 141                 tmp++;
 142         return fnmatch(ap->pattern, tmp, FNM_PERIOD) == 0;
 143 }
 144 #if ENABLE_FEATURE_FIND_TYPE
 145 ACTF(type)
 146 {
 147         return ((statbuf->st_mode & S_IFMT) == ap->type_mask);
 148 }
 149 #endif
 150 #if ENABLE_FEATURE_FIND_PERM
 151 ACTF(perm)
 152 {
 153         return !((isdigit(ap->perm_char) && (statbuf->st_mode & 07777) == ap->perm_mask)
 154                 || (ap->perm_char == '-' && (statbuf->st_mode & ap->perm_mask) == ap->perm_mask)
 155                 || (ap->perm_char == '+' && (statbuf->st_mode & ap->perm_mask) != 0));
 156 }
 157 #endif
 158 #if ENABLE_FEATURE_FIND_MTIME
 159 ACTF(mtime)
 160 {
 161         time_t file_age = time(NULL) - statbuf->st_mtime;
 162         time_t mtime_secs = ap->mtime_days * 24 * 60 * 60;
 163         return !((isdigit(ap->mtime_char) && file_age >= mtime_secs
 164                                           && file_age < mtime_secs + 24 * 60 * 60)
 165                 || (ap->mtime_char == '+' && file_age >= mtime_secs + 24 * 60 * 60)
 166                 || (ap->mtime_char == '-' && file_age < mtime_secs));
 167 }
 168 #endif
 169 #if ENABLE_FEATURE_FIND_MMIN
 170 ACTF(mmin)
 171 {
 172         time_t file_age = time(NULL) - statbuf->st_mtime;
 173         time_t mmin_secs = ap->mmin_mins * 60;
 174         return !((isdigit(ap->mmin_char) && file_age >= mmin_secs
 175                                          && file_age < mmin_secs + 60)
 176                 || (ap->mmin_char == '+' && file_age >= mmin_secs + 60)
 177                 || (ap->mmin_char == '-' && file_age < mmin_secs));
 178 }
 179 #endif
 180 #if ENABLE_FEATURE_FIND_NEWER
 181 ACTF(newer)
 182 {
 183         return (ap->newer_mtime >= statbuf->st_mtime);
 184 }
 185 #endif
 186 #if ENABLE_FEATURE_FIND_INUM
 187 ACTF(inum)
 188 {
 189         return (statbuf->st_ino != ap->inode_num);
 190 }
 191 #endif
 192 #if ENABLE_FEATURE_FIND_EXEC
 193 ACTF(exec)
 194 {
 195         int i, rc;
 196         char *argv[ap->exec_argc+1];
 197         for (i = 0; i < ap->exec_argc; i++)
 198                 argv[i] = subst(ap->exec_argv[i], ap->subst_count[i], fileName);
 199         argv[i] = NULL; /* terminate the list */
 200         errno = 0;
 201         rc = wait4pid(spawn(argv));
 202         if (errno)
 203                 bb_perror_msg("%s", argv[0]);
 204         for (i = 0; i < ap->exec_argc; i++)
 205                 free(argv[i]);
 206         return rc == 0; /* return 1 if success */
 207 }
 208 #endif
 209
 210 #if ENABLE_FEATURE_FIND_PRINT0
 211 ACTF(print0)
 212 {
 213         printf("%s%c", fileName, '\0');
 214         return TRUE;
 215 }
 216 #endif
 217
 218 ACTF(print)
 219 {
 220         puts(fileName);
 221         return TRUE;
 222 }
 223
 224 #if ENABLE_DESKTOP
 225 ACTF(paren)
 226 {
 227         return exec_actions(ap->subexpr, fileName, statbuf);
 228 }
 229
 230 /*
 231  * -prune: if -depth is not given, return true and do not descend
 232  * current dir; if -depth is given, return false with no effect.
 233  * Example:
 234  * find dir -name 'asm-*' -prune -o -name '*.[chS]' -print
 235  */
 236 ACTF(prune)
 237 {
 238         return SKIP;
 239 }
 240
 241 ACTF(size)
 242 {
 243         return statbuf->st_size == ap->size;
 244 }
 245 #endif
 246
 247
 248 static int fileAction(const char *fileName, struct stat *statbuf, void* junk, int depth)
 249 {
 250         int rc;
 251 #ifdef CONFIG_FEATURE_FIND_XDEV
 252         if (S_ISDIR(statbuf->st_mode) && xdev_count) {
 253                 int i;
 254                 for (i = 0; i < xdev_count; i++) {
 255                         if (xdev_dev[i] != statbuf->st_dev)
 256                                 return SKIP;
 257                 }
 258         }
 259 #endif
 260         rc = exec_actions(actions, fileName, statbuf);
 261         /* Had no explicit -print[0] or -exec? then print */
 262         if (rc && need_print)
 263                 puts(fileName);
 264         /* Cannot return 0: our caller, recursive_action(),
 265          * will perror() and skip dirs (if called on dir) */
 266         return rc == 0 ? TRUE : rc;
 267 }
 268
 269
 270 #if ENABLE_FEATURE_FIND_TYPE
 271 static int find_type(char *type)
 272 {
 273         int mask = 0;
 274
 275         switch (type[0]) {
 276         case 'b':
 277                 mask = S_IFBLK;
 278                 break;
 279         case 'c':
 280                 mask = S_IFCHR;
 281                 break;
 282         case 'd':
 283                 mask = S_IFDIR;
 284                 break;
 285         case 'p':
 286                 mask = S_IFIFO;
 287                 break;
 288         case 'f':
 289                 mask = S_IFREG;
 290                 break;
 291         case 'l':
 292                 mask = S_IFLNK;
 293                 break;
 294         case 's':
 295                 mask = S_IFSOCK;
 296                 break;
 297         }
 298
 299         if (mask == 0 || type[1] != '\0')
 300                 bb_error_msg_and_die(bb_msg_invalid_arg, type, "-type");
 301
 302         return mask;
 303 }
 304 #endif
 305
 306 action*** parse_params(char **argv)
 307 {
 308         action*** appp;
 309         int cur_group = 0;
 310         int cur_action = 0;
 311
 312         action* alloc_action(int sizeof_struct, action_fp f)
 313         {
 314                 action *ap;
 315                 appp[cur_group] = xrealloc(appp[cur_group], (cur_action+2) * sizeof(*appp));
 316                 appp[cur_group][cur_action++] = ap = xmalloc(sizeof_struct);
 317                 appp[cur_group][cur_action] = NULL;
 318                 ap->f = f;
 319                 return ap;
 320         }
 321 #define ALLOC_ACTION(name) (action_##name*)alloc_action(sizeof(action_##name), (action_fp) func_##name)
 322
 323         appp = xzalloc(2 * sizeof(*appp)); /* appp[0],[1] == NULL */
 324
 325 // Actions have side effects and return a true or false value
 326 // We implement: -print, -print0, -exec
 327
 328 // The rest are tests.
 329
 330 // Tests and actions are grouped by operators
 331 // ( expr )              Force precedence
 332 // ! expr                True if expr is false
 333 // -not expr             Same as ! expr
 334 // expr1 [-a[nd]] expr2  And; expr2 is not evaluated if expr1 is false
 335 // expr1 -o[r] expr2     Or; expr2 is not evaluated if expr1 is true
 336 // expr1 , expr2         List; both expr1 and expr2 are always evaluated
 337 // We implement: (), -a, -o
 338
 339         while (*argv) {
 340                 char *arg = argv[0];
 341                 char *arg1 = argv[1];
 342         /* --- Operators --- */
 343                 if (strcmp(arg, "-a") == 0
 344                     USE_DESKTOP(|| strcmp(arg, "-and") == 0)
 345                 ) {
 346                         /* no special handling required */
 347                 }
 348                 else if (strcmp(arg, "-o") == 0
 349                          USE_DESKTOP(|| strcmp(arg, "-or") == 0)
 350                 ) {
 351                         /* start new OR group */
 352                         cur_group++;
 353                         appp = xrealloc(appp, (cur_group+2) * sizeof(*appp));
 354                         appp[cur_group] = NULL;
 355                         appp[cur_group+1] = NULL;
 356                         cur_action = 0;
 357                 }
 358
 359         /* --- Tests and actions --- */
 360                 else if (strcmp(arg, "-print") == 0) {
 361                         need_print = 0;
 362                         (void) ALLOC_ACTION(print);
 363                 }
 364 #if ENABLE_FEATURE_FIND_PRINT0
 365                 else if (strcmp(arg, "-print0") == 0) {
 366                         need_print = 0;
 367                         (void) ALLOC_ACTION(print0);
 368                 }
 369 #endif
 370                 else if (strcmp(arg, "-name") == 0) {
 371                         action_name *ap;
 372                         if (!*++argv)
 373                                 bb_error_msg_and_die(bb_msg_requires_arg, arg);
 374                         ap = ALLOC_ACTION(name);
 375                         ap->pattern = arg1;
 376                 }
 377 #if ENABLE_FEATURE_FIND_TYPE
 378                 else if (strcmp(arg, "-type") == 0) {
 379                         action_type *ap;
 380                         if (!*++argv)
 381                                 bb_error_msg_and_die(bb_msg_requires_arg, arg);
 382                         ap = ALLOC_ACTION(type);
 383                         ap->type_mask = find_type(arg1);
 384                 }
 385 #endif
 386 #if ENABLE_FEATURE_FIND_PERM
 387 /* TODO:
 388  * -perm mode   File's permission bits are exactly mode (octal or symbolic).
 389  *              Symbolic modes use mode 0 as a point of departure.
 390  * -perm -mode  All of the permission bits mode are set for the file.
 391  * -perm +mode  Any of the permission bits mode are set for the file.
 392  */
 393                 else if (strcmp(arg, "-perm") == 0) {
 394                         action_perm *ap;
 395                         if (!*++argv)
 396                                 bb_error_msg_and_die(bb_msg_requires_arg, arg);
 397                         ap = ALLOC_ACTION(perm);
 398                         ap->perm_mask = xstrtol_range(arg1, 8, 0, 07777);
 399                         ap->perm_char = arg1[0];
 400                         if (ap->perm_char == '-')
 401                                 ap->perm_mask = -ap->perm_mask;
 402                 }
 403 #endif
 404 #if ENABLE_FEATURE_FIND_MTIME
 405                 else if (strcmp(arg, "-mtime") == 0) {
 406                         action_mtime *ap;
 407                         if (!*++argv)
 408                                 bb_error_msg_and_die(bb_msg_requires_arg, arg);
 409                         ap = ALLOC_ACTION(mtime);
 410                         ap->mtime_days = xatol(arg1);
 411                         ap->mtime_char = arg1[0];
 412                         if (ap->mtime_char == '-')
 413                                 ap->mtime_days = -ap->mtime_days;
 414                 }
 415 #endif
 416 #if ENABLE_FEATURE_FIND_MMIN
 417                 else if (strcmp(arg, "-mmin") == 0) {
 418                         action_mmin *ap;
 419                         if (!*++argv)
 420                                 bb_error_msg_and_die(bb_msg_requires_arg, arg);
 421                         ap = ALLOC_ACTION(mmin);
 422                         ap->mmin_mins = xatol(arg1);
 423                         ap->mmin_char = arg1[0];
 424                         if (ap->mmin_char == '-')
 425                                 ap->mmin_mins = -ap->mmin_mins;
 426                 }
 427 #endif
 428 #if ENABLE_FEATURE_FIND_NEWER
 429                 else if (strcmp(arg, "-newer") == 0) {
 430                         action_newer *ap;
 431                         struct stat stat_newer;
 432                         if (!*++argv)
 433                                 bb_error_msg_and_die(bb_msg_requires_arg, arg);
 434                         xstat(arg1, &stat_newer);
 435                         ap = ALLOC_ACTION(newer);
 436                         ap->newer_mtime = stat_newer.st_mtime;
 437                 }
 438 #endif
 439 #if ENABLE_FEATURE_FIND_INUM
 440                 else if (strcmp(arg, "-inum") == 0) {
 441                         action_inum *ap;
 442                         if (!*++argv)
 443                                 bb_error_msg_and_die(bb_msg_requires_arg, arg);
 444                         ap = ALLOC_ACTION(inum);
 445                         ap->inode_num = xatoul(arg1);
 446                 }
 447 #endif
 448 #if ENABLE_FEATURE_FIND_EXEC
 449                 else if (strcmp(arg, "-exec") == 0) {
 450                         int i;
 451                         action_exec *ap;
 452                         need_print = 0;
 453                         ap = ALLOC_ACTION(exec);
 454                         ap->exec_argv = ++argv; /* first arg after -exec */
 455                         ap->exec_argc = 0;
 456                         while (1) {
 457                                 if (!*argv) /* did not see ';' till end */
 458                                         bb_error_msg_and_die(bb_msg_requires_arg, arg);
 459                                 if (one_char(argv[0], ';'))
 460                                         break;
 461                                 argv++;
 462                                 ap->exec_argc++;
 463                         }
 464                         if (ap->exec_argc == 0)
 465                                 bb_error_msg_and_die(bb_msg_requires_arg, arg);
 466                         ap->subst_count = xmalloc(ap->exec_argc * sizeof(int));
 467                         i = ap->exec_argc;
 468                         while (i--)
 469                                 ap->subst_count[i] = count_subst(ap->exec_argv[i]);
 470                 }
 471 #endif
 472 #if ENABLE_DESKTOP
 473                 else if (one_char(arg, '(')) {
 474                         action_paren *ap;
 475                         char **endarg;
 476                         int nested = 1;
 477
 478                         endarg = argv;
 479                         while (1) {
 480                                 if (!*++endarg)
 481                                         bb_error_msg_and_die("unpaired '('");
 482                                 if (one_char(*endarg, '('))
 483                                         nested++;
 484                                 else if (one_char(*endarg, ')') && !--nested) {
 485                                         *endarg = NULL;
 486                                         break;
 487                                 }
 488                         }
 489                         ap = ALLOC_ACTION(paren);
 490                         ap->subexpr = parse_params(argv + 1);
 491                         *endarg = ")"; /* restore NULLed parameter */
 492                         argv = endarg;
 493                 }
 494                 else if (strcmp(arg, "-prune") == 0) {
 495                         (void) ALLOC_ACTION(prune);
 496                 }
 497                 else if (strcmp(arg, "-size") == 0) {
 498                         action_size *ap;
 499                         if (!*++argv)
 500                                 bb_error_msg_and_die(bb_msg_requires_arg, arg);
 501                         ap = ALLOC_ACTION(size);
 502                         ap->size = XATOOFF(arg1);
 503                 }
 504 #endif
 505                 else
 506                         bb_show_usage();
 507                 argv++;
 508         }
 509
 510         return appp;
 511 #undef ALLOC_ACTION
 512 }
 513
 514
 515 int find_main(int argc, char **argv)
 516 {
 517         int dereference = FALSE;
 518         char *arg;
 519         char **argp;
 520         int i, firstopt, status = EXIT_SUCCESS;
 521
 522         for (firstopt = 1; firstopt < argc; firstopt++) {
 523                 if (argv[firstopt][0] == '-')
 524                         break;
 525 #if ENABLE_DESKTOP
 526                 if (one_char(argv[firstopt], '('))
 527                         break;
 528 #endif
 529         }
 530         if (firstopt == 1) {
 531                 argv[0] = ".";
 532                 argv--;
 533                 firstopt++;
 534         }
 535
 536 // All options always return true. They always take effect,
 537 // rather than being processed only when their place in the
 538 // expression is reached
 539 // We implement: -follow, -xdev
 540
 541         /* Process options, and replace then with -a */
 542         /* (-a will be ignored by recursive parser later) */
 543         argp = &argv[firstopt];
 544         while ((arg = argp[0])) {
 545                 if (strcmp(arg, "-follow") == 0) {
 546                         dereference = TRUE;
 547                         argp[0] = "-a";
 548                 }
 549 #if ENABLE_FEATURE_FIND_XDEV
 550                 else if (strcmp(arg, "-xdev") == 0) {
 551                         struct stat stbuf;
 552                         if (!xdev_count) {
 553                                 xdev_count = firstopt - 1;
 554                                 xdev_dev = xmalloc(xdev_count * sizeof(dev_t));
 555                                 for (i = 1; i < firstopt; i++) {
 556                                         /* not xstat(): shouldn't bomb out on
 557                                          * "find not_exist exist -xdev" */
 558                                         if (stat(argv[i], &stbuf)) stbuf.st_dev = -1L;
 559                                         xdev_dev[i-1] = stbuf.st_dev;
 560                                 }
 561                         }
 562                         argp[0] = "-a";
 563                 }
 564                 argp++;
 565         }
 566 #endif
 567
 568         actions = parse_params(&argv[firstopt]);
 569
 570         for (i = 1; i < firstopt; i++) {
 571                 if (!recursive_action(argv[i],
 572                                 TRUE,           // recurse
 573                                 dereference,    // follow links
 574                                 FALSE,          // depth first
 575                                 fileAction,     // file action
 576                                 fileAction,     // dir action
 577                                 NULL,           // user data
 578                                 0))             // depth
 579                         status = EXIT_FAILURE;
 580         }
 581         return status;
 582 }