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