Annotation of src/usr.bin/make/dir.c, Revision 1.205
1.205 ! rillig 1: /* $NetBSD: dir.c,v 1.204 2020/11/14 06:10:28 rillig Exp $ */
1.8 christos 2:
1.1 cgd 3: /*
4: * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
1.37 agc 5: * All rights reserved.
6: *
7: * This code is derived from software contributed to Berkeley by
8: * Adam de Boor.
9: *
10: * Redistribution and use in source and binary forms, with or without
11: * modification, are permitted provided that the following conditions
12: * are met:
13: * 1. Redistributions of source code must retain the above copyright
14: * notice, this list of conditions and the following disclaimer.
15: * 2. Redistributions in binary form must reproduce the above copyright
16: * notice, this list of conditions and the following disclaimer in the
17: * documentation and/or other materials provided with the distribution.
18: * 3. Neither the name of the University nor the names of its contributors
19: * may be used to endorse or promote products derived from this software
20: * without specific prior written permission.
21: *
22: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32: * SUCH DAMAGE.
33: */
34:
35: /*
1.1 cgd 36: * Copyright (c) 1988, 1989 by Adam de Boor
37: * Copyright (c) 1989 by Berkeley Softworks
38: * All rights reserved.
39: *
40: * This code is derived from software contributed to Berkeley by
41: * Adam de Boor.
42: *
43: * Redistribution and use in source and binary forms, with or without
44: * modification, are permitted provided that the following conditions
45: * are met:
46: * 1. Redistributions of source code must retain the above copyright
47: * notice, this list of conditions and the following disclaimer.
48: * 2. Redistributions in binary form must reproduce the above copyright
49: * notice, this list of conditions and the following disclaimer in the
50: * documentation and/or other materials provided with the distribution.
51: * 3. All advertising materials mentioning features or use of this software
52: * must display the following acknowledgement:
53: * This product includes software developed by the University of
54: * California, Berkeley and its contributors.
55: * 4. Neither the name of the University nor the names of its contributors
56: * may be used to endorse or promote products derived from this software
57: * without specific prior written permission.
58: *
59: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
60: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
61: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
62: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
63: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
64: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
65: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
66: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
67: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
68: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
69: * SUCH DAMAGE.
70: */
71:
1.191 rillig 72: /* Directory searching using wildcards and/or normal names.
73: * Used both for source wildcarding in the makefile and for finding
74: * implicit sources.
1.1 cgd 75: *
76: * The interface for this module is:
1.149 rillig 77: * Dir_Init Initialize the module.
1.1 cgd 78: *
1.149 rillig 79: * Dir_InitCur Set the cur CachedDir.
1.35 sjg 80: *
1.149 rillig 81: * Dir_InitDot Set the dot CachedDir.
1.35 sjg 82: *
1.163 rillig 83: * Dir_End Clean up the module.
1.6 jtc 84: *
1.149 rillig 85: * Dir_SetPATH Set ${.PATH} to reflect state of dirSearchPath.
1.35 sjg 86: *
1.149 rillig 87: * Dir_HasWildcards
88: * Returns TRUE if the name given it needs to
89: * be wildcard-expanded.
1.1 cgd 90: *
1.149 rillig 91: * Dir_Expand Given a pattern and a path, return a Lst of names
92: * which match the pattern on the search path.
1.1 cgd 93: *
1.149 rillig 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.
1.1 cgd 97: *
1.149 rillig 98: * Dir_FindHereOrAbove
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 ("/").
1.76 rillig 102: *
1.201 rillig 103: * Dir_UpdateMTime
104: * Update the modification time and path of a node with
105: * data from the file corresponding to the node.
1.1 cgd 106: *
1.149 rillig 107: * Dir_AddDir Add a directory to a search path.
1.1 cgd 108: *
1.149 rillig 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.
1.1 cgd 113: *
1.149 rillig 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
117: * search path.
118: *
119: * Dir_ClearPath Resets a search path to the empty list.
1.1 cgd 120: *
121: * For debugging:
1.191 rillig 122: * Dir_PrintDirectories
123: * Print stats about the directory cache.
1.1 cgd 124: */
125:
126: #include <sys/types.h>
1.34 wiz 127: #include <sys/stat.h>
128:
1.5 cgd 129: #include <dirent.h>
1.34 wiz 130: #include <errno.h>
131:
1.1 cgd 132: #include "make.h"
1.5 cgd 133: #include "dir.h"
1.67 christos 134: #include "job.h"
1.1 cgd 135:
1.142 rillig 136: /* "@(#)dir.c 8.2 (Berkeley) 1/2/94" */
1.205 ! rillig 137: MAKE_RCSID("$NetBSD: dir.c,v 1.204 2020/11/14 06:10:28 rillig Exp $");
1.92 rillig 138:
1.151 rillig 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)
1.92 rillig 142:
1.191 rillig 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
149: * must be changed.
150: *
151: * All previously-read directories are kept in openDirs, which is checked
152: * first before a directory is opened.
153: *
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:
161: *
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.
165: *
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
1.205 ! rillig 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.
1.191 rillig 174: *
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.
185: *
186: * An additional thing to consider is that pmake is used primarily to create
1.205 ! rillig 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.
1.191 rillig 192: *
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.
198: *
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
1.201 rillig 207: * the mtime in a cache for when Dir_UpdateMTime was actually called.
1.1 cgd 208: */
209:
1.144 rillig 210: typedef List CachedDirList;
211: typedef ListNode CachedDirListNode;
1.1 cgd 212:
1.144 rillig 213: typedef ListNode SearchPathNode;
214:
215: SearchPath *dirSearchPath; /* main search path */
216:
1.158 rillig 217: /* A list of cached directories, with fast lookup by directory name. */
218: typedef struct OpenDirs {
219: CachedDirList *list;
1.165 rillig 220: HashTable /* of CachedDirListNode */ table;
1.158 rillig 221: } OpenDirs;
222:
223: static void
224: OpenDirs_Init(OpenDirs *odirs)
225: {
1.167 rillig 226: odirs->list = Lst_New();
1.188 rillig 227: HashTable_Init(&odirs->table);
1.158 rillig 228: }
229:
1.175 rillig 230: #ifdef CLEANUP
231: static void
1.158 rillig 232: OpenDirs_Done(OpenDirs *odirs)
233: {
1.159 rillig 234: CachedDirListNode *ln = odirs->list->first;
235: while (ln != NULL) {
1.162 rillig 236: CachedDirListNode *next = ln->next;
237: CachedDir *dir = ln->datum;
238: Dir_Destroy(dir); /* removes the dir from odirs->list */
239: ln = next;
1.159 rillig 240: }
1.158 rillig 241: Lst_Free(odirs->list);
1.188 rillig 242: HashTable_Done(&odirs->table);
1.158 rillig 243: }
1.175 rillig 244: #endif
1.158 rillig 245:
246: static CachedDir *
247: OpenDirs_Find(OpenDirs *odirs, const char *name)
248: {
1.188 rillig 249: CachedDirListNode *ln = HashTable_FindValue(&odirs->table, name);
1.158 rillig 250: return ln != NULL ? ln->datum : NULL;
251: }
252:
253: static void
254: OpenDirs_Add(OpenDirs *odirs, CachedDir *cdir)
255: {
1.188 rillig 256: HashEntry *he = HashTable_FindEntry(&odirs->table, cdir->name);
1.158 rillig 257: if (he != NULL)
258: return;
1.188 rillig 259: he = HashTable_CreateEntry(&odirs->table, cdir->name, NULL);
1.158 rillig 260: Lst_Append(odirs->list, cdir);
1.188 rillig 261: HashEntry_Set(he, odirs->list->last);
1.158 rillig 262: }
263:
264: static void
265: OpenDirs_Remove(OpenDirs *odirs, const char *name)
266: {
1.188 rillig 267: HashEntry *he = HashTable_FindEntry(&odirs->table, name);
1.158 rillig 268: CachedDirListNode *ln;
269: if (he == NULL)
270: return;
1.188 rillig 271: ln = HashEntry_Get(he);
272: HashTable_DeleteEntry(&odirs->table, he);
1.158 rillig 273: Lst_Remove(odirs->list, ln);
274: }
275:
276: static OpenDirs openDirs; /* the list of all open directories */
1.1 cgd 277:
278: /*
1.204 rillig 279: * Variables for gathering statistics on the efficiency of the caching
1.1 cgd 280: * mechanism.
281: */
1.85 rillig 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 */
286:
1.143 rillig 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
1.85 rillig 290: * look for . last */
291:
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.
294: *
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,
298: * but... */
1.165 rillig 299: static HashTable mtimes;
1.1 cgd 300:
1.165 rillig 301: static HashTable lmtimes; /* same as mtimes but for lstat */
1.1 cgd 302:
1.68 sjg 303: /*
1.89 rillig 304: * We use stat(2) a lot, cache the results.
1.68 sjg 305: * mtime and mode are all we care about.
306: */
307: struct cache_st {
1.85 rillig 308: time_t lmtime; /* lstat */
309: time_t mtime; /* stat */
310: mode_t mode;
1.68 sjg 311: };
312:
313: /* minimize changes below */
1.170 rillig 314: typedef enum CachedStatsFlags {
1.198 rillig 315: CST_NONE = 0,
316: CST_LSTAT = 1 << 0, /* call lstat(2) instead of stat(2) */
317: CST_UPDATE = 1 << 1 /* ignore existing cached entry */
1.89 rillig 318: } CachedStatsFlags;
1.68 sjg 319:
1.133 rillig 320: /* Returns 0 and the result of stat(2) or lstat(2) in *mst, or -1 on error. */
1.68 sjg 321: static int
1.165 rillig 322: cached_stats(HashTable *htp, const char *pathname, struct make_stat *mst,
1.89 rillig 323: CachedStatsFlags flags)
1.68 sjg 324: {
1.165 rillig 325: HashEntry *entry;
1.133 rillig 326: struct stat sys_st;
1.68 sjg 327: struct cache_st *cst;
328: int rc;
329:
1.196 rillig 330: if (pathname == NULL || pathname[0] == '\0')
1.68 sjg 331: return -1;
332:
1.188 rillig 333: entry = HashTable_FindEntry(htp, pathname);
1.68 sjg 334:
1.89 rillig 335: if (entry && !(flags & CST_UPDATE)) {
1.188 rillig 336: cst = HashEntry_Get(entry);
1.68 sjg 337:
1.133 rillig 338: mst->mst_mode = cst->mode;
339: mst->mst_mtime = (flags & CST_LSTAT) ? cst->lmtime : cst->mtime;
340: if (mst->mst_mtime) {
1.92 rillig 341: DIR_DEBUG2("Using cached time %s for %s\n",
1.133 rillig 342: Targ_FmtTime(mst->mst_mtime), pathname);
1.74 sjg 343: return 0;
1.73 christos 344: }
1.68 sjg 345: }
346:
1.133 rillig 347: rc = (flags & CST_LSTAT)
348: ? lstat(pathname, &sys_st)
349: : stat(pathname, &sys_st);
1.68 sjg 350: if (rc == -1)
351: return -1;
352:
1.135 rillig 353: if (sys_st.st_mtime == 0)
354: sys_st.st_mtime = 1; /* avoid confusion with missing file */
355:
1.134 rillig 356: mst->mst_mode = sys_st.st_mode;
357: mst->mst_mtime = sys_st.st_mtime;
358:
1.131 rillig 359: if (entry == NULL)
1.188 rillig 360: entry = HashTable_CreateEntry(htp, pathname, NULL);
361: if (HashEntry_Get(entry) == NULL) {
1.194 rillig 362: HashEntry_Set(entry, bmake_malloc(sizeof *cst));
363: memset(HashEntry_Get(entry), 0, sizeof *cst);
1.74 sjg 364: }
1.188 rillig 365: cst = HashEntry_Get(entry);
1.89 rillig 366: if (flags & CST_LSTAT) {
1.133 rillig 367: cst->lmtime = sys_st.st_mtime;
1.74 sjg 368: } else {
1.133 rillig 369: cst->mtime = sys_st.st_mtime;
1.74 sjg 370: }
1.133 rillig 371: cst->mode = sys_st.st_mode;
1.92 rillig 372: DIR_DEBUG2(" Caching %s for %s\n",
1.133 rillig 373: Targ_FmtTime(sys_st.st_mtime), pathname);
1.68 sjg 374:
375: return 0;
376: }
377:
378: int
1.133 rillig 379: cached_stat(const char *pathname, struct make_stat *st)
1.68 sjg 380: {
1.198 rillig 381: return cached_stats(&mtimes, pathname, st, CST_NONE);
1.68 sjg 382: }
383:
384: int
1.133 rillig 385: cached_lstat(const char *pathname, struct make_stat *st)
1.68 sjg 386: {
387: return cached_stats(&lmtimes, pathname, st, CST_LSTAT);
388: }
389:
1.163 rillig 390: /* Initialize the directories module. */
1.1 cgd 391: void
1.97 rillig 392: Dir_Init(void)
393: {
1.167 rillig 394: dirSearchPath = Lst_New();
1.158 rillig 395: OpenDirs_Init(&openDirs);
1.188 rillig 396: HashTable_Init(&mtimes);
397: HashTable_Init(&lmtimes);
1.97 rillig 398: }
399:
400: void
401: Dir_InitDir(const char *cdname)
1.1 cgd 402: {
1.35 sjg 403: Dir_InitCur(cdname);
404:
1.194 rillig 405: dotLast = bmake_malloc(sizeof *dotLast);
1.35 sjg 406: dotLast->refCount = 1;
407: dotLast->hits = 0;
1.56 joerg 408: dotLast->name = bmake_strdup(".DOTLAST");
1.188 rillig 409: HashTable_Init(&dotLast->files);
1.35 sjg 410: }
411:
412: /*
1.97 rillig 413: * Called by Dir_InitDir and whenever .CURDIR is assigned to.
1.35 sjg 414: */
415: void
1.45 christos 416: Dir_InitCur(const char *cdname)
1.35 sjg 417: {
1.143 rillig 418: CachedDir *dir;
1.76 rillig 419:
1.203 rillig 420: if (cdname == NULL)
421: return;
422:
423: /*
424: * Our build directory is not the same as our source directory.
425: * Keep this one around too.
426: */
427: dir = Dir_AddDir(NULL, cdname);
428: if (dir == NULL)
429: return;
430:
431: /* XXX: Reference counting is wrong here.
432: * If this function is called repeatedly with the same directory name,
433: * its reference count increases each time even though the number of
434: * actual references stays the same. */
435:
436: dir->refCount++;
437: if (cur != NULL && cur != dir) {
1.17 gwr 438: /*
1.203 rillig 439: * We've been here before, clean up.
1.17 gwr 440: */
1.203 rillig 441: cur->refCount--;
442: Dir_Destroy(cur);
1.17 gwr 443: }
1.203 rillig 444: cur = dir;
1.28 tv 445: }
446:
1.124 rillig 447: /* (Re)initialize "dot" (current/object directory) path hash.
448: * Some directories may be opened. */
1.28 tv 449: void
1.34 wiz 450: Dir_InitDot(void)
1.28 tv 451: {
452: if (dot != NULL) {
1.158 rillig 453: /* Remove old entry from openDirs, but do not destroy. */
454: OpenDirs_Remove(&openDirs, dot->name);
1.28 tv 455: }
456:
1.45 christos 457: dot = Dir_AddDir(NULL, ".");
1.28 tv 458:
459: if (dot == NULL) {
460: Error("Cannot open `.' (%s)", strerror(errno));
461: exit(1);
462: }
463:
464: /*
465: * We always need to have dot around, so we increment its reference count
466: * to make sure it's not destroyed.
467: */
1.153 rillig 468: dot->refCount++;
1.85 rillig 469: Dir_SetPATH(); /* initialize */
1.1 cgd 470: }
471:
1.163 rillig 472: /* Clean up the directories module. */
1.6 jtc 473: void
1.34 wiz 474: Dir_End(void)
1.6 jtc 475: {
1.24 mycroft 476: #ifdef CLEANUP
1.17 gwr 477: if (cur) {
1.153 rillig 478: cur->refCount--;
1.51 dsl 479: Dir_Destroy(cur);
1.17 gwr 480: }
1.153 rillig 481: dot->refCount--;
482: dotLast->refCount--;
1.51 dsl 483: Dir_Destroy(dotLast);
484: Dir_Destroy(dot);
1.6 jtc 485: Dir_ClearPath(dirSearchPath);
1.119 rillig 486: Lst_Free(dirSearchPath);
1.158 rillig 487: OpenDirs_Done(&openDirs);
1.188 rillig 488: HashTable_Done(&mtimes);
1.24 mycroft 489: #endif
1.6 jtc 490: }
491:
1.35 sjg 492: /*
493: * We want ${.PATH} to indicate the order in which we will actually
494: * search, so we rebuild it after any .PATH: target.
495: * This is the simplest way to deal with the effect of .DOTLAST.
496: */
497: void
1.45 christos 498: Dir_SetPATH(void)
1.35 sjg 499: {
1.144 rillig 500: CachedDirListNode *ln;
1.107 rillig 501: Boolean hasLastDot = FALSE; /* true if we should search dot last */
1.35 sjg 502:
503: Var_Delete(".PATH", VAR_GLOBAL);
1.76 rillig 504:
1.169 rillig 505: if ((ln = dirSearchPath->first) != NULL) {
506: CachedDir *dir = ln->datum;
1.143 rillig 507: if (dir == dotLast) {
1.107 rillig 508: hasLastDot = TRUE;
509: Var_Append(".PATH", dotLast->name, VAR_GLOBAL);
1.35 sjg 510: }
1.107 rillig 511: }
1.35 sjg 512:
1.107 rillig 513: if (!hasLastDot) {
514: if (dot)
515: Var_Append(".PATH", dot->name, VAR_GLOBAL);
516: if (cur)
517: Var_Append(".PATH", cur->name, VAR_GLOBAL);
518: }
1.35 sjg 519:
1.169 rillig 520: for (ln = dirSearchPath->first; ln != NULL; ln = ln->next) {
521: CachedDir *dir = ln->datum;
1.143 rillig 522: if (dir == dotLast)
1.107 rillig 523: continue;
1.143 rillig 524: if (dir == dot && hasLastDot)
1.107 rillig 525: continue;
1.143 rillig 526: Var_Append(".PATH", dir->name, VAR_GLOBAL);
1.107 rillig 527: }
1.35 sjg 528:
1.107 rillig 529: if (hasLastDot) {
530: if (dot)
531: Var_Append(".PATH", dot->name, VAR_GLOBAL);
532: if (cur)
533: Var_Append(".PATH", cur->name, VAR_GLOBAL);
1.35 sjg 534: }
535: }
536:
1.186 rillig 537: /* See if the given name has any wildcard characters in it and all braces and
538: * brackets are properly balanced.
1.124 rillig 539: *
540: * XXX: This code is not 100% correct ([^]] fails etc.). I really don't think
541: * that make(1) should be expanding patterns, because then you have to set a
542: * mechanism for escaping the expansion!
1.1 cgd 543: *
1.186 rillig 544: * Return TRUE if the word should be expanded, FALSE otherwise.
1.1 cgd 545: */
546: Boolean
1.128 rillig 547: Dir_HasWildcards(const char *name)
1.1 cgd 548: {
1.186 rillig 549: const char *p;
1.128 rillig 550: Boolean wild = FALSE;
551: int braces = 0, brackets = 0;
1.12 christos 552:
1.186 rillig 553: for (p = name; *p != '\0'; p++) {
554: switch (*p) {
1.1 cgd 555: case '{':
1.128 rillig 556: braces++;
557: wild = TRUE;
1.85 rillig 558: break;
1.13 christos 559: case '}':
1.128 rillig 560: braces--;
1.85 rillig 561: break;
1.1 cgd 562: case '[':
1.128 rillig 563: brackets++;
564: wild = TRUE;
1.85 rillig 565: break;
1.13 christos 566: case ']':
1.128 rillig 567: brackets--;
1.85 rillig 568: break;
1.1 cgd 569: case '?':
570: case '*':
1.128 rillig 571: wild = TRUE;
1.85 rillig 572: break;
1.13 christos 573: default:
1.85 rillig 574: break;
1.1 cgd 575: }
576: }
1.128 rillig 577: return wild && brackets == 0 && braces == 0;
1.1 cgd 578: }
579:
1.181 rillig 580: /* See if any files match the pattern and add their names to the 'expansions'
581: * list if they do.
582: *
583: * This is incomplete -- wildcards are only expanded in the final path
584: * component, but not in directories like src/lib*c/file*.c, but it
585: * will do for now (now being 1993 until at least 2020). To expand these,
586: * use the ':sh' variable modifier such as in ${:!echo src/lib*c/file*.c!}.
1.1 cgd 587: *
1.34 wiz 588: * Input:
589: * pattern Pattern to look for
1.143 rillig 590: * dir Directory to search
1.34 wiz 591: * expansion Place to store the results
1.1 cgd 592: */
1.98 rillig 593: static void
1.144 rillig 594: DirMatchFiles(const char *pattern, CachedDir *dir, StringList *expansions)
1.1 cgd 595: {
1.181 rillig 596: const char *dirName = dir->name;
597: Boolean isDot = dirName[0] == '.' && dirName[1] == '\0';
1.164 rillig 598: HashIter hi;
1.12 christos 599:
1.202 rillig 600: /* XXX: Iterating over all hash entries is inefficient. If the pattern
601: * is a plain string without any wildcards, a direct lookup is faster. */
602:
1.181 rillig 603: HashIter_Init(&hi, &dir->files);
604: while (HashIter_Next(&hi) != NULL) {
605: const char *base = hi.entry->key;
606:
607: if (!Str_Match(base, pattern))
608: continue;
1.12 christos 609:
1.1 cgd 610: /*
1.181 rillig 611: * Follow the UNIX convention that dot files are only found if the
612: * pattern begins with a dot. The pattern '.*' does not match '.' or
613: * '..' since these are not included in the directory cache.
614: *
1.182 rillig 615: * This means that the pattern '[a-z.]*' does not find '.file', which
616: * is consistent with bash, NetBSD sh and csh.
1.1 cgd 617: */
1.181 rillig 618: if (base[0] == '.' && pattern[0] != '.')
619: continue;
620:
1.1 cgd 621: {
1.181 rillig 622: char *fullName = isDot
623: ? bmake_strdup(base)
624: : str_concat3(dirName, "/", base);
625: Lst_Append(expansions, fullName);
1.1 cgd 626: }
627: }
628: }
629:
1.91 rillig 630: /* Find the next closing brace in the string, taking nested braces into
631: * account. */
1.80 rillig 632: static const char *
633: closing_brace(const char *p)
634: {
635: int nest = 0;
1.91 rillig 636: while (*p != '\0') {
1.106 rillig 637: if (*p == '}' && nest == 0)
1.91 rillig 638: break;
1.80 rillig 639: if (*p == '{')
640: nest++;
641: if (*p == '}')
642: nest--;
643: p++;
644: }
645: return p;
646: }
647:
1.91 rillig 648: /* Find the next closing brace or comma in the string, taking nested braces
649: * into account. */
1.80 rillig 650: static const char *
651: separator_comma(const char *p)
652: {
653: int nest = 0;
1.91 rillig 654: while (*p != '\0') {
1.106 rillig 655: if ((*p == '}' || *p == ',') && nest == 0)
1.91 rillig 656: break;
1.80 rillig 657: if (*p == '{')
658: nest++;
659: if (*p == '}')
660: nest--;
661: p++;
662: }
663: return p;
664: }
665:
666: static Boolean
667: contains_wildcard(const char *p)
668: {
669: for (; *p != '\0'; p++) {
1.85 rillig 670: switch (*p) {
1.80 rillig 671: case '*':
672: case '?':
673: case '{':
674: case '[':
675: return TRUE;
676: }
677: }
678: return FALSE;
679: }
680:
681: static char *
682: concat3(const char *a, size_t a_len, const char *b, size_t b_len,
683: const char *c, size_t c_len)
684: {
685: size_t s_len = a_len + b_len + c_len;
686: char *s = bmake_malloc(s_len + 1);
687: memcpy(s, a, a_len);
688: memcpy(s + a_len, b, b_len);
689: memcpy(s + a_len + b_len, c, c_len);
690: s[s_len] = '\0';
691: return s;
692: }
693:
1.181 rillig 694: /* Expand curly braces like the C shell. Brace expansion by itself is purely
695: * textual, the expansions are not looked up in the file system. But if an
696: * expanded word contains wildcard characters, it is expanded further,
697: * matching only the actually existing files.
698: *
699: * Example: "{a{b,c}}" expands to "ab" and "ac".
700: * Example: "{a}" expands to "a".
701: * Example: "{a,*.c}" expands to "a" and all "*.c" files that exist.
1.1 cgd 702: *
1.34 wiz 703: * Input:
704: * word Entire word to expand
705: * brace First curly brace in it
706: * path Search path to use
707: * expansions Place to store the expansions
1.1 cgd 708: */
709: static void
1.144 rillig 710: DirExpandCurly(const char *word, const char *brace, SearchPath *path,
711: StringList *expansions)
1.1 cgd 712: {
1.90 rillig 713: const char *prefix, *middle, *piece, *middle_end, *suffix;
714: size_t prefix_len, suffix_len;
715:
1.80 rillig 716: /* Split the word into prefix '{' middle '}' suffix. */
1.1 cgd 717:
1.90 rillig 718: middle = brace + 1;
719: middle_end = closing_brace(middle);
1.80 rillig 720: if (*middle_end == '\0') {
721: Error("Unterminated {} clause \"%s\"", middle);
1.1 cgd 722: return;
723: }
1.78 rillig 724:
1.84 rillig 725: prefix = word;
726: prefix_len = (size_t)(brace - prefix);
727: suffix = middle_end + 1;
728: suffix_len = strlen(suffix);
1.80 rillig 729:
730: /* Split the middle into pieces, separated by commas. */
731:
1.84 rillig 732: piece = middle;
1.81 rillig 733: while (piece < middle_end + 1) {
1.80 rillig 734: const char *piece_end = separator_comma(piece);
735: size_t piece_len = (size_t)(piece_end - piece);
1.1 cgd 736:
1.80 rillig 737: char *file = concat3(prefix, prefix_len, piece, piece_len,
738: suffix, suffix_len);
739:
740: if (contains_wildcard(file)) {
741: Dir_Expand(file, path, expansions);
742: free(file);
743: } else {
1.119 rillig 744: Lst_Append(expansions, file);
1.1 cgd 745: }
1.80 rillig 746:
747: piece = piece_end + 1; /* skip over the comma or closing brace */
1.1 cgd 748: }
749: }
750:
751:
1.183 rillig 752: /* Expand the word in each of the directories from the path. */
1.1 cgd 753: static void
1.183 rillig 754: DirExpandPath(const char *word, SearchPath *path, StringList *expansions)
1.1 cgd 755: {
1.144 rillig 756: SearchPathNode *ln;
1.147 rillig 757: for (ln = path->first; ln != NULL; ln = ln->next) {
758: CachedDir *dir = ln->datum;
1.143 rillig 759: DirMatchFiles(word, dir, expansions);
1.1 cgd 760: }
761: }
762:
1.146 rillig 763: static void
1.184 rillig 764: PrintExpansions(StringList *expansions)
1.1 cgd 765: {
1.184 rillig 766: const char *sep = "";
1.147 rillig 767: StringListNode *ln;
1.184 rillig 768: for (ln = expansions->first; ln != NULL; ln = ln->next) {
1.147 rillig 769: const char *word = ln->datum;
1.184 rillig 770: debug_printf("%s%s", sep, word);
771: sep = " ";
1.146 rillig 772: }
1.152 rillig 773: debug_printf("\n");
1.1 cgd 774: }
775:
1.180 rillig 776: /* Expand the given word into a list of words by globbing it, looking in the
777: * directories on the given search path.
1.1 cgd 778: *
1.34 wiz 779: * Input:
780: * word the word to expand
1.180 rillig 781: * path the directories in which to find the files
1.34 wiz 782: * expansions the list on which to place the results
1.1 cgd 783: */
784: void
1.144 rillig 785: Dir_Expand(const char *word, SearchPath *path, StringList *expansions)
1.1 cgd 786: {
1.85 rillig 787: const char *cp;
1.1 cgd 788:
1.112 rillig 789: assert(path != NULL);
790: assert(expansions != NULL);
791:
1.92 rillig 792: DIR_DEBUG1("Expanding \"%s\"... ", word);
1.12 christos 793:
1.5 cgd 794: cp = strchr(word, '{');
1.1 cgd 795: if (cp) {
796: DirExpandCurly(word, cp, path, expansions);
797: } else {
1.5 cgd 798: cp = strchr(word, '/');
1.1 cgd 799: if (cp) {
800: /*
801: * The thing has a directory component -- find the first wildcard
802: * in the string.
803: */
804: for (cp = word; *cp; cp++) {
1.193 rillig 805: if (*cp == '?' || *cp == '[' || *cp == '*') {
1.1 cgd 806: break;
807: }
808: }
1.193 rillig 809:
810: if (*cp != '\0') {
1.1 cgd 811: /*
812: * Back up to the start of the component
813: */
814: while (cp > word && *cp != '/') {
815: cp--;
816: }
817: if (cp != word) {
1.174 rillig 818: char *prefix = bmake_strsedup(word, cp + 1);
1.1 cgd 819: /*
820: * If the glob isn't in the first component, try and find
821: * all the components up to the one with a wildcard.
822: */
1.174 rillig 823: char *dirpath = Dir_FindFile(prefix, path);
824: free(prefix);
1.1 cgd 825: /*
826: * dirpath is null if can't find the leading component
827: * XXX: Dir_FindFile won't find internal components.
828: * i.e. if the path contains ../Etc/Object and we're
829: * looking for Etc, it won't be found. Ah well.
830: * Probably not important.
831: */
1.48 christos 832: if (dirpath != NULL) {
1.5 cgd 833: char *dp = &dirpath[strlen(dirpath) - 1];
834: if (*dp == '/')
835: *dp = '\0';
1.167 rillig 836: path = Lst_New();
1.46 christos 837: (void)Dir_AddDir(path, dirpath);
1.183 rillig 838: DirExpandPath(cp + 1, path, expansions);
1.119 rillig 839: Lst_Free(path);
1.1 cgd 840: }
841: } else {
842: /*
843: * Start the search from the local directory
844: */
1.183 rillig 845: DirExpandPath(word, path, expansions);
1.1 cgd 846: }
847: } else {
848: /*
849: * Return the file -- this should never happen.
850: */
1.183 rillig 851: DirExpandPath(word, path, expansions);
1.1 cgd 852: }
853: } else {
854: /*
855: * First the files in dot
856: */
857: DirMatchFiles(word, dot, expansions);
1.12 christos 858:
1.1 cgd 859: /*
860: * Then the files in every other directory on the path.
861: */
1.183 rillig 862: DirExpandPath(word, path, expansions);
1.1 cgd 863: }
864: }
1.146 rillig 865: if (DEBUG(DIR))
1.184 rillig 866: PrintExpansions(expansions);
1.1 cgd 867: }
868:
1.176 rillig 869: /* Find if the file with the given name exists in the given path.
870: * Return the freshly allocated path to the file, or NULL. */
1.18 christos 871: static char *
1.177 rillig 872: DirLookup(CachedDir *dir, const char *base)
1.18 christos 873: {
1.85 rillig 874: char *file; /* the current filename to check */
1.18 christos 875:
1.143 rillig 876: DIR_DEBUG1(" %s ...\n", dir->name);
1.32 pk 877:
1.188 rillig 878: if (HashTable_FindEntry(&dir->files, base) == NULL)
1.32 pk 879: return NULL;
880:
1.177 rillig 881: file = str_concat3(dir->name, "/", base);
1.92 rillig 882: DIR_DEBUG1(" returning %s\n", file);
1.153 rillig 883: dir->hits++;
884: hits++;
1.32 pk 885: return file;
1.18 christos 886: }
887:
888:
1.185 rillig 889: /* Find if the file with the given name exists in the given directory.
890: * Return the freshly allocated path to the file, or NULL. */
1.18 christos 891: static char *
1.143 rillig 892: DirLookupSubdir(CachedDir *dir, const char *name)
1.18 christos 893: {
1.133 rillig 894: struct make_stat mst;
1.185 rillig 895: char *file = dir == dot ? bmake_strdup(name)
896: : str_concat3(dir->name, "/", name);
1.18 christos 897:
1.92 rillig 898: DIR_DEBUG1("checking %s ...\n", file);
1.18 christos 899:
1.133 rillig 900: if (cached_stat(file, &mst) == 0) {
1.153 rillig 901: nearmisses++;
1.75 rillig 902: return file;
1.18 christos 903: }
1.46 christos 904: free(file);
1.18 christos 905: return NULL;
906: }
907:
1.185 rillig 908: /* Find if the file with the given name exists in the given path.
909: * Return the freshly allocated path to the file, the empty string, or NULL.
910: * Returning the empty string means that the search should be terminated.
1.32 pk 911: */
912: static char *
1.143 rillig 913: DirLookupAbs(CachedDir *dir, const char *name, const char *cp)
1.32 pk 914: {
1.185 rillig 915: const char *dnp; /* pointer into dir->name */
916: const char *np; /* pointer into name */
1.32 pk 917:
1.143 rillig 918: DIR_DEBUG1(" %s ...\n", dir->name);
1.32 pk 919:
1.85 rillig 920: /*
921: * If the file has a leading path component and that component
922: * exactly matches the entire name of the current search
923: * directory, we can attempt another cache lookup. And if we don't
924: * have a hit, we can safely assume the file does not exist at all.
925: */
1.185 rillig 926: for (dnp = dir->name, np = name; *dnp != '\0' && *dnp == *np; dnp++, np++)
1.85 rillig 927: continue;
1.185 rillig 928: if (*dnp != '\0' || np != cp - 1)
1.85 rillig 929: return NULL;
1.32 pk 930:
1.188 rillig 931: if (HashTable_FindEntry(&dir->files, cp) == NULL) {
1.92 rillig 932: DIR_DEBUG0(" must be here but isn't -- returning\n");
1.185 rillig 933: return bmake_strdup(""); /* to terminate the search */
1.85 rillig 934: }
1.32 pk 935:
1.153 rillig 936: dir->hits++;
937: hits++;
1.92 rillig 938: DIR_DEBUG1(" returning %s\n", name);
1.85 rillig 939: return bmake_strdup(name);
1.32 pk 940: }
941:
1.178 rillig 942: /* Find the file given on "." or curdir.
943: * Return the freshly allocated path to the file, or NULL. */
1.21 thorpej 944: static char *
1.178 rillig 945: DirFindDot(const char *name, const char *base)
1.21 thorpej 946: {
947:
1.188 rillig 948: if (HashTable_FindEntry(&dot->files, base) != NULL) {
1.92 rillig 949: DIR_DEBUG0(" in '.'\n");
1.153 rillig 950: hits++;
951: dot->hits++;
1.85 rillig 952: return bmake_strdup(name);
953: }
1.188 rillig 954:
955: if (cur != NULL && HashTable_FindEntry(&cur->files, base) != NULL) {
1.92 rillig 956: DIR_DEBUG1(" in ${.CURDIR} = %s\n", cur->name);
1.153 rillig 957: hits++;
958: cur->hits++;
1.178 rillig 959: return str_concat3(cur->name, "/", base);
1.85 rillig 960: }
1.21 thorpej 961:
1.85 rillig 962: return NULL;
1.21 thorpej 963: }
964:
1.179 rillig 965: /* Find the file with the given name along the given search path.
966: *
967: * If the file is found in a directory that is not on the path
968: * already (either 'name' is absolute or it is a relative path
969: * [ dir1/.../dirn/file ] which exists below one of the directories
970: * already on the search path), its directory is added to the end
971: * of the path, on the assumption that there will be more files in
972: * that directory later on. Sometimes this is true. Sometimes not.
1.1 cgd 973: *
1.34 wiz 974: * Input:
975: * name the file to find
1.179 rillig 976: * path the directories to search, or NULL
1.34 wiz 977: *
1.1 cgd 978: * Results:
1.179 rillig 979: * The freshly allocated path to the file, or NULL.
1.1 cgd 980: */
981: char *
1.144 rillig 982: Dir_FindFile(const char *name, SearchPath *path)
1.1 cgd 983: {
1.144 rillig 984: SearchPathNode *ln;
1.85 rillig 985: char *file; /* the current filename to check */
1.139 rillig 986: const char *base; /* Terminal name of file */
1.144 rillig 987: Boolean hasLastDot = FALSE; /* true if we should search dot last */
1.85 rillig 988: Boolean hasSlash; /* true if 'name' contains a / */
1.133 rillig 989: struct make_stat mst; /* Buffer for stat, if necessary */
1.85 rillig 990: const char *trailing_dot = ".";
1.12 christos 991:
1.1 cgd 992: /*
993: * Find the final component of the name and note whether it has a
994: * slash in it (the name, I mean)
995: */
1.139 rillig 996: base = strrchr(name, '/');
997: if (base) {
1.1 cgd 998: hasSlash = TRUE;
1.153 rillig 999: base++;
1.1 cgd 1000: } else {
1001: hasSlash = FALSE;
1.140 rillig 1002: base = name;
1.1 cgd 1003: }
1.12 christos 1004:
1.92 rillig 1005: DIR_DEBUG1("Searching for %s ...", name);
1.12 christos 1006:
1.112 rillig 1007: if (path == NULL) {
1.92 rillig 1008: DIR_DEBUG0("couldn't open path, file not found\n");
1.153 rillig 1009: misses++;
1.57 dsl 1010: return NULL;
1.1 cgd 1011: }
1.12 christos 1012:
1.168 rillig 1013: if ((ln = path->first) != NULL) {
1014: CachedDir *dir = ln->datum;
1.143 rillig 1015: if (dir == dotLast) {
1.31 reinoud 1016: hasLastDot = TRUE;
1.92 rillig 1017: DIR_DEBUG0("[dot last]...");
1.21 thorpej 1018: }
1.18 christos 1019: }
1.92 rillig 1020: DIR_DEBUG0("\n");
1.18 christos 1021:
1.1 cgd 1022: /*
1.32 pk 1023: * If there's no leading directory components or if the leading
1024: * directory component is exactly `./', consult the cached contents
1025: * of each of the directories on the search path.
1.21 thorpej 1026: */
1.139 rillig 1027: if (!hasSlash || (base - name == 2 && *name == '.')) {
1.85 rillig 1028: /*
1029: * We look through all the directories on the path seeking one which
1030: * contains the final component of the given name. If such a beast
1031: * is found, we concatenate the directory name and the final
1032: * component and return the resulting string. If we don't find any
1033: * such thing, we go on to phase two...
1034: *
1035: * No matter what, we always look for the file in the current
1036: * directory before anywhere else (unless we found the magic
1037: * DOTLAST path, in which case we search it last) and we *do not*
1038: * add the ./ to it if it exists.
1039: * This is so there are no conflicts between what the user
1040: * specifies (fish.c) and what pmake finds (./fish.c).
1041: */
1.178 rillig 1042: if (!hasLastDot && (file = DirFindDot(name, base)) != NULL)
1.85 rillig 1043: return file;
1.32 pk 1044:
1.168 rillig 1045: for (; ln != NULL; ln = ln->next) {
1046: CachedDir *dir = ln->datum;
1.143 rillig 1047: if (dir == dotLast)
1.85 rillig 1048: continue;
1.176 rillig 1049: if ((file = DirLookup(dir, base)) != NULL)
1.85 rillig 1050: return file;
1051: }
1.21 thorpej 1052:
1.178 rillig 1053: if (hasLastDot && (file = DirFindDot(name, base)) != NULL)
1.85 rillig 1054: return file;
1.1 cgd 1055: }
1.12 christos 1056:
1.1 cgd 1057: /*
1.32 pk 1058: * We didn't find the file on any directory in the search path.
1.1 cgd 1059: * If the name doesn't contain a slash, that means it doesn't exist.
1060: * If it *does* contain a slash, however, there is still hope: it
1061: * could be in a subdirectory of one of the members of the search
1062: * path. (eg. /usr/include and sys/types.h. The above search would
1063: * fail to turn up types.h in /usr/include, but it *is* in
1.32 pk 1064: * /usr/include/sys/types.h).
1065: * [ This no longer applies: If we find such a beast, we assume there
1.1 cgd 1066: * will be more (what else can we assume?) and add all but the last
1067: * component of the resulting name onto the search path (at the
1.32 pk 1068: * end).]
1069: * This phase is only performed if the file is *not* absolute.
1.1 cgd 1070: */
1071: if (!hasSlash) {
1.92 rillig 1072: DIR_DEBUG0(" failed.\n");
1.153 rillig 1073: misses++;
1.57 dsl 1074: return NULL;
1.1 cgd 1075: }
1.12 christos 1076:
1.139 rillig 1077: if (*base == '\0') {
1.63 sjg 1078: /* we were given a trailing "/" */
1.139 rillig 1079: base = trailing_dot;
1.63 sjg 1080: }
1081:
1.32 pk 1082: if (name[0] != '/') {
1.85 rillig 1083: Boolean checkedDot = FALSE;
1.12 christos 1084:
1.92 rillig 1085: DIR_DEBUG0(" Trying subdirectories...\n");
1.18 christos 1086:
1.35 sjg 1087: if (!hasLastDot) {
1.85 rillig 1088: if (dot) {
1089: checkedDot = TRUE;
1090: if ((file = DirLookupSubdir(dot, name)) != NULL)
1091: return file;
1092: }
1093: if (cur && (file = DirLookupSubdir(cur, name)) != NULL)
1094: return file;
1.35 sjg 1095: }
1.18 christos 1096:
1.168 rillig 1097: for (ln = path->first; ln != NULL; ln = ln->next) {
1098: CachedDir *dir = ln->datum;
1.143 rillig 1099: if (dir == dotLast)
1.21 thorpej 1100: continue;
1.143 rillig 1101: if (dir == dot) {
1.85 rillig 1102: if (checkedDot)
1103: continue;
1.1 cgd 1104: checkedDot = TRUE;
1.35 sjg 1105: }
1.168 rillig 1106: if ((file = DirLookupSubdir(dir, name)) != NULL)
1.18 christos 1107: return file;
1.1 cgd 1108: }
1.12 christos 1109:
1.35 sjg 1110: if (hasLastDot) {
1.85 rillig 1111: if (dot && !checkedDot) {
1112: checkedDot = TRUE;
1113: if ((file = DirLookupSubdir(dot, name)) != NULL)
1114: return file;
1115: }
1116: if (cur && (file = DirLookupSubdir(cur, name)) != NULL)
1117: return file;
1.35 sjg 1118: }
1.21 thorpej 1119:
1.1 cgd 1120: if (checkedDot) {
1121: /*
1122: * Already checked by the given name, since . was in the path,
1123: * so no point in proceeding...
1124: */
1.92 rillig 1125: DIR_DEBUG0(" Checked . already, returning NULL\n");
1.57 dsl 1126: return NULL;
1.32 pk 1127: }
1128:
1129: } else { /* name[0] == '/' */
1130:
1131: /*
1132: * For absolute names, compare directory path prefix against the
1133: * the directory path of each member on the search path for an exact
1134: * match. If we have an exact match on any member of the search path,
1135: * use the cached contents of that member to lookup the final file
1136: * component. If that lookup fails we can safely assume that the
1137: * file does not exist at all. This is signified by DirLookupAbs()
1138: * returning an empty string.
1139: */
1.92 rillig 1140: DIR_DEBUG0(" Trying exact path matches...\n");
1.32 pk 1141:
1.85 rillig 1142: if (!hasLastDot && cur &&
1.139 rillig 1143: ((file = DirLookupAbs(cur, name, base)) != NULL)) {
1.71 riastrad 1144: if (file[0] == '\0') {
1145: free(file);
1146: return NULL;
1147: }
1148: return file;
1149: }
1.32 pk 1150:
1.168 rillig 1151: for (ln = path->first; ln != NULL; ln = ln->next) {
1152: CachedDir *dir = ln->datum;
1.143 rillig 1153: if (dir == dotLast)
1.32 pk 1154: continue;
1.143 rillig 1155: if ((file = DirLookupAbs(dir, name, base)) != NULL) {
1.71 riastrad 1156: if (file[0] == '\0') {
1157: free(file);
1158: return NULL;
1159: }
1160: return file;
1.32 pk 1161: }
1162: }
1163:
1.85 rillig 1164: if (hasLastDot && cur &&
1.139 rillig 1165: ((file = DirLookupAbs(cur, name, base)) != NULL)) {
1.71 riastrad 1166: if (file[0] == '\0') {
1167: free(file);
1168: return NULL;
1169: }
1170: return file;
1171: }
1.1 cgd 1172: }
1.12 christos 1173:
1.1 cgd 1174: /*
1175: * Didn't find it that way, either. Sigh. Phase 3. Add its directory
1176: * onto the search path in any case, just in case, then look for the
1177: * thing in the hash table. If we find it, grand. We return a new
1178: * copy of the name. Otherwise we sadly return a NULL pointer. Sigh.
1179: * Note that if the directory holding the file doesn't exist, this will
1180: * do an extra search of the final directory on the path. Unless something
1181: * weird happens, this search won't succeed and life will be groovy.
1182: *
1183: * Sigh. We cannot add the directory onto the search path because
1184: * of this amusing case:
1185: * $(INSTALLDIR)/$(FILE): $(FILE)
1186: *
1187: * $(FILE) exists in $(INSTALLDIR) but not in the current one.
1188: * When searching for $(FILE), we will find it in $(INSTALLDIR)
1189: * b/c we added it here. This is not good...
1190: */
1.196 rillig 1191: #if 0
1.139 rillig 1192: if (base == trailing_dot) {
1193: base = strrchr(name, '/');
1.153 rillig 1194: base++;
1.63 sjg 1195: }
1.139 rillig 1196: base[-1] = '\0';
1.46 christos 1197: (void)Dir_AddDir(path, name);
1.139 rillig 1198: base[-1] = '/';
1.12 christos 1199:
1.153 rillig 1200: bigmisses++;
1.119 rillig 1201: ln = Lst_Last(path);
1.57 dsl 1202: if (ln == NULL) {
1203: return NULL;
1.1 cgd 1204: } else {
1.143 rillig 1205: dir = LstNode_Datum(ln);
1.1 cgd 1206: }
1.12 christos 1207:
1.143 rillig 1208: if (Hash_FindEntry(&dir->files, base) != NULL) {
1.75 rillig 1209: return bmake_strdup(name);
1.1 cgd 1210: } else {
1.57 dsl 1211: return NULL;
1.1 cgd 1212: }
1.196 rillig 1213: #else
1.92 rillig 1214: DIR_DEBUG1(" Looking for \"%s\" ...\n", name);
1.12 christos 1215:
1.153 rillig 1216: bigmisses++;
1.133 rillig 1217: if (cached_stat(name, &mst) == 0) {
1.75 rillig 1218: return bmake_strdup(name);
1.1 cgd 1219: }
1.73 christos 1220:
1.92 rillig 1221: DIR_DEBUG0(" failed. Returning NULL\n");
1.73 christos 1222: return NULL;
1.196 rillig 1223: #endif
1.1 cgd 1224: }
1225:
1.40 chuck 1226:
1.161 rillig 1227: /* Search for a path starting at a given directory and then working our way
1228: * up towards the root.
1.40 chuck 1229: *
1230: * Input:
1231: * here starting directory
1.161 rillig 1232: * search_path the relative path we are looking for
1.40 chuck 1233: *
1234: * Results:
1.161 rillig 1235: * The found path, or NULL.
1.40 chuck 1236: */
1.161 rillig 1237: char *
1238: Dir_FindHereOrAbove(const char *here, const char *search_path)
1.85 rillig 1239: {
1.133 rillig 1240: struct make_stat mst;
1.161 rillig 1241: char *dirbase, *dirbase_end;
1242: char *try, *try_end;
1.85 rillig 1243:
1244: /* copy out our starting point */
1.161 rillig 1245: dirbase = bmake_strdup(here);
1.129 rillig 1246: dirbase_end = dirbase + strlen(dirbase);
1.85 rillig 1247:
1248: /* loop until we determine a result */
1.161 rillig 1249: for (;;) {
1.85 rillig 1250:
1251: /* try and stat(2) it ... */
1.161 rillig 1252: try = str_concat3(dirbase, "/", search_path);
1.133 rillig 1253: if (cached_stat(try, &mst) != -1) {
1.85 rillig 1254: /*
1255: * success! if we found a file, chop off
1256: * the filename so we return a directory.
1257: */
1.133 rillig 1258: if ((mst.mst_mode & S_IFMT) != S_IFDIR) {
1.85 rillig 1259: try_end = try + strlen(try);
1260: while (try_end > try && *try_end != '/')
1261: try_end--;
1262: if (try_end > try)
1.129 rillig 1263: *try_end = '\0'; /* chop! */
1.85 rillig 1264: }
1.40 chuck 1265:
1.161 rillig 1266: free(dirbase);
1267: return try;
1.85 rillig 1268: }
1.161 rillig 1269: free(try);
1.40 chuck 1270:
1.85 rillig 1271: /*
1272: * nope, we didn't find it. if we used up dirbase we've
1273: * reached the root and failed.
1274: */
1.129 rillig 1275: if (dirbase_end == dirbase)
1.85 rillig 1276: break; /* failed! */
1.40 chuck 1277:
1.85 rillig 1278: /*
1279: * truncate dirbase from the end to move up a dir
1280: */
1.129 rillig 1281: while (dirbase_end > dirbase && *dirbase_end != '/')
1282: dirbase_end--;
1283: *dirbase_end = '\0'; /* chop! */
1.161 rillig 1284: }
1.40 chuck 1285:
1.161 rillig 1286: free(dirbase);
1287: return NULL;
1.40 chuck 1288: }
1289:
1.201 rillig 1290: /* Search gn along dirSearchPath and store its modification time in gn->mtime.
1291: * If no file is found, store 0 instead.
1.12 christos 1292: *
1.201 rillig 1293: * The found file is stored in gn->path, unless the node already had a path. */
1294: void
1295: Dir_UpdateMTime(GNode *gn, Boolean recheck)
1.1 cgd 1296: {
1.85 rillig 1297: char *fullName; /* the full pathname of name */
1.133 rillig 1298: struct make_stat mst; /* buffer for finding the mod time */
1.198 rillig 1299: CachedStatsFlags flags;
1.12 christos 1300:
1.1 cgd 1301: if (gn->type & OP_ARCHV) {
1.200 rillig 1302: Arch_UpdateMTime(gn);
1.201 rillig 1303: return;
1304: }
1305:
1306: if (gn->type & OP_PHONY) {
1.33 pk 1307: gn->mtime = 0;
1.201 rillig 1308: return;
1309: }
1310:
1311: if (gn->path == NULL) {
1.33 pk 1312: if (gn->type & OP_NOPATH)
1.16 mycroft 1313: fullName = NULL;
1.53 dsl 1314: else {
1.45 christos 1315: fullName = Dir_FindFile(gn->name, Suff_FindPath(gn));
1.62 sjg 1316: if (fullName == NULL && gn->flags & FROM_DEPEND &&
1.127 rillig 1317: !Lst_IsEmpty(gn->implicitParents)) {
1.62 sjg 1318: char *cp;
1319:
1320: cp = strrchr(gn->name, '/');
1321: if (cp) {
1322: /*
1323: * This is an implied source, and it may have moved,
1324: * see if we can find it via the current .PATH
1325: */
1326: cp++;
1.76 rillig 1327:
1.62 sjg 1328: fullName = Dir_FindFile(cp, Suff_FindPath(gn));
1329: if (fullName) {
1330: /*
1331: * Put the found file in gn->path
1332: * so that we give that to the compiler.
1333: */
1334: gn->path = bmake_strdup(fullName);
1.67 christos 1335: if (!Job_RunTarget(".STALE", gn->fname))
1336: fprintf(stdout,
1.85 rillig 1337: "%s: %s, %d: ignoring stale %s for %s, "
1338: "found %s\n", progname, gn->fname,
1339: gn->lineno,
1340: makeDependfile, gn->name, fullName);
1.62 sjg 1341: }
1342: }
1343: }
1.92 rillig 1344: DIR_DEBUG2("Found '%s' as '%s'\n",
1345: gn->name, fullName ? fullName : "(not found)");
1.53 dsl 1346: }
1.1 cgd 1347: } else {
1348: fullName = gn->path;
1349: }
1.12 christos 1350:
1.198 rillig 1351: if (fullName == NULL)
1.56 joerg 1352: fullName = bmake_strdup(gn->name);
1.1 cgd 1353:
1.198 rillig 1354: flags = recheck ? CST_UPDATE : CST_NONE;
1355: if (cached_stats(&mtimes, fullName, &mst, flags) < 0) {
1.1 cgd 1356: if (gn->type & OP_MEMBER) {
1.6 jtc 1357: if (fullName != gn->path)
1358: free(fullName);
1.199 rillig 1359: Arch_UpdateMemberMTime(gn);
1.201 rillig 1360: return;
1.1 cgd 1361: }
1.198 rillig 1362:
1363: mst.mst_mtime = 0;
1.1 cgd 1364: }
1.68 sjg 1365:
1.189 rillig 1366: if (fullName != NULL && gn->path == NULL)
1.1 cgd 1367: gn->path = fullName;
1.12 christos 1368:
1.133 rillig 1369: gn->mtime = mst.mst_mtime;
1.1 cgd 1370: }
1371:
1.150 rillig 1372: /* Read the list of filenames in the directory and store the result
1373: * in openDirectories.
1374: *
1375: * If a path is given, append the directory to that path.
1.1 cgd 1376: *
1.34 wiz 1377: * Input:
1.150 rillig 1378: * path The path to which the directory should be
1379: * added, or NULL to only add the directory to
1380: * openDirectories
1381: * name The name of the directory to add.
1382: * The name is not normalized in any way.
1.1 cgd 1383: */
1.143 rillig 1384: CachedDir *
1.144 rillig 1385: Dir_AddDir(SearchPath *path, const char *name)
1.1 cgd 1386: {
1.143 rillig 1387: CachedDir *dir = NULL; /* the added directory */
1.144 rillig 1388: DIR *d;
1389: struct dirent *dp;
1.21 thorpej 1390:
1.120 rillig 1391: if (path != NULL && strcmp(name, ".DOTLAST") == 0) {
1.173 rillig 1392: SearchPathNode *ln;
1393:
1.203 rillig 1394: /* XXX: Linear search gets slow with thousands of entries. */
1.173 rillig 1395: for (ln = path->first; ln != NULL; ln = ln->next) {
1396: CachedDir *pathDir = ln->datum;
1397: if (strcmp(pathDir->name, name) == 0)
1398: return pathDir;
1399: }
1.120 rillig 1400:
1401: dotLast->refCount++;
1402: Lst_Prepend(path, dotLast);
1.21 thorpej 1403: }
1.12 christos 1404:
1.120 rillig 1405: if (path != NULL)
1.158 rillig 1406: dir = OpenDirs_Find(&openDirs, name);
1407: if (dir != NULL) {
1.143 rillig 1408: if (Lst_FindDatum(path, dir) == NULL) {
1.153 rillig 1409: dir->refCount++;
1.143 rillig 1410: Lst_Append(path, dir);
1.1 cgd 1411: }
1.143 rillig 1412: return dir;
1.120 rillig 1413: }
1414:
1415: DIR_DEBUG1("Caching %s ...", name);
1.12 christos 1416:
1.120 rillig 1417: if ((d = opendir(name)) != NULL) {
1.194 rillig 1418: dir = bmake_malloc(sizeof *dir);
1.143 rillig 1419: dir->name = bmake_strdup(name);
1420: dir->hits = 0;
1421: dir->refCount = 1;
1.188 rillig 1422: HashTable_Init(&dir->files);
1.12 christos 1423:
1.120 rillig 1424: while ((dp = readdir(d)) != NULL) {
1.10 christos 1425: #if defined(sun) && defined(d_ino) /* d_ino is a sunos4 #define for d_fileno */
1.120 rillig 1426: /*
1427: * The sun directory library doesn't check for a 0 inode
1428: * (0-inode slots just take up space), so we have to do
1429: * it ourselves.
1430: */
1431: if (dp->d_fileno == 0) {
1432: continue;
1433: }
1.10 christos 1434: #endif /* sun && d_ino */
1.188 rillig 1435: (void)HashTable_CreateEntry(&dir->files, dp->d_name, NULL);
1.1 cgd 1436: }
1.120 rillig 1437: (void)closedir(d);
1.158 rillig 1438: OpenDirs_Add(&openDirs, dir);
1.120 rillig 1439: if (path != NULL)
1.143 rillig 1440: Lst_Append(path, dir);
1.1 cgd 1441: }
1.120 rillig 1442: DIR_DEBUG0("done\n");
1.143 rillig 1443: return dir;
1.1 cgd 1444: }
1445:
1.187 rillig 1446: /* Return a copy of dirSearchPath, incrementing the reference counts for
1447: * the contained directories. */
1448: SearchPath *
1449: Dir_CopyDirSearchPath(void)
1.1 cgd 1450: {
1.187 rillig 1451: SearchPath *path = Lst_New();
1452: SearchPathNode *ln;
1453: for (ln = dirSearchPath->first; ln != NULL; ln = ln->next) {
1454: CachedDir *dir = ln->datum;
1455: dir->refCount++;
1.192 rillig 1456: Lst_Append(path, dir);
1.187 rillig 1457: }
1458: return path;
1.1 cgd 1459: }
1460:
1461: /*-
1462: *-----------------------------------------------------------------------
1463: * Dir_MakeFlags --
1464: * Make a string by taking all the directories in the given search
1465: * path and preceding them by the given flag. Used by the suffix
1466: * module to create variables for compilers based on suffix search
1467: * paths.
1468: *
1.34 wiz 1469: * Input:
1470: * flag flag which should precede each directory
1471: * path list of directories
1472: *
1.1 cgd 1473: * Results:
1474: * The string mentioned above. Note that there is no space between
1475: * the given flag and each directory. The empty string is returned if
1476: * Things don't go well.
1477: *
1478: * Side Effects:
1479: * None
1480: *-----------------------------------------------------------------------
1481: */
1482: char *
1.144 rillig 1483: Dir_MakeFlags(const char *flag, SearchPath *path)
1.1 cgd 1484: {
1.88 rillig 1485: Buffer buf;
1.144 rillig 1486: SearchPathNode *ln;
1.12 christos 1487:
1.197 rillig 1488: Buf_Init(&buf);
1.12 christos 1489:
1.112 rillig 1490: if (path != NULL) {
1.147 rillig 1491: for (ln = path->first; ln != NULL; ln = ln->next) {
1492: CachedDir *dir = ln->datum;
1.88 rillig 1493: Buf_AddStr(&buf, " ");
1494: Buf_AddStr(&buf, flag);
1.143 rillig 1495: Buf_AddStr(&buf, dir->name);
1.1 cgd 1496: }
1497: }
1.12 christos 1498:
1.88 rillig 1499: return Buf_Destroy(&buf, FALSE);
1.1 cgd 1500: }
1501:
1.190 rillig 1502: /* Nuke a directory descriptor, if possible. Callback procedure for the
1503: * suffixes module when destroying a search path.
1.1 cgd 1504: *
1.34 wiz 1505: * Input:
1.143 rillig 1506: * dirp The directory descriptor to nuke
1.1 cgd 1507: */
1508: void
1.143 rillig 1509: Dir_Destroy(void *dirp)
1.1 cgd 1510: {
1.143 rillig 1511: CachedDir *dir = dirp;
1.153 rillig 1512: dir->refCount--;
1.1 cgd 1513:
1.143 rillig 1514: if (dir->refCount == 0) {
1.158 rillig 1515: OpenDirs_Remove(&openDirs, dir->name);
1.1 cgd 1516:
1.188 rillig 1517: HashTable_Done(&dir->files);
1.143 rillig 1518: free(dir->name);
1519: free(dir);
1.1 cgd 1520: }
1521: }
1522:
1.190 rillig 1523: /* Clear out all elements from the given search path.
1524: * The path is set to the empty list but is not destroyed. */
1.1 cgd 1525: void
1.144 rillig 1526: Dir_ClearPath(SearchPath *path)
1.1 cgd 1527: {
1.119 rillig 1528: while (!Lst_IsEmpty(path)) {
1.143 rillig 1529: CachedDir *dir = Lst_Dequeue(path);
1530: Dir_Destroy(dir);
1.1 cgd 1531: }
1532: }
1.12 christos 1533:
1.1 cgd 1534:
1.190 rillig 1535: /* Concatenate two paths, adding the second to the end of the first,
1536: * skipping duplicates. */
1.1 cgd 1537: void
1.190 rillig 1538: Dir_Concat(SearchPath *dst, SearchPath *src)
1.1 cgd 1539: {
1.144 rillig 1540: SearchPathNode *ln;
1.1 cgd 1541:
1.190 rillig 1542: for (ln = src->first; ln != NULL; ln = ln->next) {
1.148 rillig 1543: CachedDir *dir = ln->datum;
1.190 rillig 1544: if (Lst_FindDatum(dst, dir) == NULL) {
1.153 rillig 1545: dir->refCount++;
1.190 rillig 1546: Lst_Append(dst, dir);
1.1 cgd 1547: }
1548: }
1549: }
1550:
1.105 rillig 1551: static int
1552: percentage(int num, int den)
1553: {
1554: return den != 0 ? num * 100 / den : 0;
1555: }
1556:
1.1 cgd 1557: /********** DEBUG INFO **********/
1.5 cgd 1558: void
1.34 wiz 1559: Dir_PrintDirectories(void)
1.1 cgd 1560: {
1.144 rillig 1561: CachedDirListNode *ln;
1.12 christos 1562:
1.152 rillig 1563: debug_printf("#*** Directory Cache:\n");
1564: debug_printf("# Stats: %d hits %d misses %d near misses %d losers (%d%%)\n",
1565: hits, misses, nearmisses, bigmisses,
1566: percentage(hits, hits + bigmisses + nearmisses));
1567: debug_printf("# %-20s referenced\thits\n", "directory");
1.112 rillig 1568:
1.158 rillig 1569: for (ln = openDirs.list->first; ln != NULL; ln = ln->next) {
1.147 rillig 1570: CachedDir *dir = ln->datum;
1.152 rillig 1571: debug_printf("# %-20s %10d\t%4d\n", dir->name, dir->refCount,
1572: dir->hits);
1.1 cgd 1573: }
1574: }
1575:
1.5 cgd 1576: void
1.144 rillig 1577: Dir_PrintPath(SearchPath *path)
1.1 cgd 1578: {
1.146 rillig 1579: SearchPathNode *node;
1.148 rillig 1580: for (node = path->first; node != NULL; node = node->next) {
1581: const CachedDir *dir = node->datum;
1.152 rillig 1582: debug_printf("%s ", dir->name);
1.146 rillig 1583: }
1.1 cgd 1584: }
CVSweb <webmaster@jp.NetBSD.org>