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