kpathsea: Subdirectory expansion
5.3.6 Subdirectory expansion
----------------------------
Two or more consecutive slashes in a path element following a directory
D is replaced by all subdirectories of D: first those subdirectories
directly under D, then the subsubdirectories under those, and so on. At
each level, the order in which the directories are searched is
unspecified. (It's "directory order", and definitely not alphabetical.)
If you specify any filename components after the '//', only
subdirectories which match those components are included. For example,
'/a//b' would expand into directories '/a/1/b', '/a/2/b', '/a/1/1/b',
and so on, but not '/a/b/c' or '/a/1'.
You can include multiple '//' constructs in the path.
'//' at the beginning of a path is ignored; you didn't really want to
search every directory on the system, did you?
I should mention one related implementation trick, which I took from
GNU find. Matthew Farwell suggested it, and David MacKenzie implemented
it.
The trick is that in every real Unix implementation (as opposed to
the POSIX specification), a directory which contains no subdirectories
will have exactly two links (namely, one for '.' and one for '..').
That is to say, the 'st_nlink' field in the 'stat' structure will be
two. Thus, we don't have to stat everything in the bottom-level (leaf)
directories--we can just check 'st_nlink', notice it's two, and do no
more work.
But if you have a directory that contains a single subdirectory and
500 regular files, 'st_nlink' will be 3, and Kpathsea has to stat every
one of those 501 entries. Therein lies slowness.
You can disable the trick by undefining 'ST_NLINK_TRICK' in
'kpathsea/config.h'. (It is undefined by default except under Unix.)
Unfortunately, in some cases files in leaf directories are 'stat''d:
if the path specification is, say, '$TEXMF/fonts//pk//', then files in a
subdirectory '.../pk', even if it is a leaf, are checked. The reason
cannot be explained without reference to the implementation, so read
'kpathsea/elt-dirs.c' (search for 'may descend') if you are curious.
And if you find a way to solve the problem, please let me know.
Subdirectory expansion is implemented in the source file
'kpathsea/elt-dirs.c'.
Info Catalog
kpathsea: KPSE_DOT expansion
kpathsea: Path expansion