find/find.c

   1 /* find -- search for files in a directory hierarchy
   2    Copyright (C) 1990, 91, 92, 93, 94 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software
  16    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  17
  18 /* GNU find was written by Eric Decker <cire@cisco.com>,
  19    with enhancements by David MacKenzie <djm@gnu.ai.mit.edu>,
  20    Jay Plett <jay@silence.princeton.nj.us>,
  21    and Tim Wood <axolotl!tim@toad.com>.
  22    The idea for -print0 and xargs -0 came from
  23    Dan Bernstein <brnstnd@kramden.acf.nyu.edu>.  */
  24
  25 #include <config.h>
  26 #include <sys/types.h>
  27 #include <sys/stat.h>
  28 #include <stdio.h>
  29 #ifdef HAVE_FCNTL_H
  30 #include <fcntl.h>
  31 #else
  32 #include <sys/file.h>
  33 #endif
  34 #include "defs.h"
  35 #include <modetype.h>
  36
  37 #ifdef HAVE_LOCALE_H
  38 #include <locale.h>
  39 #endif
  40
  41 #if ENABLE_NLS
  42 # include <libintl.h>
  43 # define _(Text) gettext (Text)
  44 #else
  45 # define _(Text) Text
  46 #define textdomain(Domain)
  47 #define bindtextdomain(Package, Directory)
  48 #endif
  49 #ifdef gettext_noop
  50 # define N_(String) gettext_noop (String)
  51 #else
  52 # define N_(String) (String)
  53 #endif
  54
  55 #define apply_predicate(pathname, stat_buf_ptr, node)   \
  56   (*(node)->pred_func)((pathname), (stat_buf_ptr), (node))
  57
  58 static void process_top_path PARAMS((char *pathname));
  59 static int process_path PARAMS((char *pathname, char *name, boolean leaf, char *parent));
  60 static void process_dir PARAMS((char *pathname, char *name, int pathlen, struct stat *statp, char *parent));
  61 static boolean no_side_effects PARAMS((struct predicate *pred));
  62
  63 /* Name this program was run with. */
  64 char *program_name;
  65
  66 /* All predicates for each path to process. */
  67 struct predicate *predicates;
  68
  69 /* The last predicate allocated. */
  70 struct predicate *last_pred;
  71
  72 /* The root of the evaluation tree. */
  73 static struct predicate *eval_tree;
  74
  75 /* If true, process directory before contents.  True unless -depth given. */
  76 boolean do_dir_first;
  77
  78 /* If >=0, don't descend more than this many levels of subdirectories. */
  79 int maxdepth;
  80
  81 /* If >=0, don't process files above this level. */
  82 int mindepth;
  83
  84 /* Current depth; 0 means current path is a command line arg. */
  85 int curdepth;
  86
  87 /* Seconds between 00:00 1/1/70 and either one day before now
  88    (the default), or the start of today (if -daystart is given). */
  89 time_t cur_day_start;
  90
  91 /* If true, cur_day_start has been adjusted to the start of the day. */
  92 boolean full_days;
  93
  94 /* If true, do not assume that files in directories with nlink == 2
  95    are non-directories. */
  96 boolean no_leaf_check;
  97
  98 /* If true, don't cross filesystem boundaries. */
  99 boolean stay_on_filesystem;
 100
 101 /* If true, don't descend past current directory.
 102    Can be set by -prune, -maxdepth, and -xdev/-mount. */
 103 boolean stop_at_current_level;
 104
 105 #ifndef HAVE_FCHDIR
 106 /* The full path of the initial working directory.  */
 107 char *starting_dir;
 108 #else
 109 /* A file descriptor open to the initial working directory.
 110    Doing it this way allows us to work when the i.w.d. has
 111    unreadable parents.  */
 112 int starting_desc;
 113 #endif
 114
 115 /* If true, we have called stat on the current path. */
 116 boolean have_stat;
 117
 118 /* The file being operated on, relative to the current directory.
 119    Used for stat, readlink, and opendir.  */
 120 char *rel_pathname;
 121
 122 /* Length of current path. */
 123 int path_length;
 124
 125 /* true if following symlinks.  Should be consistent with xstat.  */
 126 boolean dereference;
 127
 128 /* Pointer to the function used to stat files. */
 129 int (*xstat) ();
 130
 131 /* Status value to return to system. */
 132 int exit_status;
 133
 134 #ifdef DEBUG_STAT
 135 static int
 136 debug_stat (file, bufp)
 137      char *file;
 138      struct stat *bufp;
 139 {
 140   fprintf (stderr, "debug_stat (%s)\n", file);
 141   return lstat (file, bufp);
 142 }
 143 #endif /* DEBUG_STAT */
 144 \f
 145 int
 146 main (int argc, char **argv)
 147 {
 148   int i;
 149   PFB parse_function;           /* Pointer to who is to do the parsing. */
 150   struct predicate *cur_pred;
 151   char *predicate_name;         /* Name of predicate being parsed. */
 152
 153   program_name = argv[0];
 154
 155 #ifdef HAVE_SETLOCALE
 156   setlocale (LC_ALL, "");
 157 #endif
 158   bindtextdomain (PACKAGE, LOCALEDIR);
 159   textdomain (PACKAGE);
 160
 161   predicates = NULL;
 162   last_pred = NULL;
 163   do_dir_first = true;
 164   maxdepth = mindepth = -1;
 165   cur_day_start = time ((time_t *) 0) - DAYSECS;
 166   full_days = false;
 167   no_leaf_check = false;
 168   stay_on_filesystem = false;
 169   exit_status = 0;
 170   dereference = false;
 171 #ifdef DEBUG_STAT
 172   xstat = debug_stat;
 173 #else /* !DEBUG_STAT */
 174   xstat = lstat;
 175 #endif /* !DEBUG_STAT */
 176
 177 #ifdef DEBUG
 178   printf ("cur_day_start = %s", ctime (&cur_day_start));
 179 #endif /* DEBUG */
 180
 181   /* Find where in ARGV the predicates begin. */
 182   for (i = 1; i < argc && strchr ("-!(),", argv[i][0]) == NULL; i++)
 183     /* Do nothing. */ ;
 184
 185   /* Enclose the expression in `( ... )' so a default -print will
 186      apply to the whole expression. */
 187   parse_open (argv, &argc);
 188   /* Build the input order list. */
 189   while (i < argc)
 190     {
 191       if (strchr ("-!(),", argv[i][0]) == NULL)
 192         usage (_("paths must precede expression"));
 193       predicate_name = argv[i];
 194       parse_function = find_parser (predicate_name);
 195       if (parse_function == NULL)
 196         /* Command line option not recognized */
 197         error (1, 0, _("invalid predicate `%s'"), predicate_name);
 198       i++;
 199       if (!(*parse_function) (argv, &i))
 200         {
 201           if (argv[i] == NULL)
 202             /* Command line option requires an argument */
 203             error (1, 0, _("missing argument to `%s'"), predicate_name);
 204           else
 205             error (1, 0, _("invalid argument `%s' to `%s'"),
 206                    argv[i], predicate_name);
 207         }
 208     }
 209   if (predicates->pred_next == NULL)
 210     {
 211       /* No predicates that do something other than set a global variable
 212          were given; remove the unneeded initial `(' and add `-print'. */
 213       cur_pred = predicates;
 214       predicates = last_pred = predicates->pred_next;
 215       free ((char *) cur_pred);
 216       parse_print (argv, &argc);
 217     }
 218   else if (!no_side_effects (predicates->pred_next))
 219     {
 220       /* One or more predicates that produce output were given;
 221          remove the unneeded initial `('. */
 222       cur_pred = predicates;
 223       predicates = predicates->pred_next;
 224       free ((char *) cur_pred);
 225     }
 226   else
 227     {
 228       /* `( user-supplied-expression ) -print'. */
 229       parse_close (argv, &argc);
 230       parse_print (argv, &argc);
 231     }
 232
 233 #ifdef  DEBUG
 234   printf (_("Predicate List:\n"));
 235   print_list (predicates);
 236 #endif /* DEBUG */
 237
 238   /* Done parsing the predicates.  Build the evaluation tree. */
 239   cur_pred = predicates;
 240   eval_tree = get_expr (&cur_pred, NO_PREC);
 241 #ifdef  DEBUG
 242   printf (_("Eval Tree:\n"));
 243   print_tree (eval_tree, 0);
 244 #endif /* DEBUG */
 245
 246   /* Rearrange the eval tree in optimal-predicate order. */
 247   opt_expr (&eval_tree);
 248
 249   /* Determine the point, if any, at which to stat the file. */
 250   mark_stat (eval_tree);
 251
 252 #ifdef DEBUG
 253   printf (_("Optimized Eval Tree:\n"));
 254   print_tree (eval_tree, 0);
 255 #endif /* DEBUG */
 256
 257 #ifndef HAVE_FCHDIR
 258   starting_dir = xgetcwd ();
 259   if (starting_dir == NULL)
 260     error (1, errno, _("cannot get current directory"));
 261 #else
 262   starting_desc = open (".", O_RDONLY);
 263   if (starting_desc < 0)
 264     error (1, errno, _("cannot open current directory"));
 265 #endif
 266
 267   /* If no paths are given, default to ".".  */
 268   for (i = 1; i < argc && strchr ("-!(),", argv[i][0]) == NULL; i++)
 269     process_top_path (argv[i]);
 270   if (i == 1)
 271     process_top_path (".");
 272
 273   exit (exit_status);
 274 }
 275 \f
 276 /* Descend PATHNAME, which is a command-line argument.  */
 277
 278 static void
 279 process_top_path (char *pathname)
 280 {
 281   struct stat stat_buf;
 282
 283   curdepth = 0;
 284   path_length = strlen (pathname);
 285
 286   /* We stat each pathname given on the command-line twice --
 287      once here and once in process_path.  It's not too bad, though,
 288      since the kernel can read the stat information out of its inode
 289      cache the second time.  */
 290   if ((*xstat) (pathname, &stat_buf) == 0 && S_ISDIR (stat_buf.st_mode))
 291     {
 292       if (chdir (pathname) < 0)
 293         {
 294           error (0, errno, "%s", pathname);
 295           exit_status = 1;
 296           return;
 297         }
 298       process_path (pathname, ".", false, ".");
 299 #ifndef HAVE_FCHDIR
 300       if (chdir (starting_dir) < 0)
 301         error (1, errno, "%s", starting_dir);
 302 #else
 303       if (fchdir (starting_desc))
 304         error (1, errno, _("cannot return to starting directory"));
 305 #endif
 306     }
 307   else
 308     process_path (pathname, pathname, false, ".");
 309 }
 310
 311 /* Info on each directory in the current tree branch, to avoid
 312    getting stuck in symbolic link loops.  */
 313 struct dir_id
 314 {
 315   ino_t ino;
 316   dev_t dev;
 317 };
 318 static struct dir_id *dir_ids = NULL;
 319 /* Entries allocated in `dir_ids'.  */
 320 static int dir_alloc = 0;
 321 /* Index in `dir_ids' of directory currently being searched.
 322    This is always the last valid entry.  */
 323 static int dir_curr = -1;
 324 /* (Arbitrary) number of entries to grow `dir_ids' by.  */
 325 #define DIR_ALLOC_STEP 32
 326
 327 /* Recursively descend path PATHNAME, applying the predicates.
 328    LEAF is true if PATHNAME is known to be in a directory that has no
 329    more unexamined subdirectories, and therefore it is not a directory.
 330    Knowing this allows us to avoid calling stat as long as possible for
 331    leaf files.
 332
 333    NAME is PATHNAME relative to the current directory.  We access NAME
 334    but print PATHNAME.
 335
 336    PARENT is the path of the parent of NAME, relative to find's
 337    starting directory.
 338
 339    Return nonzero iff PATHNAME is a directory. */
 340
 341 static int
 342 process_path (char *pathname, char *name, boolean leaf, char *parent)
 343 {
 344   struct stat stat_buf;
 345   static dev_t root_dev;        /* Device ID of current argument pathname. */
 346   int i;
 347
 348   /* Assume it is a non-directory initially. */
 349   stat_buf.st_mode = 0;
 350
 351   rel_pathname = name;
 352
 353   if (leaf)
 354     have_stat = false;
 355   else
 356     {
 357       if ((*xstat) (name, &stat_buf) != 0)
 358         {
 359           error (0, errno, "%s", pathname);
 360           exit_status = 1;
 361           return 0;
 362         }
 363       have_stat = true;
 364     }
 365
 366   if (!S_ISDIR (stat_buf.st_mode))
 367     {
 368       if (curdepth >= mindepth)
 369         apply_predicate (pathname, &stat_buf, eval_tree);
 370       return 0;
 371     }
 372
 373   /* From here on, we're working on a directory.  */
 374
 375   stop_at_current_level = maxdepth >= 0 && curdepth >= maxdepth;
 376
 377   /* If we've already seen this directory on this branch,
 378      don't descend it again.  */
 379   for (i = 0; i <= dir_curr; i++)
 380     if (stat_buf.st_ino == dir_ids[i].ino &&
 381         stat_buf.st_dev == dir_ids[i].dev)
 382       stop_at_current_level = true;
 383
 384   if (dir_alloc <= ++dir_curr)
 385     {
 386       dir_alloc += DIR_ALLOC_STEP;
 387       dir_ids = (struct dir_id *)
 388         xrealloc ((char *) dir_ids, dir_alloc * sizeof (struct dir_id));
 389     }
 390   dir_ids[dir_curr].ino = stat_buf.st_ino;
 391   dir_ids[dir_curr].dev = stat_buf.st_dev;
 392
 393   if (stay_on_filesystem)
 394     {
 395       if (curdepth == 0)
 396         root_dev = stat_buf.st_dev;
 397       else if (stat_buf.st_dev != root_dev)
 398         stop_at_current_level = true;
 399     }
 400
 401   if (do_dir_first && curdepth >= mindepth)
 402     apply_predicate (pathname, &stat_buf, eval_tree);
 403
 404 #ifdef DEBUG
 405   fprintf(stderr, "pathname = %s, stop_at_current_level = %d\n",
 406           pathname, stop_at_current_level);
 407 #endif /* DEBUG */
 408
 409   if (stop_at_current_level == false)
 410     /* Scan directory on disk. */
 411     process_dir (pathname, name, strlen (pathname), &stat_buf, parent);
 412
 413   if (do_dir_first == false && curdepth >= mindepth)
 414     {
 415       rel_pathname = name;
 416       apply_predicate (pathname, &stat_buf, eval_tree);
 417     }
 418
 419   dir_curr--;
 420
 421   return 1;
 422 }
 423 \f
 424 /* Scan directory PATHNAME and recurse through process_path for each entry.
 425
 426    PATHLEN is the length of PATHNAME.
 427
 428    NAME is PATHNAME relative to the current directory.
 429
 430    STATP is the results of *xstat on it.
 431
 432    PARENT is the path of the parent of NAME, relative to find's
 433    starting directory.  */
 434
 435 static void
 436 process_dir (char *pathname, char *name, int pathlen, struct stat *statp, char *parent)
 437 {
 438   char *name_space;             /* Names of files in PATHNAME. */
 439   int subdirs_left;             /* Number of unexamined subdirs in PATHNAME. */
 440
 441   subdirs_left = statp->st_nlink - 2; /* Account for name and ".". */
 442
 443   errno = 0;
 444   /* On some systems (VAX 4.3BSD+NFS), NFS mount points have st_size < 0.  */
 445   name_space = savedir (name, statp->st_size > 0 ? statp->st_size : 512);
 446   if (name_space == NULL)
 447     {
 448       if (errno)
 449         {
 450           error (0, errno, "%s", pathname);
 451           exit_status = 1;
 452         }
 453       else
 454         error (1, 0, _("virtual memory exhausted"));
 455     }
 456   else
 457     {
 458       register char *namep;     /* Current point in `name_space'. */
 459       char *cur_path;           /* Full path of each file to process. */
 460       char *cur_name;           /* Base name of each file to process. */
 461       unsigned cur_path_size;   /* Bytes allocated for `cur_path'. */
 462       register unsigned file_len; /* Length of each path to process. */
 463       register unsigned pathname_len; /* PATHLEN plus trailing '/'. */
 464
 465       if (pathname[pathlen - 1] == '/')
 466         pathname_len = pathlen + 1; /* For '\0'; already have '/'. */
 467       else
 468         pathname_len = pathlen + 2; /* For '/' and '\0'. */
 469       cur_path_size = 0;
 470       cur_path = NULL;
 471
 472       if (strcmp (name, ".") && chdir (name) < 0)
 473         {
 474           error (0, errno, "%s", pathname);
 475           exit_status = 1;
 476           return;
 477         }
 478
 479       for (namep = name_space; *namep; namep += file_len - pathname_len + 1)
 480         {
 481           /* Append this directory entry's name to the path being searched. */
 482           file_len = pathname_len + strlen (namep);
 483           if (file_len > cur_path_size)
 484             {
 485               while (file_len > cur_path_size)
 486                 cur_path_size += 1024;
 487               if (cur_path)
 488                 free (cur_path);
 489               cur_path = xmalloc (cur_path_size);
 490               strcpy (cur_path, pathname);
 491               cur_path[pathname_len - 2] = '/';
 492             }
 493           cur_name = cur_path + pathname_len - 1;
 494           strcpy (cur_name, namep);
 495
 496           curdepth++;
 497           if (!no_leaf_check)
 498             /* Normal case optimization.
 499                On normal Unix filesystems, a directory that has no
 500                subdirectories has two links: its name, and ".".  Any
 501                additional links are to the ".." entries of its
 502                subdirectories.  Once we have processed as many
 503                subdirectories as there are additional links, we know
 504                that the rest of the entries are non-directories --
 505                in other words, leaf files. */
 506             subdirs_left -= process_path (cur_path, cur_name,
 507                                           subdirs_left == 0, pathname);
 508           else
 509             /* There might be weird (e.g., CD-ROM or MS-DOS) filesystems
 510                mounted, which don't have Unix-like directory link counts. */
 511             process_path (cur_path, cur_name, false, pathname);
 512           curdepth--;
 513         }
 514
 515       if (strcmp (name, "."))
 516         {
 517           if (!dereference)
 518             {
 519               if (chdir ("..") < 0)
 520                 /* We could go back and do the next command-line arg instead,
 521                    maybe using longjmp.  */
 522                 error (1, errno, "%s", parent);
 523             }
 524           else
 525             {
 526 #ifndef HAVE_FCHDIR
 527               if (chdir (starting_dir) || chdir (parent))
 528                 error (1, errno, "%s", parent);
 529 #else
 530               if (fchdir (starting_desc) || chdir (parent))
 531                 error (1, errno, "%s", parent);
 532 #endif
 533             }
 534         }
 535
 536       if (cur_path)
 537         free (cur_path);
 538       free (name_space);
 539     }
 540 }
 541 \f
 542 /* Return true if there are no side effects in any of the predicates in
 543    predicate list PRED, false if there are any. */
 544
 545 static boolean
 546 no_side_effects (struct predicate *pred)
 547 {
 548   while (pred != NULL)
 549     {
 550       if (pred->side_effects)
 551         return (false);
 552       pred = pred->pred_next;
 553     }
 554   return (true);
 555 }