Home | History | Annotate | Line # | Download | only in make
suff.c revision 1.211
      1  1.211    rillig /*	$NetBSD: suff.c,v 1.211 2020/10/21 08:00:06 rillig Exp $	*/
      2    1.8  christos 
      3    1.1       cgd /*
      4   1.13  christos  * Copyright (c) 1988, 1989, 1990, 1993
      5   1.13  christos  *	The Regents of the University of California.  All rights reserved.
      6   1.42       agc  *
      7   1.42       agc  * This code is derived from software contributed to Berkeley by
      8   1.42       agc  * Adam de Boor.
      9   1.42       agc  *
     10   1.42       agc  * Redistribution and use in source and binary forms, with or without
     11   1.42       agc  * modification, are permitted provided that the following conditions
     12   1.42       agc  * are met:
     13   1.42       agc  * 1. Redistributions of source code must retain the above copyright
     14   1.42       agc  *    notice, this list of conditions and the following disclaimer.
     15   1.42       agc  * 2. Redistributions in binary form must reproduce the above copyright
     16   1.42       agc  *    notice, this list of conditions and the following disclaimer in the
     17   1.42       agc  *    documentation and/or other materials provided with the distribution.
     18   1.42       agc  * 3. Neither the name of the University nor the names of its contributors
     19   1.42       agc  *    may be used to endorse or promote products derived from this software
     20   1.42       agc  *    without specific prior written permission.
     21   1.42       agc  *
     22   1.42       agc  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     23   1.42       agc  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     24   1.42       agc  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     25   1.42       agc  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     26   1.42       agc  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     27   1.42       agc  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     28   1.42       agc  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     29   1.42       agc  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     30   1.42       agc  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     31   1.42       agc  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     32   1.42       agc  * SUCH DAMAGE.
     33   1.42       agc  */
     34   1.42       agc 
     35   1.42       agc /*
     36    1.1       cgd  * Copyright (c) 1989 by Berkeley Softworks
     37    1.1       cgd  * All rights reserved.
     38    1.1       cgd  *
     39    1.1       cgd  * This code is derived from software contributed to Berkeley by
     40    1.1       cgd  * Adam de Boor.
     41    1.1       cgd  *
     42    1.1       cgd  * Redistribution and use in source and binary forms, with or without
     43    1.1       cgd  * modification, are permitted provided that the following conditions
     44    1.1       cgd  * are met:
     45    1.1       cgd  * 1. Redistributions of source code must retain the above copyright
     46    1.1       cgd  *    notice, this list of conditions and the following disclaimer.
     47    1.1       cgd  * 2. Redistributions in binary form must reproduce the above copyright
     48    1.1       cgd  *    notice, this list of conditions and the following disclaimer in the
     49    1.1       cgd  *    documentation and/or other materials provided with the distribution.
     50    1.1       cgd  * 3. All advertising materials mentioning features or use of this software
     51    1.1       cgd  *    must display the following acknowledgement:
     52    1.1       cgd  *	This product includes software developed by the University of
     53    1.1       cgd  *	California, Berkeley and its contributors.
     54    1.1       cgd  * 4. Neither the name of the University nor the names of its contributors
     55    1.1       cgd  *    may be used to endorse or promote products derived from this software
     56    1.1       cgd  *    without specific prior written permission.
     57    1.1       cgd  *
     58    1.1       cgd  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
     59    1.1       cgd  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     60    1.1       cgd  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
     61    1.1       cgd  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
     62    1.1       cgd  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
     63    1.1       cgd  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
     64    1.1       cgd  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     65    1.1       cgd  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
     66    1.1       cgd  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
     67    1.1       cgd  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
     68    1.1       cgd  * SUCH DAMAGE.
     69    1.1       cgd  */
     70    1.1       cgd 
     71    1.1       cgd /*-
     72    1.1       cgd  * suff.c --
     73    1.1       cgd  *	Functions to maintain suffix lists and find implicit dependents
     74    1.1       cgd  *	using suffix transformation rules
     75    1.1       cgd  *
     76    1.1       cgd  * Interface:
     77  1.170    rillig  *	Suff_Init	Initialize all things to do with suffixes.
     78    1.1       cgd  *
     79  1.179    rillig  *	Suff_End	Clean up the module
     80    1.6       jtc  *
     81  1.170    rillig  *	Suff_DoPaths	This function is used to make life easier
     82  1.170    rillig  *			when searching for a file according to its
     83  1.170    rillig  *			suffix. It takes the global search path,
     84  1.170    rillig  *			as defined using the .PATH: target, and appends
     85  1.170    rillig  *			its directories to the path of each of the
     86  1.170    rillig  *			defined suffixes, as specified using
     87  1.170    rillig  *			.PATH<suffix>: targets. In addition, all
     88  1.170    rillig  *			directories given for suffixes labeled as
     89  1.170    rillig  *			include files or libraries, using the .INCLUDES
     90  1.170    rillig  *			or .LIBS targets, are played with using
     91  1.170    rillig  *			Dir_MakeFlags to create the .INCLUDES and
     92  1.170    rillig  *			.LIBS global variables.
     93  1.170    rillig  *
     94  1.170    rillig  *	Suff_ClearSuffixes
     95  1.170    rillig  *			Clear out all the suffixes and defined
     96  1.170    rillig  *			transformations.
     97  1.170    rillig  *
     98  1.170    rillig  *	Suff_IsTransform
     99  1.170    rillig  *			Return TRUE if the passed string is the lhs
    100  1.170    rillig  *			of a transformation rule.
    101  1.170    rillig  *
    102  1.170    rillig  *	Suff_AddSuffix	Add the passed string as another known suffix.
    103  1.170    rillig  *
    104  1.170    rillig  *	Suff_GetPath	Return the search path for the given suffix.
    105  1.170    rillig  *
    106  1.170    rillig  *	Suff_AddInclude
    107  1.170    rillig  *			Mark the given suffix as denoting an include file.
    108  1.170    rillig  *
    109  1.170    rillig  *	Suff_AddLib	Mark the given suffix as denoting a library.
    110  1.170    rillig  *
    111  1.170    rillig  *	Suff_AddTransform
    112  1.170    rillig  *			Add another transformation to the suffix
    113  1.170    rillig  *			graph. Returns  GNode suitable for framing, I
    114  1.170    rillig  *			mean, tacking commands, attributes, etc. on.
    115  1.170    rillig  *
    116  1.170    rillig  *	Suff_SetNull	Define the suffix to consider the suffix of
    117  1.170    rillig  *			any file that doesn't have a known one.
    118  1.170    rillig  *
    119  1.170    rillig  *	Suff_FindDeps	Find implicit sources for and the location of
    120  1.170    rillig  *			a target based on its suffix. Returns the
    121  1.170    rillig  *			bottom-most node added to the graph or NULL
    122  1.170    rillig  *			if the target had no implicit sources.
    123    1.1       cgd  *
    124  1.170    rillig  *	Suff_FindPath	Return the appropriate path to search in order to
    125  1.170    rillig  *			find the node.
    126    1.1       cgd  */
    127    1.1       cgd 
    128  1.176    rillig #include "make.h"
    129  1.176    rillig #include "dir.h"
    130    1.1       cgd 
    131  1.155    rillig /*	"@(#)suff.c	8.4 (Berkeley) 3/21/94"	*/
    132  1.211    rillig MAKE_RCSID("$NetBSD: suff.c,v 1.211 2020/10/21 08:00:06 rillig Exp $");
    133  1.155    rillig 
    134  1.171    rillig #define SUFF_DEBUG0(text) DEBUG0(SUFF, text)
    135  1.171    rillig #define SUFF_DEBUG1(fmt, arg1) DEBUG1(SUFF, fmt, arg1)
    136  1.171    rillig #define SUFF_DEBUG2(fmt, arg1, arg2) DEBUG2(SUFF, fmt, arg1, arg2)
    137  1.171    rillig #define SUFF_DEBUG3(fmt, arg1, arg2, arg3) DEBUG3(SUFF, fmt, arg1, arg2, arg3)
    138  1.198    rillig #define SUFF_DEBUG4(fmt, arg1, arg2, arg3, arg4) \
    139  1.198    rillig 	DEBUG4(SUFF, fmt, arg1, arg2, arg3, arg4)
    140  1.140    rillig 
    141  1.157    rillig typedef List SuffList;
    142  1.157    rillig typedef ListNode SuffListNode;
    143  1.157    rillig 
    144  1.157    rillig typedef List SrcList;
    145  1.157    rillig typedef ListNode SrcListNode;
    146  1.157    rillig 
    147  1.157    rillig static SuffList *sufflist;	/* List of suffixes */
    148   1.73     joerg #ifdef CLEANUP
    149  1.157    rillig static SuffList *suffClean;	/* List of suffixes to be cleaned */
    150   1.73     joerg #endif
    151  1.157    rillig static SrcList *srclist;	/* List of sources */
    152  1.157    rillig static GNodeList *transforms;	/* List of transformation rules */
    153    1.1       cgd 
    154   1.73     joerg static int        sNum = 0;	/* Counter for assigning suffix numbers */
    155    1.1       cgd 
    156  1.189    rillig typedef enum SuffFlags {
    157   1.96    rillig     SUFF_INCLUDE	= 0x01,	/* One which is #include'd */
    158   1.96    rillig     SUFF_LIBRARY	= 0x02,	/* One which contains a library */
    159   1.96    rillig     SUFF_NULL		= 0x04	/* The empty suffix */
    160  1.122    rillig     /* XXX: Why is SUFF_NULL needed? Wouldn't nameLen == 0 mean the same? */
    161   1.96    rillig } SuffFlags;
    162   1.96    rillig 
    163  1.122    rillig ENUM_FLAGS_RTTI_3(SuffFlags,
    164  1.122    rillig 		  SUFF_INCLUDE, SUFF_LIBRARY, SUFF_NULL);
    165  1.122    rillig 
    166  1.157    rillig typedef List SuffListList;
    167  1.157    rillig 
    168    1.1       cgd /*
    169    1.1       cgd  * Structure describing an individual suffix.
    170    1.1       cgd  */
    171   1.96    rillig typedef struct Suff {
    172  1.170    rillig     char         *name;		/* The suffix itself, such as ".c" */
    173  1.164    rillig     size_t	 nameLen;	/* Length of the name, to avoid strlen calls */
    174  1.170    rillig     SuffFlags	 flags;		/* Type of suffix */
    175  1.157    rillig     SearchPath	 *searchPath;	/* The path along which files of this suffix
    176    1.1       cgd 				 * may be found */
    177  1.170    rillig     int          sNum;		/* The suffix number */
    178  1.206    rillig     int		 refCount;	/* Reference count of list membership
    179  1.206    rillig 				 * and several other places */
    180  1.157    rillig     SuffList	 *parents;	/* Suffixes we have a transformation to */
    181  1.157    rillig     SuffList	 *children;	/* Suffixes we have a transformation from */
    182  1.157    rillig     SuffListList *ref;		/* Lists in which this suffix is referenced */
    183    1.1       cgd } Suff;
    184    1.1       cgd 
    185    1.1       cgd /*
    186    1.1       cgd  * Structure used in the search for implied sources.
    187    1.1       cgd  */
    188  1.163    rillig typedef struct Src {
    189  1.170    rillig     char *file;			/* The file to look for */
    190  1.170    rillig     char *pref;			/* Prefix from which file was formed */
    191  1.170    rillig     Suff *suff;			/* The suffix on the file */
    192  1.170    rillig     struct Src *parent;		/* The Src for which this is a source */
    193  1.170    rillig     GNode *node;		/* The node describing the file */
    194  1.170    rillig     int children;		/* Count of existing children (so we don't free
    195   1.73     joerg 				 * this thing too early or never nuke it) */
    196   1.73     joerg #ifdef DEBUG_SRC
    197  1.211    rillig     SrcList *childrenList;
    198   1.73     joerg #endif
    199    1.1       cgd } Src;
    200    1.1       cgd 
    201  1.170    rillig static Suff *suffNull;		/* The NULL suffix for this run */
    202  1.170    rillig static Suff *emptySuff;		/* The empty suffix required for POSIX
    203   1.73     joerg 				 * single-suffix transformation rules */
    204    1.1       cgd 
    205    1.4       cgd 
    206  1.160    rillig static void SuffFindDeps(GNode *, SrcList *);
    207  1.157    rillig static void SuffExpandWildcards(GNodeListNode *, GNode *);
    208    1.4       cgd 
    209   1.73     joerg 	/*************** Lst Predicates ****************/
    210    1.1       cgd /*-
    211    1.1       cgd  *-----------------------------------------------------------------------
    212    1.1       cgd  * SuffStrIsPrefix  --
    213    1.1       cgd  *	See if pref is a prefix of str.
    214    1.1       cgd  *
    215   1.39       wiz  * Input:
    216   1.39       wiz  *	pref		possible prefix
    217   1.39       wiz  *	str		string to check
    218   1.39       wiz  *
    219    1.1       cgd  * Results:
    220    1.1       cgd  *	NULL if it ain't, pointer to character in str after prefix if so
    221    1.1       cgd  *
    222    1.1       cgd  * Side Effects:
    223    1.1       cgd  *	None
    224    1.1       cgd  *-----------------------------------------------------------------------
    225    1.1       cgd  */
    226   1.67       dsl static const char *
    227   1.67       dsl SuffStrIsPrefix(const char *pref, const char *str)
    228    1.1       cgd {
    229    1.1       cgd     while (*str && *pref == *str) {
    230    1.1       cgd 	pref++;
    231    1.1       cgd 	str++;
    232    1.1       cgd     }
    233    1.1       cgd 
    234   1.88    rillig     return *pref ? NULL : str;
    235    1.1       cgd }
    236    1.1       cgd 
    237  1.199    rillig /* See if suff is a suffix of str.
    238    1.1       cgd  *
    239   1.39       wiz  * Input:
    240   1.39       wiz  *	s		possible suffix
    241  1.207    rillig  *	nameLen		length of the string to examine
    242  1.207    rillig  *	nameEnd		end of the string to examine
    243   1.39       wiz  *
    244    1.1       cgd  * Results:
    245  1.199    rillig  *	NULL if it ain't, pointer to the start of suffix in str if it is.
    246    1.1       cgd  */
    247    1.1       cgd static char *
    248  1.207    rillig SuffSuffGetSuffix(const Suff *s, size_t nameLen, char *nameEnd)
    249    1.1       cgd {
    250  1.170    rillig     char *p1;			/* Pointer into suffix name */
    251  1.170    rillig     char *p2;			/* Pointer into string being examined */
    252    1.1       cgd 
    253  1.207    rillig     if (nameLen < s->nameLen)
    254   1.22     itohy 	return NULL;		/* this string is shorter than the suffix */
    255   1.22     itohy 
    256    1.1       cgd     p1 = s->name + s->nameLen;
    257  1.207    rillig     p2 = nameEnd;
    258    1.1       cgd 
    259    1.1       cgd     while (p1 >= s->name && *p1 == *p2) {
    260    1.1       cgd 	p1--;
    261    1.1       cgd 	p2--;
    262    1.1       cgd     }
    263    1.1       cgd 
    264  1.207    rillig     /* XXX: s->name - 1 invokes undefined behavior */
    265  1.199    rillig     return p1 == s->name - 1 ? p2 + 1 : NULL;
    266    1.1       cgd }
    267    1.1       cgd 
    268  1.130    rillig /* Predicate form of SuffSuffGetSuffix, for Lst_Find. */
    269  1.129    rillig static Boolean
    270  1.207    rillig SuffSuffIsSuffix(const Suff *suff, size_t nameLen, char *nameEnd)
    271    1.1       cgd {
    272  1.207    rillig     return SuffSuffGetSuffix(suff, nameLen, nameEnd) != NULL;
    273    1.1       cgd }
    274    1.1       cgd 
    275  1.166    rillig static Suff *
    276  1.162    rillig FindSuffByName(const char *name)
    277    1.1       cgd {
    278  1.162    rillig     SuffListNode *ln;
    279  1.162    rillig 
    280  1.162    rillig     for (ln = sufflist->first; ln != NULL; ln = ln->next) {
    281  1.178    rillig 	Suff *suff = ln->datum;
    282  1.178    rillig 	if (strcmp(suff->name, name) == 0)
    283  1.178    rillig 	    return suff;
    284  1.162    rillig     }
    285  1.162    rillig     return NULL;
    286    1.1       cgd }
    287    1.1       cgd 
    288  1.210    rillig static GNode *
    289  1.210    rillig FindTransformByName(const char *name)
    290    1.1       cgd {
    291  1.210    rillig     GNodeListNode *ln;
    292  1.210    rillig     for (ln = transforms->first; ln != NULL; ln = ln->next) {
    293  1.210    rillig         GNode *gn = ln->datum;
    294  1.210    rillig         if (strcmp(gn->name, name) == 0)
    295  1.210    rillig             return gn;
    296  1.210    rillig     }
    297  1.210    rillig     return NULL;
    298    1.1       cgd }
    299    1.1       cgd 
    300   1.93    rillig 	    /*********** Maintenance Functions ************/
    301   1.73     joerg 
    302   1.73     joerg static void
    303  1.198    rillig SuffUnRef(SuffList *list, Suff *suff)
    304   1.73     joerg {
    305  1.198    rillig     SuffListNode *ln = Lst_FindDatum(list, suff);
    306   1.73     joerg     if (ln != NULL) {
    307  1.198    rillig 	Lst_Remove(list, ln);
    308  1.198    rillig 	suff->refCount--;
    309   1.73     joerg     }
    310   1.73     joerg }
    311   1.73     joerg 
    312  1.134    rillig /* Free up all memory associated with the given suffix structure. */
    313   1.73     joerg static void
    314   1.73     joerg SuffFree(void *sp)
    315   1.71  christos {
    316  1.134    rillig     Suff *s = (Suff *)sp;
    317    1.6       jtc 
    318   1.73     joerg     if (s == suffNull)
    319   1.73     joerg 	suffNull = NULL;
    320    1.6       jtc 
    321   1.73     joerg     if (s == emptySuff)
    322   1.73     joerg 	emptySuff = NULL;
    323    1.6       jtc 
    324  1.198    rillig #if 0
    325   1.73     joerg     /* We don't delete suffixes in order, so we cannot use this */
    326   1.73     joerg     if (s->refCount)
    327   1.73     joerg 	Punt("Internal error deleting suffix `%s' with refcount = %d", s->name,
    328   1.73     joerg 	    s->refCount);
    329   1.73     joerg #endif
    330    1.6       jtc 
    331  1.125    rillig     Lst_Free(s->ref);
    332  1.125    rillig     Lst_Free(s->children);
    333  1.125    rillig     Lst_Free(s->parents);
    334  1.125    rillig     Lst_Destroy(s->searchPath, Dir_Destroy);
    335   1.19  christos 
    336   1.73     joerg     free(s->name);
    337   1.73     joerg     free(s);
    338    1.1       cgd }
    339    1.1       cgd 
    340  1.134    rillig /* Remove the suffix from the list, and free if it is otherwise unused. */
    341    1.6       jtc static void
    342  1.198    rillig SuffRemove(SuffList *list, Suff *suff)
    343    1.6       jtc {
    344  1.198    rillig     SuffUnRef(list, suff);
    345  1.198    rillig     if (suff->refCount == 0) {
    346  1.198    rillig 	SuffUnRef(sufflist, suff);
    347  1.198    rillig 	SuffFree(suff);
    348   1.73     joerg     }
    349    1.6       jtc }
    350  1.101    rillig 
    351  1.198    rillig /* Insert the suffix into the list, keeping the list ordered by suffix
    352  1.198    rillig  * numbers. */
    353   1.73     joerg static void
    354  1.198    rillig SuffInsert(SuffList *list, Suff *suff)
    355    1.1       cgd {
    356  1.198    rillig     SuffListNode *ln;
    357  1.198    rillig     Suff *listSuff = NULL;
    358   1.71  christos 
    359  1.198    rillig     for (ln = list->first; ln != NULL; ln = ln->next) {
    360  1.198    rillig 	listSuff = ln->datum;
    361  1.198    rillig 	if (listSuff->sNum >= suff->sNum)
    362   1.73     joerg 	    break;
    363   1.73     joerg     }
    364   1.71  christos 
    365   1.73     joerg     if (ln == NULL) {
    366  1.198    rillig 	SUFF_DEBUG2("inserting \"%s\" (%d) at end of list\n",
    367  1.198    rillig 		    suff->name, suff->sNum);
    368  1.198    rillig 	Lst_Append(list, suff);
    369  1.198    rillig 	suff->refCount++;
    370  1.198    rillig 	Lst_Append(suff->ref, list);
    371  1.198    rillig     } else if (listSuff->sNum != suff->sNum) {
    372  1.198    rillig 	SUFF_DEBUG4("inserting \"%s\" (%d) before \"%s\" (%d)\n",
    373  1.198    rillig 		    suff->name, suff->sNum, listSuff->name, listSuff->sNum);
    374  1.198    rillig 	Lst_InsertBefore(list, ln, suff);
    375  1.198    rillig 	suff->refCount++;
    376  1.198    rillig 	Lst_Append(suff->ref, list);
    377  1.140    rillig     } else {
    378  1.198    rillig 	SUFF_DEBUG2("\"%s\" (%d) is already there\n", suff->name, suff->sNum);
    379   1.73     joerg     }
    380   1.71  christos }
    381    1.1       cgd 
    382  1.117    rillig static Suff *
    383  1.117    rillig SuffNew(const char *name)
    384  1.117    rillig {
    385  1.117    rillig     Suff *s = bmake_malloc(sizeof(Suff));
    386  1.117    rillig 
    387  1.170    rillig     s->name = bmake_strdup(name);
    388  1.170    rillig     s->nameLen = strlen(s->name);
    389  1.180    rillig     s->searchPath = Lst_New();
    390  1.180    rillig     s->children = Lst_New();
    391  1.180    rillig     s->parents = Lst_New();
    392  1.180    rillig     s->ref = Lst_New();
    393  1.170    rillig     s->sNum = sNum++;
    394  1.170    rillig     s->flags = 0;
    395  1.170    rillig     s->refCount = 1;
    396  1.117    rillig 
    397  1.117    rillig     return s;
    398  1.117    rillig }
    399  1.117    rillig 
    400  1.134    rillig /* This is gross. Nuke the list of suffixes but keep all transformation
    401  1.134    rillig  * rules around. The transformation graph is destroyed in this process, but
    402  1.134    rillig  * we leave the list of rules so when a new graph is formed the rules will
    403  1.134    rillig  * remain. This function is called from the parse module when a .SUFFIXES:\n
    404  1.134    rillig  * line is encountered. */
    405   1.73     joerg void
    406   1.73     joerg Suff_ClearSuffixes(void)
    407   1.71  christos {
    408   1.73     joerg #ifdef CLEANUP
    409  1.125    rillig     Lst_MoveAll(suffClean, sufflist);
    410   1.73     joerg #endif
    411  1.180    rillig     sufflist = Lst_New();
    412   1.73     joerg     sNum = 0;
    413   1.75       sjg     if (suffNull)
    414   1.75       sjg 	SuffFree(suffNull);
    415  1.117    rillig     emptySuff = suffNull = SuffNew("");
    416   1.75       sjg 
    417   1.75       sjg     Dir_Concat(suffNull->searchPath, dirSearchPath);
    418  1.170    rillig     suffNull->flags = SUFF_NULL;
    419    1.1       cgd }
    420    1.1       cgd 
    421  1.196    rillig /* Parse a transformation string such as ".c.o" to find its two component
    422  1.196    rillig  * suffixes (the source ".c" and the target ".o").  If there are no such
    423  1.196    rillig  * suffixes, try a single-suffix transformation as well.
    424    1.1       cgd  *
    425  1.196    rillig  * Return TRUE if the string is a valid transformation.
    426    1.1       cgd  */
    427   1.73     joerg static Boolean
    428  1.167    rillig SuffParseTransform(const char *str, Suff **out_src, Suff **out_targ)
    429   1.39       wiz {
    430  1.196    rillig     SuffListNode *ln;
    431  1.196    rillig     Suff *singleSrc = NULL;
    432   1.73     joerg 
    433   1.73     joerg     /*
    434   1.73     joerg      * Loop looking first for a suffix that matches the start of the
    435   1.73     joerg      * string and then for one that exactly matches the rest of it. If
    436   1.73     joerg      * we can find two that meet these criteria, we've successfully
    437   1.73     joerg      * parsed the string.
    438   1.73     joerg      */
    439  1.196    rillig     for (ln = sufflist->first; ln != NULL; ln = ln->next) {
    440  1.196    rillig 	Suff *src = ln->datum;
    441  1.197    rillig 
    442  1.197    rillig 	if (SuffStrIsPrefix(src->name, str) == NULL)
    443  1.196    rillig 	    continue;
    444  1.196    rillig 
    445  1.196    rillig 	if (str[src->nameLen] == '\0') {
    446  1.196    rillig 	    singleSrc = src;
    447   1.73     joerg 	} else {
    448  1.196    rillig 	    Suff *targ = FindSuffByName(str + src->nameLen);
    449  1.166    rillig 	    if (targ != NULL) {
    450  1.134    rillig 		*out_src = src;
    451  1.166    rillig 		*out_targ = targ;
    452   1.88    rillig 		return TRUE;
    453   1.73     joerg 	    }
    454   1.73     joerg 	}
    455   1.73     joerg     }
    456  1.196    rillig 
    457  1.196    rillig     if (singleSrc != NULL) {
    458  1.196    rillig 	/*
    459  1.196    rillig 	 * Not so fast Mr. Smith! There was a suffix that encompassed
    460  1.196    rillig 	 * the entire string, so we assume it was a transformation
    461  1.196    rillig 	 * to the null suffix (thank you POSIX). We still prefer to
    462  1.196    rillig 	 * find a double rule over a singleton, hence we leave this
    463  1.196    rillig 	 * check until the end.
    464  1.196    rillig 	 *
    465  1.196    rillig 	 * XXX: Use emptySuff over suffNull?
    466  1.196    rillig 	 */
    467  1.196    rillig 	*out_src = singleSrc;
    468  1.196    rillig 	*out_targ = suffNull;
    469  1.196    rillig 	return TRUE;
    470  1.196    rillig     }
    471  1.196    rillig     return FALSE;
    472    1.1       cgd }
    473    1.1       cgd 
    474  1.134    rillig /* Return TRUE if the given string is a transformation rule, that is, a
    475  1.134    rillig  * concatenation of two known suffixes. */
    476   1.73     joerg Boolean
    477  1.167    rillig Suff_IsTransform(const char *str)
    478    1.1       cgd {
    479  1.170    rillig     Suff *src, *targ;
    480    1.1       cgd 
    481   1.88    rillig     return SuffParseTransform(str, &src, &targ);
    482    1.1       cgd }
    483    1.1       cgd 
    484  1.210    rillig /* Add the transformation rule to the list of rules and place the
    485  1.210    rillig  * transformation itself in the graph.
    486  1.210    rillig  *
    487  1.210    rillig  * The transformation is linked to the two suffixes mentioned in the name.
    488    1.1       cgd  *
    489   1.73     joerg  * Input:
    490  1.210    rillig  *	name		must have the form ".from.to" or just ".from"
    491   1.39       wiz  *
    492   1.73     joerg  * Results:
    493  1.210    rillig  *	The created or existing transformation node in the transforms list
    494    1.1       cgd  */
    495   1.73     joerg GNode *
    496  1.210    rillig Suff_AddTransform(const char *name)
    497    1.1       cgd {
    498   1.73     joerg     GNode         *gn;		/* GNode of transformation rule */
    499   1.73     joerg     Suff          *s,		/* source suffix */
    500   1.93    rillig 		  *t;		/* target suffix */
    501  1.142    rillig     Boolean ok;
    502    1.1       cgd 
    503  1.210    rillig     gn = FindTransformByName(name);
    504  1.210    rillig     if (gn == NULL) {
    505   1.73     joerg 	/*
    506   1.73     joerg 	 * Make a new graph node for the transformation. It will be filled in
    507   1.73     joerg 	 * by the Parse module.
    508   1.73     joerg 	 */
    509  1.210    rillig 	gn = Targ_NewGN(name);
    510  1.125    rillig 	Lst_Append(transforms, gn);
    511   1.73     joerg     } else {
    512   1.73     joerg 	/*
    513   1.73     joerg 	 * New specification for transformation rule. Just nuke the old list
    514   1.73     joerg 	 * of commands so they can be filled in again... We don't actually
    515   1.73     joerg 	 * free the commands themselves, because a given command can be
    516   1.73     joerg 	 * attached to several different transformations.
    517   1.73     joerg 	 */
    518  1.125    rillig 	Lst_Free(gn->commands);
    519  1.125    rillig 	Lst_Free(gn->children);
    520  1.180    rillig 	gn->commands = Lst_New();
    521  1.180    rillig 	gn->children = Lst_New();
    522   1.73     joerg     }
    523    1.1       cgd 
    524   1.73     joerg     gn->type = OP_TRANSFORM;
    525    1.1       cgd 
    526  1.210    rillig     ok = SuffParseTransform(name, &s, &t);
    527  1.142    rillig     assert(ok);
    528  1.142    rillig     (void)ok;
    529    1.1       cgd 
    530   1.73     joerg     /*
    531   1.73     joerg      * link the two together in the proper relationship and order
    532   1.73     joerg      */
    533  1.140    rillig     SUFF_DEBUG2("defining transformation from `%s' to `%s'\n",
    534   1.73     joerg 		s->name, t->name);
    535   1.73     joerg     SuffInsert(t->children, s);
    536   1.73     joerg     SuffInsert(s->parents, t);
    537    1.1       cgd 
    538   1.88    rillig     return gn;
    539    1.1       cgd }
    540    1.1       cgd 
    541  1.134    rillig /* Handle the finish of a transformation definition, removing the
    542  1.134    rillig  * transformation from the graph if it has neither commands nor sources.
    543  1.134    rillig  *
    544  1.134    rillig  * If the node has no commands or children, the children and parents lists
    545  1.134    rillig  * of the affected suffixes are altered.
    546   1.71  christos  *
    547   1.73     joerg  * Input:
    548  1.150    rillig  *	gn		Node for transformation
    549    1.1       cgd  */
    550  1.150    rillig void
    551  1.150    rillig Suff_EndTransform(GNode *gn)
    552    1.1       cgd {
    553  1.125    rillig     if ((gn->type & OP_DOUBLEDEP) && !Lst_IsEmpty(gn->cohorts))
    554  1.195    rillig 	gn = gn->cohorts->last->datum;
    555  1.125    rillig     if ((gn->type & OP_TRANSFORM) && Lst_IsEmpty(gn->commands) &&
    556  1.125    rillig 	Lst_IsEmpty(gn->children))
    557   1.73     joerg     {
    558   1.73     joerg 	Suff	*s, *t;
    559   1.73     joerg 
    560   1.73     joerg 	/*
    561   1.73     joerg 	 * SuffParseTransform() may fail for special rules which are not
    562   1.73     joerg 	 * actual transformation rules. (e.g. .DEFAULT)
    563   1.73     joerg 	 */
    564   1.73     joerg 	if (SuffParseTransform(gn->name, &s, &t)) {
    565  1.157    rillig 	    SuffList *p;
    566   1.73     joerg 
    567  1.140    rillig 	    SUFF_DEBUG2("deleting transformation from `%s' to `%s'\n",
    568  1.140    rillig 			s->name, t->name);
    569   1.73     joerg 
    570   1.73     joerg 	    /*
    571   1.73     joerg 	     * Store s->parents because s could be deleted in SuffRemove
    572   1.73     joerg 	     */
    573   1.73     joerg 	    p = s->parents;
    574   1.20  christos 
    575   1.73     joerg 	    /*
    576   1.73     joerg 	     * Remove the source from the target's children list. We check for a
    577   1.73     joerg 	     * nil return to handle a beanhead saying something like
    578   1.73     joerg 	     *  .c.o .c.o:
    579   1.73     joerg 	     *
    580   1.73     joerg 	     * We'll be called twice when the next target is seen, but .c and .o
    581   1.73     joerg 	     * are only linked once...
    582   1.73     joerg 	     */
    583   1.73     joerg 	    SuffRemove(t->children, s);
    584    1.1       cgd 
    585   1.73     joerg 	    /*
    586   1.73     joerg 	     * Remove the target from the source's parents list
    587   1.73     joerg 	     */
    588   1.73     joerg 	    SuffRemove(p, t);
    589   1.73     joerg 	}
    590  1.140    rillig     } else if (gn->type & OP_TRANSFORM) {
    591  1.148    rillig 	SUFF_DEBUG1("transformation %s complete\n", gn->name);
    592    1.1       cgd     }
    593    1.1       cgd }
    594    1.1       cgd 
    595  1.159    rillig /* Called from Suff_AddSuffix via Lst_ForEachUntil to search through the list of
    596  1.134    rillig  * existing transformation rules and rebuild the transformation graph when
    597  1.134    rillig  * it has been destroyed by Suff_ClearSuffixes. If the given rule is a
    598  1.134    rillig  * transformation involving this suffix and another, existing suffix, the
    599  1.134    rillig  * proper relationship is established between the two.
    600  1.134    rillig  *
    601  1.134    rillig  * The appropriate links will be made between this suffix and others if
    602  1.134    rillig  * transformation rules exist for it.
    603    1.1       cgd  *
    604   1.39       wiz  * Input:
    605  1.192    rillig  *	transform	Transformation to test
    606  1.192    rillig  *	s		Suffix to rebuild
    607    1.1       cgd  */
    608  1.165    rillig static void
    609  1.192    rillig SuffRebuildGraph(GNode *transform, Suff *s)
    610    1.6       jtc {
    611  1.207    rillig     char *name = transform->name;
    612  1.207    rillig     size_t nameLen = strlen(name);
    613  1.170    rillig     char *cp;
    614   1.73     joerg 
    615   1.73     joerg     /*
    616   1.73     joerg      * First see if it is a transformation from this suffix.
    617   1.73     joerg      */
    618  1.207    rillig     cp = UNCONST(SuffStrIsPrefix(s->name, name));
    619   1.73     joerg     if (cp != NULL) {
    620  1.166    rillig 	Suff *s2 = FindSuffByName(cp);
    621  1.166    rillig 	if (s2 != NULL) {
    622  1.166    rillig 	    /* Link in and return, since it can't be anything else. */
    623   1.73     joerg 	    SuffInsert(s2->children, s);
    624   1.73     joerg 	    SuffInsert(s->parents, s2);
    625  1.165    rillig 	    return;
    626   1.73     joerg 	}
    627   1.73     joerg     }
    628    1.1       cgd 
    629   1.73     joerg     /*
    630   1.73     joerg      * Not from, maybe to?
    631   1.73     joerg      */
    632  1.207    rillig     cp = SuffSuffGetSuffix(s, nameLen, name + nameLen);
    633   1.73     joerg     if (cp != NULL) {
    634  1.166    rillig 	Suff *s2;
    635  1.157    rillig 
    636  1.166    rillig 	/* Null-terminate the source suffix in order to find it. */
    637  1.166    rillig 	/* XXX: don't modify strings, not even temporarily */
    638  1.199    rillig 	cp[0] = '\0';
    639  1.207    rillig 	s2 = FindSuffByName(name);
    640  1.199    rillig 	cp[0] = s->name[0];		/* restore */
    641  1.166    rillig 
    642  1.166    rillig 	if (s2 != NULL) {
    643  1.166    rillig 	    /* establish the proper relationship */
    644   1.73     joerg 	    SuffInsert(s->children, s2);
    645   1.73     joerg 	    SuffInsert(s2->parents, s);
    646   1.73     joerg 	}
    647    1.1       cgd     }
    648   1.71  christos }
    649   1.71  christos 
    650  1.186    rillig /* During Suff_AddSuffix, search through the list of existing targets and find
    651  1.186    rillig  * if any of the existing targets can be turned into a transformation rule.
    652  1.134    rillig  *
    653  1.134    rillig  * If such a target is found and the target is the current main target, the
    654  1.134    rillig  * main target is set to NULL and the next target examined (if that exists)
    655  1.134    rillig  * becomes the main target.
    656   1.71  christos  *
    657   1.73     joerg  * Results:
    658  1.186    rillig  *	TRUE iff a new main target has been selected.
    659   1.71  christos  */
    660  1.186    rillig static Boolean
    661  1.188    rillig SuffScanTargets(GNode *target, GNode **inout_main, Suff *gs_s, Boolean *gs_r)
    662   1.71  christos {
    663  1.170    rillig     Suff *s, *t;
    664  1.170    rillig     char *ptr;
    665   1.73     joerg 
    666  1.188    rillig     if (*inout_main == NULL && *gs_r && !(target->type & OP_NOTARGET)) {
    667  1.188    rillig 	*inout_main = target;
    668   1.73     joerg 	Targ_SetMain(target);
    669  1.186    rillig 	return TRUE;
    670   1.73     joerg     }
    671   1.73     joerg 
    672  1.108    rillig     if (target->type == OP_TRANSFORM)
    673  1.186    rillig 	return FALSE;
    674   1.73     joerg 
    675  1.186    rillig     if ((ptr = strstr(target->name, gs_s->name)) == NULL ||
    676   1.73     joerg 	ptr == target->name)
    677  1.186    rillig 	return FALSE;
    678   1.73     joerg 
    679   1.73     joerg     if (SuffParseTransform(target->name, &s, &t)) {
    680  1.188    rillig 	if (*inout_main == target) {
    681  1.186    rillig 	    *gs_r = TRUE;
    682  1.188    rillig 	    *inout_main = NULL;
    683   1.73     joerg 	    Targ_SetMain(NULL);
    684   1.71  christos 	}
    685  1.125    rillig 	Lst_Free(target->children);
    686  1.180    rillig 	target->children = Lst_New();
    687   1.73     joerg 	target->type = OP_TRANSFORM;
    688   1.73     joerg 	/*
    689   1.73     joerg 	 * link the two together in the proper relationship and order
    690   1.73     joerg 	 */
    691  1.140    rillig 	SUFF_DEBUG2("defining transformation from `%s' to `%s'\n",
    692  1.140    rillig 		    s->name, t->name);
    693   1.73     joerg 	SuffInsert(t->children, s);
    694   1.73     joerg 	SuffInsert(s->parents, t);
    695   1.71  christos     }
    696  1.186    rillig     return FALSE;
    697   1.14  christos }
    698   1.14  christos 
    699  1.187    rillig /* Look at all existing targets to see if adding this suffix will make one
    700  1.187    rillig  * of the current targets mutate into a suffix rule.
    701  1.187    rillig  *
    702  1.187    rillig  * This is ugly, but other makes treat all targets that start with a '.' as
    703  1.187    rillig  * suffix rules. */
    704  1.187    rillig static void
    705  1.188    rillig UpdateTargets(GNode **inout_main, Suff *s)
    706  1.187    rillig {
    707  1.187    rillig     Boolean r = FALSE;
    708  1.187    rillig     GNodeListNode *ln;
    709  1.187    rillig     for (ln = Targ_List()->first; ln != NULL; ln = ln->next) {
    710  1.187    rillig 	GNode *gn = ln->datum;
    711  1.188    rillig 	if (SuffScanTargets(gn, inout_main, s, &r))
    712  1.187    rillig 	    break;
    713  1.187    rillig     }
    714  1.187    rillig }
    715  1.187    rillig 
    716  1.134    rillig /* Add the suffix to the end of the list of known suffixes.
    717  1.134    rillig  * Should we restructure the suffix graph? Make doesn't...
    718  1.134    rillig  *
    719  1.134    rillig  * A GNode is created for the suffix and a Suff structure is created and
    720  1.134    rillig  * added to the suffixes list unless the suffix was already known.
    721  1.134    rillig  * The mainNode passed can be modified if a target mutated into a
    722  1.134    rillig  * transform and that target happened to be the main target.
    723    1.1       cgd  *
    724   1.39       wiz  * Input:
    725  1.134    rillig  *	name		the name of the suffix to add
    726    1.1       cgd  */
    727    1.1       cgd void
    728  1.188    rillig Suff_AddSuffix(const char *name, GNode **inout_main)
    729    1.1       cgd {
    730  1.192    rillig     GNodeListNode *ln;
    731  1.192    rillig 
    732  1.166    rillig     Suff *s = FindSuffByName(name);
    733  1.166    rillig     if (s != NULL)
    734  1.166    rillig 	return;
    735  1.166    rillig 
    736  1.166    rillig     s = SuffNew(name);
    737  1.166    rillig     Lst_Append(sufflist, s);
    738   1.73     joerg 
    739  1.188    rillig     UpdateTargets(inout_main, s);
    740   1.71  christos 
    741  1.166    rillig     /*
    742  1.166    rillig      * Look for any existing transformations from or to this suffix.
    743  1.166    rillig      * XXX: Only do this after a Suff_ClearSuffixes?
    744  1.166    rillig      */
    745  1.192    rillig     for (ln = transforms->first; ln != NULL; ln = ln->next)
    746  1.192    rillig 	SuffRebuildGraph(ln->datum, s);
    747    1.1       cgd }
    748    1.1       cgd 
    749  1.134    rillig /* Return the search path for the given suffix, or NULL. */
    750  1.157    rillig SearchPath *
    751  1.167    rillig Suff_GetPath(const char *sname)
    752    1.1       cgd {
    753  1.166    rillig     Suff *s = FindSuffByName(sname);
    754  1.166    rillig     return s != NULL ? s->searchPath : NULL;
    755    1.1       cgd }
    756    1.1       cgd 
    757  1.134    rillig /* Extend the search paths for all suffixes to include the default search
    758  1.134    rillig  * path.
    759    1.1       cgd  *
    760  1.134    rillig  * The searchPath field of all the suffixes is extended by the directories
    761  1.134    rillig  * in dirSearchPath. If paths were specified for the ".h" suffix, the
    762  1.134    rillig  * directories are stuffed into a global variable called ".INCLUDES" with
    763  1.134    rillig  * each directory preceded by a -I. The same is done for the ".a" suffix,
    764  1.134    rillig  * except the variable is called ".LIBS" and the flag is -L.
    765    1.1       cgd  */
    766    1.1       cgd void
    767   1.39       wiz Suff_DoPaths(void)
    768    1.1       cgd {
    769  1.157    rillig     SuffListNode *ln;
    770  1.157    rillig     char *ptr;
    771  1.157    rillig     SearchPath *inIncludes; /* Cumulative .INCLUDES path */
    772  1.157    rillig     SearchPath *inLibs;	    /* Cumulative .LIBS path */
    773    1.1       cgd 
    774  1.180    rillig     inIncludes = Lst_New();
    775  1.180    rillig     inLibs = Lst_New();
    776    1.1       cgd 
    777  1.181    rillig     for (ln = sufflist->first; ln != NULL; ln = ln->next) {
    778  1.195    rillig 	Suff *s = ln->datum;
    779  1.125    rillig 	if (!Lst_IsEmpty(s->searchPath)) {
    780    1.1       cgd #ifdef INCLUDES
    781    1.1       cgd 	    if (s->flags & SUFF_INCLUDE) {
    782    1.1       cgd 		Dir_Concat(inIncludes, s->searchPath);
    783    1.1       cgd 	    }
    784  1.154    rillig #endif
    785    1.1       cgd #ifdef LIBRARIES
    786    1.1       cgd 	    if (s->flags & SUFF_LIBRARY) {
    787    1.1       cgd 		Dir_Concat(inLibs, s->searchPath);
    788    1.1       cgd 	    }
    789  1.154    rillig #endif
    790    1.1       cgd 	    Dir_Concat(s->searchPath, dirSearchPath);
    791    1.1       cgd 	} else {
    792  1.125    rillig 	    Lst_Destroy(s->searchPath, Dir_Destroy);
    793  1.125    rillig 	    s->searchPath = Lst_Copy(dirSearchPath, Dir_CopyDir);
    794    1.1       cgd 	}
    795    1.1       cgd     }
    796    1.1       cgd 
    797   1.87    rillig     Var_Set(".INCLUDES", ptr = Dir_MakeFlags("-I", inIncludes), VAR_GLOBAL);
    798    1.6       jtc     free(ptr);
    799   1.87    rillig     Var_Set(".LIBS", ptr = Dir_MakeFlags("-L", inLibs), VAR_GLOBAL);
    800    1.6       jtc     free(ptr);
    801    1.1       cgd 
    802  1.125    rillig     Lst_Destroy(inIncludes, Dir_Destroy);
    803  1.125    rillig     Lst_Destroy(inLibs, Dir_Destroy);
    804    1.1       cgd }
    805    1.1       cgd 
    806  1.134    rillig /* Add the given suffix as a type of file which gets included.
    807  1.134    rillig  * Called from the parse module when a .INCLUDES line is parsed.
    808  1.134    rillig  * The suffix must have already been defined.
    809  1.134    rillig  * The SUFF_INCLUDE bit is set in the suffix's flags field.
    810    1.1       cgd  *
    811   1.39       wiz  * Input:
    812   1.39       wiz  *	sname		Name of the suffix to mark
    813    1.1       cgd  */
    814    1.1       cgd void
    815  1.167    rillig Suff_AddInclude(const char *sname)
    816    1.1       cgd {
    817  1.166    rillig     Suff *suff = FindSuffByName(sname);
    818  1.166    rillig     if (suff != NULL)
    819  1.166    rillig 	suff->flags |= SUFF_INCLUDE;
    820    1.1       cgd }
    821    1.1       cgd 
    822  1.134    rillig /* Add the given suffix as a type of file which is a library.
    823  1.134    rillig  * Called from the parse module when parsing a .LIBS line.
    824  1.134    rillig  * The suffix must have been defined via .SUFFIXES before this is called.
    825  1.134    rillig  * The SUFF_LIBRARY bit is set in the suffix's flags field.
    826    1.1       cgd  *
    827   1.39       wiz  * Input:
    828   1.39       wiz  *	sname		Name of the suffix to mark
    829    1.1       cgd  */
    830    1.1       cgd void
    831  1.134    rillig Suff_AddLib(const char *sname)
    832    1.1       cgd {
    833  1.166    rillig     Suff *suff = FindSuffByName(sname);
    834  1.166    rillig     if (suff != NULL)
    835  1.166    rillig 	suff->flags |= SUFF_LIBRARY;
    836    1.1       cgd }
    837    1.1       cgd 
    838   1.93    rillig 	  /********** Implicit Source Search Functions *********/
    839    1.1       cgd 
    840  1.149    rillig #ifdef DEBUG_SRC
    841  1.165    rillig static void
    842  1.193    rillig SrcList_PrintAddrs(SrcList *srcList)
    843  1.149    rillig {
    844  1.193    rillig     SrcListNode *ln;
    845  1.194    rillig     for (ln = srcList->first; ln != NULL; ln = ln->next)
    846  1.194    rillig 	debug_printf(" %p", ln->datum);
    847  1.200    rillig     debug_printf("\n");
    848  1.149    rillig }
    849  1.149    rillig #endif
    850  1.149    rillig 
    851  1.209    rillig static Src *
    852  1.209    rillig SrcNew(char *name, char *pref, Suff *suff, Src *parent, GNode *gn)
    853  1.209    rillig {
    854  1.209    rillig     Src *src = bmake_malloc(sizeof *src);
    855  1.209    rillig 
    856  1.209    rillig     src->file = name;
    857  1.209    rillig     src->pref = pref;
    858  1.209    rillig     src->suff = suff;
    859  1.209    rillig     src->parent = parent;
    860  1.209    rillig     src->node = gn;
    861  1.209    rillig     src->children = 0;
    862  1.209    rillig #ifdef DEBUG_SRC
    863  1.211    rillig     src->childrenList = Lst_New();
    864  1.209    rillig #endif
    865  1.209    rillig 
    866  1.209    rillig     return src;
    867  1.209    rillig }
    868  1.209    rillig 
    869  1.190    rillig static void
    870  1.190    rillig SuffAddSrc(Suff *suff, SrcList *srcList, Src *targ, char *srcName,
    871  1.190    rillig 	   const char *debug_tag)
    872  1.190    rillig {
    873  1.209    rillig     Src *s2 = SrcNew(srcName, targ->pref, suff, targ, NULL);
    874  1.190    rillig     suff->refCount++;
    875  1.190    rillig     targ->children++;
    876  1.190    rillig     Lst_Append(srcList, s2);
    877  1.190    rillig #ifdef DEBUG_SRC
    878  1.211    rillig     Lst_Append(targ->childrenList, s2);
    879  1.190    rillig     debug_printf("%s add %p %p to %p:", debug_tag, targ, s2, srcList);
    880  1.193    rillig     SrcList_PrintAddrs(srcList);
    881  1.190    rillig #endif
    882  1.190    rillig }
    883  1.190    rillig 
    884  1.134    rillig /* Add a suffix as a Src structure to the given list with its parent
    885  1.134    rillig  * being the given Src structure. If the suffix is the null suffix,
    886  1.134    rillig  * the prefix is used unaltered as the file name in the Src structure.
    887    1.1       cgd  *
    888   1.39       wiz  * Input:
    889  1.184    rillig  *	suff		suffix for which to create a Src structure
    890  1.184    rillig  *	srcList		list for the new Src
    891  1.184    rillig  *	targ		parent for the new Src
    892    1.1       cgd  */
    893  1.165    rillig static void
    894  1.190    rillig SuffAddSources(Suff *suff, SrcList *srcList, Src *targ)
    895    1.1       cgd {
    896  1.184    rillig     if ((suff->flags & SUFF_NULL) && suff->name[0] != '\0') {
    897   1.73     joerg 	/*
    898   1.73     joerg 	 * If the suffix has been marked as the NULL suffix, also create a Src
    899   1.73     joerg 	 * structure for a file with no suffix attached. Two birds, and all
    900   1.73     joerg 	 * that...
    901   1.73     joerg 	 */
    902  1.190    rillig 	SuffAddSrc(suff, srcList, targ, bmake_strdup(targ->pref), "1");
    903    1.1       cgd     }
    904  1.190    rillig     SuffAddSrc(suff, srcList, targ, str_concat2(targ->pref, suff->name), "2");
    905    1.1       cgd }
    906    1.1       cgd 
    907  1.134    rillig /* Add all the children of targ as Src structures to the given list.
    908    1.1       cgd  *
    909   1.73     joerg  * Input:
    910   1.73     joerg  *	l		list to which to add the new level
    911   1.73     joerg  *	targ		Src structure to use as the parent
    912    1.1       cgd  */
    913    1.1       cgd static void
    914  1.157    rillig SuffAddLevel(SrcList *l, Src *targ)
    915    1.1       cgd {
    916  1.183    rillig     SrcListNode *ln;
    917  1.183    rillig     for (ln = targ->suff->children->first; ln != NULL; ln = ln->next) {
    918  1.183    rillig 	Suff *childSuff = ln->datum;
    919  1.190    rillig 	SuffAddSources(childSuff, l, targ);
    920  1.183    rillig     }
    921    1.1       cgd }
    922    1.1       cgd 
    923  1.134    rillig /* Free the first Src in the list that doesn't have a reference count.
    924  1.134    rillig  * Return whether a Src was removed. */
    925  1.134    rillig static Boolean
    926  1.157    rillig SuffRemoveSrc(SrcList *l)
    927   1.73     joerg {
    928  1.157    rillig     SrcListNode *ln;
    929   1.73     joerg 
    930  1.125    rillig     Lst_Open(l);
    931  1.100    rillig 
    932   1.73     joerg #ifdef DEBUG_SRC
    933  1.194    rillig     debug_printf("cleaning %p:", l);
    934  1.193    rillig     SrcList_PrintAddrs(l);
    935   1.73     joerg #endif
    936   1.73     joerg 
    937  1.125    rillig     while ((ln = Lst_Next(l)) != NULL) {
    938  1.195    rillig 	Src *s = ln->datum;
    939   1.73     joerg 	if (s->children == 0) {
    940   1.73     joerg 	    free(s->file);
    941   1.73     joerg 	    if (!s->parent)
    942   1.73     joerg 		free(s->pref);
    943   1.73     joerg 	    else {
    944   1.73     joerg #ifdef DEBUG_SRC
    945  1.211    rillig 		SrcListNode *ln2 = Lst_FindDatum(s->parent->childrenList, s);
    946   1.84  dholland 		if (ln2 != NULL)
    947  1.211    rillig 		    Lst_Remove(s->parent->childrenList, ln2);
    948   1.73     joerg #endif
    949   1.73     joerg 		--s->parent->children;
    950   1.73     joerg 	    }
    951   1.73     joerg #ifdef DEBUG_SRC
    952  1.172    rillig 	    debug_printf("free: [l=%p] p=%p %d\n", l, s, s->children);
    953  1.211    rillig 	    Lst_Free(s->childrenList);
    954   1.73     joerg #endif
    955  1.125    rillig 	    Lst_Remove(l, ln);
    956   1.73     joerg 	    free(s);
    957  1.125    rillig 	    Lst_Close(l);
    958   1.73     joerg 	    return TRUE;
    959   1.73     joerg 	}
    960   1.73     joerg #ifdef DEBUG_SRC
    961   1.73     joerg 	else {
    962  1.194    rillig 	    debug_printf("keep: [l=%p] p=%p %d:", l, s, s->children);
    963  1.211    rillig 	    SrcList_PrintAddrs(s->childrenList);
    964   1.73     joerg 	}
    965   1.73     joerg #endif
    966   1.73     joerg     }
    967    1.6       jtc 
    968  1.125    rillig     Lst_Close(l);
    969    1.6       jtc 
    970  1.134    rillig     return FALSE;
    971    1.1       cgd }
    972    1.1       cgd 
    973  1.134    rillig /* Find the first existing file/target in the list srcs.
    974    1.1       cgd  *
    975   1.39       wiz  * Input:
    976   1.73     joerg  *	srcs		list of Src structures to search through
    977   1.39       wiz  *
    978    1.1       cgd  * Results:
    979  1.134    rillig  *	The lowest structure in the chain of transformations, or NULL.
    980    1.1       cgd  */
    981    1.1       cgd static Src *
    982  1.157    rillig SuffFindThem(SrcList *srcs, SrcList *slst)
    983    1.1       cgd {
    984   1.73     joerg     Src            *s;		/* current Src */
    985   1.73     joerg     Src		   *rs;		/* returned Src */
    986   1.73     joerg     char	   *ptr;
    987   1.73     joerg 
    988   1.73     joerg     rs = NULL;
    989    1.1       cgd 
    990  1.125    rillig     while (!Lst_IsEmpty(srcs)) {
    991  1.125    rillig 	s = Lst_Dequeue(srcs);
    992    1.1       cgd 
    993  1.140    rillig 	SUFF_DEBUG1("\ttrying %s...", s->file);
    994    1.6       jtc 
    995    1.1       cgd 	/*
    996   1.73     joerg 	 * A file is considered to exist if either a node exists in the
    997   1.73     joerg 	 * graph for it or the file actually exists.
    998    1.1       cgd 	 */
    999  1.168    rillig 	if (Targ_FindNode(s->file) != NULL) {
   1000    1.6       jtc #ifdef DEBUG_SRC
   1001  1.172    rillig 	    debug_printf("remove %p from %p\n", s, srcs);
   1002    1.6       jtc #endif
   1003   1.73     joerg 	    rs = s;
   1004   1.73     joerg 	    break;
   1005   1.73     joerg 	}
   1006   1.73     joerg 
   1007   1.73     joerg 	if ((ptr = Dir_FindFile(s->file, s->suff->searchPath)) != NULL) {
   1008   1.73     joerg 	    rs = s;
   1009    1.6       jtc #ifdef DEBUG_SRC
   1010  1.172    rillig 	    debug_printf("remove %p from %p\n", s, srcs);
   1011    1.6       jtc #endif
   1012   1.73     joerg 	    free(ptr);
   1013    1.1       cgd 	    break;
   1014    1.1       cgd 	}
   1015    1.6       jtc 
   1016  1.140    rillig 	SUFF_DEBUG0("not there\n");
   1017    1.6       jtc 
   1018   1.73     joerg 	SuffAddLevel(srcs, s);
   1019  1.125    rillig 	Lst_Append(slst, s);
   1020    1.6       jtc     }
   1021    1.6       jtc 
   1022  1.140    rillig     if (rs) {
   1023  1.140    rillig 	SUFF_DEBUG0("got it\n");
   1024   1.73     joerg     }
   1025   1.88    rillig     return rs;
   1026    1.1       cgd }
   1027    1.1       cgd 
   1028  1.134    rillig /* See if any of the children of the target in the Src structure is one from
   1029  1.134    rillig  * which the target can be transformed. If there is one, a Src structure is
   1030  1.134    rillig  * put together for it and returned.
   1031    1.1       cgd  *
   1032   1.39       wiz  * Input:
   1033  1.134    rillig  *	targ		Src to play with
   1034   1.73     joerg  *
   1035   1.73     joerg  * Results:
   1036  1.134    rillig  *	The Src of the "winning" child, or NULL.
   1037    1.1       cgd  */
   1038   1.73     joerg static Src *
   1039  1.157    rillig SuffFindCmds(Src *targ, SrcList *slst)
   1040    1.1       cgd {
   1041  1.157    rillig     GNodeListNode *gln;
   1042  1.170    rillig     GNode *t;			/* Target GNode */
   1043  1.170    rillig     GNode *s;			/* Source GNode */
   1044  1.170    rillig     size_t prefLen;		/* The length of the defined prefix */
   1045  1.170    rillig     Suff *suff;			/* Suffix on matching beastie */
   1046  1.170    rillig     Src *ret;			/* Return value */
   1047  1.170    rillig     char *cp;
   1048   1.73     joerg 
   1049   1.73     joerg     t = targ->node;
   1050  1.125    rillig     Lst_Open(t->children);
   1051   1.73     joerg     prefLen = strlen(targ->pref);
   1052   1.73     joerg 
   1053   1.73     joerg     for (;;) {
   1054  1.157    rillig 	gln = Lst_Next(t->children);
   1055  1.157    rillig 	if (gln == NULL) {
   1056  1.125    rillig 	    Lst_Close(t->children);
   1057   1.73     joerg 	    return NULL;
   1058   1.73     joerg 	}
   1059  1.195    rillig 	s = gln->datum;
   1060   1.73     joerg 
   1061  1.125    rillig 	if (s->type & OP_OPTIONAL && Lst_IsEmpty(t->commands)) {
   1062   1.73     joerg 	    /*
   1063   1.73     joerg 	     * We haven't looked to see if .OPTIONAL files exist yet, so
   1064   1.73     joerg 	     * don't use one as the implicit source.
   1065   1.73     joerg 	     * This allows us to use .OPTIONAL in .depend files so make won't
   1066   1.73     joerg 	     * complain "don't know how to make xxx.h' when a dependent file
   1067   1.73     joerg 	     * has been moved/deleted.
   1068   1.73     joerg 	     */
   1069   1.73     joerg 	    continue;
   1070   1.73     joerg 	}
   1071   1.73     joerg 
   1072   1.73     joerg 	cp = strrchr(s->name, '/');
   1073   1.73     joerg 	if (cp == NULL) {
   1074   1.73     joerg 	    cp = s->name;
   1075   1.73     joerg 	} else {
   1076   1.73     joerg 	    cp++;
   1077   1.73     joerg 	}
   1078   1.73     joerg 	if (strncmp(cp, targ->pref, prefLen) != 0)
   1079   1.73     joerg 	    continue;
   1080   1.73     joerg 	/*
   1081   1.73     joerg 	 * The node matches the prefix ok, see if it has a known
   1082   1.73     joerg 	 * suffix.
   1083   1.73     joerg 	 */
   1084  1.166    rillig 	suff = FindSuffByName(cp + prefLen);
   1085  1.166    rillig 	if (suff == NULL)
   1086   1.73     joerg 	    continue;
   1087  1.166    rillig 
   1088   1.73     joerg 	/*
   1089   1.73     joerg 	 * It even has a known suffix, see if there's a transformation
   1090   1.73     joerg 	 * defined between the node's suffix and the target's suffix.
   1091   1.73     joerg 	 *
   1092   1.73     joerg 	 * XXX: Handle multi-stage transformations here, too.
   1093   1.73     joerg 	 */
   1094   1.73     joerg 
   1095  1.107    rillig 	/* XXX: Can targ->suff be NULL here? */
   1096  1.107    rillig 	if (targ->suff != NULL &&
   1097  1.137    rillig 	    Lst_FindDatum(suff->parents, targ->suff) != NULL)
   1098   1.73     joerg 	    break;
   1099   1.73     joerg     }
   1100    1.1       cgd 
   1101   1.43       dsl     /*
   1102   1.73     joerg      * Hot Damn! Create a new Src structure to describe
   1103   1.73     joerg      * this transformation (making sure to duplicate the
   1104   1.73     joerg      * source node's name so Suff_FindDeps can free it
   1105   1.73     joerg      * again (ick)), and return the new structure.
   1106   1.73     joerg      */
   1107  1.209    rillig     ret = SrcNew(bmake_strdup(s->name), targ->pref, suff, targ, s);
   1108   1.73     joerg     suff->refCount++;
   1109  1.173    rillig     targ->children++;
   1110   1.73     joerg #ifdef DEBUG_SRC
   1111  1.172    rillig     debug_printf("3 add %p %p\n", targ, ret);
   1112  1.211    rillig     Lst_Append(targ->childrenList, ret);
   1113   1.73     joerg #endif
   1114  1.125    rillig     Lst_Append(slst, ret);
   1115  1.140    rillig     SUFF_DEBUG1("\tusing existing source %s\n", s->name);
   1116  1.141    rillig     Lst_Close(t->children);
   1117   1.88    rillig     return ret;
   1118    1.1       cgd }
   1119    1.1       cgd 
   1120  1.134    rillig /* Expand the names of any children of a given node that contain variable
   1121  1.153    rillig  * expressions or file wildcards into actual targets.
   1122  1.134    rillig  *
   1123  1.134    rillig  * The expanded node is removed from the parent's list of children, and the
   1124  1.134    rillig  * parent's unmade counter is decremented, but other nodes may be added.
   1125    1.1       cgd  *
   1126   1.39       wiz  * Input:
   1127   1.73     joerg  *	cln		Child to examine
   1128   1.73     joerg  *	pgn		Parent node being processed
   1129    1.1       cgd  */
   1130   1.56       dsl static void
   1131  1.157    rillig SuffExpandChildren(GNodeListNode *cln, GNode *pgn)
   1132    1.1       cgd {
   1133  1.195    rillig     GNode *cgn = cln->datum;
   1134  1.170    rillig     GNode *gn;			/* New source 8) */
   1135  1.170    rillig     char *cp;			/* Expanded value */
   1136    1.1       cgd 
   1137  1.125    rillig     if (!Lst_IsEmpty(cgn->order_pred) || !Lst_IsEmpty(cgn->order_succ))
   1138   1.61       dsl 	/* It is all too hard to process the result of .ORDER */
   1139   1.61       dsl 	return;
   1140   1.61       dsl 
   1141   1.61       dsl     if (cgn->type & OP_WAIT)
   1142   1.61       dsl 	/* Ignore these (& OP_PHONY ?) */
   1143   1.61       dsl 	return;
   1144   1.61       dsl 
   1145    1.1       cgd     /*
   1146    1.1       cgd      * First do variable expansion -- this takes precedence over
   1147    1.1       cgd      * wildcard expansion. If the result contains wildcards, they'll be gotten
   1148    1.1       cgd      * to later since the resulting words are tacked on to the end of
   1149    1.1       cgd      * the children list.
   1150    1.1       cgd      */
   1151   1.56       dsl     if (strchr(cgn->name, '$') == NULL) {
   1152   1.56       dsl 	SuffExpandWildcards(cln, pgn);
   1153   1.56       dsl 	return;
   1154   1.56       dsl     }
   1155   1.56       dsl 
   1156  1.140    rillig     SUFF_DEBUG1("Expanding \"%s\"...", cgn->name);
   1157  1.158    rillig     (void)Var_Subst(cgn->name, pgn, VARE_UNDEFERR|VARE_WANTRES, &cp);
   1158  1.158    rillig     /* TODO: handle errors */
   1159    1.1       cgd 
   1160  1.135    rillig     {
   1161  1.180    rillig 	GNodeList *members = Lst_New();
   1162   1.13  christos 
   1163   1.56       dsl 	if (cgn->type & OP_ARCHV) {
   1164   1.56       dsl 	    /*
   1165   1.56       dsl 	     * Node was an archive(member) target, so we want to call
   1166   1.56       dsl 	     * on the Arch module to find the nodes for us, expanding
   1167   1.56       dsl 	     * variables in the parent's context.
   1168   1.56       dsl 	     */
   1169   1.56       dsl 	    char	*sacrifice = cp;
   1170    1.1       cgd 
   1171   1.56       dsl 	    (void)Arch_ParseArchive(&sacrifice, members, pgn);
   1172   1.56       dsl 	} else {
   1173   1.56       dsl 	    /*
   1174   1.56       dsl 	     * Break the result into a vector of strings whose nodes
   1175   1.56       dsl 	     * we can find, then add those nodes to the members list.
   1176   1.56       dsl 	     * Unfortunately, we can't use brk_string b/c it
   1177   1.56       dsl 	     * doesn't understand about variable specifications with
   1178   1.56       dsl 	     * spaces in them...
   1179   1.56       dsl 	     */
   1180   1.56       dsl 	    char	    *start;
   1181   1.73     joerg 	    char	    *initcp = cp;   /* For freeing... */
   1182    1.1       cgd 
   1183   1.56       dsl 	    for (start = cp; *start == ' ' || *start == '\t'; start++)
   1184   1.56       dsl 		continue;
   1185  1.145    rillig 	    cp = start;
   1186  1.145    rillig 	    while (*cp != '\0') {
   1187   1.56       dsl 		if (*cp == ' ' || *cp == '\t') {
   1188   1.56       dsl 		    /*
   1189   1.56       dsl 		     * White-space -- terminate element, find the node,
   1190   1.56       dsl 		     * add it, skip any further spaces.
   1191   1.56       dsl 		     */
   1192   1.56       dsl 		    *cp++ = '\0';
   1193  1.168    rillig 		    gn = Targ_GetNode(start);
   1194  1.125    rillig 		    Lst_Append(members, gn);
   1195   1.56       dsl 		    while (*cp == ' ' || *cp == '\t') {
   1196    1.1       cgd 			cp++;
   1197    1.1       cgd 		    }
   1198  1.145    rillig 		    start = cp;		/* Continue at the next non-space. */
   1199   1.56       dsl 		} else if (*cp == '$') {
   1200   1.56       dsl 		    /*
   1201   1.56       dsl 		     * Start of a variable spec -- contact variable module
   1202   1.56       dsl 		     * to find the end so we can skip over it.
   1203   1.56       dsl 		     */
   1204  1.144    rillig 		    const char *nested_p = cp;
   1205   1.90    rillig 		    const char	*junk;
   1206   1.56       dsl 		    void	*freeIt;
   1207   1.56       dsl 
   1208  1.145    rillig 		    /* XXX: Why VARE_WANTRES when the result is not used? */
   1209  1.156    rillig 		    (void)Var_Parse(&nested_p, pgn,
   1210  1.156    rillig 				    VARE_UNDEFERR|VARE_WANTRES,
   1211  1.156    rillig 				    &junk, &freeIt);
   1212  1.156    rillig 		    /* TODO: handle errors */
   1213  1.145    rillig 		    if (junk == var_Error) {
   1214  1.145    rillig 			Parse_Error(PARSE_FATAL,
   1215  1.145    rillig 				    "Malformed variable expression at \"%s\"",
   1216  1.145    rillig 				    cp);
   1217  1.148    rillig 			cp++;
   1218  1.145    rillig 		    } else {
   1219  1.144    rillig 			cp += nested_p - cp;
   1220   1.56       dsl 		    }
   1221    1.1       cgd 
   1222   1.77  christos 		    free(freeIt);
   1223   1.82  dholland 		} else if (*cp == '\\' && cp[1] != '\0') {
   1224    1.1       cgd 		    /*
   1225   1.56       dsl 		     * Escaped something -- skip over it
   1226    1.1       cgd 		     */
   1227  1.145    rillig 		    /* XXX: In other places, escaping at this syntactical
   1228  1.145    rillig 		     * position is done by a '$', not a '\'.  The '\' is only
   1229  1.145    rillig 		     * used in variable modifiers. */
   1230  1.145    rillig 		    cp += 2;
   1231  1.145    rillig 		} else {
   1232   1.56       dsl 		    cp++;
   1233    1.1       cgd 		}
   1234   1.56       dsl 	    }
   1235   1.56       dsl 
   1236   1.56       dsl 	    if (cp != start) {
   1237    1.1       cgd 		/*
   1238   1.56       dsl 		 * Stuff left over -- add it to the list too
   1239    1.1       cgd 		 */
   1240  1.168    rillig 		gn = Targ_GetNode(start);
   1241  1.125    rillig 		Lst_Append(members, gn);
   1242    1.1       cgd 	    }
   1243   1.73     joerg 	    /*
   1244   1.73     joerg 	     * Point cp back at the beginning again so the variable value
   1245   1.73     joerg 	     * can be freed.
   1246   1.73     joerg 	     */
   1247   1.73     joerg 	    cp = initcp;
   1248   1.56       dsl 	}
   1249    1.1       cgd 
   1250    1.1       cgd 	/*
   1251   1.56       dsl 	 * Add all elements of the members list to the parent node.
   1252    1.1       cgd 	 */
   1253  1.125    rillig 	while(!Lst_IsEmpty(members)) {
   1254  1.125    rillig 	    gn = Lst_Dequeue(members);
   1255   1.56       dsl 
   1256  1.140    rillig 	    SUFF_DEBUG1("%s...", gn->name);
   1257   1.56       dsl 	    /* Add gn to the parents child list before the original child */
   1258  1.125    rillig 	    Lst_InsertBefore(pgn->children, cln, gn);
   1259  1.125    rillig 	    Lst_Append(gn->parents, pgn);
   1260   1.56       dsl 	    pgn->unmade++;
   1261   1.56       dsl 	    /* Expand wildcards on new node */
   1262  1.169    rillig 	    SuffExpandWildcards(cln->prev, pgn);
   1263    1.1       cgd 	}
   1264  1.125    rillig 	Lst_Free(members);
   1265    1.1       cgd 
   1266   1.73     joerg 	/*
   1267   1.73     joerg 	 * Free the result
   1268   1.73     joerg 	 */
   1269   1.73     joerg 	free(cp);
   1270   1.73     joerg     }
   1271  1.135    rillig 
   1272  1.140    rillig     SUFF_DEBUG0("\n");
   1273    1.1       cgd 
   1274   1.56       dsl     /*
   1275   1.56       dsl      * Now the source is expanded, remove it from the list of children to
   1276   1.56       dsl      * keep it from being processed.
   1277   1.56       dsl      */
   1278   1.56       dsl     pgn->unmade--;
   1279  1.125    rillig     Lst_Remove(pgn->children, cln);
   1280  1.137    rillig     Lst_Remove(cgn->parents, Lst_FindDatum(cgn->parents, pgn));
   1281   1.56       dsl }
   1282   1.56       dsl 
   1283   1.56       dsl static void
   1284  1.157    rillig SuffExpandWildcards(GNodeListNode *cln, GNode *pgn)
   1285   1.56       dsl {
   1286  1.195    rillig     GNode *cgn = cln->datum;
   1287  1.157    rillig     StringList *explist;
   1288    1.1       cgd 
   1289   1.56       dsl     if (!Dir_HasWildcards(cgn->name))
   1290   1.56       dsl 	return;
   1291    1.1       cgd 
   1292   1.56       dsl     /*
   1293   1.56       dsl      * Expand the word along the chosen path
   1294   1.56       dsl      */
   1295  1.180    rillig     explist = Lst_New();
   1296   1.56       dsl     Dir_Expand(cgn->name, Suff_FindPath(cgn), explist);
   1297    1.1       cgd 
   1298  1.125    rillig     while (!Lst_IsEmpty(explist)) {
   1299  1.157    rillig 	GNode	*gn;
   1300    1.1       cgd 	/*
   1301   1.56       dsl 	 * Fetch next expansion off the list and find its GNode
   1302    1.1       cgd 	 */
   1303  1.157    rillig 	char *cp = Lst_Dequeue(explist);
   1304   1.13  christos 
   1305  1.140    rillig 	SUFF_DEBUG1("%s...", cp);
   1306  1.168    rillig 	gn = Targ_GetNode(cp);
   1307   1.56       dsl 
   1308   1.56       dsl 	/* Add gn to the parents child list before the original child */
   1309  1.125    rillig 	Lst_InsertBefore(pgn->children, cln, gn);
   1310  1.125    rillig 	Lst_Append(gn->parents, pgn);
   1311   1.56       dsl 	pgn->unmade++;
   1312    1.1       cgd     }
   1313    1.1       cgd 
   1314  1.125    rillig     Lst_Free(explist);
   1315   1.56       dsl 
   1316  1.140    rillig     SUFF_DEBUG0("\n");
   1317   1.73     joerg 
   1318   1.56       dsl     /*
   1319   1.56       dsl      * Now the source is expanded, remove it from the list of children to
   1320   1.56       dsl      * keep it from being processed.
   1321   1.56       dsl      */
   1322   1.56       dsl     pgn->unmade--;
   1323  1.125    rillig     Lst_Remove(pgn->children, cln);
   1324  1.137    rillig     Lst_Remove(cgn->parents, Lst_FindDatum(cgn->parents, pgn));
   1325    1.1       cgd }
   1326    1.1       cgd 
   1327  1.134    rillig /* Find a path along which to expand the node.
   1328   1.47  christos  *
   1329  1.134    rillig  * If the word has a known suffix, use that path.
   1330  1.134    rillig  * If it has no known suffix, use the default system search path.
   1331   1.47  christos  *
   1332   1.47  christos  * Input:
   1333   1.47  christos  *	gn		Node being examined
   1334   1.47  christos  *
   1335   1.47  christos  * Results:
   1336   1.47  christos  *	The appropriate path to search for the GNode.
   1337   1.46  christos  */
   1338  1.157    rillig SearchPath *
   1339   1.46  christos Suff_FindPath(GNode* gn)
   1340   1.46  christos {
   1341   1.46  christos     Suff *suff = gn->suffix;
   1342   1.46  christos 
   1343   1.46  christos     if (suff == NULL) {
   1344  1.207    rillig         char *name = gn->name;
   1345  1.207    rillig 	size_t nameLen = strlen(gn->name);
   1346  1.157    rillig 	SuffListNode *ln;
   1347  1.207    rillig 	for (ln = sufflist->first; ln != NULL; ln = ln->next)
   1348  1.207    rillig 	    if (SuffSuffIsSuffix(ln->datum, nameLen, name + nameLen))
   1349  1.207    rillig 		break;
   1350   1.46  christos 
   1351  1.140    rillig 	SUFF_DEBUG1("Wildcard expanding \"%s\"...", gn->name);
   1352   1.65       dsl 	if (ln != NULL)
   1353  1.195    rillig 	    suff = ln->datum;
   1354   1.46  christos 	/* XXX: Here we can save the suffix so we don't have to do this again */
   1355   1.46  christos     }
   1356   1.46  christos 
   1357   1.73     joerg     if (suff != NULL) {
   1358  1.140    rillig 	SUFF_DEBUG1("suffix is \"%s\"...", suff->name);
   1359   1.46  christos 	return suff->searchPath;
   1360   1.73     joerg     } else {
   1361   1.73     joerg 	/*
   1362   1.73     joerg 	 * Use default search path
   1363   1.73     joerg 	 */
   1364   1.46  christos 	return dirSearchPath;
   1365   1.46  christos     }
   1366   1.46  christos }
   1367   1.46  christos 
   1368  1.134    rillig /* Apply a transformation rule, given the source and target nodes and
   1369  1.134    rillig  * suffixes.
   1370    1.1       cgd  *
   1371   1.39       wiz  * Input:
   1372   1.73     joerg  *	tGn		Target node
   1373   1.73     joerg  *	sGn		Source node
   1374   1.73     joerg  *	t		Target suffix
   1375   1.73     joerg  *	s		Source suffix
   1376   1.39       wiz  *
   1377    1.1       cgd  * Results:
   1378    1.1       cgd  *	TRUE if successful, FALSE if not.
   1379    1.1       cgd  *
   1380    1.1       cgd  * Side Effects:
   1381    1.1       cgd  *	The source and target are linked and the commands from the
   1382    1.1       cgd  *	transformation are added to the target node's commands list.
   1383    1.1       cgd  *	All attributes but OP_DEPMASK and OP_TRANSFORM are applied
   1384    1.1       cgd  *	to the target. The target also inherits all the sources for
   1385    1.1       cgd  *	the transformation rule.
   1386    1.1       cgd  */
   1387    1.1       cgd static Boolean
   1388   1.73     joerg SuffApplyTransform(GNode *tGn, GNode *sGn, Suff *t, Suff *s)
   1389    1.1       cgd {
   1390  1.157    rillig     GNodeListNode *ln, *nln;    /* General node */
   1391  1.170    rillig     char *tname;		/* Name of transformation rule */
   1392  1.170    rillig     GNode *gn;			/* Node for same */
   1393    1.1       cgd 
   1394   1.31   mycroft     /*
   1395   1.31   mycroft      * Form the proper links between the target and source.
   1396   1.31   mycroft      */
   1397  1.125    rillig     Lst_Append(tGn->children, sGn);
   1398  1.125    rillig     Lst_Append(sGn->parents, tGn);
   1399  1.173    rillig     tGn->unmade++;
   1400    1.1       cgd 
   1401    1.1       cgd     /*
   1402    1.1       cgd      * Locate the transformation rule itself
   1403    1.1       cgd      */
   1404   1.95    rillig     tname = str_concat2(s->name, t->name);
   1405  1.210    rillig     gn = FindTransformByName(tname);
   1406    1.1       cgd     free(tname);
   1407    1.1       cgd 
   1408  1.210    rillig     if (gn == NULL) {
   1409   1.73     joerg 	/*
   1410   1.73     joerg 	 * Not really such a transformation rule (can happen when we're
   1411   1.73     joerg 	 * called to link an OP_MEMBER and OP_ARCHV node), so return
   1412   1.73     joerg 	 * FALSE.
   1413   1.73     joerg 	 */
   1414   1.88    rillig 	return FALSE;
   1415   1.73     joerg     }
   1416   1.73     joerg 
   1417  1.140    rillig     SUFF_DEBUG3("\tapplying %s -> %s to \"%s\"\n", s->name, t->name, tGn->name);
   1418    1.1       cgd 
   1419   1.73     joerg     /*
   1420   1.73     joerg      * Record last child for expansion purposes
   1421   1.73     joerg      */
   1422  1.195    rillig     ln = tGn->children->last;
   1423   1.13  christos 
   1424    1.1       cgd     /*
   1425    1.1       cgd      * Pass the buck to Make_HandleUse to apply the rule
   1426    1.1       cgd      */
   1427    1.1       cgd     (void)Make_HandleUse(gn, tGn);
   1428    1.1       cgd 
   1429    1.1       cgd     /*
   1430   1.71  christos      * Deal with wildcards and variables in any acquired sources
   1431   1.71  christos      */
   1432  1.169    rillig     for (ln = ln != NULL ? ln->next : NULL; ln != NULL; ln = nln) {
   1433  1.169    rillig 	nln = ln->next;
   1434   1.73     joerg 	SuffExpandChildren(ln, tGn);
   1435   1.73     joerg     }
   1436    1.1       cgd 
   1437   1.73     joerg     /*
   1438   1.73     joerg      * Keep track of another parent to which this beast is transformed so
   1439   1.73     joerg      * the .IMPSRC variable can be set correctly for the parent.
   1440   1.73     joerg      */
   1441  1.139    rillig     Lst_Append(sGn->implicitParents, tGn);
   1442    1.1       cgd 
   1443   1.88    rillig     return TRUE;
   1444    1.1       cgd }
   1445    1.1       cgd 
   1446    1.1       cgd 
   1447  1.134    rillig /* Locate dependencies for an OP_ARCHV node.
   1448    1.1       cgd  *
   1449   1.39       wiz  * Input:
   1450   1.73     joerg  *	gn		Node for which to locate dependencies
   1451   1.39       wiz  *
   1452    1.1       cgd  * Side Effects:
   1453   1.73     joerg  *	Same as Suff_FindDeps
   1454    1.1       cgd  */
   1455    1.1       cgd static void
   1456  1.157    rillig SuffFindArchiveDeps(GNode *gn, SrcList *slst)
   1457    1.1       cgd {
   1458  1.157    rillig     char *eoarch;		/* End of archive portion */
   1459  1.157    rillig     char *eoname;		/* End of member portion */
   1460  1.157    rillig     GNode *mem;			/* Node for member */
   1461  1.157    rillig     SuffListNode *ln, *nln;	/* Next suffix node to check */
   1462  1.157    rillig     Suff *ms;			/* Suffix descriptor for member */
   1463  1.157    rillig     char *name;			/* Start of member's name */
   1464   1.71  christos 
   1465   1.73     joerg     /*
   1466   1.73     joerg      * The node is an archive(member) pair. so we must find a
   1467   1.73     joerg      * suffix for both of them.
   1468   1.73     joerg      */
   1469   1.73     joerg     eoarch = strchr(gn->name, '(');
   1470   1.73     joerg     eoname = strchr(eoarch, ')');
   1471   1.13  christos 
   1472   1.86  riastrad     /*
   1473   1.86  riastrad      * Caller guarantees the format `libname(member)', via
   1474   1.86  riastrad      * Arch_ParseArchive.
   1475   1.86  riastrad      */
   1476   1.86  riastrad     assert(eoarch != NULL);
   1477   1.86  riastrad     assert(eoname != NULL);
   1478   1.86  riastrad 
   1479   1.73     joerg     *eoname = '\0';	  /* Nuke parentheses during suffix search */
   1480   1.73     joerg     *eoarch = '\0';	  /* So a suffix can be found */
   1481    1.1       cgd 
   1482   1.73     joerg     name = eoarch + 1;
   1483    1.1       cgd 
   1484   1.73     joerg     /*
   1485   1.73     joerg      * To simplify things, call Suff_FindDeps recursively on the member now,
   1486   1.73     joerg      * so we can simply compare the member's .PREFIX and .TARGET variables
   1487   1.73     joerg      * to locate its suffix. This allows us to figure out the suffix to
   1488   1.73     joerg      * use for the archive without having to do a quadratic search over the
   1489   1.73     joerg      * suffix list, backtracking for each one...
   1490   1.73     joerg      */
   1491  1.168    rillig     mem = Targ_GetNode(name);
   1492   1.73     joerg     SuffFindDeps(mem, slst);
   1493   1.13  christos 
   1494    1.1       cgd     /*
   1495   1.73     joerg      * Create the link between the two nodes right off
   1496    1.1       cgd      */
   1497  1.125    rillig     Lst_Append(gn->children, mem);
   1498  1.125    rillig     Lst_Append(mem->parents, gn);
   1499  1.173    rillig     gn->unmade++;
   1500   1.13  christos 
   1501    1.1       cgd     /*
   1502   1.73     joerg      * Copy in the variables from the member node to this one.
   1503    1.1       cgd      */
   1504  1.113    rillig     {
   1505  1.113    rillig 	char *freeIt;
   1506  1.113    rillig 	Var_Set(PREFIX, Var_Value(PREFIX, mem, &freeIt), gn);
   1507  1.113    rillig 	bmake_free(freeIt);
   1508  1.113    rillig 	Var_Set(TARGET, Var_Value(TARGET, mem, &freeIt), gn);
   1509  1.113    rillig 	bmake_free(freeIt);
   1510   1.73     joerg     }
   1511    1.1       cgd 
   1512   1.73     joerg     ms = mem->suffix;
   1513   1.73     joerg     if (ms == NULL) {
   1514   1.73     joerg 	/*
   1515   1.73     joerg 	 * Didn't know what it was -- use .NULL suffix if not in make mode
   1516   1.73     joerg 	 */
   1517  1.140    rillig 	SUFF_DEBUG0("using null suffix\n");
   1518   1.73     joerg 	ms = suffNull;
   1519    1.1       cgd     }
   1520    1.1       cgd 
   1521   1.73     joerg 
   1522    1.1       cgd     /*
   1523   1.73     joerg      * Set the other two local variables required for this target.
   1524    1.1       cgd      */
   1525   1.87    rillig     Var_Set(MEMBER, name, gn);
   1526   1.87    rillig     Var_Set(ARCHIVE, gn->name, gn);
   1527   1.73     joerg 
   1528   1.79  matthias     /*
   1529   1.79  matthias      * Set $@ for compatibility with other makes
   1530   1.79  matthias      */
   1531   1.87    rillig     Var_Set(TARGET, gn->name, gn);
   1532   1.80  matthias 
   1533   1.80  matthias     /*
   1534   1.80  matthias      * Now we've got the important local variables set, expand any sources
   1535   1.80  matthias      * that still contain variables or wildcards in their names.
   1536   1.80  matthias      */
   1537  1.195    rillig     for (ln = gn->children->first; ln != NULL; ln = nln) {
   1538  1.169    rillig 	nln = ln->next;
   1539   1.80  matthias 	SuffExpandChildren(ln, gn);
   1540   1.80  matthias     }
   1541   1.80  matthias 
   1542   1.73     joerg     if (ms != NULL) {
   1543   1.73     joerg 	/*
   1544   1.73     joerg 	 * Member has a known suffix, so look for a transformation rule from
   1545   1.73     joerg 	 * it to a possible suffix of the archive. Rather than searching
   1546   1.73     joerg 	 * through the entire list, we just look at suffixes to which the
   1547   1.73     joerg 	 * member's suffix may be transformed...
   1548   1.73     joerg 	 */
   1549  1.207    rillig 	size_t nameLen = (size_t)(eoarch - gn->name);
   1550   1.73     joerg 
   1551  1.207    rillig 	/* Use first matching suffix... */
   1552  1.207    rillig 	for (ln = ms->parents->first; ln != NULL; ln = ln->next)
   1553  1.207    rillig 	    if (SuffSuffIsSuffix(ln->datum, nameLen, eoarch))
   1554  1.207    rillig 		break;
   1555   1.73     joerg 
   1556   1.73     joerg 	if (ln != NULL) {
   1557   1.73     joerg 	    /*
   1558   1.73     joerg 	     * Got one -- apply it
   1559   1.73     joerg 	     */
   1560  1.195    rillig 	    Suff *suff = ln->datum;
   1561  1.140    rillig 	    if (!SuffApplyTransform(gn, mem, suff, ms)) {
   1562  1.140    rillig 		SUFF_DEBUG2("\tNo transformation from %s -> %s\n",
   1563  1.140    rillig 			    ms->name, suff->name);
   1564    1.1       cgd 	    }
   1565    1.1       cgd 	}
   1566    1.1       cgd     }
   1567    1.1       cgd 
   1568   1.73     joerg     /*
   1569   1.73     joerg      * Replace the opening and closing parens now we've no need of the separate
   1570   1.73     joerg      * pieces.
   1571   1.73     joerg      */
   1572   1.73     joerg     *eoarch = '('; *eoname = ')';
   1573   1.71  christos 
   1574    1.1       cgd     /*
   1575   1.73     joerg      * Pretend gn appeared to the left of a dependency operator so
   1576   1.73     joerg      * the user needn't provide a transformation from the member to the
   1577   1.73     joerg      * archive.
   1578    1.1       cgd      */
   1579   1.73     joerg     if (OP_NOP(gn->type)) {
   1580   1.73     joerg 	gn->type |= OP_DEPENDS;
   1581   1.73     joerg     }
   1582   1.71  christos 
   1583   1.73     joerg     /*
   1584   1.73     joerg      * Flag the member as such so we remember to look in the archive for
   1585   1.81  matthias      * its modification time. The OP_JOIN | OP_MADE is needed because this
   1586   1.81  matthias      * target should never get made.
   1587   1.73     joerg      */
   1588   1.81  matthias     mem->type |= OP_MEMBER | OP_JOIN | OP_MADE;
   1589    1.1       cgd }
   1590    1.1       cgd 
   1591  1.201    rillig static void
   1592  1.208    rillig SuffFindNormalDepsKnown(char *name, size_t nameLen, GNode *gn,
   1593  1.208    rillig 			SrcList *srcs, SrcList *targs)
   1594  1.201    rillig {
   1595  1.203    rillig     SuffListNode *ln;
   1596  1.203    rillig     Src *targ;
   1597  1.209    rillig     char *pref;
   1598  1.201    rillig 
   1599  1.203    rillig     for (ln = sufflist->first; ln != NULL; ln = ln->next) {
   1600  1.209    rillig 	Suff *suff = ln->datum;
   1601  1.209    rillig 	if (!SuffSuffIsSuffix(suff, nameLen, name + nameLen))
   1602  1.203    rillig 	    continue;
   1603  1.201    rillig 
   1604  1.209    rillig 	pref = bmake_strldup(name, (size_t)(nameLen - suff->nameLen));
   1605  1.209    rillig 	targ = SrcNew(bmake_strdup(gn->name), pref, suff, NULL, gn);
   1606  1.209    rillig 	suff->refCount++;
   1607  1.201    rillig 
   1608  1.203    rillig 	/*
   1609  1.203    rillig 	 * Add nodes from which the target can be made
   1610  1.203    rillig 	 */
   1611  1.203    rillig 	SuffAddLevel(srcs, targ);
   1612  1.201    rillig 
   1613  1.203    rillig 	/*
   1614  1.203    rillig 	 * Record the target so we can nuke it
   1615  1.203    rillig 	 */
   1616  1.203    rillig 	Lst_Append(targs, targ);
   1617  1.201    rillig     }
   1618  1.201    rillig }
   1619  1.201    rillig 
   1620  1.202    rillig static void
   1621  1.202    rillig SuffFindNormalDepsUnknown(GNode *gn, const char *sopref,
   1622  1.202    rillig 			  SrcList *srcs, SrcList *targs)
   1623  1.202    rillig {
   1624  1.202    rillig     Src *targ;
   1625  1.202    rillig 
   1626  1.204    rillig     if (!Lst_IsEmpty(targs) || suffNull == NULL)
   1627  1.204    rillig         return;
   1628  1.202    rillig 
   1629  1.204    rillig     SUFF_DEBUG1("\tNo known suffix on %s. Using .NULL suffix\n", gn->name);
   1630  1.204    rillig 
   1631  1.209    rillig     targ = SrcNew(bmake_strdup(gn->name), bmake_strdup(sopref),
   1632  1.209    rillig 		  suffNull, NULL, gn);
   1633  1.204    rillig     targ->suff->refCount++;
   1634  1.202    rillig 
   1635  1.204    rillig     /*
   1636  1.204    rillig      * Only use the default suffix rules if we don't have commands
   1637  1.204    rillig      * defined for this gnode; traditional make programs used to
   1638  1.204    rillig      * not define suffix rules if the gnode had children but we
   1639  1.204    rillig      * don't do this anymore.
   1640  1.204    rillig      */
   1641  1.204    rillig     if (Lst_IsEmpty(gn->commands))
   1642  1.204    rillig 	SuffAddLevel(srcs, targ);
   1643  1.204    rillig     else {
   1644  1.204    rillig 	SUFF_DEBUG0("not ");
   1645  1.204    rillig     }
   1646  1.202    rillig 
   1647  1.204    rillig     SUFF_DEBUG0("adding suffix rules\n");
   1648  1.202    rillig 
   1649  1.204    rillig     Lst_Append(targs, targ);
   1650  1.202    rillig }
   1651  1.202    rillig 
   1652  1.205    rillig /*
   1653  1.205    rillig  * Deal with finding the thing on the default search path. We
   1654  1.205    rillig  * always do that, not only if the node is only a source (not
   1655  1.205    rillig  * on the lhs of a dependency operator or [XXX] it has neither
   1656  1.205    rillig  * children or commands) as the old pmake did.
   1657  1.205    rillig  */
   1658  1.205    rillig static void
   1659  1.205    rillig SuffFindNormalDepsPath(GNode *gn, Src *targ)
   1660  1.205    rillig {
   1661  1.206    rillig     if (gn->type & (OP_PHONY | OP_NOPATH))
   1662  1.206    rillig         return;
   1663  1.206    rillig 
   1664  1.206    rillig     free(gn->path);
   1665  1.206    rillig     gn->path = Dir_FindFile(gn->name,
   1666  1.206    rillig 			    (targ == NULL ? dirSearchPath :
   1667  1.206    rillig 			     targ->suff->searchPath));
   1668  1.206    rillig     if (gn->path == NULL)
   1669  1.206    rillig         return;
   1670  1.205    rillig 
   1671  1.206    rillig     Var_Set(TARGET, gn->path, gn);
   1672  1.206    rillig 
   1673  1.206    rillig     if (targ != NULL) {
   1674  1.206    rillig 	/*
   1675  1.206    rillig 	 * Suffix known for the thing -- trim the suffix off
   1676  1.206    rillig 	 * the path to form the proper .PREFIX variable.
   1677  1.206    rillig 	 */
   1678  1.206    rillig 	size_t savep = strlen(gn->path) - targ->suff->nameLen;
   1679  1.206    rillig 	char savec;
   1680  1.206    rillig 	char *ptr;
   1681  1.206    rillig 
   1682  1.206    rillig 	if (gn->suffix)
   1683  1.206    rillig 	    gn->suffix->refCount--;
   1684  1.206    rillig 	gn->suffix = targ->suff;
   1685  1.206    rillig 	gn->suffix->refCount++;
   1686  1.206    rillig 
   1687  1.206    rillig 	savec = gn->path[savep];
   1688  1.206    rillig 	gn->path[savep] = '\0';
   1689  1.205    rillig 
   1690  1.206    rillig 	if ((ptr = strrchr(gn->path, '/')) != NULL)
   1691  1.206    rillig 	    ptr++;
   1692  1.206    rillig 	else
   1693  1.206    rillig 	    ptr = gn->path;
   1694  1.205    rillig 
   1695  1.206    rillig 	Var_Set(PREFIX, ptr, gn);
   1696  1.205    rillig 
   1697  1.206    rillig 	gn->path[savep] = savec;
   1698  1.206    rillig     } else {
   1699  1.206    rillig 	char *ptr;
   1700  1.205    rillig 
   1701  1.206    rillig 	/* The .PREFIX gets the full path if the target has no known suffix. */
   1702  1.206    rillig 	if (gn->suffix)
   1703  1.206    rillig 	    gn->suffix->refCount--;
   1704  1.206    rillig 	gn->suffix = NULL;
   1705  1.205    rillig 
   1706  1.206    rillig 	if ((ptr = strrchr(gn->path, '/')) != NULL)
   1707  1.206    rillig 	    ptr++;
   1708  1.206    rillig 	else
   1709  1.206    rillig 	    ptr = gn->path;
   1710  1.205    rillig 
   1711  1.206    rillig 	Var_Set(PREFIX, ptr, gn);
   1712  1.205    rillig     }
   1713  1.205    rillig }
   1714  1.205    rillig 
   1715  1.134    rillig /* Locate implicit dependencies for regular targets.
   1716    1.1       cgd  *
   1717   1.39       wiz  * Input:
   1718   1.73     joerg  *	gn		Node for which to find sources
   1719   1.39       wiz  *
   1720    1.1       cgd  * Side Effects:
   1721  1.134    rillig  *	Same as Suff_FindDeps
   1722    1.1       cgd  */
   1723    1.1       cgd static void
   1724  1.157    rillig SuffFindNormalDeps(GNode *gn, SrcList *slst)
   1725    1.1       cgd {
   1726  1.170    rillig     SrcList *srcs;		/* List of sources at which to look */
   1727  1.170    rillig     SrcList *targs;		/* List of targets to which things can be
   1728  1.170    rillig 				 * transformed. They all have the same file,
   1729  1.170    rillig 				 * but different suff and pref fields */
   1730  1.170    rillig     Src *bottom;		/* Start of found transformation path */
   1731  1.170    rillig     Src *src;			/* General Src pointer */
   1732  1.170    rillig     char *pref;			/* Prefix to use */
   1733  1.170    rillig     Src *targ;			/* General Src target pointer */
   1734   1.73     joerg 
   1735  1.208    rillig     char *name = gn->name;
   1736  1.208    rillig     size_t nameLen = strlen(name);
   1737   1.73     joerg 
   1738   1.73     joerg     /*
   1739   1.73     joerg      * Begin at the beginning...
   1740   1.73     joerg      */
   1741  1.180    rillig     srcs = Lst_New();
   1742  1.180    rillig     targs = Lst_New();
   1743   1.73     joerg 
   1744   1.73     joerg     /*
   1745   1.73     joerg      * We're caught in a catch-22 here. On the one hand, we want to use any
   1746   1.73     joerg      * transformation implied by the target's sources, but we can't examine
   1747   1.73     joerg      * the sources until we've expanded any variables/wildcards they may hold,
   1748   1.73     joerg      * and we can't do that until we've set up the target's local variables
   1749   1.73     joerg      * and we can't do that until we know what the proper suffix for the
   1750   1.73     joerg      * target is (in case there are two suffixes one of which is a suffix of
   1751   1.73     joerg      * the other) and we can't know that until we've found its implied
   1752   1.73     joerg      * source, which we may not want to use if there's an existing source
   1753   1.73     joerg      * that implies a different transformation.
   1754   1.73     joerg      *
   1755   1.73     joerg      * In an attempt to get around this, which may not work all the time,
   1756   1.73     joerg      * but should work most of the time, we look for implied sources first,
   1757   1.73     joerg      * checking transformations to all possible suffixes of the target,
   1758   1.73     joerg      * use what we find to set the target's local variables, expand the
   1759   1.73     joerg      * children, then look for any overriding transformations they imply.
   1760   1.73     joerg      * Should we find one, we discard the one we found before.
   1761   1.73     joerg      */
   1762   1.73     joerg     bottom = NULL;
   1763   1.73     joerg     targ = NULL;
   1764   1.71  christos 
   1765   1.73     joerg     if (!(gn->type & OP_PHONY)) {
   1766   1.73     joerg 
   1767  1.208    rillig 	SuffFindNormalDepsKnown(name, nameLen, gn, srcs, targs);
   1768   1.73     joerg 
   1769  1.202    rillig 	/* Handle target of unknown suffix... */
   1770  1.208    rillig 	SuffFindNormalDepsUnknown(gn, name, srcs, targs);
   1771   1.73     joerg 
   1772   1.73     joerg 	/*
   1773   1.73     joerg 	 * Using the list of possible sources built up from the target
   1774   1.73     joerg 	 * suffix(es), try and find an existing file/target that matches.
   1775   1.73     joerg 	 */
   1776   1.73     joerg 	bottom = SuffFindThem(srcs, slst);
   1777   1.73     joerg 
   1778   1.73     joerg 	if (bottom == NULL) {
   1779   1.73     joerg 	    /*
   1780   1.73     joerg 	     * No known transformations -- use the first suffix found
   1781   1.73     joerg 	     * for setting the local variables.
   1782   1.73     joerg 	     */
   1783  1.125    rillig 	    if (!Lst_IsEmpty(targs)) {
   1784  1.195    rillig 		targ = targs->first->datum;
   1785   1.73     joerg 	    } else {
   1786   1.73     joerg 		targ = NULL;
   1787   1.73     joerg 	    }
   1788   1.73     joerg 	} else {
   1789   1.73     joerg 	    /*
   1790   1.73     joerg 	     * Work up the transformation path to find the suffix of the
   1791   1.73     joerg 	     * target to which the transformation was made.
   1792   1.73     joerg 	     */
   1793   1.73     joerg 	    for (targ = bottom; targ->parent != NULL; targ = targ->parent)
   1794   1.73     joerg 		continue;
   1795   1.73     joerg 	}
   1796   1.73     joerg     }
   1797   1.73     joerg 
   1798   1.87    rillig     Var_Set(TARGET, gn->path ? gn->path : gn->name, gn);
   1799   1.73     joerg 
   1800   1.73     joerg     pref = (targ != NULL) ? targ->pref : gn->name;
   1801   1.87    rillig     Var_Set(PREFIX, pref, gn);
   1802    1.1       cgd 
   1803    1.1       cgd     /*
   1804   1.73     joerg      * Now we've got the important local variables set, expand any sources
   1805   1.73     joerg      * that still contain variables or wildcards in their names.
   1806    1.1       cgd      */
   1807  1.201    rillig     {
   1808  1.201    rillig 	SuffListNode *ln, *nln;
   1809  1.201    rillig 	for (ln = gn->children->first; ln != NULL; ln = nln) {
   1810  1.201    rillig 	    nln = ln->next;
   1811  1.201    rillig 	    SuffExpandChildren(ln, gn);
   1812  1.201    rillig 	}
   1813   1.73     joerg     }
   1814   1.73     joerg 
   1815   1.73     joerg     if (targ == NULL) {
   1816  1.140    rillig 	SUFF_DEBUG1("\tNo valid suffix on %s\n", gn->name);
   1817   1.73     joerg 
   1818   1.73     joerg sfnd_abort:
   1819  1.205    rillig 	SuffFindNormalDepsPath(gn, targ);
   1820   1.73     joerg 	goto sfnd_return;
   1821    1.1       cgd     }
   1822    1.1       cgd 
   1823    1.1       cgd     /*
   1824   1.73     joerg      * If the suffix indicates that the target is a library, mark that in
   1825   1.73     joerg      * the node's type field.
   1826    1.1       cgd      */
   1827   1.73     joerg     if (targ->suff->flags & SUFF_LIBRARY) {
   1828   1.73     joerg 	gn->type |= OP_LIB;
   1829   1.73     joerg     }
   1830    1.1       cgd 
   1831   1.73     joerg     /*
   1832   1.73     joerg      * Check for overriding transformation rule implied by sources
   1833   1.73     joerg      */
   1834  1.125    rillig     if (!Lst_IsEmpty(gn->children)) {
   1835   1.73     joerg 	src = SuffFindCmds(targ, slst);
   1836    1.1       cgd 
   1837   1.73     joerg 	if (src != NULL) {
   1838   1.73     joerg 	    /*
   1839   1.73     joerg 	     * Free up all the Src structures in the transformation path
   1840   1.73     joerg 	     * up to, but not including, the parent node.
   1841   1.73     joerg 	     */
   1842   1.73     joerg 	    while (bottom && bottom->parent != NULL) {
   1843  1.137    rillig 		if (Lst_FindDatum(slst, bottom) == NULL) {
   1844  1.125    rillig 		    Lst_Append(slst, bottom);
   1845   1.73     joerg 		}
   1846   1.73     joerg 		bottom = bottom->parent;
   1847    1.1       cgd 	    }
   1848   1.73     joerg 	    bottom = src;
   1849    1.1       cgd 	}
   1850   1.73     joerg     }
   1851    1.1       cgd 
   1852   1.73     joerg     if (bottom == NULL) {
   1853   1.73     joerg 	/*
   1854   1.73     joerg 	 * No idea from where it can come -- return now.
   1855   1.73     joerg 	 */
   1856   1.73     joerg 	goto sfnd_abort;
   1857   1.73     joerg     }
   1858   1.73     joerg 
   1859   1.73     joerg     /*
   1860   1.73     joerg      * We now have a list of Src structures headed by 'bottom' and linked via
   1861   1.73     joerg      * their 'parent' pointers. What we do next is create links between
   1862   1.73     joerg      * source and target nodes (which may or may not have been created)
   1863   1.73     joerg      * and set the necessary local variables in each target. The
   1864   1.73     joerg      * commands for each target are set from the commands of the
   1865   1.73     joerg      * transformation rule used to get from the src suffix to the targ
   1866   1.73     joerg      * suffix. Note that this causes the commands list of the original
   1867   1.73     joerg      * node, gn, to be replaced by the commands of the final
   1868   1.73     joerg      * transformation rule. Also, the unmade field of gn is incremented.
   1869   1.73     joerg      * Etc.
   1870   1.73     joerg      */
   1871   1.73     joerg     if (bottom->node == NULL) {
   1872  1.168    rillig 	bottom->node = Targ_GetNode(bottom->file);
   1873    1.1       cgd     }
   1874    1.1       cgd 
   1875   1.73     joerg     for (src = bottom; src->parent != NULL; src = src->parent) {
   1876   1.73     joerg 	targ = src->parent;
   1877   1.73     joerg 
   1878   1.73     joerg 	if (src->node->suffix)
   1879   1.73     joerg 	    src->node->suffix->refCount--;
   1880   1.73     joerg 	src->node->suffix = src->suff;
   1881   1.73     joerg 	src->node->suffix->refCount++;
   1882   1.73     joerg 
   1883   1.73     joerg 	if (targ->node == NULL) {
   1884  1.168    rillig 	    targ->node = Targ_GetNode(targ->file);
   1885   1.73     joerg 	}
   1886   1.73     joerg 
   1887   1.73     joerg 	SuffApplyTransform(targ->node, src->node,
   1888   1.73     joerg 			   targ->suff, src->suff);
   1889   1.73     joerg 
   1890   1.73     joerg 	if (targ->node != gn) {
   1891   1.73     joerg 	    /*
   1892   1.73     joerg 	     * Finish off the dependency-search process for any nodes
   1893   1.73     joerg 	     * between bottom and gn (no point in questing around the
   1894   1.73     joerg 	     * filesystem for their implicit source when it's already
   1895   1.73     joerg 	     * known). Note that the node can't have any sources that
   1896   1.73     joerg 	     * need expanding, since SuffFindThem will stop on an existing
   1897   1.73     joerg 	     * node, so all we need to do is set the standard and System V
   1898   1.73     joerg 	     * variables.
   1899   1.73     joerg 	     */
   1900   1.73     joerg 	    targ->node->type |= OP_DEPS_FOUND;
   1901   1.73     joerg 
   1902   1.87    rillig 	    Var_Set(PREFIX, targ->pref, targ->node);
   1903    1.1       cgd 
   1904   1.87    rillig 	    Var_Set(TARGET, targ->node->name, targ->node);
   1905    1.1       cgd 	}
   1906    1.1       cgd     }
   1907    1.1       cgd 
   1908   1.73     joerg     if (gn->suffix)
   1909   1.73     joerg 	gn->suffix->refCount--;
   1910   1.73     joerg     gn->suffix = src->suff;
   1911   1.73     joerg     gn->suffix->refCount++;
   1912   1.73     joerg 
   1913   1.73     joerg     /*
   1914   1.73     joerg      * Nuke the transformation path and the Src structures left over in the
   1915   1.73     joerg      * two lists.
   1916   1.73     joerg      */
   1917   1.73     joerg sfnd_return:
   1918   1.73     joerg     if (bottom)
   1919  1.137    rillig 	if (Lst_FindDatum(slst, bottom) == NULL)
   1920  1.125    rillig 	    Lst_Append(slst, bottom);
   1921    1.1       cgd 
   1922   1.73     joerg     while (SuffRemoveSrc(srcs) || SuffRemoveSrc(targs))
   1923   1.73     joerg 	continue;
   1924    1.1       cgd 
   1925  1.125    rillig     Lst_MoveAll(slst, srcs);
   1926  1.125    rillig     Lst_MoveAll(slst, targs);
   1927    1.1       cgd }
   1928   1.13  christos 
   1929   1.13  christos 
   1930  1.134    rillig /* Find implicit sources for the target described by the graph node.
   1931    1.1       cgd  *
   1932  1.134    rillig  * Nodes are added to the graph below the passed-in node. The nodes are
   1933  1.134    rillig  * marked to have their IMPSRC variable filled in. The PREFIX variable is set
   1934  1.134    rillig  * for the given node and all its implied children.
   1935  1.134    rillig  *
   1936  1.134    rillig  * The path found by this target is the shortest path in the transformation
   1937  1.134    rillig  * graph, which may pass through non-existent targets, to an existing target.
   1938  1.134    rillig  * The search continues on all paths from the root suffix until a file is
   1939  1.134    rillig  * found. I.e. if there's a path .o -> .c -> .l -> .l,v from the root and the
   1940  1.134    rillig  * .l,v file exists but the .c and .l files don't, the search will branch out
   1941  1.134    rillig  * in all directions from .o and again from all the nodes on the next level
   1942  1.134    rillig  * until the .l,v node is encountered.
   1943    1.1       cgd  */
   1944    1.1       cgd void
   1945   1.73     joerg Suff_FindDeps(GNode *gn)
   1946    1.6       jtc {
   1947   1.13  christos 
   1948   1.73     joerg     SuffFindDeps(gn, srclist);
   1949   1.73     joerg     while (SuffRemoveSrc(srclist))
   1950   1.73     joerg 	continue;
   1951   1.73     joerg }
   1952   1.73     joerg 
   1953   1.73     joerg static void
   1954  1.157    rillig SuffFindDeps(GNode *gn, SrcList *slst)
   1955   1.73     joerg {
   1956  1.127    rillig     if (gn->type & OP_DEPS_FOUND)
   1957    1.1       cgd 	return;
   1958  1.127    rillig     gn->type |= OP_DEPS_FOUND;
   1959  1.127    rillig 
   1960   1.69       sjg     /*
   1961   1.69       sjg      * Make sure we have these set, may get revised below.
   1962   1.69       sjg      */
   1963   1.87    rillig     Var_Set(TARGET, gn->path ? gn->path : gn->name, gn);
   1964   1.87    rillig     Var_Set(PREFIX, gn->name, gn);
   1965   1.70       sjg 
   1966  1.140    rillig     SUFF_DEBUG1("SuffFindDeps (%s)\n", gn->name);
   1967   1.13  christos 
   1968   1.73     joerg     if (gn->type & OP_ARCHV) {
   1969   1.73     joerg 	SuffFindArchiveDeps(gn, slst);
   1970   1.73     joerg     } else if (gn->type & OP_LIB) {
   1971    1.1       cgd 	/*
   1972    1.1       cgd 	 * If the node is a library, it is the arch module's job to find it
   1973    1.1       cgd 	 * and set the TARGET variable accordingly. We merely provide the
   1974    1.1       cgd 	 * search path, assuming all libraries end in ".a" (if the suffix
   1975    1.1       cgd 	 * hasn't been defined, there's nothing we can do for it, so we just
   1976    1.1       cgd 	 * set the TARGET variable to the node's name in order to give it a
   1977    1.1       cgd 	 * value).
   1978    1.1       cgd 	 */
   1979  1.166    rillig 	Suff *s = FindSuffByName(LIBSUFF);
   1980   1.73     joerg 	if (gn->suffix)
   1981   1.73     joerg 	    gn->suffix->refCount--;
   1982  1.166    rillig 	if (s != NULL) {
   1983  1.166    rillig 	    gn->suffix = s;
   1984   1.73     joerg 	    gn->suffix->refCount++;
   1985   1.73     joerg 	    Arch_FindLib(gn, s->searchPath);
   1986   1.73     joerg 	} else {
   1987   1.73     joerg 	    gn->suffix = NULL;
   1988   1.87    rillig 	    Var_Set(TARGET, gn->name, gn);
   1989   1.73     joerg 	}
   1990    1.1       cgd 	/*
   1991    1.1       cgd 	 * Because a library (-lfoo) target doesn't follow the standard
   1992    1.1       cgd 	 * filesystem conventions, we don't set the regular variables for
   1993    1.1       cgd 	 * the thing. .PREFIX is simply made empty...
   1994    1.1       cgd 	 */
   1995   1.87    rillig 	Var_Set(PREFIX, "", gn);
   1996   1.73     joerg     } else {
   1997   1.73     joerg 	SuffFindNormalDeps(gn, slst);
   1998   1.73     joerg     }
   1999   1.73     joerg }
   2000   1.71  christos 
   2001  1.134    rillig /* Define which suffix is the null suffix.
   2002  1.134    rillig  *
   2003  1.134    rillig  * Need to handle the changing of the null suffix gracefully so the old
   2004  1.134    rillig  * transformation rules don't just go away.
   2005    1.1       cgd  *
   2006   1.39       wiz  * Input:
   2007   1.73     joerg  *	name		Name of null suffix
   2008    1.1       cgd  */
   2009    1.1       cgd void
   2010  1.167    rillig Suff_SetNull(const char *name)
   2011    1.1       cgd {
   2012  1.166    rillig     Suff *s = FindSuffByName(name);
   2013  1.166    rillig     if (s == NULL) {
   2014  1.166    rillig 	Parse_Error(PARSE_WARNING, "Desired null suffix %s not defined.",
   2015  1.166    rillig 		    name);
   2016  1.166    rillig 	return;
   2017  1.166    rillig     }
   2018    1.1       cgd 
   2019  1.166    rillig     if (suffNull != NULL) {
   2020  1.177    rillig 	suffNull->flags &= ~(unsigned)SUFF_NULL;
   2021   1.73     joerg     }
   2022  1.166    rillig     s->flags |= SUFF_NULL;
   2023  1.166    rillig     /*
   2024  1.166    rillig      * XXX: Here's where the transformation mangling would take place
   2025  1.166    rillig      */
   2026  1.166    rillig     suffNull = s;
   2027    1.1       cgd }
   2028    1.1       cgd 
   2029  1.127    rillig /* Initialize the suffixes module. */
   2030    1.1       cgd void
   2031   1.39       wiz Suff_Init(void)
   2032    1.1       cgd {
   2033   1.73     joerg #ifdef CLEANUP
   2034  1.180    rillig     suffClean = Lst_New();
   2035  1.180    rillig     sufflist = Lst_New();
   2036   1.73     joerg #endif
   2037  1.180    rillig     srclist = Lst_New();
   2038  1.180    rillig     transforms = Lst_New();
   2039    1.1       cgd 
   2040   1.73     joerg     /*
   2041   1.73     joerg      * Create null suffix for single-suffix rules (POSIX). The thing doesn't
   2042   1.73     joerg      * actually go on the suffix list or everyone will think that's its
   2043   1.73     joerg      * suffix.
   2044   1.73     joerg      */
   2045   1.75       sjg     Suff_ClearSuffixes();
   2046    1.1       cgd }
   2047    1.5       jtc 
   2048    1.5       jtc 
   2049  1.127    rillig /* Clean up the suffixes module. */
   2050    1.6       jtc void
   2051   1.39       wiz Suff_End(void)
   2052    1.5       jtc {
   2053   1.25   mycroft #ifdef CLEANUP
   2054  1.125    rillig     Lst_Destroy(sufflist, SuffFree);
   2055  1.125    rillig     Lst_Destroy(suffClean, SuffFree);
   2056   1.73     joerg     if (suffNull)
   2057   1.73     joerg 	SuffFree(suffNull);
   2058  1.125    rillig     Lst_Free(srclist);
   2059  1.125    rillig     Lst_Free(transforms);
   2060   1.25   mycroft #endif
   2061    1.5       jtc }
   2062    1.5       jtc 
   2063    1.1       cgd 
   2064   1.73     joerg /********************* DEBUGGING FUNCTIONS **********************/
   2065    1.1       cgd 
   2066  1.165    rillig static void
   2067  1.191    rillig PrintSuffNames(const char *prefix, SuffList *suffs)
   2068    1.6       jtc {
   2069  1.191    rillig     SuffListNode *ln;
   2070  1.191    rillig 
   2071  1.191    rillig     debug_printf("#\t%s: ", prefix);
   2072  1.191    rillig     for (ln = suffs->first; ln != NULL; ln = ln->next) {
   2073  1.191    rillig 	Suff *suff = ln->datum;
   2074  1.191    rillig 	debug_printf("%s ", suff->name);
   2075  1.191    rillig     }
   2076  1.191    rillig     debug_printf("\n");
   2077    1.6       jtc }
   2078    1.1       cgd 
   2079  1.165    rillig static void
   2080  1.191    rillig PrintSuff(Suff *s)
   2081    1.1       cgd {
   2082  1.172    rillig     debug_printf("# `%s' [%d] ", s->name, s->refCount);
   2083  1.122    rillig     if (s->flags != 0) {
   2084  1.122    rillig 	char flags_buf[SuffFlags_ToStringSize];
   2085  1.122    rillig 
   2086  1.172    rillig 	debug_printf(" (%s)",
   2087  1.172    rillig 		     Enum_FlagsToString(flags_buf, sizeof flags_buf,
   2088  1.172    rillig 					s->flags, SuffFlags_ToStringSpecs));
   2089    1.1       cgd     }
   2090  1.191    rillig     debug_printf("\n");
   2091  1.191    rillig 
   2092  1.191    rillig     PrintSuffNames("To", s->parents);
   2093  1.191    rillig     PrintSuffNames("From", s->children);
   2094  1.191    rillig 
   2095  1.172    rillig     debug_printf("#\tSearch Path: ");
   2096   1.48  christos     Dir_PrintPath(s->searchPath);
   2097  1.191    rillig     debug_printf("\n");
   2098    1.1       cgd }
   2099    1.1       cgd 
   2100  1.165    rillig static void
   2101  1.191    rillig PrintTransformation(GNode *t)
   2102    1.1       cgd {
   2103  1.172    rillig     debug_printf("%-16s:", t->name);
   2104   1.48  christos     Targ_PrintType(t->type);
   2105  1.191    rillig     debug_printf("\n");
   2106  1.151    rillig     Targ_PrintCmds(t);
   2107  1.191    rillig     debug_printf("\n");
   2108    1.1       cgd }
   2109    1.1       cgd 
   2110    1.4       cgd void
   2111   1.39       wiz Suff_PrintAll(void)
   2112    1.1       cgd {
   2113  1.172    rillig     debug_printf("#*** Suffixes:\n");
   2114  1.191    rillig     {
   2115  1.191    rillig 	SuffListNode *ln;
   2116  1.191    rillig 	for (ln = sufflist->first; ln != NULL; ln = ln->next)
   2117  1.191    rillig 	    PrintSuff(ln->datum);
   2118  1.191    rillig     }
   2119    1.1       cgd 
   2120  1.172    rillig     debug_printf("#*** Transformations:\n");
   2121  1.191    rillig     {
   2122  1.191    rillig 	GNodeListNode *ln;
   2123  1.191    rillig 	for (ln = transforms->first; ln != NULL; ln = ln->next)
   2124  1.191    rillig 	    PrintTransformation(ln->datum);
   2125  1.191    rillig     }
   2126    1.1       cgd }
   2127