find: fix -not support
[oweals/busybox.git] / 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 <fnmatch.h>
49 #include "busybox.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 #if ENABLE_FEATURE_FIND_NOT
59         smallint invert;
60 #endif
61 } action;
62 #define ACTS(name, arg...) typedef struct { action a; arg; } action_##name;
63 #define ACTF(name)         static int func_##name(const char *fileName, struct stat *statbuf, action_##name* ap)
64                         ACTS(print)
65                         ACTS(name,  const char *pattern;)
66 USE_FEATURE_FIND_PRINT0(ACTS(print0))
67 USE_FEATURE_FIND_TYPE(  ACTS(type,  int type_mask;))
68 USE_FEATURE_FIND_PERM(  ACTS(perm,  char perm_char; mode_t perm_mask;))
69 USE_FEATURE_FIND_MTIME( ACTS(mtime, char mtime_char; unsigned mtime_days;))
70 USE_FEATURE_FIND_MMIN(  ACTS(mmin,  char mmin_char; unsigned mmin_mins;))
71 USE_FEATURE_FIND_NEWER( ACTS(newer, time_t newer_mtime;))
72 USE_FEATURE_FIND_INUM(  ACTS(inum,  ino_t inode_num;))
73 USE_FEATURE_FIND_EXEC(  ACTS(exec,  char **exec_argv; unsigned int *subst_count; int exec_argc;))
74 USE_FEATURE_FIND_USER(  ACTS(user,  int uid;))
75 USE_DESKTOP(            ACTS(paren, action ***subexpr;))
76 USE_DESKTOP(            ACTS(size,  off_t size;))
77 USE_DESKTOP(            ACTS(prune))
78
79 static action ***actions;
80 static smalluint need_print = 1;
81
82
83 #if ENABLE_FEATURE_FIND_EXEC
84 static unsigned int count_subst(const char *str)
85 {
86         unsigned 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, unsigned 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 #endif
112
113
114 static int exec_actions(action ***appp, const char *fileName, struct stat *statbuf)
115 {
116         int cur_group;
117         int cur_action;
118         int rc = TRUE;
119         action **app, *ap;
120
121         cur_group = -1;
122         while ((app = appp[++cur_group])) {
123                 cur_action = -1;
124                 while (1) {
125                         ap = app[++cur_action];
126                         if (!ap) {
127                                 /* all actions in group were successful */
128                                 return rc;
129                         }
130                         rc = ap->f(fileName, statbuf, ap);
131 #if ENABLE_FEATURE_FIND_NOT
132                         if (ap->invert) rc = !rc;
133 #endif
134                         if (!rc) {
135                                 /* current group failed, try next */
136                                 break;
137                         }
138                 }
139         }
140         return rc;
141 }
142
143
144 ACTF(name)
145 {
146         const char *tmp = strrchr(fileName, '/');
147         if (tmp == NULL)
148                 tmp = fileName;
149         else
150                 tmp++;
151         return fnmatch(ap->pattern, tmp, FNM_PERIOD) == 0;
152 }
153 #if ENABLE_FEATURE_FIND_TYPE
154 ACTF(type)
155 {
156         return ((statbuf->st_mode & S_IFMT) == ap->type_mask);
157 }
158 #endif
159 #if ENABLE_FEATURE_FIND_PERM
160 ACTF(perm)
161 {
162         /* -perm +mode: at least one of perm_mask bits are set */
163         if (ap->perm_char == '+')
164                 return (statbuf->st_mode & ap->perm_mask) != 0;
165         /* -perm -mode: all of perm_mask are set */
166         if (ap->perm_char == '-')
167                 return (statbuf->st_mode & ap->perm_mask) == ap->perm_mask;
168         /* -perm mode: file mode must match perm_mask */
169         return (statbuf->st_mode & 07777) == ap->perm_mask;
170 }
171 #endif
172 #if ENABLE_FEATURE_FIND_MTIME
173 ACTF(mtime)
174 {
175         time_t file_age = time(NULL) - statbuf->st_mtime;
176         time_t mtime_secs = ap->mtime_days * 24*60*60;
177         if (ap->mtime_char == '+')
178                 return file_age >= mtime_secs + 24*60*60;
179         if (ap->mtime_char == '-')
180                 return file_age < mtime_secs;
181         /* just numeric mtime */
182         return file_age >= mtime_secs && file_age < (mtime_secs + 24*60*60);
183 }
184 #endif
185 #if ENABLE_FEATURE_FIND_MMIN
186 ACTF(mmin)
187 {
188         time_t file_age = time(NULL) - statbuf->st_mtime;
189         time_t mmin_secs = ap->mmin_mins * 60;
190         if (ap->mmin_char == '+')
191                 return file_age >= mmin_secs + 60;
192         if (ap->mmin_char == '-')
193                 return file_age < mmin_secs;
194         /* just numeric mmin */
195         return file_age >= mmin_secs && file_age < (mmin_secs + 60);
196 }
197 #endif
198 #if ENABLE_FEATURE_FIND_NEWER
199 ACTF(newer)
200 {
201         return (ap->newer_mtime < statbuf->st_mtime);
202 }
203 #endif
204 #if ENABLE_FEATURE_FIND_INUM
205 ACTF(inum)
206 {
207         return (statbuf->st_ino == ap->inode_num);
208 }
209 #endif
210 #if ENABLE_FEATURE_FIND_EXEC
211 ACTF(exec)
212 {
213         int i, rc;
214         char *argv[ap->exec_argc+1];
215         for (i = 0; i < ap->exec_argc; i++)
216                 argv[i] = subst(ap->exec_argv[i], ap->subst_count[i], fileName);
217         argv[i] = NULL; /* terminate the list */
218         rc = wait4pid(spawn(argv));
219         if (rc)
220                 bb_perror_msg("%s", argv[0]);
221         for (i = 0; i < ap->exec_argc; i++)
222                 free(argv[i]);
223         return rc == 0; /* return 1 if success */
224 }
225 #endif
226
227 #if ENABLE_FEATURE_FIND_USER
228 ACTF(user)
229 {
230         return (statbuf->st_uid == ap->uid);
231 }
232 #endif
233
234 #if ENABLE_FEATURE_FIND_PRINT0
235 ACTF(print0)
236 {
237         printf("%s%c", fileName, '\0');
238         return TRUE;
239 }
240 #endif
241
242 ACTF(print)
243 {
244         puts(fileName);
245         return TRUE;
246 }
247
248 #if ENABLE_DESKTOP
249 ACTF(paren)
250 {
251         return exec_actions(ap->subexpr, fileName, statbuf);
252 }
253
254 /*
255  * -prune: if -depth is not given, return true and do not descend
256  * current dir; if -depth is given, return false with no effect.
257  * Example:
258  * find dir -name 'asm-*' -prune -o -name '*.[chS]' -print
259  */
260 ACTF(prune)
261 {
262         return SKIP;
263 }
264
265 ACTF(size)
266 {
267         return statbuf->st_size == ap->size;
268 }
269 #endif
270
271
272 static int fileAction(const char *fileName, struct stat *statbuf, void* junk, int depth)
273 {
274         int rc;
275 #ifdef CONFIG_FEATURE_FIND_XDEV
276         if (S_ISDIR(statbuf->st_mode) && xdev_count) {
277                 int i;
278                 for (i = 0; i < xdev_count; i++) {
279                         if (xdev_dev[i] != statbuf->st_dev)
280                                 return SKIP;
281                 }
282         }
283 #endif
284         rc = exec_actions(actions, fileName, statbuf);
285         /* Had no explicit -print[0] or -exec? then print */
286         if (rc && need_print)
287                 puts(fileName);
288         /* Cannot return 0: our caller, recursive_action(),
289          * will perror() and skip dirs (if called on dir) */
290         return rc == 0 ? TRUE : rc;
291 }
292
293
294 #if ENABLE_FEATURE_FIND_TYPE
295 static int find_type(const char *type)
296 {
297         int mask = 0;
298
299         switch (type[0]) {
300         case 'b':
301                 mask = S_IFBLK;
302                 break;
303         case 'c':
304                 mask = S_IFCHR;
305                 break;
306         case 'd':
307                 mask = S_IFDIR;
308                 break;
309         case 'p':
310                 mask = S_IFIFO;
311                 break;
312         case 'f':
313                 mask = S_IFREG;
314                 break;
315         case 'l':
316                 mask = S_IFLNK;
317                 break;
318         case 's':
319                 mask = S_IFSOCK;
320                 break;
321         }
322
323         if (mask == 0 || type[1] != '\0')
324                 bb_error_msg_and_die(bb_msg_invalid_arg, type, "-type");
325
326         return mask;
327 }
328 #endif
329
330 #if ENABLE_FEATURE_FIND_PERM || ENABLE_FEATURE_FIND_MTIME \
331  || ENABLE_FEATURE_FIND_MMIN
332 static const char* plus_minus_num(const char* str)
333 {
334         if (*str == '-' || *str == '+')
335                 str++;
336         return str;
337 }
338 #endif
339
340 static action*** parse_params(char **argv)
341 {
342         action*** appp;
343         unsigned cur_group = 0;
344         unsigned cur_action = 0;
345         USE_FEATURE_FIND_NOT( smallint invert_flag = 0; )
346
347         action* alloc_action(int sizeof_struct, action_fp f)
348         {
349                 action *ap;
350                 appp[cur_group] = xrealloc(appp[cur_group], (cur_action+2) * sizeof(*appp));
351                 appp[cur_group][cur_action++] = ap = xmalloc(sizeof_struct);
352                 appp[cur_group][cur_action] = NULL;
353                 ap->f = f;
354                 USE_FEATURE_FIND_NOT( ap->invert = invert_flag; )
355                 USE_FEATURE_FIND_NOT( invert_flag = 0; )
356                 return ap;
357         }
358 #define ALLOC_ACTION(name) (action_##name*)alloc_action(sizeof(action_##name), (action_fp) func_##name)
359
360         appp = xzalloc(2 * sizeof(appp[0])); /* appp[0],[1] == NULL */
361
362 // Actions have side effects and return a true or false value
363 // We implement: -print, -print0, -exec
364
365 // The rest are tests.
366
367 // Tests and actions are grouped by operators
368 // ( expr )              Force precedence
369 // ! expr                True if expr is false
370 // -not expr             Same as ! expr
371 // expr1 [-a[nd]] expr2  And; expr2 is not evaluated if expr1 is false
372 // expr1 -o[r] expr2     Or; expr2 is not evaluated if expr1 is true
373 // expr1 , expr2         List; both expr1 and expr2 are always evaluated
374 // We implement: (), -a, -o
375
376 //XXX: TODO: Use index_in_str_array here
377         while (*argv) {
378                 const char *arg = argv[0];
379                 const char *arg1 = argv[1];
380         /* --- Operators --- */
381                 if (strcmp(arg, "-a") == 0
382                     USE_DESKTOP(|| strcmp(arg, "-and") == 0)
383                 ) {
384                         /* no further special handling required */
385                 }
386                 else if (strcmp(arg, "-o") == 0
387                          USE_DESKTOP(|| strcmp(arg, "-or") == 0)
388                 ) {
389                         /* start new OR group */
390                         cur_group++;
391                         appp = xrealloc(appp, (cur_group+2) * sizeof(*appp));
392                         /*appp[cur_group] = NULL; - already NULL */
393                         appp[cur_group+1] = NULL;
394                         cur_action = 0;
395                 }
396 #if ENABLE_FEATURE_FIND_NOT
397                 else if (LONE_CHAR(arg, '!')
398                          USE_DESKTOP(|| strcmp(arg, "-not") == 0)
399                 ) {
400                         /* also handles "find ! ! -name 'foo*'" */
401                         invert_flag ^= 1;
402                 }
403 #endif
404
405         /* --- Tests and actions --- */
406                 else if (strcmp(arg, "-print") == 0) {
407                         need_print = 0;
408                         /* GNU find ignores '!' here: "find ! -print" */
409                         USE_FEATURE_FIND_NOT( invert_flag = 0; )
410                         (void) ALLOC_ACTION(print);
411                 }
412 #if ENABLE_FEATURE_FIND_PRINT0
413                 else if (strcmp(arg, "-print0") == 0) {
414                         need_print = 0;
415                         USE_FEATURE_FIND_NOT( invert_flag = 0; )
416                         (void) ALLOC_ACTION(print0);
417                 }
418 #endif
419                 else if (strcmp(arg, "-name") == 0) {
420                         action_name *ap;
421                         if (!*++argv)
422                                 bb_error_msg_and_die(bb_msg_requires_arg, arg);
423                         ap = ALLOC_ACTION(name);
424                         ap->pattern = arg1;
425                 }
426 #if ENABLE_FEATURE_FIND_TYPE
427                 else if (strcmp(arg, "-type") == 0) {
428                         action_type *ap;
429                         if (!*++argv)
430                                 bb_error_msg_and_die(bb_msg_requires_arg, arg);
431                         ap = ALLOC_ACTION(type);
432                         ap->type_mask = find_type(arg1);
433                 }
434 #endif
435 #if ENABLE_FEATURE_FIND_PERM
436 /* TODO:
437  * -perm mode   File's permission bits are exactly mode (octal or symbolic).
438  *              Symbolic modes use mode 0 as a point of departure.
439  * -perm -mode  All of the permission bits mode are set for the file.
440  * -perm +mode  Any of the permission bits mode are set for the file.
441  */
442                 else if (strcmp(arg, "-perm") == 0) {
443                         action_perm *ap;
444                         if (!*++argv)
445                                 bb_error_msg_and_die(bb_msg_requires_arg, arg);
446                         ap = ALLOC_ACTION(perm);
447                         ap->perm_char = arg1[0];
448                         arg1 = plus_minus_num(arg1);
449                         ap->perm_mask = 0;
450                         if (!bb_parse_mode(arg1, &ap->perm_mask))
451                                 bb_error_msg_and_die("invalid mode: %s", arg1);
452                 }
453 #endif
454 #if ENABLE_FEATURE_FIND_MTIME
455                 else if (strcmp(arg, "-mtime") == 0) {
456                         action_mtime *ap;
457                         if (!*++argv)
458                                 bb_error_msg_and_die(bb_msg_requires_arg, arg);
459                         ap = ALLOC_ACTION(mtime);
460                         ap->mtime_char = arg1[0];
461                         ap->mtime_days = xatoul(plus_minus_num(arg1));
462                 }
463 #endif
464 #if ENABLE_FEATURE_FIND_MMIN
465                 else if (strcmp(arg, "-mmin") == 0) {
466                         action_mmin *ap;
467                         if (!*++argv)
468                                 bb_error_msg_and_die(bb_msg_requires_arg, arg);
469                         ap = ALLOC_ACTION(mmin);
470                         ap->mmin_char = arg1[0];
471                         ap->mmin_mins = xatoul(plus_minus_num(arg1));
472                 }
473 #endif
474 #if ENABLE_FEATURE_FIND_NEWER
475                 else if (strcmp(arg, "-newer") == 0) {
476                         action_newer *ap;
477                         struct stat stat_newer;
478                         if (!*++argv)
479                                 bb_error_msg_and_die(bb_msg_requires_arg, arg);
480                         xstat(arg1, &stat_newer);
481                         ap = ALLOC_ACTION(newer);
482                         ap->newer_mtime = stat_newer.st_mtime;
483                 }
484 #endif
485 #if ENABLE_FEATURE_FIND_INUM
486                 else if (strcmp(arg, "-inum") == 0) {
487                         action_inum *ap;
488                         if (!*++argv)
489                                 bb_error_msg_and_die(bb_msg_requires_arg, arg);
490                         ap = ALLOC_ACTION(inum);
491                         ap->inode_num = xatoul(arg1);
492                 }
493 #endif
494 #if ENABLE_FEATURE_FIND_EXEC
495                 else if (strcmp(arg, "-exec") == 0) {
496                         int i;
497                         action_exec *ap;
498                         need_print = 0;
499                         USE_FEATURE_FIND_NOT( invert_flag = 0; )
500                         ap = ALLOC_ACTION(exec);
501                         ap->exec_argv = ++argv; /* first arg after -exec */
502                         ap->exec_argc = 0;
503                         while (1) {
504                                 if (!*argv) /* did not see ';' till end */
505                                         bb_error_msg_and_die(bb_msg_requires_arg, arg);
506                                 if (LONE_CHAR(argv[0], ';'))
507                                         break;
508                                 argv++;
509                                 ap->exec_argc++;
510                         }
511                         if (ap->exec_argc == 0)
512                                 bb_error_msg_and_die(bb_msg_requires_arg, arg);
513                         ap->subst_count = xmalloc(ap->exec_argc * sizeof(int));
514                         i = ap->exec_argc;
515                         while (i--)
516                                 ap->subst_count[i] = count_subst(ap->exec_argv[i]);
517                 }
518 #endif
519 #if ENABLE_FEATURE_FIND_USER
520                 else if (strcmp(arg, "-user") == 0) {
521                         action_user *ap;
522                         if (!*++argv)
523                                 bb_error_msg_and_die(bb_msg_requires_arg, arg);
524                         ap = ALLOC_ACTION(user);
525                         ap->uid = bb_strtou(arg1, NULL, 10);
526                         if (errno)
527                                 ap->uid = xuname2uid(arg1);
528                 }
529 #endif
530 #if ENABLE_DESKTOP
531                 else if (LONE_CHAR(arg, '(')) {
532                         action_paren *ap;
533                         char **endarg;
534                         unsigned nested = 1;
535
536                         endarg = argv;
537                         while (1) {
538                                 if (!*++endarg)
539                                         bb_error_msg_and_die("unpaired '('");
540                                 if (LONE_CHAR(*endarg, '('))
541                                         nested++;
542                                 else if (LONE_CHAR(*endarg, ')') && !--nested) {
543                                         *endarg = NULL;
544                                         break;
545                                 }
546                         }
547                         ap = ALLOC_ACTION(paren);
548                         ap->subexpr = parse_params(argv + 1);
549                         *endarg = (char*) ")"; /* restore NULLed parameter */
550                         argv = endarg;
551                 }
552                 else if (strcmp(arg, "-prune") == 0) {
553                         USE_FEATURE_FIND_NOT( invert_flag = 0; )
554                         (void) ALLOC_ACTION(prune);
555                 }
556                 else if (strcmp(arg, "-size") == 0) {
557                         action_size *ap;
558                         if (!*++argv)
559                                 bb_error_msg_and_die(bb_msg_requires_arg, arg);
560                         ap = ALLOC_ACTION(size);
561                         ap->size = XATOOFF(arg1);
562                 }
563 #endif
564                 else
565                         bb_show_usage();
566                 argv++;
567         }
568
569         return appp;
570 #undef ALLOC_ACTION
571 }
572
573
574 int find_main(int argc, char **argv);
575 int find_main(int argc, char **argv)
576 {
577         int dereference = FALSE;
578         char *arg;
579         char **argp;
580         int i, firstopt, status = EXIT_SUCCESS;
581
582         for (firstopt = 1; firstopt < argc; firstopt++) {
583                 if (argv[firstopt][0] == '-')
584                         break;
585                 if (ENABLE_FEATURE_FIND_NOT && LONE_CHAR(argv[firstopt], '!'))
586                         break;
587 #if ENABLE_DESKTOP
588                 if (LONE_CHAR(argv[firstopt], '('))
589                         break;
590 #endif
591         }
592         if (firstopt == 1) {
593                 argv[0] = (char*)".";
594                 argv--;
595                 firstopt++;
596         }
597
598 // All options always return true. They always take effect,
599 // rather than being processed only when their place in the
600 // expression is reached
601 // We implement: -follow, -xdev
602
603         /* Process options, and replace then with -a */
604         /* (-a will be ignored by recursive parser later) */
605         argp = &argv[firstopt];
606         while ((arg = argp[0])) {
607                 if (strcmp(arg, "-follow") == 0) {
608                         dereference = TRUE;
609                         argp[0] = (char*)"-a";
610                 }
611 #if ENABLE_FEATURE_FIND_XDEV
612                 else if (strcmp(arg, "-xdev") == 0) {
613                         struct stat stbuf;
614                         if (!xdev_count) {
615                                 xdev_count = firstopt - 1;
616                                 xdev_dev = xmalloc(xdev_count * sizeof(dev_t));
617                                 for (i = 1; i < firstopt; i++) {
618                                         /* not xstat(): shouldn't bomb out on
619                                          * "find not_exist exist -xdev" */
620                                         if (stat(argv[i], &stbuf))
621                                                 stbuf.st_dev = -1L;
622                                         xdev_dev[i-1] = stbuf.st_dev;
623                                 }
624                         }
625                         argp[0] = (char*)"-a";
626                 }
627 #endif
628                 argp++;
629         }
630
631         actions = parse_params(&argv[firstopt]);
632
633         for (i = 1; i < firstopt; i++) {
634                 if (!recursive_action(argv[i],
635                                 TRUE,           // recurse
636                                 dereference,    // follow links
637                                 FALSE,          // depth first
638                                 fileAction,     // file action
639                                 fileAction,     // dir action
640                                 NULL,           // user data
641                                 0))             // depth
642                         status = EXIT_FAILURE;
643         }
644         return status;
645 }