1 /* $NetBSD: dir.c,v 1.210 2020/11/14 21:29:44 rillig 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
72 /* Directory searching using wildcards and/or normal names.
73 * Used both for source wildcarding in the makefile and for finding
76 * The interface for this module is:
77 * Dir_Init Initialize the module.
79 * Dir_InitCur Set the cur CachedDir.
81 * Dir_InitDot Set the dot CachedDir.
83 * Dir_End Clean up the module.
85 * Dir_SetPATH Set ${.PATH} to reflect state of dirSearchPath.
88 * Returns TRUE if the name given it needs to
89 * be wildcard-expanded.
91 * Dir_Expand Given a pattern and a path, return a Lst of names
92 * which match the pattern on the search path.
94 * Dir_FindFile Searches for a file on a given search path.
95 * If it exists, the entire path is returned.
96 * Otherwise NULL is returned.
99 * Search for a path in the current directory and
100 * then all the directories above it in turn until
101 * the path is found or we reach the root ("/").
104 * Update the modification time and path of a node with
105 * data from the file corresponding to the node.
107 * Dir_AddDir Add a directory to a search path.
109 * Dir_MakeFlags Given a search path and a command flag, create
110 * a string with each of the directories in the path
111 * preceded by the command flag and all of them
112 * separated by a space.
114 * Dir_Destroy Destroy an element of a search path. Frees up all
115 * things that can be freed for the element as long
116 * as the element is no longer referenced by any other
119 * Dir_ClearPath Resets a search path to the empty list.
122 * Dir_PrintDirectories
123 * Print stats about the directory cache.
126 #include <sys/types.h>
127 #include <sys/stat.h>
136 /* "@(#)dir.c 8.2 (Berkeley) 1/2/94" */
137 MAKE_RCSID("$NetBSD: dir.c,v 1.210 2020/11/14 21:29:44 rillig Exp $");
139 #define DIR_DEBUG0(text) DEBUG0(DIR, text)
140 #define DIR_DEBUG1(fmt, arg1) DEBUG1(DIR, fmt, arg1)
141 #define DIR_DEBUG2(fmt, arg1, arg2) DEBUG2(DIR, fmt, arg1, arg2)
143 /* A search path is a list of CachedDir structures. A CachedDir has in it the
144 * name of the directory and the names of all the files in the directory.
145 * This is used to cut down on the number of system calls necessary to find
146 * implicit dependents and their like. Since these searches are made before
147 * any actions are taken, we need not worry about the directory changing due
148 * to creation commands. If this hampers the style of some makefiles, they
151 * All previously-read directories are kept in openDirs, which is checked
152 * first before a directory is opened.
154 * The need for the caching of whole directories is brought about by the
155 * multi-level transformation code in suff.c, which tends to search for far
156 * more files than regular make does. In the initial implementation, the
157 * amount of time spent performing "stat" calls was truly astronomical.
158 * The problem with caching at the start is, of course, that pmake doesn't
159 * then detect changes to these directories during the course of the make.
160 * Three possibilities suggest themselves:
162 * 1) just use stat to test for a file's existence. As mentioned above,
163 * this is very inefficient due to the number of checks engendered by
164 * the multi-level transformation code.
166 * 2) use readdir() and company to search the directories, keeping them
167 * open between checks. I have tried this and while it didn't slow down
168 * the process too much, it could severely affect the amount of
169 * parallelism available as each directory open would take another file
170 * descriptor out of play for handling I/O for another job. Given that
171 * it is only recently (as of 1993 or earlier) that UNIX OS's have taken
172 * to allowing more than 20 or 32 file descriptors for a process, this
173 * doesn't seem acceptable to me.
175 * 3) record the mtime of the directory in the CachedDir structure and
176 * verify the directory hasn't changed since the contents were cached.
177 * This will catch the creation or deletion of files, but not the
178 * updating of files. However, since it is the creation and deletion
179 * that is the problem, this could be a good thing to do. Unfortunately,
180 * if the directory (say ".") were fairly large and changed fairly
181 * frequently, the constant reloading could seriously degrade
182 * performance. It might be good in such cases to keep track of the
183 * number of reloadings and if the number goes over a (small) limit,
184 * resort to using stat in its place.
186 * An additional thing to consider is that pmake is used primarily to create
187 * C programs and until recently (as of 1993 or earlier) pcc-based compilers
188 * refused to allow you to specify where the resulting object file should be
189 * placed. This forced all objects to be created in the current directory.
190 * This isn't meant as a full excuse, just an explanation of some of the
191 * reasons for the caching used here.
193 * One more note: the location of a target's file is only performed on the
194 * downward traversal of the graph and then only for terminal nodes in the
195 * graph. This could be construed as wrong in some cases, but prevents
196 * inadvertent modification of files when the "installed" directory for a
197 * file is provided in the search path.
199 * Another data structure maintained by this module is an mtime cache used
200 * when the searching of cached directories fails to find a file. In the past,
201 * Dir_FindFile would simply perform an access() call in such a case to
202 * determine if the file could be found using just the name given. When this
203 * hit, however, all that was gained was the knowledge that the file existed.
204 * Given that an access() is essentially a stat() without the copyout() call,
205 * and that the same filesystem overhead would have to be incurred in
206 * Dir_MTime, it made sense to replace the access() with a stat() and record
207 * the mtime in a cache for when Dir_UpdateMTime was actually called.
210 typedef List CachedDirList;
211 typedef ListNode CachedDirListNode;
213 typedef ListNode SearchPathNode;
215 SearchPath *dirSearchPath; /* main search path */
217 /* A list of cached directories, with fast lookup by directory name. */
218 typedef struct OpenDirs {
220 HashTable /* of CachedDirListNode */ table;
224 OpenDirs_Init(OpenDirs *odirs)
226 odirs->list = Lst_New();
227 HashTable_Init(&odirs->table);
232 OpenDirs_Done(OpenDirs *odirs)
234 CachedDirListNode *ln = odirs->list->first;
236 CachedDirListNode *next = ln->next;
237 CachedDir *dir = ln->datum;
238 Dir_Destroy(dir); /* removes the dir from odirs->list */
241 Lst_Free(odirs->list);
242 HashTable_Done(&odirs->table);
247 OpenDirs_Find(OpenDirs *odirs, const char *name)
249 CachedDirListNode *ln = HashTable_FindValue(&odirs->table, name);
250 return ln != NULL ? ln->datum : NULL;
254 OpenDirs_Add(OpenDirs *odirs, CachedDir *cdir)
256 if (HashTable_FindEntry(&odirs->table, cdir->name) != NULL)
258 Lst_Append(odirs->list, cdir);
259 HashTable_Set(&odirs->table, cdir->name, odirs->list->last);
263 OpenDirs_Remove(OpenDirs *odirs, const char *name)
265 HashEntry *he = HashTable_FindEntry(&odirs->table, name);
266 CachedDirListNode *ln;
269 ln = HashEntry_Get(he);
270 HashTable_DeleteEntry(&odirs->table, he);
271 Lst_Remove(odirs->list, ln);
274 static OpenDirs openDirs; /* all cached directories */
277 * Variables for gathering statistics on the efficiency of the caching
280 static int hits; /* Found in directory cache */
281 static int misses; /* Sad, but not evil misses */
282 static int nearmisses; /* Found under search path */
283 static int bigmisses; /* Sought by itself */
285 static CachedDir *dot; /* contents of current directory */
286 static CachedDir *cur; /* contents of current directory, if not dot */
287 static CachedDir *dotLast; /* a fake path entry indicating we need to
290 /* Results of doing a last-resort stat in Dir_FindFile -- if we have to go to
291 * the system to find the file, we might as well have its mtime on record.
293 * XXX: If this is done way early, there's a chance other rules will have
294 * already updated the file, in which case we'll update it again. Generally,
295 * there won't be two rules to update a single file, so this should be ok,
297 static HashTable mtimes;
299 static HashTable lmtimes; /* same as mtimes but for lstat */
301 typedef enum CachedStatsFlags {
303 CST_LSTAT = 1 << 0, /* call lstat(2) instead of stat(2) */
304 CST_UPDATE = 1 << 1 /* ignore existing cached entry */
307 /* Returns 0 and the result of stat(2) or lstat(2) in *out_cst,
310 cached_stats(const char *pathname, struct cached_stat *out_cst,
311 CachedStatsFlags flags)
313 HashTable *tbl = flags & CST_LSTAT ? &lmtimes : &mtimes;
315 struct cached_stat *cst;
318 if (pathname == NULL || pathname[0] == '\0')
319 return -1; /* This can happen in meta mode. */
321 cst = HashTable_FindValue(tbl, pathname);
322 if (cst != NULL && !(flags & CST_UPDATE)) {
324 DIR_DEBUG2("Using cached time %s for %s\n",
325 Targ_FmtTime(cst->cst_mtime), pathname);
329 rc = (flags & CST_LSTAT ? lstat : stat)(pathname, &sys_st);
331 return -1; /* don't cache negative lookups */
333 if (sys_st.st_mtime == 0)
334 sys_st.st_mtime = 1; /* avoid confusion with missing file */
337 cst = bmake_malloc(sizeof *cst);
338 HashTable_Set(tbl, pathname, cst);
341 cst->cst_mtime = sys_st.st_mtime;
342 cst->cst_mode = sys_st.st_mode;
345 DIR_DEBUG2(" Caching %s for %s\n",
346 Targ_FmtTime(sys_st.st_mtime), pathname);
352 cached_stat(const char *pathname, struct cached_stat *cst)
354 return cached_stats(pathname, cst, CST_NONE);
358 cached_lstat(const char *pathname, struct cached_stat *cst)
360 return cached_stats(pathname, cst, CST_LSTAT);
363 /* Initialize the directories module. */
367 dirSearchPath = Lst_New();
368 OpenDirs_Init(&openDirs);
369 HashTable_Init(&mtimes);
370 HashTable_Init(&lmtimes);
374 Dir_InitDir(const char *cdname)
378 dotLast = bmake_malloc(sizeof *dotLast);
379 dotLast->refCount = 1;
381 dotLast->name = bmake_strdup(".DOTLAST");
382 HashTable_Init(&dotLast->files);
386 * Called by Dir_InitDir and whenever .CURDIR is assigned to.
389 Dir_InitCur(const char *cdname)
397 * Our build directory is not the same as our source directory.
398 * Keep this one around too.
400 dir = Dir_AddDir(NULL, cdname);
404 /* XXX: Reference counting is wrong here.
405 * If this function is called repeatedly with the same directory name,
406 * its reference count increases each time even though the number of
407 * actual references stays the same. */
410 if (cur != NULL && cur != dir) {
412 * We've been here before, clean up.
420 /* (Re)initialize "dot" (current/object directory) path hash.
421 * Some directories may be opened. */
426 /* Remove old entry from openDirs, but do not destroy. */
427 OpenDirs_Remove(&openDirs, dot->name);
430 dot = Dir_AddDir(NULL, ".");
433 Error("Cannot open `.' (%s)", strerror(errno));
438 * We always need to have dot around, so we increment its reference count
439 * to make sure it's not destroyed.
442 Dir_SetPATH(); /* initialize */
445 /* Clean up the directories module. */
456 Dir_Destroy(dotLast);
458 Dir_ClearPath(dirSearchPath);
459 Lst_Free(dirSearchPath);
460 OpenDirs_Done(&openDirs);
461 HashTable_Done(&mtimes);
466 * We want ${.PATH} to indicate the order in which we will actually
467 * search, so we rebuild it after any .PATH: target.
468 * This is the simplest way to deal with the effect of .DOTLAST.
473 CachedDirListNode *ln;
474 Boolean hasLastDot = FALSE; /* true if we should search dot last */
476 Var_Delete(".PATH", VAR_GLOBAL);
478 if ((ln = dirSearchPath->first) != NULL) {
479 CachedDir *dir = ln->datum;
480 if (dir == dotLast) {
482 Var_Append(".PATH", dotLast->name, VAR_GLOBAL);
488 Var_Append(".PATH", dot->name, VAR_GLOBAL);
490 Var_Append(".PATH", cur->name, VAR_GLOBAL);
493 for (ln = dirSearchPath->first; ln != NULL; ln = ln->next) {
494 CachedDir *dir = ln->datum;
497 if (dir == dot && hasLastDot)
499 Var_Append(".PATH", dir->name, VAR_GLOBAL);
504 Var_Append(".PATH", dot->name, VAR_GLOBAL);
506 Var_Append(".PATH", cur->name, VAR_GLOBAL);
510 /* See if the given name has any wildcard characters in it and all braces and
511 * brackets are properly balanced.
513 * XXX: This code is not 100% correct ([^]] fails etc.). I really don't think
514 * that make(1) should be expanding patterns, because then you have to set a
515 * mechanism for escaping the expansion!
517 * Return TRUE if the word should be expanded, FALSE otherwise.
520 Dir_HasWildcards(const char *name)
523 Boolean wild = FALSE;
524 int braces = 0, brackets = 0;
526 for (p = name; *p != '\0'; p++) {
550 return wild && brackets == 0 && braces == 0;
553 /* See if any files match the pattern and add their names to the 'expansions'
556 * This is incomplete -- wildcards are only expanded in the final path
557 * component, but not in directories like src/lib*c/file*.c, but it
558 * will do for now (now being 1993 until at least 2020). To expand these,
559 * use the ':sh' variable modifier such as in ${:!echo src/lib*c/file*.c!}.
562 * pattern Pattern to look for
563 * dir Directory to search
564 * expansion Place to store the results
567 DirMatchFiles(const char *pattern, CachedDir *dir, StringList *expansions)
569 const char *dirName = dir->name;
570 Boolean isDot = dirName[0] == '.' && dirName[1] == '\0';
573 /* XXX: Iterating over all hash entries is inefficient. If the pattern
574 * is a plain string without any wildcards, a direct lookup is faster. */
576 HashIter_Init(&hi, &dir->files);
577 while (HashIter_Next(&hi) != NULL) {
578 const char *base = hi.entry->key;
580 if (!Str_Match(base, pattern))
584 * Follow the UNIX convention that dot files are only found if the
585 * pattern begins with a dot. The pattern '.*' does not match '.' or
586 * '..' since these are not included in the directory cache.
588 * This means that the pattern '[a-z.]*' does not find '.file', which
589 * is consistent with bash, NetBSD sh and csh.
591 if (base[0] == '.' && pattern[0] != '.')
595 char *fullName = isDot
597 : str_concat3(dirName, "/", base);
598 Lst_Append(expansions, fullName);
603 /* Find the next closing brace in the string, taking nested braces into
606 closing_brace(const char *p)
610 if (*p == '}' && nest == 0)
621 /* Find the next closing brace or comma in the string, taking nested braces
624 separator_comma(const char *p)
628 if ((*p == '}' || *p == ',') && nest == 0)
640 contains_wildcard(const char *p)
642 for (; *p != '\0'; p++) {
655 concat3(const char *a, size_t a_len, const char *b, size_t b_len,
656 const char *c, size_t c_len)
658 size_t s_len = a_len + b_len + c_len;
659 char *s = bmake_malloc(s_len + 1);
661 memcpy(s + a_len, b, b_len);
662 memcpy(s + a_len + b_len, c, c_len);
667 /* Expand curly braces like the C shell. Brace expansion by itself is purely
668 * textual, the expansions are not looked up in the file system. But if an
669 * expanded word contains wildcard characters, it is expanded further,
670 * matching only the actually existing files.
672 * Example: "{a{b,c}}" expands to "ab" and "ac".
673 * Example: "{a}" expands to "a".
674 * Example: "{a,*.c}" expands to "a" and all "*.c" files that exist.
677 * word Entire word to expand
678 * brace First curly brace in it
679 * path Search path to use
680 * expansions Place to store the expansions
683 DirExpandCurly(const char *word, const char *brace, SearchPath *path,
684 StringList *expansions)
686 const char *prefix, *middle, *piece, *middle_end, *suffix;
687 size_t prefix_len, suffix_len;
689 /* Split the word into prefix '{' middle '}' suffix. */
692 middle_end = closing_brace(middle);
693 if (*middle_end == '\0') {
694 Error("Unterminated {} clause \"%s\"", middle);
699 prefix_len = (size_t)(brace - prefix);
700 suffix = middle_end + 1;
701 suffix_len = strlen(suffix);
703 /* Split the middle into pieces, separated by commas. */
706 while (piece < middle_end + 1) {
707 const char *piece_end = separator_comma(piece);
708 size_t piece_len = (size_t)(piece_end - piece);
710 char *file = concat3(prefix, prefix_len, piece, piece_len,
713 if (contains_wildcard(file)) {
714 Dir_Expand(file, path, expansions);
717 Lst_Append(expansions, file);
720 piece = piece_end + 1; /* skip over the comma or closing brace */
725 /* Expand the word in each of the directories from the path. */
727 DirExpandPath(const char *word, SearchPath *path, StringList *expansions)
730 for (ln = path->first; ln != NULL; ln = ln->next) {
731 CachedDir *dir = ln->datum;
732 DirMatchFiles(word, dir, expansions);
737 PrintExpansions(StringList *expansions)
739 const char *sep = "";
741 for (ln = expansions->first; ln != NULL; ln = ln->next) {
742 const char *word = ln->datum;
743 debug_printf("%s%s", sep, word);
749 /* Expand the given word into a list of words by globbing it, looking in the
750 * directories on the given search path.
753 * word the word to expand
754 * path the directories in which to find the files
755 * expansions the list on which to place the results
758 Dir_Expand(const char *word, SearchPath *path, StringList *expansions)
762 assert(path != NULL);
763 assert(expansions != NULL);
765 DIR_DEBUG1("Expanding \"%s\"... ", word);
767 cp = strchr(word, '{');
769 DirExpandCurly(word, cp, path, expansions);
771 cp = strchr(word, '/');
774 * The thing has a directory component -- find the first wildcard
777 for (cp = word; *cp; cp++) {
778 if (*cp == '?' || *cp == '[' || *cp == '*') {
785 * Back up to the start of the component
787 while (cp > word && *cp != '/') {
791 char *prefix = bmake_strsedup(word, cp + 1);
793 * If the glob isn't in the first component, try and find
794 * all the components up to the one with a wildcard.
796 char *dirpath = Dir_FindFile(prefix, path);
799 * dirpath is null if can't find the leading component
800 * XXX: Dir_FindFile won't find internal components.
801 * i.e. if the path contains ../Etc/Object and we're
802 * looking for Etc, it won't be found. Ah well.
803 * Probably not important.
805 if (dirpath != NULL) {
806 char *dp = &dirpath[strlen(dirpath) - 1];
810 (void)Dir_AddDir(path, dirpath);
811 DirExpandPath(cp + 1, path, expansions);
816 * Start the search from the local directory
818 DirExpandPath(word, path, expansions);
822 * Return the file -- this should never happen.
824 DirExpandPath(word, path, expansions);
828 * First the files in dot
830 DirMatchFiles(word, dot, expansions);
833 * Then the files in every other directory on the path.
835 DirExpandPath(word, path, expansions);
839 PrintExpansions(expansions);
842 /* Find if the file with the given name exists in the given path.
843 * Return the freshly allocated path to the file, or NULL. */
845 DirLookup(CachedDir *dir, const char *base)
847 char *file; /* the current filename to check */
849 DIR_DEBUG1(" %s ...\n", dir->name);
851 if (HashTable_FindEntry(&dir->files, base) == NULL)
854 file = str_concat3(dir->name, "/", base);
855 DIR_DEBUG1(" returning %s\n", file);
862 /* Find if the file with the given name exists in the given directory.
863 * Return the freshly allocated path to the file, or NULL. */
865 DirLookupSubdir(CachedDir *dir, const char *name)
867 struct cached_stat cst;
868 char *file = dir == dot ? bmake_strdup(name)
869 : str_concat3(dir->name, "/", name);
871 DIR_DEBUG1("checking %s ...\n", file);
873 if (cached_stat(file, &cst) == 0) {
881 /* Find if the file with the given name exists in the given path.
882 * Return the freshly allocated path to the file, the empty string, or NULL.
883 * Returning the empty string means that the search should be terminated.
886 DirLookupAbs(CachedDir *dir, const char *name, const char *cp)
888 const char *dnp; /* pointer into dir->name */
889 const char *np; /* pointer into name */
891 DIR_DEBUG1(" %s ...\n", dir->name);
894 * If the file has a leading path component and that component
895 * exactly matches the entire name of the current search
896 * directory, we can attempt another cache lookup. And if we don't
897 * have a hit, we can safely assume the file does not exist at all.
899 for (dnp = dir->name, np = name; *dnp != '\0' && *dnp == *np; dnp++, np++)
901 if (*dnp != '\0' || np != cp - 1)
904 if (HashTable_FindEntry(&dir->files, cp) == NULL) {
905 DIR_DEBUG0(" must be here but isn't -- returning\n");
906 return bmake_strdup(""); /* to terminate the search */
911 DIR_DEBUG1(" returning %s\n", name);
912 return bmake_strdup(name);
915 /* Find the file given on "." or curdir.
916 * Return the freshly allocated path to the file, or NULL. */
918 DirFindDot(const char *name, const char *base)
921 if (HashTable_FindEntry(&dot->files, base) != NULL) {
922 DIR_DEBUG0(" in '.'\n");
925 return bmake_strdup(name);
928 if (cur != NULL && HashTable_FindEntry(&cur->files, base) != NULL) {
929 DIR_DEBUG1(" in ${.CURDIR} = %s\n", cur->name);
932 return str_concat3(cur->name, "/", base);
938 /* Find the file with the given name along the given search path.
940 * If the file is found in a directory that is not on the path
941 * already (either 'name' is absolute or it is a relative path
942 * [ dir1/.../dirn/file ] which exists below one of the directories
943 * already on the search path), its directory is added to the end
944 * of the path, on the assumption that there will be more files in
945 * that directory later on. Sometimes this is true. Sometimes not.
948 * name the file to find
949 * path the directories to search, or NULL
952 * The freshly allocated path to the file, or NULL.
955 Dir_FindFile(const char *name, SearchPath *path)
958 char *file; /* the current filename to check */
959 const char *base; /* Terminal name of file */
960 Boolean hasLastDot = FALSE; /* true if we should search dot last */
961 Boolean hasSlash; /* true if 'name' contains a / */
962 struct cached_stat cst; /* Buffer for stat, if necessary */
963 const char *trailing_dot = ".";
966 * Find the final component of the name and note whether it has a
967 * slash in it (the name, I mean)
969 base = strrchr(name, '/');
978 DIR_DEBUG1("Searching for %s ...", name);
981 DIR_DEBUG0("couldn't open path, file not found\n");
986 if ((ln = path->first) != NULL) {
987 CachedDir *dir = ln->datum;
988 if (dir == dotLast) {
990 DIR_DEBUG0("[dot last]...");
996 * If there's no leading directory components or if the leading
997 * directory component is exactly `./', consult the cached contents
998 * of each of the directories on the search path.
1000 if (!hasSlash || (base - name == 2 && *name == '.')) {
1002 * We look through all the directories on the path seeking one which
1003 * contains the final component of the given name. If such a beast
1004 * is found, we concatenate the directory name and the final
1005 * component and return the resulting string. If we don't find any
1006 * such thing, we go on to phase two...
1008 * No matter what, we always look for the file in the current
1009 * directory before anywhere else (unless we found the magic
1010 * DOTLAST path, in which case we search it last) and we *do not*
1011 * add the ./ to it if it exists.
1012 * This is so there are no conflicts between what the user
1013 * specifies (fish.c) and what pmake finds (./fish.c).
1015 if (!hasLastDot && (file = DirFindDot(name, base)) != NULL)
1018 for (; ln != NULL; ln = ln->next) {
1019 CachedDir *dir = ln->datum;
1022 if ((file = DirLookup(dir, base)) != NULL)
1026 if (hasLastDot && (file = DirFindDot(name, base)) != NULL)
1031 * We didn't find the file on any directory in the search path.
1032 * If the name doesn't contain a slash, that means it doesn't exist.
1033 * If it *does* contain a slash, however, there is still hope: it
1034 * could be in a subdirectory of one of the members of the search
1035 * path. (eg. /usr/include and sys/types.h. The above search would
1036 * fail to turn up types.h in /usr/include, but it *is* in
1037 * /usr/include/sys/types.h).
1038 * [ This no longer applies: If we find such a beast, we assume there
1039 * will be more (what else can we assume?) and add all but the last
1040 * component of the resulting name onto the search path (at the
1042 * This phase is only performed if the file is *not* absolute.
1045 DIR_DEBUG0(" failed.\n");
1050 if (*base == '\0') {
1051 /* we were given a trailing "/" */
1052 base = trailing_dot;
1055 if (name[0] != '/') {
1056 Boolean checkedDot = FALSE;
1058 DIR_DEBUG0(" Trying subdirectories...\n");
1063 if ((file = DirLookupSubdir(dot, name)) != NULL)
1066 if (cur && (file = DirLookupSubdir(cur, name)) != NULL)
1070 for (ln = path->first; ln != NULL; ln = ln->next) {
1071 CachedDir *dir = ln->datum;
1079 if ((file = DirLookupSubdir(dir, name)) != NULL)
1084 if (dot && !checkedDot) {
1086 if ((file = DirLookupSubdir(dot, name)) != NULL)
1089 if (cur && (file = DirLookupSubdir(cur, name)) != NULL)
1095 * Already checked by the given name, since . was in the path,
1096 * so no point in proceeding...
1098 DIR_DEBUG0(" Checked . already, returning NULL\n");
1102 } else { /* name[0] == '/' */
1105 * For absolute names, compare directory path prefix against the
1106 * the directory path of each member on the search path for an exact
1107 * match. If we have an exact match on any member of the search path,
1108 * use the cached contents of that member to lookup the final file
1109 * component. If that lookup fails we can safely assume that the
1110 * file does not exist at all. This is signified by DirLookupAbs()
1111 * returning an empty string.
1113 DIR_DEBUG0(" Trying exact path matches...\n");
1115 if (!hasLastDot && cur &&
1116 ((file = DirLookupAbs(cur, name, base)) != NULL)) {
1117 if (file[0] == '\0') {
1124 for (ln = path->first; ln != NULL; ln = ln->next) {
1125 CachedDir *dir = ln->datum;
1128 if ((file = DirLookupAbs(dir, name, base)) != NULL) {
1129 if (file[0] == '\0') {
1137 if (hasLastDot && cur &&
1138 ((file = DirLookupAbs(cur, name, base)) != NULL)) {
1139 if (file[0] == '\0') {
1148 * Didn't find it that way, either. Sigh. Phase 3. Add its directory
1149 * onto the search path in any case, just in case, then look for the
1150 * thing in the hash table. If we find it, grand. We return a new
1151 * copy of the name. Otherwise we sadly return a NULL pointer. Sigh.
1152 * Note that if the directory holding the file doesn't exist, this will
1153 * do an extra search of the final directory on the path. Unless something
1154 * weird happens, this search won't succeed and life will be groovy.
1156 * Sigh. We cannot add the directory onto the search path because
1157 * of this amusing case:
1158 * $(INSTALLDIR)/$(FILE): $(FILE)
1160 * $(FILE) exists in $(INSTALLDIR) but not in the current one.
1161 * When searching for $(FILE), we will find it in $(INSTALLDIR)
1162 * b/c we added it here. This is not good...
1165 if (base == trailing_dot) {
1166 base = strrchr(name, '/');
1170 (void)Dir_AddDir(path, name);
1174 ln = Lst_Last(path);
1178 dir = LstNode_Datum(ln);
1181 if (Hash_FindEntry(&dir->files, base) != NULL) {
1182 return bmake_strdup(name);
1187 DIR_DEBUG1(" Looking for \"%s\" ...\n", name);
1190 if (cached_stat(name, &cst) == 0) {
1191 return bmake_strdup(name);
1194 DIR_DEBUG0(" failed. Returning NULL\n");
1200 /* Search for a path starting at a given directory and then working our way
1201 * up towards the root.
1204 * here starting directory
1205 * search_path the relative path we are looking for
1208 * The found path, or NULL.
1211 Dir_FindHereOrAbove(const char *here, const char *search_path)
1213 struct cached_stat cst;
1214 char *dirbase, *dirbase_end;
1215 char *try, *try_end;
1217 /* copy out our starting point */
1218 dirbase = bmake_strdup(here);
1219 dirbase_end = dirbase + strlen(dirbase);
1221 /* loop until we determine a result */
1224 /* try and stat(2) it ... */
1225 try = str_concat3(dirbase, "/", search_path);
1226 if (cached_stat(try, &cst) != -1) {
1228 * success! if we found a file, chop off
1229 * the filename so we return a directory.
1231 if ((cst.cst_mode & S_IFMT) != S_IFDIR) {
1232 try_end = try + strlen(try);
1233 while (try_end > try && *try_end != '/')
1236 *try_end = '\0'; /* chop! */
1245 * nope, we didn't find it. if we used up dirbase we've
1246 * reached the root and failed.
1248 if (dirbase_end == dirbase)
1249 break; /* failed! */
1252 * truncate dirbase from the end to move up a dir
1254 while (dirbase_end > dirbase && *dirbase_end != '/')
1256 *dirbase_end = '\0'; /* chop! */
1263 /* Search gn along dirSearchPath and store its modification time in gn->mtime.
1264 * If no file is found, store 0 instead.
1266 * The found file is stored in gn->path, unless the node already had a path. */
1268 Dir_UpdateMTime(GNode *gn, Boolean recheck)
1271 struct cached_stat cst;
1273 if (gn->type & OP_ARCHV) {
1274 Arch_UpdateMTime(gn);
1278 if (gn->type & OP_PHONY) {
1283 if (gn->path == NULL) {
1284 if (gn->type & OP_NOPATH)
1287 fullName = Dir_FindFile(gn->name, Suff_FindPath(gn));
1288 if (fullName == NULL && gn->flags & FROM_DEPEND &&
1289 !Lst_IsEmpty(gn->implicitParents)) {
1292 cp = strrchr(gn->name, '/');
1295 * This is an implied source, and it may have moved,
1296 * see if we can find it via the current .PATH
1300 fullName = Dir_FindFile(cp, Suff_FindPath(gn));
1303 * Put the found file in gn->path
1304 * so that we give that to the compiler.
1306 gn->path = bmake_strdup(fullName);
1307 if (!Job_RunTarget(".STALE", gn->fname))
1309 "%s: %s, %d: ignoring stale %s for %s, "
1310 "found %s\n", progname, gn->fname,
1312 makeDependfile, gn->name, fullName);
1316 DIR_DEBUG2("Found '%s' as '%s'\n",
1317 gn->name, fullName ? fullName : "(not found)");
1320 fullName = gn->path;
1323 if (fullName == NULL)
1324 fullName = bmake_strdup(gn->name);
1326 if (cached_stats(fullName, &cst, recheck ? CST_UPDATE : CST_NONE) < 0) {
1327 if (gn->type & OP_MEMBER) {
1328 if (fullName != gn->path)
1330 Arch_UpdateMemberMTime(gn);
1337 if (fullName != NULL && gn->path == NULL)
1338 gn->path = fullName;
1340 gn->mtime = cst.cst_mtime;
1343 /* Read the list of filenames in the directory and store the result
1344 * in openDirectories.
1346 * If a path is given, append the directory to that path.
1349 * path The path to which the directory should be
1350 * added, or NULL to only add the directory to
1352 * name The name of the directory to add.
1353 * The name is not normalized in any way.
1356 Dir_AddDir(SearchPath *path, const char *name)
1358 CachedDir *dir = NULL; /* the added directory */
1362 if (path != NULL && strcmp(name, ".DOTLAST") == 0) {
1365 /* XXX: Linear search gets slow with thousands of entries. */
1366 for (ln = path->first; ln != NULL; ln = ln->next) {
1367 CachedDir *pathDir = ln->datum;
1368 if (strcmp(pathDir->name, name) == 0)
1372 dotLast->refCount++;
1373 Lst_Prepend(path, dotLast);
1377 dir = OpenDirs_Find(&openDirs, name);
1379 if (Lst_FindDatum(path, dir) == NULL) {
1381 Lst_Append(path, dir);
1386 DIR_DEBUG1("Caching %s ...", name);
1388 if ((d = opendir(name)) != NULL) {
1389 dir = bmake_malloc(sizeof *dir);
1390 dir->name = bmake_strdup(name);
1393 HashTable_Init(&dir->files);
1395 while ((dp = readdir(d)) != NULL) {
1396 #if defined(sun) && defined(d_ino) /* d_ino is a sunos4 #define for d_fileno */
1398 * The sun directory library doesn't check for a 0 inode
1399 * (0-inode slots just take up space), so we have to do
1402 if (dp->d_fileno == 0) {
1405 #endif /* sun && d_ino */
1406 (void)HashTable_CreateEntry(&dir->files, dp->d_name, NULL);
1409 OpenDirs_Add(&openDirs, dir);
1411 Lst_Append(path, dir);
1413 DIR_DEBUG0("done\n");
1417 /* Return a copy of dirSearchPath, incrementing the reference counts for
1418 * the contained directories. */
1420 Dir_CopyDirSearchPath(void)
1422 SearchPath *path = Lst_New();
1424 for (ln = dirSearchPath->first; ln != NULL; ln = ln->next) {
1425 CachedDir *dir = ln->datum;
1427 Lst_Append(path, dir);
1433 *-----------------------------------------------------------------------
1435 * Make a string by taking all the directories in the given search
1436 * path and preceding them by the given flag. Used by the suffix
1437 * module to create variables for compilers based on suffix search
1441 * flag flag which should precede each directory
1442 * path list of directories
1445 * The string mentioned above. Note that there is no space between
1446 * the given flag and each directory. The empty string is returned if
1447 * Things don't go well.
1451 *-----------------------------------------------------------------------
1454 Dir_MakeFlags(const char *flag, SearchPath *path)
1462 for (ln = path->first; ln != NULL; ln = ln->next) {
1463 CachedDir *dir = ln->datum;
1464 Buf_AddStr(&buf, " ");
1465 Buf_AddStr(&buf, flag);
1466 Buf_AddStr(&buf, dir->name);
1470 return Buf_Destroy(&buf, FALSE);
1473 /* Nuke a directory descriptor, if possible. Callback procedure for the
1474 * suffixes module when destroying a search path.
1477 * dirp The directory descriptor to nuke
1480 Dir_Destroy(void *dirp)
1482 CachedDir *dir = dirp;
1485 if (dir->refCount == 0) {
1486 OpenDirs_Remove(&openDirs, dir->name);
1488 HashTable_Done(&dir->files);
1494 /* Clear out all elements from the given search path.
1495 * The path is set to the empty list but is not destroyed. */
1497 Dir_ClearPath(SearchPath *path)
1499 while (!Lst_IsEmpty(path)) {
1500 CachedDir *dir = Lst_Dequeue(path);
1506 /* Concatenate two paths, adding the second to the end of the first,
1507 * skipping duplicates. */
1509 Dir_Concat(SearchPath *dst, SearchPath *src)
1513 for (ln = src->first; ln != NULL; ln = ln->next) {
1514 CachedDir *dir = ln->datum;
1515 if (Lst_FindDatum(dst, dir) == NULL) {
1517 Lst_Append(dst, dir);
1523 percentage(int num, int den)
1525 return den != 0 ? num * 100 / den : 0;
1528 /********** DEBUG INFO **********/
1530 Dir_PrintDirectories(void)
1532 CachedDirListNode *ln;
1534 debug_printf("#*** Directory Cache:\n");
1535 debug_printf("# Stats: %d hits %d misses %d near misses %d losers (%d%%)\n",
1536 hits, misses, nearmisses, bigmisses,
1537 percentage(hits, hits + bigmisses + nearmisses));
1538 debug_printf("# %-20s referenced\thits\n", "directory");
1540 for (ln = openDirs.list->first; ln != NULL; ln = ln->next) {
1541 CachedDir *dir = ln->datum;
1542 debug_printf("# %-20s %10d\t%4d\n", dir->name, dir->refCount,
1548 Dir_PrintPath(SearchPath *path)
1550 SearchPathNode *node;
1551 for (node = path->first; node != NULL; node = node->next) {
1552 const CachedDir *dir = node->datum;
1553 debug_printf("%s ", dir->name);