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