path: root/usr.bin/make/dir.c

/*	$OpenPackages$ */
/*	$OpenBSD: dir.c,v 1.46 2007/07/24 21:09:07 espie Exp $ */
/*	$NetBSD: dir.c,v 1.14 1997/03/29 16:51:26 christos Exp $	*/

/*
 * Copyright (c) 1999 Marc Espie.
 *
 * Extensive code changes for the OpenBSD project.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS
 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OPENBSD
 * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
/*
 * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
 * Copyright (c) 1988, 1989 by Adam de Boor
 * Copyright (c) 1989 by Berkeley Softworks
 * All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Adam de Boor.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#include <sys/param.h>
#include <sys/stat.h>
#include <dirent.h>
#include <limits.h>
#include <stddef.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include "config.h"
#include "defines.h"
#include "ohash.h"
#include "dir.h"
#include "lst.h"
#include "memory.h"
#include "buf.h"
#include "gnode.h"
#include "arch.h"
#include "targ.h"
#include "error.h"
#include "str.h"
#include "timestamp.h"


typedef struct Path_ {
	int 	  refCount;	/* Number of paths with this directory */
#ifdef DEBUG_DIRECTORY_CACHE
	int 	  hits; 	/* the number of times a file in this
				 * directory has been found */
#endif
	struct ohash   files;	/* Hash table of files in directory */
	char	  name[1];	/* Name of directory */
} Path;

/*	A search path consists of a Lst of Path structures. A Path structure
 *	has in it the name of the directory and a hash table of all the files
 *	in the directory. This is used to cut down on the number of system
 *	calls necessary to find implicit dependents and their like. Since
 *	these searches are made before any actions are taken, we need not
 *	worry about the directory changing due to creation commands. If this
 *	hampers the style of some makefiles, they must be changed.
 *
 *	A list of all previously-read directories is kept in the
 *	openDirectories cache.
 *
 *	The need for the caching of whole directories is brought about by
 *	the multi-level transformation code in suff.c, which tends to search
 *	for far more files than regular make does. In the initial
 *	implementation, the amount of time spent performing "stat" calls was
 *	truly astronomical. The problem with hashing at the start is,
 *	of course, that pmake doesn't then detect changes to these directories
 *	during the course of the make. Three possibilities suggest themselves:
 *
 *	    1) just use stat to test for a file's existence. As mentioned
 *	       above, this is very inefficient due to the number of checks
 *	       engendered by the multi-level transformation code.
 *	    2) use readdir() and company to search the directories, keeping
 *	       them open between checks. I have tried this and while it
 *	       didn't slow down the process too much, it could severely
 *	       affect the amount of parallelism available as each directory
 *	       open would take another file descriptor out of play for
 *	       handling I/O for another job. Given that it is only recently
 *	       that UNIX OS's have taken to allowing more than 20 or 32
 *	       file descriptors for a process, this doesn't seem acceptable
 *	       to me.
 *	    3) record the mtime of the directory in the Path structure and
 *	       verify the directory hasn't changed since the contents were
 *	       hashed. This will catch the creation or deletion of files,
 *	       but not the updating of files. However, since it is the
 *	       creation and deletion that is the problem, this could be
 *	       a good thing to do. Unfortunately, if the directory (say ".")
 *	       were fairly large and changed fairly frequently, the constant
 *	       rehashing could seriously degrade performance. It might be
 *	       good in such cases to keep track of the number of rehashes
 *	       and if the number goes over a (small) limit, resort to using
 *	       stat in its place.
 *
 *	An additional thing to consider is that pmake is used primarily
 *	to create C programs and until recently pcc-based compilers refused
 *	to allow you to specify where the resulting object file should be
 *	placed. This forced all objects to be created in the current
 *	directory. This isn't meant as a full excuse, just an explanation of
 *	some of the reasons for the caching used here.
 *
 *	One more note: the location of a target's file is only performed
 *	on the downward traversal of the graph and then only for terminal
 *	nodes in the graph. This could be construed as wrong in some cases,
 *	but prevents inadvertent modification of files when the "installed"
 *	directory for a file is provided in the search path.
 *
 *	Another data structure maintained by this module is an mtime
 *	cache used when the searching of cached directories fails to find
 *	a file. In the past, Dir_FindFile would simply perform an access()
 *	call in such a case to determine if the file could be found using
 *	just the name given. When this hit, however, all that was gained
 *	was the knowledge that the file existed. Given that an access() is
 *	essentially a stat() without the copyout() call, and that the same
 *	filesystem overhead would have to be incurred in Dir_MTime, it made
 *	sense to replace the access() with a stat() and record the mtime
 *	in a cache for when Dir_MTime was actually called.  */

static LIST   thedirSearchPath;		/* main search path */
Lst	      dirSearchPath= &thedirSearchPath;

#ifdef DEBUG_DIRECTORY_CACHE
/* Variables for gathering statistics on the efficiency of the hashing
 * mechanism.  */
static int    hits,			/* Found in directory cache */
	      misses,			/* Sad, but not evil misses */
	      nearmisses,		/* Found under search path */
	      bigmisses;		/* Sought by itself */
#endif

static Path	  *dot; 		/* contents of current directory */

struct file_stamp {
	TIMESTAMP mtime;		/* time stamp... */
	char name[1];			/* ...for that file.  */
};

static struct ohash   openDirectories;	/* cache all open directories */

/* Global structure used to cache mtimes.  XXX We don't cache an mtime
 * before a caller actually looks up for the given time, because of the
 * possibility a caller might update the file and invalidate the cache
 * entry, and we don't look up in this cache except as a last resort.
 */
static struct ohash mtimes;  


/* There are three distinct hash structures:
 * - to collate files's last modification times (global mtimes)
 * - to collate file names (in each Path structure)
 * - to collate known directories (global openDirectories).  */
static struct ohash_info stamp_info = { 
	offsetof(struct file_stamp, name), NULL, hash_alloc, hash_free, 
	element_alloc };

static struct ohash_info file_info = { 
	0, NULL, hash_alloc, hash_free, element_alloc };

static struct ohash_info dir_info = { 
	offsetof(Path, name), NULL, hash_alloc, hash_free, element_alloc };

/* add_file(path, name): add a file name to a path hash structure. */
static void add_file(Path *, const char *);
/* n = find_file_hashi(p, name, end, hv): retrieve name in a path hash
 * 	structure. */
static char *find_file_hashi(Path *, const char *, const char *, uint32_t);

/* stamp = find_stampi(name, end): look for (name, end) in the global
 *	cache. */
static struct file_stamp *find_stampi(const char *, const char *);
/* record_stamp(name, timestamp): record timestamp for name in the global
 * 	cache. */
static void record_stamp(const char *, TIMESTAMP);

/* free_hash(o): free a ohash structure, where each element can be free'd. */
static void free_hash(struct ohash *);

/* p = DirReaddiri(name, end): read an actual directory, caching results
 * 	as we go.  */
static Path *DirReaddiri(const char *, const char *);
/* Handles wildcard expansion on a given directory. */
static void DirMatchFilesi(const char *, const char *, Path *, Lst);
/* Handles simple wildcard expansion on a path. */
static void PathMatchFilesi(const char *, const char *, Lst, Lst);
/* Handles wildcards expansion except for curly braces. */
static void DirExpandWildi(const char *, const char *, Lst, Lst);
#define DirExpandWild(s, l1, l2) DirExpandWildi(s, strchr(s, '\0'), l1, l2)
/* Handles wildcard expansion including curly braces. */
static void DirExpandCurlyi(const char *, const char *, Lst, Lst);

/* Debugging: show each word in an expansion list. */
static void DirPrintWord(void *);
/* Debugging: show a dir name in a path. */
static void DirPrintDir(void *);

static void
record_stamp(const char *file, TIMESTAMP t)
{
	unsigned int slot;
	const char *end = NULL;
	struct file_stamp *n;

	slot = ohash_qlookupi(&mtimes, file, &end);
	n = ohash_find(&mtimes, slot);
	if (n)
		n->mtime = t;
	else {
		n = ohash_create_entry(&stamp_info, file, &end);
		n->mtime = t;
		ohash_insert(&mtimes, slot, n);
	}
}

static struct file_stamp *
find_stampi(const char *file, const char *efile)
{
	return ohash_find(&mtimes, ohash_qlookupi(&mtimes, file, &efile));
}

static void
add_file(Path *p, const char *file)
{
	unsigned int	slot;
	const char	*end = NULL;
	char		*n;
	struct ohash 	*h = &p->files;

	slot = ohash_qlookupi(h, file, &end);
	n = ohash_find(h, slot);
	if (n == NULL) {
		n = ohash_create_entry(&file_info, file, &end);
		ohash_insert(h, slot, n);
	}
}

static char *
find_file_hashi(Path *p, const char *file, const char *efile, uint32_t hv)
{
	struct ohash 	*h = &p->files;

	return ohash_find(h, ohash_lookup_interval(h, file, efile, hv));
}

static void
free_hash(struct ohash *h)
{
	void *e;
	unsigned int i;

	for (e = ohash_first(h, &i); e != NULL; e = ohash_next(h, &i))
		free(e);
	ohash_delete(h);
}


/* Side Effects: cache the current directory */
void
Dir_Init(void)
{
	char *dotname = ".";

	Static_Lst_Init(dirSearchPath);
	ohash_init(&openDirectories, 4, &dir_info);
	ohash_init(&mtimes, 4, &stamp_info);


	dot = DirReaddiri(dotname, dotname+1);

	if (!dot)
		Fatal("Can't access current directory");

	/* We always need to have dot around, so we increment its reference 
	 * count to make sure it won't be destroyed.  */
	dot->refCount++;
}

#ifdef CLEANUP
void
Dir_End(void)
{
	struct Path *p;
	unsigned int i;

	dot->refCount--;
	Dir_Destroy(dot);
	Lst_Destroy(dirSearchPath, Dir_Destroy);
	for (p = ohash_first(&openDirectories, &i); p != NULL;
	    p = ohash_next(&openDirectories, &i))
		Dir_Destroy(p);
	ohash_delete(&openDirectories);
	free_hash(&mtimes);
}
#endif


/* XXX: This code is not 100% correct ([^]] fails) */
bool
Dir_HasWildcardsi(const char *name, const char *ename)
{
	const char *cp;
	bool wild = false;
	unsigned long brace = 0, bracket = 0;

	for (cp = name; cp != ename; cp++) {
		switch (*cp) {
		case '{':
			brace++;
			wild = true;
			break;
		case '}':
			if (brace == 0)
				return false;
			brace--;
			break;
		case '[':
			bracket++;
			wild = true;
			break;
		case ']':
			if (bracket == 0)
				return false;
			bracket--;
			break;
		case '?':
		case '*':
			wild = true;
			break;
		default:
			break;
		}
	}
	return wild && bracket == 0 && brace == 0;
}

/*-
 *-----------------------------------------------------------------------
 * DirMatchFilesi --
 *	Given a pattern and a Path structure, see if any files
 *	match the pattern and add their names to the 'expansions' list if
 *	any do. This is incomplete -- it doesn't take care of patterns like
 *	src / *src / *.c properly (just *.c on any of the directories), but it
 *	will do for now.
 *-----------------------------------------------------------------------
 */
static void
DirMatchFilesi(const char *word, const char *eword, Path *p, Lst expansions)
{
	unsigned int search; 	/* Index into the directory's table */
	const char *entry; 	/* Current entry in the table */
	bool isDot;		/* Is the directory "." ? */

	isDot = p->name[0] == '.' && p->name[1] == '\0';

	for (entry = ohash_first(&p->files, &search); entry != NULL;
	     entry = ohash_next(&p->files, &search)) {
		/* See if the file matches the given pattern. We follow the UNIX
		 * convention that dot files will only be found if the pattern
		 * begins with a dot (the hashing scheme doesn't hash . or ..,
		 * so they won't match `.*'.  */
		if (*word != '.' && *entry == '.')
			continue;
		if (Str_Matchi(entry, strchr(entry, '\0'), word, eword))
			Lst_AtEnd(expansions, 
			    isDot ? estrdup(entry) : 
			    Str_concat(p->name, entry, '/'));
	}
}

/*-
 *-----------------------------------------------------------------------
 * PathMatchFilesi --
 *	Traverse directories in the path, calling DirMatchFiles for each.
 *	NOTE: This doesn't handle patterns in directories.
 *-----------------------------------------------------------------------
 */
static void
PathMatchFilesi(const char *word, const char *eword, Lst path, Lst expansions)
{
	LstNode	ln;		/* Current node */

	for (ln = Lst_First(path); ln != NULL; ln = Lst_Adv(ln))
		DirMatchFilesi(word, eword, (Path *)Lst_Datum(ln), expansions);
}

static void
DirPrintWord(void *word)
{
	printf("%s ", (char *)word);
}

/*-
 *-----------------------------------------------------------------------
 * DirExpandWildi:
 *	Expand all wild cards in a fully qualified name, except for
 *	curly braces.
 * Side-effect:
 *	Will hash any directory in which a file is found, and add it to
 *	the path, on the assumption that future lookups will find files
 *	there as well.
 *-----------------------------------------------------------------------
 */
static void
DirExpandWildi(const char *word, const char *eword, Lst path, Lst expansions)
{
	const char	*cp;
	const char	*slash; 	/* keep track of first slash before wildcard */

	slash = memchr(word, '/', eword - word);
	if (slash == NULL) {
		/* First the files in dot.  */
		DirMatchFilesi(word, eword, dot, expansions);

		/* Then the files in every other directory on the path.  */
		PathMatchFilesi(word, eword, path, expansions);
		return;
	}
	/* The thing has a directory component -- find the first wildcard
	 * in the string.  */
	slash = word;
	for (cp = word; cp != eword; cp++) {
		if (*cp == '/')
			slash = cp;
		if (*cp == '?' || *cp == '[' || *cp == '*') {

			if (slash != word) {
				char	*dirpath;

				/* If the glob isn't in the first component, 
				 * try and find all the components up to 
				 * the one with a wildcard.  */
				dirpath = Dir_FindFilei(word, slash+1, path);
				/* dirpath is null if we can't find the 
				 * leading component 
				 * XXX: Dir_FindFile won't find internal 
				 * components.  i.e. if the path contains 
				 * ../Etc/Object and we're looking for Etc, 
				 * it won't be found. */
				if (dirpath != NULL) {
					char *dp;
					LIST temp;

					dp = strchr(dirpath, '\0');
					while (dp > dirpath && dp[-1] == '/')
						dp--;

					Lst_Init(&temp);
					Dir_AddDiri(&temp, dirpath, dp);
					PathMatchFilesi(slash+1, eword, &temp, 
					    expansions);
					Lst_Destroy(&temp, NOFREE);
				}
			} else
				/* Start the search from the local directory. */
				PathMatchFilesi(word, eword, path, expansions);
			return;
		}
	}
	/* Return the file -- this should never happen.  */
	PathMatchFilesi(word, eword, path, expansions);
}

/*-
 *-----------------------------------------------------------------------
 * DirExpandCurly --
 *	Expand curly braces like the C shell, and other wildcards as per
 *	Str_Match.
 *	XXX: if curly expansion yields a result with
 *	no wildcards, the result is placed on the list WITHOUT CHECKING
 *	FOR ITS EXISTENCE.
 *-----------------------------------------------------------------------
 */
static void
DirExpandCurlyi(const char *word, const char *eword, Lst path, Lst expansions)
{
	const char *cp2;/* Pointer for checking for wildcards in
			 * expansion before calling Dir_Expand */
	LIST curled; 	/* Queue of words to expand */
	char *toexpand;	/* Current word to expand */
	bool dowild; 	/* Wildcard left after curlies ? */

	/* Determine once and for all if there is something else going on */
	dowild = false;
	for (cp2 = word; cp2 != eword; cp2++)
		if (*cp2 == '*' || *cp2 == '?' || *cp2 == '[') {
			dowild = true;
			break;
		}

	/* Prime queue with copy of initial word */
	Lst_Init(&curled);
	Lst_EnQueue(&curled, Str_dupi(word, eword));
	while ((toexpand = (char *)Lst_DeQueue(&curled)) != NULL) {
		const char *brace;
		const char *start;
				/* Start of current chunk of brace clause */
		const char *end;/* Character after the closing brace */
		int bracelevel; /* Keep track of nested braces. If we hit
				 * the right brace with bracelevel == 0,
				 * this is the end of the clause. */
		size_t endLen;  /* The length of the ending non-curlied 
				 * part of the current expansion */

		/* End case: no curly left to expand */
		brace = strchr(toexpand, '{');
		if (brace == NULL) {
			if (dowild) {
				DirExpandWild(toexpand, path, expansions);
				free(toexpand);
			} else
				Lst_AtEnd(expansions, toexpand);
			continue;
		} 

		start = brace+1;

		/* Find the end of the brace clause first, being wary of 
		 * nested brace clauses.  */
		for (end = start, bracelevel = 0;; end++) {
			if (*end == '{')
				bracelevel++;
			else if (*end == '\0') {
				Error("Unterminated {} clause \"%s\"", start);
				return;
			} else if (*end == '}' && bracelevel-- == 0)
				break;
		}
		end++;
		endLen = strlen(end);

		for (;;) {
			char *file;	/* To hold current expansion */
			const char *cp;	/* Current position in brace clause */
		    
			/* Find the end of the current expansion */
			for (bracelevel = 0, cp = start; 
			    bracelevel != 0 || (*cp != '}' && *cp != ','); 
			    cp++) {
				if (*cp == '{')
					bracelevel++;
				else if (*cp == '}')
					bracelevel--;
			}

			/* Build the current combination and enqueue it.  */
			file = emalloc((brace - toexpand) + (cp - start) + 
			    endLen + 1);
			if (brace != toexpand)
				memcpy(file, toexpand, brace-toexpand);
			if (cp != start)
				memcpy(file+(brace-toexpand), start, cp-start);
			memcpy(file+(brace-toexpand)+(cp-start), end, 
			    endLen + 1);
			Lst_EnQueue(&curled, file);
			if (*cp == '}')
				break;
			start = cp+1;
		}
		free(toexpand);
	}
}

/* Side effects:
 * 	Dir_Expandi will hash directories that were not yet visited */
void
Dir_Expandi(const char *word, const char *eword, Lst path, Lst expansions)
{
	const char	*cp;

	if (DEBUG(DIR)) {
		char *s = Str_dupi(word, eword);
		printf("expanding \"%s\"...", s);
		free(s);
	}

	cp = memchr(word, '{', eword - word);
	if (cp)
		DirExpandCurlyi(word, eword, path, expansions);
	else
		DirExpandWildi(word, eword, path, expansions);

	if (DEBUG(DIR)) {
		Lst_Every(expansions, DirPrintWord);
		fputc('\n', stdout);
	}
}


/*-
 * Side Effects:
 *	If the file is found in a directory which is not on the path
 *	already (either 'name' is absolute or it is a relative path
 *	[ dir1/.../dirn/file ] which exists below one of the directories
 *	already on the search path), its directory is added to the end
 *	of the path on the assumption that there will be more files in
 *	that directory later on. 
 */
char *
Dir_FindFileComplexi(const char *name, const char *ename, Lst path, 
    bool checkCurdirFirst)
{
	Path *p;	/* current path member */
	char *p1;	/* pointer into p->name */
	const char *p2;	/* pointer into name */
	LstNode ln;	/* a list element */
	char *file;	/* the current filename to check */
	char *temp;	/* index into file */
	const char *cp;	/* index of first slash, if any */
	bool hasSlash;
	struct stat stb;/* Buffer for stat, if necessary */
	struct file_stamp *entry; 
			/* Entry for mtimes table */
	uint32_t hv;	/* hash value for last component in file name */
	char *q;	/* Str_dupi(name, ename) */

	/* Find the final component of the name and note whether name has a
	 * slash in it */
	cp = Str_rchri(name, ename, '/');
	if (cp) {
		hasSlash = true;
		cp++;
	} else {
		hasSlash = false;
		cp = name;
	}

	hv = ohash_interval(cp, &ename);

	if (DEBUG(DIR))
		printf("Searching for %s...", name);
	/* Unless checkCurDirFirst is false, we always look for 
	 * the file in the current directory before anywhere else 
	 * and we always return exactly what the caller specified. */
	if (checkCurdirFirst && 
	    (!hasSlash || (cp - name == 2 && *name == '.')) &&
	    find_file_hashi(dot, cp, ename, hv) != NULL) {
		if (DEBUG(DIR))
			printf("in '.'\n");
#ifdef DEBUG_DIRECTORY_CACHE
		hits++;
		dot->hits++;
#endif
		return Str_dupi(name, ename);
	}

	/* Then, we look through all the directories on path, seeking one 
	 * containing the final component of name and whose final
	 * component(s) match name's initial component(s). 
	 * If found, we concatenate the directory name and the 
	 * final component and return the resulting string.  */
	for (ln = Lst_First(path); ln != NULL; ln = Lst_Adv(ln)) {
		p = (Path *)Lst_Datum(ln);
		if (DEBUG(DIR))
			printf("%s...", p->name);
		if (find_file_hashi(p, cp, ename, hv) != NULL) {
			if (DEBUG(DIR))
				printf("here...");
			if (hasSlash) {
				/* If the name had a slash, its initial 
				 * components and p's final components must 
				 * match. This is false if a mismatch is 
				 * encountered before all of the initial 
				 * components have been checked (p2 > name at 
				 * the end of the loop), or we matched only 
				 * part of one of the components of p along 
				 * with all the rest of them (*p1 != '/').  */
				p1 = p->name + strlen(p->name) - 1;
				p2 = cp - 2;
				while (p2 >= name && p1 >= p->name && 
				    *p1 == *p2) {
					p1--;
					p2--;
				}
				if (p2 >= name || 
				    (p1 >= p->name && *p1 != '/')) {
					if (DEBUG(DIR))
						printf("component mismatch -- continuing...");
					continue;
				}
			}
			file = Str_concati(p->name, strchr(p->name, '\0'), cp, 
			    ename, '/');
			if (DEBUG(DIR))
				printf("returning %s\n", file);
#ifdef DEBUG_DIRECTORY_CACHE
			p->hits++;
			hits++;
#endif
			return file;
		} else if (hasSlash) {
			/* If the file has a leading path component and that 
			 * component exactly matches the entire name of the 
			 * current search directory, we assume the file 
			 * doesn't exist and return NULL.  */
			for (p1 = p->name, p2 = name; *p1 && *p1 == *p2; 
			    p1++, p2++)
				continue;
			if (*p1 == '\0' && p2 == cp - 1) {
				if (DEBUG(DIR))
					printf("has to be here but isn't -- returning NULL\n");
				return NULL;
			}
		}
	}

	/* We didn't find the file on any existing member of the path.
	 * If the name doesn't contain a slash, end of story.
	 * If it does contain a slash, however, it could be in a subdirectory 
	 * of one of the members of the search path. (eg., for path=/usr/include 
	 * and name=sys/types.h, the above search fails to turn up types.h 
	 * in /usr/include, even though /usr/include/sys/types.h exists).
	 *
	 * We only perform this look-up for non-absolute file names.
	 *
	 * Whenever we score a hit, we assume there will be more matches from
	 * that directory, and append all but the last component of the 
	 * resulting name onto the search path. */
	if (!hasSlash) {
		if (DEBUG(DIR))
			printf("failed.\n");
#ifdef DEBUG_DIRECTORY_CACHE
		misses++;
#endif
		return NULL;
	}

	if (*name != '/') {
		bool checkedDot = false;

		if (DEBUG(DIR))
			printf("failed. Trying subdirectories...");
		for (ln = Lst_First(path); ln != NULL; ln = Lst_Adv(ln)) {
			p = (Path *)Lst_Datum(ln);
			if (p != dot)
				file = Str_concati(p->name, 
				    strchr(p->name, '\0'), name, ename, '/');
			else {
				/* Checking in dot -- DON'T put a leading 
				* ./ on the thing.  */
				file = Str_dupi(name, ename);
				checkedDot = true;
			}
			if (DEBUG(DIR))
				printf("checking %s...", file);

			if (stat(file, &stb) == 0) {
				TIMESTAMP mtime;

				ts_set_from_stat(stb, mtime);
				if (DEBUG(DIR))
					printf("got it.\n");

				/* We've found another directory to search. 
				 * We know there is a slash in 'file'. We 
				 * call Dir_AddDiri to add the new directory 
				 * onto the existing search path. Once that's 
				 * done, we return the file name, knowing that 
				 * should a file in this directory ever be 
				 * referenced again in such a manner, we will 
				 * find it without having to do numerous 
				 * access calls.  */
				temp = strrchr(file, '/');
				Dir_AddDiri(path, file, temp);

				/* Save the modification time so if it's 
				* needed, we don't have to fetch it again.  */
				if (DEBUG(DIR))
					printf("Caching %s for %s\n", 
					    Targ_FmtTime(mtime), file);
				record_stamp(file, mtime);
#ifdef DEBUG_DIRECTORY_CACHE
				nearmisses++;
#endif
				return file;
			} else
				free(file);
		}

		if (DEBUG(DIR))
			printf("failed. ");

		if (checkedDot) {
			/* Already checked by the given name, since . was in 
			 * the path, so no point in proceeding...  */
			if (DEBUG(DIR))
				printf("Checked . already, returning NULL\n");
			return NULL;
		}
	}

	/* Didn't find it that way, either. Last resort: look for the file
	 * in the global mtime cache, then on the disk.
	 * If this doesn't succeed, we finally return a NULL pointer.
	 *
	 * We cannot add this directory onto the search path because
	 * of this amusing case:
	 * $(INSTALLDIR)/$(FILE): $(FILE)
	 *
	 * $(FILE) exists in $(INSTALLDIR) but not in the current one.
	 * When searching for $(FILE), we will find it in $(INSTALLDIR)
	 * b/c we added it here. This is not good...  */
	q = Str_dupi(name, ename);
	if (DEBUG(DIR))
		printf("Looking for \"%s\"...", q);

#ifdef DEBUG_DIRECTORY_CACHE
	bigmisses++;
#endif
	entry = find_stampi(name, ename);
	if (entry != NULL) {
		if (DEBUG(DIR))
			printf("got it (in mtime cache)\n");
		return q;
	} else if (stat(q, &stb) == 0) {
		TIMESTAMP mtime;

		ts_set_from_stat(stb, mtime);
		if (DEBUG(DIR))
			printf("Caching %s for %s\n", Targ_FmtTime(mtime), q);
		record_stamp(q, mtime);
		return q;
	} else {
	    if (DEBUG(DIR))
		    printf("failed. Returning NULL\n");
	    free(q);
	    return NULL;
	}
}

/* Read a directory, either from the disk, or from the cache.  */
static Path *
DirReaddiri(const char *name, const char *ename)
{
	Path *p;
	DIR *d;
	struct dirent *dp;
	unsigned int slot;

	slot = ohash_qlookupi(&openDirectories, name, &ename);
	p = ohash_find(&openDirectories, slot);

	if (p != NULL)
		return p;

	p = ohash_create_entry(&dir_info, name, &ename);
#ifdef DEBUG_DIRECTORY_CACHE
	p->hits = 0;
#endif
	p->refCount = 0;
	ohash_init(&p->files, 4, &file_info);

	if (DEBUG(DIR)) {
		printf("Caching %s...", p->name);
		fflush(stdout);
	}

	if ((d = opendir(p->name)) == NULL)
		return NULL;

	while ((dp = readdir(d)) != NULL) {
		if (dp->d_name[0] == '.' && 
		    (dp->d_name[1] == '\0' || 
			(dp->d_name[1] == '.' && dp->d_name[2] == '\0')))
			continue;
		add_file(p, dp->d_name);
	}
	(void)closedir(d);
	if (DEBUG(DIR))
		printf("done\n");

	ohash_insert(&openDirectories, slot, p);
	return p;
}

/*-
 *-----------------------------------------------------------------------
 * Dir_AddDiri --
 *	Add the given name to the end of the given path. The order of
 *	the arguments is backwards so ParseDoDependency can do a
 *	Lst_ForEach of its list of paths...
 *
 * Side Effects:
 *	A structure is added to the list and the directory is
 *	read and hashed.
 *-----------------------------------------------------------------------
 */

void
Dir_AddDiri(Lst path, const char *name, const char *ename)
{
	Path	*p;

	p = DirReaddiri(name, ename);
	if (p == NULL)
		return;
	if (p->refCount == 0)
		Lst_AtEnd(path, p);
	else if (!Lst_AddNew(path, p))
		return;
	p->refCount++;
}

/*-
 *-----------------------------------------------------------------------
 * Dir_CopyDir --
 *	Callback function for duplicating a search path via Lst_Duplicate.
 *	Ups the reference count for the directory.
 *
 * Results:
 *	Returns the Path it was given.
 *
 * Side Effects:
 *	The refCount of the path is incremented.
 *-----------------------------------------------------------------------
 */
void *
Dir_CopyDir(void *p)
{
	((Path *)p)->refCount++;
	return p;
}

/*-
 *-----------------------------------------------------------------------
 * Dir_MakeFlags --
 *	Make a string by taking all the directories in the given search
 *	path and preceding them by the given flag. Used by the suffix
 *	module to create variables for compilers based on suffix search
 *	paths.
 *
 * Results:
 *	The string mentioned above. Note that there is no space between
 *	the given flag and each directory. The empty string is returned if
 *	Things don't go well.
 *-----------------------------------------------------------------------
 */
char *
Dir_MakeFlags(const char *flag, Lst path)
{
	LstNode	  ln;
	BUFFER	  buf;

	Buf_Init(&buf, 0);

	for (ln = Lst_First(path); ln != NULL; ln = Lst_Adv(ln)) {
		Buf_AddString(&buf, flag);
		Buf_AddString(&buf, ((Path *)Lst_Datum(ln))->name);
		Buf_AddSpace(&buf);
	}

	return Buf_Retrieve(&buf);
}

/*-
 *-----------------------------------------------------------------------
 * Dir_Destroy --
 *	Nuke a directory descriptor, if possible. Callback procedure
 *	for the suffixes module when destroying a search path.
 *
 * Side Effects:
 *	If no other path references this directory (refCount == 0),
 *	the Path and all its data are freed.
 *-----------------------------------------------------------------------
 */
void
Dir_Destroy(void *pp)
{
	Path *p = (Path *)pp;

	if (--p->refCount == 0) {
		ohash_remove(&openDirectories, 
		    ohash_qlookup(&openDirectories, p->name));
		free_hash(&p->files);
		free(p);
	}
}

/*-
 *-----------------------------------------------------------------------
 * Dir_Concat --
 *	Concatenate two paths, adding the second to the end of the first.
 *	Makes sure to avoid duplicates.
 *
 * Side Effects:
 *	Reference counts for added dirs are upped.
 *-----------------------------------------------------------------------
 */
void
Dir_Concat(Lst path1, Lst path2)
{
	LstNode	ln;
	Path	*p;

	for (ln = Lst_First(path2); ln != NULL; ln = Lst_Adv(ln)) {
		p = (Path *)Lst_Datum(ln);
		if (Lst_AddNew(path1, p))
			p->refCount++;
	}
}

#ifdef DEBUG_DIRECTORY_CACHE
void
Dir_PrintDirectories(void)
{
	Path		*p;
	unsigned int	i;

	printf("#*** Directory Cache:\n");
	printf("# Stats: %d hits %d misses %d near misses %d losers (%d%%)\n",
	      hits, misses, nearmisses, bigmisses,
	      (hits+bigmisses+nearmisses ?
	       hits * 100 / (hits + bigmisses + nearmisses) : 0));
	printf("# %-20s referenced\thits\n", "directory");
	for (p = ohash_first(&openDirectories, &i); p != NULL;
	    p = ohash_next(&openDirectories, &i))
		printf("# %-20s %10d\t%4d\n", p->name, p->refCount, p->hits);
}
#endif

static void
DirPrintDir(void *p)
{
	printf("%s ", ((Path *)p)->name);
}

void
Dir_PrintPath(Lst path)
{
	Lst_Every(path, DirPrintDir);
}

TIMESTAMP
Dir_MTime(GNode *gn)
{
	char *fullName;
	struct stat stb;
	struct file_stamp *entry;
	unsigned int slot;
	TIMESTAMP	  mtime;

	if (gn->type & OP_ARCHV)
		return Arch_MTime(gn);

	if (gn->path == NULL) {
		fullName = Dir_FindFile(gn->name, dirSearchPath);
		if (fullName == NULL)
			fullName = estrdup(gn->name);
	} else
		fullName = gn->path;

	slot = ohash_qlookup(&mtimes, fullName);
	entry = ohash_find(&mtimes, slot);
	if (entry != NULL) {
		/* Only do this once -- the second time folks are checking to
		 * see if the file was actually updated, so we need to 
		 * actually go to the file system.	*/
		if (DEBUG(DIR))
			printf("Using cached time %s for %s\n",
			    Targ_FmtTime(entry->mtime), fullName);
		mtime = entry->mtime;
		free(entry);
		ohash_remove(&mtimes, slot);
	} else if (stat(fullName, &stb) == 0)
		ts_set_from_stat(stb, mtime);
	else {
		if (gn->type & OP_MEMBER) {
			if (fullName != gn->path)
				free(fullName);
			return Arch_MemMTime(gn);
		} else
			ts_set_out_of_date(mtime);
	}
	if (fullName && gn->path == NULL)
		gn->path = fullName;

	gn->mtime = mtime;
	return gn->mtime;
}