xref: /freebsd/contrib/bmake/suff.c (revision faf139cc5dd3396181c11922bc6685c0c59b7b24)
1 /*	$NetBSD: suff.c,v 1.78 2016/02/18 18:29:14 christos 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 #ifndef MAKE_NATIVE
72 static char rcsid[] = "$NetBSD: suff.c,v 1.78 2016/02/18 18:29:14 christos Exp $";
73 #else
74 #include <sys/cdefs.h>
75 #ifndef lint
76 #if 0
77 static char sccsid[] = "@(#)suff.c	8.4 (Berkeley) 3/21/94";
78 #else
79 __RCSID("$NetBSD: suff.c,v 1.78 2016/02/18 18:29:14 christos Exp $");
80 #endif
81 #endif /* not lint */
82 #endif
83 
84 /*-
85  * suff.c --
86  *	Functions to maintain suffix lists and find implicit dependents
87  *	using suffix transformation rules
88  *
89  * Interface:
90  *	Suff_Init 	    	Initialize all things to do with suffixes.
91  *
92  *	Suff_End 	    	Cleanup the module
93  *
94  *	Suff_DoPaths	    	This function is used to make life easier
95  *	    	  	    	when searching for a file according to its
96  *	    	  	    	suffix. It takes the global search path,
97  *	    	  	    	as defined using the .PATH: target, and appends
98  *	    	  	    	its directories to the path of each of the
99  *	    	  	    	defined suffixes, as specified using
100  *	    	  	    	.PATH<suffix>: targets. In addition, all
101  *	    	  	    	directories given for suffixes labeled as
102  *	    	  	    	include files or libraries, using the .INCLUDES
103  *	    	  	    	or .LIBS targets, are played with using
104  *	    	  	    	Dir_MakeFlags to create the .INCLUDES and
105  *	    	  	    	.LIBS global variables.
106  *
107  *	Suff_ClearSuffixes  	Clear out all the suffixes and defined
108  *	    	  	    	transformations.
109  *
110  *	Suff_IsTransform    	Return TRUE if the passed string is the lhs
111  *	    	  	    	of a transformation rule.
112  *
113  *	Suff_AddSuffix	    	Add the passed string as another known suffix.
114  *
115  *	Suff_GetPath	    	Return the search path for the given suffix.
116  *
117  *	Suff_AddInclude	    	Mark the given suffix as denoting an include
118  *	    	  	    	file.
119  *
120  *	Suff_AddLib	    	Mark the given suffix as denoting a library.
121  *
122  *	Suff_AddTransform   	Add another transformation to the suffix
123  *	    	  	    	graph. Returns  GNode suitable for framing, I
124  *	    	  	    	mean, tacking commands, attributes, etc. on.
125  *
126  *	Suff_SetNull	    	Define the suffix to consider the suffix of
127  *	    	  	    	any file that doesn't have a known one.
128  *
129  *	Suff_FindDeps	    	Find implicit sources for and the location of
130  *	    	  	    	a target based on its suffix. Returns the
131  *	    	  	    	bottom-most node added to the graph or NULL
132  *	    	  	    	if the target had no implicit sources.
133  *
134  *	Suff_FindPath	    	Return the appropriate path to search in
135  *				order to find the node.
136  */
137 
138 #include    	  <stdio.h>
139 #include	  "make.h"
140 #include	  "hash.h"
141 #include	  "dir.h"
142 
143 static Lst       sufflist;	/* Lst of suffixes */
144 #ifdef CLEANUP
145 static Lst	 suffClean;	/* Lst of suffixes to be cleaned */
146 #endif
147 static Lst	 srclist;	/* Lst of sources */
148 static Lst       transforms;	/* Lst of transformation rules */
149 
150 static int        sNum = 0;	/* Counter for assigning suffix numbers */
151 
152 /*
153  * Structure describing an individual suffix.
154  */
155 typedef struct _Suff {
156     char         *name;	    	/* The suffix itself */
157     int		 nameLen;	/* Length of the suffix */
158     short	 flags;      	/* Type of suffix */
159 #define SUFF_INCLUDE	  0x01	    /* One which is #include'd */
160 #define SUFF_LIBRARY	  0x02	    /* One which contains a library */
161 #define SUFF_NULL 	  0x04	    /* The empty suffix */
162     Lst    	 searchPath;	/* The path along which files of this suffix
163 				 * may be found */
164     int          sNum;	      	/* The suffix number */
165     int		 refCount;	/* Reference count of list membership */
166     Lst          parents;	/* Suffixes we have a transformation to */
167     Lst          children;	/* Suffixes we have a transformation from */
168     Lst		 ref;		/* List of lists this suffix is referenced */
169 } Suff;
170 
171 /*
172  * for SuffSuffIsSuffix
173  */
174 typedef struct {
175     char	*ename;		/* The end of the name */
176     int		 len;		/* Length of the name */
177 } SuffixCmpData;
178 
179 /*
180  * Structure used in the search for implied sources.
181  */
182 typedef struct _Src {
183     char            *file;	/* The file to look for */
184     char    	    *pref;  	/* Prefix from which file was formed */
185     Suff            *suff;	/* The suffix on the file */
186     struct _Src     *parent;	/* The Src for which this is a source */
187     GNode           *node;	/* The node describing the file */
188     int	    	    children;	/* Count of existing children (so we don't free
189 				 * this thing too early or never nuke it) */
190 #ifdef DEBUG_SRC
191     Lst		    cp;		/* Debug; children list */
192 #endif
193 } Src;
194 
195 /*
196  * A structure for passing more than one argument to the Lst-library-invoked
197  * function...
198  */
199 typedef struct {
200     Lst            l;
201     Src            *s;
202 } LstSrc;
203 
204 typedef struct {
205     GNode	  **gn;
206     Suff	   *s;
207     Boolean	    r;
208 } GNodeSuff;
209 
210 static Suff 	    *suffNull;	/* The NULL suffix for this run */
211 static Suff 	    *emptySuff;	/* The empty suffix required for POSIX
212 				 * single-suffix transformation rules */
213 
214 
215 static const char *SuffStrIsPrefix(const char *, const char *);
216 static char *SuffSuffIsSuffix(const Suff *, const SuffixCmpData *);
217 static int SuffSuffIsSuffixP(const void *, const void *);
218 static int SuffSuffHasNameP(const void *, const void *);
219 static int SuffSuffIsPrefix(const void *, const void *);
220 static int SuffGNHasNameP(const void *, const void *);
221 static void SuffUnRef(void *, void *);
222 static void SuffFree(void *);
223 static void SuffInsert(Lst, Suff *);
224 static void SuffRemove(Lst, Suff *);
225 static Boolean SuffParseTransform(char *, Suff **, Suff **);
226 static int SuffRebuildGraph(void *, void *);
227 static int SuffScanTargets(void *, void *);
228 static int SuffAddSrc(void *, void *);
229 static int SuffRemoveSrc(Lst);
230 static void SuffAddLevel(Lst, Src *);
231 static Src *SuffFindThem(Lst, Lst);
232 static Src *SuffFindCmds(Src *, Lst);
233 static void SuffExpandChildren(LstNode, GNode *);
234 static void SuffExpandWildcards(LstNode, GNode *);
235 static Boolean SuffApplyTransform(GNode *, GNode *, Suff *, Suff *);
236 static void SuffFindDeps(GNode *, Lst);
237 static void SuffFindArchiveDeps(GNode *, Lst);
238 static void SuffFindNormalDeps(GNode *, Lst);
239 static int SuffPrintName(void *, void *);
240 static int SuffPrintSuff(void *, void *);
241 static int SuffPrintTrans(void *, void *);
242 
243 	/*************** Lst Predicates ****************/
244 /*-
245  *-----------------------------------------------------------------------
246  * SuffStrIsPrefix  --
247  *	See if pref is a prefix of str.
248  *
249  * Input:
250  *	pref		possible prefix
251  *	str		string to check
252  *
253  * Results:
254  *	NULL if it ain't, pointer to character in str after prefix if so
255  *
256  * Side Effects:
257  *	None
258  *-----------------------------------------------------------------------
259  */
260 static const char *
261 SuffStrIsPrefix(const char *pref, const char *str)
262 {
263     while (*str && *pref == *str) {
264 	pref++;
265 	str++;
266     }
267 
268     return (*pref ? NULL : str);
269 }
270 
271 /*-
272  *-----------------------------------------------------------------------
273  * SuffSuffIsSuffix  --
274  *	See if suff is a suffix of str. sd->ename should point to THE END
275  *	of the string to check. (THE END == the null byte)
276  *
277  * Input:
278  *	s		possible suffix
279  *	sd		string to examine
280  *
281  * Results:
282  *	NULL if it ain't, pointer to character in str before suffix if
283  *	it is.
284  *
285  * Side Effects:
286  *	None
287  *-----------------------------------------------------------------------
288  */
289 static char *
290 SuffSuffIsSuffix(const Suff *s, const SuffixCmpData *sd)
291 {
292     char  *p1;	    	/* Pointer into suffix name */
293     char  *p2;	    	/* Pointer into string being examined */
294 
295     if (sd->len < s->nameLen)
296 	return NULL;		/* this string is shorter than the suffix */
297 
298     p1 = s->name + s->nameLen;
299     p2 = sd->ename;
300 
301     while (p1 >= s->name && *p1 == *p2) {
302 	p1--;
303 	p2--;
304     }
305 
306     return (p1 == s->name - 1 ? p2 : NULL);
307 }
308 
309 /*-
310  *-----------------------------------------------------------------------
311  * SuffSuffIsSuffixP --
312  *	Predicate form of SuffSuffIsSuffix. Passed as the callback function
313  *	to Lst_Find.
314  *
315  * Results:
316  *	0 if the suffix is the one desired, non-zero if not.
317  *
318  * Side Effects:
319  *	None.
320  *
321  *-----------------------------------------------------------------------
322  */
323 static int
324 SuffSuffIsSuffixP(const void *s, const void *sd)
325 {
326     return(!SuffSuffIsSuffix(s, sd));
327 }
328 
329 /*-
330  *-----------------------------------------------------------------------
331  * SuffSuffHasNameP --
332  *	Callback procedure for finding a suffix based on its name. Used by
333  *	Suff_GetPath.
334  *
335  * Input:
336  *	s		Suffix to check
337  *	sd		Desired name
338  *
339  * Results:
340  *	0 if the suffix is of the given name. non-zero otherwise.
341  *
342  * Side Effects:
343  *	None
344  *-----------------------------------------------------------------------
345  */
346 static int
347 SuffSuffHasNameP(const void *s, const void *sname)
348 {
349     return (strcmp(sname, ((const Suff *)s)->name));
350 }
351 
352 /*-
353  *-----------------------------------------------------------------------
354  * SuffSuffIsPrefix  --
355  *	See if the suffix described by s is a prefix of the string. Care
356  *	must be taken when using this to search for transformations and
357  *	what-not, since there could well be two suffixes, one of which
358  *	is a prefix of the other...
359  *
360  * Input:
361  *	s		suffix to compare
362  *	str		string to examine
363  *
364  * Results:
365  *	0 if s is a prefix of str. non-zero otherwise
366  *
367  * Side Effects:
368  *	None
369  *-----------------------------------------------------------------------
370  */
371 static int
372 SuffSuffIsPrefix(const void *s, const void *str)
373 {
374     return SuffStrIsPrefix(((const Suff *)s)->name, str) == NULL;
375 }
376 
377 /*-
378  *-----------------------------------------------------------------------
379  * SuffGNHasNameP  --
380  *	See if the graph node has the desired name
381  *
382  * Input:
383  *	gn		current node we're looking at
384  *	name		name we're looking for
385  *
386  * Results:
387  *	0 if it does. non-zero if it doesn't
388  *
389  * Side Effects:
390  *	None
391  *-----------------------------------------------------------------------
392  */
393 static int
394 SuffGNHasNameP(const void *gn, const void *name)
395 {
396     return (strcmp(name, ((const GNode *)gn)->name));
397 }
398 
399  	    /*********** Maintenance Functions ************/
400 
401 static void
402 SuffUnRef(void *lp, void *sp)
403 {
404     Lst l = (Lst) lp;
405 
406     LstNode ln = Lst_Member(l, sp);
407     if (ln != NULL) {
408 	Lst_Remove(l, ln);
409 	((Suff *)sp)->refCount--;
410     }
411 }
412 
413 /*-
414  *-----------------------------------------------------------------------
415  * SuffFree  --
416  *	Free up all memory associated with the given suffix structure.
417  *
418  * Results:
419  *	none
420  *
421  * Side Effects:
422  *	the suffix entry is detroyed
423  *-----------------------------------------------------------------------
424  */
425 static void
426 SuffFree(void *sp)
427 {
428     Suff           *s = (Suff *)sp;
429 
430     if (s == suffNull)
431 	suffNull = NULL;
432 
433     if (s == emptySuff)
434 	emptySuff = NULL;
435 
436 #ifdef notdef
437     /* We don't delete suffixes in order, so we cannot use this */
438     if (s->refCount)
439 	Punt("Internal error deleting suffix `%s' with refcount = %d", s->name,
440 	    s->refCount);
441 #endif
442 
443     Lst_Destroy(s->ref, NULL);
444     Lst_Destroy(s->children, NULL);
445     Lst_Destroy(s->parents, NULL);
446     Lst_Destroy(s->searchPath, Dir_Destroy);
447 
448     free(s->name);
449     free(s);
450 }
451 
452 /*-
453  *-----------------------------------------------------------------------
454  * SuffRemove  --
455  *	Remove the suffix into the list
456  *
457  * Results:
458  *	None
459  *
460  * Side Effects:
461  *	The reference count for the suffix is decremented and the
462  *	suffix is possibly freed
463  *-----------------------------------------------------------------------
464  */
465 static void
466 SuffRemove(Lst l, Suff *s)
467 {
468     SuffUnRef(l, s);
469     if (s->refCount == 0) {
470 	SuffUnRef(sufflist, s);
471 	SuffFree(s);
472     }
473 }
474 
475 /*-
476  *-----------------------------------------------------------------------
477  * SuffInsert  --
478  *	Insert the suffix into the list keeping the list ordered by suffix
479  *	numbers.
480  *
481  * Input:
482  *	l		the list where in s should be inserted
483  *	s		the suffix to insert
484  *
485  * Results:
486  *	None
487  *
488  * Side Effects:
489  *	The reference count of the suffix is incremented
490  *-----------------------------------------------------------------------
491  */
492 static void
493 SuffInsert(Lst l, Suff *s)
494 {
495     LstNode 	  ln;		/* current element in l we're examining */
496     Suff          *s2 = NULL;	/* the suffix descriptor in this element */
497 
498     if (Lst_Open(l) == FAILURE) {
499 	return;
500     }
501     while ((ln = Lst_Next(l)) != NULL) {
502 	s2 = (Suff *)Lst_Datum(ln);
503 	if (s2->sNum >= s->sNum) {
504 	    break;
505 	}
506     }
507 
508     Lst_Close(l);
509     if (DEBUG(SUFF)) {
510 	fprintf(debug_file, "inserting %s(%d)...", s->name, s->sNum);
511     }
512     if (ln == NULL) {
513 	if (DEBUG(SUFF)) {
514 	    fprintf(debug_file, "at end of list\n");
515 	}
516 	(void)Lst_AtEnd(l, s);
517 	s->refCount++;
518 	(void)Lst_AtEnd(s->ref, l);
519     } else if (s2->sNum != s->sNum) {
520 	if (DEBUG(SUFF)) {
521 	    fprintf(debug_file, "before %s(%d)\n", s2->name, s2->sNum);
522 	}
523 	(void)Lst_InsertBefore(l, ln, s);
524 	s->refCount++;
525 	(void)Lst_AtEnd(s->ref, l);
526     } else if (DEBUG(SUFF)) {
527 	fprintf(debug_file, "already there\n");
528     }
529 }
530 
531 /*-
532  *-----------------------------------------------------------------------
533  * Suff_ClearSuffixes --
534  *	This is gross. Nuke the list of suffixes but keep all transformation
535  *	rules around. The transformation graph is destroyed in this process,
536  *	but we leave the list of rules so when a new graph is formed the rules
537  *	will remain.
538  *	This function is called from the parse module when a
539  *	.SUFFIXES:\n line is encountered.
540  *
541  * Results:
542  *	none
543  *
544  * Side Effects:
545  *	the sufflist and its graph nodes are destroyed
546  *-----------------------------------------------------------------------
547  */
548 void
549 Suff_ClearSuffixes(void)
550 {
551 #ifdef CLEANUP
552     Lst_Concat(suffClean, sufflist, LST_CONCLINK);
553 #endif
554     sufflist = Lst_Init(FALSE);
555     sNum = 0;
556     if (suffNull)
557 	SuffFree(suffNull);
558     emptySuff = suffNull = bmake_malloc(sizeof(Suff));
559 
560     suffNull->name =   	    bmake_strdup("");
561     suffNull->nameLen =     0;
562     suffNull->searchPath =  Lst_Init(FALSE);
563     Dir_Concat(suffNull->searchPath, dirSearchPath);
564     suffNull->children =    Lst_Init(FALSE);
565     suffNull->parents =	    Lst_Init(FALSE);
566     suffNull->ref =	    Lst_Init(FALSE);
567     suffNull->sNum =   	    sNum++;
568     suffNull->flags =  	    SUFF_NULL;
569     suffNull->refCount =    1;
570 }
571 
572 /*-
573  *-----------------------------------------------------------------------
574  * SuffParseTransform --
575  *	Parse a transformation string to find its two component suffixes.
576  *
577  * Input:
578  *	str		String being parsed
579  *	srcPtr		Place to store source of trans.
580  *	targPtr		Place to store target of trans.
581  *
582  * Results:
583  *	TRUE if the string is a valid transformation and FALSE otherwise.
584  *
585  * Side Effects:
586  *	The passed pointers are overwritten.
587  *
588  *-----------------------------------------------------------------------
589  */
590 static Boolean
591 SuffParseTransform(char *str, Suff **srcPtr, Suff **targPtr)
592 {
593     LstNode		srcLn;	    /* element in suffix list of trans source*/
594     Suff		*src;	    /* Source of transformation */
595     LstNode		targLn;	    /* element in suffix list of trans target*/
596     char		*str2;	    /* Extra pointer (maybe target suffix) */
597     LstNode 	    	singleLn;   /* element in suffix list of any suffix
598 				     * that exactly matches str */
599     Suff    	    	*single = NULL;/* Source of possible transformation to
600 				     * null suffix */
601 
602     srcLn = NULL;
603     singleLn = NULL;
604 
605     /*
606      * Loop looking first for a suffix that matches the start of the
607      * string and then for one that exactly matches the rest of it. If
608      * we can find two that meet these criteria, we've successfully
609      * parsed the string.
610      */
611     for (;;) {
612 	if (srcLn == NULL) {
613 	    srcLn = Lst_Find(sufflist, str, SuffSuffIsPrefix);
614 	} else {
615 	    srcLn = Lst_FindFrom(sufflist, Lst_Succ(srcLn), str,
616 				  SuffSuffIsPrefix);
617 	}
618 	if (srcLn == NULL) {
619 	    /*
620 	     * Ran out of source suffixes -- no such rule
621 	     */
622 	    if (singleLn != NULL) {
623 		/*
624 		 * Not so fast Mr. Smith! There was a suffix that encompassed
625 		 * the entire string, so we assume it was a transformation
626 		 * to the null suffix (thank you POSIX). We still prefer to
627 		 * find a double rule over a singleton, hence we leave this
628 		 * check until the end.
629 		 *
630 		 * XXX: Use emptySuff over suffNull?
631 		 */
632 		*srcPtr = single;
633 		*targPtr = suffNull;
634 		return(TRUE);
635 	    }
636 	    return (FALSE);
637 	}
638 	src = (Suff *)Lst_Datum(srcLn);
639 	str2 = str + src->nameLen;
640 	if (*str2 == '\0') {
641 	    single = src;
642 	    singleLn = srcLn;
643 	} else {
644 	    targLn = Lst_Find(sufflist, str2, SuffSuffHasNameP);
645 	    if (targLn != NULL) {
646 		*srcPtr = src;
647 		*targPtr = (Suff *)Lst_Datum(targLn);
648 		return (TRUE);
649 	    }
650 	}
651     }
652 }
653 
654 /*-
655  *-----------------------------------------------------------------------
656  * Suff_IsTransform  --
657  *	Return TRUE if the given string is a transformation rule
658  *
659  *
660  * Input:
661  *	str		string to check
662  *
663  * Results:
664  *	TRUE if the string is a concatenation of two known suffixes.
665  *	FALSE otherwise
666  *
667  * Side Effects:
668  *	None
669  *-----------------------------------------------------------------------
670  */
671 Boolean
672 Suff_IsTransform(char *str)
673 {
674     Suff    	  *src, *targ;
675 
676     return (SuffParseTransform(str, &src, &targ));
677 }
678 
679 /*-
680  *-----------------------------------------------------------------------
681  * Suff_AddTransform --
682  *	Add the transformation rule described by the line to the
683  *	list of rules and place the transformation itself in the graph
684  *
685  * Input:
686  *	line		name of transformation to add
687  *
688  * Results:
689  *	The node created for the transformation in the transforms list
690  *
691  * Side Effects:
692  *	The node is placed on the end of the transforms Lst and links are
693  *	made between the two suffixes mentioned in the target name
694  *-----------------------------------------------------------------------
695  */
696 GNode *
697 Suff_AddTransform(char *line)
698 {
699     GNode         *gn;		/* GNode of transformation rule */
700     Suff          *s,		/* source suffix */
701                   *t;		/* target suffix */
702     LstNode 	  ln;	    	/* Node for existing transformation */
703 
704     ln = Lst_Find(transforms, line, SuffGNHasNameP);
705     if (ln == NULL) {
706 	/*
707 	 * Make a new graph node for the transformation. It will be filled in
708 	 * by the Parse module.
709 	 */
710 	gn = Targ_NewGN(line);
711 	(void)Lst_AtEnd(transforms, gn);
712     } else {
713 	/*
714 	 * New specification for transformation rule. Just nuke the old list
715 	 * of commands so they can be filled in again... We don't actually
716 	 * free the commands themselves, because a given command can be
717 	 * attached to several different transformations.
718 	 */
719 	gn = (GNode *)Lst_Datum(ln);
720 	Lst_Destroy(gn->commands, NULL);
721 	Lst_Destroy(gn->children, NULL);
722 	gn->commands = Lst_Init(FALSE);
723 	gn->children = Lst_Init(FALSE);
724     }
725 
726     gn->type = OP_TRANSFORM;
727 
728     (void)SuffParseTransform(line, &s, &t);
729 
730     /*
731      * link the two together in the proper relationship and order
732      */
733     if (DEBUG(SUFF)) {
734 	fprintf(debug_file, "defining transformation from `%s' to `%s'\n",
735 		s->name, t->name);
736     }
737     SuffInsert(t->children, s);
738     SuffInsert(s->parents, t);
739 
740     return (gn);
741 }
742 
743 /*-
744  *-----------------------------------------------------------------------
745  * Suff_EndTransform --
746  *	Handle the finish of a transformation definition, removing the
747  *	transformation from the graph if it has neither commands nor
748  *	sources. This is a callback procedure for the Parse module via
749  *	Lst_ForEach
750  *
751  * Input:
752  *	gnp		Node for transformation
753  *	dummy		Node for transformation
754  *
755  * Results:
756  *	=== 0
757  *
758  * Side Effects:
759  *	If the node has no commands or children, the children and parents
760  *	lists of the affected suffixes are altered.
761  *
762  *-----------------------------------------------------------------------
763  */
764 int
765 Suff_EndTransform(void *gnp, void *dummy)
766 {
767     GNode *gn = (GNode *)gnp;
768 
769     if ((gn->type & OP_DOUBLEDEP) && !Lst_IsEmpty (gn->cohorts))
770 	gn = (GNode *)Lst_Datum(Lst_Last(gn->cohorts));
771     if ((gn->type & OP_TRANSFORM) && Lst_IsEmpty(gn->commands) &&
772 	Lst_IsEmpty(gn->children))
773     {
774 	Suff	*s, *t;
775 
776 	/*
777 	 * SuffParseTransform() may fail for special rules which are not
778 	 * actual transformation rules. (e.g. .DEFAULT)
779 	 */
780 	if (SuffParseTransform(gn->name, &s, &t)) {
781 	    Lst	 p;
782 
783 	    if (DEBUG(SUFF)) {
784 		fprintf(debug_file, "deleting transformation from `%s' to `%s'\n",
785 		s->name, t->name);
786 	    }
787 
788 	    /*
789 	     * Store s->parents because s could be deleted in SuffRemove
790 	     */
791 	    p = s->parents;
792 
793 	    /*
794 	     * Remove the source from the target's children list. We check for a
795 	     * nil return to handle a beanhead saying something like
796 	     *  .c.o .c.o:
797 	     *
798 	     * We'll be called twice when the next target is seen, but .c and .o
799 	     * are only linked once...
800 	     */
801 	    SuffRemove(t->children, s);
802 
803 	    /*
804 	     * Remove the target from the source's parents list
805 	     */
806 	    SuffRemove(p, t);
807 	}
808     } else if ((gn->type & OP_TRANSFORM) && DEBUG(SUFF)) {
809 	fprintf(debug_file, "transformation %s complete\n", gn->name);
810     }
811 
812     return(dummy ? 0 : 0);
813 }
814 
815 /*-
816  *-----------------------------------------------------------------------
817  * SuffRebuildGraph --
818  *	Called from Suff_AddSuffix via Lst_ForEach to search through the
819  *	list of existing transformation rules and rebuild the transformation
820  *	graph when it has been destroyed by Suff_ClearSuffixes. If the
821  *	given rule is a transformation involving this suffix and another,
822  *	existing suffix, the proper relationship is established between
823  *	the two.
824  *
825  * Input:
826  *	transformp	Transformation to test
827  *	sp		Suffix to rebuild
828  *
829  * Results:
830  *	Always 0.
831  *
832  * Side Effects:
833  *	The appropriate links will be made between this suffix and
834  *	others if transformation rules exist for it.
835  *
836  *-----------------------------------------------------------------------
837  */
838 static int
839 SuffRebuildGraph(void *transformp, void *sp)
840 {
841     GNode   	*transform = (GNode *)transformp;
842     Suff    	*s = (Suff *)sp;
843     char 	*cp;
844     LstNode	ln;
845     Suff  	*s2;
846     SuffixCmpData sd;
847 
848     /*
849      * First see if it is a transformation from this suffix.
850      */
851     cp = UNCONST(SuffStrIsPrefix(s->name, transform->name));
852     if (cp != NULL) {
853 	ln = Lst_Find(sufflist, cp, SuffSuffHasNameP);
854 	if (ln != NULL) {
855 	    /*
856 	     * Found target. Link in and return, since it can't be anything
857 	     * else.
858 	     */
859 	    s2 = (Suff *)Lst_Datum(ln);
860 	    SuffInsert(s2->children, s);
861 	    SuffInsert(s->parents, s2);
862 	    return(0);
863 	}
864     }
865 
866     /*
867      * Not from, maybe to?
868      */
869     sd.len = strlen(transform->name);
870     sd.ename = transform->name + sd.len;
871     cp = SuffSuffIsSuffix(s, &sd);
872     if (cp != NULL) {
873 	/*
874 	 * Null-terminate the source suffix in order to find it.
875 	 */
876 	cp[1] = '\0';
877 	ln = Lst_Find(sufflist, transform->name, SuffSuffHasNameP);
878 	/*
879 	 * Replace the start of the target suffix
880 	 */
881 	cp[1] = s->name[0];
882 	if (ln != NULL) {
883 	    /*
884 	     * Found it -- establish the proper relationship
885 	     */
886 	    s2 = (Suff *)Lst_Datum(ln);
887 	    SuffInsert(s->children, s2);
888 	    SuffInsert(s2->parents, s);
889 	}
890     }
891     return(0);
892 }
893 
894 /*-
895  *-----------------------------------------------------------------------
896  * SuffScanTargets --
897  *	Called from Suff_AddSuffix via Lst_ForEach to search through the
898  *	list of existing targets and find if any of the existing targets
899  *	can be turned into a transformation rule.
900  *
901  * Results:
902  *	1 if a new main target has been selected, 0 otherwise.
903  *
904  * Side Effects:
905  *	If such a target is found and the target is the current main
906  *	target, the main target is set to NULL and the next target
907  *	examined (if that exists) becomes the main target.
908  *
909  *-----------------------------------------------------------------------
910  */
911 static int
912 SuffScanTargets(void *targetp, void *gsp)
913 {
914     GNode   	*target = (GNode *)targetp;
915     GNodeSuff	*gs = (GNodeSuff *)gsp;
916     Suff	*s, *t;
917     char 	*ptr;
918 
919     if (*gs->gn == NULL && gs->r && (target->type & OP_NOTARGET) == 0) {
920 	*gs->gn = target;
921 	Targ_SetMain(target);
922 	return 1;
923     }
924 
925     if ((unsigned int)target->type == OP_TRANSFORM)
926 	return 0;
927 
928     if ((ptr = strstr(target->name, gs->s->name)) == NULL ||
929 	ptr == target->name)
930 	return 0;
931 
932     if (SuffParseTransform(target->name, &s, &t)) {
933 	if (*gs->gn == target) {
934 	    gs->r = TRUE;
935 	    *gs->gn = NULL;
936 	    Targ_SetMain(NULL);
937 	}
938 	Lst_Destroy(target->children, NULL);
939 	target->children = Lst_Init(FALSE);
940 	target->type = OP_TRANSFORM;
941 	/*
942 	 * link the two together in the proper relationship and order
943 	 */
944 	if (DEBUG(SUFF)) {
945 	    fprintf(debug_file, "defining transformation from `%s' to `%s'\n",
946 		s->name, t->name);
947 	}
948 	SuffInsert(t->children, s);
949 	SuffInsert(s->parents, t);
950     }
951     return 0;
952 }
953 
954 /*-
955  *-----------------------------------------------------------------------
956  * Suff_AddSuffix --
957  *	Add the suffix in string to the end of the list of known suffixes.
958  *	Should we restructure the suffix graph? Make doesn't...
959  *
960  * Input:
961  *	str		the name of the suffix to add
962  *
963  * Results:
964  *	None
965  *
966  * Side Effects:
967  *	A GNode is created for the suffix and a Suff structure is created and
968  *	added to the suffixes list unless the suffix was already known.
969  *	The mainNode passed can be modified if a target mutated into a
970  *	transform and that target happened to be the main target.
971  *-----------------------------------------------------------------------
972  */
973 void
974 Suff_AddSuffix(char *str, GNode **gn)
975 {
976     Suff          *s;	    /* new suffix descriptor */
977     LstNode 	  ln;
978     GNodeSuff	  gs;
979 
980     ln = Lst_Find(sufflist, str, SuffSuffHasNameP);
981     if (ln == NULL) {
982 	s = bmake_malloc(sizeof(Suff));
983 
984 	s->name =   	bmake_strdup(str);
985 	s->nameLen = 	strlen(s->name);
986 	s->searchPath = Lst_Init(FALSE);
987 	s->children = 	Lst_Init(FALSE);
988 	s->parents = 	Lst_Init(FALSE);
989 	s->ref = 	Lst_Init(FALSE);
990 	s->sNum =   	sNum++;
991 	s->flags =  	0;
992 	s->refCount =	1;
993 
994 	(void)Lst_AtEnd(sufflist, s);
995 	/*
996 	 * We also look at our existing targets list to see if adding
997 	 * this suffix will make one of our current targets mutate into
998 	 * a suffix rule. This is ugly, but other makes treat all targets
999 	 * that start with a . as suffix rules.
1000 	 */
1001 	gs.gn = gn;
1002 	gs.s  = s;
1003 	gs.r  = FALSE;
1004 	Lst_ForEach(Targ_List(), SuffScanTargets, &gs);
1005 	/*
1006 	 * Look for any existing transformations from or to this suffix.
1007 	 * XXX: Only do this after a Suff_ClearSuffixes?
1008 	 */
1009 	Lst_ForEach(transforms, SuffRebuildGraph, s);
1010     }
1011 }
1012 
1013 /*-
1014  *-----------------------------------------------------------------------
1015  * Suff_GetPath --
1016  *	Return the search path for the given suffix, if it's defined.
1017  *
1018  * Results:
1019  *	The searchPath for the desired suffix or NULL if the suffix isn't
1020  *	defined.
1021  *
1022  * Side Effects:
1023  *	None
1024  *-----------------------------------------------------------------------
1025  */
1026 Lst
1027 Suff_GetPath(char *sname)
1028 {
1029     LstNode   	  ln;
1030     Suff    	  *s;
1031 
1032     ln = Lst_Find(sufflist, sname, SuffSuffHasNameP);
1033     if (ln == NULL) {
1034 	return NULL;
1035     } else {
1036 	s = (Suff *)Lst_Datum(ln);
1037 	return (s->searchPath);
1038     }
1039 }
1040 
1041 /*-
1042  *-----------------------------------------------------------------------
1043  * Suff_DoPaths --
1044  *	Extend the search paths for all suffixes to include the default
1045  *	search path.
1046  *
1047  * Results:
1048  *	None.
1049  *
1050  * Side Effects:
1051  *	The searchPath field of all the suffixes is extended by the
1052  *	directories in dirSearchPath. If paths were specified for the
1053  *	".h" suffix, the directories are stuffed into a global variable
1054  *	called ".INCLUDES" with each directory preceded by a -I. The same
1055  *	is done for the ".a" suffix, except the variable is called
1056  *	".LIBS" and the flag is -L.
1057  *-----------------------------------------------------------------------
1058  */
1059 void
1060 Suff_DoPaths(void)
1061 {
1062     Suff	   	*s;
1063     LstNode  		ln;
1064     char		*ptr;
1065     Lst	    	    	inIncludes; /* Cumulative .INCLUDES path */
1066     Lst	    	    	inLibs;	    /* Cumulative .LIBS path */
1067 
1068     if (Lst_Open(sufflist) == FAILURE) {
1069 	return;
1070     }
1071 
1072     inIncludes = Lst_Init(FALSE);
1073     inLibs = Lst_Init(FALSE);
1074 
1075     while ((ln = Lst_Next(sufflist)) != NULL) {
1076 	s = (Suff *)Lst_Datum(ln);
1077 	if (!Lst_IsEmpty (s->searchPath)) {
1078 #ifdef INCLUDES
1079 	    if (s->flags & SUFF_INCLUDE) {
1080 		Dir_Concat(inIncludes, s->searchPath);
1081 	    }
1082 #endif /* INCLUDES */
1083 #ifdef LIBRARIES
1084 	    if (s->flags & SUFF_LIBRARY) {
1085 		Dir_Concat(inLibs, s->searchPath);
1086 	    }
1087 #endif /* LIBRARIES */
1088 	    Dir_Concat(s->searchPath, dirSearchPath);
1089 	} else {
1090 	    Lst_Destroy(s->searchPath, Dir_Destroy);
1091 	    s->searchPath = Lst_Duplicate(dirSearchPath, Dir_CopyDir);
1092 	}
1093     }
1094 
1095     Var_Set(".INCLUDES", ptr = Dir_MakeFlags("-I", inIncludes), VAR_GLOBAL, 0);
1096     free(ptr);
1097     Var_Set(".LIBS", ptr = Dir_MakeFlags("-L", inLibs), VAR_GLOBAL, 0);
1098     free(ptr);
1099 
1100     Lst_Destroy(inIncludes, Dir_Destroy);
1101     Lst_Destroy(inLibs, Dir_Destroy);
1102 
1103     Lst_Close(sufflist);
1104 }
1105 
1106 /*-
1107  *-----------------------------------------------------------------------
1108  * Suff_AddInclude --
1109  *	Add the given suffix as a type of file which gets included.
1110  *	Called from the parse module when a .INCLUDES line is parsed.
1111  *	The suffix must have already been defined.
1112  *
1113  * Input:
1114  *	sname		Name of the suffix to mark
1115  *
1116  * Results:
1117  *	None.
1118  *
1119  * Side Effects:
1120  *	The SUFF_INCLUDE bit is set in the suffix's flags field
1121  *
1122  *-----------------------------------------------------------------------
1123  */
1124 void
1125 Suff_AddInclude(char *sname)
1126 {
1127     LstNode	  ln;
1128     Suff	  *s;
1129 
1130     ln = Lst_Find(sufflist, sname, SuffSuffHasNameP);
1131     if (ln != NULL) {
1132 	s = (Suff *)Lst_Datum(ln);
1133 	s->flags |= SUFF_INCLUDE;
1134     }
1135 }
1136 
1137 /*-
1138  *-----------------------------------------------------------------------
1139  * Suff_AddLib --
1140  *	Add the given suffix as a type of file which is a library.
1141  *	Called from the parse module when parsing a .LIBS line. The
1142  *	suffix must have been defined via .SUFFIXES before this is
1143  *	called.
1144  *
1145  * Input:
1146  *	sname		Name of the suffix to mark
1147  *
1148  * Results:
1149  *	None.
1150  *
1151  * Side Effects:
1152  *	The SUFF_LIBRARY bit is set in the suffix's flags field
1153  *
1154  *-----------------------------------------------------------------------
1155  */
1156 void
1157 Suff_AddLib(char *sname)
1158 {
1159     LstNode	  ln;
1160     Suff	  *s;
1161 
1162     ln = Lst_Find(sufflist, sname, SuffSuffHasNameP);
1163     if (ln != NULL) {
1164 	s = (Suff *)Lst_Datum(ln);
1165 	s->flags |= SUFF_LIBRARY;
1166     }
1167 }
1168 
1169  	  /********** Implicit Source Search Functions *********/
1170 
1171 /*-
1172  *-----------------------------------------------------------------------
1173  * SuffAddSrc  --
1174  *	Add a suffix as a Src structure to the given list with its parent
1175  *	being the given Src structure. If the suffix is the null suffix,
1176  *	the prefix is used unaltered as the file name in the Src structure.
1177  *
1178  * Input:
1179  *	sp		suffix for which to create a Src structure
1180  *	lsp		list and parent for the new Src
1181  *
1182  * Results:
1183  *	always returns 0
1184  *
1185  * Side Effects:
1186  *	A Src structure is created and tacked onto the end of the list
1187  *-----------------------------------------------------------------------
1188  */
1189 static int
1190 SuffAddSrc(void *sp, void *lsp)
1191 {
1192     Suff	*s = (Suff *)sp;
1193     LstSrc      *ls = (LstSrc *)lsp;
1194     Src         *s2;	    /* new Src structure */
1195     Src    	*targ; 	    /* Target structure */
1196 
1197     targ = ls->s;
1198 
1199     if ((s->flags & SUFF_NULL) && (*s->name != '\0')) {
1200 	/*
1201 	 * If the suffix has been marked as the NULL suffix, also create a Src
1202 	 * structure for a file with no suffix attached. Two birds, and all
1203 	 * that...
1204 	 */
1205 	s2 = bmake_malloc(sizeof(Src));
1206 	s2->file =  	bmake_strdup(targ->pref);
1207 	s2->pref =  	targ->pref;
1208 	s2->parent = 	targ;
1209 	s2->node =  	NULL;
1210 	s2->suff =  	s;
1211 	s->refCount++;
1212 	s2->children =	0;
1213 	targ->children += 1;
1214 	(void)Lst_AtEnd(ls->l, s2);
1215 #ifdef DEBUG_SRC
1216 	s2->cp = Lst_Init(FALSE);
1217 	Lst_AtEnd(targ->cp, s2);
1218 	fprintf(debug_file, "1 add %x %x to %x:", targ, s2, ls->l);
1219 	Lst_ForEach(ls->l, PrintAddr, NULL);
1220 	fprintf(debug_file, "\n");
1221 #endif
1222     }
1223     s2 = bmake_malloc(sizeof(Src));
1224     s2->file = 	    str_concat(targ->pref, s->name, 0);
1225     s2->pref =	    targ->pref;
1226     s2->parent =    targ;
1227     s2->node = 	    NULL;
1228     s2->suff = 	    s;
1229     s->refCount++;
1230     s2->children =  0;
1231     targ->children += 1;
1232     (void)Lst_AtEnd(ls->l, s2);
1233 #ifdef DEBUG_SRC
1234     s2->cp = Lst_Init(FALSE);
1235     Lst_AtEnd(targ->cp, s2);
1236     fprintf(debug_file, "2 add %x %x to %x:", targ, s2, ls->l);
1237     Lst_ForEach(ls->l, PrintAddr, NULL);
1238     fprintf(debug_file, "\n");
1239 #endif
1240 
1241     return(0);
1242 }
1243 
1244 /*-
1245  *-----------------------------------------------------------------------
1246  * SuffAddLevel  --
1247  *	Add all the children of targ as Src structures to the given list
1248  *
1249  * Input:
1250  *	l		list to which to add the new level
1251  *	targ		Src structure to use as the parent
1252  *
1253  * Results:
1254  *	None
1255  *
1256  * Side Effects:
1257  * 	Lots of structures are created and added to the list
1258  *-----------------------------------------------------------------------
1259  */
1260 static void
1261 SuffAddLevel(Lst l, Src *targ)
1262 {
1263     LstSrc         ls;
1264 
1265     ls.s = targ;
1266     ls.l = l;
1267 
1268     Lst_ForEach(targ->suff->children, SuffAddSrc, &ls);
1269 }
1270 
1271 /*-
1272  *----------------------------------------------------------------------
1273  * SuffRemoveSrc --
1274  *	Free all src structures in list that don't have a reference count
1275  *
1276  * Results:
1277  *	Ture if an src was removed
1278  *
1279  * Side Effects:
1280  *	The memory is free'd.
1281  *----------------------------------------------------------------------
1282  */
1283 static int
1284 SuffRemoveSrc(Lst l)
1285 {
1286     LstNode ln;
1287     Src *s;
1288     int t = 0;
1289 
1290     if (Lst_Open(l) == FAILURE) {
1291 	return 0;
1292     }
1293 #ifdef DEBUG_SRC
1294     fprintf(debug_file, "cleaning %lx: ", (unsigned long) l);
1295     Lst_ForEach(l, PrintAddr, NULL);
1296     fprintf(debug_file, "\n");
1297 #endif
1298 
1299 
1300     while ((ln = Lst_Next(l)) != NULL) {
1301 	s = (Src *)Lst_Datum(ln);
1302 	if (s->children == 0) {
1303 	    free(s->file);
1304 	    if (!s->parent)
1305 		free(s->pref);
1306 	    else {
1307 #ifdef DEBUG_SRC
1308 		LstNode ln = Lst_Member(s->parent->cp, s);
1309 		if (ln != NULL)
1310 		    Lst_Remove(s->parent->cp, ln);
1311 #endif
1312 		--s->parent->children;
1313 	    }
1314 #ifdef DEBUG_SRC
1315 	    fprintf(debug_file, "free: [l=%x] p=%x %d\n", l, s, s->children);
1316 	    Lst_Destroy(s->cp, NULL);
1317 #endif
1318 	    Lst_Remove(l, ln);
1319 	    free(s);
1320 	    t |= 1;
1321 	    Lst_Close(l);
1322 	    return TRUE;
1323 	}
1324 #ifdef DEBUG_SRC
1325 	else {
1326 	    fprintf(debug_file, "keep: [l=%x] p=%x %d: ", l, s, s->children);
1327 	    Lst_ForEach(s->cp, PrintAddr, NULL);
1328 	    fprintf(debug_file, "\n");
1329 	}
1330 #endif
1331     }
1332 
1333     Lst_Close(l);
1334 
1335     return t;
1336 }
1337 
1338 /*-
1339  *-----------------------------------------------------------------------
1340  * SuffFindThem --
1341  *	Find the first existing file/target in the list srcs
1342  *
1343  * Input:
1344  *	srcs		list of Src structures to search through
1345  *
1346  * Results:
1347  *	The lowest structure in the chain of transformations
1348  *
1349  * Side Effects:
1350  *	None
1351  *-----------------------------------------------------------------------
1352  */
1353 static Src *
1354 SuffFindThem(Lst srcs, Lst slst)
1355 {
1356     Src            *s;		/* current Src */
1357     Src		   *rs;		/* returned Src */
1358     char	   *ptr;
1359 
1360     rs = NULL;
1361 
1362     while (!Lst_IsEmpty (srcs)) {
1363 	s = (Src *)Lst_DeQueue(srcs);
1364 
1365 	if (DEBUG(SUFF)) {
1366 	    fprintf(debug_file, "\ttrying %s...", s->file);
1367 	}
1368 
1369 	/*
1370 	 * A file is considered to exist if either a node exists in the
1371 	 * graph for it or the file actually exists.
1372 	 */
1373 	if (Targ_FindNode(s->file, TARG_NOCREATE) != NULL) {
1374 #ifdef DEBUG_SRC
1375 	    fprintf(debug_file, "remove %x from %x\n", s, srcs);
1376 #endif
1377 	    rs = s;
1378 	    break;
1379 	}
1380 
1381 	if ((ptr = Dir_FindFile(s->file, s->suff->searchPath)) != NULL) {
1382 	    rs = s;
1383 #ifdef DEBUG_SRC
1384 	    fprintf(debug_file, "remove %x from %x\n", s, srcs);
1385 #endif
1386 	    free(ptr);
1387 	    break;
1388 	}
1389 
1390 	if (DEBUG(SUFF)) {
1391 	    fprintf(debug_file, "not there\n");
1392 	}
1393 
1394 	SuffAddLevel(srcs, s);
1395 	Lst_AtEnd(slst, s);
1396     }
1397 
1398     if (DEBUG(SUFF) && rs) {
1399 	fprintf(debug_file, "got it\n");
1400     }
1401     return (rs);
1402 }
1403 
1404 /*-
1405  *-----------------------------------------------------------------------
1406  * SuffFindCmds --
1407  *	See if any of the children of the target in the Src structure is
1408  *	one from which the target can be transformed. If there is one,
1409  *	a Src structure is put together for it and returned.
1410  *
1411  * Input:
1412  *	targ		Src structure to play with
1413  *
1414  * Results:
1415  *	The Src structure of the "winning" child, or NULL if no such beast.
1416  *
1417  * Side Effects:
1418  *	A Src structure may be allocated.
1419  *
1420  *-----------------------------------------------------------------------
1421  */
1422 static Src *
1423 SuffFindCmds(Src *targ, Lst slst)
1424 {
1425     LstNode 	  	ln; 	/* General-purpose list node */
1426     GNode		*t, 	/* Target GNode */
1427 	    	  	*s; 	/* Source GNode */
1428     int	    	  	prefLen;/* The length of the defined prefix */
1429     Suff    	  	*suff;	/* Suffix on matching beastie */
1430     Src	    	  	*ret;	/* Return value */
1431     char    	  	*cp;
1432 
1433     t = targ->node;
1434     (void)Lst_Open(t->children);
1435     prefLen = strlen(targ->pref);
1436 
1437     for (;;) {
1438 	ln = Lst_Next(t->children);
1439 	if (ln == NULL) {
1440 	    Lst_Close(t->children);
1441 	    return NULL;
1442 	}
1443 	s = (GNode *)Lst_Datum(ln);
1444 
1445 	if (s->type & OP_OPTIONAL && Lst_IsEmpty(t->commands)) {
1446 	    /*
1447 	     * We haven't looked to see if .OPTIONAL files exist yet, so
1448 	     * don't use one as the implicit source.
1449 	     * This allows us to use .OPTIONAL in .depend files so make won't
1450 	     * complain "don't know how to make xxx.h' when a dependent file
1451 	     * has been moved/deleted.
1452 	     */
1453 	    continue;
1454 	}
1455 
1456 	cp = strrchr(s->name, '/');
1457 	if (cp == NULL) {
1458 	    cp = s->name;
1459 	} else {
1460 	    cp++;
1461 	}
1462 	if (strncmp(cp, targ->pref, prefLen) != 0)
1463 	    continue;
1464 	/*
1465 	 * The node matches the prefix ok, see if it has a known
1466 	 * suffix.
1467 	 */
1468 	ln = Lst_Find(sufflist, &cp[prefLen], SuffSuffHasNameP);
1469 	if (ln == NULL)
1470 	    continue;
1471 	/*
1472 	 * It even has a known suffix, see if there's a transformation
1473 	 * defined between the node's suffix and the target's suffix.
1474 	 *
1475 	 * XXX: Handle multi-stage transformations here, too.
1476 	 */
1477 	suff = (Suff *)Lst_Datum(ln);
1478 
1479 	if (Lst_Member(suff->parents, targ->suff) != NULL)
1480 	    break;
1481     }
1482 
1483     /*
1484      * Hot Damn! Create a new Src structure to describe
1485      * this transformation (making sure to duplicate the
1486      * source node's name so Suff_FindDeps can free it
1487      * again (ick)), and return the new structure.
1488      */
1489     ret = bmake_malloc(sizeof(Src));
1490     ret->file = bmake_strdup(s->name);
1491     ret->pref = targ->pref;
1492     ret->suff = suff;
1493     suff->refCount++;
1494     ret->parent = targ;
1495     ret->node = s;
1496     ret->children = 0;
1497     targ->children += 1;
1498 #ifdef DEBUG_SRC
1499     ret->cp = Lst_Init(FALSE);
1500     fprintf(debug_file, "3 add %x %x\n", targ, ret);
1501     Lst_AtEnd(targ->cp, ret);
1502 #endif
1503     Lst_AtEnd(slst, ret);
1504     if (DEBUG(SUFF)) {
1505 	fprintf(debug_file, "\tusing existing source %s\n", s->name);
1506     }
1507     return (ret);
1508 }
1509 
1510 /*-
1511  *-----------------------------------------------------------------------
1512  * SuffExpandChildren --
1513  *	Expand the names of any children of a given node that contain
1514  *	variable invocations or file wildcards into actual targets.
1515  *
1516  * Input:
1517  *	cln		Child to examine
1518  *	pgn		Parent node being processed
1519  *
1520  * Results:
1521  *	=== 0 (continue)
1522  *
1523  * Side Effects:
1524  *	The expanded node is removed from the parent's list of children,
1525  *	and the parent's unmade counter is decremented, but other nodes
1526  * 	may be added.
1527  *
1528  *-----------------------------------------------------------------------
1529  */
1530 static void
1531 SuffExpandChildren(LstNode cln, GNode *pgn)
1532 {
1533     GNode   	*cgn = (GNode *)Lst_Datum(cln);
1534     GNode	*gn;	    /* New source 8) */
1535     char	*cp;	    /* Expanded value */
1536 
1537     if (!Lst_IsEmpty(cgn->order_pred) || !Lst_IsEmpty(cgn->order_succ))
1538 	/* It is all too hard to process the result of .ORDER */
1539 	return;
1540 
1541     if (cgn->type & OP_WAIT)
1542 	/* Ignore these (& OP_PHONY ?) */
1543 	return;
1544 
1545     /*
1546      * First do variable expansion -- this takes precedence over
1547      * wildcard expansion. If the result contains wildcards, they'll be gotten
1548      * to later since the resulting words are tacked on to the end of
1549      * the children list.
1550      */
1551     if (strchr(cgn->name, '$') == NULL) {
1552 	SuffExpandWildcards(cln, pgn);
1553 	return;
1554     }
1555 
1556     if (DEBUG(SUFF)) {
1557 	fprintf(debug_file, "Expanding \"%s\"...", cgn->name);
1558     }
1559     cp = Var_Subst(NULL, cgn->name, pgn, VARF_UNDEFERR|VARF_WANTRES);
1560 
1561     if (cp != NULL) {
1562 	Lst	    members = Lst_Init(FALSE);
1563 
1564 	if (cgn->type & OP_ARCHV) {
1565 	    /*
1566 	     * Node was an archive(member) target, so we want to call
1567 	     * on the Arch module to find the nodes for us, expanding
1568 	     * variables in the parent's context.
1569 	     */
1570 	    char	*sacrifice = cp;
1571 
1572 	    (void)Arch_ParseArchive(&sacrifice, members, pgn);
1573 	} else {
1574 	    /*
1575 	     * Break the result into a vector of strings whose nodes
1576 	     * we can find, then add those nodes to the members list.
1577 	     * Unfortunately, we can't use brk_string b/c it
1578 	     * doesn't understand about variable specifications with
1579 	     * spaces in them...
1580 	     */
1581 	    char	    *start;
1582 	    char	    *initcp = cp;   /* For freeing... */
1583 
1584 	    for (start = cp; *start == ' ' || *start == '\t'; start++)
1585 		continue;
1586 	    for (cp = start; *cp != '\0'; cp++) {
1587 		if (*cp == ' ' || *cp == '\t') {
1588 		    /*
1589 		     * White-space -- terminate element, find the node,
1590 		     * add it, skip any further spaces.
1591 		     */
1592 		    *cp++ = '\0';
1593 		    gn = Targ_FindNode(start, TARG_CREATE);
1594 		    (void)Lst_AtEnd(members, gn);
1595 		    while (*cp == ' ' || *cp == '\t') {
1596 			cp++;
1597 		    }
1598 		    /*
1599 		     * Adjust cp for increment at start of loop, but
1600 		     * set start to first non-space.
1601 		     */
1602 		    start = cp--;
1603 		} else if (*cp == '$') {
1604 		    /*
1605 		     * Start of a variable spec -- contact variable module
1606 		     * to find the end so we can skip over it.
1607 		     */
1608 		    char	*junk;
1609 		    int 	len;
1610 		    void	*freeIt;
1611 
1612 		    junk = Var_Parse(cp, pgn, VARF_UNDEFERR|VARF_WANTRES,
1613 			&len, &freeIt);
1614 		    if (junk != var_Error) {
1615 			cp += len - 1;
1616 		    }
1617 
1618 		    free(freeIt);
1619 		} else if (*cp == '\\' && *cp != '\0') {
1620 		    /*
1621 		     * Escaped something -- skip over it
1622 		     */
1623 		    cp++;
1624 		}
1625 	    }
1626 
1627 	    if (cp != start) {
1628 		/*
1629 		 * Stuff left over -- add it to the list too
1630 		 */
1631 		gn = Targ_FindNode(start, TARG_CREATE);
1632 		(void)Lst_AtEnd(members, gn);
1633 	    }
1634 	    /*
1635 	     * Point cp back at the beginning again so the variable value
1636 	     * can be freed.
1637 	     */
1638 	    cp = initcp;
1639 	}
1640 
1641 	/*
1642 	 * Add all elements of the members list to the parent node.
1643 	 */
1644 	while(!Lst_IsEmpty(members)) {
1645 	    gn = (GNode *)Lst_DeQueue(members);
1646 
1647 	    if (DEBUG(SUFF)) {
1648 		fprintf(debug_file, "%s...", gn->name);
1649 	    }
1650 	    /* Add gn to the parents child list before the original child */
1651 	    (void)Lst_InsertBefore(pgn->children, cln, gn);
1652 	    (void)Lst_AtEnd(gn->parents, pgn);
1653 	    pgn->unmade++;
1654 	    /* Expand wildcards on new node */
1655 	    SuffExpandWildcards(Lst_Prev(cln), pgn);
1656 	}
1657 	Lst_Destroy(members, NULL);
1658 
1659 	/*
1660 	 * Free the result
1661 	 */
1662 	free(cp);
1663     }
1664     if (DEBUG(SUFF)) {
1665 	fprintf(debug_file, "\n");
1666     }
1667 
1668     /*
1669      * Now the source is expanded, remove it from the list of children to
1670      * keep it from being processed.
1671      */
1672     pgn->unmade--;
1673     Lst_Remove(pgn->children, cln);
1674     Lst_Remove(cgn->parents, Lst_Member(cgn->parents, pgn));
1675 }
1676 
1677 static void
1678 SuffExpandWildcards(LstNode cln, GNode *pgn)
1679 {
1680     GNode   	*cgn = (GNode *)Lst_Datum(cln);
1681     GNode	*gn;	    /* New source 8) */
1682     char	*cp;	    /* Expanded value */
1683     Lst 	explist;    /* List of expansions */
1684 
1685     if (!Dir_HasWildcards(cgn->name))
1686 	return;
1687 
1688     /*
1689      * Expand the word along the chosen path
1690      */
1691     explist = Lst_Init(FALSE);
1692     Dir_Expand(cgn->name, Suff_FindPath(cgn), explist);
1693 
1694     while (!Lst_IsEmpty(explist)) {
1695 	/*
1696 	 * Fetch next expansion off the list and find its GNode
1697 	 */
1698 	cp = (char *)Lst_DeQueue(explist);
1699 
1700 	if (DEBUG(SUFF)) {
1701 	    fprintf(debug_file, "%s...", cp);
1702 	}
1703 	gn = Targ_FindNode(cp, TARG_CREATE);
1704 
1705 	/* Add gn to the parents child list before the original child */
1706 	(void)Lst_InsertBefore(pgn->children, cln, gn);
1707 	(void)Lst_AtEnd(gn->parents, pgn);
1708 	pgn->unmade++;
1709     }
1710 
1711     /*
1712      * Nuke what's left of the list
1713      */
1714     Lst_Destroy(explist, NULL);
1715 
1716     if (DEBUG(SUFF)) {
1717 	fprintf(debug_file, "\n");
1718     }
1719 
1720     /*
1721      * Now the source is expanded, remove it from the list of children to
1722      * keep it from being processed.
1723      */
1724     pgn->unmade--;
1725     Lst_Remove(pgn->children, cln);
1726     Lst_Remove(cgn->parents, Lst_Member(cgn->parents, pgn));
1727 }
1728 
1729 /*-
1730  *-----------------------------------------------------------------------
1731  * Suff_FindPath --
1732  *	Find a path along which to expand the node.
1733  *
1734  *	If the word has a known suffix, use that path.
1735  *	If it has no known suffix, use the default system search path.
1736  *
1737  * Input:
1738  *	gn		Node being examined
1739  *
1740  * Results:
1741  *	The appropriate path to search for the GNode.
1742  *
1743  * Side Effects:
1744  *	XXX: We could set the suffix here so that we don't have to scan
1745  *	again.
1746  *
1747  *-----------------------------------------------------------------------
1748  */
1749 Lst
1750 Suff_FindPath(GNode* gn)
1751 {
1752     Suff *suff = gn->suffix;
1753 
1754     if (suff == NULL) {
1755 	SuffixCmpData sd;   /* Search string data */
1756 	LstNode ln;
1757 	sd.len = strlen(gn->name);
1758 	sd.ename = gn->name + sd.len;
1759 	ln = Lst_Find(sufflist, &sd, SuffSuffIsSuffixP);
1760 
1761 	if (DEBUG(SUFF)) {
1762 	    fprintf(debug_file, "Wildcard expanding \"%s\"...", gn->name);
1763 	}
1764 	if (ln != NULL)
1765 	    suff = (Suff *)Lst_Datum(ln);
1766 	/* XXX: Here we can save the suffix so we don't have to do this again */
1767     }
1768 
1769     if (suff != NULL) {
1770 	if (DEBUG(SUFF)) {
1771 	    fprintf(debug_file, "suffix is \"%s\"...", suff->name);
1772 	}
1773 	return suff->searchPath;
1774     } else {
1775 	/*
1776 	 * Use default search path
1777 	 */
1778 	return dirSearchPath;
1779     }
1780 }
1781 
1782 /*-
1783  *-----------------------------------------------------------------------
1784  * SuffApplyTransform --
1785  *	Apply a transformation rule, given the source and target nodes
1786  *	and suffixes.
1787  *
1788  * Input:
1789  *	tGn		Target node
1790  *	sGn		Source node
1791  *	t		Target suffix
1792  *	s		Source suffix
1793  *
1794  * Results:
1795  *	TRUE if successful, FALSE if not.
1796  *
1797  * Side Effects:
1798  *	The source and target are linked and the commands from the
1799  *	transformation are added to the target node's commands list.
1800  *	All attributes but OP_DEPMASK and OP_TRANSFORM are applied
1801  *	to the target. The target also inherits all the sources for
1802  *	the transformation rule.
1803  *
1804  *-----------------------------------------------------------------------
1805  */
1806 static Boolean
1807 SuffApplyTransform(GNode *tGn, GNode *sGn, Suff *t, Suff *s)
1808 {
1809     LstNode 	ln, nln;    /* General node */
1810     char    	*tname;	    /* Name of transformation rule */
1811     GNode   	*gn;	    /* Node for same */
1812 
1813     /*
1814      * Form the proper links between the target and source.
1815      */
1816     (void)Lst_AtEnd(tGn->children, sGn);
1817     (void)Lst_AtEnd(sGn->parents, tGn);
1818     tGn->unmade += 1;
1819 
1820     /*
1821      * Locate the transformation rule itself
1822      */
1823     tname = str_concat(s->name, t->name, 0);
1824     ln = Lst_Find(transforms, tname, SuffGNHasNameP);
1825     free(tname);
1826 
1827     if (ln == NULL) {
1828 	/*
1829 	 * Not really such a transformation rule (can happen when we're
1830 	 * called to link an OP_MEMBER and OP_ARCHV node), so return
1831 	 * FALSE.
1832 	 */
1833 	return(FALSE);
1834     }
1835 
1836     gn = (GNode *)Lst_Datum(ln);
1837 
1838     if (DEBUG(SUFF)) {
1839 	fprintf(debug_file, "\tapplying %s -> %s to \"%s\"\n", s->name, t->name, tGn->name);
1840     }
1841 
1842     /*
1843      * Record last child for expansion purposes
1844      */
1845     ln = Lst_Last(tGn->children);
1846 
1847     /*
1848      * Pass the buck to Make_HandleUse to apply the rule
1849      */
1850     (void)Make_HandleUse(gn, tGn);
1851 
1852     /*
1853      * Deal with wildcards and variables in any acquired sources
1854      */
1855     for (ln = Lst_Succ(ln); ln != NULL; ln = nln) {
1856 	nln = Lst_Succ(ln);
1857 	SuffExpandChildren(ln, tGn);
1858     }
1859 
1860     /*
1861      * Keep track of another parent to which this beast is transformed so
1862      * the .IMPSRC variable can be set correctly for the parent.
1863      */
1864     (void)Lst_AtEnd(sGn->iParents, tGn);
1865 
1866     return(TRUE);
1867 }
1868 
1869 
1870 /*-
1871  *-----------------------------------------------------------------------
1872  * SuffFindArchiveDeps --
1873  *	Locate dependencies for an OP_ARCHV node.
1874  *
1875  * Input:
1876  *	gn		Node for which to locate dependencies
1877  *
1878  * Results:
1879  *	None
1880  *
1881  * Side Effects:
1882  *	Same as Suff_FindDeps
1883  *
1884  *-----------------------------------------------------------------------
1885  */
1886 static void
1887 SuffFindArchiveDeps(GNode *gn, Lst slst)
1888 {
1889     char    	*eoarch;    /* End of archive portion */
1890     char    	*eoname;    /* End of member portion */
1891     GNode   	*mem;	    /* Node for member */
1892     static const char	*copy[] = {
1893 	/* Variables to be copied from the member node */
1894 	TARGET,	    	    /* Must be first */
1895 	PREFIX,	    	    /* Must be second */
1896     };
1897     int	    	i;  	    /* Index into copy and vals */
1898     Suff    	*ms;	    /* Suffix descriptor for member */
1899     char    	*name;	    /* Start of member's name */
1900 
1901     /*
1902      * The node is an archive(member) pair. so we must find a
1903      * suffix for both of them.
1904      */
1905     eoarch = strchr(gn->name, '(');
1906     eoname = strchr(eoarch, ')');
1907 
1908     *eoname = '\0';	  /* Nuke parentheses during suffix search */
1909     *eoarch = '\0';	  /* So a suffix can be found */
1910 
1911     name = eoarch + 1;
1912 
1913     /*
1914      * To simplify things, call Suff_FindDeps recursively on the member now,
1915      * so we can simply compare the member's .PREFIX and .TARGET variables
1916      * to locate its suffix. This allows us to figure out the suffix to
1917      * use for the archive without having to do a quadratic search over the
1918      * suffix list, backtracking for each one...
1919      */
1920     mem = Targ_FindNode(name, TARG_CREATE);
1921     SuffFindDeps(mem, slst);
1922 
1923     /*
1924      * Create the link between the two nodes right off
1925      */
1926     (void)Lst_AtEnd(gn->children, mem);
1927     (void)Lst_AtEnd(mem->parents, gn);
1928     gn->unmade += 1;
1929 
1930     /*
1931      * Copy in the variables from the member node to this one.
1932      */
1933     for (i = (sizeof(copy)/sizeof(copy[0]))-1; i >= 0; i--) {
1934 	char *p1;
1935 	Var_Set(copy[i], Var_Value(copy[i], mem, &p1), gn, 0);
1936 	free(p1);
1937 
1938     }
1939 
1940     ms = mem->suffix;
1941     if (ms == NULL) {
1942 	/*
1943 	 * Didn't know what it was -- use .NULL suffix if not in make mode
1944 	 */
1945 	if (DEBUG(SUFF)) {
1946 	    fprintf(debug_file, "using null suffix\n");
1947 	}
1948 	ms = suffNull;
1949     }
1950 
1951 
1952     /*
1953      * Set the other two local variables required for this target.
1954      */
1955     Var_Set(MEMBER, name, gn, 0);
1956     Var_Set(ARCHIVE, gn->name, gn, 0);
1957 
1958     if (ms != NULL) {
1959 	/*
1960 	 * Member has a known suffix, so look for a transformation rule from
1961 	 * it to a possible suffix of the archive. Rather than searching
1962 	 * through the entire list, we just look at suffixes to which the
1963 	 * member's suffix may be transformed...
1964 	 */
1965 	LstNode		ln;
1966 	SuffixCmpData	sd;		/* Search string data */
1967 
1968 	/*
1969 	 * Use first matching suffix...
1970 	 */
1971 	sd.len = eoarch - gn->name;
1972 	sd.ename = eoarch;
1973 	ln = Lst_Find(ms->parents, &sd, SuffSuffIsSuffixP);
1974 
1975 	if (ln != NULL) {
1976 	    /*
1977 	     * Got one -- apply it
1978 	     */
1979 	    if (!SuffApplyTransform(gn, mem, (Suff *)Lst_Datum(ln), ms) &&
1980 		DEBUG(SUFF))
1981 	    {
1982 		fprintf(debug_file, "\tNo transformation from %s -> %s\n",
1983 		       ms->name, ((Suff *)Lst_Datum(ln))->name);
1984 	    }
1985 	}
1986     }
1987 
1988     /*
1989      * Replace the opening and closing parens now we've no need of the separate
1990      * pieces.
1991      */
1992     *eoarch = '('; *eoname = ')';
1993 
1994     /*
1995      * Pretend gn appeared to the left of a dependency operator so
1996      * the user needn't provide a transformation from the member to the
1997      * archive.
1998      */
1999     if (OP_NOP(gn->type)) {
2000 	gn->type |= OP_DEPENDS;
2001     }
2002 
2003     /*
2004      * Flag the member as such so we remember to look in the archive for
2005      * its modification time.
2006      */
2007     mem->type |= OP_MEMBER;
2008 }
2009 
2010 /*-
2011  *-----------------------------------------------------------------------
2012  * SuffFindNormalDeps --
2013  *	Locate implicit dependencies for regular targets.
2014  *
2015  * Input:
2016  *	gn		Node for which to find sources
2017  *
2018  * Results:
2019  *	None.
2020  *
2021  * Side Effects:
2022  *	Same as Suff_FindDeps...
2023  *
2024  *-----------------------------------------------------------------------
2025  */
2026 static void
2027 SuffFindNormalDeps(GNode *gn, Lst slst)
2028 {
2029     char    	*eoname;    /* End of name */
2030     char    	*sopref;    /* Start of prefix */
2031     LstNode 	ln, nln;    /* Next suffix node to check */
2032     Lst	    	srcs;	    /* List of sources at which to look */
2033     Lst	    	targs;	    /* List of targets to which things can be
2034 			     * transformed. They all have the same file,
2035 			     * but different suff and pref fields */
2036     Src	    	*bottom;    /* Start of found transformation path */
2037     Src 	*src;	    /* General Src pointer */
2038     char    	*pref;	    /* Prefix to use */
2039     Src	    	*targ;	    /* General Src target pointer */
2040     SuffixCmpData sd;	    /* Search string data */
2041 
2042 
2043     sd.len = strlen(gn->name);
2044     sd.ename = eoname = gn->name + sd.len;
2045 
2046     sopref = gn->name;
2047 
2048     /*
2049      * Begin at the beginning...
2050      */
2051     ln = Lst_First(sufflist);
2052     srcs = Lst_Init(FALSE);
2053     targs = Lst_Init(FALSE);
2054 
2055     /*
2056      * We're caught in a catch-22 here. On the one hand, we want to use any
2057      * transformation implied by the target's sources, but we can't examine
2058      * the sources until we've expanded any variables/wildcards they may hold,
2059      * and we can't do that until we've set up the target's local variables
2060      * and we can't do that until we know what the proper suffix for the
2061      * target is (in case there are two suffixes one of which is a suffix of
2062      * the other) and we can't know that until we've found its implied
2063      * source, which we may not want to use if there's an existing source
2064      * that implies a different transformation.
2065      *
2066      * In an attempt to get around this, which may not work all the time,
2067      * but should work most of the time, we look for implied sources first,
2068      * checking transformations to all possible suffixes of the target,
2069      * use what we find to set the target's local variables, expand the
2070      * children, then look for any overriding transformations they imply.
2071      * Should we find one, we discard the one we found before.
2072      */
2073     bottom = NULL;
2074     targ = NULL;
2075 
2076     if (!(gn->type & OP_PHONY)) {
2077 
2078 	while (ln != NULL) {
2079 	    /*
2080 	     * Look for next possible suffix...
2081 	     */
2082 	    ln = Lst_FindFrom(sufflist, ln, &sd, SuffSuffIsSuffixP);
2083 
2084 	    if (ln != NULL) {
2085 		int	    prefLen;	    /* Length of the prefix */
2086 
2087 		/*
2088 		 * Allocate a Src structure to which things can be transformed
2089 		 */
2090 		targ = bmake_malloc(sizeof(Src));
2091 		targ->file = bmake_strdup(gn->name);
2092 		targ->suff = (Suff *)Lst_Datum(ln);
2093 		targ->suff->refCount++;
2094 		targ->node = gn;
2095 		targ->parent = NULL;
2096 		targ->children = 0;
2097 #ifdef DEBUG_SRC
2098 		targ->cp = Lst_Init(FALSE);
2099 #endif
2100 
2101 		/*
2102 		 * Allocate room for the prefix, whose end is found by
2103 		 * subtracting the length of the suffix from
2104 		 * the end of the name.
2105 		 */
2106 		prefLen = (eoname - targ->suff->nameLen) - sopref;
2107 		targ->pref = bmake_malloc(prefLen + 1);
2108 		memcpy(targ->pref, sopref, prefLen);
2109 		targ->pref[prefLen] = '\0';
2110 
2111 		/*
2112 		 * Add nodes from which the target can be made
2113 		 */
2114 		SuffAddLevel(srcs, targ);
2115 
2116 		/*
2117 		 * Record the target so we can nuke it
2118 		 */
2119 		(void)Lst_AtEnd(targs, targ);
2120 
2121 		/*
2122 		 * Search from this suffix's successor...
2123 		 */
2124 		ln = Lst_Succ(ln);
2125 	    }
2126 	}
2127 
2128 	/*
2129 	 * Handle target of unknown suffix...
2130 	 */
2131 	if (Lst_IsEmpty(targs) && suffNull != NULL) {
2132 	    if (DEBUG(SUFF)) {
2133 		fprintf(debug_file, "\tNo known suffix on %s. Using .NULL suffix\n", gn->name);
2134 	    }
2135 
2136 	    targ = bmake_malloc(sizeof(Src));
2137 	    targ->file = bmake_strdup(gn->name);
2138 	    targ->suff = suffNull;
2139 	    targ->suff->refCount++;
2140 	    targ->node = gn;
2141 	    targ->parent = NULL;
2142 	    targ->children = 0;
2143 	    targ->pref = bmake_strdup(sopref);
2144 #ifdef DEBUG_SRC
2145 	    targ->cp = Lst_Init(FALSE);
2146 #endif
2147 
2148 	    /*
2149 	     * Only use the default suffix rules if we don't have commands
2150 	     * defined for this gnode; traditional make programs used to
2151 	     * not define suffix rules if the gnode had children but we
2152 	     * don't do this anymore.
2153 	     */
2154 	    if (Lst_IsEmpty(gn->commands))
2155 		SuffAddLevel(srcs, targ);
2156 	    else {
2157 		if (DEBUG(SUFF))
2158 		    fprintf(debug_file, "not ");
2159 	    }
2160 
2161 	    if (DEBUG(SUFF))
2162 		fprintf(debug_file, "adding suffix rules\n");
2163 
2164 	    (void)Lst_AtEnd(targs, targ);
2165 	}
2166 
2167 	/*
2168 	 * Using the list of possible sources built up from the target
2169 	 * suffix(es), try and find an existing file/target that matches.
2170 	 */
2171 	bottom = SuffFindThem(srcs, slst);
2172 
2173 	if (bottom == NULL) {
2174 	    /*
2175 	     * No known transformations -- use the first suffix found
2176 	     * for setting the local variables.
2177 	     */
2178 	    if (!Lst_IsEmpty(targs)) {
2179 		targ = (Src *)Lst_Datum(Lst_First(targs));
2180 	    } else {
2181 		targ = NULL;
2182 	    }
2183 	} else {
2184 	    /*
2185 	     * Work up the transformation path to find the suffix of the
2186 	     * target to which the transformation was made.
2187 	     */
2188 	    for (targ = bottom; targ->parent != NULL; targ = targ->parent)
2189 		continue;
2190 	}
2191     }
2192 
2193     Var_Set(TARGET, gn->path ? gn->path : gn->name, gn, 0);
2194 
2195     pref = (targ != NULL) ? targ->pref : gn->name;
2196     Var_Set(PREFIX, pref, gn, 0);
2197 
2198     /*
2199      * Now we've got the important local variables set, expand any sources
2200      * that still contain variables or wildcards in their names.
2201      */
2202     for (ln = Lst_First(gn->children); ln != NULL; ln = nln) {
2203 	nln = Lst_Succ(ln);
2204 	SuffExpandChildren(ln, gn);
2205     }
2206 
2207     if (targ == NULL) {
2208 	if (DEBUG(SUFF)) {
2209 	    fprintf(debug_file, "\tNo valid suffix on %s\n", gn->name);
2210 	}
2211 
2212 sfnd_abort:
2213 	/*
2214 	 * Deal with finding the thing on the default search path. We
2215 	 * always do that, not only if the node is only a source (not
2216 	 * on the lhs of a dependency operator or [XXX] it has neither
2217 	 * children or commands) as the old pmake did.
2218 	 */
2219 	if ((gn->type & (OP_PHONY|OP_NOPATH)) == 0) {
2220 	    free(gn->path);
2221 	    gn->path = Dir_FindFile(gn->name,
2222 				    (targ == NULL ? dirSearchPath :
2223 				     targ->suff->searchPath));
2224 	    if (gn->path != NULL) {
2225 		char *ptr;
2226 		Var_Set(TARGET, gn->path, gn, 0);
2227 
2228 		if (targ != NULL) {
2229 		    /*
2230 		     * Suffix known for the thing -- trim the suffix off
2231 		     * the path to form the proper .PREFIX variable.
2232 		     */
2233 		    int     savep = strlen(gn->path) - targ->suff->nameLen;
2234 		    char    savec;
2235 
2236 		    if (gn->suffix)
2237 			gn->suffix->refCount--;
2238 		    gn->suffix = targ->suff;
2239 		    gn->suffix->refCount++;
2240 
2241 		    savec = gn->path[savep];
2242 		    gn->path[savep] = '\0';
2243 
2244 		    if ((ptr = strrchr(gn->path, '/')) != NULL)
2245 			ptr++;
2246 		    else
2247 			ptr = gn->path;
2248 
2249 		    Var_Set(PREFIX, ptr, gn, 0);
2250 
2251 		    gn->path[savep] = savec;
2252 		} else {
2253 		    /*
2254 		     * The .PREFIX gets the full path if the target has
2255 		     * no known suffix.
2256 		     */
2257 		    if (gn->suffix)
2258 			gn->suffix->refCount--;
2259 		    gn->suffix = NULL;
2260 
2261 		    if ((ptr = strrchr(gn->path, '/')) != NULL)
2262 			ptr++;
2263 		    else
2264 			ptr = gn->path;
2265 
2266 		    Var_Set(PREFIX, ptr, gn, 0);
2267 		}
2268 	    }
2269 	}
2270 
2271 	goto sfnd_return;
2272     }
2273 
2274     /*
2275      * If the suffix indicates that the target is a library, mark that in
2276      * the node's type field.
2277      */
2278     if (targ->suff->flags & SUFF_LIBRARY) {
2279 	gn->type |= OP_LIB;
2280     }
2281 
2282     /*
2283      * Check for overriding transformation rule implied by sources
2284      */
2285     if (!Lst_IsEmpty(gn->children)) {
2286 	src = SuffFindCmds(targ, slst);
2287 
2288 	if (src != NULL) {
2289 	    /*
2290 	     * Free up all the Src structures in the transformation path
2291 	     * up to, but not including, the parent node.
2292 	     */
2293 	    while (bottom && bottom->parent != NULL) {
2294 		if (Lst_Member(slst, bottom) == NULL) {
2295 		    Lst_AtEnd(slst, bottom);
2296 		}
2297 		bottom = bottom->parent;
2298 	    }
2299 	    bottom = src;
2300 	}
2301     }
2302 
2303     if (bottom == NULL) {
2304 	/*
2305 	 * No idea from where it can come -- return now.
2306 	 */
2307 	goto sfnd_abort;
2308     }
2309 
2310     /*
2311      * We now have a list of Src structures headed by 'bottom' and linked via
2312      * their 'parent' pointers. What we do next is create links between
2313      * source and target nodes (which may or may not have been created)
2314      * and set the necessary local variables in each target. The
2315      * commands for each target are set from the commands of the
2316      * transformation rule used to get from the src suffix to the targ
2317      * suffix. Note that this causes the commands list of the original
2318      * node, gn, to be replaced by the commands of the final
2319      * transformation rule. Also, the unmade field of gn is incremented.
2320      * Etc.
2321      */
2322     if (bottom->node == NULL) {
2323 	bottom->node = Targ_FindNode(bottom->file, TARG_CREATE);
2324     }
2325 
2326     for (src = bottom; src->parent != NULL; src = src->parent) {
2327 	targ = src->parent;
2328 
2329 	if (src->node->suffix)
2330 	    src->node->suffix->refCount--;
2331 	src->node->suffix = src->suff;
2332 	src->node->suffix->refCount++;
2333 
2334 	if (targ->node == NULL) {
2335 	    targ->node = Targ_FindNode(targ->file, TARG_CREATE);
2336 	}
2337 
2338 	SuffApplyTransform(targ->node, src->node,
2339 			   targ->suff, src->suff);
2340 
2341 	if (targ->node != gn) {
2342 	    /*
2343 	     * Finish off the dependency-search process for any nodes
2344 	     * between bottom and gn (no point in questing around the
2345 	     * filesystem for their implicit source when it's already
2346 	     * known). Note that the node can't have any sources that
2347 	     * need expanding, since SuffFindThem will stop on an existing
2348 	     * node, so all we need to do is set the standard and System V
2349 	     * variables.
2350 	     */
2351 	    targ->node->type |= OP_DEPS_FOUND;
2352 
2353 	    Var_Set(PREFIX, targ->pref, targ->node, 0);
2354 
2355 	    Var_Set(TARGET, targ->node->name, targ->node, 0);
2356 	}
2357     }
2358 
2359     if (gn->suffix)
2360 	gn->suffix->refCount--;
2361     gn->suffix = src->suff;
2362     gn->suffix->refCount++;
2363 
2364     /*
2365      * Nuke the transformation path and the Src structures left over in the
2366      * two lists.
2367      */
2368 sfnd_return:
2369     if (bottom)
2370 	if (Lst_Member(slst, bottom) == NULL)
2371 	    Lst_AtEnd(slst, bottom);
2372 
2373     while (SuffRemoveSrc(srcs) || SuffRemoveSrc(targs))
2374 	continue;
2375 
2376     Lst_Concat(slst, srcs, LST_CONCLINK);
2377     Lst_Concat(slst, targs, LST_CONCLINK);
2378 }
2379 
2380 
2381 /*-
2382  *-----------------------------------------------------------------------
2383  * Suff_FindDeps  --
2384  *	Find implicit sources for the target described by the graph node
2385  *	gn
2386  *
2387  * Results:
2388  *	Nothing.
2389  *
2390  * Side Effects:
2391  *	Nodes are added to the graph below the passed-in node. The nodes
2392  *	are marked to have their IMPSRC variable filled in. The
2393  *	PREFIX variable is set for the given node and all its
2394  *	implied children.
2395  *
2396  * Notes:
2397  *	The path found by this target is the shortest path in the
2398  *	transformation graph, which may pass through non-existent targets,
2399  *	to an existing target. The search continues on all paths from the
2400  *	root suffix until a file is found. I.e. if there's a path
2401  *	.o -> .c -> .l -> .l,v from the root and the .l,v file exists but
2402  *	the .c and .l files don't, the search will branch out in
2403  *	all directions from .o and again from all the nodes on the
2404  *	next level until the .l,v node is encountered.
2405  *
2406  *-----------------------------------------------------------------------
2407  */
2408 
2409 void
2410 Suff_FindDeps(GNode *gn)
2411 {
2412 
2413     SuffFindDeps(gn, srclist);
2414     while (SuffRemoveSrc(srclist))
2415 	continue;
2416 }
2417 
2418 
2419 /*
2420  * Input:
2421  *	gn		node we're dealing with
2422  *
2423  */
2424 static void
2425 SuffFindDeps(GNode *gn, Lst slst)
2426 {
2427     if (gn->type & OP_DEPS_FOUND) {
2428 	/*
2429 	 * If dependencies already found, no need to do it again...
2430 	 */
2431 	return;
2432     } else {
2433 	gn->type |= OP_DEPS_FOUND;
2434     }
2435     /*
2436      * Make sure we have these set, may get revised below.
2437      */
2438     Var_Set(TARGET, gn->path ? gn->path : gn->name, gn, 0);
2439     Var_Set(PREFIX, gn->name, gn, 0);
2440 
2441     if (DEBUG(SUFF)) {
2442 	fprintf(debug_file, "SuffFindDeps (%s)\n", gn->name);
2443     }
2444 
2445     if (gn->type & OP_ARCHV) {
2446 	SuffFindArchiveDeps(gn, slst);
2447     } else if (gn->type & OP_LIB) {
2448 	/*
2449 	 * If the node is a library, it is the arch module's job to find it
2450 	 * and set the TARGET variable accordingly. We merely provide the
2451 	 * search path, assuming all libraries end in ".a" (if the suffix
2452 	 * hasn't been defined, there's nothing we can do for it, so we just
2453 	 * set the TARGET variable to the node's name in order to give it a
2454 	 * value).
2455 	 */
2456 	LstNode	ln;
2457 	Suff	*s;
2458 
2459 	ln = Lst_Find(sufflist, LIBSUFF, SuffSuffHasNameP);
2460 	if (gn->suffix)
2461 	    gn->suffix->refCount--;
2462 	if (ln != NULL) {
2463 	    gn->suffix = s = (Suff *)Lst_Datum(ln);
2464 	    gn->suffix->refCount++;
2465 	    Arch_FindLib(gn, s->searchPath);
2466 	} else {
2467 	    gn->suffix = NULL;
2468 	    Var_Set(TARGET, gn->name, gn, 0);
2469 	}
2470 	/*
2471 	 * Because a library (-lfoo) target doesn't follow the standard
2472 	 * filesystem conventions, we don't set the regular variables for
2473 	 * the thing. .PREFIX is simply made empty...
2474 	 */
2475 	Var_Set(PREFIX, "", gn, 0);
2476     } else {
2477 	SuffFindNormalDeps(gn, slst);
2478     }
2479 }
2480 
2481 /*-
2482  *-----------------------------------------------------------------------
2483  * Suff_SetNull --
2484  *	Define which suffix is the null suffix.
2485  *
2486  * Input:
2487  *	name		Name of null suffix
2488  *
2489  * Results:
2490  *	None.
2491  *
2492  * Side Effects:
2493  *	'suffNull' is altered.
2494  *
2495  * Notes:
2496  *	Need to handle the changing of the null suffix gracefully so the
2497  *	old transformation rules don't just go away.
2498  *
2499  *-----------------------------------------------------------------------
2500  */
2501 void
2502 Suff_SetNull(char *name)
2503 {
2504     Suff    *s;
2505     LstNode ln;
2506 
2507     ln = Lst_Find(sufflist, name, SuffSuffHasNameP);
2508     if (ln != NULL) {
2509 	s = (Suff *)Lst_Datum(ln);
2510 	if (suffNull != NULL) {
2511 	    suffNull->flags &= ~SUFF_NULL;
2512 	}
2513 	s->flags |= SUFF_NULL;
2514 	/*
2515 	 * XXX: Here's where the transformation mangling would take place
2516 	 */
2517 	suffNull = s;
2518     } else {
2519 	Parse_Error(PARSE_WARNING, "Desired null suffix %s not defined.",
2520 		     name);
2521     }
2522 }
2523 
2524 /*-
2525  *-----------------------------------------------------------------------
2526  * Suff_Init --
2527  *	Initialize suffixes module
2528  *
2529  * Results:
2530  *	None
2531  *
2532  * Side Effects:
2533  *	Many
2534  *-----------------------------------------------------------------------
2535  */
2536 void
2537 Suff_Init(void)
2538 {
2539 #ifdef CLEANUP
2540     suffClean = Lst_Init(FALSE);
2541 #endif
2542     srclist = Lst_Init(FALSE);
2543     transforms = Lst_Init(FALSE);
2544 
2545     /*
2546      * Create null suffix for single-suffix rules (POSIX). The thing doesn't
2547      * actually go on the suffix list or everyone will think that's its
2548      * suffix.
2549      */
2550     Suff_ClearSuffixes();
2551 }
2552 
2553 
2554 /*-
2555  *----------------------------------------------------------------------
2556  * Suff_End --
2557  *	Cleanup the this module
2558  *
2559  * Results:
2560  *	None
2561  *
2562  * Side Effects:
2563  *	The memory is free'd.
2564  *----------------------------------------------------------------------
2565  */
2566 
2567 void
2568 Suff_End(void)
2569 {
2570 #ifdef CLEANUP
2571     Lst_Destroy(sufflist, SuffFree);
2572     Lst_Destroy(suffClean, SuffFree);
2573     if (suffNull)
2574 	SuffFree(suffNull);
2575     Lst_Destroy(srclist, NULL);
2576     Lst_Destroy(transforms, NULL);
2577 #endif
2578 }
2579 
2580 
2581 /********************* DEBUGGING FUNCTIONS **********************/
2582 
2583 static int SuffPrintName(void *s, void *dummy)
2584 {
2585     fprintf(debug_file, "%s ", ((Suff *)s)->name);
2586     return (dummy ? 0 : 0);
2587 }
2588 
2589 static int
2590 SuffPrintSuff(void *sp, void *dummy)
2591 {
2592     Suff    *s = (Suff *)sp;
2593     int	    flags;
2594     int	    flag;
2595 
2596     fprintf(debug_file, "# `%s' [%d] ", s->name, s->refCount);
2597 
2598     flags = s->flags;
2599     if (flags) {
2600 	fputs(" (", debug_file);
2601 	while (flags) {
2602 	    flag = 1 << (ffs(flags) - 1);
2603 	    flags &= ~flag;
2604 	    switch (flag) {
2605 		case SUFF_NULL:
2606 		    fprintf(debug_file, "NULL");
2607 		    break;
2608 		case SUFF_INCLUDE:
2609 		    fprintf(debug_file, "INCLUDE");
2610 		    break;
2611 		case SUFF_LIBRARY:
2612 		    fprintf(debug_file, "LIBRARY");
2613 		    break;
2614 	    }
2615 	    fputc(flags ? '|' : ')', debug_file);
2616 	}
2617     }
2618     fputc('\n', debug_file);
2619     fprintf(debug_file, "#\tTo: ");
2620     Lst_ForEach(s->parents, SuffPrintName, NULL);
2621     fputc('\n', debug_file);
2622     fprintf(debug_file, "#\tFrom: ");
2623     Lst_ForEach(s->children, SuffPrintName, NULL);
2624     fputc('\n', debug_file);
2625     fprintf(debug_file, "#\tSearch Path: ");
2626     Dir_PrintPath(s->searchPath);
2627     fputc('\n', debug_file);
2628     return (dummy ? 0 : 0);
2629 }
2630 
2631 static int
2632 SuffPrintTrans(void *tp, void *dummy)
2633 {
2634     GNode   *t = (GNode *)tp;
2635 
2636     fprintf(debug_file, "%-16s: ", t->name);
2637     Targ_PrintType(t->type);
2638     fputc('\n', debug_file);
2639     Lst_ForEach(t->commands, Targ_PrintCmd, NULL);
2640     fputc('\n', debug_file);
2641     return(dummy ? 0 : 0);
2642 }
2643 
2644 void
2645 Suff_PrintAll(void)
2646 {
2647     fprintf(debug_file, "#*** Suffixes:\n");
2648     Lst_ForEach(sufflist, SuffPrintSuff, NULL);
2649 
2650     fprintf(debug_file, "#*** Transformations:\n");
2651     Lst_ForEach(transforms, SuffPrintTrans, NULL);
2652 }
2653