1 /* find -- search for files in a directory hierarchy
2 Copyright (C) 1990, 91, 92, 93, 94, 2000, 2003 Free Software Foundation, Inc.
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)
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.
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., 9 Temple Place - Suite 330, Boston, MA 02111-1307,
19 /* GNU find was written by Eric Decker <cire@cisco.com>,
20 with enhancements by David MacKenzie <djm@gnu.ai.mit.edu>,
21 Jay Plett <jay@silence.princeton.nj.us>,
22 and Tim Wood <axolotl!tim@toad.com>.
23 The idea for -print0 and xargs -0 came from
24 Dan Bernstein <brnstnd@kramden.acf.nyu.edu>. */
43 # define _(Text) gettext (Text)
46 #define textdomain(Domain)
47 #define bindtextdomain(Package, Directory)
50 # define N_(String) gettext_noop (String)
52 # define N_(String) (String)
55 #define apply_predicate(pathname, stat_buf_ptr, node) \
56 (*(node)->pred_func)((pathname), (stat_buf_ptr), (node))
58 static void process_top_path
PARAMS((char *pathname
));
59 static int process_path
PARAMS((char *pathname
, char *name
, boolean leaf
, char *parent
));
60 static void process_dir
PARAMS((char *pathname
, char *name
, int pathlen
, struct stat
*statp
, char *parent
));
61 static boolean no_side_effects
PARAMS((struct predicate
*pred
));
62 static boolean default_prints
PARAMS((struct predicate
*pred
));
64 /* Name this program was run with. */
67 /* All predicates for each path to process. */
68 struct predicate
*predicates
;
70 /* The last predicate allocated. */
71 struct predicate
*last_pred
;
73 /* The root of the evaluation tree. */
74 static struct predicate
*eval_tree
;
76 /* If true, process directory before contents. True unless -depth given. */
79 /* If >=0, don't descend more than this many levels of subdirectories. */
82 /* If >=0, don't process files above this level. */
85 /* Current depth; 0 means current path is a command line arg. */
88 /* Output block size. */
89 int output_block_size
;
91 /* Time at start of execution. */
94 /* Seconds between 00:00 1/1/70 and either one day before now
95 (the default), or the start of today (if -daystart is given). */
98 /* If true, cur_day_start has been adjusted to the start of the day. */
101 /* If true, do not assume that files in directories with nlink == 2
102 are non-directories. */
103 boolean no_leaf_check
;
105 /* If true, don't cross filesystem boundaries. */
106 boolean stay_on_filesystem
;
108 /* If true, don't descend past current directory.
109 Can be set by -prune, -maxdepth, and -xdev/-mount. */
110 boolean stop_at_current_level
;
112 /* The full path of the initial working directory, or "." if
113 STARTING_DESC is nonnegative. */
114 char const *starting_dir
= ".";
116 /* A file descriptor open to the initial working directory.
117 Doing it this way allows us to work when the i.w.d. has
118 unreadable parents. */
121 /* The stat buffer of the initial working directory. */
122 struct stat starting_stat_buf
;
124 /* If true, we have called stat on the current path. */
127 /* The file being operated on, relative to the current directory.
128 Used for stat, readlink, remove, and opendir. */
131 /* Length of current path. */
134 /* true if following symlinks. Should be consistent with xstat. */
137 /* Pointer to the function used to stat files. */
140 /* Status value to return to system. */
145 debug_stat (file
, bufp
)
149 fprintf (stderr
, "debug_stat (%s)\n", file
);
150 return lstat (file
, bufp
);
152 #endif /* DEBUG_STAT */
155 main (int argc
, char **argv
)
158 PFB parse_function
; /* Pointer to the function which parses. */
159 struct predicate
*cur_pred
;
160 char *predicate_name
; /* Name of predicate being parsed. */
162 program_name
= argv
[0];
164 #ifdef HAVE_SETLOCALE
165 setlocale (LC_ALL
, "");
167 bindtextdomain (PACKAGE
, LOCALEDIR
);
168 textdomain (PACKAGE
);
173 maxdepth
= mindepth
= -1;
174 start_time
= time (NULL
);
175 cur_day_start
= start_time
- DAYSECS
;
177 no_leaf_check
= false;
178 stay_on_filesystem
= false;
183 #else /* !DEBUG_STAT */
185 #endif /* !DEBUG_STAT */
188 human_block_size (getenv ("FIND_BLOCK_SIZE"), 0, &output_block_size
);
190 if (getenv("FIND_BLOCK_SIZE"))
192 error (1, errno
, _("The environment variable FIND_BLOCK_SIZE is not supported"));
198 printf ("cur_day_start = %s", ctime (&cur_day_start
));
201 /* Find where in ARGV the predicates begin. */
202 for (i
= 1; i
< argc
&& strchr ("-!(),", argv
[i
][0]) == NULL
; i
++)
205 /* Enclose the expression in `( ... )' so a default -print will
206 apply to the whole expression. */
207 parse_open (argv
, &argc
);
208 /* Build the input order list. */
211 if (strchr ("-!(),", argv
[i
][0]) == NULL
)
212 usage (_("paths must precede expression"));
213 predicate_name
= argv
[i
];
214 parse_function
= find_parser (predicate_name
);
215 if (parse_function
== NULL
)
216 /* Command line option not recognized */
217 error (1, 0, _("invalid predicate `%s'"), predicate_name
);
219 if (!(*parse_function
) (argv
, &i
))
222 /* Command line option requires an argument */
223 error (1, 0, _("missing argument to `%s'"), predicate_name
);
225 error (1, 0, _("invalid argument `%s' to `%s'"),
226 argv
[i
], predicate_name
);
229 if (predicates
->pred_next
== NULL
)
231 /* No predicates that do something other than set a global variable
232 were given; remove the unneeded initial `(' and add `-print'. */
233 cur_pred
= predicates
;
234 predicates
= last_pred
= predicates
->pred_next
;
235 free ((char *) cur_pred
);
236 parse_print (argv
, &argc
);
238 else if (!default_prints (predicates
->pred_next
))
240 /* One or more predicates that produce output were given;
241 remove the unneeded initial `('. */
242 cur_pred
= predicates
;
243 predicates
= predicates
->pred_next
;
244 free ((char *) cur_pred
);
248 /* `( user-supplied-expression ) -print'. */
249 parse_close (argv
, &argc
);
250 parse_print (argv
, &argc
);
254 printf (_("Predicate List:\n"));
255 print_list (predicates
);
258 /* Done parsing the predicates. Build the evaluation tree. */
259 cur_pred
= predicates
;
260 eval_tree
= get_expr (&cur_pred
, NO_PREC
);
262 /* Check if we have any left-over predicates (this fixes
263 * Debian bug #185202).
265 if (cur_pred
!= NULL
)
267 /* This happens for example if the user gave
268 * the command 'find x -print \)'
270 const char *predname
= find_pred_name (cur_pred
->pred_func
);
272 /* Remove trainling whitespace. We need to use an int */
273 size_t len
= strlen(predname
);
274 while (len
> 0 && isblank(predname
[len
-1]))
278 error (1, 0, _("unexpected extra predicate `%.*s'"),
283 printf (_("Eval Tree:\n"));
284 print_tree (eval_tree
, 0);
287 /* Rearrange the eval tree in optimal-predicate order. */
288 opt_expr (&eval_tree
);
290 /* Determine the point, if any, at which to stat the file. */
291 mark_stat (eval_tree
);
294 printf (_("Optimized Eval Tree:\n"));
295 print_tree (eval_tree
, 0);
298 starting_desc
= open (".", O_RDONLY
);
299 if (0 <= starting_desc
&& fchdir (starting_desc
) != 0)
301 close (starting_desc
);
304 if (starting_desc
< 0)
306 starting_dir
= xgetcwd ();
308 error (1, errno
, _("cannot get current directory"));
310 if ((*xstat
) (".", &starting_stat_buf
) != 0)
311 error (1, errno
, _("cannot get current directory"));
313 /* If no paths are given, default to ".". */
314 for (i
= 1; i
< argc
&& strchr ("-!(),", argv
[i
][0]) == NULL
; i
++)
315 process_top_path (argv
[i
]);
317 process_top_path (".");
322 /* Safely go back to the starting directory. */
326 struct stat stat_buf
;
328 if (starting_desc
< 0)
330 if (chdir (starting_dir
) != 0)
331 error (1, errno
, "%s", starting_dir
);
332 if ((*xstat
) (".", &stat_buf
) != 0)
333 error (1, errno
, "%s", starting_dir
);
334 if (stat_buf
.st_dev
!= starting_stat_buf
.st_dev
||
335 stat_buf
.st_ino
!= starting_stat_buf
.st_ino
)
336 error (1, 0, _("%s changed during execution of %s"), starting_dir
, program_name
);
340 if (fchdir (starting_desc
) != 0)
341 error (1, errno
, "%s", starting_dir
);
345 /* Descend PATHNAME, which is a command-line argument. */
348 process_top_path (char *pathname
)
350 struct stat stat_buf
, cur_stat_buf
;
353 path_length
= strlen (pathname
);
355 /* We stat each pathname given on the command-line twice --
356 once here and once in process_path. It's not too bad, though,
357 since the kernel can read the stat information out of its inode
358 cache the second time. */
359 if ((*xstat
) (pathname
, &stat_buf
) == 0 && S_ISDIR (stat_buf
.st_mode
))
361 if (chdir (pathname
) < 0)
363 error (0, errno
, "%s", pathname
);
368 /* Check that we are where we should be. */
369 if ((*xstat
) (".", &cur_stat_buf
) != 0)
370 error (1, errno
, "%s", pathname
);
371 if (cur_stat_buf
.st_dev
!= stat_buf
.st_dev
||
372 cur_stat_buf
.st_ino
!= stat_buf
.st_ino
)
373 error (1, 0, _("%s changed during execution of %s"), pathname
, program_name
);
375 process_path (pathname
, ".", false, ".");
379 process_path (pathname
, pathname
, false, ".");
382 /* Info on each directory in the current tree branch, to avoid
383 getting stuck in symbolic link loops. */
389 static struct dir_id
*dir_ids
= NULL
;
390 /* Entries allocated in `dir_ids'. */
391 static int dir_alloc
= 0;
392 /* Index in `dir_ids' of directory currently being searched.
393 This is always the last valid entry. */
394 static int dir_curr
= -1;
395 /* (Arbitrary) number of entries to grow `dir_ids' by. */
396 #define DIR_ALLOC_STEP 32
398 /* Recursively descend path PATHNAME, applying the predicates.
399 LEAF is true if PATHNAME is known to be in a directory that has no
400 more unexamined subdirectories, and therefore it is not a directory.
401 Knowing this allows us to avoid calling stat as long as possible for
404 NAME is PATHNAME relative to the current directory. We access NAME
407 PARENT is the path of the parent of NAME, relative to find's
410 Return nonzero iff PATHNAME is a directory. */
413 process_path (char *pathname
, char *name
, boolean leaf
, char *parent
)
415 struct stat stat_buf
;
416 static dev_t root_dev
; /* Device ID of current argument pathname. */
421 /* Assume it is a non-directory initially. */
422 stat_buf
.st_mode
= 0;
430 if ((*xstat
) (name
, &stat_buf
) != 0)
432 error (0, errno
, "%s", pathname
);
439 if (!S_ISDIR (stat_buf
.st_mode
))
441 if (curdepth
>= mindepth
)
442 apply_predicate (pathname
, &stat_buf
, eval_tree
);
446 /* From here on, we're working on a directory. */
448 stop_at_current_level
= maxdepth
>= 0 && curdepth
>= maxdepth
;
450 /* If we've already seen this directory on this branch,
451 don't descend it again. */
452 for (i
= 0; i
<= dir_curr
; i
++)
453 if (stat_buf
.st_ino
== dir_ids
[i
].ino
&&
454 stat_buf
.st_dev
== dir_ids
[i
].dev
)
455 stop_at_current_level
= true;
457 if (dir_alloc
<= ++dir_curr
)
459 dir_alloc
+= DIR_ALLOC_STEP
;
460 dir_ids
= (struct dir_id
*)
461 xrealloc ((char *) dir_ids
, dir_alloc
* sizeof (struct dir_id
));
463 dir_ids
[dir_curr
].ino
= stat_buf
.st_ino
;
464 dir_ids
[dir_curr
].dev
= stat_buf
.st_dev
;
466 if (stay_on_filesystem
)
469 root_dev
= stat_buf
.st_dev
;
470 else if (stat_buf
.st_dev
!= root_dev
)
471 stop_at_current_level
= true;
474 if (do_dir_first
&& curdepth
>= mindepth
)
475 apply_predicate (pathname
, &stat_buf
, eval_tree
);
478 fprintf(stderr
, "pathname = %s, stop_at_current_level = %d\n",
479 pathname
, stop_at_current_level
);
482 if (stop_at_current_level
== false)
483 /* Scan directory on disk. */
484 process_dir (pathname
, name
, strlen (pathname
), &stat_buf
, parent
);
486 if (do_dir_first
== false && curdepth
>= mindepth
)
489 apply_predicate (pathname
, &stat_buf
, eval_tree
);
497 /* Scan directory PATHNAME and recurse through process_path for each entry.
499 PATHLEN is the length of PATHNAME.
501 NAME is PATHNAME relative to the current directory.
503 STATP is the results of *xstat on it.
505 PARENT is the path of the parent of NAME, relative to find's
506 starting directory. */
509 process_dir (char *pathname
, char *name
, int pathlen
, struct stat
*statp
, char *parent
)
511 char *name_space
; /* Names of files in PATHNAME. */
512 int subdirs_left
; /* Number of unexamined subdirs in PATHNAME. */
513 struct stat stat_buf
;
515 subdirs_left
= statp
->st_nlink
- 2; /* Account for name and ".". */
518 name_space
= savedir (name
);
519 if (name_space
== NULL
)
523 error (0, errno
, "%s", pathname
);
527 error (1, 0, _("virtual memory exhausted"));
531 register char *namep
; /* Current point in `name_space'. */
532 char *cur_path
; /* Full path of each file to process. */
533 char *cur_name
; /* Base name of each file to process. */
534 unsigned cur_path_size
; /* Bytes allocated for `cur_path'. */
535 register unsigned file_len
; /* Length of each path to process. */
536 register unsigned pathname_len
; /* PATHLEN plus trailing '/'. */
538 if (pathname
[pathlen
- 1] == '/')
539 pathname_len
= pathlen
+ 1; /* For '\0'; already have '/'. */
541 pathname_len
= pathlen
+ 2; /* For '/' and '\0'. */
545 if (strcmp (name
, ".") && chdir (name
) < 0)
547 error (0, errno
, "%s", pathname
);
552 /* Check that we are where we should be. */
553 if ((*xstat
) (".", &stat_buf
) != 0)
554 error (1, errno
, "%s", pathname
);
555 if (stat_buf
.st_dev
!= dir_ids
[dir_curr
].dev
||
556 stat_buf
.st_ino
!= dir_ids
[dir_curr
].ino
)
557 error (1, 0, _("%s changed during execution of %s"), starting_dir
, program_name
);
559 for (namep
= name_space
; *namep
; namep
+= file_len
- pathname_len
+ 1)
561 /* Append this directory entry's name to the path being searched. */
562 file_len
= pathname_len
+ strlen (namep
);
563 if (file_len
> cur_path_size
)
565 while (file_len
> cur_path_size
)
566 cur_path_size
+= 1024;
569 cur_path
= xmalloc (cur_path_size
);
570 strcpy (cur_path
, pathname
);
571 cur_path
[pathname_len
- 2] = '/';
573 cur_name
= cur_path
+ pathname_len
- 1;
574 strcpy (cur_name
, namep
);
578 /* Normal case optimization.
579 On normal Unix filesystems, a directory that has no
580 subdirectories has two links: its name, and ".". Any
581 additional links are to the ".." entries of its
582 subdirectories. Once we have processed as many
583 subdirectories as there are additional links, we know
584 that the rest of the entries are non-directories --
585 in other words, leaf files. */
586 subdirs_left
-= process_path (cur_path
, cur_name
,
587 subdirs_left
== 0, pathname
);
589 /* There might be weird (e.g., CD-ROM or MS-DOS) filesystems
590 mounted, which don't have Unix-like directory link counts. */
591 process_path (cur_path
, cur_name
, false, pathname
);
595 if (strcmp (name
, "."))
597 /* We could go back and do the next command-line arg
598 instead, maybe using longjmp. */
609 if (chdir (dir
) != 0)
610 error (1, errno
, "%s", parent
);
612 /* Check that we are where we should be. */
613 if ((*xstat
) (".", &stat_buf
) != 0)
614 error (1, errno
, "%s", pathname
);
615 if (stat_buf
.st_dev
!=
616 (dir_curr
> 0 ? dir_ids
[dir_curr
-1].dev
: starting_stat_buf
.st_dev
) ||
618 (dir_curr
> 0 ? dir_ids
[dir_curr
-1].ino
: starting_stat_buf
.st_ino
))
621 error (1, 0, _("%s changed during execution of %s"), parent
, program_name
);
623 error (1, 0, _("%s/.. changed during execution of %s"), starting_dir
, program_name
);
633 /* Return true if there are no side effects in any of the predicates in
634 predicate list PRED, false if there are any. */
637 no_side_effects (struct predicate
*pred
)
641 if (pred
->side_effects
)
643 pred
= pred
->pred_next
;
648 /* Return true if there are no predicates with no_default_print in
649 predicate list PRED, false if there are any.
650 Returns true if default print should be performed */
653 default_prints (struct predicate
*pred
)
657 if (pred
->no_default_print
)
659 pred
= pred
->pred_next
;