Path specifications
*******************

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.

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 during the run are not seen.

Directory list generation
=========================

Kpathsearch constructs a directory list from an environment variable 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 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.

The ``colon'' and ``slash'' mentioned below aren't necessarily : and / on non-Unix systems; the library tries to adapt these characters to other operating systems' conventions.

The following subdirectories explain the various kinds of expansion the path is subjected to.  After expansion, nonexistent directories in the path is ignored.

Default expansion
-----------------

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.

Tilde expansion
---------------

A leading ~ or ~USER in a path component is replaced by the current or USER's home directory, respectively.

If USER is invalid, or the home directory cannot be determined, Kpathsea uses . instead.

Variable expansion
------------------

A construct $foo or ${foo} is replaced by the expansion of the environment variable 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 $'s and braces as necessary for your shell.

Shell variable values cannot be seen by Kpathsea.

Subdirectory expansion
----------------------

If a component directory D contains //, all subdirectories of D are included in the path: 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.

If you specify any filename components after the //, only subdirectories which have 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.

Subdirectory problems
.....................

Perhaps the first problem is best put as a question-and-answer.

Question: I know all about slow starting TeX :-).  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 /usr/local/lib/tex/macros// and .../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 stat (if you don't know what 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 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.

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 DEBUG_STAT in the variable kpathsea_debug (see 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.

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

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 . and ..).  That is to say, the 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 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.

You can disable the trick by undefining UNIX_ST_LINK in kpathsea/config.h.

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

The directory immediately followed by the //, 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 D; then D will no longer be a leaf, and the symlinks will be followed.

Path specification example
--------------------------

For example, the following value for an environment variable says to search the following: the current user's fonts directory and alll its subdirectories, then the directory fonts in user karls home directory, and finally the system default directories specified at compilation time.

     ~/fonts//:~karl/fonts:

File lookups
============

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.

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