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