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