1 /*-
2 * Copyright (c) 1988, 1989, 1990, 1993
3 * The Regents of the University of California. All rights reserved.
4 * Copyright (c) 1988, 1989 by Adam de Boor
5 * Copyright (c) 1989 by Berkeley Softworks
6 * All rights reserved.
7 *
8 * This code is derived from software contributed to Berkeley by
9 * Adam de Boor.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 * 3. All advertising materials mentioning features or use of this software
20 * must display the following acknowledgement:
21 * This product includes software developed by the University of
22 * California, Berkeley and its contributors.
23 * 4. Neither the name of the University nor the names of its contributors
24 * may be used to endorse or promote products derived from this software
25 * without specific prior written permission.
26 *
27 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
28 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
29 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
30 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
31 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
32 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
33 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
34 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
35 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
36 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
37 * SUCH DAMAGE.
38 *
39 * @(#)dir.c 8.2 (Berkeley) 1/2/94
40 */
41
42 #include <sys/cdefs.h>
43
44 /*-
45 * dir.c --
46 * Directory searching using wildcards and/or normal names...
47 * Used both for source wildcarding in the Makefile and for finding
48 * implicit sources.
49 *
50 * The interface for this module is:
51 * Dir_Init Initialize the module.
52 *
53 * Dir_HasWildcards Returns TRUE if the name given it needs to
54 * be wildcard-expanded.
55 *
56 * Path_Expand Given a pattern and a path, return a Lst of names
57 * which match the pattern on the search path.
58 *
59 * Path_FindFile Searches for a file on a given search path.
60 * If it exists, the entire path is returned.
61 * Otherwise NULL is returned.
62 *
63 * Dir_FindHereOrAbove Search for a path in the current directory and
64 * then all the directories above it in turn until
65 * the path is found or we reach the root ("/").
66 *
67 * Dir_MTime Return the modification time of a node. The file
68 * is searched for along the default search path.
69 * The path and mtime fields of the node are filled in.
70 *
71 * Path_AddDir Add a directory to a search path.
72 *
73 * Dir_MakeFlags Given a search path and a command flag, create
74 * a string with each of the directories in the path
75 * preceded by the command flag and all of them
76 * separated by a space.
77 *
78 * Dir_Destroy Destroy an element of a search path. Frees up all
79 * things that can be freed for the element as long
80 * as the element is no longer referenced by any other
81 * search path.
82 *
83 * Dir_ClearPath Resets a search path to the empty list.
84 *
85 * For debugging:
86 * Dir_PrintDirectories Print stats about the directory cache.
87 */
88
89 #include <sys/param.h>
90 #include <sys/stat.h>
91 #include <dirent.h>
92 #include <err.h>
93 #include <stdio.h>
94 #include <stdlib.h>
95 #include <string.h>
96
97 #include "arch.h"
98 #include "dir.h"
99 #include "globals.h"
100 #include "GNode.h"
101 #include "hash.h"
102 #include "lst.h"
103 #include "str.h"
104 #include "targ.h"
105 #include "util.h"
106
107 /*
108 * A search path consists of a list of Dir structures. A Dir structure
109 * has in it the name of the directory and a hash table of all the files
110 * in the directory. This is used to cut down on the number of system
111 * calls necessary to find implicit dependents and their like. Since
112 * these searches are made before any actions are taken, we need not
113 * worry about the directory changing due to creation commands. If this
114 * hampers the style of some makefiles, they must be changed.
115 *
116 * A list of all previously-read directories is kept in the
117 * openDirectories list. This list is checked first before a directory
118 * is opened.
119 *
120 * The need for the caching of whole directories is brought about by
121 * the multi-level transformation code in suff.c, which tends to search
122 * for far more files than regular make does. In the initial
123 * implementation, the amount of time spent performing "stat" calls was
124 * truly astronomical. The problem with hashing at the start is,
125 * of course, that pmake doesn't then detect changes to these directories
126 * during the course of the make. Three possibilities suggest themselves:
127 *
128 * 1) just use stat to test for a file's existence. As mentioned
129 * above, this is very inefficient due to the number of checks
130 * engendered by the multi-level transformation code.
131 * 2) use readdir() and company to search the directories, keeping
132 * them open between checks. I have tried this and while it
133 * didn't slow down the process too much, it could severely
134 * affect the amount of parallelism available as each directory
135 * open would take another file descriptor out of play for
136 * handling I/O for another job. Given that it is only recently
137 * that UNIX OS's have taken to allowing more than 20 or 32
138 * file descriptors for a process, this doesn't seem acceptable
139 * to me.
140 * 3) record the mtime of the directory in the Dir structure and
141 * verify the directory hasn't changed since the contents were
142 * hashed. This will catch the creation or deletion of files,
143 * but not the updating of files. However, since it is the
144 * creation and deletion that is the problem, this could be
145 * a good thing to do. Unfortunately, if the directory (say ".")
146 * were fairly large and changed fairly frequently, the constant
147 * rehashing could seriously degrade performance. It might be
148 * good in such cases to keep track of the number of rehashes
149 * and if the number goes over a (small) limit, resort to using
150 * stat in its place.
151 *
152 * An additional thing to consider is that pmake is used primarily
153 * to create C programs and until recently pcc-based compilers refused
154 * to allow you to specify where the resulting object file should be
155 * placed. This forced all objects to be created in the current
156 * directory. This isn't meant as a full excuse, just an explanation of
157 * some of the reasons for the caching used here.
158 *
159 * One more note: the location of a target's file is only performed
160 * on the downward traversal of the graph and then only for terminal
161 * nodes in the graph. This could be construed as wrong in some cases,
162 * but prevents inadvertent modification of files when the "installed"
163 * directory for a file is provided in the search path.
164 *
165 * Another data structure maintained by this module is an mtime
166 * cache used when the searching of cached directories fails to find
167 * a file. In the past, Path_FindFile would simply perform an access()
168 * call in such a case to determine if the file could be found using
169 * just the name given. When this hit, however, all that was gained
170 * was the knowledge that the file existed. Given that an access() is
171 * essentially a stat() without the copyout() call, and that the same
172 * filesystem overhead would have to be incurred in Dir_MTime, it made
173 * sense to replace the access() with a stat() and record the mtime
174 * in a cache for when Dir_MTime was actually called.
175 */
176
177 typedef struct Dir {
178 char *name; /* Name of directory */
179 int refCount; /* No. of paths with this directory */
180 int hits; /* No. of times a file has been found here */
181 Hash_Table files; /* Hash table of files in directory */
182 TAILQ_ENTRY(Dir) link; /* allDirs link */
183 } Dir;
184
185 /*
186 * A path is a list of pointers to directories. These directories are
187 * reference counted so a directory can be on more than one path.
188 */
189 struct PathElement {
190 struct Dir *dir; /* pointer to the directory */
191 TAILQ_ENTRY(PathElement) link; /* path link */
192 };
193
194 /* main search path */
195 struct Path dirSearchPath = TAILQ_HEAD_INITIALIZER(dirSearchPath);
196
197 /* the list of all open directories */
198 static TAILQ_HEAD(, Dir) openDirectories =
199 TAILQ_HEAD_INITIALIZER(openDirectories);
200
201 /*
202 * Variables for gathering statistics on the efficiency of the hashing
203 * mechanism.
204 */
205 static int hits; /* Found in directory cache */
206 static int misses; /* Sad, but not evil misses */
207 static int nearmisses; /* Found under search path */
208 static int bigmisses; /* Sought by itself */
209
210 static Dir *dot; /* contents of current directory */
211
212 /* Results of doing a last-resort stat in Path_FindFile --
213 * if we have to go to the system to find the file, we might as well
214 * have its mtime on record.
215 * XXX: If this is done way early, there's a chance other rules will
216 * have already updated the file, in which case we'll update it again.
217 * Generally, there won't be two rules to update a single file, so this
218 * should be ok, but...
219 */
220 static Hash_Table mtimes;
221
222 /*-
223 *-----------------------------------------------------------------------
224 * Dir_Init --
225 * initialize things for this module
226 *
227 * Results:
228 * none
229 *
230 * Side Effects:
231 * none
232 *-----------------------------------------------------------------------
233 */
234 void
Dir_Init(void)235 Dir_Init(void)
236 {
237
238 Hash_InitTable(&mtimes, 0);
239 }
240
241 /*-
242 *-----------------------------------------------------------------------
243 * Dir_InitDot --
244 * initialize the "." directory
245 *
246 * Results:
247 * none
248 *
249 * Side Effects:
250 * some directories may be opened.
251 *-----------------------------------------------------------------------
252 */
253 void
Dir_InitDot(void)254 Dir_InitDot(void)
255 {
256
257 dot = Path_AddDir(NULL, ".");
258 if (dot == NULL)
259 err(1, "cannot open current directory");
260
261 /*
262 * We always need to have dot around, so we increment its
263 * reference count to make sure it's not destroyed.
264 */
265 dot->refCount += 1;
266 }
267
268 /*-
269 *-----------------------------------------------------------------------
270 * Dir_HasWildcards --
271 * See if the given name has any wildcard characters in it.
272 *
273 * Results:
274 * returns TRUE if the word should be expanded, FALSE otherwise
275 *
276 * Side Effects:
277 * none
278 *-----------------------------------------------------------------------
279 */
280 Boolean
Dir_HasWildcards(const char * name)281 Dir_HasWildcards(const char *name)
282 {
283 const char *cp;
284 int wild = 0, brace = 0, bracket = 0;
285
286 for (cp = name; *cp; cp++) {
287 switch (*cp) {
288 case '{':
289 brace++;
290 wild = 1;
291 break;
292 case '}':
293 brace--;
294 break;
295 case '[':
296 bracket++;
297 wild = 1;
298 break;
299 case ']':
300 bracket--;
301 break;
302 case '?':
303 case '*':
304 wild = 1;
305 break;
306 default:
307 break;
308 }
309 }
310 return (wild && bracket == 0 && brace == 0);
311 }
312
313 /*-
314 *-----------------------------------------------------------------------
315 * DirMatchFiles --
316 * Given a pattern and a Dir structure, see if any files
317 * match the pattern and add their names to the 'expansions' list if
318 * any do. This is incomplete -- it doesn't take care of patterns like
319 * src / *src / *.c properly (just *.c on any of the directories), but it
320 * will do for now.
321 *
322 * Results:
323 * Always returns 0
324 *
325 * Side Effects:
326 * File names are added to the expansions lst. The directory will be
327 * fully hashed when this is done.
328 *-----------------------------------------------------------------------
329 */
330 static int
DirMatchFiles(const char * pattern,const Dir * p,Lst * expansions)331 DirMatchFiles(const char *pattern, const Dir *p, Lst *expansions)
332 {
333 Hash_Search search; /* Index into the directory's table */
334 Hash_Entry *entry; /* Current entry in the table */
335 Boolean isDot; /* TRUE if the directory being searched is . */
336
337 isDot = (*p->name == '.' && p->name[1] == '\0');
338
339 for (entry = Hash_EnumFirst(&p->files, &search);
340 entry != NULL;
341 entry = Hash_EnumNext(&search)) {
342 /*
343 * See if the file matches the given pattern. Note we follow
344 * the UNIX convention that dot files will only be found if
345 * the pattern begins with a dot (note also that as a side
346 * effect of the hashing scheme, .* won't match . or ..
347 * since they aren't hashed).
348 */
349 if (Str_Match(entry->name, pattern) &&
350 ((entry->name[0] != '.') ||
351 (pattern[0] == '.'))) {
352 Lst_AtEnd(expansions, (isDot ? estrdup(entry->name) :
353 str_concat(p->name, entry->name, STR_ADDSLASH)));
354 }
355 }
356 return (0);
357 }
358
359 /*-
360 *-----------------------------------------------------------------------
361 * DirExpandCurly --
362 * Expand curly braces like the C shell. Does this recursively.
363 * Note the special case: if after the piece of the curly brace is
364 * done there are no wildcard characters in the result, the result is
365 * placed on the list WITHOUT CHECKING FOR ITS EXISTENCE. The
366 * given arguments are the entire word to expand, the first curly
367 * brace in the word, the search path, and the list to store the
368 * expansions in.
369 *
370 * Results:
371 * None.
372 *
373 * Side Effects:
374 * The given list is filled with the expansions...
375 *
376 *-----------------------------------------------------------------------
377 */
378 static void
DirExpandCurly(const char * word,const char * brace,struct Path * path,Lst * expansions)379 DirExpandCurly(const char *word, const char *brace, struct Path *path,
380 Lst *expansions)
381 {
382 const char *end; /* Character after the closing brace */
383 const char *cp; /* Current position in brace clause */
384 const char *start; /* Start of current piece of brace clause */
385 int bracelevel; /* Number of braces we've seen. If we see a right brace
386 * when this is 0, we've hit the end of the clause. */
387 char *file; /* Current expansion */
388 int otherLen; /* The length of the other pieces of the expansion
389 * (chars before and after the clause in 'word') */
390 char *cp2; /* Pointer for checking for wildcards in
391 * expansion before calling Dir_Expand */
392
393 start = brace + 1;
394
395 /*
396 * Find the end of the brace clause first, being wary of nested brace
397 * clauses.
398 */
399 for (end = start, bracelevel = 0; *end != '\0'; end++) {
400 if (*end == '{')
401 bracelevel++;
402 else if ((*end == '}') && (bracelevel-- == 0))
403 break;
404 }
405 if (*end == '\0') {
406 Error("Unterminated {} clause \"%s\"", start);
407 return;
408 } else
409 end++;
410
411 otherLen = brace - word + strlen(end);
412
413 for (cp = start; cp < end; cp++) {
414 /*
415 * Find the end of this piece of the clause.
416 */
417 bracelevel = 0;
418 while (*cp != ',') {
419 if (*cp == '{')
420 bracelevel++;
421 else if ((*cp == '}') && (bracelevel-- <= 0))
422 break;
423 cp++;
424 }
425 /*
426 * Allocate room for the combination and install the
427 * three pieces.
428 */
429 file = emalloc(otherLen + cp - start + 1);
430 if (brace != word)
431 strncpy(file, word, brace - word);
432 if (cp != start)
433 strncpy(&file[brace - word], start, cp - start);
434 strcpy(&file[(brace - word) + (cp - start)], end);
435
436 /*
437 * See if the result has any wildcards in it. If we find one,
438 * call Dir_Expand right away, telling it to place the result
439 * on our list of expansions.
440 */
441 for (cp2 = file; *cp2 != '\0'; cp2++) {
442 switch (*cp2) {
443 case '*':
444 case '?':
445 case '{':
446 case '[':
447 Path_Expand(file, path, expansions);
448 goto next;
449 default:
450 break;
451 }
452 }
453 if (*cp2 == '\0') {
454 /*
455 * Hit the end w/o finding any wildcards, so stick
456 * the expansion on the end of the list.
457 */
458 Lst_AtEnd(expansions, file);
459 } else {
460 next:
461 free(file);
462 }
463 start = cp + 1;
464 }
465 }
466
467 /*-
468 *-----------------------------------------------------------------------
469 * DirExpandInt --
470 * Internal expand routine. Passes through the directories in the
471 * path one by one, calling DirMatchFiles for each. NOTE: This still
472 * doesn't handle patterns in directories... Works given a word to
473 * expand, a path to look in, and a list to store expansions in.
474 *
475 * Results:
476 * None.
477 *
478 * Side Effects:
479 * Things are added to the expansions list.
480 *
481 *-----------------------------------------------------------------------
482 */
483 static void
DirExpandInt(const char * word,const struct Path * path,Lst * expansions)484 DirExpandInt(const char *word, const struct Path *path, Lst *expansions)
485 {
486 struct PathElement *pe;
487
488 TAILQ_FOREACH(pe, path, link)
489 DirMatchFiles(word, pe->dir, expansions);
490 }
491
492 /*-
493 *-----------------------------------------------------------------------
494 * Dir_Expand --
495 * Expand the given word into a list of words by globbing it looking
496 * in the directories on the given search path.
497 *
498 * Results:
499 * A list of words consisting of the files which exist along the search
500 * path matching the given pattern is placed in expansions.
501 *
502 * Side Effects:
503 * Directories may be opened. Who knows?
504 *-----------------------------------------------------------------------
505 */
506 void
Path_Expand(char * word,struct Path * path,Lst * expansions)507 Path_Expand(char *word, struct Path *path, Lst *expansions)
508 {
509 LstNode *ln;
510 char *cp;
511
512 DEBUGF(DIR, ("expanding \"%s\"...", word));
513
514 cp = strchr(word, '{');
515 if (cp != NULL)
516 DirExpandCurly(word, cp, path, expansions);
517 else {
518 cp = strchr(word, '/');
519 if (cp != NULL) {
520 /*
521 * The thing has a directory component -- find the
522 * first wildcard in the string.
523 */
524 for (cp = word; *cp != '\0'; cp++) {
525 if (*cp == '?' || *cp == '[' ||
526 *cp == '*' || *cp == '{') {
527 break;
528 }
529 }
530 if (*cp == '{') {
531 /*
532 * This one will be fun.
533 */
534 DirExpandCurly(word, cp, path, expansions);
535 return;
536 } else if (*cp != '\0') {
537 /*
538 * Back up to the start of the component
539 */
540 char *dirpath;
541
542 while (cp > word && *cp != '/')
543 cp--;
544 if (cp != word) {
545 char sc;
546
547 /*
548 * If the glob isn't in the first
549 * component, try and find all the
550 * components up to the one with a
551 * wildcard.
552 */
553 sc = cp[1];
554 cp[1] = '\0';
555 dirpath = Path_FindFile(word, path);
556 cp[1] = sc;
557 /*
558 * dirpath is null if can't find the
559 * leading component
560 * XXX: Path_FindFile won't find internal
561 * components. i.e. if the path contains
562 * ../Etc/Object and we're looking for
563 * Etc, * it won't be found. Ah well.
564 * Probably not important.
565 */
566 if (dirpath != NULL) {
567 char *dp =
568 &dirpath[strlen(dirpath)
569 - 1];
570 struct Path tp =
571 TAILQ_HEAD_INITIALIZER(tp);
572
573 if (*dp == '/')
574 *dp = '\0';
575 Path_AddDir(&tp, dirpath);
576 DirExpandInt(cp + 1, &tp,
577 expansions);
578 Path_Clear(&tp);
579 }
580 } else {
581 /*
582 * Start the search from the local
583 * directory
584 */
585 DirExpandInt(word, path, expansions);
586 }
587 } else {
588 /*
589 * Return the file -- this should never happen.
590 */
591 DirExpandInt(word, path, expansions);
592 }
593 } else {
594 /*
595 * First the files in dot
596 */
597 DirMatchFiles(word, dot, expansions);
598
599 /*
600 * Then the files in every other directory on the path.
601 */
602 DirExpandInt(word, path, expansions);
603 }
604 }
605 if (DEBUG(DIR)) {
606 LST_FOREACH(ln, expansions)
607 DEBUGF(DIR, ("%s ", (const char *)Lst_Datum(ln)));
608 DEBUGF(DIR, ("\n"));
609 }
610 }
611
612 /**
613 * Path_FindFile
614 * Find the file with the given name along the given search path.
615 *
616 * Results:
617 * The path to the file or NULL. This path is guaranteed to be in a
618 * different part of memory than name and so may be safely free'd.
619 *
620 * Side Effects:
621 * If the file is found in a directory which is not on the path
622 * already (either 'name' is absolute or it is a relative path
623 * [ dir1/.../dirn/file ] which exists below one of the directories
624 * already on the search path), its directory is added to the end
625 * of the path on the assumption that there will be more files in
626 * that directory later on. Sometimes this is true. Sometimes not.
627 */
628 char *
Path_FindFile(char * name,struct Path * path)629 Path_FindFile(char *name, struct Path *path)
630 {
631 char *p1; /* pointer into p->name */
632 char *p2; /* pointer into name */
633 char *file; /* the current filename to check */
634 const struct PathElement *pe; /* current path member */
635 char *cp; /* final component of the name */
636 Boolean hasSlash; /* true if 'name' contains a / */
637 struct stat stb; /* Buffer for stat, if necessary */
638 Hash_Entry *entry; /* Entry for mtimes table */
639
640 /*
641 * Find the final component of the name and note whether it has a
642 * slash in it (the name, I mean)
643 */
644 cp = strrchr(name, '/');
645 if (cp != NULL) {
646 hasSlash = TRUE;
647 cp += 1;
648 } else {
649 hasSlash = FALSE;
650 cp = name;
651 }
652
653 DEBUGF(DIR, ("Searching for %s...", name));
654 /*
655 * No matter what, we always look for the file in the current directory
656 * before anywhere else and we *do not* add the ./ to it if it exists.
657 * This is so there are no conflicts between what the user specifies
658 * (fish.c) and what pmake finds (./fish.c).
659 */
660 if ((!hasSlash || (cp - name == 2 && *name == '.')) &&
661 (Hash_FindEntry(&dot->files, cp) != NULL)) {
662 DEBUGF(DIR, ("in '.'\n"));
663 hits += 1;
664 dot->hits += 1;
665 return (estrdup(name));
666 }
667
668 /*
669 * We look through all the directories on the path seeking one which
670 * contains the final component of the given name and whose final
671 * component(s) match the name's initial component(s). If such a beast
672 * is found, we concatenate the directory name and the final component
673 * and return the resulting string. If we don't find any such thing,
674 * we go on to phase two...
675 */
676 TAILQ_FOREACH(pe, path, link) {
677 DEBUGF(DIR, ("%s...", pe->dir->name));
678 if (Hash_FindEntry(&pe->dir->files, cp) != NULL) {
679 DEBUGF(DIR, ("here..."));
680 if (hasSlash) {
681 /*
682 * If the name had a slash, its initial
683 * components and p's final components must
684 * match. This is false if a mismatch is
685 * encountered before all of the initial
686 * components have been checked (p2 > name at
687 * the end of the loop), or we matched only
688 * part of one of the components of p
689 * along with all the rest of them (*p1 != '/').
690 */
691 p1 = pe->dir->name + strlen(pe->dir->name) - 1;
692 p2 = cp - 2;
693 while (p2 >= name && p1 >= pe->dir->name &&
694 *p1 == *p2) {
695 p1 -= 1; p2 -= 1;
696 }
697 if (p2 >= name || (p1 >= pe->dir->name &&
698 *p1 != '/')) {
699 DEBUGF(DIR, ("component mismatch -- "
700 "continuing..."));
701 continue;
702 }
703 }
704 file = str_concat(pe->dir->name, cp, STR_ADDSLASH);
705 DEBUGF(DIR, ("returning %s\n", file));
706 pe->dir->hits += 1;
707 hits += 1;
708 return (file);
709 } else if (hasSlash) {
710 /*
711 * If the file has a leading path component and that
712 * component exactly matches the entire name of the
713 * current search directory, we assume the file
714 * doesn't exist and return NULL.
715 */
716 for (p1 = pe->dir->name, p2 = name; *p1 && *p1 == *p2;
717 p1++, p2++)
718 continue;
719 if (*p1 == '\0' && p2 == cp - 1) {
720 if (*cp == '\0' || ISDOT(cp) || ISDOTDOT(cp)) {
721 DEBUGF(DIR, ("returning %s\n", name));
722 return (estrdup(name));
723 } else {
724 DEBUGF(DIR, ("must be here but isn't --"
725 " returning NULL\n"));
726 return (NULL);
727 }
728 }
729 }
730 }
731
732 /*
733 * We didn't find the file on any existing members of the directory.
734 * If the name doesn't contain a slash, that means it doesn't exist.
735 * If it *does* contain a slash, however, there is still hope: it
736 * could be in a subdirectory of one of the members of the search
737 * path. (eg. /usr/include and sys/types.h. The above search would
738 * fail to turn up types.h in /usr/include, but it *is* in
739 * /usr/include/sys/types.h) If we find such a beast, we assume there
740 * will be more (what else can we assume?) and add all but the last
741 * component of the resulting name onto the search path (at the
742 * end). This phase is only performed if the file is *not* absolute.
743 */
744 if (!hasSlash) {
745 DEBUGF(DIR, ("failed.\n"));
746 misses += 1;
747 return (NULL);
748 }
749
750 if (*name != '/') {
751 Boolean checkedDot = FALSE;
752
753 DEBUGF(DIR, ("failed. Trying subdirectories..."));
754 TAILQ_FOREACH(pe, path, link) {
755 if (pe->dir != dot) {
756 file = str_concat(pe->dir->name,
757 name, STR_ADDSLASH);
758 } else {
759 /*
760 * Checking in dot -- DON'T put a leading ./
761 * on the thing.
762 */
763 file = estrdup(name);
764 checkedDot = TRUE;
765 }
766 DEBUGF(DIR, ("checking %s...", file));
767
768 if (stat(file, &stb) == 0) {
769 DEBUGF(DIR, ("got it.\n"));
770
771 /*
772 * We've found another directory to search. We
773 * know there's a slash in 'file' because we put
774 * one there. We nuke it after finding it and
775 * call Path_AddDir to add this new directory
776 * onto the existing search path. Once that's
777 * done, we restore the slash and triumphantly
778 * return the file name, knowing that should a
779 * file in this directory every be referenced
780 * again in such a manner, we will find it
781 * without having to do numerous numbers of
782 * access calls. Hurrah!
783 */
784 cp = strrchr(file, '/');
785 *cp = '\0';
786 Path_AddDir(path, file);
787 *cp = '/';
788
789 /*
790 * Save the modification time so if
791 * it's needed, we don't have to fetch it again.
792 */
793 DEBUGF(DIR, ("Caching %s for %s\n",
794 Targ_FmtTime(stb.st_mtime), file));
795 entry = Hash_CreateEntry(&mtimes, file,
796 (Boolean *)NULL);
797 Hash_SetValue(entry,
798 (void *)(long)stb.st_mtime);
799 nearmisses += 1;
800 return (file);
801 } else {
802 free(file);
803 }
804 }
805
806 DEBUGF(DIR, ("failed. "));
807
808 if (checkedDot) {
809 /*
810 * Already checked by the given name, since . was in
811 * the path, so no point in proceeding...
812 */
813 DEBUGF(DIR, ("Checked . already, returning NULL\n"));
814 return (NULL);
815 }
816 }
817
818 /*
819 * Didn't find it that way, either. Sigh. Phase 3. Add its directory
820 * onto the search path in any case, just in case, then look for the
821 * thing in the hash table. If we find it, grand. We return a new
822 * copy of the name. Otherwise we sadly return a NULL pointer. Sigh.
823 * Note that if the directory holding the file doesn't exist, this will
824 * do an extra search of the final directory on the path. Unless
825 * something weird happens, this search won't succeed and life will
826 * be groovy.
827 *
828 * Sigh. We cannot add the directory onto the search path because
829 * of this amusing case:
830 * $(INSTALLDIR)/$(FILE): $(FILE)
831 *
832 * $(FILE) exists in $(INSTALLDIR) but not in the current one.
833 * When searching for $(FILE), we will find it in $(INSTALLDIR)
834 * b/c we added it here. This is not good...
835 */
836 DEBUGF(DIR, ("Looking for \"%s\"...", name));
837
838 bigmisses += 1;
839 entry = Hash_FindEntry(&mtimes, name);
840 if (entry != NULL) {
841 DEBUGF(DIR, ("got it (in mtime cache)\n"));
842 return (estrdup(name));
843 } else if (stat (name, &stb) == 0) {
844 entry = Hash_CreateEntry(&mtimes, name, (Boolean *)NULL);
845 DEBUGF(DIR, ("Caching %s for %s\n",
846 Targ_FmtTime(stb.st_mtime), name));
847 Hash_SetValue(entry, (void *)(long)stb.st_mtime);
848 return (estrdup(name));
849 } else {
850 DEBUGF(DIR, ("failed. Returning NULL\n"));
851 return (NULL);
852 }
853 }
854
855 /*-
856 *-----------------------------------------------------------------------
857 * Dir_FindHereOrAbove --
858 * search for a path starting at a given directory and then working
859 * our way up towards the root.
860 *
861 * Input:
862 * here starting directory
863 * search_path the path we are looking for
864 * result the result of a successful search is placed here
865 * rlen the length of the result buffer
866 * (typically MAXPATHLEN + 1)
867 *
868 * Results:
869 * 0 on failure, 1 on success [in which case the found path is put
870 * in the result buffer].
871 *
872 * Side Effects:
873 *-----------------------------------------------------------------------
874 */
875 int
Dir_FindHereOrAbove(char * here,char * search_path,char * result,int rlen)876 Dir_FindHereOrAbove(char *here, char *search_path, char *result, int rlen)
877 {
878 struct stat st;
879 char dirbase[MAXPATHLEN + 1], *db_end;
880 char try[MAXPATHLEN + 1], *try_end;
881
882 /* copy out our starting point */
883 snprintf(dirbase, sizeof(dirbase), "%s", here);
884 db_end = dirbase + strlen(dirbase);
885
886 /* loop until we determine a result */
887 while (1) {
888 /* try and stat(2) it ... */
889 snprintf(try, sizeof(try), "%s/%s", dirbase, search_path);
890 if (stat(try, &st) != -1) {
891 /*
892 * Success! If we found a file, chop off
893 * the filename so we return a directory.
894 */
895 if ((st.st_mode & S_IFMT) != S_IFDIR) {
896 try_end = try + strlen(try);
897 while (try_end > try && *try_end != '/')
898 try_end--;
899 if (try_end > try)
900 *try_end = 0; /* chop! */
901 }
902
903 /*
904 * Done!
905 */
906 snprintf(result, rlen, "%s", try);
907 return(1);
908 }
909
910 /*
911 * Nope, we didn't find it. If we used up dirbase we've
912 * reached the root and failed.
913 */
914 if (db_end == dirbase)
915 break; /* Failed! */
916
917 /*
918 * truncate dirbase from the end to move up a dir
919 */
920 while (db_end > dirbase && *db_end != '/')
921 db_end--;
922 *db_end = 0; /* chop! */
923
924 } /* while (1) */
925
926 /*
927 * We failed...
928 */
929 return(0);
930 }
931
932 /*-
933 *-----------------------------------------------------------------------
934 * Dir_MTime --
935 * Find the modification time of the file described by gn along the
936 * search path dirSearchPath.
937 *
938 * Results:
939 * The modification time or 0 if it doesn't exist
940 *
941 * Side Effects:
942 * The modification time is placed in the node's mtime slot.
943 * If the node didn't have a path entry before, and Path_FindFile
944 * found one for it, the full name is placed in the path slot.
945 *-----------------------------------------------------------------------
946 */
947 int
Dir_MTime(GNode * gn)948 Dir_MTime(GNode *gn)
949 {
950 char *fullName; /* the full pathname of name */
951 struct stat stb; /* buffer for finding the mod time */
952 Hash_Entry *entry;
953
954 if (gn->type & OP_ARCHV)
955 return (Arch_MTime(gn));
956
957 else if (gn->path == NULL)
958 fullName = Path_FindFile(gn->name, &dirSearchPath);
959 else
960 fullName = gn->path;
961
962 if (fullName == NULL)
963 fullName = estrdup(gn->name);
964
965 entry = Hash_FindEntry(&mtimes, fullName);
966 if (entry != NULL) {
967 /*
968 * Only do this once -- the second time folks are checking to
969 * see if the file was actually updated, so we need to
970 * actually go to the filesystem.
971 */
972 DEBUGF(DIR, ("Using cached time %s for %s\n",
973 Targ_FmtTime((time_t)(long)Hash_GetValue(entry)),
974 fullName));
975 stb.st_mtime = (time_t)(long)Hash_GetValue(entry);
976 Hash_DeleteEntry(&mtimes, entry);
977 } else if (stat(fullName, &stb) < 0) {
978 if (gn->type & OP_MEMBER) {
979 if (fullName != gn->path)
980 free(fullName);
981 return (Arch_MemMTime(gn));
982 } else {
983 stb.st_mtime = 0;
984 }
985 }
986 if (fullName && gn->path == (char *)NULL)
987 gn->path = fullName;
988
989 gn->mtime = stb.st_mtime;
990 return (gn->mtime);
991 }
992
993 /*-
994 *-----------------------------------------------------------------------
995 * Path_AddDir --
996 * Add the given name to the end of the given path.
997 *
998 * Results:
999 * none
1000 *
1001 * Side Effects:
1002 * A structure is added to the list and the directory is
1003 * read and hashed.
1004 *-----------------------------------------------------------------------
1005 */
1006 struct Dir *
Path_AddDir(struct Path * path,const char * name)1007 Path_AddDir(struct Path *path, const char *name)
1008 {
1009 Dir *d; /* pointer to new Path structure */
1010 DIR *dir; /* for reading directory */
1011 struct PathElement *pe;
1012 struct dirent *dp; /* entry in directory */
1013
1014 /* check whether we know this directory */
1015 TAILQ_FOREACH(d, &openDirectories, link) {
1016 if (strcmp(d->name, name) == 0) {
1017 /* Found it. */
1018 if (path == NULL)
1019 return (d);
1020
1021 /* Check whether its already on the path. */
1022 TAILQ_FOREACH(pe, path, link) {
1023 if (pe->dir == d)
1024 return (d);
1025 }
1026 /* Add it to the path */
1027 d->refCount += 1;
1028 pe = emalloc(sizeof(*pe));
1029 pe->dir = d;
1030 TAILQ_INSERT_TAIL(path, pe, link);
1031 return (d);
1032 }
1033 }
1034
1035 DEBUGF(DIR, ("Caching %s...", name));
1036
1037 if ((dir = opendir(name)) == NULL) {
1038 DEBUGF(DIR, (" cannot open\n"));
1039 return (NULL);
1040 }
1041
1042 d = emalloc(sizeof(*d));
1043 d->name = estrdup(name);
1044 d->hits = 0;
1045 d->refCount = 1;
1046 Hash_InitTable(&d->files, -1);
1047
1048 while ((dp = readdir(dir)) != NULL) {
1049 #if defined(sun) && defined(d_ino) /* d_ino is a sunos4 #define for d_fileno */
1050 /*
1051 * The sun directory library doesn't check for
1052 * a 0 inode (0-inode slots just take up space),
1053 * so we have to do it ourselves.
1054 */
1055 if (dp->d_fileno == 0)
1056 continue;
1057 #endif /* sun && d_ino */
1058
1059 /* Skip the '.' and '..' entries by checking
1060 * for them specifically instead of assuming
1061 * readdir() reuturns them in that order when
1062 * first going through a directory. This is
1063 * needed for XFS over NFS filesystems since
1064 * SGI does not guarantee that these are the
1065 * first two entries returned from readdir().
1066 */
1067 if (ISDOT(dp->d_name) || ISDOTDOT(dp->d_name))
1068 continue;
1069
1070 Hash_CreateEntry(&d->files, dp->d_name, (Boolean *)NULL);
1071 }
1072 closedir(dir);
1073
1074 if (path != NULL) {
1075 /* Add it to the path */
1076 d->refCount += 1;
1077 pe = emalloc(sizeof(*pe));
1078 pe->dir = d;
1079 TAILQ_INSERT_TAIL(path, pe, link);
1080 }
1081
1082 /* Add to list of all directories */
1083 TAILQ_INSERT_TAIL(&openDirectories, d, link);
1084
1085 DEBUGF(DIR, ("done\n"));
1086
1087 return (d);
1088 }
1089
1090 /**
1091 * Path_Duplicate
1092 * Duplicate a path. Ups the reference count for the directories.
1093 */
1094 void
Path_Duplicate(struct Path * dst,const struct Path * src)1095 Path_Duplicate(struct Path *dst, const struct Path *src)
1096 {
1097 struct PathElement *ped, *pes;
1098
1099 TAILQ_FOREACH(pes, src, link) {
1100 ped = emalloc(sizeof(*ped));
1101 ped->dir = pes->dir;
1102 ped->dir->refCount++;
1103 TAILQ_INSERT_TAIL(dst, ped, link);
1104 }
1105 }
1106
1107 /**
1108 * Path_MakeFlags
1109 * Make a string by taking all the directories in the given search
1110 * path and preceding them by the given flag. Used by the suffix
1111 * module to create variables for compilers based on suffix search
1112 * paths.
1113 *
1114 * Results:
1115 * The string mentioned above. Note that there is no space between
1116 * the given flag and each directory. The empty string is returned if
1117 * Things don't go well.
1118 */
1119 char *
Path_MakeFlags(const char * flag,const struct Path * path)1120 Path_MakeFlags(const char *flag, const struct Path *path)
1121 {
1122 char *str; /* the string which will be returned */
1123 char *tstr; /* the current directory preceded by 'flag' */
1124 char *nstr;
1125 const struct PathElement *pe;
1126
1127 str = estrdup("");
1128
1129 TAILQ_FOREACH(pe, path, link) {
1130 tstr = str_concat(flag, pe->dir->name, 0);
1131 nstr = str_concat(str, tstr, STR_ADDSPACE);
1132 free(str);
1133 free(tstr);
1134 str = nstr;
1135 }
1136
1137 return (str);
1138 }
1139
1140 /**
1141 * Path_Clear
1142 *
1143 * Destroy a path. This decrements the reference counts of all
1144 * directories of this path and, if a reference count goes 0,
1145 * destroys the directory object.
1146 */
1147 void
Path_Clear(struct Path * path)1148 Path_Clear(struct Path *path)
1149 {
1150 struct PathElement *pe;
1151
1152 while ((pe = TAILQ_FIRST(path)) != NULL) {
1153 pe->dir->refCount--;
1154 TAILQ_REMOVE(path, pe, link);
1155 if (pe->dir->refCount == 0) {
1156 TAILQ_REMOVE(&openDirectories, pe->dir, link);
1157 Hash_DeleteTable(&pe->dir->files);
1158 free(pe->dir->name);
1159 free(pe->dir);
1160 }
1161 free(pe);
1162 }
1163 }
1164
1165 /**
1166 * Path_Concat
1167 *
1168 * Concatenate two paths, adding the second to the end of the first.
1169 * Make sure to avoid duplicates.
1170 *
1171 * Side Effects:
1172 * Reference counts for added dirs are upped.
1173 */
1174 void
Path_Concat(struct Path * path1,const struct Path * path2)1175 Path_Concat(struct Path *path1, const struct Path *path2)
1176 {
1177 struct PathElement *p1, *p2;
1178
1179 TAILQ_FOREACH(p2, path2, link) {
1180 TAILQ_FOREACH(p1, path1, link) {
1181 if (p1->dir == p2->dir)
1182 break;
1183 }
1184 if (p1 == NULL) {
1185 p1 = emalloc(sizeof(*p1));
1186 p1->dir = p2->dir;
1187 p1->dir->refCount++;
1188 TAILQ_INSERT_TAIL(path1, p1, link);
1189 }
1190 }
1191 }
1192
1193 /********** DEBUG INFO **********/
1194 void
Dir_PrintDirectories(void)1195 Dir_PrintDirectories(void)
1196 {
1197 const Dir *d;
1198
1199 printf("#*** Directory Cache:\n");
1200 printf("# Stats: %d hits %d misses %d near misses %d losers (%d%%)\n",
1201 hits, misses, nearmisses, bigmisses,
1202 (hits + bigmisses + nearmisses ?
1203 hits * 100 / (hits + bigmisses + nearmisses) : 0));
1204 printf("# %-20s referenced\thits\n", "directory");
1205 TAILQ_FOREACH(d, &openDirectories, link)
1206 printf("# %-20s %10d\t%4d\n", d->name, d->refCount, d->hits);
1207 }
1208
1209 void
Path_Print(const struct Path * path)1210 Path_Print(const struct Path *path)
1211 {
1212 const struct PathElement *p;
1213
1214 TAILQ_FOREACH(p, path, link)
1215 printf("%s ", p->dir->name);
1216 }
1217