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