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