usr.bin/make/dir.c

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