1 /* $NetBSD: dir.c,v 1.65 2012/06/12 19:21:50 joerg Exp $ */
4 * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
7 * This code is derived from software contributed to Berkeley by
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
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.
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
36 * Copyright (c) 1988, 1989 by Adam de Boor
37 * Copyright (c) 1989 by Berkeley Softworks
38 * All rights reserved.
40 * This code is derived from software contributed to Berkeley by
43 * Redistribution and use in source and binary forms, with or without
44 * modification, are permitted provided that the following conditions
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.
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
73 static char rcsid[] = "$NetBSD: dir.c,v 1.65 2012/06/12 19:21:50 joerg Exp $";
75 #include <sys/cdefs.h>
78 static char sccsid[] = "@(#)dir.c 8.2 (Berkeley) 1/2/94";
80 __RCSID("$NetBSD: dir.c,v 1.65 2012/06/12 19:21:50 joerg Exp $");
87 * Directory searching using wildcards and/or normal names...
88 * Used both for source wildcarding in the Makefile and for finding
91 * The interface for this module is:
92 * Dir_Init Initialize the module.
94 * Dir_InitCur Set the cur Path.
96 * Dir_InitDot Set the dot Path.
98 * Dir_End Cleanup the module.
100 * Dir_SetPATH Set ${.PATH} to reflect state of dirSearchPath.
102 * Dir_HasWildcards Returns TRUE if the name given it needs to
103 * be wildcard-expanded.
105 * Dir_Expand Given a pattern and a path, return a Lst of names
106 * which match the pattern on the search path.
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.
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 ("/").
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
121 * Dir_AddDir Add a directory to a search path.
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.
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
132 * Dir_ClearPath Resets a search path to the empty list.
135 * Dir_PrintDirectories Print stats about the directory cache.
138 #include <sys/types.h>
139 #include <sys/stat.h>
150 * A search path consists of a Lst of Path structures. A Path structure
151 * has in it the name of the directory and a hash table of all the files
152 * in the directory. This is used to cut down on the number of system
153 * calls necessary to find implicit dependents and their like. Since
154 * these searches are made before any actions are taken, we need not
155 * worry about the directory changing due to creation commands. If this
156 * hampers the style of some makefiles, they must be changed.
158 * A list of all previously-read directories is kept in the
159 * openDirectories Lst. This list is checked first before a directory
162 * The need for the caching of whole directories is brought about by
163 * the multi-level transformation code in suff.c, which tends to search
164 * for far more files than regular make does. In the initial
165 * implementation, the amount of time spent performing "stat" calls was
166 * truly astronomical. The problem with hashing at the start is,
167 * of course, that pmake doesn't then detect changes to these directories
168 * during the course of the make. Three possibilities suggest themselves:
170 * 1) just use stat to test for a file's existence. As mentioned
171 * above, this is very inefficient due to the number of checks
172 * engendered by the multi-level transformation code.
173 * 2) use readdir() and company to search the directories, keeping
174 * them open between checks. I have tried this and while it
175 * didn't slow down the process too much, it could severely
176 * affect the amount of parallelism available as each directory
177 * open would take another file descriptor out of play for
178 * handling I/O for another job. Given that it is only recently
179 * that UNIX OS's have taken to allowing more than 20 or 32
180 * file descriptors for a process, this doesn't seem acceptable
182 * 3) record the mtime of the directory in the Path structure and
183 * verify the directory hasn't changed since the contents were
184 * hashed. This will catch the creation or deletion of files,
185 * but not the updating of files. However, since it is the
186 * creation and deletion that is the problem, this could be
187 * a good thing to do. Unfortunately, if the directory (say ".")
188 * were fairly large and changed fairly frequently, the constant
189 * rehashing could seriously degrade performance. It might be
190 * good in such cases to keep track of the number of rehashes
191 * and if the number goes over a (small) limit, resort to using
194 * An additional thing to consider is that pmake is used primarily
195 * to create C programs and until recently pcc-based compilers refused
196 * to allow you to specify where the resulting object file should be
197 * placed. This forced all objects to be created in the current
198 * directory. This isn't meant as a full excuse, just an explanation of
199 * some of the reasons for the caching used here.
201 * One more note: the location of a target's file is only performed
202 * on the downward traversal of the graph and then only for terminal
203 * nodes in the graph. This could be construed as wrong in some cases,
204 * but prevents inadvertent modification of files when the "installed"
205 * directory for a file is provided in the search path.
207 * Another data structure maintained by this module is an mtime
208 * cache used when the searching of cached directories fails to find
209 * a file. In the past, Dir_FindFile would simply perform an access()
210 * call in such a case to determine if the file could be found using
211 * just the name given. When this hit, however, all that was gained
212 * was the knowledge that the file existed. Given that an access() is
213 * essentially a stat() without the copyout() call, and that the same
214 * filesystem overhead would have to be incurred in Dir_MTime, it made
215 * sense to replace the access() with a stat() and record the mtime
216 * in a cache for when Dir_MTime was actually called.
219 Lst dirSearchPath; /* main search path */
221 static Lst openDirectories; /* the list of all open directories */
224 * Variables for gathering statistics on the efficiency of the hashing
227 static int hits, /* Found in directory cache */
228 misses, /* Sad, but not evil misses */
229 nearmisses, /* Found under search path */
230 bigmisses; /* Sought by itself */
232 static Path *dot; /* contents of current directory */
233 static Path *cur; /* contents of current directory, if not dot */
234 static Path *dotLast; /* a fake path entry indicating we need to
236 static Hash_Table mtimes; /* Results of doing a last-resort stat in
237 * Dir_FindFile -- if we have to go to the
238 * system to find the file, we might as well
239 * have its mtime on record. XXX: If this is done
240 * way early, there's a chance other rules will
241 * have already updated the file, in which case
242 * we'll update it again. Generally, there won't
243 * be two rules to update a single file, so this
244 * should be ok, but... */
247 static int DirFindName(const void *, const void *);
248 static int DirMatchFiles(const char *, Path *, Lst);
249 static void DirExpandCurly(const char *, const char *, Lst, Lst);
250 static void DirExpandInt(const char *, Lst, Lst);
251 static int DirPrintWord(void *, void *);
252 static int DirPrintDir(void *, void *);
253 static char *DirLookup(Path *, const char *, const char *, Boolean);
254 static char *DirLookupSubdir(Path *, const char *);
255 static char *DirFindDot(Boolean, const char *, const char *);
256 static char *DirLookupAbs(Path *, const char *, const char *);
259 *-----------------------------------------------------------------------
261 * initialize things for this module
267 * some directories may be opened.
268 *-----------------------------------------------------------------------
271 Dir_Init(const char *cdname)
273 dirSearchPath = Lst_Init(FALSE);
274 openDirectories = Lst_Init(FALSE);
275 Hash_InitTable(&mtimes, 0);
279 dotLast = bmake_malloc(sizeof(Path));
280 dotLast->refCount = 1;
282 dotLast->name = bmake_strdup(".DOTLAST");
283 Hash_InitTable(&dotLast->files, -1);
287 * Called by Dir_Init() and whenever .CURDIR is assigned to.
290 Dir_InitCur(const char *cdname)
294 if (cdname != NULL) {
296 * Our build directory is not the same as our source directory.
297 * Keep this one around too.
299 if ((p = Dir_AddDir(NULL, cdname))) {
301 if (cur && cur != p) {
303 * We've been here before, cleanup.
314 *-----------------------------------------------------------------------
316 * (re)initialize "dot" (current/object directory) path hash
322 * some directories may be opened.
323 *-----------------------------------------------------------------------
331 /* Remove old entry from openDirectories, but do not destroy. */
332 ln = Lst_Member(openDirectories, dot);
333 (void)Lst_Remove(openDirectories, ln);
336 dot = Dir_AddDir(NULL, ".");
339 Error("Cannot open `.' (%s)", strerror(errno));
344 * We always need to have dot around, so we increment its reference count
345 * to make sure it's not destroyed.
348 Dir_SetPATH(); /* initialize */
352 *-----------------------------------------------------------------------
354 * cleanup things for this module
361 *-----------------------------------------------------------------------
372 dotLast->refCount -= 1;
373 Dir_Destroy(dotLast);
375 Dir_ClearPath(dirSearchPath);
376 Lst_Destroy(dirSearchPath, NULL);
377 Dir_ClearPath(openDirectories);
378 Lst_Destroy(openDirectories, NULL);
379 Hash_DeleteTable(&mtimes);
384 * We want ${.PATH} to indicate the order in which we will actually
385 * search, so we rebuild it after any .PATH: target.
386 * This is the simplest way to deal with the effect of .DOTLAST.
391 LstNode ln; /* a list element */
393 Boolean hasLastDot = FALSE; /* true we should search dot last */
395 Var_Delete(".PATH", VAR_GLOBAL);
397 if (Lst_Open(dirSearchPath) == SUCCESS) {
398 if ((ln = Lst_First(dirSearchPath)) != NULL) {
399 p = (Path *)Lst_Datum(ln);
402 Var_Append(".PATH", dotLast->name, VAR_GLOBAL);
408 Var_Append(".PATH", dot->name, VAR_GLOBAL);
410 Var_Append(".PATH", cur->name, VAR_GLOBAL);
413 while ((ln = Lst_Next(dirSearchPath)) != NULL) {
414 p = (Path *)Lst_Datum(ln);
417 if (p == dot && hasLastDot)
419 Var_Append(".PATH", p->name, VAR_GLOBAL);
424 Var_Append(".PATH", dot->name, VAR_GLOBAL);
426 Var_Append(".PATH", cur->name, VAR_GLOBAL);
428 Lst_Close(dirSearchPath);
433 *-----------------------------------------------------------------------
435 * See if the Path structure describes the same directory as the
436 * given one by comparing their names. Called from Dir_AddDir via
437 * Lst_Find when searching the list of open directories.
444 * 0 if it is the same. Non-zero otherwise
448 *-----------------------------------------------------------------------
451 DirFindName(const void *p, const void *dname)
453 return (strcmp(((const Path *)p)->name, dname));
457 *-----------------------------------------------------------------------
458 * Dir_HasWildcards --
459 * see if the given name has any wildcard characters in it
460 * be careful not to expand unmatching brackets or braces.
461 * XXX: This code is not 100% correct. ([^]] fails etc.)
462 * I really don't think that make(1) should be expanding
463 * patterns, because then you have to set a mechanism for
464 * escaping the expansion!
470 * returns TRUE if the word should be expanded, FALSE otherwise
474 *-----------------------------------------------------------------------
477 Dir_HasWildcards(char *name)
480 int wild = 0, brace = 0, bracket = 0;
482 for (cp = name; *cp; cp++) {
506 return wild && bracket == 0 && brace == 0;
510 *-----------------------------------------------------------------------
512 * Given a pattern and a Path structure, see if any files
513 * match the pattern and add their names to the 'expansions' list if
514 * any do. This is incomplete -- it doesn't take care of patterns like
515 * src / *src / *.c properly (just *.c on any of the directories), but it
519 * pattern Pattern to look for
520 * p Directory to search
521 * expansion Place to store the results
527 * File names are added to the expansions lst. The directory will be
528 * fully hashed when this is done.
529 *-----------------------------------------------------------------------
532 DirMatchFiles(const char *pattern, Path *p, Lst expansions)
534 Hash_Search search; /* Index into the directory's table */
535 Hash_Entry *entry; /* Current entry in the table */
536 Boolean isDot; /* TRUE if the directory being searched is . */
538 isDot = (*p->name == '.' && p->name[1] == '\0');
540 for (entry = Hash_EnumFirst(&p->files, &search);
542 entry = Hash_EnumNext(&search))
545 * See if the file matches the given pattern. Note we follow the UNIX
546 * convention that dot files will only be found if the pattern
547 * begins with a dot (note also that as a side effect of the hashing
548 * scheme, .* won't match . or .. since they aren't hashed).
550 if (Str_Match(entry->name, pattern) &&
551 ((entry->name[0] != '.') ||
552 (pattern[0] == '.')))
554 (void)Lst_AtEnd(expansions,
555 (isDot ? bmake_strdup(entry->name) :
556 str_concat(p->name, entry->name,
564 *-----------------------------------------------------------------------
566 * Expand curly braces like the C shell. Does this recursively.
567 * Note the special case: if after the piece of the curly brace is
568 * done there are no wildcard characters in the result, the result is
569 * placed on the list WITHOUT CHECKING FOR ITS EXISTENCE.
572 * word Entire word to expand
573 * brace First curly brace in it
574 * path Search path to use
575 * expansions Place to store the expansions
581 * The given list is filled with the expansions...
583 *-----------------------------------------------------------------------
586 DirExpandCurly(const char *word, const char *brace, Lst path, Lst expansions)
588 const char *end; /* Character after the closing brace */
589 const char *cp; /* Current position in brace clause */
590 const char *start; /* Start of current piece of brace clause */
591 int bracelevel; /* Number of braces we've seen. If we see a
592 * right brace when this is 0, we've hit the
593 * end of the clause. */
594 char *file; /* Current expansion */
595 int otherLen; /* The length of the other pieces of the
596 * expansion (chars before and after the
597 * clause in 'word') */
598 char *cp2; /* Pointer for checking for wildcards in
599 * expansion before calling Dir_Expand */
604 * Find the end of the brace clause first, being wary of nested brace
607 for (end = start, bracelevel = 0; *end != '\0'; end++) {
610 } else if ((*end == '}') && (bracelevel-- == 0)) {
615 Error("Unterminated {} clause \"%s\"", start);
620 otherLen = brace - word + strlen(end);
622 for (cp = start; cp < end; cp++) {
624 * Find the end of this piece of the clause.
630 } else if ((*cp == '}') && (bracelevel-- <= 0)) {
636 * Allocate room for the combination and install the three pieces.
638 file = bmake_malloc(otherLen + cp - start + 1);
640 strncpy(file, word, brace-word);
643 strncpy(&file[brace-word], start, cp-start);
645 strcpy(&file[(brace-word)+(cp-start)], end);
648 * See if the result has any wildcards in it. If we find one, call
649 * Dir_Expand right away, telling it to place the result on our list
652 for (cp2 = file; *cp2 != '\0'; cp2++) {
658 Dir_Expand(file, path, expansions);
664 * Hit the end w/o finding any wildcards, so stick the expansion
665 * on the end of the list.
667 (void)Lst_AtEnd(expansions, file);
678 *-----------------------------------------------------------------------
680 * Internal expand routine. Passes through the directories in the
681 * path one by one, calling DirMatchFiles for each. NOTE: This still
682 * doesn't handle patterns in directories...
685 * word Word to expand
686 * path Path on which to look
687 * expansions Place to store the result
693 * Things are added to the expansions list.
695 *-----------------------------------------------------------------------
698 DirExpandInt(const char *word, Lst path, Lst expansions)
700 LstNode ln; /* Current node */
701 Path *p; /* Directory in the node */
703 if (Lst_Open(path) == SUCCESS) {
704 while ((ln = Lst_Next(path)) != NULL) {
705 p = (Path *)Lst_Datum(ln);
706 DirMatchFiles(word, p, expansions);
713 *-----------------------------------------------------------------------
715 * Print a word in the list of expansions. Callback for Dir_Expand
716 * when DEBUG(DIR), via Lst_ForEach.
722 * The passed word is printed, followed by a space.
724 *-----------------------------------------------------------------------
727 DirPrintWord(void *word, void *dummy)
729 fprintf(debug_file, "%s ", (char *)word);
731 return(dummy ? 0 : 0);
735 *-----------------------------------------------------------------------
737 * Expand the given word into a list of words by globbing it looking
738 * in the directories on the given search path.
741 * word the word to expand
742 * path the list of directories in which to find the
744 * expansions the list on which to place the results
747 * A list of words consisting of the files which exist along the search
748 * path matching the given pattern.
751 * Directories may be opened. Who knows?
752 *-----------------------------------------------------------------------
755 Dir_Expand(const char *word, Lst path, Lst expansions)
760 fprintf(debug_file, "Expanding \"%s\"... ", word);
763 cp = strchr(word, '{');
765 DirExpandCurly(word, cp, path, expansions);
767 cp = strchr(word, '/');
770 * The thing has a directory component -- find the first wildcard
773 for (cp = word; *cp; cp++) {
774 if (*cp == '?' || *cp == '[' || *cp == '*' || *cp == '{') {
780 * This one will be fun.
782 DirExpandCurly(word, cp, path, expansions);
784 } else if (*cp != '\0') {
786 * Back up to the start of the component
790 while (cp > word && *cp != '/') {
796 * If the glob isn't in the first component, try and find
797 * all the components up to the one with a wildcard.
800 ((char *)UNCONST(cp))[1] = '\0';
801 dirpath = Dir_FindFile(word, path);
802 ((char *)UNCONST(cp))[1] = sc;
804 * dirpath is null if can't find the leading component
805 * XXX: Dir_FindFile won't find internal components.
806 * i.e. if the path contains ../Etc/Object and we're
807 * looking for Etc, it won't be found. Ah well.
808 * Probably not important.
810 if (dirpath != NULL) {
811 char *dp = &dirpath[strlen(dirpath) - 1];
814 path = Lst_Init(FALSE);
815 (void)Dir_AddDir(path, dirpath);
816 DirExpandInt(cp+1, path, expansions);
817 Lst_Destroy(path, NULL);
821 * Start the search from the local directory
823 DirExpandInt(word, path, expansions);
827 * Return the file -- this should never happen.
829 DirExpandInt(word, path, expansions);
833 * First the files in dot
835 DirMatchFiles(word, dot, expansions);
838 * Then the files in every other directory on the path.
840 DirExpandInt(word, path, expansions);
844 Lst_ForEach(expansions, DirPrintWord, NULL);
845 fprintf(debug_file, "\n");
850 *-----------------------------------------------------------------------
852 * Find if the file with the given name exists in the given path.
855 * The path to the file or NULL. This path is guaranteed to be in a
856 * different part of memory than name and so may be safely free'd.
860 *-----------------------------------------------------------------------
863 DirLookup(Path *p, const char *name MAKE_ATTR_UNUSED, const char *cp,
864 Boolean hasSlash MAKE_ATTR_UNUSED)
866 char *file; /* the current filename to check */
869 fprintf(debug_file, " %s ...\n", p->name);
872 if (Hash_FindEntry(&p->files, cp) == NULL)
875 file = str_concat(p->name, cp, STR_ADDSLASH);
877 fprintf(debug_file, " returning %s\n", file);
886 *-----------------------------------------------------------------------
888 * Find if the file with the given name exists in the given path.
891 * The path to the file or NULL. This path is guaranteed to be in a
892 * different part of memory than name and so may be safely free'd.
895 * If the file is found, it is added in the modification times hash
897 *-----------------------------------------------------------------------
900 DirLookupSubdir(Path *p, const char *name)
902 struct stat stb; /* Buffer for stat, if necessary */
903 Hash_Entry *entry; /* Entry for mtimes table */
904 char *file; /* the current filename to check */
907 file = str_concat(p->name, name, STR_ADDSLASH);
910 * Checking in dot -- DON'T put a leading ./ on the thing.
912 file = bmake_strdup(name);
916 fprintf(debug_file, "checking %s ...\n", file);
919 if (stat(file, &stb) == 0) {
920 if (stb.st_mtime == 0)
923 * Save the modification time so if it's needed, we don't have
927 fprintf(debug_file, " Caching %s for %s\n", Targ_FmtTime(stb.st_mtime),
930 entry = Hash_CreateEntry(&mtimes, file, NULL);
931 Hash_SetTimeValue(entry, stb.st_mtime);
940 *-----------------------------------------------------------------------
942 * Find if the file with the given name exists in the given path.
945 * The path to the file, the empty string or NULL. If the file is
946 * the empty string, the search should be terminated.
947 * This path is guaranteed to be in a different part of memory
948 * than name and so may be safely free'd.
952 *-----------------------------------------------------------------------
955 DirLookupAbs(Path *p, const char *name, const char *cp)
957 char *p1; /* pointer into p->name */
958 const char *p2; /* pointer into name */
961 fprintf(debug_file, " %s ...\n", p->name);
965 * If the file has a leading path component and that component
966 * exactly matches the entire name of the current search
967 * directory, we can attempt another cache lookup. And if we don't
968 * have a hit, we can safely assume the file does not exist at all.
970 for (p1 = p->name, p2 = name; *p1 && *p1 == *p2; p1++, p2++) {
973 if (*p1 != '\0' || p2 != cp - 1) {
977 if (Hash_FindEntry(&p->files, cp) == NULL) {
979 fprintf(debug_file, " must be here but isn't -- returning\n");
981 /* Return empty string: terminates search */
982 return bmake_strdup("");
988 fprintf(debug_file, " returning %s\n", name);
990 return (bmake_strdup(name));
994 *-----------------------------------------------------------------------
996 * Find the file given on "." or curdir
999 * The path to the file or NULL. This path is guaranteed to be in a
1000 * different part of memory than name and so may be safely free'd.
1004 *-----------------------------------------------------------------------
1007 DirFindDot(Boolean hasSlash MAKE_ATTR_UNUSED, const char *name, const char *cp)
1010 if (Hash_FindEntry(&dot->files, cp) != NULL) {
1012 fprintf(debug_file, " in '.'\n");
1016 return (bmake_strdup(name));
1019 Hash_FindEntry(&cur->files, cp) != NULL) {
1021 fprintf(debug_file, " in ${.CURDIR} = %s\n", cur->name);
1025 return str_concat(cur->name, cp, STR_ADDSLASH);
1032 *-----------------------------------------------------------------------
1034 * Find the file with the given name along the given search path.
1037 * name the file to find
1038 * path the Lst of directories to search
1041 * The path to the file or NULL. This path is guaranteed to be in a
1042 * different part of memory than name and so may be safely free'd.
1045 * If the file is found in a directory which is not on the path
1046 * already (either 'name' is absolute or it is a relative path
1047 * [ dir1/.../dirn/file ] which exists below one of the directories
1048 * already on the search path), its directory is added to the end
1049 * of the path on the assumption that there will be more files in
1050 * that directory later on. Sometimes this is true. Sometimes not.
1051 *-----------------------------------------------------------------------
1054 Dir_FindFile(const char *name, Lst path)
1056 LstNode ln; /* a list element */
1057 char *file; /* the current filename to check */
1058 Path *p; /* current path member */
1059 const char *cp; /* Terminal name of file */
1060 Boolean hasLastDot = FALSE; /* true we should search dot last */
1061 Boolean hasSlash; /* true if 'name' contains a / */
1062 struct stat stb; /* Buffer for stat, if necessary */
1063 Hash_Entry *entry; /* Entry for mtimes table */
1064 const char *trailing_dot = ".";
1067 * Find the final component of the name and note whether it has a
1068 * slash in it (the name, I mean)
1070 cp = strrchr(name, '/');
1080 fprintf(debug_file, "Searching for %s ...", name);
1083 if (Lst_Open(path) == FAILURE) {
1085 fprintf(debug_file, "couldn't open path, file not found\n");
1091 if ((ln = Lst_First(path)) != NULL) {
1092 p = (Path *)Lst_Datum(ln);
1096 fprintf(debug_file, "[dot last]...");
1100 fprintf(debug_file, "\n");
1104 * If there's no leading directory components or if the leading
1105 * directory component is exactly `./', consult the cached contents
1106 * of each of the directories on the search path.
1108 if (!hasSlash || (cp - name == 2 && *name == '.')) {
1110 * We look through all the directories on the path seeking one which
1111 * contains the final component of the given name. If such a beast
1112 * is found, we concatenate the directory name and the final
1113 * component and return the resulting string. If we don't find any
1114 * such thing, we go on to phase two...
1116 * No matter what, we always look for the file in the current
1117 * directory before anywhere else (unless we found the magic
1118 * DOTLAST path, in which case we search it last) and we *do not*
1119 * add the ./ to it if it exists.
1120 * This is so there are no conflicts between what the user
1121 * specifies (fish.c) and what pmake finds (./fish.c).
1124 (file = DirFindDot(hasSlash, name, cp)) != NULL) {
1129 while ((ln = Lst_Next(path)) != NULL) {
1130 p = (Path *)Lst_Datum(ln);
1133 if ((file = DirLookup(p, name, cp, hasSlash)) != NULL) {
1140 (file = DirFindDot(hasSlash, name, cp)) != NULL) {
1148 * We didn't find the file on any directory in the search path.
1149 * If the name doesn't contain a slash, that means it doesn't exist.
1150 * If it *does* contain a slash, however, there is still hope: it
1151 * could be in a subdirectory of one of the members of the search
1152 * path. (eg. /usr/include and sys/types.h. The above search would
1153 * fail to turn up types.h in /usr/include, but it *is* in
1154 * /usr/include/sys/types.h).
1155 * [ This no longer applies: If we find such a beast, we assume there
1156 * will be more (what else can we assume?) and add all but the last
1157 * component of the resulting name onto the search path (at the
1159 * This phase is only performed if the file is *not* absolute.
1163 fprintf(debug_file, " failed.\n");
1170 /* we were given a trailing "/" */
1174 if (name[0] != '/') {
1175 Boolean checkedDot = FALSE;
1178 fprintf(debug_file, " Trying subdirectories...\n");
1184 if ((file = DirLookupSubdir(dot, name)) != NULL)
1187 if (cur && (file = DirLookupSubdir(cur, name)) != NULL)
1191 (void)Lst_Open(path);
1192 while ((ln = Lst_Next(path)) != NULL) {
1193 p = (Path *)Lst_Datum(ln);
1201 if ((file = DirLookupSubdir(p, name)) != NULL) {
1209 if (dot && !checkedDot) {
1211 if ((file = DirLookupSubdir(dot, name)) != NULL)
1214 if (cur && (file = DirLookupSubdir(cur, name)) != NULL)
1220 * Already checked by the given name, since . was in the path,
1221 * so no point in proceeding...
1224 fprintf(debug_file, " Checked . already, returning NULL\n");
1229 } else { /* name[0] == '/' */
1232 * For absolute names, compare directory path prefix against the
1233 * the directory path of each member on the search path for an exact
1234 * match. If we have an exact match on any member of the search path,
1235 * use the cached contents of that member to lookup the final file
1236 * component. If that lookup fails we can safely assume that the
1237 * file does not exist at all. This is signified by DirLookupAbs()
1238 * returning an empty string.
1241 fprintf(debug_file, " Trying exact path matches...\n");
1244 if (!hasLastDot && cur && (file = DirLookupAbs(cur, name, cp)) != NULL)
1245 return *file?file:NULL;
1247 (void)Lst_Open(path);
1248 while ((ln = Lst_Next(path)) != NULL) {
1249 p = (Path *)Lst_Datum(ln);
1252 if ((file = DirLookupAbs(p, name, cp)) != NULL) {
1254 return *file?file:NULL;
1259 if (hasLastDot && cur && (file = DirLookupAbs(cur, name, cp)) != NULL)
1260 return *file?file:NULL;
1264 * Didn't find it that way, either. Sigh. Phase 3. Add its directory
1265 * onto the search path in any case, just in case, then look for the
1266 * thing in the hash table. If we find it, grand. We return a new
1267 * copy of the name. Otherwise we sadly return a NULL pointer. Sigh.
1268 * Note that if the directory holding the file doesn't exist, this will
1269 * do an extra search of the final directory on the path. Unless something
1270 * weird happens, this search won't succeed and life will be groovy.
1272 * Sigh. We cannot add the directory onto the search path because
1273 * of this amusing case:
1274 * $(INSTALLDIR)/$(FILE): $(FILE)
1276 * $(FILE) exists in $(INSTALLDIR) but not in the current one.
1277 * When searching for $(FILE), we will find it in $(INSTALLDIR)
1278 * b/c we added it here. This is not good...
1281 if (cp == traling_dot) {
1282 cp = strrchr(name, '/');
1286 (void)Dir_AddDir(path, name);
1290 ln = Lst_Last(path);
1294 p = (Path *)Lst_Datum(ln);
1297 if (Hash_FindEntry(&p->files, cp) != NULL) {
1298 return (bmake_strdup(name));
1304 fprintf(debug_file, " Looking for \"%s\" ...\n", name);
1308 entry = Hash_FindEntry(&mtimes, name);
1309 if (entry != NULL) {
1311 fprintf(debug_file, " got it (in mtime cache)\n");
1313 return(bmake_strdup(name));
1314 } else if (stat(name, &stb) == 0) {
1315 if (stb.st_mtime == 0)
1317 entry = Hash_CreateEntry(&mtimes, name, NULL);
1319 fprintf(debug_file, " Caching %s for %s\n", Targ_FmtTime(stb.st_mtime),
1322 Hash_SetTimeValue(entry, stb.st_mtime);
1323 return (bmake_strdup(name));
1326 fprintf(debug_file, " failed. Returning NULL\n");
1335 *-----------------------------------------------------------------------
1336 * Dir_FindHereOrAbove --
1337 * search for a path starting at a given directory and then working
1338 * our way up towards the root.
1341 * here starting directory
1342 * search_path the path we are looking for
1343 * result the result of a successful search is placed here
1344 * rlen the length of the result buffer
1345 * (typically MAXPATHLEN + 1)
1348 * 0 on failure, 1 on success [in which case the found path is put
1349 * in the result buffer].
1352 *-----------------------------------------------------------------------
1355 Dir_FindHereOrAbove(char *here, char *search_path, char *result, int rlen) {
1358 char dirbase[MAXPATHLEN + 1], *db_end;
1359 char try[MAXPATHLEN + 1], *try_end;
1361 /* copy out our starting point */
1362 snprintf(dirbase, sizeof(dirbase), "%s", here);
1363 db_end = dirbase + strlen(dirbase);
1365 /* loop until we determine a result */
1368 /* try and stat(2) it ... */
1369 snprintf(try, sizeof(try), "%s/%s", dirbase, search_path);
1370 if (stat(try, &st) != -1) {
1372 * success! if we found a file, chop off
1373 * the filename so we return a directory.
1375 if ((st.st_mode & S_IFMT) != S_IFDIR) {
1376 try_end = try + strlen(try);
1377 while (try_end > try && *try_end != '/')
1380 *try_end = 0; /* chop! */
1386 snprintf(result, rlen, "%s", try);
1391 * nope, we didn't find it. if we used up dirbase we've
1392 * reached the root and failed.
1394 if (db_end == dirbase)
1395 break; /* failed! */
1398 * truncate dirbase from the end to move up a dir
1400 while (db_end > dirbase && *db_end != '/')
1402 *db_end = 0; /* chop! */
1413 *-----------------------------------------------------------------------
1415 * Find the modification time of the file described by gn along the
1416 * search path dirSearchPath.
1419 * gn the file whose modification time is desired
1422 * The modification time or 0 if it doesn't exist
1425 * The modification time is placed in the node's mtime slot.
1426 * If the node didn't have a path entry before, and Dir_FindFile
1427 * found one for it, the full name is placed in the path slot.
1428 *-----------------------------------------------------------------------
1431 Dir_MTime(GNode *gn, Boolean recheck)
1433 char *fullName; /* the full pathname of name */
1434 struct stat stb; /* buffer for finding the mod time */
1437 if (gn->type & OP_ARCHV) {
1438 return Arch_MTime(gn);
1439 } else if (gn->type & OP_PHONY) {
1442 } else if (gn->path == NULL) {
1443 if (gn->type & OP_NOPATH)
1446 fullName = Dir_FindFile(gn->name, Suff_FindPath(gn));
1447 if (fullName == NULL && gn->flags & FROM_DEPEND &&
1448 !Lst_IsEmpty(gn->iParents)) {
1451 cp = strrchr(gn->name, '/');
1454 * This is an implied source, and it may have moved,
1455 * see if we can find it via the current .PATH
1459 fullName = Dir_FindFile(cp, Suff_FindPath(gn));
1462 * Put the found file in gn->path
1463 * so that we give that to the compiler.
1465 gn->path = bmake_strdup(fullName);
1467 "%s: ignoring stale %s for %s, found %s\n",
1468 progname, makeDependfile, gn->name, fullName);
1473 fprintf(debug_file, "Found '%s' as '%s'\n",
1474 gn->name, fullName ? fullName : "(not found)" );
1477 fullName = gn->path;
1480 if (fullName == NULL) {
1481 fullName = bmake_strdup(gn->name);
1485 entry = Hash_FindEntry(&mtimes, fullName);
1488 if (entry != NULL) {
1490 fprintf(debug_file, "Using cached time %s for %s\n",
1491 Targ_FmtTime(Hash_GetTimeValue(entry)), fullName);
1493 stb.st_mtime = Hash_GetTimeValue(entry);
1494 } else if (stat(fullName, &stb) < 0) {
1495 if (gn->type & OP_MEMBER) {
1496 if (fullName != gn->path)
1498 return Arch_MemMTime(gn);
1503 if (stb.st_mtime == 0) {
1505 * 0 handled specially by the code, if the time is really 0,
1506 * return something else instead
1510 entry = Hash_CreateEntry(&mtimes, fullName, NULL);
1511 Hash_SetTimeValue(entry, stb.st_mtime);
1514 if (fullName && gn->path == NULL) {
1515 gn->path = fullName;
1518 gn->mtime = stb.st_mtime;
1523 *-----------------------------------------------------------------------
1525 * Add the given name to the end of the given path. The order of
1526 * the arguments is backwards so ParseDoDependency can do a
1527 * Lst_ForEach of its list of paths...
1530 * path the path to which the directory should be
1532 * name the name of the directory to add
1538 * A structure is added to the list and the directory is
1540 *-----------------------------------------------------------------------
1543 Dir_AddDir(Lst path, const char *name)
1545 LstNode ln = NULL; /* node in case Path structure is found */
1546 Path *p = NULL; /* pointer to new Path structure */
1547 DIR *d; /* for reading directory */
1548 struct dirent *dp; /* entry in directory */
1550 if (strcmp(name, ".DOTLAST") == 0) {
1551 ln = Lst_Find(path, name, DirFindName);
1553 return (Path *)Lst_Datum(ln);
1555 dotLast->refCount += 1;
1556 (void)Lst_AtFront(path, dotLast);
1561 ln = Lst_Find(openDirectories, name, DirFindName);
1563 p = (Path *)Lst_Datum(ln);
1564 if (path && Lst_Member(path, p) == NULL) {
1566 (void)Lst_AtEnd(path, p);
1570 fprintf(debug_file, "Caching %s ...", name);
1573 if ((d = opendir(name)) != NULL) {
1574 p = bmake_malloc(sizeof(Path));
1575 p->name = bmake_strdup(name);
1578 Hash_InitTable(&p->files, -1);
1580 while ((dp = readdir(d)) != NULL) {
1581 #if defined(sun) && defined(d_ino) /* d_ino is a sunos4 #define for d_fileno */
1583 * The sun directory library doesn't check for a 0 inode
1584 * (0-inode slots just take up space), so we have to do
1587 if (dp->d_fileno == 0) {
1590 #endif /* sun && d_ino */
1591 (void)Hash_CreateEntry(&p->files, dp->d_name, NULL);
1594 (void)Lst_AtEnd(openDirectories, p);
1596 (void)Lst_AtEnd(path, p);
1599 fprintf(debug_file, "done\n");
1606 *-----------------------------------------------------------------------
1608 * Callback function for duplicating a search path via Lst_Duplicate.
1609 * Ups the reference count for the directory.
1612 * Returns the Path it was given.
1615 * The refCount of the path is incremented.
1617 *-----------------------------------------------------------------------
1620 Dir_CopyDir(void *p)
1622 ((Path *)p)->refCount += 1;
1628 *-----------------------------------------------------------------------
1630 * Make a string by taking all the directories in the given search
1631 * path and preceding them by the given flag. Used by the suffix
1632 * module to create variables for compilers based on suffix search
1636 * flag flag which should precede each directory
1637 * path list of directories
1640 * The string mentioned above. Note that there is no space between
1641 * the given flag and each directory. The empty string is returned if
1642 * Things don't go well.
1646 *-----------------------------------------------------------------------
1649 Dir_MakeFlags(const char *flag, Lst path)
1651 char *str; /* the string which will be returned */
1652 char *s1, *s2;/* the current directory preceded by 'flag' */
1653 LstNode ln; /* the node of the current directory */
1654 Path *p; /* the structure describing the current directory */
1656 str = bmake_strdup("");
1658 if (Lst_Open(path) == SUCCESS) {
1659 while ((ln = Lst_Next(path)) != NULL) {
1660 p = (Path *)Lst_Datum(ln);
1661 s2 = str_concat(flag, p->name, 0);
1662 str = str_concat(s1 = str, s2, STR_ADDSPACE);
1673 *-----------------------------------------------------------------------
1675 * Nuke a directory descriptor, if possible. Callback procedure
1676 * for the suffixes module when destroying a search path.
1679 * pp The directory descriptor to nuke
1685 * If no other path references this directory (refCount == 0),
1686 * the Path and all its data are freed.
1688 *-----------------------------------------------------------------------
1691 Dir_Destroy(void *pp)
1693 Path *p = (Path *)pp;
1696 if (p->refCount == 0) {
1699 ln = Lst_Member(openDirectories, p);
1700 (void)Lst_Remove(openDirectories, ln);
1702 Hash_DeleteTable(&p->files);
1709 *-----------------------------------------------------------------------
1711 * Clear out all elements of the given search path. This is different
1712 * from destroying the list, notice.
1715 * path Path to clear
1721 * The path is set to the empty list.
1723 *-----------------------------------------------------------------------
1726 Dir_ClearPath(Lst path)
1729 while (!Lst_IsEmpty(path)) {
1730 p = (Path *)Lst_DeQueue(path);
1737 *-----------------------------------------------------------------------
1739 * Concatenate two paths, adding the second to the end of the first.
1740 * Makes sure to avoid duplicates.
1750 * Reference counts for added dirs are upped.
1752 *-----------------------------------------------------------------------
1755 Dir_Concat(Lst path1, Lst path2)
1760 for (ln = Lst_First(path2); ln != NULL; ln = Lst_Succ(ln)) {
1761 p = (Path *)Lst_Datum(ln);
1762 if (Lst_Member(path1, p) == NULL) {
1764 (void)Lst_AtEnd(path1, p);
1769 /********** DEBUG INFO **********/
1771 Dir_PrintDirectories(void)
1776 fprintf(debug_file, "#*** Directory Cache:\n");
1777 fprintf(debug_file, "# Stats: %d hits %d misses %d near misses %d losers (%d%%)\n",
1778 hits, misses, nearmisses, bigmisses,
1779 (hits+bigmisses+nearmisses ?
1780 hits * 100 / (hits + bigmisses + nearmisses) : 0));
1781 fprintf(debug_file, "# %-20s referenced\thits\n", "directory");
1782 if (Lst_Open(openDirectories) == SUCCESS) {
1783 while ((ln = Lst_Next(openDirectories)) != NULL) {
1784 p = (Path *)Lst_Datum(ln);
1785 fprintf(debug_file, "# %-20s %10d\t%4d\n", p->name, p->refCount, p->hits);
1787 Lst_Close(openDirectories);
1792 DirPrintDir(void *p, void *dummy)
1794 fprintf(debug_file, "%s ", ((Path *)p)->name);
1795 return (dummy ? 0 : 0);
1799 Dir_PrintPath(Lst path)
1801 Lst_ForEach(path, DirPrintDir, NULL);