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