@c Copyright (C) 1993 Karl Berry.
@c For copying conditions, see the file copying.texi.

@node Path specifications
@chapter Path specifications

@cindex path specification
@cindex specifying search paths
@cindex search path specification

This chapter describes the user interface of the path specifications
that the Kpathsearch library implements.

Conceptually, there are two distinct stages: generating a list of
directories in which to search, and then looking up files using that
list.  The sections below describe each of these in turn.

@cindex lazy evaluation
In the implementation, however, these stages are interleaved---directory
lists are only generated as needed for a particular file lookup, then
they are cached for future lookups.  (Analogous to lazy evaluation in
programming languages.)  This implies that directories that are created
@emph{during} the run are not seen.

@menu
* Directory list generation::	How you specify where to search.
* File lookups::		How files are found in directory lists.
@end menu


@node Directory list generation
@section Directory list generation

@cindex directory list generation
@cindex generation of directory lists

@cindex environment variable, source for path
@cindex configuration file, source for path
@cindex compilation value, source for path
@cindex sources for path
Kpathsearch constructs a directory list from an environment variable
@var{var} set by the user, (possibly) a setting from a configuration
file, and a default path set at compile time.  Each of these are
colon-separated lists of directories.  If @var{var} is set, its value is
used; otherwise, if a config file defines a value, that value is used;
otherwise, the compilation default is used.  In any case, once the path
specification to use is determined, its evaluation is independent of its
source.

@cindex magic characters
@kindex : @r{may not be :}
@kindex / @r{may not be /}
The ``colon'' and ``slash'' mentioned below aren't
necessarily @samp{:} and @samp{/} on non-Unix systems; the library tries
to adapt these characters to other operating systems' conventions.

@cindex expansion, in paths
The following subdirectories explain the various kinds of
@dfn{expansion} the path is subjected to.  After expansion, nonexistent
directories in the path is ignored.

@menu
* Default expansion::           Extra colons expand to the compilation default.
* Tilde expansion::             ~ and ~user expand to home directories.
* Variable expansion::          $foo and $@{foo@} expand to environment values.
* Subdirectory expansion::	a// and a//b recursively expand to subdirs.
* Path specification example::	An example.
@end menu


@node Default expansion
@subsection Default expansion

@kindex ::
@cindex doubled colon, in paths
@cindex extra colons in paths
@cindex default expansion
@cindex expansion, default

If an environment variable or config file value has a leading or
trailing or doubled colon, the default path is inserted at that point.

Putting an extra colon into the default value has unpredictable results,
and may cause the program to crash, so installers beware.


@node Tilde expansion
@subsection Tilde expansion

@kindex ~
@cindex home directories in paths
@cindex tilde expansion
@cindex expansion, tilde

A leading @samp{~} or @samp{~@var{user}} in a path component is replaced
by the current or @var{user}'s home directory, respectively.

If @var{user} is invalid, or the home directory cannot be determined,
Kpathsea uses @file{.} instead.


@node Variable expansion
@subsection Variable expansion

@kindex $
@cindex environment variables in paths
@cindex variable expansion
@cindex expansion, variable

A construct @samp{$foo} or @samp{$@{foo@}} is replaced by the expansion
of the environment variable @samp{foo}.  In the first case, the variable
name consists of consecutive alphanumeric-or-underscore characters.  In
the second, the variable name consists of everything between the
braces.

Remember to quote the @samp{$}'s and braces as necessary for your shell.

@emph{Shell} variable values cannot be seen by Kpathsea.


@node Subdirectory expansion
@subsection Subdirectory expansion

@kindex //
@cindex subdirectory searching
@cindex expansion, subdirectory

If a component directory @var{d} contains @samp{//}, all
subdirectories of @var{d} are included in the path: first those
subdirectories directly under @var{d}, then the subsubdirectories under
those, and so on.  At each level, the order in which the directories are
searched is unspecified.

If you specify any filename components after the @samp{//}, only
subdirectories which have those components are included.  For example,
@samp{/a//b} would expand into directories @file{/a/1/b}, @file{/a/2/b},
@file{/a/1/1/b}, and so on, but not @file{/a/b/c} or @file{/a/1}.

@menu
* Subdirectory problems::       If you have trouble with subdirectories.
@end menu


@node Subdirectory problems
@subsubsection Subdirectory problems

@cindex problems with subdirectory searching
@cindex subdirectory searching problems

@cindex excessive startup time
Perhaps the first problem is best put as a question-and-answer.

Question: I know all about slow starting @TeX{} @samp{:-)}.  How do I
organize the directory scheme to avoid the slowness, while at the same
time enjoying a structured inputs directory?

(Naturally, this applies to any Kpathsea-using program, not just @TeX{}.)

I will give the false Short Answer first, then the Real Explanation.

The Short Answer: in your equivalent of
@file{/usr/local/lib/tex/macros//} and @file{.../fonts//}, make each
subdirectory contain either 1) only directories; or 2) only files.

As long as you do not have (literally) hundreds of subdirectories, this
should cure the problem.  It has in every case I have been told about.


The Real Explanation: the thing that makes @TeX{} slow is calling
@code{stat} (if you don't know what @code{stat} (2) is, ignore this explanation)
on ``too many'' pathnames, where ``too many'' is some nebulous number
depending on things like whether the filesystem is NFS-mounted or not,
whether it's on a fast disk, whether your Fast File System
implementation is really Fast, etc., etc.

(Side note: If you're curious, you can find this number by writing a
program that does nothing but read filenames (presumably from a file)
and stat them, and see how many pathnames make the execution time
noticeable.  On the systems I use (Suns with an NFS-mounted directory,
ISC 2.2.1 and a local directory), it's several hundred, at least.  On an
NFS-mounted mounted directory under Solaris 2.1, 150 is quite slow,
according to @samp{hammer@@kis.uni-freiburg.de}.)

Whether or not it's directories or files that are being stat-ed is
irrelevant (this is why the Short Answer is false).  It's sheer numbers
that count.

@vindex DEBUG_STAT
@vindex kpathsea_debug
@cindex debugging slow startup time
@flindex debug.h
If you think your directory structure is ok, and you're still
experiencing slowness, I advise running @TeX{} (or whatever program)
under a debugger, setting the bit @code{DEBUG_STAT} in the variable
@code{kpathsea_debug} (see @file{debug.h}) to one and seeing exactly
what is getting stat-ed.  If only a few things are getting stat-ed, and
@TeX{} is still slow, tell me.

@cindex trick for detecting leaf directories
@cindex leaf directory trick
I should also mention ``the trick'', which I stole from GNU find.
(Matthew Farwell @samp{<dylan@@ibmpcug.co.uk>} suggested it, and David
MacKenzie @samp{<djm@@gnu.ai.mit.edu>} implemented it, I believe.)

@vindex st_nlink
The trick is that in every real Unix implementation (that I know about)
(as opposed to the POSIX specification), a directory which contains no
subdirectories will have exactly two links (specifically, one each for
@file{.} and @file{..}).  That is to say, the @code{st_nlink} field in
the stat structure will be two.  Thus, the path searching code doesn't
have to stat every entry in the bottom-level directories---it can check
@code{st_nlink}, and if it's two, it knows there are no subdirectories.

But if you have a directory that contains *one* subdirectory and five
hundred files, st_nlink will be 3, and Kpathsea has to
stat every one of those 501 entries.  Therein lies slowness.

@vindex UNIX_ST_LINK
You can disable the trick by undefining UNIX_ST_LINK in
@file{kpathsea/config.h}.

@cindex symbolic links not found
@cindex leaf directories wrongly guessed
The subdirectory searching has one other known (and irreconciliable)
deficiency.  If a directory @var{d} being searched for subdirectories
contains plain files and symbolic links to other directories, but no
true subdirectories, @var{d} will be considered a leaf directory, i.e.,
the symbolic links will not be followed.

The directory immediately followed by the @samp{//}, however, is
always searched for subdirectories, even if it is a ``leaf''.  We do
this since presumably you would not have asked for the directory to be
searched for subdirectories if you didn't want it to be.

This is a consequence of the trick explained above.  You can work around
this problem by simply creating an empty dummy subdirectory in @var{d};
then @var{d} will no longer be a leaf, and the symlinks will be
followed.


@node Path specification example
@subsection Path specification example

@cindex path specification, example
For example, the following value for an environment variable says to
search the following: the current user's @file{fonts} directory and alll
its subdirectories, then the directory @file{fonts} in user @samp{karl}s
home directory, and finally the system default directories specified at
compilation time.

@example
~/fonts//:~karl/fonts:
@end example


@node File lookups
@section File lookups

@cindex filename lookup
@cindex lookup of filenames

Given the directory list generated from the rules in the previous
section, looking up a file presents no problem at all: we just look in
each directory in the list in turn, and return the first one found.

@cindex absolute filenames
@cindex relative filenames
@cindex explicitly relative filenames
@cindex filenames, absolute or explicitly relative
The only complication is if the filename is absolute or explicitly
relative, i.e., (under Unix-like operating systems) starts with @samp{/}
or @samp{./} or @samp{../}.  Then the library does not use the directory
list at all.  Instead, the file is simply searched for in the given
directory.
