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