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, 2006, 2007 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 3 of the License, or
   8    (at your option) 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, see <http://www.gnu.org/licenses/>.
  17 */
  18
  19 /* This file was written by James Youngman, based on find.c.
  20
  21    GNU find was written by Eric Decker <cire@cisco.com>,
  22    with enhancements by David MacKenzie <djm@gnu.org>,
  23    Jay Plett <jay@silence.princeton.nj.us>,
  24    and Tim Wood <axolotl!tim@toad.com>.
  25    The idea for -print0 and xargs -0 came from
  26    Dan Bernstein <brnstnd@kramden.acf.nyu.edu>.
  27 */
  28
  29
  30 #include <config.h>
  31 #include "defs.h"
  32
  33
  34 #define USE_SAFE_CHDIR 1
  35 #undef  STAT_MOUNTPOINTS
  36
  37
  38 #include <errno.h>
  39 #include <assert.h>
  40
  41 #include <fcntl.h>
  42 #include <sys/stat.h>
  43
  44 #include <unistd.h>
  45
  46 #include "xalloc.h"
  47 #include "closeout.h"
  48 #include <modetype.h>
  49 #include "quotearg.h"
  50 #include "quote.h"
  51 #include "fts_.h"
  52 #include "openat.h"
  53 #include "save-cwd.h"
  54 #include "xgetcwd.h"
  55 #include "error.h"
  56 #include "dircallback.h"
  57
  58 #ifdef HAVE_LOCALE_H
  59 #include <locale.h>
  60 #endif
  61
  62 #if ENABLE_NLS
  63 # include <libintl.h>
  64 # define _(Text) gettext (Text)
  65 #else
  66 # define _(Text) Text
  67 #define textdomain(Domain)
  68 #define bindtextdomain(Package, Directory)
  69 #endif
  70 #ifdef gettext_noop
  71 # define N_(String) gettext_noop (String)
  72 #else
  73 /* See locate.c for explanation as to why not use (String) */
  74 # define N_(String) String
  75 #endif
  76
  77
  78 static void set_close_on_exec(int fd)
  79 {
  80 #if defined F_GETFD && defined FD_CLOEXEC
  81   int flags;
  82   flags = fcntl(fd, F_GETFD);
  83   if (flags >= 0)
  84     {
  85       flags |= FD_CLOEXEC;
  86       fcntl(fd, F_SETFD, flags);
  87     }
  88 #endif
  89 }
  90
  91
  92
  93 /* FTS_TIGHT_CYCLE_CHECK tries to work around Savannah bug #17877
  94  * (but actually using it doesn't fix the bug).
  95  */
  96 static int ftsoptions = FTS_NOSTAT|FTS_TIGHT_CYCLE_CHECK;
  97
  98 static int prev_depth = INT_MIN; /* fts_level can be < 0 */
  99 static int curr_fd = -1;
 100
 101 int get_current_dirfd(void)
 102 {
 103   if (ftsoptions & FTS_CWDFD)
 104     {
 105       assert (curr_fd != -1);
 106       assert ( (AT_FDCWD == curr_fd) || (curr_fd >= 0) );
 107
 108       if (AT_FDCWD == curr_fd)
 109         return starting_desc;
 110       else
 111         return curr_fd;
 112     }
 113   else
 114     {
 115       return AT_FDCWD;
 116     }
 117 }
 118
 119 static void left_dir(void)
 120 {
 121   if (ftsoptions & FTS_CWDFD)
 122     {
 123       if (curr_fd >= 0)
 124         {
 125           close(curr_fd);
 126           curr_fd = -1;
 127         }
 128     }
 129   else
 130     {
 131       /* do nothing. */
 132     }
 133 }
 134
 135 /*
 136  * Signal that we are now inside a directory pointed to by dirfd.
 137  * The caller can't tell if this is the first time this happens, so
 138  * we have to be careful not to call dup() more than once
 139  */
 140 static void inside_dir(int dirfd)
 141 {
 142   if (ftsoptions & FTS_CWDFD)
 143     {
 144       assert (dirfd == AT_FDCWD || dirfd >= 0);
 145
 146       state.cwd_dir_fd = dirfd;
 147       if (curr_fd < 0)
 148         {
 149           if (AT_FDCWD == dirfd)
 150             {
 151               curr_fd = AT_FDCWD;
 152             }
 153           else if (dirfd >= 0)
 154             {
 155               curr_fd = dup(dirfd);
 156               set_close_on_exec(curr_fd);
 157             }
 158           else
 159             {
 160               /* curr_fd is invalid, but dirfd is also invalid.
 161                * This should not have happened.
 162                */
 163               assert (curr_fd >= 0 || dirfd >= 0);
 164             }
 165         }
 166     }
 167   else
 168     {
 169       /* FTS_CWDFD is not in use.  We can always assume that
 170        * AT_FDCWD refers to the directory we are currentl searching.
 171        *
 172        * Therefore there is nothing to do.
 173        */
 174     }
 175 }
 176
 177
 178
 179 #ifdef STAT_MOUNTPOINTS
 180 static void init_mounted_dev_list(void);
 181 #endif
 182 \f
 183 /* We have encountered an error which should affect the exit status.
 184  * This is normally used to change the exit status from 0 to 1.
 185  * However, if the exit status is already 2 for example, we don't want to
 186  * reduce it to 1.
 187  */
 188 static void
 189 error_severity(int level)
 190 {
 191   if (state.exit_status < level)
 192     state.exit_status = level;
 193 }
 194 \f
 195
 196 #define STRINGIFY(X) #X
 197 #define HANDLECASE(N) case N: return #N;
 198
 199 static char *
 200 get_fts_info_name(int info)
 201 {
 202   static char buf[10];
 203   switch (info)
 204     {
 205       HANDLECASE(FTS_D);
 206       HANDLECASE(FTS_DC);
 207       HANDLECASE(FTS_DEFAULT);
 208       HANDLECASE(FTS_DNR);
 209       HANDLECASE(FTS_DOT);
 210       HANDLECASE(FTS_DP);
 211       HANDLECASE(FTS_ERR);
 212       HANDLECASE(FTS_F);
 213       HANDLECASE(FTS_INIT);
 214       HANDLECASE(FTS_NS);
 215       HANDLECASE(FTS_NSOK);
 216       HANDLECASE(FTS_SL);
 217       HANDLECASE(FTS_SLNONE);
 218       HANDLECASE(FTS_W);
 219     default:
 220       sprintf(buf, "[%d]", info);
 221       return buf;
 222     }
 223 }
 224 \f
 225 static void
 226 visit(FTS *p, FTSENT *ent, struct stat *pstat)
 227 {
 228   struct predicate *eval_tree;
 229
 230   state.curdepth = ent->fts_level;
 231   state.have_stat = (ent->fts_info != FTS_NS) && (ent->fts_info != FTS_NSOK);
 232   state.rel_pathname = ent->fts_accpath;
 233   state.cwd_dir_fd   = p->fts_cwd_fd;
 234
 235   /* Apply the predicates to this path. */
 236   eval_tree = get_eval_tree();
 237   apply_predicate(ent->fts_path, pstat, eval_tree);
 238
 239   /* Deal with any side effects of applying the predicates. */
 240   if (state.stop_at_current_level)
 241     {
 242       fts_set(p, ent, FTS_SKIP);
 243     }
 244 }
 245 \f
 246 static const char*
 247 partial_quotearg_n(int n, char *s, size_t len, enum quoting_style style)
 248 {
 249   if (0 == len)
 250     {
 251       return quotearg_n_style(n, style, "");
 252     }
 253   else
 254     {
 255       char saved;
 256       const char *result;
 257
 258       saved = s[len];
 259       s[len] = 0;
 260       result = quotearg_n_style(n, style, s);
 261       s[len] = saved;
 262       return result;
 263     }
 264 }
 265
 266 \f
 267 /* We've detected a file system loop.   This is caused by one of
 268  * two things:
 269  *
 270  * 1. Option -L is in effect and we've hit a symbolic link that
 271  *    points to an ancestor.  This is harmless.  We won't traverse the
 272  *    symbolic link.
 273  *
 274  * 2. We have hit a real cycle in the directory hierarchy.  In this
 275  *    case, we issue a diagnostic message (POSIX requires this) and we
 276  *    skip that directory entry.
 277  */
 278 static void
 279 issue_loop_warning(FTSENT * ent)
 280 {
 281   if (S_ISLNK(ent->fts_statp->st_mode))
 282     {
 283       error(0, 0,
 284             _("Symbolic link %s is part of a loop in the directory hierarchy; we have already visited the directory to which it points."),
 285             safely_quote_err_filename(0, ent->fts_path));
 286     }
 287   else
 288     {
 289       /* We have found an infinite loop.  POSIX requires us to
 290        * issue a diagnostic.  Usually we won't get to here
 291        * because when the leaf optimisation is on, it will cause
 292        * the subdirectory to be skipped.  If /a/b/c/d is a hard
 293        * link to /a/b, then the link count of /a/b/c is 2,
 294        * because the ".." entry of /a/b/c/d points to /a, not
 295        * to /a/b/c.
 296        */
 297       error(0, 0,
 298             _("File system loop detected; "
 299               "%1$s is part of the same file system loop as %2$s."),
 300             safely_quote_err_filename(0, ent->fts_path),
 301             partial_quotearg_n(1,
 302                                ent->fts_cycle->fts_path,
 303                                ent->fts_cycle->fts_pathlen,
 304                                options.err_quoting_style));
 305     }
 306 }
 307 \f
 308 /*
 309  * Return true if NAME corresponds to a file which forms part of a
 310  * symbolic link loop.  The command
 311  *      rm -f a b; ln -s a b; ln -s b a
 312  * produces such a loop.
 313  */
 314 static boolean
 315 symlink_loop(const char *name)
 316 {
 317   struct stat stbuf;
 318   int rv;
 319   if (following_links())
 320     rv = stat(name, &stbuf);
 321   else
 322     rv = lstat(name, &stbuf);
 323   return (0 != rv) && (ELOOP == errno);
 324 }
 325 \f
 326
 327 static int
 328 complete_execdirs_cb(void *context)
 329 {
 330   (void) context;
 331   /* By the tme this callback is called, the current directory is correct. */
 332   complete_pending_execdirs(AT_FDCWD);
 333   return 0;
 334 }
 335
 336 static void
 337 show_outstanding_execdirs(FILE *fp)
 338 {
 339   if (options.debug_options & DebugExec)
 340     {
 341       int seen=0;
 342       struct predicate *p;
 343       p = get_eval_tree();
 344       fprintf(fp, "Outstanding execdirs:");
 345
 346       while (p)
 347         {
 348           const char *pfx;
 349
 350           if (pred_is(p, pred_execdir))
 351             pfx = "-execdir";
 352           else if (pred_is(p, pred_okdir))
 353             pfx = "-okdir";
 354           else
 355             pfx = NULL;
 356           if (pfx)
 357             {
 358               int i;
 359               const struct exec_val *execp = &p->args.exec_vec;
 360               ++seen;
 361
 362               fprintf(fp, "%s ", pfx);
 363               if (execp->multiple)
 364                 fprintf(fp, "multiple ");
 365               fprintf(fp, "%d args: ", execp->state.cmd_argc);
 366               for (i=0; i<execp->state.cmd_argc; ++i)
 367                 {
 368                   fprintf(fp, "%s ", execp->state.cmd_argv[i]);
 369                 }
 370               fprintf(fp, "\n");
 371             }
 372           p = p->pred_next;
 373         }
 374       if (!seen)
 375         fprintf(fp, " none\n");
 376     }
 377   else
 378     {
 379       /* No debug output is wanted. */
 380     }
 381 }
 382
 383
 384
 385 \f
 386 static void
 387 consider_visiting(FTS *p, FTSENT *ent)
 388 {
 389   struct stat statbuf;
 390   mode_t mode;
 391   int ignore, isdir;
 392
 393   if (options.debug_options & DebugSearch)
 394     fprintf(stderr,
 395             "consider_visiting: fts_info=%-6s, fts_level=%2d, prev_depth=%d "
 396             "fts_path=%s, fts_accpath=%s\n",
 397             get_fts_info_name(ent->fts_info),
 398             (int)ent->fts_level, prev_depth,
 399             quotearg_n_style(0, options.err_quoting_style, ent->fts_path),
 400             quotearg_n_style(1, options.err_quoting_style, ent->fts_accpath));
 401
 402   if (ent->fts_info == FTS_DP)
 403     {
 404       left_dir();
 405     }
 406   else if (ent->fts_level > prev_depth || ent->fts_level==0)
 407     {
 408       left_dir();
 409     }
 410   inside_dir(p->fts_cwd_fd);
 411   prev_depth = ent->fts_level;
 412
 413
 414   /* Cope with various error conditions. */
 415   if (ent->fts_info == FTS_ERR
 416       || ent->fts_info == FTS_DNR)
 417     {
 418       error(0, ent->fts_errno, "%s",
 419             safely_quote_err_filename(0, ent->fts_path));
 420       error_severity(1);
 421       return;
 422     }
 423   else if (ent->fts_info == FTS_DC)
 424     {
 425       issue_loop_warning(ent);
 426       error_severity(1);
 427       return;
 428     }
 429   else if (ent->fts_info == FTS_SLNONE)
 430     {
 431       /* fts_read() claims that ent->fts_accpath is a broken symbolic
 432        * link.  That would be fine, but if this is part of a symbolic
 433        * link loop, we diagnose the problem and also ensure that the
 434        * eventual return value is nonzero.   Note that while the path
 435        * we stat is local (fts_accpath), we print the fill path name
 436        * of the file (fts_path) in the error message.
 437        */
 438       if (symlink_loop(ent->fts_accpath))
 439         {
 440           error(0, ELOOP, "%s", safely_quote_err_filename(0, ent->fts_path));
 441           error_severity(1);
 442           return;
 443         }
 444     }
 445   else if (ent->fts_info == FTS_NS)
 446     {
 447       if (ent->fts_level == 0)
 448         {
 449           /* e.g., nonexistent starting point */
 450           error(0, ent->fts_errno, "%s",
 451                 safely_quote_err_filename(0, ent->fts_path));
 452           error_severity(1);    /* remember problem */
 453           return;
 454         }
 455       else
 456         {
 457           /* The following if statement fixes Savannah bug #19605
 458            * (failure to diagnose a symbolic link loop)
 459            */
 460           if (symlink_loop(ent->fts_accpath))
 461             {
 462               error(0, ELOOP, "%s",
 463                     safely_quote_err_filename(0, ent->fts_path));
 464               error_severity(1);
 465               return;
 466             }
 467         }
 468     }
 469
 470   /* Cope with the usual cases. */
 471   if (ent->fts_info == FTS_NSOK
 472       || ent->fts_info == FTS_NS /* e.g. symlink loop */)
 473     {
 474       assert (!state.have_stat);
 475       assert (!state.have_type);
 476       state.type = mode = 0;
 477     }
 478   else
 479     {
 480       state.have_stat = true;
 481       state.have_type = true;
 482       statbuf = *(ent->fts_statp);
 483       state.type = mode = statbuf.st_mode;
 484
 485       if (00000 == mode)
 486         {
 487           /* Savannah bug #16378. */
 488           error(0, 0, _("Warning: file %s appears to have mode 0000"),
 489                 quotearg_n_style(0, options.err_quoting_style, ent->fts_path));
 490         }
 491     }
 492
 493   if (mode)
 494     {
 495       if (!digest_mode(mode, ent->fts_path, ent->fts_name, &statbuf, 0))
 496         return;
 497     }
 498
 499   /* examine this item. */
 500   ignore = 0;
 501   isdir = S_ISDIR(statbuf.st_mode)
 502     || (FTS_D  == ent->fts_info)
 503     || (FTS_DP == ent->fts_info)
 504     || (FTS_DC == ent->fts_info);
 505
 506   if (isdir && (ent->fts_info == FTS_NSOK))
 507     {
 508       /* This is a directory, but fts did not stat it, so
 509        * presumably would not be planning to search its
 510        * children.  Force a stat of the file so that the
 511        * children can be checked.
 512        */
 513       fts_set(p, ent, FTS_AGAIN);
 514       return;
 515     }
 516
 517   if (options.maxdepth >= 0)
 518     {
 519       if (ent->fts_level >= options.maxdepth)
 520         {
 521           fts_set(p, ent, FTS_SKIP); /* descend no further */
 522
 523           if (ent->fts_level > options.maxdepth)
 524             ignore = 1;         /* don't even look at this one */
 525         }
 526     }
 527
 528   if ( (ent->fts_info == FTS_D) && !options.do_dir_first )
 529     {
 530       /* this is the preorder visit, but user said -depth */
 531       ignore = 1;
 532     }
 533   else if ( (ent->fts_info == FTS_DP) && options.do_dir_first )
 534     {
 535       /* this is the postorder visit, but user didn't say -depth */
 536       ignore = 1;
 537     }
 538   else if (ent->fts_level < options.mindepth)
 539     {
 540       ignore = 1;
 541     }
 542
 543   if (!ignore)
 544     {
 545       visit(p, ent, &statbuf);
 546     }
 547
 548   /* XXX: if we allow a build-up of pending arguments for "-execdir foo {} +"
 549    * we need to execute them in the same directory as we found the item.
 550    * If we are trying to do "find a -execdir echo {} +", we will need to
 551    * echo
 552    *      a while in the original working directory
 553    *      b while in a
 554    *      c while in b (just before leaving b)
 555    *
 556    * These restrictions are hard to satisfy while using fts().   The reason is
 557    * that it doesn't tell us just before we leave a directory.  For the moment,
 558    * we punt and don't allow the arguments to build up.
 559    */
 560   if (state.execdirs_outstanding)
 561     {
 562       show_outstanding_execdirs(stderr);
 563       run_in_dir(p->fts_cwd_fd, complete_execdirs_cb, NULL);
 564     }
 565
 566   if (ent->fts_info == FTS_DP)
 567     {
 568       /* we're leaving a directory. */
 569       state.stop_at_current_level = false;
 570     }
 571 }
 572
 573
 574 \f
 575 static void
 576 find(char *arg)
 577 {
 578   char * arglist[2];
 579   FTS *p;
 580   FTSENT *ent;
 581
 582
 583   state.starting_path_length = strlen(arg);
 584   inside_dir(AT_FDCWD);
 585
 586   arglist[0] = arg;
 587   arglist[1] = NULL;
 588
 589   switch (options.symlink_handling)
 590     {
 591     case SYMLINK_ALWAYS_DEREF:
 592       ftsoptions |= FTS_COMFOLLOW|FTS_LOGICAL;
 593       break;
 594
 595     case SYMLINK_DEREF_ARGSONLY:
 596       ftsoptions |= FTS_COMFOLLOW|FTS_PHYSICAL;
 597       break;
 598
 599     case SYMLINK_NEVER_DEREF:
 600       ftsoptions |= FTS_PHYSICAL;
 601       break;
 602     }
 603
 604   if (options.stay_on_filesystem)
 605     ftsoptions |= FTS_XDEV;
 606
 607   p = fts_open(arglist, ftsoptions, NULL);
 608   if (NULL == p)
 609     {
 610       error (0, errno, _("cannot search %s"
 611                          /* TRANSLATORS: the argument is either
 612                             a file or a directory. */
 613                          ),
 614              safely_quote_err_filename(0, arg));
 615     }
 616   else
 617     {
 618       while ( (ent=fts_read(p)) != NULL )
 619         {
 620           state.have_stat = false;
 621           state.have_type = false;
 622           state.type = 0;
 623           consider_visiting(p, ent);
 624         }
 625       fts_close(p);
 626       p = NULL;
 627     }
 628 }
 629
 630
 631 static void
 632 process_all_startpoints(int argc, char *argv[])
 633 {
 634   int i;
 635
 636   /* figure out how many start points there are */
 637   for (i = 0; i < argc && !looks_like_expression(argv[i], true); i++)
 638     {
 639       state.starting_path_length = strlen(argv[i]); /* TODO: is this redundant? */
 640       find(argv[i]);
 641     }
 642
 643   if (i == 0)
 644     {
 645       /*
 646        * We use a temporary variable here because some actions modify
 647        * the path temporarily.  Hence if we use a string constant,
 648        * we get a coredump.  The best example of this is if we say
 649        * "find -printf %H" (note, not "find . -printf %H").
 650        */
 651       char defaultpath[2] = ".";
 652       find(defaultpath);
 653     }
 654 }
 655
 656
 657
 658 \f
 659 int
 660 main (int argc, char **argv)
 661 {
 662   int end_of_leading_options = 0; /* First arg after any -H/-L etc. */
 663   struct predicate *eval_tree;
 664
 665   program_name = argv[0];
 666   state.exit_status = 0;
 667   state.execdirs_outstanding = false;
 668   state.cwd_dir_fd = AT_FDCWD;
 669
 670   /* Set the option defaults before we do the locale initialisation as
 671    * check_nofollow() needs to be executed in the POSIX locale.
 672    */
 673   set_option_defaults(&options);
 674
 675 #ifdef HAVE_SETLOCALE
 676   setlocale (LC_ALL, "");
 677 #endif
 678
 679   bindtextdomain (PACKAGE, LOCALEDIR);
 680   textdomain (PACKAGE);
 681   atexit (close_stdout);
 682
 683   /* Check for -P, -H or -L options.  Also -D and -O, which are
 684    * both GNU extensions.
 685    */
 686   end_of_leading_options = process_leading_options(argc, argv);
 687
 688   if (options.debug_options & DebugStat)
 689     options.xstat = debug_stat;
 690
 691 #ifdef DEBUG
 692   fprintf (stderr, "cur_day_start = %s", ctime (&options.cur_day_start));
 693 #endif /* DEBUG */
 694
 695
 696   /* We are now processing the part of the "find" command line
 697    * after the -H/-L options (if any).
 698    */
 699   eval_tree = build_expression_tree(argc, argv, end_of_leading_options);
 700
 701   /* safely_chdir() needs to check that it has ended up in the right place.
 702    * To avoid bailing out when something gets automounted, it checks if
 703    * the target directory appears to have had a directory mounted on it as
 704    * we chdir()ed.  The problem with this is that in order to notice that
 705    * a file system was mounted, we would need to lstat() all the mount points.
 706    * That strategy loses if our machine is a client of a dead NFS server.
 707    *
 708    * Hence if safely_chdir() and wd_sanity_check() can manage without needing
 709    * to know the mounted device list, we do that.
 710    */
 711   if (!options.open_nofollow_available)
 712     {
 713 #ifdef STAT_MOUNTPOINTS
 714       init_mounted_dev_list();
 715 #endif
 716     }
 717
 718
 719   starting_desc = open (".", O_RDONLY
 720 #if defined O_LARGEFILE
 721                         |O_LARGEFILE
 722 #endif
 723                         );
 724   if (0 <= starting_desc && fchdir (starting_desc) != 0)
 725     {
 726       close (starting_desc);
 727       starting_desc = -1;
 728     }
 729   if (starting_desc < 0)
 730     {
 731       starting_dir = xgetcwd ();
 732       if (! starting_dir)
 733         error (1, errno, _("cannot get current directory"));
 734     }
 735
 736
 737   process_all_startpoints(argc-end_of_leading_options, argv+end_of_leading_options);
 738
 739   /* If "-exec ... {} +" has been used, there may be some
 740    * partially-full command lines which have been built,
 741    * but which are not yet complete.   Execute those now.
 742    */
 743   show_success_rates(eval_tree);
 744   cleanup();
 745   return state.exit_status;
 746 }
 747
 748 boolean
 749 is_fts_enabled(int *fts_options)
 750 {
 751   /* this version of find (i.e. this main()) uses fts. */
 752   *fts_options = ftsoptions;
 753   return true;
 754 }