find/find.c

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