find/ftsfind.c

   1 /* find -- search for files in a directory hierarchy (fts version)
   2    Copyright (C) 1990, 91, 92, 93, 94, 2000,
   3                  2003, 2004, 2005 Free Software Foundation, Inc.
   4
   5    This program is free software; you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 2, or (at your option)
   8    any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program; if not, write to the Free Software
  17    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  18    USA.*/
  19
  20 /* GNU find was written by Eric Decker <cire@cisco.com>,
  21    with enhancements by David MacKenzie <djm@gnu.org>,
  22    Jay Plett <jay@silence.princeton.nj.us>,
  23    and Tim Wood <axolotl!tim@toad.com>.
  24    The idea for -print0 and xargs -0 came from
  25    Dan Bernstein <brnstnd@kramden.acf.nyu.edu>.
  26    Improvements have been made by James Youngman <jay@gnu.org>.
  27 */
  28
  29
  30 #include "defs.h"
  31
  32
  33 #define USE_SAFE_CHDIR 1
  34 #undef  STAT_MOUNTPOINTS
  35
  36
  37 #include <errno.h>
  38 #include <assert.h>
  39
  40 #ifdef HAVE_FCNTL_H
  41 #include <fcntl.h>
  42 #else
  43 #include <sys/file.h>
  44 #endif
  45
  46
  47 #include "../gnulib/lib/xalloc.h"
  48 #include "closeout.h"
  49 #include <modetype.h>
  50 #include "quotearg.h"
  51 #include "quote.h"
  52 #include "fts_.h"
  53
  54 #ifdef HAVE_LOCALE_H
  55 #include <locale.h>
  56 #endif
  57
  58 #if ENABLE_NLS
  59 # include <libintl.h>
  60 # define _(Text) gettext (Text)
  61 #else
  62 # define _(Text) Text
  63 #define textdomain(Domain)
  64 #define bindtextdomain(Package, Directory)
  65 #endif
  66 #ifdef gettext_noop
  67 # define N_(String) gettext_noop (String)
  68 #else
  69 /* See locate.c for explanation as to why not use (String) */
  70 # define N_(String) String
  71 #endif
  72
  73
  74 #ifdef STAT_MOUNTPOINTS
  75 static void init_mounted_dev_list(void);
  76 #endif
  77 \f
  78 /* We have encountered an error which shoudl affect the exit status.
  79  * This is normally used to change the exit status from 0 to 1.
  80  * However, if the exit status is already 2 for example, we don't want to
  81  * reduce it to 1.
  82  */
  83 static void
  84 error_severity(int level)
  85 {
  86   if (state.exit_status < level)
  87     state.exit_status = level;
  88 }
  89 \f
  90 #ifdef DEBUG
  91 #define STRINGIFY(X) #X
  92 #define HANDLECASE(N) case N: return #N;
  93
  94 static char *
  95 get_fts_info_name(int info)
  96 {
  97   static char buf[10];
  98   switch (info)
  99     {
 100       HANDLECASE(FTS_D);
 101       HANDLECASE(FTS_DC);
 102       HANDLECASE(FTS_DEFAULT);
 103       HANDLECASE(FTS_DNR);
 104       HANDLECASE(FTS_DOT);
 105       HANDLECASE(FTS_DP);
 106       HANDLECASE(FTS_ERR);
 107       HANDLECASE(FTS_F);
 108       HANDLECASE(FTS_INIT);
 109       HANDLECASE(FTS_NS);
 110       HANDLECASE(FTS_NSOK);
 111       HANDLECASE(FTS_SL);
 112       HANDLECASE(FTS_SLNONE);
 113       HANDLECASE(FTS_W);
 114     default:
 115       sprintf(buf, "[%d]", info);
 116       return buf;
 117     }
 118 }
 119
 120 #endif
 121 \f
 122 static void
 123 visit(FTS *p, FTSENT *ent, struct stat *pstat)
 124 {
 125   state.curdepth = ent->fts_level;
 126   state.have_stat = (ent->fts_info != FTS_NS) && (ent->fts_info != FTS_NSOK);
 127   state.rel_pathname = ent->fts_accpath;
 128
 129   /* Apply the predicates to this path. */
 130   (*(eval_tree)->pred_func)(ent->fts_path, pstat, eval_tree);
 131
 132   /* Deal with any side effects of applying the predicates. */
 133   if (state.stop_at_current_level)
 134     {
 135       fts_set(p, ent, FTS_SKIP);
 136     }
 137 }
 138 \f
 139 static const char*
 140 partial_quotearg_n(int n, char *s, size_t len, enum quoting_style style)
 141 {
 142   if (0 == len)
 143     {
 144       return quotearg_n_style(n, style, "");
 145     }
 146   else
 147     {
 148       char saved;
 149       const char *result;
 150
 151       saved = s[len];
 152       s[len] = 0;
 153       result = quotearg_n_style(n, style, s);
 154       s[len] = saved;
 155       return result;
 156     }
 157 }
 158
 159 \f
 160 /* We've detected a filesystem loop.   This is caused by one of
 161  * two things:
 162  *
 163  * 1. Option -L is in effect and we've hit a symbolic link that
 164  *    points to an ancestor.  This is harmless.  We won't traverse the
 165  *    symbolic link.
 166  *
 167  * 2. We have hit a real cycle in the directory hierarchy.  In this
 168  *    case, we issue a diagnostic message (POSIX requires this) and we
 169  *    skip that directory entry.
 170  */
 171 static void
 172 issue_loop_warning(FTSENT * ent)
 173 {
 174   if (S_ISLNK(ent->fts_statp->st_mode))
 175     {
 176       error(0, 0,
 177             _("Symbolic link %s is part of a loop in the directory hierarchy; we have already visited the directory to which it points."),
 178             quotearg_n_style(0, locale_quoting_style, ent->fts_path));
 179     }
 180   else
 181     {
 182       /* We have found an infinite loop.  POSIX requires us to
 183        * issue a diagnostic.  Usually we won't get to here
 184        * because when the leaf optimisation is on, it will cause
 185        * the subdirectory to be skipped.  If /a/b/c/d is a hard
 186        * link to /a/b, then the link count of /a/b/c is 2,
 187        * because the ".." entry of /b/b/c/d points to /a, not
 188        * to /a/b/c.
 189        */
 190       error(0, 0,
 191             _("Filesystem loop detected; "
 192               "%s is part of the same filesystem loop as %s."),
 193             quotearg_n_style(0, locale_quoting_style, ent->fts_path),
 194             partial_quotearg_n(1,
 195                                ent->fts_cycle->fts_path,
 196                                ent->fts_cycle->fts_pathlen,
 197                                locale_quoting_style));
 198     }
 199 }
 200 \f
 201 /*
 202  * Return true if NAME corresponds to a file which forms part of a
 203  * symbolic link loop.  The command
 204  *      rm -f a b; ln -s a b; ln -s b a
 205  * produces such a loop.
 206  */
 207 static boolean
 208 symlink_loop(const char *name)
 209 {
 210   struct stat stbuf;
 211   int rv;
 212   if (following_links())
 213     rv = stat(name, &stbuf);
 214   else
 215     rv = lstat(name, &stbuf);
 216   return (0 != rv) && (ELOOP == errno);
 217 }
 218
 219 \f
 220 static void
 221 consider_visiting(FTS *p, FTSENT *ent)
 222 {
 223   struct stat statbuf;
 224   mode_t mode;
 225
 226 #ifdef DEBUG
 227   fprintf(stderr,
 228           "consider_visiting: end->fts_info=%s, ent->fts_path=%s\n",
 229           get_fts_info_name(ent->fts_info),
 230           quotearg_n(0, ent->fts_path, locale_quoting_style));
 231 #endif
 232
 233   /* Cope with various error conditions. */
 234   if (ent->fts_info == FTS_ERR
 235       || ent->fts_info == FTS_NS
 236       || ent->fts_info == FTS_DNR)
 237     {
 238       error(0, ent->fts_errno, ent->fts_path);
 239       error_severity(1);
 240       return;
 241     }
 242   else if (ent->fts_info == FTS_DC)
 243     {
 244       issue_loop_warning(ent);
 245       error_severity(1);
 246       return;
 247     }
 248   else if (ent->fts_info == FTS_SLNONE)
 249     {
 250       /* fts_read() claims that ent->fts_accpath is a broken symbolic
 251        * link.  That would be fine, but if this is part of a symbolic
 252        * link loop, we diagnose the problem and also ensure that the
 253        * eventual return value is nonzero.   Note that while the path
 254        * we stat is local (fts_accpath), we print the fill path name
 255        * of the file (fts_path) in the error message.
 256        */
 257       if (symlink_loop(ent->fts_accpath))
 258         {
 259           error(0, ELOOP, ent->fts_path);
 260           error_severity(1);
 261           return;
 262         }
 263     }
 264
 265   /* Not an error, cope with the usual cases. */
 266   if (ent->fts_info == FTS_NSOK)
 267     {
 268       state.have_stat = false;
 269       mode = 0;
 270     }
 271   else
 272     {
 273       state.have_stat = true;
 274       statbuf = *(ent->fts_statp);
 275       mode = statbuf.st_mode;
 276     }
 277
 278   if (0 == ent->fts_level && (0u == state.starting_path_length))
 279     state.starting_path_length = ent->fts_pathlen;
 280
 281   if (0 != digest_mode(mode, ent->fts_path, ent->fts_name, &statbuf, 0))
 282     {
 283       /* examine this item. */
 284       int ignore = 0;
 285
 286       if (S_ISDIR(statbuf.st_mode) && (ent->fts_info == FTS_NSOK))
 287         {
 288           /* This is a directory, but fts did not stat it, so
 289            * presumably would not be planning to search its
 290            * children.  Force a stat of the file so that the
 291            * children can be checked.
 292            */
 293           fts_set(p, ent, FTS_AGAIN);
 294           return;
 295         }
 296
 297       if (options.maxdepth >= 0 && (ent->fts_level > options.maxdepth))
 298         {
 299           ignore = 1;
 300           fts_set(p, ent, FTS_SKIP);
 301         }
 302       else if ( (ent->fts_info == FTS_D) && !options.do_dir_first )
 303         {
 304           /* this is the preorder visit, but user said -depth */
 305           ignore = 1;
 306         }
 307       else if ( (ent->fts_info == FTS_DP) && options.do_dir_first )
 308         {
 309           /* this is the postorder visit, but user didn't say -depth */
 310           ignore = 1;
 311         }
 312       else if (ent->fts_level < options.mindepth)
 313         {
 314           ignore = 1;
 315         }
 316
 317       if (!ignore)
 318         {
 319           visit(p, ent, &statbuf);
 320         }
 321
 322
 323       if (ent->fts_info == FTS_DP)
 324         {
 325           /* we're leaving a directory. */
 326           state.stop_at_current_level = false;
 327           complete_pending_execdirs(eval_tree);
 328         }
 329     }
 330 }
 331
 332 \f
 333 static void
 334 find(char *arg)
 335 {
 336   char * arglist[2];
 337   int ftsoptions;
 338   FTS *p;
 339   FTSENT *ent;
 340
 341
 342   arglist[0] = arg;
 343   arglist[1] = NULL;
 344
 345   ftsoptions = FTS_NOSTAT;
 346   switch (options.symlink_handling)
 347     {
 348     case SYMLINK_ALWAYS_DEREF:
 349       ftsoptions |= FTS_COMFOLLOW|FTS_LOGICAL;
 350       break;
 351
 352     case SYMLINK_DEREF_ARGSONLY:
 353       ftsoptions |= FTS_COMFOLLOW;
 354       break;
 355
 356     case SYMLINK_NEVER_DEREF:
 357       ftsoptions |= FTS_PHYSICAL;
 358       break;
 359     }
 360
 361   if (options.stay_on_filesystem)
 362     ftsoptions |= FTS_XDEV;
 363
 364   p = fts_open(arglist, ftsoptions, NULL);
 365   if (NULL == p)
 366     {
 367       error (0, errno,
 368              _("cannot search %s"),
 369              quotearg_n_style(0, locale_quoting_style, arg));
 370     }
 371   else
 372     {
 373       while ( (ent=fts_read(p)) != NULL )
 374         {
 375           consider_visiting(p, ent);
 376         }
 377       fts_close(p);
 378       p = NULL;
 379     }
 380 }
 381
 382
 383 static void
 384 process_all_startpoints(int argc, char *argv[])
 385 {
 386   int i;
 387
 388   /* figure out how many start points there are */
 389   for (i = 0; i < argc && strchr ("-!(),", argv[i][0]) == NULL; i++)
 390     {
 391       find(argv[i]);
 392     }
 393
 394   if (i == 0)
 395     {
 396       /*
 397        * We use a temporary variable here because some actions modify
 398        * the path temporarily.  Hence if we use a string constant,
 399        * we get a coredump.  The best example of this is if we say
 400        * "find -printf %H" (note, not "find . -printf %H").
 401        */
 402       char defaultpath[2] = ".";
 403       find(defaultpath);
 404     }
 405 }
 406
 407
 408
 409 \f
 410 int
 411 main (int argc, char **argv)
 412 {
 413   int i;
 414   const struct parser_table *parse_entry; /* Pointer to the parsing table entry for this expression. */
 415   struct predicate *cur_pred;
 416   char *predicate_name;         /* Name of predicate being parsed. */
 417   int end_of_leading_options = 0; /* First arg after any -H/-L etc. */
 418   program_name = argv[0];
 419   const struct parser_table *entry_close, *entry_print, *entry_open;
 420
 421
 422   /* We call check_nofollow() before setlocale() because the numbers
 423    * for which we check (in the results of uname) definitiely have "."
 424    * as the decimal point indicator even under locales for which that
 425    * is not normally true.   Hence atof() would do the wrong thing
 426    * if we call it after setlocale().
 427    */
 428 #ifdef O_NOFOLLOW
 429   options.open_nofollow_available = check_nofollow();
 430 #else
 431   options.open_nofollow_available = false;
 432 #endif
 433
 434   options.regex_options = RE_SYNTAX_EMACS;
 435
 436 #ifdef HAVE_SETLOCALE
 437   setlocale (LC_ALL, "");
 438 #endif
 439
 440   bindtextdomain (PACKAGE, LOCALEDIR);
 441   textdomain (PACKAGE);
 442   atexit (close_stdout);
 443
 444
 445   if (isatty(0))
 446     {
 447       options.warnings = true;
 448     }
 449   else
 450     {
 451       options.warnings = false;
 452     }
 453
 454
 455   predicates = NULL;
 456   last_pred = NULL;
 457   options.do_dir_first = true;
 458   options.maxdepth = options.mindepth = -1;
 459   options.start_time = time (NULL);
 460   options.cur_day_start = options.start_time - DAYSECS;
 461   options.full_days = false;
 462   options.stay_on_filesystem = false;
 463   options.ignore_readdir_race = false;
 464
 465   state.exit_status = 0;
 466
 467 #if defined(DEBUG_STAT)
 468   options.xstat = debug_stat;
 469 #endif /* !DEBUG_STAT */
 470
 471   if (getenv("POSIXLY_CORRECT"))
 472     options.output_block_size = 512;
 473   else
 474     options.output_block_size = 1024;
 475
 476   if (getenv("FIND_BLOCK_SIZE"))
 477     {
 478       error (1, 0, _("The environment variable FIND_BLOCK_SIZE is not supported, the only thing that affects the block size is the POSIXLY_CORRECT environment variable"));
 479     }
 480
 481 #if LEAF_OPTIMISATION
 482   /* The leaf optimisation is enabled. */
 483   options.no_leaf_check = false;
 484 #else
 485   /* The leaf optimisation is disabled. */
 486   options.no_leaf_check = true;
 487 #endif
 488
 489   set_follow_state(SYMLINK_NEVER_DEREF); /* The default is equivalent to -P. */
 490
 491 #ifdef DEBUG
 492   fprintf (stderr, "cur_day_start = %s", ctime (&options.cur_day_start));
 493 #endif /* DEBUG */
 494
 495   /* Check for -P, -H or -L options. */
 496   for (i=1; (end_of_leading_options = i) < argc; ++i)
 497     {
 498       if (0 == strcmp("-H", argv[i]))
 499         {
 500           /* Meaning: dereference symbolic links on command line, but nowhere else. */
 501           set_follow_state(SYMLINK_DEREF_ARGSONLY);
 502         }
 503       else if (0 == strcmp("-L", argv[i]))
 504         {
 505           /* Meaning: dereference all symbolic links. */
 506           set_follow_state(SYMLINK_ALWAYS_DEREF);
 507         }
 508       else if (0 == strcmp("-P", argv[i]))
 509         {
 510           /* Meaning: never dereference symbolic links (default). */
 511           set_follow_state(SYMLINK_NEVER_DEREF);
 512         }
 513       else if (0 == strcmp("--", argv[i]))
 514         {
 515           /* -- signifies the end of options. */
 516           end_of_leading_options = i+1; /* Next time start with the next option */
 517           break;
 518         }
 519       else
 520         {
 521           /* Hmm, must be one of
 522            * (a) A path name
 523            * (b) A predicate
 524            */
 525           end_of_leading_options = i; /* Next time start with this option */
 526           break;
 527         }
 528     }
 529
 530   /* We are now processing the part of the "find" command line
 531    * after the -H/-L options (if any).
 532    */
 533
 534   /* fprintf(stderr, "rest: optind=%ld\n", (long)optind); */
 535
 536   /* Find where in ARGV the predicates begin. */
 537   for (i = end_of_leading_options; i < argc && strchr ("-!(),", argv[i][0]) == NULL; i++)
 538     {
 539       /* fprintf(stderr, "Looks like %s is not a predicate\n", argv[i]); */
 540       /* Do nothing. */ ;
 541     }
 542
 543   /* Enclose the expression in `( ... )' so a default -print will
 544      apply to the whole expression. */
 545   entry_open  = find_parser("(");
 546   entry_close = find_parser(")");
 547   entry_print = find_parser("print");
 548   assert(entry_open  != NULL);
 549   assert(entry_close != NULL);
 550   assert(entry_print != NULL);
 551
 552   parse_open (entry_open, argv, &argc);
 553   parse_begin_user_args(argv, argc, last_pred, predicates);
 554   pred_sanity_check(last_pred);
 555
 556   /* Build the input order list. */
 557   while (i < argc)
 558     {
 559       if (strchr ("-!(),", argv[i][0]) == NULL)
 560         usage (_("paths must precede expression"));
 561       predicate_name = argv[i];
 562       parse_entry = find_parser (predicate_name);
 563       if (parse_entry == NULL)
 564         {
 565           /* Command line option not recognized */
 566           error (1, 0, _("invalid predicate `%s'"), predicate_name);
 567         }
 568
 569       i++;
 570       if (!(*(parse_entry->parser_func)) (parse_entry, argv, &i))
 571         {
 572           if (argv[i] == NULL)
 573             /* Command line option requires an argument */
 574             error (1, 0, _("missing argument to `%s'"), predicate_name);
 575           else
 576             error (1, 0, _("invalid argument `%s' to `%s'"),
 577                    argv[i], predicate_name);
 578         }
 579
 580       pred_sanity_check(last_pred);
 581       pred_sanity_check(predicates); /* XXX: expensive */
 582     }
 583   parse_end_user_args(argv, argc, last_pred, predicates);
 584
 585   if (predicates->pred_next == NULL)
 586     {
 587       /* No predicates that do something other than set a global variable
 588          were given; remove the unneeded initial `(' and add `-print'. */
 589       cur_pred = predicates;
 590       predicates = last_pred = predicates->pred_next;
 591       free ((char *) cur_pred);
 592       parse_print (entry_print, argv, &argc);
 593       pred_sanity_check(last_pred);
 594       pred_sanity_check(predicates); /* XXX: expensive */
 595     }
 596   else if (!default_prints (predicates->pred_next))
 597     {
 598       /* One or more predicates that produce output were given;
 599          remove the unneeded initial `('. */
 600       cur_pred = predicates;
 601       predicates = predicates->pred_next;
 602       pred_sanity_check(predicates); /* XXX: expensive */
 603       free ((char *) cur_pred);
 604     }
 605   else
 606     {
 607       /* `( user-supplied-expression ) -print'. */
 608       parse_close (entry_close, argv, &argc);
 609       pred_sanity_check(last_pred);
 610       parse_print (entry_print, argv, &argc);
 611       pred_sanity_check(last_pred);
 612       pred_sanity_check(predicates); /* XXX: expensive */
 613     }
 614
 615 #ifdef  DEBUG
 616   fprintf (stderr, "Predicate List:\n");
 617   print_list (stderr, predicates);
 618 #endif /* DEBUG */
 619
 620   /* do a sanity check */
 621   pred_sanity_check(predicates);
 622
 623   /* Done parsing the predicates.  Build the evaluation tree. */
 624   cur_pred = predicates;
 625   eval_tree = get_expr (&cur_pred, NO_PREC);
 626
 627   /* Check if we have any left-over predicates (this fixes
 628    * Debian bug #185202).
 629    */
 630   if (cur_pred != NULL)
 631     {
 632       error (1, 0, _("unexpected extra predicate"));
 633     }
 634
 635 #ifdef  DEBUG
 636   fprintf (stderr, "Eval Tree:\n");
 637   print_tree (stderr, eval_tree, 0);
 638 #endif /* DEBUG */
 639
 640   /* Rearrange the eval tree in optimal-predicate order. */
 641   opt_expr (&eval_tree);
 642
 643   /* Determine the point, if any, at which to stat the file. */
 644   mark_stat (eval_tree);
 645   /* Determine the point, if any, at which to determine file type. */
 646   mark_type (eval_tree);
 647
 648 #ifdef DEBUG
 649   fprintf (stderr, "Optimized Eval Tree:\n");
 650   print_tree (stderr, eval_tree, 0);
 651   fprintf (stderr, "Optimized command line:\n");
 652   print_optlist(stderr, eval_tree);
 653   fprintf(stderr, "\n");
 654 #endif /* DEBUG */
 655
 656   /* safely_chdir() needs to check that it has ended up in the right place.
 657    * To avoid bailing out when something gets automounted, it checks if
 658    * the target directory appears to have had a directory mounted on it as
 659    * we chdir()ed.  The problem with this is that in order to notice that
 660    * a filesystem was mounted, we would need to lstat() all the mount points.
 661    * That strategy loses if our machine is a client of a dead NFS server.
 662    *
 663    * Hence if safely_chdir() and wd_sanity_check() can manage without needing
 664    * to know the mounted device list, we do that.
 665    */
 666   if (!options.open_nofollow_available)
 667     {
 668 #ifdef STAT_MOUNTPOINTS
 669       init_mounted_dev_list();
 670 #endif
 671     }
 672
 673
 674   starting_desc = open (".", O_RDONLY);
 675   if (0 <= starting_desc && fchdir (starting_desc) != 0)
 676     {
 677       close (starting_desc);
 678       starting_desc = -1;
 679     }
 680   if (starting_desc < 0)
 681     {
 682       starting_dir = xgetcwd ();
 683       if (! starting_dir)
 684         error (1, errno, _("cannot get current directory"));
 685     }
 686
 687
 688   process_all_startpoints(argc-end_of_leading_options, argv+end_of_leading_options);
 689
 690   /* If "-exec ... {} +" has been used, there may be some
 691    * partially-full command lines which have been built,
 692    * but which are not yet complete.   Execute those now.
 693    */
 694   cleanup();
 695   return state.exit_status;
 696 }
 697
 698 boolean is_fts_enabled()
 699 {
 700   /* this version of find (i.e. this main()) uses fts. */
 701   return true;
 702 }