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