[BACK]Return to dir.c CVS log [TXT][DIR] Up to [cvs.NetBSD.org] / src / usr.bin / make

Annotation of src/usr.bin/make/dir.c, Revision 1.205

1.205   ! rillig      1: /*     $NetBSD: dir.c,v 1.204 2020/11/14 06:10:28 rillig Exp $ */
1.8       christos    2:
1.1       cgd         3: /*
                      4:  * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
1.37      agc         5:  * All rights reserved.
                      6:  *
                      7:  * This code is derived from software contributed to Berkeley by
                      8:  * Adam de Boor.
                      9:  *
                     10:  * Redistribution and use in source and binary forms, with or without
                     11:  * modification, are permitted provided that the following conditions
                     12:  * are met:
                     13:  * 1. Redistributions of source code must retain the above copyright
                     14:  *    notice, this list of conditions and the following disclaimer.
                     15:  * 2. Redistributions in binary form must reproduce the above copyright
                     16:  *    notice, this list of conditions and the following disclaimer in the
                     17:  *    documentation and/or other materials provided with the distribution.
                     18:  * 3. Neither the name of the University nor the names of its contributors
                     19:  *    may be used to endorse or promote products derived from this software
                     20:  *    without specific prior written permission.
                     21:  *
                     22:  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
                     23:  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
                     24:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
                     25:  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
                     26:  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
                     27:  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
                     28:  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
                     29:  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
                     30:  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
                     31:  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
                     32:  * SUCH DAMAGE.
                     33:  */
                     34:
                     35: /*
1.1       cgd        36:  * Copyright (c) 1988, 1989 by Adam de Boor
                     37:  * Copyright (c) 1989 by Berkeley Softworks
                     38:  * All rights reserved.
                     39:  *
                     40:  * This code is derived from software contributed to Berkeley by
                     41:  * Adam de Boor.
                     42:  *
                     43:  * Redistribution and use in source and binary forms, with or without
                     44:  * modification, are permitted provided that the following conditions
                     45:  * are met:
                     46:  * 1. Redistributions of source code must retain the above copyright
                     47:  *    notice, this list of conditions and the following disclaimer.
                     48:  * 2. Redistributions in binary form must reproduce the above copyright
                     49:  *    notice, this list of conditions and the following disclaimer in the
                     50:  *    documentation and/or other materials provided with the distribution.
                     51:  * 3. All advertising materials mentioning features or use of this software
                     52:  *    must display the following acknowledgement:
                     53:  *     This product includes software developed by the University of
                     54:  *     California, Berkeley and its contributors.
                     55:  * 4. Neither the name of the University nor the names of its contributors
                     56:  *    may be used to endorse or promote products derived from this software
                     57:  *    without specific prior written permission.
                     58:  *
                     59:  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
                     60:  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
                     61:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
                     62:  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
                     63:  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
                     64:  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
                     65:  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
                     66:  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
                     67:  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
                     68:  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
                     69:  * SUCH DAMAGE.
                     70:  */
                     71:
1.191     rillig     72: /* Directory searching using wildcards and/or normal names.
                     73:  * Used both for source wildcarding in the makefile and for finding
                     74:  * implicit sources.
1.1       cgd        75:  *
                     76:  * The interface for this module is:
1.149     rillig     77:  *     Dir_Init        Initialize the module.
1.1       cgd        78:  *
1.149     rillig     79:  *     Dir_InitCur     Set the cur CachedDir.
1.35      sjg        80:  *
1.149     rillig     81:  *     Dir_InitDot     Set the dot CachedDir.
1.35      sjg        82:  *
1.163     rillig     83:  *     Dir_End         Clean up the module.
1.6       jtc        84:  *
1.149     rillig     85:  *     Dir_SetPATH     Set ${.PATH} to reflect state of dirSearchPath.
1.35      sjg        86:  *
1.149     rillig     87:  *     Dir_HasWildcards
                     88:  *                     Returns TRUE if the name given it needs to
                     89:  *                     be wildcard-expanded.
1.1       cgd        90:  *
1.149     rillig     91:  *     Dir_Expand      Given a pattern and a path, return a Lst of names
                     92:  *                     which match the pattern on the search path.
1.1       cgd        93:  *
1.149     rillig     94:  *     Dir_FindFile    Searches for a file on a given search path.
                     95:  *                     If it exists, the entire path is returned.
                     96:  *                     Otherwise NULL is returned.
1.1       cgd        97:  *
1.149     rillig     98:  *     Dir_FindHereOrAbove
                     99:  *                     Search for a path in the current directory and
                    100:  *                     then all the directories above it in turn until
                    101:  *                     the path is found or we reach the root ("/").
1.76      rillig    102:  *
1.201     rillig    103:  *     Dir_UpdateMTime
                    104:  *                     Update the modification time and path of a node with
                    105:  *                     data from the file corresponding to the node.
1.1       cgd       106:  *
1.149     rillig    107:  *     Dir_AddDir      Add a directory to a search path.
1.1       cgd       108:  *
1.149     rillig    109:  *     Dir_MakeFlags   Given a search path and a command flag, create
                    110:  *                     a string with each of the directories in the path
                    111:  *                     preceded by the command flag and all of them
                    112:  *                     separated by a space.
1.1       cgd       113:  *
1.149     rillig    114:  *     Dir_Destroy     Destroy an element of a search path. Frees up all
                    115:  *                     things that can be freed for the element as long
                    116:  *                     as the element is no longer referenced by any other
                    117:  *                     search path.
                    118:  *
                    119:  *     Dir_ClearPath   Resets a search path to the empty list.
1.1       cgd       120:  *
                    121:  * For debugging:
1.191     rillig    122:  *     Dir_PrintDirectories
                    123:  *                     Print stats about the directory cache.
1.1       cgd       124:  */
                    125:
                    126: #include <sys/types.h>
1.34      wiz       127: #include <sys/stat.h>
                    128:
1.5       cgd       129: #include <dirent.h>
1.34      wiz       130: #include <errno.h>
                    131:
1.1       cgd       132: #include "make.h"
1.5       cgd       133: #include "dir.h"
1.67      christos  134: #include "job.h"
1.1       cgd       135:
1.142     rillig    136: /*     "@(#)dir.c      8.2 (Berkeley) 1/2/94"  */
1.205   ! rillig    137: MAKE_RCSID("$NetBSD: dir.c,v 1.204 2020/11/14 06:10:28 rillig Exp $");
1.92      rillig    138:
1.151     rillig    139: #define DIR_DEBUG0(text) DEBUG0(DIR, text)
                    140: #define DIR_DEBUG1(fmt, arg1) DEBUG1(DIR, fmt, arg1)
                    141: #define DIR_DEBUG2(fmt, arg1, arg2) DEBUG2(DIR, fmt, arg1, arg2)
1.92      rillig    142:
1.191     rillig    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
1.205   ! rillig    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.
1.191     rillig    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
1.205   ! rillig    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.
1.191     rillig    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
1.201     rillig    207:  * the mtime in a cache for when Dir_UpdateMTime was actually called.
1.1       cgd       208:  */
                    209:
1.144     rillig    210: typedef List CachedDirList;
                    211: typedef ListNode CachedDirListNode;
1.1       cgd       212:
1.144     rillig    213: typedef ListNode SearchPathNode;
                    214:
                    215: SearchPath *dirSearchPath;             /* main search path */
                    216:
1.158     rillig    217: /* A list of cached directories, with fast lookup by directory name. */
                    218: typedef struct OpenDirs {
                    219:     CachedDirList *list;
1.165     rillig    220:     HashTable /* of CachedDirListNode */ table;
1.158     rillig    221: } OpenDirs;
                    222:
                    223: static void
                    224: OpenDirs_Init(OpenDirs *odirs)
                    225: {
1.167     rillig    226:     odirs->list = Lst_New();
1.188     rillig    227:     HashTable_Init(&odirs->table);
1.158     rillig    228: }
                    229:
1.175     rillig    230: #ifdef CLEANUP
                    231: static void
1.158     rillig    232: OpenDirs_Done(OpenDirs *odirs)
                    233: {
1.159     rillig    234:     CachedDirListNode *ln = odirs->list->first;
                    235:     while (ln != NULL) {
1.162     rillig    236:        CachedDirListNode *next = ln->next;
                    237:        CachedDir *dir = ln->datum;
                    238:        Dir_Destroy(dir);       /* removes the dir from odirs->list */
                    239:        ln = next;
1.159     rillig    240:     }
1.158     rillig    241:     Lst_Free(odirs->list);
1.188     rillig    242:     HashTable_Done(&odirs->table);
1.158     rillig    243: }
1.175     rillig    244: #endif
1.158     rillig    245:
                    246: static CachedDir *
                    247: OpenDirs_Find(OpenDirs *odirs, const char *name)
                    248: {
1.188     rillig    249:     CachedDirListNode *ln = HashTable_FindValue(&odirs->table, name);
1.158     rillig    250:     return ln != NULL ? ln->datum : NULL;
                    251: }
                    252:
                    253: static void
                    254: OpenDirs_Add(OpenDirs *odirs, CachedDir *cdir)
                    255: {
1.188     rillig    256:     HashEntry *he = HashTable_FindEntry(&odirs->table, cdir->name);
1.158     rillig    257:     if (he != NULL)
                    258:        return;
1.188     rillig    259:     he = HashTable_CreateEntry(&odirs->table, cdir->name, NULL);
1.158     rillig    260:     Lst_Append(odirs->list, cdir);
1.188     rillig    261:     HashEntry_Set(he, odirs->list->last);
1.158     rillig    262: }
                    263:
                    264: static void
                    265: OpenDirs_Remove(OpenDirs *odirs, const char *name)
                    266: {
1.188     rillig    267:     HashEntry *he = HashTable_FindEntry(&odirs->table, name);
1.158     rillig    268:     CachedDirListNode *ln;
                    269:     if (he == NULL)
                    270:        return;
1.188     rillig    271:     ln = HashEntry_Get(he);
                    272:     HashTable_DeleteEntry(&odirs->table, he);
1.158     rillig    273:     Lst_Remove(odirs->list, ln);
                    274: }
                    275:
                    276: static OpenDirs openDirs;      /* the list of all open directories */
1.1       cgd       277:
                    278: /*
1.204     rillig    279:  * Variables for gathering statistics on the efficiency of the caching
1.1       cgd       280:  * mechanism.
                    281:  */
1.85      rillig    282: static int hits;               /* Found in directory cache */
                    283: static int misses;             /* Sad, but not evil misses */
                    284: static int nearmisses;         /* Found under search path */
                    285: static int bigmisses;          /* Sought by itself */
                    286:
1.143     rillig    287: static CachedDir *dot;         /* contents of current directory */
                    288: static CachedDir *cur;         /* contents of current directory, if not dot */
                    289: static CachedDir *dotLast;     /* a fake path entry indicating we need to
1.85      rillig    290:                                 * look for . last */
                    291:
                    292: /* Results of doing a last-resort stat in Dir_FindFile -- if we have to go to
                    293:  * the system to find the file, we might as well have its mtime on record.
                    294:  *
                    295:  * XXX: If this is done way early, there's a chance other rules will have
                    296:  * already updated the file, in which case we'll update it again. Generally,
                    297:  * there won't be two rules to update a single file, so this should be ok,
                    298:  * but... */
1.165     rillig    299: static HashTable mtimes;
1.1       cgd       300:
1.165     rillig    301: static HashTable lmtimes;      /* same as mtimes but for lstat */
1.1       cgd       302:
1.68      sjg       303: /*
1.89      rillig    304:  * We use stat(2) a lot, cache the results.
1.68      sjg       305:  * mtime and mode are all we care about.
                    306:  */
                    307: struct cache_st {
1.85      rillig    308:     time_t lmtime;             /* lstat */
                    309:     time_t mtime;              /* stat */
                    310:     mode_t mode;
1.68      sjg       311: };
                    312:
                    313: /* minimize changes below */
1.170     rillig    314: typedef enum CachedStatsFlags {
1.198     rillig    315:     CST_NONE   = 0,
                    316:     CST_LSTAT  = 1 << 0,       /* call lstat(2) instead of stat(2) */
                    317:     CST_UPDATE = 1 << 1        /* ignore existing cached entry */
1.89      rillig    318: } CachedStatsFlags;
1.68      sjg       319:
1.133     rillig    320: /* Returns 0 and the result of stat(2) or lstat(2) in *mst, or -1 on error. */
1.68      sjg       321: static int
1.165     rillig    322: cached_stats(HashTable *htp, const char *pathname, struct make_stat *mst,
1.89      rillig    323:             CachedStatsFlags flags)
1.68      sjg       324: {
1.165     rillig    325:     HashEntry *entry;
1.133     rillig    326:     struct stat sys_st;
1.68      sjg       327:     struct cache_st *cst;
                    328:     int rc;
                    329:
1.196     rillig    330:     if (pathname == NULL || pathname[0] == '\0')
1.68      sjg       331:        return -1;
                    332:
1.188     rillig    333:     entry = HashTable_FindEntry(htp, pathname);
1.68      sjg       334:
1.89      rillig    335:     if (entry && !(flags & CST_UPDATE)) {
1.188     rillig    336:        cst = HashEntry_Get(entry);
1.68      sjg       337:
1.133     rillig    338:        mst->mst_mode = cst->mode;
                    339:        mst->mst_mtime = (flags & CST_LSTAT) ? cst->lmtime : cst->mtime;
                    340:        if (mst->mst_mtime) {
1.92      rillig    341:            DIR_DEBUG2("Using cached time %s for %s\n",
1.133     rillig    342:                       Targ_FmtTime(mst->mst_mtime), pathname);
1.74      sjg       343:            return 0;
1.73      christos  344:        }
1.68      sjg       345:     }
                    346:
1.133     rillig    347:     rc = (flags & CST_LSTAT)
                    348:         ? lstat(pathname, &sys_st)
                    349:         : stat(pathname, &sys_st);
1.68      sjg       350:     if (rc == -1)
                    351:        return -1;
                    352:
1.135     rillig    353:     if (sys_st.st_mtime == 0)
                    354:        sys_st.st_mtime = 1;    /* avoid confusion with missing file */
                    355:
1.134     rillig    356:     mst->mst_mode = sys_st.st_mode;
                    357:     mst->mst_mtime = sys_st.st_mtime;
                    358:
1.131     rillig    359:     if (entry == NULL)
1.188     rillig    360:        entry = HashTable_CreateEntry(htp, pathname, NULL);
                    361:     if (HashEntry_Get(entry) == NULL) {
1.194     rillig    362:        HashEntry_Set(entry, bmake_malloc(sizeof *cst));
                    363:        memset(HashEntry_Get(entry), 0, sizeof *cst);
1.74      sjg       364:     }
1.188     rillig    365:     cst = HashEntry_Get(entry);
1.89      rillig    366:     if (flags & CST_LSTAT) {
1.133     rillig    367:        cst->lmtime = sys_st.st_mtime;
1.74      sjg       368:     } else {
1.133     rillig    369:        cst->mtime = sys_st.st_mtime;
1.74      sjg       370:     }
1.133     rillig    371:     cst->mode = sys_st.st_mode;
1.92      rillig    372:     DIR_DEBUG2("   Caching %s for %s\n",
1.133     rillig    373:               Targ_FmtTime(sys_st.st_mtime), pathname);
1.68      sjg       374:
                    375:     return 0;
                    376: }
                    377:
                    378: int
1.133     rillig    379: cached_stat(const char *pathname, struct make_stat *st)
1.68      sjg       380: {
1.198     rillig    381:     return cached_stats(&mtimes, pathname, st, CST_NONE);
1.68      sjg       382: }
                    383:
                    384: int
1.133     rillig    385: cached_lstat(const char *pathname, struct make_stat *st)
1.68      sjg       386: {
                    387:     return cached_stats(&lmtimes, pathname, st, CST_LSTAT);
                    388: }
                    389:
1.163     rillig    390: /* Initialize the directories module. */
1.1       cgd       391: void
1.97      rillig    392: Dir_Init(void)
                    393: {
1.167     rillig    394:     dirSearchPath = Lst_New();
1.158     rillig    395:     OpenDirs_Init(&openDirs);
1.188     rillig    396:     HashTable_Init(&mtimes);
                    397:     HashTable_Init(&lmtimes);
1.97      rillig    398: }
                    399:
                    400: void
                    401: Dir_InitDir(const char *cdname)
1.1       cgd       402: {
1.35      sjg       403:     Dir_InitCur(cdname);
                    404:
1.194     rillig    405:     dotLast = bmake_malloc(sizeof *dotLast);
1.35      sjg       406:     dotLast->refCount = 1;
                    407:     dotLast->hits = 0;
1.56      joerg     408:     dotLast->name = bmake_strdup(".DOTLAST");
1.188     rillig    409:     HashTable_Init(&dotLast->files);
1.35      sjg       410: }
                    411:
                    412: /*
1.97      rillig    413:  * Called by Dir_InitDir and whenever .CURDIR is assigned to.
1.35      sjg       414:  */
                    415: void
1.45      christos  416: Dir_InitCur(const char *cdname)
1.35      sjg       417: {
1.143     rillig    418:     CachedDir *dir;
1.76      rillig    419:
1.203     rillig    420:     if (cdname == NULL)
                    421:        return;
                    422:
                    423:     /*
                    424:      * Our build directory is not the same as our source directory.
                    425:      * Keep this one around too.
                    426:      */
                    427:     dir = Dir_AddDir(NULL, cdname);
                    428:     if (dir == NULL)
                    429:        return;
                    430:
                    431:     /* XXX: Reference counting is wrong here.
                    432:      * If this function is called repeatedly with the same directory name,
                    433:      * its reference count increases each time even though the number of
                    434:      * actual references stays the same. */
                    435:
                    436:     dir->refCount++;
                    437:     if (cur != NULL && cur != dir) {
1.17      gwr       438:        /*
1.203     rillig    439:         * We've been here before, clean up.
1.17      gwr       440:         */
1.203     rillig    441:        cur->refCount--;
                    442:        Dir_Destroy(cur);
1.17      gwr       443:     }
1.203     rillig    444:     cur = dir;
1.28      tv        445: }
                    446:
1.124     rillig    447: /* (Re)initialize "dot" (current/object directory) path hash.
                    448:  * Some directories may be opened. */
1.28      tv        449: void
1.34      wiz       450: Dir_InitDot(void)
1.28      tv        451: {
                    452:     if (dot != NULL) {
1.158     rillig    453:        /* Remove old entry from openDirs, but do not destroy. */
                    454:        OpenDirs_Remove(&openDirs, dot->name);
1.28      tv        455:     }
                    456:
1.45      christos  457:     dot = Dir_AddDir(NULL, ".");
1.28      tv        458:
                    459:     if (dot == NULL) {
                    460:        Error("Cannot open `.' (%s)", strerror(errno));
                    461:        exit(1);
                    462:     }
                    463:
                    464:     /*
                    465:      * We always need to have dot around, so we increment its reference count
                    466:      * to make sure it's not destroyed.
                    467:      */
1.153     rillig    468:     dot->refCount++;
1.85      rillig    469:     Dir_SetPATH();             /* initialize */
1.1       cgd       470: }
                    471:
1.163     rillig    472: /* Clean up the directories module. */
1.6       jtc       473: void
1.34      wiz       474: Dir_End(void)
1.6       jtc       475: {
1.24      mycroft   476: #ifdef CLEANUP
1.17      gwr       477:     if (cur) {
1.153     rillig    478:        cur->refCount--;
1.51      dsl       479:        Dir_Destroy(cur);
1.17      gwr       480:     }
1.153     rillig    481:     dot->refCount--;
                    482:     dotLast->refCount--;
1.51      dsl       483:     Dir_Destroy(dotLast);
                    484:     Dir_Destroy(dot);
1.6       jtc       485:     Dir_ClearPath(dirSearchPath);
1.119     rillig    486:     Lst_Free(dirSearchPath);
1.158     rillig    487:     OpenDirs_Done(&openDirs);
1.188     rillig    488:     HashTable_Done(&mtimes);
1.24      mycroft   489: #endif
1.6       jtc       490: }
                    491:
1.35      sjg       492: /*
                    493:  * We want ${.PATH} to indicate the order in which we will actually
                    494:  * search, so we rebuild it after any .PATH: target.
                    495:  * This is the simplest way to deal with the effect of .DOTLAST.
                    496:  */
                    497: void
1.45      christos  498: Dir_SetPATH(void)
1.35      sjg       499: {
1.144     rillig    500:     CachedDirListNode *ln;
1.107     rillig    501:     Boolean hasLastDot = FALSE;        /* true if we should search dot last */
1.35      sjg       502:
                    503:     Var_Delete(".PATH", VAR_GLOBAL);
1.76      rillig    504:
1.169     rillig    505:     if ((ln = dirSearchPath->first) != NULL) {
                    506:        CachedDir *dir = ln->datum;
1.143     rillig    507:        if (dir == dotLast) {
1.107     rillig    508:            hasLastDot = TRUE;
                    509:            Var_Append(".PATH", dotLast->name, VAR_GLOBAL);
1.35      sjg       510:        }
1.107     rillig    511:     }
1.35      sjg       512:
1.107     rillig    513:     if (!hasLastDot) {
                    514:        if (dot)
                    515:            Var_Append(".PATH", dot->name, VAR_GLOBAL);
                    516:        if (cur)
                    517:            Var_Append(".PATH", cur->name, VAR_GLOBAL);
                    518:     }
1.35      sjg       519:
1.169     rillig    520:     for (ln = dirSearchPath->first; ln != NULL; ln = ln->next) {
                    521:        CachedDir *dir = ln->datum;
1.143     rillig    522:        if (dir == dotLast)
1.107     rillig    523:            continue;
1.143     rillig    524:        if (dir == dot && hasLastDot)
1.107     rillig    525:            continue;
1.143     rillig    526:        Var_Append(".PATH", dir->name, VAR_GLOBAL);
1.107     rillig    527:     }
1.35      sjg       528:
1.107     rillig    529:     if (hasLastDot) {
                    530:        if (dot)
                    531:            Var_Append(".PATH", dot->name, VAR_GLOBAL);
                    532:        if (cur)
                    533:            Var_Append(".PATH", cur->name, VAR_GLOBAL);
1.35      sjg       534:     }
                    535: }
                    536:
1.186     rillig    537: /* See if the given name has any wildcard characters in it and all braces and
                    538:  * brackets are properly balanced.
1.124     rillig    539:  *
                    540:  * XXX: This code is not 100% correct ([^]] fails etc.). I really don't think
                    541:  * that make(1) should be expanding patterns, because then you have to set a
                    542:  * mechanism for escaping the expansion!
1.1       cgd       543:  *
1.186     rillig    544:  * Return TRUE if the word should be expanded, FALSE otherwise.
1.1       cgd       545:  */
                    546: Boolean
1.128     rillig    547: Dir_HasWildcards(const char *name)
1.1       cgd       548: {
1.186     rillig    549:     const char *p;
1.128     rillig    550:     Boolean wild = FALSE;
                    551:     int braces = 0, brackets = 0;
1.12      christos  552:
1.186     rillig    553:     for (p = name; *p != '\0'; p++) {
                    554:        switch (*p) {
1.1       cgd       555:        case '{':
1.128     rillig    556:            braces++;
                    557:            wild = TRUE;
1.85      rillig    558:            break;
1.13      christos  559:        case '}':
1.128     rillig    560:            braces--;
1.85      rillig    561:            break;
1.1       cgd       562:        case '[':
1.128     rillig    563:            brackets++;
                    564:            wild = TRUE;
1.85      rillig    565:            break;
1.13      christos  566:        case ']':
1.128     rillig    567:            brackets--;
1.85      rillig    568:            break;
1.1       cgd       569:        case '?':
                    570:        case '*':
1.128     rillig    571:            wild = TRUE;
1.85      rillig    572:            break;
1.13      christos  573:        default:
1.85      rillig    574:            break;
1.1       cgd       575:        }
                    576:     }
1.128     rillig    577:     return wild && brackets == 0 && braces == 0;
1.1       cgd       578: }
                    579:
1.181     rillig    580: /* See if any files match the pattern and add their names to the 'expansions'
                    581:  * list if they do.
                    582:  *
                    583:  * This is incomplete -- wildcards are only expanded in the final path
                    584:  * component, but not in directories like src/lib*c/file*.c, but it
                    585:  * will do for now (now being 1993 until at least 2020). To expand these,
                    586:  * use the ':sh' variable modifier such as in ${:!echo src/lib*c/file*.c!}.
1.1       cgd       587:  *
1.34      wiz       588:  * Input:
                    589:  *     pattern         Pattern to look for
1.143     rillig    590:  *     dir             Directory to search
1.34      wiz       591:  *     expansion       Place to store the results
1.1       cgd       592:  */
1.98      rillig    593: static void
1.144     rillig    594: DirMatchFiles(const char *pattern, CachedDir *dir, StringList *expansions)
1.1       cgd       595: {
1.181     rillig    596:     const char *dirName = dir->name;
                    597:     Boolean isDot = dirName[0] == '.' && dirName[1] == '\0';
1.164     rillig    598:     HashIter hi;
1.12      christos  599:
1.202     rillig    600:     /* XXX: Iterating over all hash entries is inefficient.  If the pattern
                    601:      * is a plain string without any wildcards, a direct lookup is faster. */
                    602:
1.181     rillig    603:     HashIter_Init(&hi, &dir->files);
                    604:     while (HashIter_Next(&hi) != NULL) {
                    605:        const char *base = hi.entry->key;
                    606:
                    607:        if (!Str_Match(base, pattern))
                    608:            continue;
1.12      christos  609:
1.1       cgd       610:        /*
1.181     rillig    611:         * Follow the UNIX convention that dot files are only found if the
                    612:         * pattern begins with a dot. The pattern '.*' does not match '.' or
                    613:         * '..' since these are not included in the directory cache.
                    614:         *
1.182     rillig    615:         * This means that the pattern '[a-z.]*' does not find '.file', which
                    616:         * is consistent with bash, NetBSD sh and csh.
1.1       cgd       617:         */
1.181     rillig    618:        if (base[0] == '.' && pattern[0] != '.')
                    619:            continue;
                    620:
1.1       cgd       621:        {
1.181     rillig    622:            char *fullName = isDot
                    623:                             ? bmake_strdup(base)
                    624:                             : str_concat3(dirName, "/", base);
                    625:            Lst_Append(expansions, fullName);
1.1       cgd       626:        }
                    627:     }
                    628: }
                    629:
1.91      rillig    630: /* Find the next closing brace in the string, taking nested braces into
                    631:  * account. */
1.80      rillig    632: static const char *
                    633: closing_brace(const char *p)
                    634: {
                    635:     int nest = 0;
1.91      rillig    636:     while (*p != '\0') {
1.106     rillig    637:        if (*p == '}' && nest == 0)
1.91      rillig    638:            break;
1.80      rillig    639:        if (*p == '{')
                    640:            nest++;
                    641:        if (*p == '}')
                    642:            nest--;
                    643:        p++;
                    644:     }
                    645:     return p;
                    646: }
                    647:
1.91      rillig    648: /* Find the next closing brace or comma in the string, taking nested braces
                    649:  * into account. */
1.80      rillig    650: static const char *
                    651: separator_comma(const char *p)
                    652: {
                    653:     int nest = 0;
1.91      rillig    654:     while (*p != '\0') {
1.106     rillig    655:        if ((*p == '}' || *p == ',') && nest == 0)
1.91      rillig    656:            break;
1.80      rillig    657:        if (*p == '{')
                    658:            nest++;
                    659:        if (*p == '}')
                    660:            nest--;
                    661:        p++;
                    662:     }
                    663:     return p;
                    664: }
                    665:
                    666: static Boolean
                    667: contains_wildcard(const char *p)
                    668: {
                    669:     for (; *p != '\0'; p++) {
1.85      rillig    670:        switch (*p) {
1.80      rillig    671:        case '*':
                    672:        case '?':
                    673:        case '{':
                    674:        case '[':
                    675:            return TRUE;
                    676:        }
                    677:     }
                    678:     return FALSE;
                    679: }
                    680:
                    681: static char *
                    682: concat3(const char *a, size_t a_len, const char *b, size_t b_len,
                    683:        const char *c, size_t c_len)
                    684: {
                    685:     size_t s_len = a_len + b_len + c_len;
                    686:     char *s = bmake_malloc(s_len + 1);
                    687:     memcpy(s, a, a_len);
                    688:     memcpy(s + a_len, b, b_len);
                    689:     memcpy(s + a_len + b_len, c, c_len);
                    690:     s[s_len] = '\0';
                    691:     return s;
                    692: }
                    693:
1.181     rillig    694: /* Expand curly braces like the C shell. Brace expansion by itself is purely
                    695:  * textual, the expansions are not looked up in the file system. But if an
                    696:  * expanded word contains wildcard characters, it is expanded further,
                    697:  * matching only the actually existing files.
                    698:  *
                    699:  * Example: "{a{b,c}}" expands to "ab" and "ac".
                    700:  * Example: "{a}" expands to "a".
                    701:  * Example: "{a,*.c}" expands to "a" and all "*.c" files that exist.
1.1       cgd       702:  *
1.34      wiz       703:  * Input:
                    704:  *     word            Entire word to expand
                    705:  *     brace           First curly brace in it
                    706:  *     path            Search path to use
                    707:  *     expansions      Place to store the expansions
1.1       cgd       708:  */
                    709: static void
1.144     rillig    710: DirExpandCurly(const char *word, const char *brace, SearchPath *path,
                    711:               StringList *expansions)
1.1       cgd       712: {
1.90      rillig    713:     const char *prefix, *middle, *piece, *middle_end, *suffix;
                    714:     size_t prefix_len, suffix_len;
                    715:
1.80      rillig    716:     /* Split the word into prefix '{' middle '}' suffix. */
1.1       cgd       717:
1.90      rillig    718:     middle = brace + 1;
                    719:     middle_end = closing_brace(middle);
1.80      rillig    720:     if (*middle_end == '\0') {
                    721:        Error("Unterminated {} clause \"%s\"", middle);
1.1       cgd       722:        return;
                    723:     }
1.78      rillig    724:
1.84      rillig    725:     prefix = word;
                    726:     prefix_len = (size_t)(brace - prefix);
                    727:     suffix = middle_end + 1;
                    728:     suffix_len = strlen(suffix);
1.80      rillig    729:
                    730:     /* Split the middle into pieces, separated by commas. */
                    731:
1.84      rillig    732:     piece = middle;
1.81      rillig    733:     while (piece < middle_end + 1) {
1.80      rillig    734:        const char *piece_end = separator_comma(piece);
                    735:        size_t piece_len = (size_t)(piece_end - piece);
1.1       cgd       736:
1.80      rillig    737:        char *file = concat3(prefix, prefix_len, piece, piece_len,
                    738:                             suffix, suffix_len);
                    739:
                    740:        if (contains_wildcard(file)) {
                    741:            Dir_Expand(file, path, expansions);
                    742:            free(file);
                    743:        } else {
1.119     rillig    744:            Lst_Append(expansions, file);
1.1       cgd       745:        }
1.80      rillig    746:
                    747:        piece = piece_end + 1;  /* skip over the comma or closing brace */
1.1       cgd       748:     }
                    749: }
                    750:
                    751:
1.183     rillig    752: /* Expand the word in each of the directories from the path. */
1.1       cgd       753: static void
1.183     rillig    754: DirExpandPath(const char *word, SearchPath *path, StringList *expansions)
1.1       cgd       755: {
1.144     rillig    756:     SearchPathNode *ln;
1.147     rillig    757:     for (ln = path->first; ln != NULL; ln = ln->next) {
                    758:        CachedDir *dir = ln->datum;
1.143     rillig    759:        DirMatchFiles(word, dir, expansions);
1.1       cgd       760:     }
                    761: }
                    762:
1.146     rillig    763: static void
1.184     rillig    764: PrintExpansions(StringList *expansions)
1.1       cgd       765: {
1.184     rillig    766:     const char *sep = "";
1.147     rillig    767:     StringListNode *ln;
1.184     rillig    768:     for (ln = expansions->first; ln != NULL; ln = ln->next) {
1.147     rillig    769:        const char *word = ln->datum;
1.184     rillig    770:        debug_printf("%s%s", sep, word);
                    771:        sep = " ";
1.146     rillig    772:     }
1.152     rillig    773:     debug_printf("\n");
1.1       cgd       774: }
                    775:
1.180     rillig    776: /* Expand the given word into a list of words by globbing it, looking in the
                    777:  * directories on the given search path.
1.1       cgd       778:  *
1.34      wiz       779:  * Input:
                    780:  *     word            the word to expand
1.180     rillig    781:  *     path            the directories in which to find the files
1.34      wiz       782:  *     expansions      the list on which to place the results
1.1       cgd       783:  */
                    784: void
1.144     rillig    785: Dir_Expand(const char *word, SearchPath *path, StringList *expansions)
1.1       cgd       786: {
1.85      rillig    787:     const char *cp;
1.1       cgd       788:
1.112     rillig    789:     assert(path != NULL);
                    790:     assert(expansions != NULL);
                    791:
1.92      rillig    792:     DIR_DEBUG1("Expanding \"%s\"... ", word);
1.12      christos  793:
1.5       cgd       794:     cp = strchr(word, '{');
1.1       cgd       795:     if (cp) {
                    796:        DirExpandCurly(word, cp, path, expansions);
                    797:     } else {
1.5       cgd       798:        cp = strchr(word, '/');
1.1       cgd       799:        if (cp) {
                    800:            /*
                    801:             * The thing has a directory component -- find the first wildcard
                    802:             * in the string.
                    803:             */
                    804:            for (cp = word; *cp; cp++) {
1.193     rillig    805:                if (*cp == '?' || *cp == '[' || *cp == '*') {
1.1       cgd       806:                    break;
                    807:                }
                    808:            }
1.193     rillig    809:
                    810:            if (*cp != '\0') {
1.1       cgd       811:                /*
                    812:                 * Back up to the start of the component
                    813:                 */
                    814:                while (cp > word && *cp != '/') {
                    815:                    cp--;
                    816:                }
                    817:                if (cp != word) {
1.174     rillig    818:                    char *prefix = bmake_strsedup(word, cp + 1);
1.1       cgd       819:                    /*
                    820:                     * If the glob isn't in the first component, try and find
                    821:                     * all the components up to the one with a wildcard.
                    822:                     */
1.174     rillig    823:                    char *dirpath = Dir_FindFile(prefix, path);
                    824:                    free(prefix);
1.1       cgd       825:                    /*
                    826:                     * dirpath is null if can't find the leading component
                    827:                     * XXX: Dir_FindFile won't find internal components.
                    828:                     * i.e. if the path contains ../Etc/Object and we're
                    829:                     * looking for Etc, it won't be found. Ah well.
                    830:                     * Probably not important.
                    831:                     */
1.48      christos  832:                    if (dirpath != NULL) {
1.5       cgd       833:                        char *dp = &dirpath[strlen(dirpath) - 1];
                    834:                        if (*dp == '/')
                    835:                            *dp = '\0';
1.167     rillig    836:                        path = Lst_New();
1.46      christos  837:                        (void)Dir_AddDir(path, dirpath);
1.183     rillig    838:                        DirExpandPath(cp + 1, path, expansions);
1.119     rillig    839:                        Lst_Free(path);
1.1       cgd       840:                    }
                    841:                } else {
                    842:                    /*
                    843:                     * Start the search from the local directory
                    844:                     */
1.183     rillig    845:                    DirExpandPath(word, path, expansions);
1.1       cgd       846:                }
                    847:            } else {
                    848:                /*
                    849:                 * Return the file -- this should never happen.
                    850:                 */
1.183     rillig    851:                DirExpandPath(word, path, expansions);
1.1       cgd       852:            }
                    853:        } else {
                    854:            /*
                    855:             * First the files in dot
                    856:             */
                    857:            DirMatchFiles(word, dot, expansions);
1.12      christos  858:
1.1       cgd       859:            /*
                    860:             * Then the files in every other directory on the path.
                    861:             */
1.183     rillig    862:            DirExpandPath(word, path, expansions);
1.1       cgd       863:        }
                    864:     }
1.146     rillig    865:     if (DEBUG(DIR))
1.184     rillig    866:        PrintExpansions(expansions);
1.1       cgd       867: }
                    868:
1.176     rillig    869: /* Find if the file with the given name exists in the given path.
                    870:  * Return the freshly allocated path to the file, or NULL. */
1.18      christos  871: static char *
1.177     rillig    872: DirLookup(CachedDir *dir, const char *base)
1.18      christos  873: {
1.85      rillig    874:     char *file;                        /* the current filename to check */
1.18      christos  875:
1.143     rillig    876:     DIR_DEBUG1("   %s ...\n", dir->name);
1.32      pk        877:
1.188     rillig    878:     if (HashTable_FindEntry(&dir->files, base) == NULL)
1.32      pk        879:        return NULL;
                    880:
1.177     rillig    881:     file = str_concat3(dir->name, "/", base);
1.92      rillig    882:     DIR_DEBUG1("   returning %s\n", file);
1.153     rillig    883:     dir->hits++;
                    884:     hits++;
1.32      pk        885:     return file;
1.18      christos  886: }
                    887:
                    888:
1.185     rillig    889: /* Find if the file with the given name exists in the given directory.
                    890:  * Return the freshly allocated path to the file, or NULL. */
1.18      christos  891: static char *
1.143     rillig    892: DirLookupSubdir(CachedDir *dir, const char *name)
1.18      christos  893: {
1.133     rillig    894:     struct make_stat mst;
1.185     rillig    895:     char *file = dir == dot ? bmake_strdup(name)
                    896:                            : str_concat3(dir->name, "/", name);
1.18      christos  897:
1.92      rillig    898:     DIR_DEBUG1("checking %s ...\n", file);
1.18      christos  899:
1.133     rillig    900:     if (cached_stat(file, &mst) == 0) {
1.153     rillig    901:        nearmisses++;
1.75      rillig    902:        return file;
1.18      christos  903:     }
1.46      christos  904:     free(file);
1.18      christos  905:     return NULL;
                    906: }
                    907:
1.185     rillig    908: /* Find if the file with the given name exists in the given path.
                    909:  * Return the freshly allocated path to the file, the empty string, or NULL.
                    910:  * Returning the empty string means that the search should be terminated.
1.32      pk        911:  */
                    912: static char *
1.143     rillig    913: DirLookupAbs(CachedDir *dir, const char *name, const char *cp)
1.32      pk        914: {
1.185     rillig    915:     const char *dnp;           /* pointer into dir->name */
                    916:     const char *np;            /* pointer into name */
1.32      pk        917:
1.143     rillig    918:     DIR_DEBUG1("   %s ...\n", dir->name);
1.32      pk        919:
1.85      rillig    920:     /*
                    921:      * If the file has a leading path component and that component
                    922:      * exactly matches the entire name of the current search
                    923:      * directory, we can attempt another cache lookup. And if we don't
                    924:      * have a hit, we can safely assume the file does not exist at all.
                    925:      */
1.185     rillig    926:     for (dnp = dir->name, np = name; *dnp != '\0' && *dnp == *np; dnp++, np++)
1.85      rillig    927:        continue;
1.185     rillig    928:     if (*dnp != '\0' || np != cp - 1)
1.85      rillig    929:        return NULL;
1.32      pk        930:
1.188     rillig    931:     if (HashTable_FindEntry(&dir->files, cp) == NULL) {
1.92      rillig    932:        DIR_DEBUG0("   must be here but isn't -- returning\n");
1.185     rillig    933:        return bmake_strdup("");        /* to terminate the search */
1.85      rillig    934:     }
1.32      pk        935:
1.153     rillig    936:     dir->hits++;
                    937:     hits++;
1.92      rillig    938:     DIR_DEBUG1("   returning %s\n", name);
1.85      rillig    939:     return bmake_strdup(name);
1.32      pk        940: }
                    941:
1.178     rillig    942: /* Find the file given on "." or curdir.
                    943:  * Return the freshly allocated path to the file, or NULL. */
1.21      thorpej   944: static char *
1.178     rillig    945: DirFindDot(const char *name, const char *base)
1.21      thorpej   946: {
                    947:
1.188     rillig    948:     if (HashTable_FindEntry(&dot->files, base) != NULL) {
1.92      rillig    949:        DIR_DEBUG0("   in '.'\n");
1.153     rillig    950:        hits++;
                    951:        dot->hits++;
1.85      rillig    952:        return bmake_strdup(name);
                    953:     }
1.188     rillig    954:
                    955:     if (cur != NULL && HashTable_FindEntry(&cur->files, base) != NULL) {
1.92      rillig    956:        DIR_DEBUG1("   in ${.CURDIR} = %s\n", cur->name);
1.153     rillig    957:        hits++;
                    958:        cur->hits++;
1.178     rillig    959:        return str_concat3(cur->name, "/", base);
1.85      rillig    960:     }
1.21      thorpej   961:
1.85      rillig    962:     return NULL;
1.21      thorpej   963: }
                    964:
1.179     rillig    965: /* Find the file with the given name along the given search path.
                    966:  *
                    967:  * If the file is found in a directory that is not on the path
                    968:  * already (either 'name' is absolute or it is a relative path
                    969:  * [ dir1/.../dirn/file ] which exists below one of the directories
                    970:  * already on the search path), its directory is added to the end
                    971:  * of the path, on the assumption that there will be more files in
                    972:  * that directory later on. Sometimes this is true. Sometimes not.
1.1       cgd       973:  *
1.34      wiz       974:  * Input:
                    975:  *     name            the file to find
1.179     rillig    976:  *     path            the directories to search, or NULL
1.34      wiz       977:  *
1.1       cgd       978:  * Results:
1.179     rillig    979:  *     The freshly allocated path to the file, or NULL.
1.1       cgd       980:  */
                    981: char *
1.144     rillig    982: Dir_FindFile(const char *name, SearchPath *path)
1.1       cgd       983: {
1.144     rillig    984:     SearchPathNode *ln;
1.85      rillig    985:     char *file;                        /* the current filename to check */
1.139     rillig    986:     const char *base;          /* Terminal name of file */
1.144     rillig    987:     Boolean hasLastDot = FALSE;        /* true if we should search dot last */
1.85      rillig    988:     Boolean hasSlash;          /* true if 'name' contains a / */
1.133     rillig    989:     struct make_stat mst;      /* Buffer for stat, if necessary */
1.85      rillig    990:     const char *trailing_dot = ".";
1.12      christos  991:
1.1       cgd       992:     /*
                    993:      * Find the final component of the name and note whether it has a
                    994:      * slash in it (the name, I mean)
                    995:      */
1.139     rillig    996:     base = strrchr(name, '/');
                    997:     if (base) {
1.1       cgd       998:        hasSlash = TRUE;
1.153     rillig    999:        base++;
1.1       cgd      1000:     } else {
                   1001:        hasSlash = FALSE;
1.140     rillig   1002:        base = name;
1.1       cgd      1003:     }
1.12      christos 1004:
1.92      rillig   1005:     DIR_DEBUG1("Searching for %s ...", name);
1.12      christos 1006:
1.112     rillig   1007:     if (path == NULL) {
1.92      rillig   1008:        DIR_DEBUG0("couldn't open path, file not found\n");
1.153     rillig   1009:        misses++;
1.57      dsl      1010:        return NULL;
1.1       cgd      1011:     }
1.12      christos 1012:
1.168     rillig   1013:     if ((ln = path->first) != NULL) {
                   1014:        CachedDir *dir = ln->datum;
1.143     rillig   1015:        if (dir == dotLast) {
1.31      reinoud  1016:            hasLastDot = TRUE;
1.92      rillig   1017:            DIR_DEBUG0("[dot last]...");
1.21      thorpej  1018:        }
1.18      christos 1019:     }
1.92      rillig   1020:     DIR_DEBUG0("\n");
1.18      christos 1021:
1.1       cgd      1022:     /*
1.32      pk       1023:      * If there's no leading directory components or if the leading
                   1024:      * directory component is exactly `./', consult the cached contents
                   1025:      * of each of the directories on the search path.
1.21      thorpej  1026:      */
1.139     rillig   1027:     if (!hasSlash || (base - name == 2 && *name == '.')) {
1.85      rillig   1028:        /*
                   1029:         * We look through all the directories on the path seeking one which
                   1030:         * contains the final component of the given name.  If such a beast
                   1031:         * is found, we concatenate the directory name and the final
                   1032:         * component and return the resulting string. If we don't find any
                   1033:         * such thing, we go on to phase two...
                   1034:         *
                   1035:         * No matter what, we always look for the file in the current
                   1036:         * directory before anywhere else (unless we found the magic
                   1037:         * DOTLAST path, in which case we search it last) and we *do not*
                   1038:         * add the ./ to it if it exists.
                   1039:         * This is so there are no conflicts between what the user
                   1040:         * specifies (fish.c) and what pmake finds (./fish.c).
                   1041:         */
1.178     rillig   1042:        if (!hasLastDot && (file = DirFindDot(name, base)) != NULL)
1.85      rillig   1043:            return file;
1.32      pk       1044:
1.168     rillig   1045:        for (; ln != NULL; ln = ln->next) {
                   1046:            CachedDir *dir = ln->datum;
1.143     rillig   1047:            if (dir == dotLast)
1.85      rillig   1048:                continue;
1.176     rillig   1049:            if ((file = DirLookup(dir, base)) != NULL)
1.85      rillig   1050:                return file;
                   1051:        }
1.21      thorpej  1052:
1.178     rillig   1053:        if (hasLastDot && (file = DirFindDot(name, base)) != NULL)
1.85      rillig   1054:            return file;
1.1       cgd      1055:     }
1.12      christos 1056:
1.1       cgd      1057:     /*
1.32      pk       1058:      * We didn't find the file on any directory in the search path.
1.1       cgd      1059:      * If the name doesn't contain a slash, that means it doesn't exist.
                   1060:      * If it *does* contain a slash, however, there is still hope: it
                   1061:      * could be in a subdirectory of one of the members of the search
                   1062:      * path. (eg. /usr/include and sys/types.h. The above search would
                   1063:      * fail to turn up types.h in /usr/include, but it *is* in
1.32      pk       1064:      * /usr/include/sys/types.h).
                   1065:      * [ This no longer applies: If we find such a beast, we assume there
1.1       cgd      1066:      * will be more (what else can we assume?) and add all but the last
                   1067:      * component of the resulting name onto the search path (at the
1.32      pk       1068:      * end).]
                   1069:      * This phase is only performed if the file is *not* absolute.
1.1       cgd      1070:      */
                   1071:     if (!hasSlash) {
1.92      rillig   1072:        DIR_DEBUG0("   failed.\n");
1.153     rillig   1073:        misses++;
1.57      dsl      1074:        return NULL;
1.1       cgd      1075:     }
1.12      christos 1076:
1.139     rillig   1077:     if (*base == '\0') {
1.63      sjg      1078:        /* we were given a trailing "/" */
1.139     rillig   1079:        base = trailing_dot;
1.63      sjg      1080:     }
                   1081:
1.32      pk       1082:     if (name[0] != '/') {
1.85      rillig   1083:        Boolean checkedDot = FALSE;
1.12      christos 1084:
1.92      rillig   1085:        DIR_DEBUG0("   Trying subdirectories...\n");
1.18      christos 1086:
1.35      sjg      1087:        if (!hasLastDot) {
1.85      rillig   1088:            if (dot) {
                   1089:                checkedDot = TRUE;
                   1090:                if ((file = DirLookupSubdir(dot, name)) != NULL)
                   1091:                    return file;
                   1092:            }
                   1093:            if (cur && (file = DirLookupSubdir(cur, name)) != NULL)
                   1094:                return file;
1.35      sjg      1095:        }
1.18      christos 1096:
1.168     rillig   1097:        for (ln = path->first; ln != NULL; ln = ln->next) {
                   1098:            CachedDir *dir = ln->datum;
1.143     rillig   1099:            if (dir == dotLast)
1.21      thorpej  1100:                continue;
1.143     rillig   1101:            if (dir == dot) {
1.85      rillig   1102:                if (checkedDot)
                   1103:                    continue;
1.1       cgd      1104:                checkedDot = TRUE;
1.35      sjg      1105:            }
1.168     rillig   1106:            if ((file = DirLookupSubdir(dir, name)) != NULL)
1.18      christos 1107:                return file;
1.1       cgd      1108:        }
1.12      christos 1109:
1.35      sjg      1110:        if (hasLastDot) {
1.85      rillig   1111:            if (dot && !checkedDot) {
                   1112:                checkedDot = TRUE;
                   1113:                if ((file = DirLookupSubdir(dot, name)) != NULL)
                   1114:                    return file;
                   1115:            }
                   1116:            if (cur && (file = DirLookupSubdir(cur, name)) != NULL)
                   1117:                return file;
1.35      sjg      1118:        }
1.21      thorpej  1119:
1.1       cgd      1120:        if (checkedDot) {
                   1121:            /*
                   1122:             * Already checked by the given name, since . was in the path,
                   1123:             * so no point in proceeding...
                   1124:             */
1.92      rillig   1125:            DIR_DEBUG0("   Checked . already, returning NULL\n");
1.57      dsl      1126:            return NULL;
1.32      pk       1127:        }
                   1128:
                   1129:     } else { /* name[0] == '/' */
                   1130:
                   1131:        /*
                   1132:         * For absolute names, compare directory path prefix against the
                   1133:         * the directory path of each member on the search path for an exact
                   1134:         * match. If we have an exact match on any member of the search path,
                   1135:         * use the cached contents of that member to lookup the final file
                   1136:         * component. If that lookup fails we can safely assume that the
                   1137:         * file does not exist at all.  This is signified by DirLookupAbs()
                   1138:         * returning an empty string.
                   1139:         */
1.92      rillig   1140:        DIR_DEBUG0("   Trying exact path matches...\n");
1.32      pk       1141:
1.85      rillig   1142:        if (!hasLastDot && cur &&
1.139     rillig   1143:            ((file = DirLookupAbs(cur, name, base)) != NULL)) {
1.71      riastrad 1144:            if (file[0] == '\0') {
                   1145:                free(file);
                   1146:                return NULL;
                   1147:            }
                   1148:            return file;
                   1149:        }
1.32      pk       1150:
1.168     rillig   1151:        for (ln = path->first; ln != NULL; ln = ln->next) {
                   1152:            CachedDir *dir = ln->datum;
1.143     rillig   1153:            if (dir == dotLast)
1.32      pk       1154:                continue;
1.143     rillig   1155:            if ((file = DirLookupAbs(dir, name, base)) != NULL) {
1.71      riastrad 1156:                if (file[0] == '\0') {
                   1157:                    free(file);
                   1158:                    return NULL;
                   1159:                }
                   1160:                return file;
1.32      pk       1161:            }
                   1162:        }
                   1163:
1.85      rillig   1164:        if (hasLastDot && cur &&
1.139     rillig   1165:            ((file = DirLookupAbs(cur, name, base)) != NULL)) {
1.71      riastrad 1166:            if (file[0] == '\0') {
                   1167:                free(file);
                   1168:                return NULL;
                   1169:            }
                   1170:            return file;
                   1171:        }
1.1       cgd      1172:     }
1.12      christos 1173:
1.1       cgd      1174:     /*
                   1175:      * Didn't find it that way, either. Sigh. Phase 3. Add its directory
                   1176:      * onto the search path in any case, just in case, then look for the
                   1177:      * thing in the hash table. If we find it, grand. We return a new
                   1178:      * copy of the name. Otherwise we sadly return a NULL pointer. Sigh.
                   1179:      * Note that if the directory holding the file doesn't exist, this will
                   1180:      * do an extra search of the final directory on the path. Unless something
                   1181:      * weird happens, this search won't succeed and life will be groovy.
                   1182:      *
                   1183:      * Sigh. We cannot add the directory onto the search path because
                   1184:      * of this amusing case:
                   1185:      * $(INSTALLDIR)/$(FILE): $(FILE)
                   1186:      *
                   1187:      * $(FILE) exists in $(INSTALLDIR) but not in the current one.
                   1188:      * When searching for $(FILE), we will find it in $(INSTALLDIR)
                   1189:      * b/c we added it here. This is not good...
                   1190:      */
1.196     rillig   1191: #if 0
1.139     rillig   1192:     if (base == trailing_dot) {
                   1193:        base = strrchr(name, '/');
1.153     rillig   1194:        base++;
1.63      sjg      1195:     }
1.139     rillig   1196:     base[-1] = '\0';
1.46      christos 1197:     (void)Dir_AddDir(path, name);
1.139     rillig   1198:     base[-1] = '/';
1.12      christos 1199:
1.153     rillig   1200:     bigmisses++;
1.119     rillig   1201:     ln = Lst_Last(path);
1.57      dsl      1202:     if (ln == NULL) {
                   1203:        return NULL;
1.1       cgd      1204:     } else {
1.143     rillig   1205:        dir = LstNode_Datum(ln);
1.1       cgd      1206:     }
1.12      christos 1207:
1.143     rillig   1208:     if (Hash_FindEntry(&dir->files, base) != NULL) {
1.75      rillig   1209:        return bmake_strdup(name);
1.1       cgd      1210:     } else {
1.57      dsl      1211:        return NULL;
1.1       cgd      1212:     }
1.196     rillig   1213: #else
1.92      rillig   1214:     DIR_DEBUG1("   Looking for \"%s\" ...\n", name);
1.12      christos 1215:
1.153     rillig   1216:     bigmisses++;
1.133     rillig   1217:     if (cached_stat(name, &mst) == 0) {
1.75      rillig   1218:        return bmake_strdup(name);
1.1       cgd      1219:     }
1.73      christos 1220:
1.92      rillig   1221:     DIR_DEBUG0("   failed. Returning NULL\n");
1.73      christos 1222:     return NULL;
1.196     rillig   1223: #endif
1.1       cgd      1224: }
                   1225:
1.40      chuck    1226:
1.161     rillig   1227: /* Search for a path starting at a given directory and then working our way
                   1228:  * up towards the root.
1.40      chuck    1229:  *
                   1230:  * Input:
                   1231:  *     here            starting directory
1.161     rillig   1232:  *     search_path     the relative path we are looking for
1.40      chuck    1233:  *
                   1234:  * Results:
1.161     rillig   1235:  *     The found path, or NULL.
1.40      chuck    1236:  */
1.161     rillig   1237: char *
                   1238: Dir_FindHereOrAbove(const char *here, const char *search_path)
1.85      rillig   1239: {
1.133     rillig   1240:     struct make_stat mst;
1.161     rillig   1241:     char *dirbase, *dirbase_end;
                   1242:     char *try, *try_end;
1.85      rillig   1243:
                   1244:     /* copy out our starting point */
1.161     rillig   1245:     dirbase = bmake_strdup(here);
1.129     rillig   1246:     dirbase_end = dirbase + strlen(dirbase);
1.85      rillig   1247:
                   1248:     /* loop until we determine a result */
1.161     rillig   1249:     for (;;) {
1.85      rillig   1250:
                   1251:        /* try and stat(2) it ... */
1.161     rillig   1252:        try = str_concat3(dirbase, "/", search_path);
1.133     rillig   1253:        if (cached_stat(try, &mst) != -1) {
1.85      rillig   1254:            /*
                   1255:             * success!  if we found a file, chop off
                   1256:             * the filename so we return a directory.
                   1257:             */
1.133     rillig   1258:            if ((mst.mst_mode & S_IFMT) != S_IFDIR) {
1.85      rillig   1259:                try_end = try + strlen(try);
                   1260:                while (try_end > try && *try_end != '/')
                   1261:                    try_end--;
                   1262:                if (try_end > try)
1.129     rillig   1263:                    *try_end = '\0';    /* chop! */
1.85      rillig   1264:            }
1.40      chuck    1265:
1.161     rillig   1266:            free(dirbase);
                   1267:            return try;
1.85      rillig   1268:        }
1.161     rillig   1269:        free(try);
1.40      chuck    1270:
1.85      rillig   1271:        /*
                   1272:         * nope, we didn't find it.  if we used up dirbase we've
                   1273:         * reached the root and failed.
                   1274:         */
1.129     rillig   1275:        if (dirbase_end == dirbase)
1.85      rillig   1276:            break;              /* failed! */
1.40      chuck    1277:
1.85      rillig   1278:        /*
                   1279:         * truncate dirbase from the end to move up a dir
                   1280:         */
1.129     rillig   1281:        while (dirbase_end > dirbase && *dirbase_end != '/')
                   1282:            dirbase_end--;
                   1283:        *dirbase_end = '\0';    /* chop! */
1.161     rillig   1284:     }
1.40      chuck    1285:
1.161     rillig   1286:     free(dirbase);
                   1287:     return NULL;
1.40      chuck    1288: }
                   1289:
1.201     rillig   1290: /* Search gn along dirSearchPath and store its modification time in gn->mtime.
                   1291:  * If no file is found, store 0 instead.
1.12      christos 1292:  *
1.201     rillig   1293:  * The found file is stored in gn->path, unless the node already had a path. */
                   1294: void
                   1295: Dir_UpdateMTime(GNode *gn, Boolean recheck)
1.1       cgd      1296: {
1.85      rillig   1297:     char *fullName;            /* the full pathname of name */
1.133     rillig   1298:     struct make_stat mst;      /* buffer for finding the mod time */
1.198     rillig   1299:     CachedStatsFlags flags;
1.12      christos 1300:
1.1       cgd      1301:     if (gn->type & OP_ARCHV) {
1.200     rillig   1302:        Arch_UpdateMTime(gn);
1.201     rillig   1303:        return;
                   1304:     }
                   1305:
                   1306:     if (gn->type & OP_PHONY) {
1.33      pk       1307:        gn->mtime = 0;
1.201     rillig   1308:        return;
                   1309:     }
                   1310:
                   1311:     if (gn->path == NULL) {
1.33      pk       1312:        if (gn->type & OP_NOPATH)
1.16      mycroft  1313:            fullName = NULL;
1.53      dsl      1314:        else {
1.45      christos 1315:            fullName = Dir_FindFile(gn->name, Suff_FindPath(gn));
1.62      sjg      1316:            if (fullName == NULL && gn->flags & FROM_DEPEND &&
1.127     rillig   1317:                !Lst_IsEmpty(gn->implicitParents)) {
1.62      sjg      1318:                char *cp;
                   1319:
                   1320:                cp = strrchr(gn->name, '/');
                   1321:                if (cp) {
                   1322:                    /*
                   1323:                     * This is an implied source, and it may have moved,
                   1324:                     * see if we can find it via the current .PATH
                   1325:                     */
                   1326:                    cp++;
1.76      rillig   1327:
1.62      sjg      1328:                    fullName = Dir_FindFile(cp, Suff_FindPath(gn));
                   1329:                    if (fullName) {
                   1330:                        /*
                   1331:                         * Put the found file in gn->path
                   1332:                         * so that we give that to the compiler.
                   1333:                         */
                   1334:                        gn->path = bmake_strdup(fullName);
1.67      christos 1335:                        if (!Job_RunTarget(".STALE", gn->fname))
                   1336:                            fprintf(stdout,
1.85      rillig   1337:                                    "%s: %s, %d: ignoring stale %s for %s, "
                   1338:                                    "found %s\n", progname, gn->fname,
                   1339:                                    gn->lineno,
                   1340:                                    makeDependfile, gn->name, fullName);
1.62      sjg      1341:                    }
                   1342:                }
                   1343:            }
1.92      rillig   1344:            DIR_DEBUG2("Found '%s' as '%s'\n",
                   1345:                       gn->name, fullName ? fullName : "(not found)");
1.53      dsl      1346:        }
1.1       cgd      1347:     } else {
                   1348:        fullName = gn->path;
                   1349:     }
1.12      christos 1350:
1.198     rillig   1351:     if (fullName == NULL)
1.56      joerg    1352:        fullName = bmake_strdup(gn->name);
1.1       cgd      1353:
1.198     rillig   1354:     flags = recheck ? CST_UPDATE : CST_NONE;
                   1355:     if (cached_stats(&mtimes, fullName, &mst, flags) < 0) {
1.1       cgd      1356:        if (gn->type & OP_MEMBER) {
1.6       jtc      1357:            if (fullName != gn->path)
                   1358:                free(fullName);
1.199     rillig   1359:            Arch_UpdateMemberMTime(gn);
1.201     rillig   1360:            return;
1.1       cgd      1361:        }
1.198     rillig   1362:
                   1363:        mst.mst_mtime = 0;
1.1       cgd      1364:     }
1.68      sjg      1365:
1.189     rillig   1366:     if (fullName != NULL && gn->path == NULL)
1.1       cgd      1367:        gn->path = fullName;
1.12      christos 1368:
1.133     rillig   1369:     gn->mtime = mst.mst_mtime;
1.1       cgd      1370: }
                   1371:
1.150     rillig   1372: /* Read the list of filenames in the directory and store the result
                   1373:  * in openDirectories.
                   1374:  *
                   1375:  * If a path is given, append the directory to that path.
1.1       cgd      1376:  *
1.34      wiz      1377:  * Input:
1.150     rillig   1378:  *     path            The path to which the directory should be
                   1379:  *                     added, or NULL to only add the directory to
                   1380:  *                     openDirectories
                   1381:  *     name            The name of the directory to add.
                   1382:  *                     The name is not normalized in any way.
1.1       cgd      1383:  */
1.143     rillig   1384: CachedDir *
1.144     rillig   1385: Dir_AddDir(SearchPath *path, const char *name)
1.1       cgd      1386: {
1.143     rillig   1387:     CachedDir *dir = NULL;     /* the added directory */
1.144     rillig   1388:     DIR *d;
                   1389:     struct dirent *dp;
1.21      thorpej  1390:
1.120     rillig   1391:     if (path != NULL && strcmp(name, ".DOTLAST") == 0) {
1.173     rillig   1392:        SearchPathNode *ln;
                   1393:
1.203     rillig   1394:        /* XXX: Linear search gets slow with thousands of entries. */
1.173     rillig   1395:        for (ln = path->first; ln != NULL; ln = ln->next) {
                   1396:            CachedDir *pathDir = ln->datum;
                   1397:            if (strcmp(pathDir->name, name) == 0)
                   1398:                return pathDir;
                   1399:        }
1.120     rillig   1400:
                   1401:        dotLast->refCount++;
                   1402:        Lst_Prepend(path, dotLast);
1.21      thorpej  1403:     }
1.12      christos 1404:
1.120     rillig   1405:     if (path != NULL)
1.158     rillig   1406:        dir = OpenDirs_Find(&openDirs, name);
                   1407:     if (dir != NULL) {
1.143     rillig   1408:        if (Lst_FindDatum(path, dir) == NULL) {
1.153     rillig   1409:            dir->refCount++;
1.143     rillig   1410:            Lst_Append(path, dir);
1.1       cgd      1411:        }
1.143     rillig   1412:        return dir;
1.120     rillig   1413:     }
                   1414:
                   1415:     DIR_DEBUG1("Caching %s ...", name);
1.12      christos 1416:
1.120     rillig   1417:     if ((d = opendir(name)) != NULL) {
1.194     rillig   1418:        dir = bmake_malloc(sizeof *dir);
1.143     rillig   1419:        dir->name = bmake_strdup(name);
                   1420:        dir->hits = 0;
                   1421:        dir->refCount = 1;
1.188     rillig   1422:        HashTable_Init(&dir->files);
1.12      christos 1423:
1.120     rillig   1424:        while ((dp = readdir(d)) != NULL) {
1.10      christos 1425: #if defined(sun) && defined(d_ino) /* d_ino is a sunos4 #define for d_fileno */
1.120     rillig   1426:            /*
                   1427:             * The sun directory library doesn't check for a 0 inode
                   1428:             * (0-inode slots just take up space), so we have to do
                   1429:             * it ourselves.
                   1430:             */
                   1431:            if (dp->d_fileno == 0) {
                   1432:                continue;
                   1433:            }
1.10      christos 1434: #endif /* sun && d_ino */
1.188     rillig   1435:            (void)HashTable_CreateEntry(&dir->files, dp->d_name, NULL);
1.1       cgd      1436:        }
1.120     rillig   1437:        (void)closedir(d);
1.158     rillig   1438:        OpenDirs_Add(&openDirs, dir);
1.120     rillig   1439:        if (path != NULL)
1.143     rillig   1440:            Lst_Append(path, dir);
1.1       cgd      1441:     }
1.120     rillig   1442:     DIR_DEBUG0("done\n");
1.143     rillig   1443:     return dir;
1.1       cgd      1444: }
                   1445:
1.187     rillig   1446: /* Return a copy of dirSearchPath, incrementing the reference counts for
                   1447:  * the contained directories. */
                   1448: SearchPath *
                   1449: Dir_CopyDirSearchPath(void)
1.1       cgd      1450: {
1.187     rillig   1451:     SearchPath *path = Lst_New();
                   1452:     SearchPathNode *ln;
                   1453:     for (ln = dirSearchPath->first; ln != NULL; ln = ln->next) {
                   1454:        CachedDir *dir = ln->datum;
                   1455:        dir->refCount++;
1.192     rillig   1456:        Lst_Append(path, dir);
1.187     rillig   1457:     }
                   1458:     return path;
1.1       cgd      1459: }
                   1460:
                   1461: /*-
                   1462:  *-----------------------------------------------------------------------
                   1463:  * Dir_MakeFlags --
                   1464:  *     Make a string by taking all the directories in the given search
                   1465:  *     path and preceding them by the given flag. Used by the suffix
                   1466:  *     module to create variables for compilers based on suffix search
                   1467:  *     paths.
                   1468:  *
1.34      wiz      1469:  * Input:
                   1470:  *     flag            flag which should precede each directory
                   1471:  *     path            list of directories
                   1472:  *
1.1       cgd      1473:  * Results:
                   1474:  *     The string mentioned above. Note that there is no space between
                   1475:  *     the given flag and each directory. The empty string is returned if
                   1476:  *     Things don't go well.
                   1477:  *
                   1478:  * Side Effects:
                   1479:  *     None
                   1480:  *-----------------------------------------------------------------------
                   1481:  */
                   1482: char *
1.144     rillig   1483: Dir_MakeFlags(const char *flag, SearchPath *path)
1.1       cgd      1484: {
1.88      rillig   1485:     Buffer buf;
1.144     rillig   1486:     SearchPathNode *ln;
1.12      christos 1487:
1.197     rillig   1488:     Buf_Init(&buf);
1.12      christos 1489:
1.112     rillig   1490:     if (path != NULL) {
1.147     rillig   1491:        for (ln = path->first; ln != NULL; ln = ln->next) {
                   1492:            CachedDir *dir = ln->datum;
1.88      rillig   1493:            Buf_AddStr(&buf, " ");
                   1494:            Buf_AddStr(&buf, flag);
1.143     rillig   1495:            Buf_AddStr(&buf, dir->name);
1.1       cgd      1496:        }
                   1497:     }
1.12      christos 1498:
1.88      rillig   1499:     return Buf_Destroy(&buf, FALSE);
1.1       cgd      1500: }
                   1501:
1.190     rillig   1502: /* Nuke a directory descriptor, if possible. Callback procedure for the
                   1503:  * suffixes module when destroying a search path.
1.1       cgd      1504:  *
1.34      wiz      1505:  * Input:
1.143     rillig   1506:  *     dirp            The directory descriptor to nuke
1.1       cgd      1507:  */
                   1508: void
1.143     rillig   1509: Dir_Destroy(void *dirp)
1.1       cgd      1510: {
1.143     rillig   1511:     CachedDir *dir = dirp;
1.153     rillig   1512:     dir->refCount--;
1.1       cgd      1513:
1.143     rillig   1514:     if (dir->refCount == 0) {
1.158     rillig   1515:        OpenDirs_Remove(&openDirs, dir->name);
1.1       cgd      1516:
1.188     rillig   1517:        HashTable_Done(&dir->files);
1.143     rillig   1518:        free(dir->name);
                   1519:        free(dir);
1.1       cgd      1520:     }
                   1521: }
                   1522:
1.190     rillig   1523: /* Clear out all elements from the given search path.
                   1524:  * The path is set to the empty list but is not destroyed. */
1.1       cgd      1525: void
1.144     rillig   1526: Dir_ClearPath(SearchPath *path)
1.1       cgd      1527: {
1.119     rillig   1528:     while (!Lst_IsEmpty(path)) {
1.143     rillig   1529:        CachedDir *dir = Lst_Dequeue(path);
                   1530:        Dir_Destroy(dir);
1.1       cgd      1531:     }
                   1532: }
1.12      christos 1533:
1.1       cgd      1534:
1.190     rillig   1535: /* Concatenate two paths, adding the second to the end of the first,
                   1536:  * skipping duplicates. */
1.1       cgd      1537: void
1.190     rillig   1538: Dir_Concat(SearchPath *dst, SearchPath *src)
1.1       cgd      1539: {
1.144     rillig   1540:     SearchPathNode *ln;
1.1       cgd      1541:
1.190     rillig   1542:     for (ln = src->first; ln != NULL; ln = ln->next) {
1.148     rillig   1543:        CachedDir *dir = ln->datum;
1.190     rillig   1544:        if (Lst_FindDatum(dst, dir) == NULL) {
1.153     rillig   1545:            dir->refCount++;
1.190     rillig   1546:            Lst_Append(dst, dir);
1.1       cgd      1547:        }
                   1548:     }
                   1549: }
                   1550:
1.105     rillig   1551: static int
                   1552: percentage(int num, int den)
                   1553: {
                   1554:     return den != 0 ? num * 100 / den : 0;
                   1555: }
                   1556:
1.1       cgd      1557: /********** DEBUG INFO **********/
1.5       cgd      1558: void
1.34      wiz      1559: Dir_PrintDirectories(void)
1.1       cgd      1560: {
1.144     rillig   1561:     CachedDirListNode *ln;
1.12      christos 1562:
1.152     rillig   1563:     debug_printf("#*** Directory Cache:\n");
                   1564:     debug_printf("# Stats: %d hits %d misses %d near misses %d losers (%d%%)\n",
                   1565:                 hits, misses, nearmisses, bigmisses,
                   1566:                 percentage(hits, hits + bigmisses + nearmisses));
                   1567:     debug_printf("# %-20s referenced\thits\n", "directory");
1.112     rillig   1568:
1.158     rillig   1569:     for (ln = openDirs.list->first; ln != NULL; ln = ln->next) {
1.147     rillig   1570:        CachedDir *dir = ln->datum;
1.152     rillig   1571:        debug_printf("# %-20s %10d\t%4d\n", dir->name, dir->refCount,
                   1572:                     dir->hits);
1.1       cgd      1573:     }
                   1574: }
                   1575:
1.5       cgd      1576: void
1.144     rillig   1577: Dir_PrintPath(SearchPath *path)
1.1       cgd      1578: {
1.146     rillig   1579:     SearchPathNode *node;
1.148     rillig   1580:     for (node = path->first; node != NULL; node = node->next) {
                   1581:        const CachedDir *dir = node->datum;
1.152     rillig   1582:        debug_printf("%s ", dir->name);
1.146     rillig   1583:     }
1.1       cgd      1584: }

CVSweb <webmaster@jp.NetBSD.org>