1

For a Perl script I'm working on, I'm looking for a fast and reliable way to find all subdirectories (transitively) of a given directory which are leaves, i.e. those not having any subdirectories of their own. For example, given this hierarchy:

foo/
foo/bar/
foo/bar/baz
foo/you_fool

my hypothetical function, when called with "foo" as the argument, should return the list ("foo/bar/baz/", "foo/you_fool/").

Because this will clearly require File::Find or something equivalent, and that already does a stat system call for each file it finds, fast means not doing another stat on each file, although one extra stat on each directory, i.e. the value of $File::Find::dir is okay.

Because my main target system is Darwin aka MacOS, I unfortunately cannot use the nlink field of struct stat; it doesn't seem to be meaningful on that file system. I'm aware that on a "real Unix" file system I could just compare nlink to 2 for each directory.

If it matters, we may disregard symlinks, special files and all other oddities; the hierarchies I'll be searching are very clean and regular.

0

3 Answers 3

1

You could do something like:

perl -MFile::Find -le '
  find(sub { 
         if (-d _) {
           undef $leaves{$File::Find::name};
           delete $leaves{$File::Find::dir};
         }
       }, ".");
  print for keys %leaves'

undef sets hash element for the current dir to an undef value, while delete deletes the hash element for the parent directory. So at the end the keys of the %leaves hash contain only the leaves.

With -d _, we're reusing the information from the lstat() that File::Find did on the current file, so no extra lstat() / stat() is performed. With -d alone, an extra stat() (not lstat()) would be performed, which means it would also return true for symlinks to directories.

While it works in my test, it may not be a valid and future-proof thing to do. The documentation says:

[with "follow"] It is guaranteed that an lstat has been called before the user's "wanted()" function is called. This enables fast file checks involving "_". Note that this guarantee no longer holds if follow or follow_fast are not set.

Doing if (! -l && -d _) may be safer, at the expense of an extra lstat() being performed for each file.

1
  • Thanks for the explanation about -d and lstat.
    – q.undertow
    Commented Aug 17, 2022 at 15:50
0

Just some thoughts. I'm not a perl maestro, so not sure what File::Find can do, so I turned to the shell 'find'.

find / -type d -print

prints out a list of directories starting from '/', so there's the basic list. I very much doubt you can improve on its speed in perl, though a C app just might manage. I suspect it would be wasted effort for miniscule benefits.

GNU find has an option '-printf' that accepts a '%h' flag to print out the parent directory. What you could do therefore is to -printf both the path %p and the parent path %h at the same time, then in perl split the parents off into a new list. You now have a list of paths that are not leaves, so remove those from the %p list, and you're done.

Sadly MacOS doesn't have the GNU find but a lesser version. You can install GNU find using 'brew', but it wouldn't be too hard to create the effect of %h from the %p lines in perl directly.

One last thing to note. Relying on linefeed termination of pathnames from a pipe or similar is known to be subject to error under some circumstances, hence GNU find and (I think) MacOS find both have a zero-terminate option for lines separated by \0 rather than \n. If you can use it, do so.

0

It turns out to be much more straightforward than I thought, using a feature of File::Find that I had not known, or had forgotten. Here's the entire script (before I start adding code irrelevant to the question);

#! /usr/bin/env perl

use warnings;
use strict;
use File::Find;
use Cwd qw(realpath);

@main::leaves = ();

sub preprocess {
  our (@leaves);
  my @names = @_;
  my @subdirs = grep { $_ ne q(.) && $_ ne q(..) && -d } @names;
  push @leaves, $File::Find::dir unless @subdirs;
  return @subdirs;
}

sub wanted {
  # do nothing at all
}

sub find_leaves {
  my @roots = map { realpath($_) } @ARGV;
  find({ wanted => \&wanted, preprocess => \&preprocess }, @roots);
}

sub main {
  our (@leaves);
  @ARGV or push @ARGV, q(.);
  find_leaves();
  print $_, qq(\n) foreach (@leaves);
  # my $num_leaves = $#leaves + 1;
}

main();
__END__
1
  • Note that -d implies extra stat()s (not lstat()s, meaning you'll also have problems with symlinks to directories in leaves). Commented Aug 17, 2022 at 9:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .