find/find.c

   1 /*-
   2  * Copyright (c) 1991, 1993, 1994
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * This code is derived from software contributed to Berkeley by
   6  * Cimarron D. Taylor of the University of California, Berkeley.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. All advertising materials mentioning features or use of this software
  17  *    must display the following acknowledgement:
  18  *      This product includes software developed by the University of
  19  *      California, Berkeley and its contributors.
  20  * 4. Neither the name of the University nor the names of its contributors
  21  *    may be used to endorse or promote products derived from this software
  22  *    without specific prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  */
  36
  37 #ifndef lint
  38 #if 0
  39 static char sccsid[] = "@(#)find.c      8.5 (Berkeley) 8/5/94";
  40 #else
  41 #endif
  42 #endif /* not lint */
  43
  44 #include <sys/cdefs.h>
  45 __FBSDID("$FreeBSD: src/usr.bin/find/find.c,v 1.18 2006/05/14 20:23:00 krion Exp $");
  46
  47 #include <sys/types.h>
  48 #include <sys/stat.h>
  49
  50 #include <err.h>
  51 #include <errno.h>
  52 #include <fts.h>
  53 #include <regex.h>
  54 #include <stdio.h>
  55 #include <stdlib.h>
  56 #include <string.h>
  57
  58 #ifdef __APPLE__
  59 #include <get_compat.h>
  60 #include <unistd.h>
  61 #else
  62 #define COMPAT_MODE(func, mode) 1
  63 #endif
  64
  65 #include "find.h"
  66
  67 static int find_compare(const FTSENT * const *s1, const FTSENT * const *s2);
  68
  69 /*
  70  * find_compare --
  71  *      tell fts_open() how to order the traversal of the hierarchy.
  72  *      This variant gives lexicographical order, i.e., alphabetical
  73  *      order within each directory.
  74  */
  75 static int
  76 find_compare(const FTSENT * const *s1, const FTSENT * const *s2)
  77 {
  78
  79         return (strcoll((*s1)->fts_name, (*s2)->fts_name));
  80 }
  81
  82 /*
  83  * find_formplan --
  84  *      process the command line and create a "plan" corresponding to the
  85  *      command arguments.
  86  */
  87 PLAN *
  88 find_formplan(char *argv[])
  89 {
  90         PLAN *plan, *tail, *new;
  91
  92         /*
  93          * for each argument in the command line, determine what kind of node
  94          * it is, create the appropriate node type and add the new plan node
  95          * to the end of the existing plan.  The resulting plan is a linked
  96          * list of plan nodes.  For example, the string:
  97          *
  98          *      % find . -name foo -newer bar -print
  99          *
 100          * results in the plan:
 101          *
 102          *      [-name foo]--> [-newer bar]--> [-print]
 103          *
 104          * in this diagram, `[-name foo]' represents the plan node generated
 105          * by c_name() with an argument of foo and `-->' represents the
 106          * plan->next pointer.
 107          */
 108         for (plan = tail = NULL; *argv;) {
 109                 if (!(new = find_create(&argv)))
 110                         continue;
 111                 if (plan == NULL)
 112                         tail = plan = new;
 113                 else {
 114                         tail->next = new;
 115                         tail = new;
 116                 }
 117         }
 118
 119         /*
 120          * if the user didn't specify one of -print, -ok or -exec, then -print
 121          * is assumed so we bracket the current expression with parens, if
 122          * necessary, and add a -print node on the end.
 123          */
 124         if (!isoutput) {
 125                 OPTION *p;
 126                 char **argv1 = 0;
 127
 128                 if (plan == NULL) {
 129                         p = lookup_option("-print");
 130                         new = (p->create)(p, &argv1);
 131                         tail = plan = new;
 132                 } else {
 133                         p = lookup_option("(");
 134                         new = (p->create)(p, &argv1);
 135                         new->next = plan;
 136                         plan = new;
 137                         p = lookup_option(")");
 138                         new = (p->create)(p, &argv1);
 139                         tail->next = new;
 140                         tail = new;
 141                         p = lookup_option("-print");
 142                         new = (p->create)(p, &argv1);
 143                         tail->next = new;
 144                         tail = new;
 145                 }
 146         }
 147
 148         /*
 149          * the command line has been completely processed into a search plan
 150          * except for the (, ), !, and -o operators.  Rearrange the plan so
 151          * that the portions of the plan which are affected by the operators
 152          * are moved into operator nodes themselves.  For example:
 153          *
 154          *      [!]--> [-name foo]--> [-print]
 155          *
 156          * becomes
 157          *
 158          *      [! [-name foo] ]--> [-print]
 159          *
 160          * and
 161          *
 162          *      [(]--> [-depth]--> [-name foo]--> [)]--> [-print]
 163          *
 164          * becomes
 165          *
 166          *      [expr [-depth]-->[-name foo] ]--> [-print]
 167          *
 168          * operators are handled in order of precedence.
 169          */
 170
 171         plan = paren_squish(plan);              /* ()'s */
 172         plan = not_squish(plan);                /* !'s */
 173         plan = or_squish(plan);                 /* -o's */
 174         return (plan);
 175 }
 176
 177 /* addPath - helper function used to build a list of paths that were
 178  * specified on the command line that we are allowed to search.
 179  */
 180 static char **addPath(char **array, char *newPath)
 181 {
 182         static int pathCounter = 0;
 183
 184         if (newPath == NULL) {  /* initialize array */
 185                 if ((array = malloc(sizeof(char *))) == NULL)
 186                         err(2, "out of memory");
 187                 array[0] = NULL;
 188         }
 189         else {
 190                 array = realloc(array, (++pathCounter + 1) * sizeof(char *));
 191                 if (array == NULL)
 192                         err(2, "out of memory");
 193                 else {
 194                         array[pathCounter - 1] = newPath;
 195                         array[pathCounter] = NULL;      /* ensure array is null terminated */
 196                 }
 197         }
 198         return (array);
 199 }
 200
 201 FTS *tree;                      /* pointer to top of FTS hierarchy */
 202
 203 /*
 204  * find_execute --
 205  *      take a search plan and an array of search paths and executes the plan
 206  *      over all FTSENT's returned for the given search paths.
 207  */
 208 int
 209 find_execute(PLAN *plan, char *paths[])
 210 {
 211         FTSENT *entry;
 212         PLAN *p;
 213         int rval;
 214         char **myPaths;
 215         int nonSearchableDirFound = 0;
 216         int pathIndex;
 217         struct stat statInfo;
 218
 219         /* special-case directories specified on command line - explicitly examine
 220          * mode bits, to ensure failure if the directory cannot be searched
 221          * (whether or not it's empty). UNIX conformance... <sigh>
 222          */
 223
 224         int strict_symlinks = (ftsoptions & (FTS_COMFOLLOW|FTS_LOGICAL))
 225           && COMPAT_MODE("bin/find", "unix2003");
 226
 227         myPaths = addPath(NULL, NULL);
 228         for (pathIndex = 0; paths[pathIndex] != NULL; ++pathIndex) {
 229                 int stat_ret = stat(paths[pathIndex], &statInfo);
 230                 int stat_errno = errno;
 231                 if (strict_symlinks && stat_ret < 0) {
 232                     if (stat_errno == ELOOP) {
 233                         errx(1, "Symlink loop resolving %s", paths[pathIndex]);
 234                     }
 235                 }
 236
 237                 /* retrieve mode bits, and examine "searchable" bit of
 238                   directories, exempt root from POSIX conformance */
 239                 if (COMPAT_MODE("bin/find", "unix2003") && getuid()
 240                   && stat_ret == 0
 241                   && ((statInfo.st_mode & S_IFMT) == S_IFDIR)) {
 242                         if ((statInfo.st_mode & (S_IXUSR + S_IXGRP + S_IXOTH)) != 0) {
 243                                 myPaths = addPath(myPaths, paths[pathIndex]);
 244                         } else {
 245                                 if (stat_errno != ENAMETOOLONG) {       /* if name is too long, just let existing logic handle it */
 246                                         warnx("%s: Permission denied", paths[pathIndex]);
 247                                         nonSearchableDirFound = 1;
 248                                 }
 249                         }
 250                 } else {
 251                         /* not a directory, so add path to array */
 252                         myPaths = addPath(myPaths, paths[pathIndex]);
 253                 }
 254         }
 255         if (myPaths[0] == NULL) {       /* were any directories searchable? */
 256                 free(myPaths);
 257                 return(nonSearchableDirFound);  /* no... */
 258         }
 259
 260         tree = fts_open(myPaths, ftsoptions, (issort ? find_compare : NULL));
 261         if (tree == NULL)
 262                 err(1, "ftsopen");
 263
 264         for (rval = nonSearchableDirFound; (entry = fts_read(tree)) != NULL;) {
 265                 if (maxdepth != -1 && entry->fts_level >= maxdepth) {
 266                         if (fts_set(tree, entry, FTS_SKIP))
 267                                 err(1, "%s", entry->fts_path);
 268                 }
 269
 270                 switch (entry->fts_info) {
 271                 case FTS_D:
 272                         if (isdepth)
 273                                 continue;
 274                         break;
 275                 case FTS_DP:
 276                         if (!isdepth)
 277                                 continue;
 278                         break;
 279                 case FTS_DNR:
 280                 case FTS_ERR:
 281                 case FTS_NS:
 282                         (void)fflush(stdout);
 283                         warnx("%s: %s",
 284                             entry->fts_path, strerror(entry->fts_errno));
 285                         rval = 1;
 286                         continue;
 287 #ifdef FTS_W
 288                 case FTS_W:
 289                         continue;
 290 #endif /* FTS_W */
 291                 }
 292 #define BADCH   " \t\n\\'\""
 293                 if (isxargs && strpbrk(entry->fts_path, BADCH)) {
 294                         (void)fflush(stdout);
 295                         warnx("%s: illegal path", entry->fts_path);
 296                         rval = 1;
 297                         continue;
 298                 }
 299
 300                 if (mindepth != -1 && entry->fts_level < mindepth)
 301                         continue;
 302
 303                 /*
 304                  * Call all the functions in the execution plan until one is
 305                  * false or all have been executed.  This is where we do all
 306                  * the work specified by the user on the command line.
 307                  */
 308                 for (p = plan; p && (p->execute)(p, entry); p = p->next);
 309         }
 310         free (myPaths);
 311         finish_execplus();
 312         if (errno)
 313                 err(1, "fts_read");
 314         fts_close(tree);
 315         return (rval);
 316 }