Annotation of src/usr.bin/make/dir.c, Revision 1.250
1.250 ! rillig 1: /* $NetBSD: dir.c,v 1.249 2020/12/04 14:39:56 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.224 rillig 109: * SearchPath_ToFlags
110: * Given a search path and a command flag, create
1.149 rillig 111: * a string with each of the directories in the path
112: * preceded by the command flag and all of them
113: * separated by a space.
1.1 cgd 114: *
1.149 rillig 115: * Dir_Destroy Destroy an element of a search path. Frees up all
116: * things that can be freed for the element as long
117: * as the element is no longer referenced by any other
118: * search path.
119: *
1.224 rillig 120: * SearchPath_Clear
121: * Resets a search path to the empty list.
1.1 cgd 122: *
123: * For debugging:
1.191 rillig 124: * Dir_PrintDirectories
125: * Print stats about the directory cache.
1.1 cgd 126: */
127:
128: #include <sys/types.h>
1.34 wiz 129: #include <sys/stat.h>
130:
1.5 cgd 131: #include <dirent.h>
1.34 wiz 132: #include <errno.h>
133:
1.1 cgd 134: #include "make.h"
1.5 cgd 135: #include "dir.h"
1.67 christos 136: #include "job.h"
1.1 cgd 137:
1.142 rillig 138: /* "@(#)dir.c 8.2 (Berkeley) 1/2/94" */
1.250 ! rillig 139: MAKE_RCSID("$NetBSD: dir.c,v 1.249 2020/12/04 14:39:56 rillig Exp $");
1.92 rillig 140:
1.191 rillig 141: /* A search path is a list of CachedDir structures. A CachedDir has in it the
142: * name of the directory and the names of all the files in the directory.
143: * This is used to cut down on the number of system calls necessary to find
144: * implicit dependents and their like. Since these searches are made before
145: * any actions are taken, we need not worry about the directory changing due
146: * to creation commands. If this hampers the style of some makefiles, they
147: * must be changed.
148: *
149: * All previously-read directories are kept in openDirs, which is checked
150: * first before a directory is opened.
151: *
152: * The need for the caching of whole directories is brought about by the
153: * multi-level transformation code in suff.c, which tends to search for far
154: * more files than regular make does. In the initial implementation, the
155: * amount of time spent performing "stat" calls was truly astronomical.
156: * The problem with caching at the start is, of course, that pmake doesn't
157: * then detect changes to these directories during the course of the make.
158: * Three possibilities suggest themselves:
159: *
160: * 1) just use stat to test for a file's existence. As mentioned above,
161: * this is very inefficient due to the number of checks engendered by
162: * the multi-level transformation code.
163: *
164: * 2) use readdir() and company to search the directories, keeping them
165: * open between checks. I have tried this and while it didn't slow down
166: * the process too much, it could severely affect the amount of
167: * parallelism available as each directory open would take another file
168: * descriptor out of play for handling I/O for another job. Given that
1.205 rillig 169: * it is only recently (as of 1993 or earlier) that UNIX OS's have taken
170: * to allowing more than 20 or 32 file descriptors for a process, this
171: * doesn't seem acceptable to me.
1.191 rillig 172: *
173: * 3) record the mtime of the directory in the CachedDir structure and
174: * verify the directory hasn't changed since the contents were cached.
175: * This will catch the creation or deletion of files, but not the
176: * updating of files. However, since it is the creation and deletion
177: * that is the problem, this could be a good thing to do. Unfortunately,
178: * if the directory (say ".") were fairly large and changed fairly
179: * frequently, the constant reloading could seriously degrade
180: * performance. It might be good in such cases to keep track of the
181: * number of reloadings and if the number goes over a (small) limit,
182: * resort to using stat in its place.
183: *
184: * An additional thing to consider is that pmake is used primarily to create
1.205 rillig 185: * C programs and until recently (as of 1993 or earlier) pcc-based compilers
186: * refused to allow you to specify where the resulting object file should be
187: * placed. This forced all objects to be created in the current directory.
188: * This isn't meant as a full excuse, just an explanation of some of the
189: * reasons for the caching used here.
1.191 rillig 190: *
191: * One more note: the location of a target's file is only performed on the
192: * downward traversal of the graph and then only for terminal nodes in the
193: * graph. This could be construed as wrong in some cases, but prevents
194: * inadvertent modification of files when the "installed" directory for a
195: * file is provided in the search path.
196: *
197: * Another data structure maintained by this module is an mtime cache used
198: * when the searching of cached directories fails to find a file. In the past,
199: * Dir_FindFile would simply perform an access() call in such a case to
200: * determine if the file could be found using just the name given. When this
201: * hit, however, all that was gained was the knowledge that the file existed.
202: * Given that an access() is essentially a stat() without the copyout() call,
203: * and that the same filesystem overhead would have to be incurred in
204: * Dir_MTime, it made sense to replace the access() with a stat() and record
1.201 rillig 205: * the mtime in a cache for when Dir_UpdateMTime was actually called.
1.1 cgd 206: */
207:
1.144 rillig 208:
1.229 rillig 209: /* A cache for the filenames in a directory. */
210: struct CachedDir {
211: /*
212: * Name of directory, either absolute or relative to the current
213: * directory. The name is not normalized in any way, that is, "."
214: * and "./." are different.
215: *
216: * Not sure what happens when .CURDIR is assigned a new value; see
217: * Parse_DoVar.
218: */
219: char *name;
220:
221: /*
1.233 rillig 222: * The number of SearchPaths that refer to this directory.
223: * Plus the number of global variables that refer to this directory.
1.234 rillig 224: * References from openDirs do not count though.
1.229 rillig 225: */
226: int refCount;
227:
228: /* The number of times a file in this directory has been found. */
229: int hits;
230:
1.243 rillig 231: /* The names of the directory entries. */
1.229 rillig 232: HashSet files;
233: };
234:
1.232 rillig 235: typedef List CachedDirList;
236: typedef ListNode CachedDirListNode;
237:
238: typedef ListNode SearchPathNode;
1.144 rillig 239:
1.158 rillig 240: /* A list of cached directories, with fast lookup by directory name. */
241: typedef struct OpenDirs {
1.227 rillig 242: CachedDirList list;
1.212 rillig 243: HashTable /* of CachedDirListNode */ table;
1.158 rillig 244: } OpenDirs;
245:
1.232 rillig 246: typedef enum CachedStatsFlags {
247: CST_NONE = 0,
248: CST_LSTAT = 1 << 0, /* call lstat(2) instead of stat(2) */
249: CST_UPDATE = 1 << 1 /* ignore existing cached entry */
250: } CachedStatsFlags;
251:
252:
253: SearchPath dirSearchPath = LST_INIT; /* main search path */
254:
255: static OpenDirs openDirs; /* all cached directories */
256:
257: /*
258: * Variables for gathering statistics on the efficiency of the caching
259: * mechanism.
260: */
261: static int hits; /* Found in directory cache */
262: static int misses; /* Sad, but not evil misses */
263: static int nearmisses; /* Found under search path */
264: static int bigmisses; /* Sought by itself */
265:
1.244 rillig 266: /* The cached contents of ".", the relative current directory. */
267: static CachedDir *dot = NULL;
268: /* The cached contents of the absolute current directory. */
269: static CachedDir *cur = NULL;
1.240 rillig 270: /* A fake path entry indicating we need to look for '.' last. */
271: static CachedDir *dotLast = NULL;
1.232 rillig 272:
273: /* Results of doing a last-resort stat in Dir_FindFile -- if we have to go to
274: * the system to find the file, we might as well have its mtime on record.
275: *
276: * XXX: If this is done way early, there's a chance other rules will have
277: * already updated the file, in which case we'll update it again. Generally,
278: * there won't be two rules to update a single file, so this should be ok,
279: * but... */
280: static HashTable mtimes;
281:
282: static HashTable lmtimes; /* same as mtimes but for lstat */
283:
284:
1.238 rillig 285: static void OpenDirs_Remove(OpenDirs *, const char *);
1.232 rillig 286:
287:
1.233 rillig 288: static CachedDir *
289: CachedDir_New(const char *name)
290: {
291: CachedDir *dir = bmake_malloc(sizeof *dir);
292:
293: dir->name = bmake_strdup(name);
294: dir->refCount = 0;
295: dir->hits = 0;
296: HashSet_Init(&dir->files);
297:
1.241 rillig 298: #ifdef DEBUG_REFCNT
299: DEBUG2(DIR, "CachedDir %p new for \"%s\"\n", dir, dir->name);
300: #endif
301:
1.233 rillig 302: return dir;
303: }
304:
305: static CachedDir *
306: CachedDir_Ref(CachedDir *dir)
307: {
308: dir->refCount++;
1.241 rillig 309:
310: #ifdef DEBUG_REFCNT
311: DEBUG3(DIR, "CachedDir %p ++ %d for \"%s\"\n",
312: dir, dir->refCount, dir->name);
313: #endif
314:
1.233 rillig 315: return dir;
316: }
317:
1.238 rillig 318: static void
1.241 rillig 319: CachedDir_Unref(CachedDir *dir)
1.238 rillig 320: {
1.241 rillig 321: dir->refCount--;
322:
323: #ifdef DEBUG_REFCNT
324: DEBUG3(DIR, "CachedDir %p -- %d for \"%s\"\n",
325: dir, dir->refCount, dir->name);
326: #endif
327:
328: if (dir->refCount > 0)
329: return;
330:
331: #ifdef DEBUG_REFCNT
332: DEBUG2(DIR, "CachedDir %p free for \"%s\"\n", dir, dir->name);
333: #endif
1.238 rillig 334:
335: OpenDirs_Remove(&openDirs, dir->name);
336:
337: free(dir->name);
338: HashSet_Done(&dir->files);
339: free(dir);
340: }
341:
1.240 rillig 342: /* Update the value of the CachedDir variable, updating the reference counts. */
343: static void
344: CachedDir_Assign(CachedDir **var, CachedDir *dir)
345: {
346: CachedDir *prev;
347:
348: prev = *var;
349: *var = dir;
350: if (dir != NULL)
351: CachedDir_Ref(dir);
352: if (prev != NULL)
1.241 rillig 353: CachedDir_Unref(prev);
1.240 rillig 354: }
355:
1.158 rillig 356: static void
357: OpenDirs_Init(OpenDirs *odirs)
358: {
1.227 rillig 359: Lst_Init(&odirs->list);
1.212 rillig 360: HashTable_Init(&odirs->table);
1.158 rillig 361: }
362:
1.175 rillig 363: #ifdef CLEANUP
364: static void
1.158 rillig 365: OpenDirs_Done(OpenDirs *odirs)
366: {
1.227 rillig 367: CachedDirListNode *ln = odirs->list.first;
1.250 ! rillig 368: DEBUG1(DIR, "OpenDirs_Done: %u entries to remove\n",
1.236 rillig 369: odirs->table.numEntries);
1.212 rillig 370: while (ln != NULL) {
371: CachedDirListNode *next = ln->next;
372: CachedDir *dir = ln->datum;
1.250 ! rillig 373: DEBUG2(DIR, "OpenDirs_Done: refCount %d for \"%s\"\n",
1.236 rillig 374: dir->refCount, dir->name);
1.241 rillig 375: CachedDir_Unref(dir); /* removes the dir from odirs->list */
1.212 rillig 376: ln = next;
377: }
1.227 rillig 378: Lst_Done(&odirs->list);
1.212 rillig 379: HashTable_Done(&odirs->table);
1.158 rillig 380: }
1.175 rillig 381: #endif
1.158 rillig 382:
383: static CachedDir *
384: OpenDirs_Find(OpenDirs *odirs, const char *name)
385: {
1.212 rillig 386: CachedDirListNode *ln = HashTable_FindValue(&odirs->table, name);
387: return ln != NULL ? ln->datum : NULL;
1.158 rillig 388: }
389:
390: static void
391: OpenDirs_Add(OpenDirs *odirs, CachedDir *cdir)
392: {
1.212 rillig 393: if (HashTable_FindEntry(&odirs->table, cdir->name) != NULL)
394: return;
1.227 rillig 395: Lst_Append(&odirs->list, cdir);
396: HashTable_Set(&odirs->table, cdir->name, odirs->list.last);
1.158 rillig 397: }
398:
399: static void
400: OpenDirs_Remove(OpenDirs *odirs, const char *name)
401: {
1.212 rillig 402: HashEntry *he = HashTable_FindEntry(&odirs->table, name);
403: CachedDirListNode *ln;
404: if (he == NULL)
405: return;
406: ln = HashEntry_Get(he);
407: HashTable_DeleteEntry(&odirs->table, he);
1.227 rillig 408: Lst_Remove(&odirs->list, ln);
1.158 rillig 409: }
410:
1.208 rillig 411: /* Returns 0 and the result of stat(2) or lstat(2) in *out_cst,
412: * or -1 on error. */
1.68 sjg 413: static int
1.208 rillig 414: cached_stats(const char *pathname, struct cached_stat *out_cst,
1.89 rillig 415: CachedStatsFlags flags)
1.68 sjg 416: {
1.212 rillig 417: HashTable *tbl = flags & CST_LSTAT ? &lmtimes : &mtimes;
418: struct stat sys_st;
419: struct cached_stat *cst;
420: int rc;
1.68 sjg 421:
1.212 rillig 422: if (pathname == NULL || pathname[0] == '\0')
423: return -1; /* This can happen in meta mode. */
1.68 sjg 424:
1.212 rillig 425: cst = HashTable_FindValue(tbl, pathname);
426: if (cst != NULL && !(flags & CST_UPDATE)) {
427: *out_cst = *cst;
1.250 ! rillig 428: DEBUG2(DIR, "Using cached time %s for %s\n",
! 429: Targ_FmtTime(cst->cst_mtime), pathname);
1.212 rillig 430: return 0;
431: }
432:
433: rc = (flags & CST_LSTAT ? lstat : stat)(pathname, &sys_st);
434: if (rc == -1)
435: return -1; /* don't cache negative lookups */
436:
437: if (sys_st.st_mtime == 0)
438: sys_st.st_mtime = 1; /* avoid confusion with missing file */
1.208 rillig 439:
1.212 rillig 440: if (cst == NULL) {
441: cst = bmake_malloc(sizeof *cst);
442: HashTable_Set(tbl, pathname, cst);
443: }
1.208 rillig 444:
1.212 rillig 445: cst->cst_mtime = sys_st.st_mtime;
446: cst->cst_mode = sys_st.st_mode;
1.208 rillig 447:
1.212 rillig 448: *out_cst = *cst;
1.250 ! rillig 449: DEBUG2(DIR, " Caching %s for %s\n",
! 450: Targ_FmtTime(sys_st.st_mtime), pathname);
1.68 sjg 451:
1.212 rillig 452: return 0;
1.68 sjg 453: }
454:
455: int
1.208 rillig 456: cached_stat(const char *pathname, struct cached_stat *cst)
1.68 sjg 457: {
1.212 rillig 458: return cached_stats(pathname, cst, CST_NONE);
1.68 sjg 459: }
460:
461: int
1.208 rillig 462: cached_lstat(const char *pathname, struct cached_stat *cst)
1.68 sjg 463: {
1.212 rillig 464: return cached_stats(pathname, cst, CST_LSTAT);
1.68 sjg 465: }
466:
1.163 rillig 467: /* Initialize the directories module. */
1.1 cgd 468: void
1.97 rillig 469: Dir_Init(void)
470: {
1.212 rillig 471: OpenDirs_Init(&openDirs);
472: HashTable_Init(&mtimes);
473: HashTable_Init(&lmtimes);
1.240 rillig 474: CachedDir_Assign(&dotLast, CachedDir_New(".DOTLAST"));
1.35 sjg 475: }
476:
477: /*
1.97 rillig 478: * Called by Dir_InitDir and whenever .CURDIR is assigned to.
1.35 sjg 479: */
480: void
1.45 christos 481: Dir_InitCur(const char *cdname)
1.35 sjg 482: {
1.212 rillig 483: CachedDir *dir;
1.203 rillig 484:
1.212 rillig 485: if (cdname == NULL)
486: return;
1.203 rillig 487:
1.17 gwr 488: /*
1.212 rillig 489: * Our build directory is not the same as our source directory.
490: * Keep this one around too.
1.17 gwr 491: */
1.212 rillig 492: dir = Dir_AddDir(NULL, cdname);
493: if (dir == NULL)
494: return;
495:
1.241 rillig 496: CachedDir_Assign(&cur, dir);
1.28 tv 497: }
498:
1.124 rillig 499: /* (Re)initialize "dot" (current/object directory) path hash.
1.233 rillig 500: * Some directories may be cached. */
1.28 tv 501: void
1.34 wiz 502: Dir_InitDot(void)
1.28 tv 503: {
1.241 rillig 504: CachedDir *dir;
1.28 tv 505:
1.241 rillig 506: dir = Dir_AddDir(NULL, ".");
507: if (dir == NULL) {
1.212 rillig 508: Error("Cannot open `.' (%s)", strerror(errno));
509: exit(1);
510: }
1.28 tv 511:
1.241 rillig 512: CachedDir_Assign(&dot, dir);
513:
1.213 rillig 514: Dir_SetPATH(); /* initialize */
1.1 cgd 515: }
516:
1.163 rillig 517: /* Clean up the directories module. */
1.6 jtc 518: void
1.34 wiz 519: Dir_End(void)
1.6 jtc 520: {
1.24 mycroft 521: #ifdef CLEANUP
1.241 rillig 522: CachedDir_Assign(&cur, NULL);
523: CachedDir_Assign(&dot, NULL);
1.240 rillig 524: CachedDir_Assign(&dotLast, NULL);
1.228 rillig 525: SearchPath_Clear(&dirSearchPath);
1.212 rillig 526: OpenDirs_Done(&openDirs);
527: HashTable_Done(&mtimes);
1.243 rillig 528: HashTable_Done(&lmtimes);
1.24 mycroft 529: #endif
1.6 jtc 530: }
531:
1.35 sjg 532: /*
533: * We want ${.PATH} to indicate the order in which we will actually
534: * search, so we rebuild it after any .PATH: target.
535: * This is the simplest way to deal with the effect of .DOTLAST.
536: */
537: void
1.45 christos 538: Dir_SetPATH(void)
1.35 sjg 539: {
1.212 rillig 540: CachedDirListNode *ln;
1.247 rillig 541: Boolean seenDotLast = FALSE; /* true if we should search '.' last */
1.35 sjg 542:
1.212 rillig 543: Var_Delete(".PATH", VAR_GLOBAL);
1.76 rillig 544:
1.228 rillig 545: if ((ln = dirSearchPath.first) != NULL) {
1.212 rillig 546: CachedDir *dir = ln->datum;
547: if (dir == dotLast) {
1.247 rillig 548: seenDotLast = TRUE;
1.212 rillig 549: Var_Append(".PATH", dotLast->name, VAR_GLOBAL);
550: }
1.35 sjg 551: }
552:
1.247 rillig 553: if (!seenDotLast) {
1.222 rillig 554: if (dot != NULL)
1.212 rillig 555: Var_Append(".PATH", dot->name, VAR_GLOBAL);
1.222 rillig 556: if (cur != NULL)
1.212 rillig 557: Var_Append(".PATH", cur->name, VAR_GLOBAL);
558: }
1.35 sjg 559:
1.228 rillig 560: for (ln = dirSearchPath.first; ln != NULL; ln = ln->next) {
1.212 rillig 561: CachedDir *dir = ln->datum;
562: if (dir == dotLast)
563: continue;
1.247 rillig 564: if (dir == dot && seenDotLast)
1.212 rillig 565: continue;
566: Var_Append(".PATH", dir->name, VAR_GLOBAL);
567: }
1.35 sjg 568:
1.247 rillig 569: if (seenDotLast) {
1.222 rillig 570: if (dot != NULL)
1.212 rillig 571: Var_Append(".PATH", dot->name, VAR_GLOBAL);
1.222 rillig 572: if (cur != NULL)
1.212 rillig 573: Var_Append(".PATH", cur->name, VAR_GLOBAL);
574: }
1.35 sjg 575: }
576:
1.186 rillig 577: /* See if the given name has any wildcard characters in it and all braces and
578: * brackets are properly balanced.
1.124 rillig 579: *
580: * XXX: This code is not 100% correct ([^]] fails etc.). I really don't think
581: * that make(1) should be expanding patterns, because then you have to set a
582: * mechanism for escaping the expansion!
1.1 cgd 583: *
1.186 rillig 584: * Return TRUE if the word should be expanded, FALSE otherwise.
1.1 cgd 585: */
586: Boolean
1.128 rillig 587: Dir_HasWildcards(const char *name)
1.1 cgd 588: {
1.212 rillig 589: const char *p;
590: Boolean wild = FALSE;
591: int braces = 0, brackets = 0;
592:
593: for (p = name; *p != '\0'; p++) {
594: switch (*p) {
595: case '{':
596: braces++;
597: wild = TRUE;
598: break;
599: case '}':
600: braces--;
601: break;
602: case '[':
603: brackets++;
604: wild = TRUE;
605: break;
606: case ']':
607: brackets--;
608: break;
609: case '?':
610: case '*':
611: wild = TRUE;
612: break;
613: default:
614: break;
615: }
1.1 cgd 616: }
1.212 rillig 617: return wild && brackets == 0 && braces == 0;
1.1 cgd 618: }
619:
1.181 rillig 620: /* See if any files match the pattern and add their names to the 'expansions'
621: * list if they do.
622: *
623: * This is incomplete -- wildcards are only expanded in the final path
624: * component, but not in directories like src/lib*c/file*.c, but it
625: * will do for now (now being 1993 until at least 2020). To expand these,
626: * use the ':sh' variable modifier such as in ${:!echo src/lib*c/file*.c!}.
1.1 cgd 627: *
1.34 wiz 628: * Input:
629: * pattern Pattern to look for
1.143 rillig 630: * dir Directory to search
1.34 wiz 631: * expansion Place to store the results
1.1 cgd 632: */
1.98 rillig 633: static void
1.144 rillig 634: DirMatchFiles(const char *pattern, CachedDir *dir, StringList *expansions)
1.1 cgd 635: {
1.212 rillig 636: const char *dirName = dir->name;
637: Boolean isDot = dirName[0] == '.' && dirName[1] == '\0';
638: HashIter hi;
1.12 christos 639:
1.1 cgd 640: /*
1.212 rillig 641: * XXX: Iterating over all hash entries is inefficient. If the
642: * pattern is a plain string without any wildcards, a direct lookup
643: * is faster.
1.1 cgd 644: */
1.181 rillig 645:
1.212 rillig 646: HashIter_InitSet(&hi, &dir->files);
647: while (HashIter_Next(&hi) != NULL) {
648: const char *base = hi.entry->key;
649:
650: if (!Str_Match(base, pattern))
651: continue;
652:
653: /*
654: * Follow the UNIX convention that dot files are only found
655: * if the pattern begins with a dot. The pattern '.*' does
656: * not match '.' or '..' since these are not included in the
657: * directory cache.
658: *
659: * This means that the pattern '[a-z.]*' does not find
660: * '.file', which is consistent with bash, NetBSD sh and csh.
661: */
662: if (base[0] == '.' && pattern[0] != '.')
663: continue;
664:
665: {
666: char *fullName = isDot
667: ? bmake_strdup(base)
668: : str_concat3(dirName, "/", base);
669: Lst_Append(expansions, fullName);
670: }
1.1 cgd 671: }
672: }
673:
1.91 rillig 674: /* Find the next closing brace in the string, taking nested braces into
675: * account. */
1.80 rillig 676: static const char *
677: closing_brace(const char *p)
678: {
1.212 rillig 679: int nest = 0;
680: while (*p != '\0') {
681: if (*p == '}' && nest == 0)
682: break;
683: if (*p == '{')
684: nest++;
685: if (*p == '}')
686: nest--;
687: p++;
688: }
689: return p;
1.80 rillig 690: }
691:
1.91 rillig 692: /* Find the next closing brace or comma in the string, taking nested braces
693: * into account. */
1.80 rillig 694: static const char *
695: separator_comma(const char *p)
696: {
1.212 rillig 697: int nest = 0;
698: while (*p != '\0') {
699: if ((*p == '}' || *p == ',') && nest == 0)
700: break;
701: if (*p == '{')
702: nest++;
703: if (*p == '}')
704: nest--;
705: p++;
706: }
707: return p;
1.80 rillig 708: }
709:
710: static Boolean
711: contains_wildcard(const char *p)
712: {
1.212 rillig 713: for (; *p != '\0'; p++) {
714: switch (*p) {
715: case '*':
716: case '?':
717: case '{':
718: case '[':
719: return TRUE;
720: }
1.80 rillig 721: }
1.212 rillig 722: return FALSE;
1.80 rillig 723: }
724:
725: static char *
726: concat3(const char *a, size_t a_len, const char *b, size_t b_len,
727: const char *c, size_t c_len)
728: {
1.212 rillig 729: size_t s_len = a_len + b_len + c_len;
730: char *s = bmake_malloc(s_len + 1);
731: memcpy(s, a, a_len);
732: memcpy(s + a_len, b, b_len);
733: memcpy(s + a_len + b_len, c, c_len);
734: s[s_len] = '\0';
735: return s;
1.80 rillig 736: }
737:
1.181 rillig 738: /* Expand curly braces like the C shell. Brace expansion by itself is purely
739: * textual, the expansions are not looked up in the file system. But if an
740: * expanded word contains wildcard characters, it is expanded further,
741: * matching only the actually existing files.
742: *
743: * Example: "{a{b,c}}" expands to "ab" and "ac".
744: * Example: "{a}" expands to "a".
745: * Example: "{a,*.c}" expands to "a" and all "*.c" files that exist.
1.1 cgd 746: *
1.34 wiz 747: * Input:
748: * word Entire word to expand
749: * brace First curly brace in it
750: * path Search path to use
751: * expansions Place to store the expansions
1.1 cgd 752: */
753: static void
1.144 rillig 754: DirExpandCurly(const char *word, const char *brace, SearchPath *path,
755: StringList *expansions)
1.1 cgd 756: {
1.212 rillig 757: const char *prefix, *middle, *piece, *middle_end, *suffix;
758: size_t prefix_len, suffix_len;
759:
760: /* Split the word into prefix '{' middle '}' suffix. */
761:
762: middle = brace + 1;
763: middle_end = closing_brace(middle);
764: if (*middle_end == '\0') {
765: Error("Unterminated {} clause \"%s\"", middle);
766: return;
767: }
768:
769: prefix = word;
770: prefix_len = (size_t)(brace - prefix);
771: suffix = middle_end + 1;
772: suffix_len = strlen(suffix);
773:
774: /* Split the middle into pieces, separated by commas. */
775:
776: piece = middle;
777: while (piece < middle_end + 1) {
778: const char *piece_end = separator_comma(piece);
779: size_t piece_len = (size_t)(piece_end - piece);
1.90 rillig 780:
1.212 rillig 781: char *file = concat3(prefix, prefix_len, piece, piece_len,
782: suffix, suffix_len);
1.1 cgd 783:
1.212 rillig 784: if (contains_wildcard(file)) {
785: Dir_Expand(file, path, expansions);
786: free(file);
787: } else {
788: Lst_Append(expansions, file);
789: }
1.78 rillig 790:
1.213 rillig 791: /* skip over the comma or closing brace */
792: piece = piece_end + 1;
1.1 cgd 793: }
794: }
795:
796:
1.183 rillig 797: /* Expand the word in each of the directories from the path. */
1.1 cgd 798: static void
1.183 rillig 799: DirExpandPath(const char *word, SearchPath *path, StringList *expansions)
1.1 cgd 800: {
1.212 rillig 801: SearchPathNode *ln;
802: for (ln = path->first; ln != NULL; ln = ln->next) {
803: CachedDir *dir = ln->datum;
804: DirMatchFiles(word, dir, expansions);
805: }
1.1 cgd 806: }
807:
1.146 rillig 808: static void
1.184 rillig 809: PrintExpansions(StringList *expansions)
1.1 cgd 810: {
1.212 rillig 811: const char *sep = "";
812: StringListNode *ln;
813: for (ln = expansions->first; ln != NULL; ln = ln->next) {
814: const char *word = ln->datum;
815: debug_printf("%s%s", sep, word);
816: sep = " ";
817: }
818: debug_printf("\n");
1.1 cgd 819: }
820:
1.180 rillig 821: /* Expand the given word into a list of words by globbing it, looking in the
822: * directories on the given search path.
1.1 cgd 823: *
1.34 wiz 824: * Input:
825: * word the word to expand
1.180 rillig 826: * path the directories in which to find the files
1.34 wiz 827: * expansions the list on which to place the results
1.1 cgd 828: */
829: void
1.144 rillig 830: Dir_Expand(const char *word, SearchPath *path, StringList *expansions)
1.1 cgd 831: {
1.216 rillig 832: const char *cp;
1.1 cgd 833:
1.216 rillig 834: assert(path != NULL);
835: assert(expansions != NULL);
1.112 rillig 836:
1.250 ! rillig 837: DEBUG1(DIR, "Expanding \"%s\"... ", word);
1.12 christos 838:
1.216 rillig 839: cp = strchr(word, '{');
840: if (cp != NULL) {
841: DirExpandCurly(word, cp, path, expansions);
842: goto done;
843: }
844:
845: /* At this point, the word does not contain '{'. */
1.215 rillig 846:
1.216 rillig 847: cp = strchr(word, '/');
848: if (cp == NULL) {
849: /* The word has no directory component. */
850: /* First the files in dot. */
851: DirMatchFiles(word, dot, expansions);
1.215 rillig 852:
1.216 rillig 853: /* Then the files in every other directory on the path. */
854: DirExpandPath(word, path, expansions);
855: goto done;
856: }
1.215 rillig 857:
1.216 rillig 858: /* At this point, the word has a directory component. */
1.215 rillig 859:
1.218 rillig 860: /* Find the first wildcard in the word. */
1.216 rillig 861: for (cp = word; *cp != '\0'; cp++)
862: if (*cp == '?' || *cp == '[' || *cp == '*')
863: break;
1.215 rillig 864:
1.216 rillig 865: if (*cp == '\0') {
866: /*
867: * No directory component and no wildcard at all -- this
868: * should never happen as in such a simple case there is no
869: * need to expand anything.
870: */
871: DirExpandPath(word, path, expansions);
872: goto done;
873: }
874:
875: /* Back up to the start of the component containing the wildcard. */
876: /* XXX: This handles '///' and '/' differently. */
877: while (cp > word && *cp != '/')
878: cp--;
1.215 rillig 879:
1.216 rillig 880: if (cp == word) {
881: /* The first component contains the wildcard. */
882: /* Start the search from the local directory */
883: DirExpandPath(word, path, expansions);
884: goto done;
885: }
1.215 rillig 886:
1.216 rillig 887: {
888: char *prefix = bmake_strsedup(word, cp + 1);
889: /*
890: * The wildcard isn't in the first component.
891: * Find all the components up to the one with the wildcard.
892: */
893: /*
894: * XXX: Check the "the directory is added to the path" part.
895: * It is probably surprising that the directory before a
896: * wildcard gets added to the path.
897: */
1.218 rillig 898: /*
899: * XXX: Only the first match of the prefix in the path is
900: * taken, any others are ignored. The expectation may be
901: * that the pattern is expanded in the whole path.
902: */
1.216 rillig 903: char *dirpath = Dir_FindFile(prefix, path);
904: free(prefix);
1.193 rillig 905:
1.216 rillig 906: /*
907: * dirpath is null if can't find the leading component
908: * XXX: Dir_FindFile won't find internal components.
909: * i.e. if the path contains ../Etc/Object and we're
910: * looking for Etc, it won't be found. Ah well.
911: * Probably not important.
912: * XXX: Check whether the above comment is still true.
913: */
914: if (dirpath != NULL) {
1.218 rillig 915: SearchPath *partPath;
916:
917: char *end = &dirpath[strlen(dirpath) - 1];
918: /* XXX: What about multiple trailing slashes? */
919: if (*end == '/')
920: *end = '\0';
921:
1.225 rillig 922: partPath = SearchPath_New();
1.218 rillig 923: (void)Dir_AddDir(partPath, dirpath);
924: DirExpandPath(cp + 1, partPath, expansions);
1.241 rillig 925: SearchPath_Free(partPath);
1.216 rillig 926: }
1.1 cgd 927: }
1.215 rillig 928:
929: done:
1.216 rillig 930: if (DEBUG(DIR))
931: PrintExpansions(expansions);
1.1 cgd 932: }
933:
1.176 rillig 934: /* Find if the file with the given name exists in the given path.
935: * Return the freshly allocated path to the file, or NULL. */
1.18 christos 936: static char *
1.177 rillig 937: DirLookup(CachedDir *dir, const char *base)
1.18 christos 938: {
1.212 rillig 939: char *file; /* the current filename to check */
1.18 christos 940:
1.250 ! rillig 941: DEBUG1(DIR, " %s ...\n", dir->name);
1.32 pk 942:
1.212 rillig 943: if (!HashSet_Contains(&dir->files, base))
944: return NULL;
1.32 pk 945:
1.212 rillig 946: file = str_concat3(dir->name, "/", base);
1.250 ! rillig 947: DEBUG1(DIR, " returning %s\n", file);
1.212 rillig 948: dir->hits++;
949: hits++;
950: return file;
1.18 christos 951: }
952:
953:
1.185 rillig 954: /* Find if the file with the given name exists in the given directory.
955: * Return the freshly allocated path to the file, or NULL. */
1.18 christos 956: static char *
1.143 rillig 957: DirLookupSubdir(CachedDir *dir, const char *name)
1.18 christos 958: {
1.212 rillig 959: struct cached_stat cst;
960: char *file = dir == dot ? bmake_strdup(name)
961: : str_concat3(dir->name, "/", name);
1.18 christos 962:
1.250 ! rillig 963: DEBUG1(DIR, "checking %s ...\n", file);
1.18 christos 964:
1.212 rillig 965: if (cached_stat(file, &cst) == 0) {
966: nearmisses++;
967: return file;
968: }
969: free(file);
970: return NULL;
1.18 christos 971: }
972:
1.185 rillig 973: /* Find if the file with the given name exists in the given path.
974: * Return the freshly allocated path to the file, the empty string, or NULL.
975: * Returning the empty string means that the search should be terminated.
1.32 pk 976: */
977: static char *
1.143 rillig 978: DirLookupAbs(CachedDir *dir, const char *name, const char *cp)
1.32 pk 979: {
1.212 rillig 980: const char *dnp; /* pointer into dir->name */
981: const char *np; /* pointer into name */
1.32 pk 982:
1.250 ! rillig 983: DEBUG1(DIR, " %s ...\n", dir->name);
1.32 pk 984:
1.212 rillig 985: /*
986: * If the file has a leading path component and that component
987: * exactly matches the entire name of the current search
988: * directory, we can attempt another cache lookup. And if we don't
989: * have a hit, we can safely assume the file does not exist at all.
990: */
991: for (dnp = dir->name, np = name;
992: *dnp != '\0' && *dnp == *np; dnp++, np++)
993: continue;
994: if (*dnp != '\0' || np != cp - 1)
995: return NULL;
1.32 pk 996:
1.212 rillig 997: if (!HashSet_Contains(&dir->files, cp)) {
1.250 ! rillig 998: DEBUG0(DIR, " must be here but isn't -- returning\n");
1.212 rillig 999: return bmake_strdup(""); /* to terminate the search */
1000: }
1.32 pk 1001:
1.212 rillig 1002: dir->hits++;
1003: hits++;
1.250 ! rillig 1004: DEBUG1(DIR, " returning %s\n", name);
1.212 rillig 1005: return bmake_strdup(name);
1.32 pk 1006: }
1007:
1.178 rillig 1008: /* Find the file given on "." or curdir.
1009: * Return the freshly allocated path to the file, or NULL. */
1.21 thorpej 1010: static char *
1.178 rillig 1011: DirFindDot(const char *name, const char *base)
1.21 thorpej 1012: {
1013:
1.212 rillig 1014: if (HashSet_Contains(&dot->files, base)) {
1.250 ! rillig 1015: DEBUG0(DIR, " in '.'\n");
1.212 rillig 1016: hits++;
1017: dot->hits++;
1018: return bmake_strdup(name);
1019: }
1.188 rillig 1020:
1.212 rillig 1021: if (cur != NULL && HashSet_Contains(&cur->files, base)) {
1.250 ! rillig 1022: DEBUG1(DIR, " in ${.CURDIR} = %s\n", cur->name);
1.212 rillig 1023: hits++;
1024: cur->hits++;
1025: return str_concat3(cur->name, "/", base);
1026: }
1.21 thorpej 1027:
1.212 rillig 1028: return NULL;
1.21 thorpej 1029: }
1030:
1.179 rillig 1031: /* Find the file with the given name along the given search path.
1032: *
1033: * If the file is found in a directory that is not on the path
1034: * already (either 'name' is absolute or it is a relative path
1035: * [ dir1/.../dirn/file ] which exists below one of the directories
1036: * already on the search path), its directory is added to the end
1037: * of the path, on the assumption that there will be more files in
1038: * that directory later on. Sometimes this is true. Sometimes not.
1.1 cgd 1039: *
1.34 wiz 1040: * Input:
1041: * name the file to find
1.179 rillig 1042: * path the directories to search, or NULL
1.34 wiz 1043: *
1.1 cgd 1044: * Results:
1.179 rillig 1045: * The freshly allocated path to the file, or NULL.
1.1 cgd 1046: */
1047: char *
1.144 rillig 1048: Dir_FindFile(const char *name, SearchPath *path)
1.1 cgd 1049: {
1.212 rillig 1050: char *file; /* the current filename to check */
1.245 rillig 1051: const char *lastSlash; /* the last slash in name */
1052: const char *base; /* basename(name) */
1053: Boolean seenDotLast = FALSE; /* true if we should search dot last */
1.212 rillig 1054: struct cached_stat cst; /* Buffer for stat, if necessary */
1055: const char *trailing_dot = ".";
1056:
1.245 rillig 1057: lastSlash = strrchr(name, '/');
1058: base = lastSlash != NULL ? lastSlash + 1 : name;
1.12 christos 1059:
1.250 ! rillig 1060: DEBUG1(DIR, "Searching for %s ...", name);
1.12 christos 1061:
1.212 rillig 1062: if (path == NULL) {
1.250 ! rillig 1063: DEBUG0(DIR, "couldn't open path, file not found\n");
1.212 rillig 1064: misses++;
1065: return NULL;
1066: }
1.12 christos 1067:
1.217 rillig 1068: if (path->first != NULL) {
1069: CachedDir *dir = path->first->datum;
1.212 rillig 1070: if (dir == dotLast) {
1.245 rillig 1071: seenDotLast = TRUE;
1.250 ! rillig 1072: DEBUG0(DIR, "[dot last]...");
1.212 rillig 1073: }
1.21 thorpej 1074: }
1.250 ! rillig 1075: DEBUG0(DIR, "\n");
1.18 christos 1076:
1.85 rillig 1077: /*
1.212 rillig 1078: * If there's no leading directory components or if the leading
1079: * directory component is exactly `./', consult the cached contents
1080: * of each of the directories on the search path.
1.85 rillig 1081: */
1.245 rillig 1082: if (lastSlash == NULL || (base - name == 2 && *name == '.')) {
1.217 rillig 1083: SearchPathNode *ln;
1084:
1.212 rillig 1085: /*
1086: * We look through all the directories on the path seeking one
1087: * which contains the final component of the given name. If
1088: * such a beast is found, we concatenate the directory name
1089: * and the final component and return the resulting string.
1090: * If we don't find any such thing, we go on to phase two.
1091: *
1092: * No matter what, we always look for the file in the current
1093: * directory before anywhere else (unless we found the magic
1094: * DOTLAST path, in which case we search it last) and we *do
1095: * not* add the ./ to it if it exists.
1096: * This is so there are no conflicts between what the user
1097: * specifies (fish.c) and what pmake finds (./fish.c).
1098: */
1.245 rillig 1099: if (!seenDotLast && (file = DirFindDot(name, base)) != NULL)
1.212 rillig 1100: return file;
1101:
1.217 rillig 1102: for (ln = path->first; ln != NULL; ln = ln->next) {
1.212 rillig 1103: CachedDir *dir = ln->datum;
1104: if (dir == dotLast)
1105: continue;
1106: if ((file = DirLookup(dir, base)) != NULL)
1107: return file;
1108: }
1.32 pk 1109:
1.245 rillig 1110: if (seenDotLast && (file = DirFindDot(name, base)) != NULL)
1.212 rillig 1111: return file;
1112: }
1113:
1114: /*
1115: * We didn't find the file on any directory in the search path.
1116: * If the name doesn't contain a slash, that means it doesn't exist.
1117: * If it *does* contain a slash, however, there is still hope: it
1118: * could be in a subdirectory of one of the members of the search
1119: * path. (eg. /usr/include and sys/types.h. The above search would
1120: * fail to turn up types.h in /usr/include, but it *is* in
1121: * /usr/include/sys/types.h).
1122: * [ This no longer applies: If we find such a beast, we assume there
1123: * will be more (what else can we assume?) and add all but the last
1124: * component of the resulting name onto the search path (at the
1125: * end).]
1126: * This phase is only performed if the file is *not* absolute.
1127: */
1.245 rillig 1128: if (lastSlash == NULL) {
1.250 ! rillig 1129: DEBUG0(DIR, " failed.\n");
1.212 rillig 1130: misses++;
1131: return NULL;
1.85 rillig 1132: }
1.21 thorpej 1133:
1.212 rillig 1134: if (*base == '\0') {
1135: /* we were given a trailing "/" */
1136: base = trailing_dot;
1137: }
1138:
1139: if (name[0] != '/') {
1.217 rillig 1140: SearchPathNode *ln;
1.212 rillig 1141: Boolean checkedDot = FALSE;
1142:
1.250 ! rillig 1143: DEBUG0(DIR, " Trying subdirectories...\n");
1.212 rillig 1144:
1.245 rillig 1145: if (!seenDotLast) {
1.222 rillig 1146: if (dot != NULL) {
1.212 rillig 1147: checkedDot = TRUE;
1148: if ((file = DirLookupSubdir(dot, name)) != NULL)
1149: return file;
1150: }
1151: if (cur && (file = DirLookupSubdir(cur, name)) != NULL)
1152: return file;
1153: }
1.12 christos 1154:
1.212 rillig 1155: for (ln = path->first; ln != NULL; ln = ln->next) {
1156: CachedDir *dir = ln->datum;
1157: if (dir == dotLast)
1158: continue;
1159: if (dir == dot) {
1160: if (checkedDot)
1161: continue;
1162: checkedDot = TRUE;
1163: }
1164: if ((file = DirLookupSubdir(dir, name)) != NULL)
1165: return file;
1166: }
1.12 christos 1167:
1.245 rillig 1168: if (seenDotLast) {
1.212 rillig 1169: if (dot && !checkedDot) {
1170: checkedDot = TRUE;
1171: if ((file = DirLookupSubdir(dot, name)) != NULL)
1172: return file;
1173: }
1174: if (cur && (file = DirLookupSubdir(cur, name)) != NULL)
1175: return file;
1176: }
1.63 sjg 1177:
1.212 rillig 1178: if (checkedDot) {
1179: /*
1180: * Already checked by the given name, since . was in
1181: * the path, so no point in proceeding.
1182: */
1.250 ! rillig 1183: DEBUG0(DIR, " Checked . already, returning NULL\n");
1.212 rillig 1184: return NULL;
1185: }
1.12 christos 1186:
1.212 rillig 1187: } else { /* name[0] == '/' */
1.217 rillig 1188: SearchPathNode *ln;
1.18 christos 1189:
1.212 rillig 1190: /*
1191: * For absolute names, compare directory path prefix against
1192: * the the directory path of each member on the search path
1193: * for an exact match. If we have an exact match on any member
1194: * of the search path, use the cached contents of that member
1195: * to lookup the final file component. If that lookup fails we
1196: * can safely assume that the file does not exist at all.
1197: * This is signified by DirLookupAbs() returning an empty
1198: * string.
1199: */
1.250 ! rillig 1200: DEBUG0(DIR, " Trying exact path matches...\n");
1.18 christos 1201:
1.245 rillig 1202: if (!seenDotLast && cur &&
1.212 rillig 1203: ((file = DirLookupAbs(cur, name, base)) != NULL)) {
1204: if (file[0] == '\0') {
1205: free(file);
1206: return NULL;
1207: }
1208: return file;
1209: }
1.12 christos 1210:
1.212 rillig 1211: for (ln = path->first; ln != NULL; ln = ln->next) {
1212: CachedDir *dir = ln->datum;
1213: if (dir == dotLast)
1214: continue;
1215: if ((file = DirLookupAbs(dir, name, base)) != NULL) {
1216: if (file[0] == '\0') {
1217: free(file);
1218: return NULL;
1219: }
1220: return file;
1221: }
1222: }
1.21 thorpej 1223:
1.245 rillig 1224: if (seenDotLast && cur &&
1.212 rillig 1225: ((file = DirLookupAbs(cur, name, base)) != NULL)) {
1226: if (file[0] == '\0') {
1227: free(file);
1228: return NULL;
1229: }
1230: return file;
1231: }
1.32 pk 1232: }
1233:
1234: /*
1.212 rillig 1235: * Didn't find it that way, either. Sigh. Phase 3. Add its directory
1236: * onto the search path in any case, just in case, then look for the
1237: * thing in the hash table. If we find it, grand. We return a new
1238: * copy of the name. Otherwise we sadly return a NULL pointer. Sigh.
1239: * Note that if the directory holding the file doesn't exist, this
1240: * will do an extra search of the final directory on the path. Unless
1241: * something weird happens, this search won't succeed and life will
1242: * be groovy.
1243: *
1244: * Sigh. We cannot add the directory onto the search path because
1245: * of this amusing case:
1246: * $(INSTALLDIR)/$(FILE): $(FILE)
1247: *
1248: * $(FILE) exists in $(INSTALLDIR) but not in the current one.
1249: * When searching for $(FILE), we will find it in $(INSTALLDIR)
1250: * b/c we added it here. This is not good...
1.32 pk 1251: */
1.212 rillig 1252: #if 0
1.217 rillig 1253: {
1254: CachedDir *dir;
1255: char *prefix;
1256:
1257: if (base == trailing_dot) {
1258: base = strrchr(name, '/');
1259: base++;
1260: }
1261: prefix = bmake_strsedup(name, base - 1);
1262: (void)Dir_AddDir(path, prefix);
1263: free(prefix);
1.212 rillig 1264:
1.217 rillig 1265: bigmisses++;
1266: if (path->last == NULL)
1267: return NULL;
1.32 pk 1268:
1.217 rillig 1269: dir = path->last->datum;
1270: if (HashSet_Contains(&dir->files, base))
1271: return bmake_strdup(name);
1.212 rillig 1272: return NULL;
1.32 pk 1273: }
1.212 rillig 1274: #else
1.250 ! rillig 1275: DEBUG1(DIR, " Looking for \"%s\" ...\n", name);
1.32 pk 1276:
1.212 rillig 1277: bigmisses++;
1278: if (cached_stat(name, &cst) == 0) {
1279: return bmake_strdup(name);
1.71 riastrad 1280: }
1.12 christos 1281:
1.250 ! rillig 1282: DEBUG0(DIR, " failed. Returning NULL\n");
1.57 dsl 1283: return NULL;
1.196 rillig 1284: #endif
1.1 cgd 1285: }
1286:
1.40 chuck 1287:
1.161 rillig 1288: /* Search for a path starting at a given directory and then working our way
1289: * up towards the root.
1.40 chuck 1290: *
1291: * Input:
1292: * here starting directory
1.161 rillig 1293: * search_path the relative path we are looking for
1.40 chuck 1294: *
1295: * Results:
1.161 rillig 1296: * The found path, or NULL.
1.40 chuck 1297: */
1.161 rillig 1298: char *
1299: Dir_FindHereOrAbove(const char *here, const char *search_path)
1.85 rillig 1300: {
1.212 rillig 1301: struct cached_stat cst;
1302: char *dirbase, *dirbase_end;
1303: char *try, *try_end;
1304:
1305: /* copy out our starting point */
1306: dirbase = bmake_strdup(here);
1307: dirbase_end = dirbase + strlen(dirbase);
1308:
1309: /* loop until we determine a result */
1310: for (;;) {
1311:
1312: /* try and stat(2) it ... */
1313: try = str_concat3(dirbase, "/", search_path);
1314: if (cached_stat(try, &cst) != -1) {
1315: /*
1316: * success! if we found a file, chop off
1317: * the filename so we return a directory.
1318: */
1319: if ((cst.cst_mode & S_IFMT) != S_IFDIR) {
1320: try_end = try + strlen(try);
1321: while (try_end > try && *try_end != '/')
1322: try_end--;
1323: if (try_end > try)
1324: *try_end = '\0'; /* chop! */
1325: }
1326:
1327: free(dirbase);
1328: return try;
1329: }
1330: free(try);
1.85 rillig 1331:
1.212 rillig 1332: /*
1333: * nope, we didn't find it. if we used up dirbase we've
1334: * reached the root and failed.
1335: */
1336: if (dirbase_end == dirbase)
1337: break; /* failed! */
1.40 chuck 1338:
1.212 rillig 1339: /*
1340: * truncate dirbase from the end to move up a dir
1341: */
1342: while (dirbase_end > dirbase && *dirbase_end != '/')
1343: dirbase_end--;
1344: *dirbase_end = '\0'; /* chop! */
1.85 rillig 1345: }
1.40 chuck 1346:
1.212 rillig 1347: free(dirbase);
1348: return NULL;
1.40 chuck 1349: }
1350:
1.220 rillig 1351: /*
1352: * This is an implied source, and it may have moved,
1353: * see if we can find it via the current .PATH
1354: */
1355: static char *
1356: ResolveMovedDepends(GNode *gn)
1357: {
1.221 rillig 1358: char *fullName;
1.220 rillig 1359:
1.221 rillig 1360: char *base = strrchr(gn->name, '/');
1361: if (base == NULL)
1362: return NULL;
1363: base++;
1.220 rillig 1364:
1.221 rillig 1365: fullName = Dir_FindFile(base, Suff_FindPath(gn));
1366: if (fullName == NULL)
1367: return NULL;
1.220 rillig 1368:
1.221 rillig 1369: /*
1370: * Put the found file in gn->path so that we give that to the compiler.
1371: */
1372: /*
1373: * XXX: Better just reset gn->path to NULL; updating it is already done
1374: * by Dir_UpdateMTime.
1375: */
1376: gn->path = bmake_strdup(fullName);
1377: if (!Job_RunTarget(".STALE", gn->fname))
1378: fprintf(stdout, /* XXX: Why stdout? */
1379: "%s: %s, %d: ignoring stale %s for %s, found %s\n",
1380: progname, gn->fname, gn->lineno,
1381: makeDependfile, gn->name, fullName);
1.220 rillig 1382:
1.221 rillig 1383: return fullName;
1.220 rillig 1384: }
1385:
1.219 rillig 1386: static char *
1387: ResolveFullName(GNode *gn)
1.1 cgd 1388: {
1.221 rillig 1389: char *fullName;
1.201 rillig 1390:
1.221 rillig 1391: fullName = gn->path;
1392: if (fullName == NULL && !(gn->type & OP_NOPATH)) {
1.76 rillig 1393:
1.221 rillig 1394: fullName = Dir_FindFile(gn->name, Suff_FindPath(gn));
1.220 rillig 1395:
1.221 rillig 1396: if (fullName == NULL && gn->flags & FROM_DEPEND &&
1.223 rillig 1397: !Lst_IsEmpty(&gn->implicitParents))
1.221 rillig 1398: fullName = ResolveMovedDepends(gn);
1.220 rillig 1399:
1.250 ! rillig 1400: DEBUG2(DIR, "Found '%s' as '%s'\n",
1.221 rillig 1401: gn->name, fullName ? fullName : "(not found)");
1402: }
1.12 christos 1403:
1.221 rillig 1404: if (fullName == NULL)
1405: fullName = bmake_strdup(gn->name);
1.1 cgd 1406:
1.221 rillig 1407: /* XXX: Is every piece of memory freed as it should? */
1.219 rillig 1408:
1.221 rillig 1409: return fullName;
1.219 rillig 1410: }
1411:
1412: /* Search gn along dirSearchPath and store its modification time in gn->mtime.
1413: * If no file is found, store 0 instead.
1414: *
1415: * The found file is stored in gn->path, unless the node already had a path. */
1416: void
1417: Dir_UpdateMTime(GNode *gn, Boolean recheck)
1418: {
1.221 rillig 1419: char *fullName;
1420: struct cached_stat cst;
1421:
1422: if (gn->type & OP_ARCHV) {
1423: Arch_UpdateMTime(gn);
1424: return;
1425: }
1.219 rillig 1426:
1.221 rillig 1427: if (gn->type & OP_PHONY) {
1428: gn->mtime = 0;
1429: return;
1430: }
1.219 rillig 1431:
1.221 rillig 1432: fullName = ResolveFullName(gn);
1.219 rillig 1433:
1.221 rillig 1434: if (cached_stats(fullName, &cst, recheck ? CST_UPDATE : CST_NONE) < 0) {
1435: if (gn->type & OP_MEMBER) {
1436: if (fullName != gn->path)
1437: free(fullName);
1438: Arch_UpdateMemberMTime(gn);
1439: return;
1440: }
1.219 rillig 1441:
1.221 rillig 1442: cst.cst_mtime = 0;
1.1 cgd 1443: }
1.198 rillig 1444:
1.221 rillig 1445: if (fullName != NULL && gn->path == NULL)
1446: gn->path = fullName;
1447: /* XXX: else free(fullName)? */
1.12 christos 1448:
1.221 rillig 1449: gn->mtime = cst.cst_mtime;
1.1 cgd 1450: }
1451:
1.235 rillig 1452: /*
1.242 rillig 1453: * Read the directory and add it to the cache in openDirs.
1454: * If a path is given, add the directory to that path as well.
1.235 rillig 1455: */
1456: static CachedDir *
1457: CacheNewDir(const char *name, SearchPath *path)
1458: {
1459: CachedDir *dir = NULL;
1460: DIR *d;
1461: struct dirent *dp;
1462:
1463: if ((d = opendir(name)) == NULL) {
1.250 ! rillig 1464: DEBUG1(DIR, "Caching %s ... not found\n", name);
1.235 rillig 1465: return dir;
1466: }
1467:
1.250 ! rillig 1468: DEBUG1(DIR, "Caching %s ...\n", name);
1.235 rillig 1469:
1470: dir = CachedDir_New(name);
1471:
1472: while ((dp = readdir(d)) != NULL) {
1473:
1474: #if defined(sun) && defined(d_ino) /* d_ino is a sunos4 #define for d_fileno */
1475: /*
1476: * The sun directory library doesn't check for a 0 inode
1477: * (0-inode slots just take up space), so we have to do
1478: * it ourselves.
1479: */
1480: if (dp->d_fileno == 0)
1481: continue;
1482: #endif /* sun && d_ino */
1483:
1484: (void)HashSet_Add(&dir->files, dp->d_name);
1485: }
1486: (void)closedir(d);
1487:
1488: OpenDirs_Add(&openDirs, dir);
1489: if (path != NULL)
1.241 rillig 1490: Lst_Append(path, CachedDir_Ref(dir));
1.235 rillig 1491:
1.250 ! rillig 1492: DEBUG1(DIR, "Caching %s done\n", name);
1.235 rillig 1493: return dir;
1494: }
1495:
1.150 rillig 1496: /* Read the list of filenames in the directory and store the result
1.215 rillig 1497: * in openDirs.
1.150 rillig 1498: *
1499: * If a path is given, append the directory to that path.
1.1 cgd 1500: *
1.34 wiz 1501: * Input:
1.150 rillig 1502: * path The path to which the directory should be
1.215 rillig 1503: * added, or NULL to only add the directory to openDirs
1.150 rillig 1504: * name The name of the directory to add.
1505: * The name is not normalized in any way.
1.242 rillig 1506: * Output:
1507: * result If no path is given and the directory exists, the
1508: * returned CachedDir has a reference count of 0. It
1509: * must either be assigned to a variable using
1510: * CachedDir_Assign or be appended to a SearchPath using
1511: * Lst_Append and CachedDir_Ref.
1.1 cgd 1512: */
1.143 rillig 1513: CachedDir *
1.144 rillig 1514: Dir_AddDir(SearchPath *path, const char *name)
1.1 cgd 1515: {
1.212 rillig 1516:
1517: if (path != NULL && strcmp(name, ".DOTLAST") == 0) {
1518: SearchPathNode *ln;
1519:
1520: /* XXX: Linear search gets slow with thousands of entries. */
1521: for (ln = path->first; ln != NULL; ln = ln->next) {
1522: CachedDir *pathDir = ln->datum;
1523: if (strcmp(pathDir->name, name) == 0)
1524: return pathDir;
1525: }
1.173 rillig 1526:
1.241 rillig 1527: Lst_Prepend(path, CachedDir_Ref(dotLast));
1.173 rillig 1528: }
1.120 rillig 1529:
1.235 rillig 1530: if (path != NULL) {
1.242 rillig 1531: /* XXX: Why is OpenDirs only checked if path != NULL? */
1.235 rillig 1532: CachedDir *dir = OpenDirs_Find(&openDirs, name);
1533: if (dir != NULL) {
1534: if (Lst_FindDatum(path, dir) == NULL)
1535: Lst_Append(path, CachedDir_Ref(dir));
1536: return dir;
1537: }
1.1 cgd 1538: }
1.120 rillig 1539:
1.235 rillig 1540: return CacheNewDir(name, path);
1.1 cgd 1541: }
1542:
1.187 rillig 1543: /* Return a copy of dirSearchPath, incrementing the reference counts for
1544: * the contained directories. */
1545: SearchPath *
1546: Dir_CopyDirSearchPath(void)
1.1 cgd 1547: {
1.225 rillig 1548: SearchPath *path = SearchPath_New();
1.212 rillig 1549: SearchPathNode *ln;
1.228 rillig 1550: for (ln = dirSearchPath.first; ln != NULL; ln = ln->next) {
1.212 rillig 1551: CachedDir *dir = ln->datum;
1.233 rillig 1552: Lst_Append(path, CachedDir_Ref(dir));
1.212 rillig 1553: }
1554: return path;
1.1 cgd 1555: }
1556:
1557: /*-
1558: *-----------------------------------------------------------------------
1.224 rillig 1559: * SearchPath_ToFlags --
1.1 cgd 1560: * Make a string by taking all the directories in the given search
1561: * path and preceding them by the given flag. Used by the suffix
1562: * module to create variables for compilers based on suffix search
1563: * paths.
1564: *
1.34 wiz 1565: * Input:
1566: * flag flag which should precede each directory
1567: * path list of directories
1568: *
1.1 cgd 1569: * Results:
1570: * The string mentioned above. Note that there is no space between
1571: * the given flag and each directory. The empty string is returned if
1572: * Things don't go well.
1573: *
1574: * Side Effects:
1575: * None
1576: *-----------------------------------------------------------------------
1577: */
1578: char *
1.224 rillig 1579: SearchPath_ToFlags(const char *flag, SearchPath *path)
1.1 cgd 1580: {
1.212 rillig 1581: Buffer buf;
1582: SearchPathNode *ln;
1.12 christos 1583:
1.212 rillig 1584: Buf_Init(&buf);
1.12 christos 1585:
1.212 rillig 1586: if (path != NULL) {
1587: for (ln = path->first; ln != NULL; ln = ln->next) {
1588: CachedDir *dir = ln->datum;
1589: Buf_AddStr(&buf, " ");
1590: Buf_AddStr(&buf, flag);
1591: Buf_AddStr(&buf, dir->name);
1592: }
1.1 cgd 1593: }
1.12 christos 1594:
1.212 rillig 1595: return Buf_Destroy(&buf, FALSE);
1.1 cgd 1596: }
1597:
1.225 rillig 1598: /* Free the search path and all directories mentioned in it. */
1599: void
1600: SearchPath_Free(SearchPath *path)
1601: {
1602: SearchPathNode *ln;
1603:
1604: for (ln = path->first; ln != NULL; ln = ln->next) {
1605: CachedDir *dir = ln->datum;
1.241 rillig 1606: CachedDir_Unref(dir);
1.225 rillig 1607: }
1608: Lst_Free(path);
1609: }
1610:
1.190 rillig 1611: /* Clear out all elements from the given search path.
1612: * The path is set to the empty list but is not destroyed. */
1.1 cgd 1613: void
1.224 rillig 1614: SearchPath_Clear(SearchPath *path)
1.1 cgd 1615: {
1.212 rillig 1616: while (!Lst_IsEmpty(path)) {
1617: CachedDir *dir = Lst_Dequeue(path);
1.241 rillig 1618: CachedDir_Unref(dir);
1.212 rillig 1619: }
1.1 cgd 1620: }
1.12 christos 1621:
1.1 cgd 1622:
1.190 rillig 1623: /* Concatenate two paths, adding the second to the end of the first,
1624: * skipping duplicates. */
1.1 cgd 1625: void
1.224 rillig 1626: SearchPath_AddAll(SearchPath *dst, SearchPath *src)
1.1 cgd 1627: {
1.212 rillig 1628: SearchPathNode *ln;
1.1 cgd 1629:
1.212 rillig 1630: for (ln = src->first; ln != NULL; ln = ln->next) {
1631: CachedDir *dir = ln->datum;
1.233 rillig 1632: if (Lst_FindDatum(dst, dir) == NULL)
1633: Lst_Append(dst, CachedDir_Ref(dir));
1.1 cgd 1634: }
1635: }
1636:
1.105 rillig 1637: static int
1638: percentage(int num, int den)
1639: {
1.212 rillig 1640: return den != 0 ? num * 100 / den : 0;
1.105 rillig 1641: }
1642:
1.1 cgd 1643: /********** DEBUG INFO **********/
1.5 cgd 1644: void
1.34 wiz 1645: Dir_PrintDirectories(void)
1.1 cgd 1646: {
1.212 rillig 1647: CachedDirListNode *ln;
1.12 christos 1648:
1.212 rillig 1649: debug_printf("#*** Directory Cache:\n");
1650: debug_printf(
1651: "# Stats: %d hits %d misses %d near misses %d losers (%d%%)\n",
1652: hits, misses, nearmisses, bigmisses,
1653: percentage(hits, hits + bigmisses + nearmisses));
1.248 rillig 1654: debug_printf("# refs hits directory\n");
1.212 rillig 1655:
1.227 rillig 1656: for (ln = openDirs.list.first; ln != NULL; ln = ln->next) {
1.212 rillig 1657: CachedDir *dir = ln->datum;
1.248 rillig 1658: debug_printf("# %4d %4d %s\n",
1659: dir->refCount, dir->hits, dir->name);
1.212 rillig 1660: }
1.1 cgd 1661: }
1662:
1.5 cgd 1663: void
1.224 rillig 1664: SearchPath_Print(SearchPath *path)
1.1 cgd 1665: {
1.249 rillig 1666: SearchPathNode *ln;
1667:
1668: for (ln = path->first; ln != NULL; ln = ln->next) {
1669: const CachedDir *dir = ln->datum;
1.212 rillig 1670: debug_printf("%s ", dir->name);
1671: }
1.1 cgd 1672: }
CVSweb <webmaster@jp.NetBSD.org>