1 /* $NetBSD: dir.c,v 1.135 2020/09/02 04:32:13 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
73 static char rcsid[] = "$NetBSD: dir.c,v 1.135 2020/09/02 04:32:13 rillig 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.135 2020/09/02 04:32:13 rillig 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 #define DIR_DEBUG0(fmt) \
151 if (!DEBUG(DIR)) (void) 0; else fprintf(debug_file, fmt)
153 #define DIR_DEBUG1(fmt, arg1) \
154 if (!DEBUG(DIR)) (void) 0; else fprintf(debug_file, fmt, arg1)
156 #define DIR_DEBUG2(fmt, arg1, arg2) \
157 if (!DEBUG(DIR)) (void) 0; else fprintf(debug_file, fmt, arg1, arg2)
161 * A search path consists of a Lst of Path structures. A Path structure
162 * has in it the name of the directory and a hash table of all the files
163 * in the directory. This is used to cut down on the number of system
164 * calls necessary to find implicit dependents and their like. Since
165 * these searches are made before any actions are taken, we need not
166 * worry about the directory changing due to creation commands. If this
167 * hampers the style of some makefiles, they must be changed.
169 * A list of all previously-read directories is kept in the
170 * openDirectories Lst. This list is checked first before a directory
173 * The need for the caching of whole directories is brought about by
174 * the multi-level transformation code in suff.c, which tends to search
175 * for far more files than regular make does. In the initial
176 * implementation, the amount of time spent performing "stat" calls was
177 * truly astronomical. The problem with hashing at the start is,
178 * of course, that pmake doesn't then detect changes to these directories
179 * during the course of the make. Three possibilities suggest themselves:
181 * 1) just use stat to test for a file's existence. As mentioned
182 * above, this is very inefficient due to the number of checks
183 * engendered by the multi-level transformation code.
184 * 2) use readdir() and company to search the directories, keeping
185 * them open between checks. I have tried this and while it
186 * didn't slow down the process too much, it could severely
187 * affect the amount of parallelism available as each directory
188 * open would take another file descriptor out of play for
189 * handling I/O for another job. Given that it is only recently
190 * that UNIX OS's have taken to allowing more than 20 or 32
191 * file descriptors for a process, this doesn't seem acceptable
193 * 3) record the mtime of the directory in the Path structure and
194 * verify the directory hasn't changed since the contents were
195 * hashed. This will catch the creation or deletion of files,
196 * but not the updating of files. However, since it is the
197 * creation and deletion that is the problem, this could be
198 * a good thing to do. Unfortunately, if the directory (say ".")
199 * were fairly large and changed fairly frequently, the constant
200 * rehashing could seriously degrade performance. It might be
201 * good in such cases to keep track of the number of rehashes
202 * and if the number goes over a (small) limit, resort to using
205 * An additional thing to consider is that pmake is used primarily
206 * to create C programs and until recently pcc-based compilers refused
207 * to allow you to specify where the resulting object file should be
208 * placed. This forced all objects to be created in the current
209 * directory. This isn't meant as a full excuse, just an explanation of
210 * some of the reasons for the caching used here.
212 * One more note: the location of a target's file is only performed
213 * on the downward traversal of the graph and then only for terminal
214 * nodes in the graph. This could be construed as wrong in some cases,
215 * but prevents inadvertent modification of files when the "installed"
216 * directory for a file is provided in the search path.
218 * Another data structure maintained by this module is an mtime
219 * cache used when the searching of cached directories fails to find
220 * a file. In the past, Dir_FindFile would simply perform an access()
221 * call in such a case to determine if the file could be found using
222 * just the name given. When this hit, however, all that was gained
223 * was the knowledge that the file existed. Given that an access() is
224 * essentially a stat() without the copyout() call, and that the same
225 * filesystem overhead would have to be incurred in Dir_MTime, it made
226 * sense to replace the access() with a stat() and record the mtime
227 * in a cache for when Dir_MTime was actually called.
230 Lst dirSearchPath; /* main search path */
232 static Lst openDirectories; /* the list of all open directories */
235 * Variables for gathering statistics on the efficiency of the hashing
238 static int hits; /* Found in directory cache */
239 static int misses; /* Sad, but not evil misses */
240 static int nearmisses; /* Found under search path */
241 static int bigmisses; /* Sought by itself */
243 static Path *dot; /* contents of current directory */
244 static Path *cur; /* contents of current directory, if not dot */
245 static Path *dotLast; /* a fake path entry indicating we need to
248 /* Results of doing a last-resort stat in Dir_FindFile -- if we have to go to
249 * the system to find the file, we might as well have its mtime on record.
251 * XXX: If this is done way early, there's a chance other rules will have
252 * already updated the file, in which case we'll update it again. Generally,
253 * there won't be two rules to update a single file, so this should be ok,
255 static Hash_Table mtimes;
257 static Hash_Table lmtimes; /* same as mtimes but for lstat */
259 static void DirExpandCurly(const char *, const char *, Lst, Lst);
260 static void DirExpandInt(const char *, Lst, Lst);
261 static int DirPrintWord(void *, void *);
262 static int DirPrintDir(void *, void *);
263 static char *DirLookup(Path *, const char *, const char *, Boolean);
264 static char *DirLookupSubdir(Path *, const char *);
265 static char *DirFindDot(Boolean, const char *, const char *);
266 static char *DirLookupAbs(Path *, const char *, const char *);
270 * We use stat(2) a lot, cache the results.
271 * mtime and mode are all we care about.
274 time_t lmtime; /* lstat */
275 time_t mtime; /* stat */
279 /* minimize changes below */
281 CST_LSTAT = 0x01, /* call lstat(2) instead of stat(2) */
282 CST_UPDATE = 0x02 /* ignore existing cached entry */
285 /* Returns 0 and the result of stat(2) or lstat(2) in *mst, or -1 on error. */
287 cached_stats(Hash_Table *htp, const char *pathname, struct make_stat *mst,
288 CachedStatsFlags flags)
292 struct cache_st *cst;
295 if (!pathname || !pathname[0])
298 entry = Hash_FindEntry(htp, pathname);
300 if (entry && !(flags & CST_UPDATE)) {
301 cst = Hash_GetValue(entry);
303 mst->mst_mode = cst->mode;
304 mst->mst_mtime = (flags & CST_LSTAT) ? cst->lmtime : cst->mtime;
305 if (mst->mst_mtime) {
306 DIR_DEBUG2("Using cached time %s for %s\n",
307 Targ_FmtTime(mst->mst_mtime), pathname);
312 rc = (flags & CST_LSTAT)
313 ? lstat(pathname, &sys_st)
314 : stat(pathname, &sys_st);
318 if (sys_st.st_mtime == 0)
319 sys_st.st_mtime = 1; /* avoid confusion with missing file */
321 mst->mst_mode = sys_st.st_mode;
322 mst->mst_mtime = sys_st.st_mtime;
325 entry = Hash_CreateEntry(htp, pathname, NULL);
326 if (Hash_GetValue(entry) == NULL) {
327 Hash_SetValue(entry, bmake_malloc(sizeof(*cst)));
328 memset(Hash_GetValue(entry), 0, sizeof(*cst));
330 cst = Hash_GetValue(entry);
331 if (flags & CST_LSTAT) {
332 cst->lmtime = sys_st.st_mtime;
334 cst->mtime = sys_st.st_mtime;
336 cst->mode = sys_st.st_mode;
337 DIR_DEBUG2(" Caching %s for %s\n",
338 Targ_FmtTime(sys_st.st_mtime), pathname);
344 cached_stat(const char *pathname, struct make_stat *st)
346 return cached_stats(&mtimes, pathname, st, 0);
350 cached_lstat(const char *pathname, struct make_stat *st)
352 return cached_stats(&lmtimes, pathname, st, CST_LSTAT);
355 /* Initialize things for this module. */
359 dirSearchPath = Lst_Init();
360 openDirectories = Lst_Init();
361 Hash_InitTable(&mtimes, 0);
362 Hash_InitTable(&lmtimes, 0);
366 Dir_InitDir(const char *cdname)
370 dotLast = bmake_malloc(sizeof(Path));
371 dotLast->refCount = 1;
373 dotLast->name = bmake_strdup(".DOTLAST");
374 Hash_InitTable(&dotLast->files, -1);
378 * Called by Dir_InitDir and whenever .CURDIR is assigned to.
381 Dir_InitCur(const char *cdname)
385 if (cdname != NULL) {
387 * Our build directory is not the same as our source directory.
388 * Keep this one around too.
390 if ((p = Dir_AddDir(NULL, cdname))) {
392 if (cur && cur != p) {
394 * We've been here before, cleanup.
404 /* (Re)initialize "dot" (current/object directory) path hash.
405 * Some directories may be opened. */
412 /* Remove old entry from openDirectories, but do not destroy. */
413 ln = Lst_FindDatum(openDirectories, dot);
414 Lst_Remove(openDirectories, ln);
417 dot = Dir_AddDir(NULL, ".");
420 Error("Cannot open `.' (%s)", strerror(errno));
425 * We always need to have dot around, so we increment its reference count
426 * to make sure it's not destroyed.
429 Dir_SetPATH(); /* initialize */
432 /* Clean up things for this module. */
442 dotLast->refCount -= 1;
443 Dir_Destroy(dotLast);
445 Dir_ClearPath(dirSearchPath);
446 Lst_Free(dirSearchPath);
447 Dir_ClearPath(openDirectories);
448 Lst_Free(openDirectories);
449 Hash_DeleteTable(&mtimes);
454 * We want ${.PATH} to indicate the order in which we will actually
455 * search, so we rebuild it after any .PATH: target.
456 * This is the simplest way to deal with the effect of .DOTLAST.
461 LstNode ln; /* a list element */
463 Boolean hasLastDot = FALSE; /* true if we should search dot last */
465 Var_Delete(".PATH", VAR_GLOBAL);
467 Lst_Open(dirSearchPath);
468 if ((ln = Lst_First(dirSearchPath)) != NULL) {
469 p = LstNode_Datum(ln);
472 Var_Append(".PATH", dotLast->name, VAR_GLOBAL);
478 Var_Append(".PATH", dot->name, VAR_GLOBAL);
480 Var_Append(".PATH", cur->name, VAR_GLOBAL);
483 while ((ln = Lst_Next(dirSearchPath)) != NULL) {
484 p = LstNode_Datum(ln);
487 if (p == dot && hasLastDot)
489 Var_Append(".PATH", p->name, VAR_GLOBAL);
494 Var_Append(".PATH", dot->name, VAR_GLOBAL);
496 Var_Append(".PATH", cur->name, VAR_GLOBAL);
498 Lst_Close(dirSearchPath);
501 /* See if the Path structure describes the same directory as the
502 * given one by comparing their names. Called from Dir_AddDir via
503 * Lst_Find when searching the list of open directories. */
505 DirFindName(const void *p, const void *desiredName)
507 return strcmp(((const Path *)p)->name, desiredName) == 0;
510 /* See if the given name has any wildcard characters in it. Be careful not to
511 * expand unmatching brackets or braces.
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!
521 * returns TRUE if the word should be expanded, FALSE otherwise
524 Dir_HasWildcards(const char *name)
527 Boolean wild = FALSE;
528 int braces = 0, brackets = 0;
530 for (cp = name; *cp; cp++) {
554 return wild && brackets == 0 && braces == 0;
558 *-----------------------------------------------------------------------
560 * Given a pattern and a Path structure, see if any files
561 * match the pattern and add their names to the 'expansions' list if
562 * any do. This is incomplete -- it doesn't take care of patterns like
563 * src / *src / *.c properly (just *.c on any of the directories), but it
567 * pattern Pattern to look for
568 * p Directory to search
569 * expansion Place to store the results
572 * File names are added to the expansions lst. The directory will be
573 * fully hashed when this is done.
574 *-----------------------------------------------------------------------
577 DirMatchFiles(const char *pattern, Path *p, Lst expansions)
579 Hash_Search search; /* Index into the directory's table */
580 Hash_Entry *entry; /* Current entry in the table */
581 Boolean isDot; /* TRUE if the directory being searched is . */
583 isDot = (*p->name == '.' && p->name[1] == '\0');
585 for (entry = Hash_EnumFirst(&p->files, &search);
587 entry = Hash_EnumNext(&search))
590 * See if the file matches the given pattern. Note we follow the UNIX
591 * convention that dot files will only be found if the pattern
592 * begins with a dot (note also that as a side effect of the hashing
593 * scheme, .* won't match . or .. since they aren't hashed).
595 if (Str_Match(entry->name, pattern) &&
596 ((entry->name[0] != '.') ||
597 (pattern[0] == '.')))
599 Lst_Append(expansions,
600 (isDot ? bmake_strdup(entry->name) :
601 str_concat3(p->name, "/", entry->name)));
606 /* Find the next closing brace in the string, taking nested braces into
609 closing_brace(const char *p)
613 if (*p == '}' && nest == 0)
624 /* Find the next closing brace or comma in the string, taking nested braces
627 separator_comma(const char *p)
631 if ((*p == '}' || *p == ',') && nest == 0)
643 contains_wildcard(const char *p)
645 for (; *p != '\0'; p++) {
658 concat3(const char *a, size_t a_len, const char *b, size_t b_len,
659 const char *c, size_t c_len)
661 size_t s_len = a_len + b_len + c_len;
662 char *s = bmake_malloc(s_len + 1);
664 memcpy(s + a_len, b, b_len);
665 memcpy(s + a_len + b_len, c, c_len);
671 *-----------------------------------------------------------------------
673 * Expand curly braces like the C shell. Does this recursively.
674 * Note the special case: if after the piece of the curly brace is
675 * done there are no wildcard characters in the result, the result is
676 * placed on the list WITHOUT CHECKING FOR ITS EXISTENCE.
679 * word Entire word to expand
680 * brace First curly brace in it
681 * path Search path to use
682 * expansions Place to store the expansions
688 * The given list is filled with the expansions...
690 *-----------------------------------------------------------------------
693 DirExpandCurly(const char *word, const char *brace, Lst path, Lst expansions)
695 const char *prefix, *middle, *piece, *middle_end, *suffix;
696 size_t prefix_len, suffix_len;
698 /* Split the word into prefix '{' middle '}' suffix. */
701 middle_end = closing_brace(middle);
702 if (*middle_end == '\0') {
703 Error("Unterminated {} clause \"%s\"", middle);
708 prefix_len = (size_t)(brace - prefix);
709 suffix = middle_end + 1;
710 suffix_len = strlen(suffix);
712 /* Split the middle into pieces, separated by commas. */
715 while (piece < middle_end + 1) {
716 const char *piece_end = separator_comma(piece);
717 size_t piece_len = (size_t)(piece_end - piece);
719 char *file = concat3(prefix, prefix_len, piece, piece_len,
722 if (contains_wildcard(file)) {
723 Dir_Expand(file, path, expansions);
726 Lst_Append(expansions, file);
729 piece = piece_end + 1; /* skip over the comma or closing brace */
735 *-----------------------------------------------------------------------
737 * Internal expand routine. Passes through the directories in the
738 * path one by one, calling DirMatchFiles for each. NOTE: This still
739 * doesn't handle patterns in directories...
742 * word Word to expand
743 * path Path on which to look
744 * expansions Place to store the result
750 * Things are added to the expansions list.
752 *-----------------------------------------------------------------------
755 DirExpandInt(const char *word, Lst path, Lst expansions)
757 LstNode ln; /* Current node */
760 while ((ln = Lst_Next(path)) != NULL) {
761 Path *p = LstNode_Datum(ln);
762 DirMatchFiles(word, p, expansions);
767 /* Print a word in the list of expansions.
768 * Callback for Dir_Expand when DEBUG(DIR), via Lst_ForEach. */
770 DirPrintWord(void *word, void *dummy MAKE_ATTR_UNUSED)
772 fprintf(debug_file, "%s ", (char *)word);
778 *-----------------------------------------------------------------------
780 * Expand the given word into a list of words by globbing it looking
781 * in the directories on the given search path.
784 * word the word to expand
785 * path the list of directories in which to find the
787 * expansions the list on which to place the results
790 * A list of words consisting of the files which exist along the search
791 * path matching the given pattern.
794 * Directories may be opened. Who knows?
795 * Undefined behavior if the word is really in read-only memory.
796 *-----------------------------------------------------------------------
799 Dir_Expand(const char *word, Lst path, Lst expansions)
803 assert(path != NULL);
804 assert(expansions != NULL);
806 DIR_DEBUG1("Expanding \"%s\"... ", word);
808 cp = strchr(word, '{');
810 DirExpandCurly(word, cp, path, expansions);
812 cp = strchr(word, '/');
815 * The thing has a directory component -- find the first wildcard
818 for (cp = word; *cp; cp++) {
819 if (*cp == '?' || *cp == '[' || *cp == '*' || *cp == '{') {
825 * This one will be fun.
827 DirExpandCurly(word, cp, path, expansions);
829 } else if (*cp != '\0') {
831 * Back up to the start of the component
833 while (cp > word && *cp != '/') {
840 * If the glob isn't in the first component, try and find
841 * all the components up to the one with a wildcard.
844 ((char *)UNCONST(cp))[1] = '\0';
845 dirpath = Dir_FindFile(word, path);
846 ((char *)UNCONST(cp))[1] = sc;
848 * dirpath is null if can't find the leading component
849 * XXX: Dir_FindFile won't find internal components.
850 * i.e. if the path contains ../Etc/Object and we're
851 * looking for Etc, it won't be found. Ah well.
852 * Probably not important.
854 if (dirpath != NULL) {
855 char *dp = &dirpath[strlen(dirpath) - 1];
859 (void)Dir_AddDir(path, dirpath);
860 DirExpandInt(cp + 1, path, expansions);
865 * Start the search from the local directory
867 DirExpandInt(word, path, expansions);
871 * Return the file -- this should never happen.
873 DirExpandInt(word, path, expansions);
877 * First the files in dot
879 DirMatchFiles(word, dot, expansions);
882 * Then the files in every other directory on the path.
884 DirExpandInt(word, path, expansions);
888 Lst_ForEach(expansions, DirPrintWord, NULL);
889 fprintf(debug_file, "\n");
894 *-----------------------------------------------------------------------
896 * Find if the file with the given name exists in the given path.
899 * The path to the file or NULL. This path is guaranteed to be in a
900 * different part of memory than name and so may be safely free'd.
904 *-----------------------------------------------------------------------
907 DirLookup(Path *p, const char *name MAKE_ATTR_UNUSED, const char *cp,
908 Boolean hasSlash MAKE_ATTR_UNUSED)
910 char *file; /* the current filename to check */
912 DIR_DEBUG1(" %s ...\n", p->name);
914 if (Hash_FindEntry(&p->files, cp) == NULL)
917 file = str_concat3(p->name, "/", cp);
918 DIR_DEBUG1(" returning %s\n", file);
926 *-----------------------------------------------------------------------
928 * Find if the file with the given name exists in the given path.
931 * The path to the file or NULL. This path is guaranteed to be in a
932 * different part of memory than name and so may be safely free'd.
935 * If the file is found, it is added in the modification times hash
937 *-----------------------------------------------------------------------
940 DirLookupSubdir(Path *p, const char *name)
942 struct make_stat mst;
943 char *file; /* the current filename to check */
946 file = str_concat3(p->name, "/", name);
949 * Checking in dot -- DON'T put a leading ./ on the thing.
951 file = bmake_strdup(name);
954 DIR_DEBUG1("checking %s ...\n", file);
956 if (cached_stat(file, &mst) == 0) {
965 *-----------------------------------------------------------------------
967 * Find if the file with the given name exists in the given path.
970 * The path to the file, the empty string or NULL. If the file is
971 * the empty string, the search should be terminated.
972 * This path is guaranteed to be in a different part of memory
973 * than name and so may be safely free'd.
977 *-----------------------------------------------------------------------
980 DirLookupAbs(Path *p, const char *name, const char *cp)
982 char *p1; /* pointer into p->name */
983 const char *p2; /* pointer into name */
985 DIR_DEBUG1(" %s ...\n", p->name);
988 * If the file has a leading path component and that component
989 * exactly matches the entire name of the current search
990 * directory, we can attempt another cache lookup. And if we don't
991 * have a hit, we can safely assume the file does not exist at all.
993 for (p1 = p->name, p2 = name; *p1 && *p1 == *p2; p1++, p2++) {
996 if (*p1 != '\0' || p2 != cp - 1) {
1000 if (Hash_FindEntry(&p->files, cp) == NULL) {
1001 DIR_DEBUG0(" must be here but isn't -- returning\n");
1002 /* Return empty string: terminates search */
1003 return bmake_strdup("");
1008 DIR_DEBUG1(" returning %s\n", name);
1009 return bmake_strdup(name);
1013 *-----------------------------------------------------------------------
1015 * Find the file given on "." or curdir
1018 * The path to the file or NULL. This path is guaranteed to be in a
1019 * different part of memory than name and so may be safely free'd.
1023 *-----------------------------------------------------------------------
1026 DirFindDot(Boolean hasSlash MAKE_ATTR_UNUSED, const char *name, const char *cp)
1029 if (Hash_FindEntry(&dot->files, cp) != NULL) {
1030 DIR_DEBUG0(" in '.'\n");
1033 return bmake_strdup(name);
1035 if (cur && Hash_FindEntry(&cur->files, cp) != NULL) {
1036 DIR_DEBUG1(" in ${.CURDIR} = %s\n", cur->name);
1039 return str_concat3(cur->name, "/", cp);
1046 *-----------------------------------------------------------------------
1048 * Find the file with the given name along the given search path.
1051 * name the file to find
1052 * path the Lst of directories to search
1055 * The path to the file or NULL. This path is guaranteed to be in a
1056 * different part of memory than name and so may be safely free'd.
1059 * If the file is found in a directory which is not on the path
1060 * already (either 'name' is absolute or it is a relative path
1061 * [ dir1/.../dirn/file ] which exists below one of the directories
1062 * already on the search path), its directory is added to the end
1063 * of the path on the assumption that there will be more files in
1064 * that directory later on. Sometimes this is true. Sometimes not.
1065 *-----------------------------------------------------------------------
1068 Dir_FindFile(const char *name, Lst path)
1070 LstNode ln; /* a list element */
1071 char *file; /* the current filename to check */
1072 Path *p; /* current path member */
1073 const char *cp; /* Terminal name of file */
1074 Boolean hasLastDot = FALSE; /* true we should search dot last */
1075 Boolean hasSlash; /* true if 'name' contains a / */
1076 struct make_stat mst; /* Buffer for stat, if necessary */
1077 const char *trailing_dot = ".";
1080 * Find the final component of the name and note whether it has a
1081 * slash in it (the name, I mean)
1083 cp = strrchr(name, '/');
1092 DIR_DEBUG1("Searching for %s ...", name);
1095 DIR_DEBUG0("couldn't open path, file not found\n");
1101 if ((ln = Lst_First(path)) != NULL) {
1102 p = LstNode_Datum(ln);
1105 DIR_DEBUG0("[dot last]...");
1111 * If there's no leading directory components or if the leading
1112 * directory component is exactly `./', consult the cached contents
1113 * of each of the directories on the search path.
1115 if (!hasSlash || (cp - name == 2 && *name == '.')) {
1117 * We look through all the directories on the path seeking one which
1118 * contains the final component of the given name. If such a beast
1119 * is found, we concatenate the directory name and the final
1120 * component and return the resulting string. If we don't find any
1121 * such thing, we go on to phase two...
1123 * No matter what, we always look for the file in the current
1124 * directory before anywhere else (unless we found the magic
1125 * DOTLAST path, in which case we search it last) and we *do not*
1126 * add the ./ to it if it exists.
1127 * This is so there are no conflicts between what the user
1128 * specifies (fish.c) and what pmake finds (./fish.c).
1130 if (!hasLastDot && (file = DirFindDot(hasSlash, name, cp)) != NULL) {
1135 while ((ln = Lst_Next(path)) != NULL) {
1136 p = LstNode_Datum(ln);
1139 if ((file = DirLookup(p, name, cp, hasSlash)) != NULL) {
1145 if (hasLastDot && (file = DirFindDot(hasSlash, name, cp)) != NULL) {
1153 * We didn't find the file on any directory in the search path.
1154 * If the name doesn't contain a slash, that means it doesn't exist.
1155 * If it *does* contain a slash, however, there is still hope: it
1156 * could be in a subdirectory of one of the members of the search
1157 * path. (eg. /usr/include and sys/types.h. The above search would
1158 * fail to turn up types.h in /usr/include, but it *is* in
1159 * /usr/include/sys/types.h).
1160 * [ This no longer applies: If we find such a beast, we assume there
1161 * will be more (what else can we assume?) and add all but the last
1162 * component of the resulting name onto the search path (at the
1164 * This phase is only performed if the file is *not* absolute.
1167 DIR_DEBUG0(" failed.\n");
1173 /* we were given a trailing "/" */
1177 if (name[0] != '/') {
1178 Boolean checkedDot = FALSE;
1180 DIR_DEBUG0(" Trying subdirectories...\n");
1185 if ((file = DirLookupSubdir(dot, name)) != NULL)
1188 if (cur && (file = DirLookupSubdir(cur, name)) != NULL)
1193 while ((ln = Lst_Next(path)) != NULL) {
1194 p = LstNode_Datum(ln);
1202 if ((file = DirLookupSubdir(p, name)) != NULL) {
1210 if (dot && !checkedDot) {
1212 if ((file = DirLookupSubdir(dot, name)) != NULL)
1215 if (cur && (file = DirLookupSubdir(cur, name)) != NULL)
1221 * Already checked by the given name, since . was in the path,
1222 * so no point in proceeding...
1224 DIR_DEBUG0(" Checked . already, returning NULL\n");
1228 } else { /* name[0] == '/' */
1231 * For absolute names, compare directory path prefix against the
1232 * the directory path of each member on the search path for an exact
1233 * match. If we have an exact match on any member of the search path,
1234 * use the cached contents of that member to lookup the final file
1235 * component. If that lookup fails we can safely assume that the
1236 * file does not exist at all. This is signified by DirLookupAbs()
1237 * returning an empty string.
1239 DIR_DEBUG0(" Trying exact path matches...\n");
1241 if (!hasLastDot && cur &&
1242 ((file = DirLookupAbs(cur, name, cp)) != NULL)) {
1243 if (file[0] == '\0') {
1251 while ((ln = Lst_Next(path)) != NULL) {
1252 p = LstNode_Datum(ln);
1255 if ((file = DirLookupAbs(p, name, cp)) != NULL) {
1257 if (file[0] == '\0') {
1266 if (hasLastDot && cur &&
1267 ((file = DirLookupAbs(cur, name, cp)) != NULL)) {
1268 if (file[0] == '\0') {
1277 * Didn't find it that way, either. Sigh. Phase 3. Add its directory
1278 * onto the search path in any case, just in case, then look for the
1279 * thing in the hash table. If we find it, grand. We return a new
1280 * copy of the name. Otherwise we sadly return a NULL pointer. Sigh.
1281 * Note that if the directory holding the file doesn't exist, this will
1282 * do an extra search of the final directory on the path. Unless something
1283 * weird happens, this search won't succeed and life will be groovy.
1285 * Sigh. We cannot add the directory onto the search path because
1286 * of this amusing case:
1287 * $(INSTALLDIR)/$(FILE): $(FILE)
1289 * $(FILE) exists in $(INSTALLDIR) but not in the current one.
1290 * When searching for $(FILE), we will find it in $(INSTALLDIR)
1291 * b/c we added it here. This is not good...
1294 if (cp == traling_dot) {
1295 cp = strrchr(name, '/');
1299 (void)Dir_AddDir(path, name);
1303 ln = Lst_Last(path);
1307 p = LstNode_Datum(ln);
1310 if (Hash_FindEntry(&p->files, cp) != NULL) {
1311 return bmake_strdup(name);
1316 DIR_DEBUG1(" Looking for \"%s\" ...\n", name);
1319 if (cached_stat(name, &mst) == 0) {
1320 return bmake_strdup(name);
1323 DIR_DEBUG0(" failed. Returning NULL\n");
1330 *-----------------------------------------------------------------------
1331 * Dir_FindHereOrAbove --
1332 * search for a path starting at a given directory and then working
1333 * our way up towards the root.
1336 * here starting directory
1337 * search_path the path we are looking for
1338 * result the result of a successful search is placed here
1339 * result_len the length of the result buffer
1340 * (typically MAXPATHLEN + 1)
1343 * 0 on failure, 1 on success [in which case the found path is put
1344 * in the result buffer].
1347 *-----------------------------------------------------------------------
1350 Dir_FindHereOrAbove(const char *here, const char *search_path,
1351 char *result, int result_len)
1353 struct make_stat mst;
1354 char dirbase[MAXPATHLEN + 1], *dirbase_end;
1355 char try[MAXPATHLEN + 1], *try_end;
1357 /* copy out our starting point */
1358 snprintf(dirbase, sizeof(dirbase), "%s", here);
1359 dirbase_end = dirbase + strlen(dirbase);
1361 /* loop until we determine a result */
1364 /* try and stat(2) it ... */
1365 snprintf(try, sizeof(try), "%s/%s", dirbase, search_path);
1366 if (cached_stat(try, &mst) != -1) {
1368 * success! if we found a file, chop off
1369 * the filename so we return a directory.
1371 if ((mst.mst_mode & S_IFMT) != S_IFDIR) {
1372 try_end = try + strlen(try);
1373 while (try_end > try && *try_end != '/')
1376 *try_end = '\0'; /* chop! */
1379 snprintf(result, result_len, "%s", try);
1384 * nope, we didn't find it. if we used up dirbase we've
1385 * reached the root and failed.
1387 if (dirbase_end == dirbase)
1388 break; /* failed! */
1391 * truncate dirbase from the end to move up a dir
1393 while (dirbase_end > dirbase && *dirbase_end != '/')
1395 *dirbase_end = '\0'; /* chop! */
1397 } /* while (TRUE) */
1403 *-----------------------------------------------------------------------
1405 * Find the modification time of the file described by gn along the
1406 * search path dirSearchPath.
1409 * gn the file whose modification time is desired
1412 * The modification time or 0 if it doesn't exist
1415 * The modification time is placed in the node's mtime slot.
1416 * If the node didn't have a path entry before, and Dir_FindFile
1417 * found one for it, the full name is placed in the path slot.
1418 *-----------------------------------------------------------------------
1421 Dir_MTime(GNode *gn, Boolean recheck)
1423 char *fullName; /* the full pathname of name */
1424 struct make_stat mst; /* buffer for finding the mod time */
1426 if (gn->type & OP_ARCHV) {
1427 return Arch_MTime(gn);
1428 } else if (gn->type & OP_PHONY) {
1431 } else if (gn->path == NULL) {
1432 if (gn->type & OP_NOPATH)
1435 fullName = Dir_FindFile(gn->name, Suff_FindPath(gn));
1436 if (fullName == NULL && gn->flags & FROM_DEPEND &&
1437 !Lst_IsEmpty(gn->implicitParents)) {
1440 cp = strrchr(gn->name, '/');
1443 * This is an implied source, and it may have moved,
1444 * see if we can find it via the current .PATH
1448 fullName = Dir_FindFile(cp, Suff_FindPath(gn));
1451 * Put the found file in gn->path
1452 * so that we give that to the compiler.
1454 gn->path = bmake_strdup(fullName);
1455 if (!Job_RunTarget(".STALE", gn->fname))
1457 "%s: %s, %d: ignoring stale %s for %s, "
1458 "found %s\n", progname, gn->fname,
1460 makeDependfile, gn->name, fullName);
1464 DIR_DEBUG2("Found '%s' as '%s'\n",
1465 gn->name, fullName ? fullName : "(not found)");
1468 fullName = gn->path;
1471 if (fullName == NULL) {
1472 fullName = bmake_strdup(gn->name);
1475 if (cached_stats(&mtimes, fullName, &mst, recheck ? CST_UPDATE : 0) < 0) {
1476 if (gn->type & OP_MEMBER) {
1477 if (fullName != gn->path)
1479 return Arch_MemMTime(gn);
1485 if (fullName && gn->path == NULL) {
1486 gn->path = fullName;
1489 gn->mtime = mst.mst_mtime;
1494 *-----------------------------------------------------------------------
1496 * Add the given name to the end of the given path. The order of
1497 * the arguments is backwards so ParseDoDependency can do a
1498 * Lst_ForEach of its list of paths...
1501 * path the path to which the directory should be
1503 * XXX: Why would this ever be NULL, and what does
1505 * name the name of the directory to add
1511 * A structure is added to the list and the directory is
1513 *-----------------------------------------------------------------------
1516 Dir_AddDir(Lst path, const char *name)
1518 LstNode ln = NULL; /* node in case Path structure is found */
1519 Path *p = NULL; /* pointer to new Path structure */
1520 DIR *d; /* for reading directory */
1521 struct dirent *dp; /* entry in directory */
1523 if (path != NULL && strcmp(name, ".DOTLAST") == 0) {
1524 ln = Lst_Find(path, DirFindName, name);
1526 return LstNode_Datum(ln);
1528 dotLast->refCount++;
1529 Lst_Prepend(path, dotLast);
1533 ln = Lst_Find(openDirectories, DirFindName, name);
1535 p = LstNode_Datum(ln);
1536 if (Lst_FindDatum(path, p) == NULL) {
1538 Lst_Append(path, p);
1543 DIR_DEBUG1("Caching %s ...", name);
1545 if ((d = opendir(name)) != NULL) {
1546 p = bmake_malloc(sizeof(Path));
1547 p->name = bmake_strdup(name);
1550 Hash_InitTable(&p->files, -1);
1552 while ((dp = readdir(d)) != NULL) {
1553 #if defined(sun) && defined(d_ino) /* d_ino is a sunos4 #define for d_fileno */
1555 * The sun directory library doesn't check for a 0 inode
1556 * (0-inode slots just take up space), so we have to do
1559 if (dp->d_fileno == 0) {
1562 #endif /* sun && d_ino */
1563 (void)Hash_CreateEntry(&p->files, dp->d_name, NULL);
1566 Lst_Append(openDirectories, p);
1568 Lst_Append(path, p);
1570 DIR_DEBUG0("done\n");
1575 *-----------------------------------------------------------------------
1577 * Callback function for duplicating a search path via Lst_Copy.
1578 * Ups the reference count for the directory.
1581 * Returns the Path it was given.
1582 *-----------------------------------------------------------------------
1585 Dir_CopyDir(void *p)
1587 ((Path *)p)->refCount += 1;
1593 *-----------------------------------------------------------------------
1595 * Make a string by taking all the directories in the given search
1596 * path and preceding them by the given flag. Used by the suffix
1597 * module to create variables for compilers based on suffix search
1601 * flag flag which should precede each directory
1602 * path list of directories
1605 * The string mentioned above. Note that there is no space between
1606 * the given flag and each directory. The empty string is returned if
1607 * Things don't go well.
1611 *-----------------------------------------------------------------------
1614 Dir_MakeFlags(const char *flag, Lst path)
1617 LstNode ln; /* the node of the current directory */
1623 while ((ln = Lst_Next(path)) != NULL) {
1624 Path *p = LstNode_Datum(ln);
1625 Buf_AddStr(&buf, " ");
1626 Buf_AddStr(&buf, flag);
1627 Buf_AddStr(&buf, p->name);
1632 return Buf_Destroy(&buf, FALSE);
1636 *-----------------------------------------------------------------------
1638 * Nuke a directory descriptor, if possible. Callback procedure
1639 * for the suffixes module when destroying a search path.
1642 * pp The directory descriptor to nuke
1648 * If no other path references this directory (refCount == 0),
1649 * the Path and all its data are freed.
1651 *-----------------------------------------------------------------------
1654 Dir_Destroy(void *pp)
1656 Path *p = (Path *)pp;
1659 if (p->refCount == 0) {
1662 ln = Lst_FindDatum(openDirectories, p);
1663 Lst_Remove(openDirectories, ln);
1665 Hash_DeleteTable(&p->files);
1672 *-----------------------------------------------------------------------
1674 * Clear out all elements of the given search path. This is different
1675 * from destroying the list, notice.
1678 * path Path to clear
1684 * The path is set to the empty list.
1686 *-----------------------------------------------------------------------
1689 Dir_ClearPath(Lst path)
1691 while (!Lst_IsEmpty(path)) {
1692 Path *p = Lst_Dequeue(path);
1699 *-----------------------------------------------------------------------
1701 * Concatenate two paths, adding the second to the end of the first.
1702 * Makes sure to avoid duplicates.
1712 * Reference counts for added dirs are upped.
1714 *-----------------------------------------------------------------------
1717 Dir_Concat(Lst path1, Lst path2)
1722 for (ln = Lst_First(path2); ln != NULL; ln = LstNode_Next(ln)) {
1723 p = LstNode_Datum(ln);
1724 if (Lst_FindDatum(path1, p) == NULL) {
1726 Lst_Append(path1, p);
1732 percentage(int num, int den)
1734 return den != 0 ? num * 100 / den : 0;
1737 /********** DEBUG INFO **********/
1739 Dir_PrintDirectories(void)
1743 fprintf(debug_file, "#*** Directory Cache:\n");
1745 "# Stats: %d hits %d misses %d near misses %d losers (%d%%)\n",
1746 hits, misses, nearmisses, bigmisses,
1747 percentage(hits, hits + bigmisses + nearmisses));
1748 fprintf(debug_file, "# %-20s referenced\thits\n", "directory");
1750 Lst_Open(openDirectories);
1751 while ((ln = Lst_Next(openDirectories)) != NULL) {
1752 Path *p = LstNode_Datum(ln);
1753 fprintf(debug_file, "# %-20s %10d\t%4d\n", p->name, p->refCount,
1756 Lst_Close(openDirectories);
1760 DirPrintDir(void *p, void *dummy MAKE_ATTR_UNUSED)
1762 fprintf(debug_file, "%s ", ((Path *)p)->name);
1767 Dir_PrintPath(Lst path)
1769 Lst_ForEach(path, DirPrintDir, NULL);