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