1 /* $NetBSD: dir.c,v 1.193 2020/10/31 17:39:20 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 ("/").
103 * Dir_MTime Return the modification time of a node. The file
104 * is searched for along the default search path.
105 * The path and mtime fields of the node are filled in.
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.193 2020/10/31 17:39:20 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 that UNIX OS's have taken to allowing more than
172 * 20 or 32 file descriptors for a process, this doesn't seem acceptable
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 pcc-based compilers refused to allow you to
188 * specify where the resulting object file should be placed. This forced all
189 * objects to be created in the current directory. This isn't meant as a full
190 * excuse, just an explanation of some of the reasons for the caching used
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_MTime 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 HashEntry *he = HashTable_FindEntry(&odirs->table, cdir->name);
259 he = HashTable_CreateEntry(&odirs->table, cdir->name, NULL);
260 Lst_Append(odirs->list, cdir);
261 HashEntry_Set(he, odirs->list->last);
265 OpenDirs_Remove(OpenDirs *odirs, const char *name)
267 HashEntry *he = HashTable_FindEntry(&odirs->table, name);
268 CachedDirListNode *ln;
271 ln = HashEntry_Get(he);
272 HashTable_DeleteEntry(&odirs->table, he);
273 Lst_Remove(odirs->list, ln);
276 static OpenDirs openDirs; /* the list of all open directories */
279 * Variables for gathering statistics on the efficiency of the cashing
282 static int hits; /* Found in directory cache */
283 static int misses; /* Sad, but not evil misses */
284 static int nearmisses; /* Found under search path */
285 static int bigmisses; /* Sought by itself */
287 static CachedDir *dot; /* contents of current directory */
288 static CachedDir *cur; /* contents of current directory, if not dot */
289 static CachedDir *dotLast; /* a fake path entry indicating we need to
292 /* Results of doing a last-resort stat in Dir_FindFile -- if we have to go to
293 * the system to find the file, we might as well have its mtime on record.
295 * XXX: If this is done way early, there's a chance other rules will have
296 * already updated the file, in which case we'll update it again. Generally,
297 * there won't be two rules to update a single file, so this should be ok,
299 static HashTable mtimes;
301 static HashTable lmtimes; /* same as mtimes but for lstat */
304 * We use stat(2) a lot, cache the results.
305 * mtime and mode are all we care about.
308 time_t lmtime; /* lstat */
309 time_t mtime; /* stat */
313 /* minimize changes below */
314 typedef enum CachedStatsFlags {
315 CST_LSTAT = 0x01, /* call lstat(2) instead of stat(2) */
316 CST_UPDATE = 0x02 /* ignore existing cached entry */
319 /* Returns 0 and the result of stat(2) or lstat(2) in *mst, or -1 on error. */
321 cached_stats(HashTable *htp, const char *pathname, struct make_stat *mst,
322 CachedStatsFlags flags)
326 struct cache_st *cst;
329 if (!pathname || !pathname[0])
332 entry = HashTable_FindEntry(htp, pathname);
334 if (entry && !(flags & CST_UPDATE)) {
335 cst = HashEntry_Get(entry);
337 mst->mst_mode = cst->mode;
338 mst->mst_mtime = (flags & CST_LSTAT) ? cst->lmtime : cst->mtime;
339 if (mst->mst_mtime) {
340 DIR_DEBUG2("Using cached time %s for %s\n",
341 Targ_FmtTime(mst->mst_mtime), pathname);
346 rc = (flags & CST_LSTAT)
347 ? lstat(pathname, &sys_st)
348 : stat(pathname, &sys_st);
352 if (sys_st.st_mtime == 0)
353 sys_st.st_mtime = 1; /* avoid confusion with missing file */
355 mst->mst_mode = sys_st.st_mode;
356 mst->mst_mtime = sys_st.st_mtime;
359 entry = HashTable_CreateEntry(htp, pathname, NULL);
360 if (HashEntry_Get(entry) == NULL) {
361 HashEntry_Set(entry, bmake_malloc(sizeof(*cst)));
362 memset(HashEntry_Get(entry), 0, sizeof(*cst));
364 cst = HashEntry_Get(entry);
365 if (flags & CST_LSTAT) {
366 cst->lmtime = sys_st.st_mtime;
368 cst->mtime = sys_st.st_mtime;
370 cst->mode = sys_st.st_mode;
371 DIR_DEBUG2(" Caching %s for %s\n",
372 Targ_FmtTime(sys_st.st_mtime), pathname);
378 cached_stat(const char *pathname, struct make_stat *st)
380 return cached_stats(&mtimes, pathname, st, 0);
384 cached_lstat(const char *pathname, struct make_stat *st)
386 return cached_stats(&lmtimes, pathname, st, CST_LSTAT);
389 /* Initialize the directories module. */
393 dirSearchPath = Lst_New();
394 OpenDirs_Init(&openDirs);
395 HashTable_Init(&mtimes);
396 HashTable_Init(&lmtimes);
400 Dir_InitDir(const char *cdname)
404 dotLast = bmake_malloc(sizeof(CachedDir));
405 dotLast->refCount = 1;
407 dotLast->name = bmake_strdup(".DOTLAST");
408 HashTable_Init(&dotLast->files);
412 * Called by Dir_InitDir and whenever .CURDIR is assigned to.
415 Dir_InitCur(const char *cdname)
419 if (cdname != NULL) {
421 * Our build directory is not the same as our source directory.
422 * Keep this one around too.
424 if ((dir = Dir_AddDir(NULL, cdname))) {
426 if (cur && cur != dir) {
428 * We've been here before, clean up.
438 /* (Re)initialize "dot" (current/object directory) path hash.
439 * Some directories may be opened. */
444 /* Remove old entry from openDirs, but do not destroy. */
445 OpenDirs_Remove(&openDirs, dot->name);
448 dot = Dir_AddDir(NULL, ".");
451 Error("Cannot open `.' (%s)", strerror(errno));
456 * We always need to have dot around, so we increment its reference count
457 * to make sure it's not destroyed.
460 Dir_SetPATH(); /* initialize */
463 /* Clean up the directories module. */
474 Dir_Destroy(dotLast);
476 Dir_ClearPath(dirSearchPath);
477 Lst_Free(dirSearchPath);
478 OpenDirs_Done(&openDirs);
479 HashTable_Done(&mtimes);
484 * We want ${.PATH} to indicate the order in which we will actually
485 * search, so we rebuild it after any .PATH: target.
486 * This is the simplest way to deal with the effect of .DOTLAST.
491 CachedDirListNode *ln;
492 Boolean hasLastDot = FALSE; /* true if we should search dot last */
494 Var_Delete(".PATH", VAR_GLOBAL);
496 if ((ln = dirSearchPath->first) != NULL) {
497 CachedDir *dir = ln->datum;
498 if (dir == dotLast) {
500 Var_Append(".PATH", dotLast->name, VAR_GLOBAL);
506 Var_Append(".PATH", dot->name, VAR_GLOBAL);
508 Var_Append(".PATH", cur->name, VAR_GLOBAL);
511 for (ln = dirSearchPath->first; ln != NULL; ln = ln->next) {
512 CachedDir *dir = ln->datum;
515 if (dir == dot && hasLastDot)
517 Var_Append(".PATH", dir->name, VAR_GLOBAL);
522 Var_Append(".PATH", dot->name, VAR_GLOBAL);
524 Var_Append(".PATH", cur->name, VAR_GLOBAL);
528 /* See if the given name has any wildcard characters in it and all braces and
529 * brackets are properly balanced.
531 * XXX: This code is not 100% correct ([^]] fails etc.). I really don't think
532 * that make(1) should be expanding patterns, because then you have to set a
533 * mechanism for escaping the expansion!
535 * Return TRUE if the word should be expanded, FALSE otherwise.
538 Dir_HasWildcards(const char *name)
541 Boolean wild = FALSE;
542 int braces = 0, brackets = 0;
544 for (p = name; *p != '\0'; p++) {
568 return wild && brackets == 0 && braces == 0;
571 /* See if any files match the pattern and add their names to the 'expansions'
574 * This is incomplete -- wildcards are only expanded in the final path
575 * component, but not in directories like src/lib*c/file*.c, but it
576 * will do for now (now being 1993 until at least 2020). To expand these,
577 * use the ':sh' variable modifier such as in ${:!echo src/lib*c/file*.c!}.
580 * pattern Pattern to look for
581 * dir Directory to search
582 * expansion Place to store the results
585 DirMatchFiles(const char *pattern, CachedDir *dir, StringList *expansions)
587 const char *dirName = dir->name;
588 Boolean isDot = dirName[0] == '.' && dirName[1] == '\0';
591 HashIter_Init(&hi, &dir->files);
592 while (HashIter_Next(&hi) != NULL) {
593 const char *base = hi.entry->key;
595 if (!Str_Match(base, pattern))
599 * Follow the UNIX convention that dot files are only found if the
600 * pattern begins with a dot. The pattern '.*' does not match '.' or
601 * '..' since these are not included in the directory cache.
603 * This means that the pattern '[a-z.]*' does not find '.file', which
604 * is consistent with bash, NetBSD sh and csh.
606 if (base[0] == '.' && pattern[0] != '.')
610 char *fullName = isDot
612 : str_concat3(dirName, "/", base);
613 Lst_Append(expansions, fullName);
618 /* Find the next closing brace in the string, taking nested braces into
621 closing_brace(const char *p)
625 if (*p == '}' && nest == 0)
636 /* Find the next closing brace or comma in the string, taking nested braces
639 separator_comma(const char *p)
643 if ((*p == '}' || *p == ',') && nest == 0)
655 contains_wildcard(const char *p)
657 for (; *p != '\0'; p++) {
670 concat3(const char *a, size_t a_len, const char *b, size_t b_len,
671 const char *c, size_t c_len)
673 size_t s_len = a_len + b_len + c_len;
674 char *s = bmake_malloc(s_len + 1);
676 memcpy(s + a_len, b, b_len);
677 memcpy(s + a_len + b_len, c, c_len);
682 /* Expand curly braces like the C shell. Brace expansion by itself is purely
683 * textual, the expansions are not looked up in the file system. But if an
684 * expanded word contains wildcard characters, it is expanded further,
685 * matching only the actually existing files.
687 * Example: "{a{b,c}}" expands to "ab" and "ac".
688 * Example: "{a}" expands to "a".
689 * Example: "{a,*.c}" expands to "a" and all "*.c" files that exist.
692 * word Entire word to expand
693 * brace First curly brace in it
694 * path Search path to use
695 * expansions Place to store the expansions
698 DirExpandCurly(const char *word, const char *brace, SearchPath *path,
699 StringList *expansions)
701 const char *prefix, *middle, *piece, *middle_end, *suffix;
702 size_t prefix_len, suffix_len;
704 /* Split the word into prefix '{' middle '}' suffix. */
707 middle_end = closing_brace(middle);
708 if (*middle_end == '\0') {
709 Error("Unterminated {} clause \"%s\"", middle);
714 prefix_len = (size_t)(brace - prefix);
715 suffix = middle_end + 1;
716 suffix_len = strlen(suffix);
718 /* Split the middle into pieces, separated by commas. */
721 while (piece < middle_end + 1) {
722 const char *piece_end = separator_comma(piece);
723 size_t piece_len = (size_t)(piece_end - piece);
725 char *file = concat3(prefix, prefix_len, piece, piece_len,
728 if (contains_wildcard(file)) {
729 Dir_Expand(file, path, expansions);
732 Lst_Append(expansions, file);
735 piece = piece_end + 1; /* skip over the comma or closing brace */
740 /* Expand the word in each of the directories from the path. */
742 DirExpandPath(const char *word, SearchPath *path, StringList *expansions)
745 for (ln = path->first; ln != NULL; ln = ln->next) {
746 CachedDir *dir = ln->datum;
747 DirMatchFiles(word, dir, expansions);
752 PrintExpansions(StringList *expansions)
754 const char *sep = "";
756 for (ln = expansions->first; ln != NULL; ln = ln->next) {
757 const char *word = ln->datum;
758 debug_printf("%s%s", sep, word);
764 /* Expand the given word into a list of words by globbing it, looking in the
765 * directories on the given search path.
768 * word the word to expand
769 * path the directories in which to find the files
770 * expansions the list on which to place the results
773 Dir_Expand(const char *word, SearchPath *path, StringList *expansions)
777 assert(path != NULL);
778 assert(expansions != NULL);
780 DIR_DEBUG1("Expanding \"%s\"... ", word);
782 cp = strchr(word, '{');
784 DirExpandCurly(word, cp, path, expansions);
786 cp = strchr(word, '/');
789 * The thing has a directory component -- find the first wildcard
792 for (cp = word; *cp; cp++) {
793 if (*cp == '?' || *cp == '[' || *cp == '*') {
800 * Back up to the start of the component
802 while (cp > word && *cp != '/') {
806 char *prefix = bmake_strsedup(word, cp + 1);
808 * If the glob isn't in the first component, try and find
809 * all the components up to the one with a wildcard.
811 char *dirpath = Dir_FindFile(prefix, path);
814 * dirpath is null if can't find the leading component
815 * XXX: Dir_FindFile won't find internal components.
816 * i.e. if the path contains ../Etc/Object and we're
817 * looking for Etc, it won't be found. Ah well.
818 * Probably not important.
820 if (dirpath != NULL) {
821 char *dp = &dirpath[strlen(dirpath) - 1];
825 (void)Dir_AddDir(path, dirpath);
826 DirExpandPath(cp + 1, path, expansions);
831 * Start the search from the local directory
833 DirExpandPath(word, path, expansions);
837 * Return the file -- this should never happen.
839 DirExpandPath(word, path, expansions);
843 * First the files in dot
845 DirMatchFiles(word, dot, expansions);
848 * Then the files in every other directory on the path.
850 DirExpandPath(word, path, expansions);
854 PrintExpansions(expansions);
857 /* Find if the file with the given name exists in the given path.
858 * Return the freshly allocated path to the file, or NULL. */
860 DirLookup(CachedDir *dir, const char *base)
862 char *file; /* the current filename to check */
864 DIR_DEBUG1(" %s ...\n", dir->name);
866 if (HashTable_FindEntry(&dir->files, base) == NULL)
869 file = str_concat3(dir->name, "/", base);
870 DIR_DEBUG1(" returning %s\n", file);
877 /* Find if the file with the given name exists in the given directory.
878 * Return the freshly allocated path to the file, or NULL. */
880 DirLookupSubdir(CachedDir *dir, const char *name)
882 struct make_stat mst;
883 char *file = dir == dot ? bmake_strdup(name)
884 : str_concat3(dir->name, "/", name);
886 DIR_DEBUG1("checking %s ...\n", file);
888 if (cached_stat(file, &mst) == 0) {
896 /* Find if the file with the given name exists in the given path.
897 * Return the freshly allocated path to the file, the empty string, or NULL.
898 * Returning the empty string means that the search should be terminated.
901 DirLookupAbs(CachedDir *dir, const char *name, const char *cp)
903 const char *dnp; /* pointer into dir->name */
904 const char *np; /* pointer into name */
906 DIR_DEBUG1(" %s ...\n", dir->name);
909 * If the file has a leading path component and that component
910 * exactly matches the entire name of the current search
911 * directory, we can attempt another cache lookup. And if we don't
912 * have a hit, we can safely assume the file does not exist at all.
914 for (dnp = dir->name, np = name; *dnp != '\0' && *dnp == *np; dnp++, np++)
916 if (*dnp != '\0' || np != cp - 1)
919 if (HashTable_FindEntry(&dir->files, cp) == NULL) {
920 DIR_DEBUG0(" must be here but isn't -- returning\n");
921 return bmake_strdup(""); /* to terminate the search */
926 DIR_DEBUG1(" returning %s\n", name);
927 return bmake_strdup(name);
930 /* Find the file given on "." or curdir.
931 * Return the freshly allocated path to the file, or NULL. */
933 DirFindDot(const char *name, const char *base)
936 if (HashTable_FindEntry(&dot->files, base) != NULL) {
937 DIR_DEBUG0(" in '.'\n");
940 return bmake_strdup(name);
943 if (cur != NULL && HashTable_FindEntry(&cur->files, base) != NULL) {
944 DIR_DEBUG1(" in ${.CURDIR} = %s\n", cur->name);
947 return str_concat3(cur->name, "/", base);
953 /* Find the file with the given name along the given search path.
955 * If the file is found in a directory that is not on the path
956 * already (either 'name' is absolute or it is a relative path
957 * [ dir1/.../dirn/file ] which exists below one of the directories
958 * already on the search path), its directory is added to the end
959 * of the path, on the assumption that there will be more files in
960 * that directory later on. Sometimes this is true. Sometimes not.
963 * name the file to find
964 * path the directories to search, or NULL
967 * The freshly allocated path to the file, or NULL.
970 Dir_FindFile(const char *name, SearchPath *path)
973 char *file; /* the current filename to check */
974 const char *base; /* Terminal name of file */
975 Boolean hasLastDot = FALSE; /* true if we should search dot last */
976 Boolean hasSlash; /* true if 'name' contains a / */
977 struct make_stat mst; /* Buffer for stat, if necessary */
978 const char *trailing_dot = ".";
981 * Find the final component of the name and note whether it has a
982 * slash in it (the name, I mean)
984 base = strrchr(name, '/');
993 DIR_DEBUG1("Searching for %s ...", name);
996 DIR_DEBUG0("couldn't open path, file not found\n");
1001 if ((ln = path->first) != NULL) {
1002 CachedDir *dir = ln->datum;
1003 if (dir == dotLast) {
1005 DIR_DEBUG0("[dot last]...");
1011 * If there's no leading directory components or if the leading
1012 * directory component is exactly `./', consult the cached contents
1013 * of each of the directories on the search path.
1015 if (!hasSlash || (base - name == 2 && *name == '.')) {
1017 * We look through all the directories on the path seeking one which
1018 * contains the final component of the given name. If such a beast
1019 * is found, we concatenate the directory name and the final
1020 * component and return the resulting string. If we don't find any
1021 * such thing, we go on to phase two...
1023 * No matter what, we always look for the file in the current
1024 * directory before anywhere else (unless we found the magic
1025 * DOTLAST path, in which case we search it last) and we *do not*
1026 * add the ./ to it if it exists.
1027 * This is so there are no conflicts between what the user
1028 * specifies (fish.c) and what pmake finds (./fish.c).
1030 if (!hasLastDot && (file = DirFindDot(name, base)) != NULL)
1033 for (; ln != NULL; ln = ln->next) {
1034 CachedDir *dir = ln->datum;
1037 if ((file = DirLookup(dir, base)) != NULL)
1041 if (hasLastDot && (file = DirFindDot(name, base)) != NULL)
1046 * We didn't find the file on any directory in the search path.
1047 * If the name doesn't contain a slash, that means it doesn't exist.
1048 * If it *does* contain a slash, however, there is still hope: it
1049 * could be in a subdirectory of one of the members of the search
1050 * path. (eg. /usr/include and sys/types.h. The above search would
1051 * fail to turn up types.h in /usr/include, but it *is* in
1052 * /usr/include/sys/types.h).
1053 * [ This no longer applies: If we find such a beast, we assume there
1054 * will be more (what else can we assume?) and add all but the last
1055 * component of the resulting name onto the search path (at the
1057 * This phase is only performed if the file is *not* absolute.
1060 DIR_DEBUG0(" failed.\n");
1065 if (*base == '\0') {
1066 /* we were given a trailing "/" */
1067 base = trailing_dot;
1070 if (name[0] != '/') {
1071 Boolean checkedDot = FALSE;
1073 DIR_DEBUG0(" Trying subdirectories...\n");
1078 if ((file = DirLookupSubdir(dot, name)) != NULL)
1081 if (cur && (file = DirLookupSubdir(cur, name)) != NULL)
1085 for (ln = path->first; ln != NULL; ln = ln->next) {
1086 CachedDir *dir = ln->datum;
1094 if ((file = DirLookupSubdir(dir, name)) != NULL)
1099 if (dot && !checkedDot) {
1101 if ((file = DirLookupSubdir(dot, name)) != NULL)
1104 if (cur && (file = DirLookupSubdir(cur, name)) != NULL)
1110 * Already checked by the given name, since . was in the path,
1111 * so no point in proceeding...
1113 DIR_DEBUG0(" Checked . already, returning NULL\n");
1117 } else { /* name[0] == '/' */
1120 * For absolute names, compare directory path prefix against the
1121 * the directory path of each member on the search path for an exact
1122 * match. If we have an exact match on any member of the search path,
1123 * use the cached contents of that member to lookup the final file
1124 * component. If that lookup fails we can safely assume that the
1125 * file does not exist at all. This is signified by DirLookupAbs()
1126 * returning an empty string.
1128 DIR_DEBUG0(" Trying exact path matches...\n");
1130 if (!hasLastDot && cur &&
1131 ((file = DirLookupAbs(cur, name, base)) != NULL)) {
1132 if (file[0] == '\0') {
1139 for (ln = path->first; ln != NULL; ln = ln->next) {
1140 CachedDir *dir = ln->datum;
1143 if ((file = DirLookupAbs(dir, name, base)) != NULL) {
1144 if (file[0] == '\0') {
1152 if (hasLastDot && cur &&
1153 ((file = DirLookupAbs(cur, name, base)) != NULL)) {
1154 if (file[0] == '\0') {
1163 * Didn't find it that way, either. Sigh. Phase 3. Add its directory
1164 * onto the search path in any case, just in case, then look for the
1165 * thing in the hash table. If we find it, grand. We return a new
1166 * copy of the name. Otherwise we sadly return a NULL pointer. Sigh.
1167 * Note that if the directory holding the file doesn't exist, this will
1168 * do an extra search of the final directory on the path. Unless something
1169 * weird happens, this search won't succeed and life will be groovy.
1171 * Sigh. We cannot add the directory onto the search path because
1172 * of this amusing case:
1173 * $(INSTALLDIR)/$(FILE): $(FILE)
1175 * $(FILE) exists in $(INSTALLDIR) but not in the current one.
1176 * When searching for $(FILE), we will find it in $(INSTALLDIR)
1177 * b/c we added it here. This is not good...
1180 if (base == trailing_dot) {
1181 base = strrchr(name, '/');
1185 (void)Dir_AddDir(path, name);
1189 ln = Lst_Last(path);
1193 dir = LstNode_Datum(ln);
1196 if (Hash_FindEntry(&dir->files, base) != NULL) {
1197 return bmake_strdup(name);
1202 DIR_DEBUG1(" Looking for \"%s\" ...\n", name);
1205 if (cached_stat(name, &mst) == 0) {
1206 return bmake_strdup(name);
1209 DIR_DEBUG0(" failed. Returning NULL\n");
1215 /* Search for a path starting at a given directory and then working our way
1216 * up towards the root.
1219 * here starting directory
1220 * search_path the relative path we are looking for
1223 * The found path, or NULL.
1226 Dir_FindHereOrAbove(const char *here, const char *search_path)
1228 struct make_stat mst;
1229 char *dirbase, *dirbase_end;
1230 char *try, *try_end;
1232 /* copy out our starting point */
1233 dirbase = bmake_strdup(here);
1234 dirbase_end = dirbase + strlen(dirbase);
1236 /* loop until we determine a result */
1239 /* try and stat(2) it ... */
1240 try = str_concat3(dirbase, "/", search_path);
1241 if (cached_stat(try, &mst) != -1) {
1243 * success! if we found a file, chop off
1244 * the filename so we return a directory.
1246 if ((mst.mst_mode & S_IFMT) != S_IFDIR) {
1247 try_end = try + strlen(try);
1248 while (try_end > try && *try_end != '/')
1251 *try_end = '\0'; /* chop! */
1260 * nope, we didn't find it. if we used up dirbase we've
1261 * reached the root and failed.
1263 if (dirbase_end == dirbase)
1264 break; /* failed! */
1267 * truncate dirbase from the end to move up a dir
1269 while (dirbase_end > dirbase && *dirbase_end != '/')
1271 *dirbase_end = '\0'; /* chop! */
1279 *-----------------------------------------------------------------------
1281 * Find the modification time of the file described by gn along the
1282 * search path dirSearchPath.
1285 * gn the file whose modification time is desired
1288 * The modification time or 0 if it doesn't exist
1291 * The modification time is placed in the node's mtime slot.
1292 * If the node didn't have a path entry before, and Dir_FindFile
1293 * found one for it, the full name is placed in the path slot.
1294 *-----------------------------------------------------------------------
1297 Dir_MTime(GNode *gn, Boolean recheck)
1299 char *fullName; /* the full pathname of name */
1300 struct make_stat mst; /* buffer for finding the mod time */
1302 if (gn->type & OP_ARCHV) {
1303 return Arch_MTime(gn);
1304 } else if (gn->type & OP_PHONY) {
1307 } else if (gn->path == NULL) {
1308 if (gn->type & OP_NOPATH)
1311 fullName = Dir_FindFile(gn->name, Suff_FindPath(gn));
1312 if (fullName == NULL && gn->flags & FROM_DEPEND &&
1313 !Lst_IsEmpty(gn->implicitParents)) {
1316 cp = strrchr(gn->name, '/');
1319 * This is an implied source, and it may have moved,
1320 * see if we can find it via the current .PATH
1324 fullName = Dir_FindFile(cp, Suff_FindPath(gn));
1327 * Put the found file in gn->path
1328 * so that we give that to the compiler.
1330 gn->path = bmake_strdup(fullName);
1331 if (!Job_RunTarget(".STALE", gn->fname))
1333 "%s: %s, %d: ignoring stale %s for %s, "
1334 "found %s\n", progname, gn->fname,
1336 makeDependfile, gn->name, fullName);
1340 DIR_DEBUG2("Found '%s' as '%s'\n",
1341 gn->name, fullName ? fullName : "(not found)");
1344 fullName = gn->path;
1347 if (fullName == NULL) {
1348 fullName = bmake_strdup(gn->name);
1351 if (cached_stats(&mtimes, fullName, &mst, recheck ? CST_UPDATE : 0) < 0) {
1352 if (gn->type & OP_MEMBER) {
1353 if (fullName != gn->path)
1355 return Arch_MemMTime(gn);
1361 if (fullName != NULL && gn->path == NULL)
1362 gn->path = fullName;
1364 gn->mtime = mst.mst_mtime;
1368 /* Read the list of filenames in the directory and store the result
1369 * in openDirectories.
1371 * If a path is given, append the directory to that path.
1374 * path The path to which the directory should be
1375 * added, or NULL to only add the directory to
1377 * name The name of the directory to add.
1378 * The name is not normalized in any way.
1381 Dir_AddDir(SearchPath *path, const char *name)
1383 CachedDir *dir = NULL; /* the added directory */
1387 if (path != NULL && strcmp(name, ".DOTLAST") == 0) {
1390 for (ln = path->first; ln != NULL; ln = ln->next) {
1391 CachedDir *pathDir = ln->datum;
1392 if (strcmp(pathDir->name, name) == 0)
1396 dotLast->refCount++;
1397 Lst_Prepend(path, dotLast);
1401 dir = OpenDirs_Find(&openDirs, name);
1403 if (Lst_FindDatum(path, dir) == NULL) {
1405 Lst_Append(path, dir);
1410 DIR_DEBUG1("Caching %s ...", name);
1412 if ((d = opendir(name)) != NULL) {
1413 dir = bmake_malloc(sizeof(CachedDir));
1414 dir->name = bmake_strdup(name);
1417 HashTable_Init(&dir->files);
1419 while ((dp = readdir(d)) != NULL) {
1420 #if defined(sun) && defined(d_ino) /* d_ino is a sunos4 #define for d_fileno */
1422 * The sun directory library doesn't check for a 0 inode
1423 * (0-inode slots just take up space), so we have to do
1426 if (dp->d_fileno == 0) {
1429 #endif /* sun && d_ino */
1430 (void)HashTable_CreateEntry(&dir->files, dp->d_name, NULL);
1433 OpenDirs_Add(&openDirs, dir);
1435 Lst_Append(path, dir);
1437 DIR_DEBUG0("done\n");
1441 /* Return a copy of dirSearchPath, incrementing the reference counts for
1442 * the contained directories. */
1444 Dir_CopyDirSearchPath(void)
1446 SearchPath *path = Lst_New();
1448 for (ln = dirSearchPath->first; ln != NULL; ln = ln->next) {
1449 CachedDir *dir = ln->datum;
1451 Lst_Append(path, dir);
1457 *-----------------------------------------------------------------------
1459 * Make a string by taking all the directories in the given search
1460 * path and preceding them by the given flag. Used by the suffix
1461 * module to create variables for compilers based on suffix search
1465 * flag flag which should precede each directory
1466 * path list of directories
1469 * The string mentioned above. Note that there is no space between
1470 * the given flag and each directory. The empty string is returned if
1471 * Things don't go well.
1475 *-----------------------------------------------------------------------
1478 Dir_MakeFlags(const char *flag, SearchPath *path)
1486 for (ln = path->first; ln != NULL; ln = ln->next) {
1487 CachedDir *dir = ln->datum;
1488 Buf_AddStr(&buf, " ");
1489 Buf_AddStr(&buf, flag);
1490 Buf_AddStr(&buf, dir->name);
1494 return Buf_Destroy(&buf, FALSE);
1497 /* Nuke a directory descriptor, if possible. Callback procedure for the
1498 * suffixes module when destroying a search path.
1501 * dirp The directory descriptor to nuke
1504 Dir_Destroy(void *dirp)
1506 CachedDir *dir = dirp;
1509 if (dir->refCount == 0) {
1510 OpenDirs_Remove(&openDirs, dir->name);
1512 HashTable_Done(&dir->files);
1518 /* Clear out all elements from the given search path.
1519 * The path is set to the empty list but is not destroyed. */
1521 Dir_ClearPath(SearchPath *path)
1523 while (!Lst_IsEmpty(path)) {
1524 CachedDir *dir = Lst_Dequeue(path);
1530 /* Concatenate two paths, adding the second to the end of the first,
1531 * skipping duplicates. */
1533 Dir_Concat(SearchPath *dst, SearchPath *src)
1537 for (ln = src->first; ln != NULL; ln = ln->next) {
1538 CachedDir *dir = ln->datum;
1539 if (Lst_FindDatum(dst, dir) == NULL) {
1541 Lst_Append(dst, dir);
1547 percentage(int num, int den)
1549 return den != 0 ? num * 100 / den : 0;
1552 /********** DEBUG INFO **********/
1554 Dir_PrintDirectories(void)
1556 CachedDirListNode *ln;
1558 debug_printf("#*** Directory Cache:\n");
1559 debug_printf("# Stats: %d hits %d misses %d near misses %d losers (%d%%)\n",
1560 hits, misses, nearmisses, bigmisses,
1561 percentage(hits, hits + bigmisses + nearmisses));
1562 debug_printf("# %-20s referenced\thits\n", "directory");
1564 for (ln = openDirs.list->first; ln != NULL; ln = ln->next) {
1565 CachedDir *dir = ln->datum;
1566 debug_printf("# %-20s %10d\t%4d\n", dir->name, dir->refCount,
1572 Dir_PrintPath(SearchPath *path)
1574 SearchPathNode *node;
1575 for (node = path->first; node != NULL; node = node->next) {
1576 const CachedDir *dir = node->datum;
1577 debug_printf("%s ", dir->name);