xref: /freebsd/contrib/bmake/dir.c (revision a35f04fba2ebb8f86d4cbdc710c89a094572b08e)
1 /*	$NetBSD: dir.c,v 1.69 2017/01/31 06:54:23 sjg Exp $	*/
2 
3 /*
4  * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
5  * All rights reserved.
6  *
7  * This code is derived from software contributed to Berkeley by
8  * Adam de Boor.
9  *
10  * Redistribution and use in source and binary forms, with or without
11  * modification, are permitted provided that the following conditions
12  * are met:
13  * 1. Redistributions of source code must retain the above copyright
14  *    notice, this list of conditions and the following disclaimer.
15  * 2. Redistributions in binary form must reproduce the above copyright
16  *    notice, this list of conditions and the following disclaimer in the
17  *    documentation and/or other materials provided with the distribution.
18  * 3. Neither the name of the University nor the names of its contributors
19  *    may be used to endorse or promote products derived from this software
20  *    without specific prior written permission.
21  *
22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32  * SUCH DAMAGE.
33  */
34 
35 /*
36  * Copyright (c) 1988, 1989 by Adam de Boor
37  * Copyright (c) 1989 by Berkeley Softworks
38  * All rights reserved.
39  *
40  * This code is derived from software contributed to Berkeley by
41  * Adam de Boor.
42  *
43  * Redistribution and use in source and binary forms, with or without
44  * modification, are permitted provided that the following conditions
45  * are met:
46  * 1. Redistributions of source code must retain the above copyright
47  *    notice, this list of conditions and the following disclaimer.
48  * 2. Redistributions in binary form must reproduce the above copyright
49  *    notice, this list of conditions and the following disclaimer in the
50  *    documentation and/or other materials provided with the distribution.
51  * 3. All advertising materials mentioning features or use of this software
52  *    must display the following acknowledgement:
53  *	This product includes software developed by the University of
54  *	California, Berkeley and its contributors.
55  * 4. Neither the name of the University nor the names of its contributors
56  *    may be used to endorse or promote products derived from this software
57  *    without specific prior written permission.
58  *
59  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
60  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
61  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
62  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
63  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
64  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
65  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
66  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
67  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
68  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
69  * SUCH DAMAGE.
70  */
71 
72 #ifndef MAKE_NATIVE
73 static char rcsid[] = "$NetBSD: dir.c,v 1.69 2017/01/31 06:54:23 sjg Exp $";
74 #else
75 #include <sys/cdefs.h>
76 #ifndef lint
77 #if 0
78 static char sccsid[] = "@(#)dir.c	8.2 (Berkeley) 1/2/94";
79 #else
80 __RCSID("$NetBSD: dir.c,v 1.69 2017/01/31 06:54:23 sjg Exp $");
81 #endif
82 #endif /* not lint */
83 #endif
84 
85 /*-
86  * dir.c --
87  *	Directory searching using wildcards and/or normal names...
88  *	Used both for source wildcarding in the Makefile and for finding
89  *	implicit sources.
90  *
91  * The interface for this module is:
92  *	Dir_Init  	    Initialize the module.
93  *
94  *	Dir_InitCur	    Set the cur Path.
95  *
96  *	Dir_InitDot	    Set the dot Path.
97  *
98  *	Dir_End  	    Cleanup the module.
99  *
100  *	Dir_SetPATH	    Set ${.PATH} to reflect state of dirSearchPath.
101  *
102  *	Dir_HasWildcards    Returns TRUE if the name given it needs to
103  *	    	  	    be wildcard-expanded.
104  *
105  *	Dir_Expand	    Given a pattern and a path, return a Lst of names
106  *	    	  	    which match the pattern on the search path.
107  *
108  *	Dir_FindFile	    Searches for a file on a given search path.
109  *	    	  	    If it exists, the entire path is returned.
110  *	    	  	    Otherwise NULL is returned.
111  *
112  *	Dir_FindHereOrAbove Search for a path in the current directory and
113  *			    then all the directories above it in turn until
114  *			    the path is found or we reach the root ("/").
115  *
116  *	Dir_MTime 	    Return the modification time of a node. The file
117  *	    	  	    is searched for along the default search path.
118  *	    	  	    The path and mtime fields of the node are filled
119  *	    	  	    in.
120  *
121  *	Dir_AddDir	    Add a directory to a search path.
122  *
123  *	Dir_MakeFlags	    Given a search path and a command flag, create
124  *	    	  	    a string with each of the directories in the path
125  *	    	  	    preceded by the command flag and all of them
126  *	    	  	    separated by a space.
127  *
128  *	Dir_Destroy	    Destroy an element of a search path. Frees up all
129  *	    	  	    things that can be freed for the element as long
130  *	    	  	    as the element is no longer referenced by any other
131  *	    	  	    search path.
132  *	Dir_ClearPath	    Resets a search path to the empty list.
133  *
134  * For debugging:
135  *	Dir_PrintDirectories	Print stats about the directory cache.
136  */
137 
138 #include <sys/types.h>
139 #include <sys/stat.h>
140 
141 #include <dirent.h>
142 #include <errno.h>
143 #include <stdio.h>
144 
145 #include "make.h"
146 #include "hash.h"
147 #include "dir.h"
148 #include "job.h"
149 
150 /*
151  *	A search path consists of a Lst of Path structures. A Path structure
152  *	has in it the name of the directory and a hash table of all the files
153  *	in the directory. This is used to cut down on the number of system
154  *	calls necessary to find implicit dependents and their like. Since
155  *	these searches are made before any actions are taken, we need not
156  *	worry about the directory changing due to creation commands. If this
157  *	hampers the style of some makefiles, they must be changed.
158  *
159  *	A list of all previously-read directories is kept in the
160  *	openDirectories Lst. This list is checked first before a directory
161  *	is opened.
162  *
163  *	The need for the caching of whole directories is brought about by
164  *	the multi-level transformation code in suff.c, which tends to search
165  *	for far more files than regular make does. In the initial
166  *	implementation, the amount of time spent performing "stat" calls was
167  *	truly astronomical. The problem with hashing at the start is,
168  *	of course, that pmake doesn't then detect changes to these directories
169  *	during the course of the make. Three possibilities suggest themselves:
170  *
171  *	    1) just use stat to test for a file's existence. As mentioned
172  *	       above, this is very inefficient due to the number of checks
173  *	       engendered by the multi-level transformation code.
174  *	    2) use readdir() and company to search the directories, keeping
175  *	       them open between checks. I have tried this and while it
176  *	       didn't slow down the process too much, it could severely
177  *	       affect the amount of parallelism available as each directory
178  *	       open would take another file descriptor out of play for
179  *	       handling I/O for another job. Given that it is only recently
180  *	       that UNIX OS's have taken to allowing more than 20 or 32
181  *	       file descriptors for a process, this doesn't seem acceptable
182  *	       to me.
183  *	    3) record the mtime of the directory in the Path structure and
184  *	       verify the directory hasn't changed since the contents were
185  *	       hashed. This will catch the creation or deletion of files,
186  *	       but not the updating of files. However, since it is the
187  *	       creation and deletion that is the problem, this could be
188  *	       a good thing to do. Unfortunately, if the directory (say ".")
189  *	       were fairly large and changed fairly frequently, the constant
190  *	       rehashing could seriously degrade performance. It might be
191  *	       good in such cases to keep track of the number of rehashes
192  *	       and if the number goes over a (small) limit, resort to using
193  *	       stat in its place.
194  *
195  *	An additional thing to consider is that pmake is used primarily
196  *	to create C programs and until recently pcc-based compilers refused
197  *	to allow you to specify where the resulting object file should be
198  *	placed. This forced all objects to be created in the current
199  *	directory. This isn't meant as a full excuse, just an explanation of
200  *	some of the reasons for the caching used here.
201  *
202  *	One more note: the location of a target's file is only performed
203  *	on the downward traversal of the graph and then only for terminal
204  *	nodes in the graph. This could be construed as wrong in some cases,
205  *	but prevents inadvertent modification of files when the "installed"
206  *	directory for a file is provided in the search path.
207  *
208  *	Another data structure maintained by this module is an mtime
209  *	cache used when the searching of cached directories fails to find
210  *	a file. In the past, Dir_FindFile would simply perform an access()
211  *	call in such a case to determine if the file could be found using
212  *	just the name given. When this hit, however, all that was gained
213  *	was the knowledge that the file existed. Given that an access() is
214  *	essentially a stat() without the copyout() call, and that the same
215  *	filesystem overhead would have to be incurred in Dir_MTime, it made
216  *	sense to replace the access() with a stat() and record the mtime
217  *	in a cache for when Dir_MTime was actually called.
218  */
219 
220 Lst          dirSearchPath;	/* main search path */
221 
222 static Lst   openDirectories;	/* the list of all open directories */
223 
224 /*
225  * Variables for gathering statistics on the efficiency of the hashing
226  * mechanism.
227  */
228 static int    hits,	      /* Found in directory cache */
229 	      misses,	      /* Sad, but not evil misses */
230 	      nearmisses,     /* Found under search path */
231 	      bigmisses;      /* Sought by itself */
232 
233 static Path    	  *dot;	    /* contents of current directory */
234 static Path    	  *cur;	    /* contents of current directory, if not dot */
235 static Path	  *dotLast; /* a fake path entry indicating we need to
236 			     * look for . last */
237 static Hash_Table mtimes;   /* Results of doing a last-resort stat in
238 			     * Dir_FindFile -- if we have to go to the
239 			     * system to find the file, we might as well
240 			     * have its mtime on record. XXX: If this is done
241 			     * way early, there's a chance other rules will
242 			     * have already updated the file, in which case
243 			     * we'll update it again. Generally, there won't
244 			     * be two rules to update a single file, so this
245 			     * should be ok, but... */
246 
247 static Hash_Table lmtimes;  /* same as mtimes but for lstat */
248 
249 static int DirFindName(const void *, const void *);
250 static int DirMatchFiles(const char *, Path *, Lst);
251 static void DirExpandCurly(const char *, const char *, Lst, Lst);
252 static void DirExpandInt(const char *, Lst, Lst);
253 static int DirPrintWord(void *, void *);
254 static int DirPrintDir(void *, void *);
255 static char *DirLookup(Path *, const char *, const char *, Boolean);
256 static char *DirLookupSubdir(Path *, const char *);
257 static char *DirFindDot(Boolean, const char *, const char *);
258 static char *DirLookupAbs(Path *, const char *, const char *);
259 
260 
261 /*
262  * We use stat(2) a lot, cache the results
263  * mtime and mode are all we care about.
264  */
265 struct cache_st {
266     time_t mtime;
267     mode_t  mode;
268 };
269 
270 /* minimize changes below */
271 static time_t
272 Hash_GetTimeValue(Hash_Entry *entry)
273 {
274     struct cache_st *cst;
275 
276     cst = entry->clientPtr;
277     return cst->mtime;
278 }
279 
280 #define CST_LSTAT 1
281 #define CST_UPDATE 2
282 
283 static int
284 cached_stats(Hash_Table *htp, const char *pathname, struct stat *st, int flags)
285 {
286     Hash_Entry *entry;
287     struct cache_st *cst;
288     int rc;
289 
290     if (!pathname || !pathname[0])
291 	return -1;
292 
293     entry = Hash_FindEntry(htp, pathname);
294 
295     if (entry && (flags & CST_UPDATE) == 0) {
296 	cst = entry->clientPtr;
297 
298 	memset(st, 0, sizeof(*st));
299 	st->st_mtime = cst->mtime;
300 	st->st_mode = cst->mode;
301 	return 0;
302     }
303 
304     rc = (flags & CST_LSTAT) ? lstat(pathname, st) : stat(pathname, st);
305     if (rc == -1)
306 	return -1;
307 
308     if (st->st_mtime == 0)
309 	st->st_mtime = 1;      /* avoid confusion with missing file */
310 
311     if (!entry)
312 	entry = Hash_CreateEntry(htp, pathname, NULL);
313     if (!entry->clientPtr)
314 	entry->clientPtr = bmake_malloc(sizeof(*cst));
315     cst = entry->clientPtr;
316     cst->mtime = st->st_mtime;
317     cst->mode = st->st_mode;
318 
319     return 0;
320 }
321 
322 int
323 cached_stat(const char *pathname, void *st)
324 {
325     return cached_stats(&mtimes, pathname, st, 0);
326 }
327 
328 int
329 cached_lstat(const char *pathname, void *st)
330 {
331     return cached_stats(&lmtimes, pathname, st, CST_LSTAT);
332 }
333 
334 /*-
335  *-----------------------------------------------------------------------
336  * Dir_Init --
337  *	initialize things for this module
338  *
339  * Results:
340  *	none
341  *
342  * Side Effects:
343  *	some directories may be opened.
344  *-----------------------------------------------------------------------
345  */
346 void
347 Dir_Init(const char *cdname)
348 {
349     if (!cdname) {
350 	dirSearchPath = Lst_Init(FALSE);
351 	openDirectories = Lst_Init(FALSE);
352 	Hash_InitTable(&mtimes, 0);
353 	Hash_InitTable(&lmtimes, 0);
354 	return;
355     }
356     Dir_InitCur(cdname);
357 
358     dotLast = bmake_malloc(sizeof(Path));
359     dotLast->refCount = 1;
360     dotLast->hits = 0;
361     dotLast->name = bmake_strdup(".DOTLAST");
362     Hash_InitTable(&dotLast->files, -1);
363 }
364 
365 /*
366  * Called by Dir_Init() and whenever .CURDIR is assigned to.
367  */
368 void
369 Dir_InitCur(const char *cdname)
370 {
371     Path *p;
372 
373     if (cdname != NULL) {
374 	/*
375 	 * Our build directory is not the same as our source directory.
376 	 * Keep this one around too.
377 	 */
378 	if ((p = Dir_AddDir(NULL, cdname))) {
379 	    p->refCount += 1;
380 	    if (cur && cur != p) {
381 		/*
382 		 * We've been here before, cleanup.
383 		 */
384 		cur->refCount -= 1;
385 		Dir_Destroy(cur);
386 	    }
387 	    cur = p;
388 	}
389     }
390 }
391 
392 /*-
393  *-----------------------------------------------------------------------
394  * Dir_InitDot --
395  *	(re)initialize "dot" (current/object directory) path hash
396  *
397  * Results:
398  *	none
399  *
400  * Side Effects:
401  *	some directories may be opened.
402  *-----------------------------------------------------------------------
403  */
404 void
405 Dir_InitDot(void)
406 {
407     if (dot != NULL) {
408 	LstNode ln;
409 
410 	/* Remove old entry from openDirectories, but do not destroy. */
411 	ln = Lst_Member(openDirectories, dot);
412 	(void)Lst_Remove(openDirectories, ln);
413     }
414 
415     dot = Dir_AddDir(NULL, ".");
416 
417     if (dot == NULL) {
418 	Error("Cannot open `.' (%s)", strerror(errno));
419 	exit(1);
420     }
421 
422     /*
423      * We always need to have dot around, so we increment its reference count
424      * to make sure it's not destroyed.
425      */
426     dot->refCount += 1;
427     Dir_SetPATH();			/* initialize */
428 }
429 
430 /*-
431  *-----------------------------------------------------------------------
432  * Dir_End --
433  *	cleanup things for this module
434  *
435  * Results:
436  *	none
437  *
438  * Side Effects:
439  *	none
440  *-----------------------------------------------------------------------
441  */
442 void
443 Dir_End(void)
444 {
445 #ifdef CLEANUP
446     if (cur) {
447 	cur->refCount -= 1;
448 	Dir_Destroy(cur);
449     }
450     dot->refCount -= 1;
451     dotLast->refCount -= 1;
452     Dir_Destroy(dotLast);
453     Dir_Destroy(dot);
454     Dir_ClearPath(dirSearchPath);
455     Lst_Destroy(dirSearchPath, NULL);
456     Dir_ClearPath(openDirectories);
457     Lst_Destroy(openDirectories, NULL);
458     Hash_DeleteTable(&mtimes);
459 #endif
460 }
461 
462 /*
463  * We want ${.PATH} to indicate the order in which we will actually
464  * search, so we rebuild it after any .PATH: target.
465  * This is the simplest way to deal with the effect of .DOTLAST.
466  */
467 void
468 Dir_SetPATH(void)
469 {
470     LstNode       ln;		/* a list element */
471     Path *p;
472     Boolean	  hasLastDot = FALSE;	/* true we should search dot last */
473 
474     Var_Delete(".PATH", VAR_GLOBAL);
475 
476     if (Lst_Open(dirSearchPath) == SUCCESS) {
477 	if ((ln = Lst_First(dirSearchPath)) != NULL) {
478 	    p = (Path *)Lst_Datum(ln);
479 	    if (p == dotLast) {
480 		hasLastDot = TRUE;
481 		Var_Append(".PATH", dotLast->name, VAR_GLOBAL);
482 	    }
483 	}
484 
485 	if (!hasLastDot) {
486 	    if (dot)
487 		Var_Append(".PATH", dot->name, VAR_GLOBAL);
488 	    if (cur)
489 		Var_Append(".PATH", cur->name, VAR_GLOBAL);
490 	}
491 
492 	while ((ln = Lst_Next(dirSearchPath)) != NULL) {
493 	    p = (Path *)Lst_Datum(ln);
494 	    if (p == dotLast)
495 		continue;
496 	    if (p == dot && hasLastDot)
497 		continue;
498 	    Var_Append(".PATH", p->name, VAR_GLOBAL);
499 	}
500 
501 	if (hasLastDot) {
502 	    if (dot)
503 		Var_Append(".PATH", dot->name, VAR_GLOBAL);
504 	    if (cur)
505 		Var_Append(".PATH", cur->name, VAR_GLOBAL);
506 	}
507 	Lst_Close(dirSearchPath);
508     }
509 }
510 
511 /*-
512  *-----------------------------------------------------------------------
513  * DirFindName --
514  *	See if the Path structure describes the same directory as the
515  *	given one by comparing their names. Called from Dir_AddDir via
516  *	Lst_Find when searching the list of open directories.
517  *
518  * Input:
519  *	p		Current name
520  *	dname		Desired name
521  *
522  * Results:
523  *	0 if it is the same. Non-zero otherwise
524  *
525  * Side Effects:
526  *	None
527  *-----------------------------------------------------------------------
528  */
529 static int
530 DirFindName(const void *p, const void *dname)
531 {
532     return (strcmp(((const Path *)p)->name, dname));
533 }
534 
535 /*-
536  *-----------------------------------------------------------------------
537  * Dir_HasWildcards  --
538  *	see if the given name has any wildcard characters in it
539  *	be careful not to expand unmatching brackets or braces.
540  *	XXX: This code is not 100% correct. ([^]] fails etc.)
541  *	I really don't think that make(1) should be expanding
542  *	patterns, because then you have to set a mechanism for
543  *	escaping the expansion!
544  *
545  * Input:
546  *	name		name to check
547  *
548  * Results:
549  *	returns TRUE if the word should be expanded, FALSE otherwise
550  *
551  * Side Effects:
552  *	none
553  *-----------------------------------------------------------------------
554  */
555 Boolean
556 Dir_HasWildcards(char *name)
557 {
558     char *cp;
559     int wild = 0, brace = 0, bracket = 0;
560 
561     for (cp = name; *cp; cp++) {
562 	switch(*cp) {
563 	case '{':
564 		brace++;
565 		wild = 1;
566 		break;
567 	case '}':
568 		brace--;
569 		break;
570 	case '[':
571 		bracket++;
572 		wild = 1;
573 		break;
574 	case ']':
575 		bracket--;
576 		break;
577 	case '?':
578 	case '*':
579 		wild = 1;
580 		break;
581 	default:
582 		break;
583 	}
584     }
585     return wild && bracket == 0 && brace == 0;
586 }
587 
588 /*-
589  *-----------------------------------------------------------------------
590  * DirMatchFiles --
591  * 	Given a pattern and a Path structure, see if any files
592  *	match the pattern and add their names to the 'expansions' list if
593  *	any do. This is incomplete -- it doesn't take care of patterns like
594  *	src / *src / *.c properly (just *.c on any of the directories), but it
595  *	will do for now.
596  *
597  * Input:
598  *	pattern		Pattern to look for
599  *	p		Directory to search
600  *	expansion	Place to store the results
601  *
602  * Results:
603  *	Always returns 0
604  *
605  * Side Effects:
606  *	File names are added to the expansions lst. The directory will be
607  *	fully hashed when this is done.
608  *-----------------------------------------------------------------------
609  */
610 static int
611 DirMatchFiles(const char *pattern, Path *p, Lst expansions)
612 {
613     Hash_Search	  search;   	/* Index into the directory's table */
614     Hash_Entry	  *entry;   	/* Current entry in the table */
615     Boolean 	  isDot;    	/* TRUE if the directory being searched is . */
616 
617     isDot = (*p->name == '.' && p->name[1] == '\0');
618 
619     for (entry = Hash_EnumFirst(&p->files, &search);
620 	 entry != NULL;
621 	 entry = Hash_EnumNext(&search))
622     {
623 	/*
624 	 * See if the file matches the given pattern. Note we follow the UNIX
625 	 * convention that dot files will only be found if the pattern
626 	 * begins with a dot (note also that as a side effect of the hashing
627 	 * scheme, .* won't match . or .. since they aren't hashed).
628 	 */
629 	if (Str_Match(entry->name, pattern) &&
630 	    ((entry->name[0] != '.') ||
631 	     (pattern[0] == '.')))
632 	{
633 	    (void)Lst_AtEnd(expansions,
634 			    (isDot ? bmake_strdup(entry->name) :
635 			     str_concat(p->name, entry->name,
636 					STR_ADDSLASH)));
637 	}
638     }
639     return (0);
640 }
641 
642 /*-
643  *-----------------------------------------------------------------------
644  * DirExpandCurly --
645  *	Expand curly braces like the C shell. Does this recursively.
646  *	Note the special case: if after the piece of the curly brace is
647  *	done there are no wildcard characters in the result, the result is
648  *	placed on the list WITHOUT CHECKING FOR ITS EXISTENCE.
649  *
650  * Input:
651  *	word		Entire word to expand
652  *	brace		First curly brace in it
653  *	path		Search path to use
654  *	expansions	Place to store the expansions
655  *
656  * Results:
657  *	None.
658  *
659  * Side Effects:
660  *	The given list is filled with the expansions...
661  *
662  *-----------------------------------------------------------------------
663  */
664 static void
665 DirExpandCurly(const char *word, const char *brace, Lst path, Lst expansions)
666 {
667     const char   *end;	    	/* Character after the closing brace */
668     const char   *cp;	    	/* Current position in brace clause */
669     const char   *start;   	/* Start of current piece of brace clause */
670     int	    	  bracelevel;	/* Number of braces we've seen. If we see a
671 				 * right brace when this is 0, we've hit the
672 				 * end of the clause. */
673     char    	 *file;    	/* Current expansion */
674     int	    	  otherLen; 	/* The length of the other pieces of the
675 				 * expansion (chars before and after the
676 				 * clause in 'word') */
677     char    	 *cp2;	    	/* Pointer for checking for wildcards in
678 				 * expansion before calling Dir_Expand */
679 
680     start = brace+1;
681 
682     /*
683      * Find the end of the brace clause first, being wary of nested brace
684      * clauses.
685      */
686     for (end = start, bracelevel = 0; *end != '\0'; end++) {
687 	if (*end == '{') {
688 	    bracelevel++;
689 	} else if ((*end == '}') && (bracelevel-- == 0)) {
690 	    break;
691 	}
692     }
693     if (*end == '\0') {
694 	Error("Unterminated {} clause \"%s\"", start);
695 	return;
696     } else {
697 	end++;
698     }
699     otherLen = brace - word + strlen(end);
700 
701     for (cp = start; cp < end; cp++) {
702 	/*
703 	 * Find the end of this piece of the clause.
704 	 */
705 	bracelevel = 0;
706 	while (*cp != ',') {
707 	    if (*cp == '{') {
708 		bracelevel++;
709 	    } else if ((*cp == '}') && (bracelevel-- <= 0)) {
710 		break;
711 	    }
712 	    cp++;
713 	}
714 	/*
715 	 * Allocate room for the combination and install the three pieces.
716 	 */
717 	file = bmake_malloc(otherLen + cp - start + 1);
718 	if (brace != word) {
719 	    strncpy(file, word, brace-word);
720 	}
721 	if (cp != start) {
722 	    strncpy(&file[brace-word], start, cp-start);
723 	}
724 	strcpy(&file[(brace-word)+(cp-start)], end);
725 
726 	/*
727 	 * See if the result has any wildcards in it. If we find one, call
728 	 * Dir_Expand right away, telling it to place the result on our list
729 	 * of expansions.
730 	 */
731 	for (cp2 = file; *cp2 != '\0'; cp2++) {
732 	    switch(*cp2) {
733 	    case '*':
734 	    case '?':
735 	    case '{':
736 	    case '[':
737 		Dir_Expand(file, path, expansions);
738 		goto next;
739 	    }
740 	}
741 	if (*cp2 == '\0') {
742 	    /*
743 	     * Hit the end w/o finding any wildcards, so stick the expansion
744 	     * on the end of the list.
745 	     */
746 	    (void)Lst_AtEnd(expansions, file);
747 	} else {
748 	next:
749 	    free(file);
750 	}
751 	start = cp+1;
752     }
753 }
754 
755 
756 /*-
757  *-----------------------------------------------------------------------
758  * DirExpandInt --
759  *	Internal expand routine. Passes through the directories in the
760  *	path one by one, calling DirMatchFiles for each. NOTE: This still
761  *	doesn't handle patterns in directories...
762  *
763  * Input:
764  *	word		Word to expand
765  *	path		Path on which to look
766  *	expansions	Place to store the result
767  *
768  * Results:
769  *	None.
770  *
771  * Side Effects:
772  *	Things are added to the expansions list.
773  *
774  *-----------------------------------------------------------------------
775  */
776 static void
777 DirExpandInt(const char *word, Lst path, Lst expansions)
778 {
779     LstNode 	  ln;	    	/* Current node */
780     Path	  *p;	    	/* Directory in the node */
781 
782     if (Lst_Open(path) == SUCCESS) {
783 	while ((ln = Lst_Next(path)) != NULL) {
784 	    p = (Path *)Lst_Datum(ln);
785 	    DirMatchFiles(word, p, expansions);
786 	}
787 	Lst_Close(path);
788     }
789 }
790 
791 /*-
792  *-----------------------------------------------------------------------
793  * DirPrintWord --
794  *	Print a word in the list of expansions. Callback for Dir_Expand
795  *	when DEBUG(DIR), via Lst_ForEach.
796  *
797  * Results:
798  *	=== 0
799  *
800  * Side Effects:
801  *	The passed word is printed, followed by a space.
802  *
803  *-----------------------------------------------------------------------
804  */
805 static int
806 DirPrintWord(void *word, void *dummy)
807 {
808     fprintf(debug_file, "%s ", (char *)word);
809 
810     return(dummy ? 0 : 0);
811 }
812 
813 /*-
814  *-----------------------------------------------------------------------
815  * Dir_Expand  --
816  *	Expand the given word into a list of words by globbing it looking
817  *	in the directories on the given search path.
818  *
819  * Input:
820  *	word		the word to expand
821  *	path		the list of directories in which to find the
822  *			resulting files
823  *	expansions	the list on which to place the results
824  *
825  * Results:
826  *	A list of words consisting of the files which exist along the search
827  *	path matching the given pattern.
828  *
829  * Side Effects:
830  *	Directories may be opened. Who knows?
831  *-----------------------------------------------------------------------
832  */
833 void
834 Dir_Expand(const char *word, Lst path, Lst expansions)
835 {
836     const char    	  *cp;
837 
838     if (DEBUG(DIR)) {
839 	fprintf(debug_file, "Expanding \"%s\"... ", word);
840     }
841 
842     cp = strchr(word, '{');
843     if (cp) {
844 	DirExpandCurly(word, cp, path, expansions);
845     } else {
846 	cp = strchr(word, '/');
847 	if (cp) {
848 	    /*
849 	     * The thing has a directory component -- find the first wildcard
850 	     * in the string.
851 	     */
852 	    for (cp = word; *cp; cp++) {
853 		if (*cp == '?' || *cp == '[' || *cp == '*' || *cp == '{') {
854 		    break;
855 		}
856 	    }
857 	    if (*cp == '{') {
858 		/*
859 		 * This one will be fun.
860 		 */
861 		DirExpandCurly(word, cp, path, expansions);
862 		return;
863 	    } else if (*cp != '\0') {
864 		/*
865 		 * Back up to the start of the component
866 		 */
867 		char  *dirpath;
868 
869 		while (cp > word && *cp != '/') {
870 		    cp--;
871 		}
872 		if (cp != word) {
873 		    char sc;
874 		    /*
875 		     * If the glob isn't in the first component, try and find
876 		     * all the components up to the one with a wildcard.
877 		     */
878 		    sc = cp[1];
879 		    ((char *)UNCONST(cp))[1] = '\0';
880 		    dirpath = Dir_FindFile(word, path);
881 		    ((char *)UNCONST(cp))[1] = sc;
882 		    /*
883 		     * dirpath is null if can't find the leading component
884 		     * XXX: Dir_FindFile won't find internal components.
885 		     * i.e. if the path contains ../Etc/Object and we're
886 		     * looking for Etc, it won't be found. Ah well.
887 		     * Probably not important.
888 		     */
889 		    if (dirpath != NULL) {
890 			char *dp = &dirpath[strlen(dirpath) - 1];
891 			if (*dp == '/')
892 			    *dp = '\0';
893 			path = Lst_Init(FALSE);
894 			(void)Dir_AddDir(path, dirpath);
895 			DirExpandInt(cp+1, path, expansions);
896 			Lst_Destroy(path, NULL);
897 		    }
898 		} else {
899 		    /*
900 		     * Start the search from the local directory
901 		     */
902 		    DirExpandInt(word, path, expansions);
903 		}
904 	    } else {
905 		/*
906 		 * Return the file -- this should never happen.
907 		 */
908 		DirExpandInt(word, path, expansions);
909 	    }
910 	} else {
911 	    /*
912 	     * First the files in dot
913 	     */
914 	    DirMatchFiles(word, dot, expansions);
915 
916 	    /*
917 	     * Then the files in every other directory on the path.
918 	     */
919 	    DirExpandInt(word, path, expansions);
920 	}
921     }
922     if (DEBUG(DIR)) {
923 	Lst_ForEach(expansions, DirPrintWord, NULL);
924 	fprintf(debug_file, "\n");
925     }
926 }
927 
928 /*-
929  *-----------------------------------------------------------------------
930  * DirLookup  --
931  *	Find if the file with the given name exists in the given path.
932  *
933  * Results:
934  *	The path to the file or NULL. This path is guaranteed to be in a
935  *	different part of memory than name and so may be safely free'd.
936  *
937  * Side Effects:
938  *	None.
939  *-----------------------------------------------------------------------
940  */
941 static char *
942 DirLookup(Path *p, const char *name MAKE_ATTR_UNUSED, const char *cp,
943           Boolean hasSlash MAKE_ATTR_UNUSED)
944 {
945     char *file;		/* the current filename to check */
946 
947     if (DEBUG(DIR)) {
948 	fprintf(debug_file, "   %s ...\n", p->name);
949     }
950 
951     if (Hash_FindEntry(&p->files, cp) == NULL)
952 	return NULL;
953 
954     file = str_concat(p->name, cp, STR_ADDSLASH);
955     if (DEBUG(DIR)) {
956 	fprintf(debug_file, "   returning %s\n", file);
957     }
958     p->hits += 1;
959     hits += 1;
960     return file;
961 }
962 
963 
964 /*-
965  *-----------------------------------------------------------------------
966  * DirLookupSubdir  --
967  *	Find if the file with the given name exists in the given path.
968  *
969  * Results:
970  *	The path to the file or NULL. This path is guaranteed to be in a
971  *	different part of memory than name and so may be safely free'd.
972  *
973  * Side Effects:
974  *	If the file is found, it is added in the modification times hash
975  *	table.
976  *-----------------------------------------------------------------------
977  */
978 static char *
979 DirLookupSubdir(Path *p, const char *name)
980 {
981     struct stat	  stb;		/* Buffer for stat, if necessary */
982     char 	 *file;		/* the current filename to check */
983 
984     if (p != dot) {
985 	file = str_concat(p->name, name, STR_ADDSLASH);
986     } else {
987 	/*
988 	 * Checking in dot -- DON'T put a leading ./ on the thing.
989 	 */
990 	file = bmake_strdup(name);
991     }
992 
993     if (DEBUG(DIR)) {
994 	fprintf(debug_file, "checking %s ...\n", file);
995     }
996 
997     if (cached_stat(file, &stb) == 0) {
998 	/*
999 	 * Save the modification time so if it's needed, we don't have
1000 	 * to fetch it again.
1001 	 */
1002 	if (DEBUG(DIR)) {
1003 	    fprintf(debug_file, "   Caching %s for %s\n", Targ_FmtTime(stb.st_mtime),
1004 		    file);
1005 	}
1006 	nearmisses += 1;
1007 	return (file);
1008     }
1009     free(file);
1010     return NULL;
1011 }
1012 
1013 /*-
1014  *-----------------------------------------------------------------------
1015  * DirLookupAbs  --
1016  *	Find if the file with the given name exists in the given path.
1017  *
1018  * Results:
1019  *	The path to the file, the empty string or NULL. If the file is
1020  *	the empty string, the search should be terminated.
1021  *	This path is guaranteed to be in a different part of memory
1022  *	than name and so may be safely free'd.
1023  *
1024  * Side Effects:
1025  *	None.
1026  *-----------------------------------------------------------------------
1027  */
1028 static char *
1029 DirLookupAbs(Path *p, const char *name, const char *cp)
1030 {
1031 	char *p1;		/* pointer into p->name */
1032 	const char *p2;		/* pointer into name */
1033 
1034 	if (DEBUG(DIR)) {
1035 		fprintf(debug_file, "   %s ...\n", p->name);
1036 	}
1037 
1038 	/*
1039 	 * If the file has a leading path component and that component
1040 	 * exactly matches the entire name of the current search
1041 	 * directory, we can attempt another cache lookup. And if we don't
1042 	 * have a hit, we can safely assume the file does not exist at all.
1043 	 */
1044 	for (p1 = p->name, p2 = name; *p1 && *p1 == *p2; p1++, p2++) {
1045 		continue;
1046 	}
1047 	if (*p1 != '\0' || p2 != cp - 1) {
1048 		return NULL;
1049 	}
1050 
1051 	if (Hash_FindEntry(&p->files, cp) == NULL) {
1052 		if (DEBUG(DIR)) {
1053 			fprintf(debug_file, "   must be here but isn't -- returning\n");
1054 		}
1055 		/* Return empty string: terminates search */
1056 		return bmake_strdup("");
1057 	}
1058 
1059 	p->hits += 1;
1060 	hits += 1;
1061 	if (DEBUG(DIR)) {
1062 		fprintf(debug_file, "   returning %s\n", name);
1063 	}
1064 	return (bmake_strdup(name));
1065 }
1066 
1067 /*-
1068  *-----------------------------------------------------------------------
1069  * DirFindDot  --
1070  *	Find the file given on "." or curdir
1071  *
1072  * Results:
1073  *	The path to the file or NULL. This path is guaranteed to be in a
1074  *	different part of memory than name and so may be safely free'd.
1075  *
1076  * Side Effects:
1077  *	Hit counts change
1078  *-----------------------------------------------------------------------
1079  */
1080 static char *
1081 DirFindDot(Boolean hasSlash MAKE_ATTR_UNUSED, const char *name, const char *cp)
1082 {
1083 
1084 	if (Hash_FindEntry(&dot->files, cp) != NULL) {
1085 	    if (DEBUG(DIR)) {
1086 		fprintf(debug_file, "   in '.'\n");
1087 	    }
1088 	    hits += 1;
1089 	    dot->hits += 1;
1090 	    return (bmake_strdup(name));
1091 	}
1092 	if (cur &&
1093 	    Hash_FindEntry(&cur->files, cp) != NULL) {
1094 	    if (DEBUG(DIR)) {
1095 		fprintf(debug_file, "   in ${.CURDIR} = %s\n", cur->name);
1096 	    }
1097 	    hits += 1;
1098 	    cur->hits += 1;
1099 	    return str_concat(cur->name, cp, STR_ADDSLASH);
1100 	}
1101 
1102 	return NULL;
1103 }
1104 
1105 /*-
1106  *-----------------------------------------------------------------------
1107  * Dir_FindFile  --
1108  *	Find the file with the given name along the given search path.
1109  *
1110  * Input:
1111  *	name		the file to find
1112  *	path		the Lst of directories to search
1113  *
1114  * Results:
1115  *	The path to the file or NULL. This path is guaranteed to be in a
1116  *	different part of memory than name and so may be safely free'd.
1117  *
1118  * Side Effects:
1119  *	If the file is found in a directory which is not on the path
1120  *	already (either 'name' is absolute or it is a relative path
1121  *	[ dir1/.../dirn/file ] which exists below one of the directories
1122  *	already on the search path), its directory is added to the end
1123  *	of the path on the assumption that there will be more files in
1124  *	that directory later on. Sometimes this is true. Sometimes not.
1125  *-----------------------------------------------------------------------
1126  */
1127 char *
1128 Dir_FindFile(const char *name, Lst path)
1129 {
1130     LstNode       ln;			/* a list element */
1131     char	  *file;		/* the current filename to check */
1132     Path	  *p;			/* current path member */
1133     const char	  *cp;			/* Terminal name of file */
1134     Boolean	  hasLastDot = FALSE;	/* true we should search dot last */
1135     Boolean	  hasSlash;		/* true if 'name' contains a / */
1136     struct stat	  stb;			/* Buffer for stat, if necessary */
1137     Hash_Entry	  *entry;		/* Entry for mtimes table */
1138     const char   *trailing_dot = ".";
1139 
1140     /*
1141      * Find the final component of the name and note whether it has a
1142      * slash in it (the name, I mean)
1143      */
1144     cp = strrchr(name, '/');
1145     if (cp) {
1146 	hasSlash = TRUE;
1147 	cp += 1;
1148     } else {
1149 	hasSlash = FALSE;
1150 	cp = name;
1151     }
1152 
1153     if (DEBUG(DIR)) {
1154 	fprintf(debug_file, "Searching for %s ...", name);
1155     }
1156 
1157     if (Lst_Open(path) == FAILURE) {
1158 	if (DEBUG(DIR)) {
1159 	    fprintf(debug_file, "couldn't open path, file not found\n");
1160 	}
1161 	misses += 1;
1162 	return NULL;
1163     }
1164 
1165     if ((ln = Lst_First(path)) != NULL) {
1166 	p = (Path *)Lst_Datum(ln);
1167 	if (p == dotLast) {
1168 	    hasLastDot = TRUE;
1169             if (DEBUG(DIR))
1170 		fprintf(debug_file, "[dot last]...");
1171 	}
1172     }
1173     if (DEBUG(DIR)) {
1174 	fprintf(debug_file, "\n");
1175     }
1176 
1177     /*
1178      * If there's no leading directory components or if the leading
1179      * directory component is exactly `./', consult the cached contents
1180      * of each of the directories on the search path.
1181      */
1182     if (!hasSlash || (cp - name == 2 && *name == '.')) {
1183 	    /*
1184 	     * We look through all the directories on the path seeking one which
1185 	     * contains the final component of the given name.  If such a beast
1186 	     * is found, we concatenate the directory name and the final
1187 	     * component and return the resulting string. If we don't find any
1188 	     * such thing, we go on to phase two...
1189 	     *
1190 	     * No matter what, we always look for the file in the current
1191 	     * directory before anywhere else (unless we found the magic
1192 	     * DOTLAST path, in which case we search it last) and we *do not*
1193 	     * add the ./ to it if it exists.
1194 	     * This is so there are no conflicts between what the user
1195 	     * specifies (fish.c) and what pmake finds (./fish.c).
1196 	     */
1197 	    if (!hasLastDot &&
1198 			(file = DirFindDot(hasSlash, name, cp)) != NULL) {
1199 		    Lst_Close(path);
1200 		    return file;
1201 	    }
1202 
1203 	    while ((ln = Lst_Next(path)) != NULL) {
1204 		p = (Path *)Lst_Datum(ln);
1205 		if (p == dotLast)
1206 		    continue;
1207 		if ((file = DirLookup(p, name, cp, hasSlash)) != NULL) {
1208 		    Lst_Close(path);
1209 		    return file;
1210 		}
1211 	    }
1212 
1213 	    if (hasLastDot &&
1214 			(file = DirFindDot(hasSlash, name, cp)) != NULL) {
1215 		    Lst_Close(path);
1216 		    return file;
1217 	    }
1218     }
1219     Lst_Close(path);
1220 
1221     /*
1222      * We didn't find the file on any directory in the search path.
1223      * If the name doesn't contain a slash, that means it doesn't exist.
1224      * If it *does* contain a slash, however, there is still hope: it
1225      * could be in a subdirectory of one of the members of the search
1226      * path. (eg. /usr/include and sys/types.h. The above search would
1227      * fail to turn up types.h in /usr/include, but it *is* in
1228      * /usr/include/sys/types.h).
1229      * [ This no longer applies: If we find such a beast, we assume there
1230      * will be more (what else can we assume?) and add all but the last
1231      * component of the resulting name onto the search path (at the
1232      * end).]
1233      * This phase is only performed if the file is *not* absolute.
1234      */
1235     if (!hasSlash) {
1236 	if (DEBUG(DIR)) {
1237 	    fprintf(debug_file, "   failed.\n");
1238 	}
1239 	misses += 1;
1240 	return NULL;
1241     }
1242 
1243     if (*cp == '\0') {
1244 	/* we were given a trailing "/" */
1245 	cp = trailing_dot;
1246     }
1247 
1248     if (name[0] != '/') {
1249 	Boolean	checkedDot = FALSE;
1250 
1251 	if (DEBUG(DIR)) {
1252 	    fprintf(debug_file, "   Trying subdirectories...\n");
1253 	}
1254 
1255 	if (!hasLastDot) {
1256 		if (dot) {
1257 			checkedDot = TRUE;
1258 			if ((file = DirLookupSubdir(dot, name)) != NULL)
1259 				return file;
1260 		}
1261 		if (cur && (file = DirLookupSubdir(cur, name)) != NULL)
1262 			return file;
1263 	}
1264 
1265 	(void)Lst_Open(path);
1266 	while ((ln = Lst_Next(path)) != NULL) {
1267 	    p = (Path *)Lst_Datum(ln);
1268 	    if (p == dotLast)
1269 		continue;
1270 	    if (p == dot) {
1271 		    if (checkedDot)
1272 			    continue;
1273 		checkedDot = TRUE;
1274 	    }
1275 	    if ((file = DirLookupSubdir(p, name)) != NULL) {
1276 		Lst_Close(path);
1277 		return file;
1278 	    }
1279 	}
1280 	Lst_Close(path);
1281 
1282 	if (hasLastDot) {
1283 		if (dot && !checkedDot) {
1284 			checkedDot = TRUE;
1285 			if ((file = DirLookupSubdir(dot, name)) != NULL)
1286 				return file;
1287 		}
1288 		if (cur && (file = DirLookupSubdir(cur, name)) != NULL)
1289 			return file;
1290 	}
1291 
1292 	if (checkedDot) {
1293 	    /*
1294 	     * Already checked by the given name, since . was in the path,
1295 	     * so no point in proceeding...
1296 	     */
1297 	    if (DEBUG(DIR)) {
1298 		fprintf(debug_file, "   Checked . already, returning NULL\n");
1299 	    }
1300 	    return NULL;
1301 	}
1302 
1303     } else { /* name[0] == '/' */
1304 
1305 	/*
1306 	 * For absolute names, compare directory path prefix against the
1307 	 * the directory path of each member on the search path for an exact
1308 	 * match. If we have an exact match on any member of the search path,
1309 	 * use the cached contents of that member to lookup the final file
1310 	 * component. If that lookup fails we can safely assume that the
1311 	 * file does not exist at all.  This is signified by DirLookupAbs()
1312 	 * returning an empty string.
1313 	 */
1314 	if (DEBUG(DIR)) {
1315 	    fprintf(debug_file, "   Trying exact path matches...\n");
1316 	}
1317 
1318 	if (!hasLastDot && cur && (file = DirLookupAbs(cur, name, cp)) != NULL)
1319 	    return *file?file:NULL;
1320 
1321 	(void)Lst_Open(path);
1322 	while ((ln = Lst_Next(path)) != NULL) {
1323 	    p = (Path *)Lst_Datum(ln);
1324 	    if (p == dotLast)
1325 		continue;
1326 	    if ((file = DirLookupAbs(p, name, cp)) != NULL) {
1327 		Lst_Close(path);
1328 		return *file?file:NULL;
1329 	    }
1330 	}
1331 	Lst_Close(path);
1332 
1333 	if (hasLastDot && cur && (file = DirLookupAbs(cur, name, cp)) != NULL)
1334 	    return *file?file:NULL;
1335     }
1336 
1337     /*
1338      * Didn't find it that way, either. Sigh. Phase 3. Add its directory
1339      * onto the search path in any case, just in case, then look for the
1340      * thing in the hash table. If we find it, grand. We return a new
1341      * copy of the name. Otherwise we sadly return a NULL pointer. Sigh.
1342      * Note that if the directory holding the file doesn't exist, this will
1343      * do an extra search of the final directory on the path. Unless something
1344      * weird happens, this search won't succeed and life will be groovy.
1345      *
1346      * Sigh. We cannot add the directory onto the search path because
1347      * of this amusing case:
1348      * $(INSTALLDIR)/$(FILE): $(FILE)
1349      *
1350      * $(FILE) exists in $(INSTALLDIR) but not in the current one.
1351      * When searching for $(FILE), we will find it in $(INSTALLDIR)
1352      * b/c we added it here. This is not good...
1353      */
1354 #ifdef notdef
1355     if (cp == traling_dot) {
1356 	cp = strrchr(name, '/');
1357 	cp += 1;
1358     }
1359     cp[-1] = '\0';
1360     (void)Dir_AddDir(path, name);
1361     cp[-1] = '/';
1362 
1363     bigmisses += 1;
1364     ln = Lst_Last(path);
1365     if (ln == NULL) {
1366 	return NULL;
1367     } else {
1368 	p = (Path *)Lst_Datum(ln);
1369     }
1370 
1371     if (Hash_FindEntry(&p->files, cp) != NULL) {
1372 	return (bmake_strdup(name));
1373     } else {
1374 	return NULL;
1375     }
1376 #else /* !notdef */
1377     if (DEBUG(DIR)) {
1378 	fprintf(debug_file, "   Looking for \"%s\" ...\n", name);
1379     }
1380 
1381     bigmisses += 1;
1382     entry = Hash_FindEntry(&mtimes, name);
1383     if (entry != NULL) {
1384 	if (DEBUG(DIR)) {
1385 	    fprintf(debug_file, "   got it (in mtime cache)\n");
1386 	}
1387 	return(bmake_strdup(name));
1388     } else if (cached_stat(name, &stb) == 0) {
1389 	if (DEBUG(DIR)) {
1390 	    fprintf(debug_file, "   Caching %s for %s\n", Targ_FmtTime(stb.st_mtime),
1391 		    name);
1392 	}
1393 	return (bmake_strdup(name));
1394     } else {
1395 	if (DEBUG(DIR)) {
1396 	    fprintf(debug_file, "   failed. Returning NULL\n");
1397 	}
1398 	return NULL;
1399     }
1400 #endif /* notdef */
1401 }
1402 
1403 
1404 /*-
1405  *-----------------------------------------------------------------------
1406  * Dir_FindHereOrAbove  --
1407  *	search for a path starting at a given directory and then working
1408  *	our way up towards the root.
1409  *
1410  * Input:
1411  *	here		starting directory
1412  *	search_path	the path we are looking for
1413  *	result		the result of a successful search is placed here
1414  *	rlen		the length of the result buffer
1415  *			(typically MAXPATHLEN + 1)
1416  *
1417  * Results:
1418  *	0 on failure, 1 on success [in which case the found path is put
1419  *	in the result buffer].
1420  *
1421  * Side Effects:
1422  *-----------------------------------------------------------------------
1423  */
1424 int
1425 Dir_FindHereOrAbove(char *here, char *search_path, char *result, int rlen) {
1426 
1427 	struct stat st;
1428 	char dirbase[MAXPATHLEN + 1], *db_end;
1429         char try[MAXPATHLEN + 1], *try_end;
1430 
1431 	/* copy out our starting point */
1432 	snprintf(dirbase, sizeof(dirbase), "%s", here);
1433 	db_end = dirbase + strlen(dirbase);
1434 
1435 	/* loop until we determine a result */
1436 	while (1) {
1437 
1438 		/* try and stat(2) it ... */
1439 		snprintf(try, sizeof(try), "%s/%s", dirbase, search_path);
1440 		if (cached_stat(try, &st) != -1) {
1441 			/*
1442 			 * success!  if we found a file, chop off
1443 			 * the filename so we return a directory.
1444 			 */
1445 			if ((st.st_mode & S_IFMT) != S_IFDIR) {
1446 				try_end = try + strlen(try);
1447 				while (try_end > try && *try_end != '/')
1448 					try_end--;
1449 				if (try_end > try)
1450 					*try_end = 0;	/* chop! */
1451 			}
1452 
1453 			/*
1454 			 * done!
1455 			 */
1456 			snprintf(result, rlen, "%s", try);
1457 			return(1);
1458 		}
1459 
1460 		/*
1461 		 * nope, we didn't find it.  if we used up dirbase we've
1462 		 * reached the root and failed.
1463 		 */
1464 		if (db_end == dirbase)
1465 			break;		/* failed! */
1466 
1467 		/*
1468 		 * truncate dirbase from the end to move up a dir
1469 		 */
1470 		while (db_end > dirbase && *db_end != '/')
1471 			db_end--;
1472 		*db_end = 0;		/* chop! */
1473 
1474 	} /* while (1) */
1475 
1476 	/*
1477 	 * we failed...
1478 	 */
1479 	return(0);
1480 }
1481 
1482 /*-
1483  *-----------------------------------------------------------------------
1484  * Dir_MTime  --
1485  *	Find the modification time of the file described by gn along the
1486  *	search path dirSearchPath.
1487  *
1488  * Input:
1489  *	gn		the file whose modification time is desired
1490  *
1491  * Results:
1492  *	The modification time or 0 if it doesn't exist
1493  *
1494  * Side Effects:
1495  *	The modification time is placed in the node's mtime slot.
1496  *	If the node didn't have a path entry before, and Dir_FindFile
1497  *	found one for it, the full name is placed in the path slot.
1498  *-----------------------------------------------------------------------
1499  */
1500 int
1501 Dir_MTime(GNode *gn, Boolean recheck)
1502 {
1503     char          *fullName;  /* the full pathname of name */
1504     struct stat	  stb;	      /* buffer for finding the mod time */
1505     Hash_Entry	  *entry;
1506 
1507     if (gn->type & OP_ARCHV) {
1508 	return Arch_MTime(gn);
1509     } else if (gn->type & OP_PHONY) {
1510 	gn->mtime = 0;
1511 	return 0;
1512     } else if (gn->path == NULL) {
1513 	if (gn->type & OP_NOPATH)
1514 	    fullName = NULL;
1515 	else {
1516 	    fullName = Dir_FindFile(gn->name, Suff_FindPath(gn));
1517 	    if (fullName == NULL && gn->flags & FROM_DEPEND &&
1518 		!Lst_IsEmpty(gn->iParents)) {
1519 		char *cp;
1520 
1521 		cp = strrchr(gn->name, '/');
1522 		if (cp) {
1523 		    /*
1524 		     * This is an implied source, and it may have moved,
1525 		     * see if we can find it via the current .PATH
1526 		     */
1527 		    cp++;
1528 
1529 		    fullName = Dir_FindFile(cp, Suff_FindPath(gn));
1530 		    if (fullName) {
1531 			/*
1532 			 * Put the found file in gn->path
1533 			 * so that we give that to the compiler.
1534 			 */
1535 			gn->path = bmake_strdup(fullName);
1536 			if (!Job_RunTarget(".STALE", gn->fname))
1537 			    fprintf(stdout,
1538 				"%s: %s, %d: ignoring stale %s for %s, "
1539 				"found %s\n", progname, gn->fname, gn->lineno,
1540 				makeDependfile, gn->name, fullName);
1541 		    }
1542 		}
1543 	    }
1544 	    if (DEBUG(DIR))
1545 		fprintf(debug_file, "Found '%s' as '%s'\n",
1546 			gn->name, fullName ? fullName : "(not found)" );
1547 	}
1548     } else {
1549 	fullName = gn->path;
1550     }
1551 
1552     if (fullName == NULL) {
1553 	fullName = bmake_strdup(gn->name);
1554     }
1555 
1556     if (!recheck)
1557 	entry = Hash_FindEntry(&mtimes, fullName);
1558     else
1559 	entry = NULL;
1560     if (entry != NULL) {
1561 	stb.st_mtime = Hash_GetTimeValue(entry);
1562 	if (DEBUG(DIR)) {
1563 	    fprintf(debug_file, "Using cached time %s for %s\n",
1564 		    Targ_FmtTime(stb.st_mtime), fullName);
1565 	}
1566     } else if (cached_stats(&mtimes, fullName, &stb, recheck ? CST_UPDATE : 0) < 0) {
1567 	if (gn->type & OP_MEMBER) {
1568 	    if (fullName != gn->path)
1569 		free(fullName);
1570 	    return Arch_MemMTime(gn);
1571 	} else {
1572 	    stb.st_mtime = 0;
1573 	}
1574     }
1575 
1576     if (fullName && gn->path == NULL) {
1577 	gn->path = fullName;
1578     }
1579 
1580     gn->mtime = stb.st_mtime;
1581     return (gn->mtime);
1582 }
1583 
1584 /*-
1585  *-----------------------------------------------------------------------
1586  * Dir_AddDir --
1587  *	Add the given name to the end of the given path. The order of
1588  *	the arguments is backwards so ParseDoDependency can do a
1589  *	Lst_ForEach of its list of paths...
1590  *
1591  * Input:
1592  *	path		the path to which the directory should be
1593  *			added
1594  *	name		the name of the directory to add
1595  *
1596  * Results:
1597  *	none
1598  *
1599  * Side Effects:
1600  *	A structure is added to the list and the directory is
1601  *	read and hashed.
1602  *-----------------------------------------------------------------------
1603  */
1604 Path *
1605 Dir_AddDir(Lst path, const char *name)
1606 {
1607     LstNode       ln = NULL; /* node in case Path structure is found */
1608     Path	  *p = NULL;  /* pointer to new Path structure */
1609     DIR     	  *d;	      /* for reading directory */
1610     struct dirent *dp;	      /* entry in directory */
1611 
1612     if (strcmp(name, ".DOTLAST") == 0) {
1613 	ln = Lst_Find(path, name, DirFindName);
1614 	if (ln != NULL)
1615 	    return (Path *)Lst_Datum(ln);
1616 	else {
1617 	    dotLast->refCount += 1;
1618 	    (void)Lst_AtFront(path, dotLast);
1619 	}
1620     }
1621 
1622     if (path)
1623 	ln = Lst_Find(openDirectories, name, DirFindName);
1624     if (ln != NULL) {
1625 	p = (Path *)Lst_Datum(ln);
1626 	if (path && Lst_Member(path, p) == NULL) {
1627 	    p->refCount += 1;
1628 	    (void)Lst_AtEnd(path, p);
1629 	}
1630     } else {
1631 	if (DEBUG(DIR)) {
1632 	    fprintf(debug_file, "Caching %s ...", name);
1633 	}
1634 
1635 	if ((d = opendir(name)) != NULL) {
1636 	    p = bmake_malloc(sizeof(Path));
1637 	    p->name = bmake_strdup(name);
1638 	    p->hits = 0;
1639 	    p->refCount = 1;
1640 	    Hash_InitTable(&p->files, -1);
1641 
1642 	    while ((dp = readdir(d)) != NULL) {
1643 #if defined(sun) && defined(d_ino) /* d_ino is a sunos4 #define for d_fileno */
1644 		/*
1645 		 * The sun directory library doesn't check for a 0 inode
1646 		 * (0-inode slots just take up space), so we have to do
1647 		 * it ourselves.
1648 		 */
1649 		if (dp->d_fileno == 0) {
1650 		    continue;
1651 		}
1652 #endif /* sun && d_ino */
1653 		(void)Hash_CreateEntry(&p->files, dp->d_name, NULL);
1654 	    }
1655 	    (void)closedir(d);
1656 	    (void)Lst_AtEnd(openDirectories, p);
1657 	    if (path != NULL)
1658 		(void)Lst_AtEnd(path, p);
1659 	}
1660 	if (DEBUG(DIR)) {
1661 	    fprintf(debug_file, "done\n");
1662 	}
1663     }
1664     return p;
1665 }
1666 
1667 /*-
1668  *-----------------------------------------------------------------------
1669  * Dir_CopyDir --
1670  *	Callback function for duplicating a search path via Lst_Duplicate.
1671  *	Ups the reference count for the directory.
1672  *
1673  * Results:
1674  *	Returns the Path it was given.
1675  *
1676  * Side Effects:
1677  *	The refCount of the path is incremented.
1678  *
1679  *-----------------------------------------------------------------------
1680  */
1681 void *
1682 Dir_CopyDir(void *p)
1683 {
1684     ((Path *)p)->refCount += 1;
1685 
1686     return (p);
1687 }
1688 
1689 /*-
1690  *-----------------------------------------------------------------------
1691  * Dir_MakeFlags --
1692  *	Make a string by taking all the directories in the given search
1693  *	path and preceding them by the given flag. Used by the suffix
1694  *	module to create variables for compilers based on suffix search
1695  *	paths.
1696  *
1697  * Input:
1698  *	flag		flag which should precede each directory
1699  *	path		list of directories
1700  *
1701  * Results:
1702  *	The string mentioned above. Note that there is no space between
1703  *	the given flag and each directory. The empty string is returned if
1704  *	Things don't go well.
1705  *
1706  * Side Effects:
1707  *	None
1708  *-----------------------------------------------------------------------
1709  */
1710 char *
1711 Dir_MakeFlags(const char *flag, Lst path)
1712 {
1713     char	  *str;	  /* the string which will be returned */
1714     char	  *s1, *s2;/* the current directory preceded by 'flag' */
1715     LstNode	  ln;	  /* the node of the current directory */
1716     Path	  *p;	  /* the structure describing the current directory */
1717 
1718     str = bmake_strdup("");
1719 
1720     if (Lst_Open(path) == SUCCESS) {
1721 	while ((ln = Lst_Next(path)) != NULL) {
1722 	    p = (Path *)Lst_Datum(ln);
1723 	    s2 = str_concat(flag, p->name, 0);
1724 	    str = str_concat(s1 = str, s2, STR_ADDSPACE);
1725 	    free(s1);
1726 	    free(s2);
1727 	}
1728 	Lst_Close(path);
1729     }
1730 
1731     return (str);
1732 }
1733 
1734 /*-
1735  *-----------------------------------------------------------------------
1736  * Dir_Destroy --
1737  *	Nuke a directory descriptor, if possible. Callback procedure
1738  *	for the suffixes module when destroying a search path.
1739  *
1740  * Input:
1741  *	pp		The directory descriptor to nuke
1742  *
1743  * Results:
1744  *	None.
1745  *
1746  * Side Effects:
1747  *	If no other path references this directory (refCount == 0),
1748  *	the Path and all its data are freed.
1749  *
1750  *-----------------------------------------------------------------------
1751  */
1752 void
1753 Dir_Destroy(void *pp)
1754 {
1755     Path    	  *p = (Path *)pp;
1756     p->refCount -= 1;
1757 
1758     if (p->refCount == 0) {
1759 	LstNode	ln;
1760 
1761 	ln = Lst_Member(openDirectories, p);
1762 	(void)Lst_Remove(openDirectories, ln);
1763 
1764 	Hash_DeleteTable(&p->files);
1765 	free(p->name);
1766 	free(p);
1767     }
1768 }
1769 
1770 /*-
1771  *-----------------------------------------------------------------------
1772  * Dir_ClearPath --
1773  *	Clear out all elements of the given search path. This is different
1774  *	from destroying the list, notice.
1775  *
1776  * Input:
1777  *	path		Path to clear
1778  *
1779  * Results:
1780  *	None.
1781  *
1782  * Side Effects:
1783  *	The path is set to the empty list.
1784  *
1785  *-----------------------------------------------------------------------
1786  */
1787 void
1788 Dir_ClearPath(Lst path)
1789 {
1790     Path    *p;
1791     while (!Lst_IsEmpty(path)) {
1792 	p = (Path *)Lst_DeQueue(path);
1793 	Dir_Destroy(p);
1794     }
1795 }
1796 
1797 
1798 /*-
1799  *-----------------------------------------------------------------------
1800  * Dir_Concat --
1801  *	Concatenate two paths, adding the second to the end of the first.
1802  *	Makes sure to avoid duplicates.
1803  *
1804  * Input:
1805  *	path1		Dest
1806  *	path2		Source
1807  *
1808  * Results:
1809  *	None
1810  *
1811  * Side Effects:
1812  *	Reference counts for added dirs are upped.
1813  *
1814  *-----------------------------------------------------------------------
1815  */
1816 void
1817 Dir_Concat(Lst path1, Lst path2)
1818 {
1819     LstNode ln;
1820     Path    *p;
1821 
1822     for (ln = Lst_First(path2); ln != NULL; ln = Lst_Succ(ln)) {
1823 	p = (Path *)Lst_Datum(ln);
1824 	if (Lst_Member(path1, p) == NULL) {
1825 	    p->refCount += 1;
1826 	    (void)Lst_AtEnd(path1, p);
1827 	}
1828     }
1829 }
1830 
1831 /********** DEBUG INFO **********/
1832 void
1833 Dir_PrintDirectories(void)
1834 {
1835     LstNode	ln;
1836     Path	*p;
1837 
1838     fprintf(debug_file, "#*** Directory Cache:\n");
1839     fprintf(debug_file, "# Stats: %d hits %d misses %d near misses %d losers (%d%%)\n",
1840 	      hits, misses, nearmisses, bigmisses,
1841 	      (hits+bigmisses+nearmisses ?
1842 	       hits * 100 / (hits + bigmisses + nearmisses) : 0));
1843     fprintf(debug_file, "# %-20s referenced\thits\n", "directory");
1844     if (Lst_Open(openDirectories) == SUCCESS) {
1845 	while ((ln = Lst_Next(openDirectories)) != NULL) {
1846 	    p = (Path *)Lst_Datum(ln);
1847 	    fprintf(debug_file, "# %-20s %10d\t%4d\n", p->name, p->refCount, p->hits);
1848 	}
1849 	Lst_Close(openDirectories);
1850     }
1851 }
1852 
1853 static int
1854 DirPrintDir(void *p, void *dummy)
1855 {
1856     fprintf(debug_file, "%s ", ((Path *)p)->name);
1857     return (dummy ? 0 : 0);
1858 }
1859 
1860 void
1861 Dir_PrintPath(Lst path)
1862 {
1863     Lst_ForEach(path, DirPrintDir, NULL);
1864 }
1865