1/*	$OpenBSD: suff.c,v 1.103 2023/09/04 11:35:11 espie Exp $ */
2/*	$NetBSD: suff.c,v 1.13 1996/11/06 17:59:25 christos Exp $	*/
3
4/*
5 * Copyright (c) 1988, 1989, 1990, 1993
6 *	The Regents of the University of California.  All rights reserved.
7 * Copyright (c) 1989 by Berkeley Softworks
8 * All rights reserved.
9 *
10 * This code is derived from software contributed to Berkeley by
11 * Adam de Boor.
12 *
13 * Redistribution and use in source and binary forms, with or without
14 * modification, are permitted provided that the following conditions
15 * are met:
16 * 1. Redistributions of source code must retain the above copyright
17 *    notice, this list of conditions and the following disclaimer.
18 * 2. Redistributions in binary form must reproduce the above copyright
19 *    notice, this list of conditions and the following disclaimer in the
20 *    documentation and/or other materials provided with the distribution.
21 * 3. Neither the name of the University nor the names of its contributors
22 *    may be used to endorse or promote products derived from this software
23 *    without specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35 * SUCH DAMAGE.
36 */
37
38/*-
39 * suff.c --
40 *	Functions to maintain suffix lists and find implicit dependents
41 *	using suffix transformation rules
42 */
43
44#include <ctype.h>
45#include <stddef.h>
46#include <stdint.h>
47#include <stdio.h>
48#include <stdlib.h>
49#include <string.h>
50#include <ohash.h>
51#include "defines.h"
52#include "dir.h"
53#include "engine.h"
54#include "suff.h"
55#include "var.h"
56#include "targ.h"
57#include "error.h"
58#include "str.h"
59#include "lst.h"
60#include "memory.h"
61#include "gnode.h"
62#include "stats.h"
63#include "dump.h"
64#include "expandchildren.h"
65
66/* XXX the suffixes hash is stored using a specific hash function, suitable
67 * for looking up suffixes in reverse.
68 */
69static struct ohash suffixes;
70
71/* We remember the longest suffix, so we don't need to look beyond that.  */
72size_t maxLen = 0U;
73static LIST srclist;
74
75/* Transforms (.c.o) are stored in another hash, independently from suffixes.
76 * When make sees a target, it checks whether it's currently parsable as a
77 * transform (according to the active suffixes). If yes, it's stored as a
78 * new transform.
79 *
80 * XXX
81 * But transforms DO NOT have a canonical decomposition as a set of suffixes,
82 * and will be used as necessary later, when looking up implicit rules for
83 * actual targets.
84 *
85 * For instance, a transform .a.b.c  can be parsed as .a -> .b.c if suffixes
86 * .a and .b.c are active, and then LATER, reused as .a.b -> .c if suffixes
87 * .a.b and .c are active.
88 */
89static struct ohash transforms;
90
91/* conflicts between suffixes are solved by suffix declaration order. */
92static int order = 0;
93
94/*
95 * Structure describing an individual suffix.
96 */
97struct Suff_ {
98	size_t nameLen;		/* optimisation: strlen(name) */
99	short flags;
100#define SUFF_ACTIVE	  0x08	/* We never destroy suffixes and rules, */
101				/* we just deactivate them. */
102#define SUFF_PATH	  0x10	/* False suffix: actually, the path keyword */
103	LIST searchPath;	/* The path along which files of this suffix
104			     	 * may be found */
105	int order;		/* order of declaration for conflict
106				 * resolution. */
107	LIST parents;		/* List of Suff we have a transformation to */
108	LIST children;		/* List of Suff we have a transformation from */
109	char name[1];
110};
111
112static struct ohash_info suff_info = {
113	offsetof(struct Suff_, name), NULL,
114	hash_calloc, hash_free, element_alloc
115};
116
117/*
118 * Structure used in the search for implied sources.
119 */
120typedef struct Src_ {
121	char *file;		/* The file to look for */
122	char *prefix;		/* Prefix from which file was formed */
123	Suff *suff;		/* The suffix on the file */
124	struct Src_ *parent;	/* The Src for which this is a source */
125	GNode *node;		/* The node describing the file */
126	int children;		/* Count of existing children (so we don't free
127				 * this thing too early or never nuke it) */
128#ifdef DEBUG_SRC
129	LIST	    cp; 	/* Debug; children list */
130#endif
131} Src;
132
133/*
134 * A structure for passing more than one argument to the Lst-library-invoked
135 * function...
136 */
137typedef struct {
138	Lst l;
139	Src *s;
140} LstSrc;
141
142static Suff *emptySuff; /* The empty suffix required for POSIX
143			 * single-suffix transformation rules */
144
145
146#define parse_transform(s, p, q) parse_transformi(s, s + strlen(s), p, q)
147static bool parse_transformi(const char *, const char *, Suff **, Suff **);
148#define new_suffix(s)	new_suffixi(s, NULL)
149static Suff *new_suffixi(const char *, const char *);
150static void reverse_hash_add_char(uint32_t *, const char *);
151static uint32_t reverse_hashi(const char *, const char **);
152static unsigned int reverse_slot(struct ohash *, const char *, const char **);
153static void record_possible_suffix(Suff *, GNode *, char *, Lst, Lst);
154static void record_possible_suffixes(GNode *, Lst, Lst);
155static Suff *find_suffix_as_suffix(Lst, const char *, const char *);
156static Suff *add_suffixi(const char *, const char *);
157
158static void SuffInsert(Lst, Suff *);
159static void SuffAddSrc(void *, void *);
160static bool SuffRemoveSrc(Lst);
161static void SuffAddLevel(Lst, Src *);
162static Src *SuffFindThem(Lst, Lst);
163static Src *SuffFindCmds(Src *, Lst);
164static bool SuffApplyTransform(GNode *, GNode *, Suff *, Suff *);
165static void SuffFindDeps(GNode *, Lst);
166static void SuffFindArchiveDeps(GNode *, Lst);
167static void SuffFindNormalDeps(GNode *, Lst);
168static void SuffPrintName(void *);
169static void SuffPrintSuff(void *);
170static void SuffPrintTrans(GNode *);
171
172#define find_suff(name)	find_suffi(name, NULL)
173static Suff *find_suffi(const char *, const char *);
174static Suff *find_best_suffix(const char *, const char *);
175static GNode *find_transform(const char *);
176static GNode *find_or_create_transformi(const char *, const char *);
177static void setup_paths(void);
178static void build_suffixes_graph(void);
179static void special_path_hack(void);
180
181#ifdef DEBUG_SRC
182static void PrintAddr(void *);
183#endif
184
185/* hash functions for the suffixes hash */
186/* add one char to the hash */
187static void
188reverse_hash_add_char(uint32_t *pk, const char *s)
189{
190	*pk =  ((*pk << 2) | (*pk >> 30)) ^ *s;
191}
192
193/* build a full hash from end to start */
194static uint32_t
195reverse_hashi(const char *s, const char **e)
196{
197	const char *p;
198	uint32_t k;
199
200	if (*e == NULL)
201		*e = s + strlen(s);
202	p = *e;
203	if (p == s)
204		k = 0;
205	else
206		k = *--p;
207	while (p != s) {
208		reverse_hash_add_char(&k, --p);
209	}
210	return k;
211}
212
213static unsigned int
214reverse_slot(struct ohash *h, const char *s, const char **e)
215{
216	uint32_t hv;
217
218	hv = reverse_hashi(s, e);
219	return ohash_lookup_interval(h, s, *e, hv);
220}
221
222
223static char *
224suffix_is_suffix(Suff *s, const char *str, const char *estr)
225{
226	const char *p1; 	/* Pointer into suffix name */
227	const char *p2; 	/* Pointer into string being examined */
228
229	if (estr - str < (ptrdiff_t) s->nameLen)
230		return NULL;
231	p1 = s->name + s->nameLen;
232	p2 = estr;
233
234	while (p1 != s->name) {
235		p1--;
236		p2--;
237		if (*p1 != *p2)
238			return NULL;
239	}
240
241	return (char *)p2;
242}
243
244static Suff *
245find_suffi(const char *name, const char *ename)
246{
247	unsigned int slot;
248#ifdef STATS_SUFF
249	STAT_SUFF_LOOKUP_NAME++;
250#endif
251	slot = reverse_slot(&suffixes, name, &ename);
252	return ohash_find(&suffixes, slot);
253}
254
255static GNode *
256find_transform(const char *name)
257{
258	unsigned int slot;
259
260#ifdef STATS_SUFF
261	STAT_TRANSFORM_LOOKUP_NAME++;
262#endif
263	slot = ohash_qlookup(&transforms, name);
264
265	return ohash_find(&transforms, slot);
266}
267
268static GNode *
269find_or_create_transformi(const char *name, const char *end)
270{
271	GNode *r;
272	unsigned int slot;
273
274#ifdef STATS_SUFF
275	STAT_TRANSFORM_LOOKUP_NAME++;
276#endif
277	slot = ohash_qlookupi(&transforms, name, &end);
278
279	r = ohash_find(&transforms, slot);
280
281	if (r == NULL) {
282		r = Targ_NewGNi(name, end);
283		ohash_insert(&transforms, slot, r);
284	}
285	return r;
286}
287
288/*-
289 *-----------------------------------------------------------------------
290 * SuffInsert  --
291 *	Insert the suffix into the list keeping the list ordered by suffix
292 *	numbers.
293 *
294 * Side Effects:
295 *	The reference count of the suffix is incremented
296 *-----------------------------------------------------------------------
297 */
298static void
299SuffInsert(Lst l, Suff *s)
300{
301	LstNode ln;		/* current element in l we're examining */
302	Suff *s2 = NULL;	/* the suffix descriptor in this element */
303
304	for (ln = Lst_First(l); ln != NULL; ln = Lst_Adv(ln)) {
305		s2 = Lst_Datum(ln);
306		if (s2->order >= s->order)
307			break;
308	}
309
310	if (DEBUG(SUFF))
311		printf("inserting %s(%d)...", s->name, s->order);
312	if (ln == NULL) {
313		if (DEBUG(SUFF))
314			printf("at end of list\n");
315		Lst_AtEnd(l, s);
316	} else if (s2->order != s->order) {
317		if (DEBUG(SUFF))
318			printf("before %s(%d)\n", s2->name, s2->order);
319		Lst_Insert(l, ln, s);
320	} else if (DEBUG(SUFF)) {
321		printf("already there\n");
322	}
323}
324
325/* Suff_DisableAllSuffixes
326 *	mark all current suffixes as inactive, and reset precedence
327 *	computation.  */
328void
329Suff_DisableAllSuffixes(void)
330{
331	unsigned int i;
332	Suff *s;
333
334	for (s = ohash_first(&suffixes, &i); s != NULL;
335	    s = ohash_next(&suffixes, &i))
336		s->flags &= ~SUFF_ACTIVE;
337
338	order = 0;
339	maxLen = 0;
340}
341
342
343/* okay = parse_transform(str, &src, &targ);
344 * 	try parsing a string as a transformation rule, returns true if
345 *	successful. Fills &src, &targ with the constituent suffixes.
346 * Special hack: source suffixes must exist OR be the special SUFF_PATH
347 * pseudo suffix (.PATH)
348 */
349static bool
350parse_transformi(const char *str, const char *e, Suff **srcPtr, Suff **targPtr)
351{
352	Suff *src, *target, *best_src, *best_target;
353	const char *p;
354
355	size_t len;
356	uint32_t hv;
357	unsigned int slot;
358
359	/* empty string -> no suffix */
360	if (e == str)
361		return false;
362
363	len = e - str;
364
365	if (len > 2 * maxLen)
366		return false;
367
368	p = e;
369	best_src = best_target = NULL;
370
371	hv = *--p;
372	while (p != str) {
373		slot = ohash_lookup_interval(&suffixes, p, e, hv);
374		/* no double suffix in there */
375		if (p - str <= (ptrdiff_t)maxLen) {
376			target = ohash_find(&suffixes, slot);
377			if (target != NULL && (target->flags & SUFF_ACTIVE)) {
378				src = find_suffi(str, p);
379				if (src != NULL &&
380				    (src->flags & (SUFF_ACTIVE | SUFF_PATH))) {
381				/* XXX even if we find a set of suffixes, we
382				 * have to keep going to find the best one,
383				 * namely, the one whose src appears first in
384				 * .SUFFIXES
385				 */
386					if (best_src == NULL ||
387					    src->order < best_src->order) {
388						best_src = src;
389						best_target = target;
390					}
391				}
392			}
393		}
394		/* can't be a suffix anyways */
395		if (e - p >= (ptrdiff_t)maxLen)
396			break;
397		reverse_hash_add_char(&hv, --p);
398	}
399
400	if (p == str && best_src == NULL) {
401		/* no double suffix transformation, resort to single suffix if
402		 * we find one.  */
403		slot = ohash_lookup_interval(&suffixes, p, e, hv);
404		src = ohash_find(&suffixes, slot);
405		if (src != NULL && (src->flags & (SUFF_ACTIVE | SUFF_PATH))) {
406			best_src = src;
407			best_target = emptySuff;
408		}
409	}
410	if (best_src != NULL) {
411		*srcPtr = best_src;
412		*targPtr = best_target;
413		return true;
414	} else {
415		return false;
416	}
417}
418
419static void
420special_path_hack(void)
421{
422	Suff *path = add_suffixi(".PATH", NULL);
423	path->flags |= SUFF_PATH;
424}
425
426static Suff *
427find_best_suffix(const char *s, const char *e)
428{
429	const char *p;
430	uint32_t hv;
431	unsigned int slot;
432	Suff *best = NULL;
433	Suff *suff;
434
435	if (e == s)
436		return NULL;
437	p = e;
438	hv = *--p;
439	while (p != s) {
440		slot = ohash_lookup_interval(&suffixes, p, e, hv);
441		suff = ohash_find(&suffixes, slot);
442		if (suff != NULL)
443			if (best == NULL || suff->order < best->order)
444				best = suff;
445		if (e - p >= (ptrdiff_t)maxLen)
446			break;
447		reverse_hash_add_char(&hv, --p);
448	}
449	return best;
450}
451
452Lst
453find_best_path(const char *name)
454{
455	Suff *s = find_best_suffix(name, name + strlen(name));
456	if (s != NULL) {
457		if (DEBUG(SUFF))
458			printf("suffix is \"%s\"...", s->name);
459		return &s->searchPath;
460	} else
461		return defaultPath;
462}
463
464/*-
465 *-----------------------------------------------------------------------
466 * Suff_ParseAsTransform --
467 *	Try parsing a target line as a transformation rule, depending on
468 *	existing suffixes.
469 *
470 *	Possibly create a new transform, or reset an existing one.
471 *-----------------------------------------------------------------------
472 */
473GNode *
474Suff_ParseAsTransform(const char *line, const char *end)
475{
476	GNode *gn;	/* GNode of transformation rule */
477	Suff *s;	/* source suffix */
478	Suff *t;	/* target suffix */
479
480	if (!parse_transformi(line, end, &s, &t))
481		return NULL;
482
483	gn = find_or_create_transformi(line, end);
484	/* In case the transform already exists, nuke old commands and children.
485	 * Note we can't free them, since there might be stuff that references
486	 * them elsewhere
487	 */
488	if (!Lst_IsEmpty(&gn->commands)) {
489		Lst_Destroy(&gn->commands, NOFREE);
490		Lst_Init(&gn->commands);
491	}
492	if (!Lst_IsEmpty(&gn->children)) {
493		Lst_Destroy(&gn->children, NOFREE);
494		Lst_Init(&gn->children);
495	}
496
497	gn->type = OP_TRANSFORM;
498	if (s->flags & SUFF_PATH) {
499		gn->special = SPECIAL_PATH;
500		gn->suffix = t;
501	}
502
503	if (DEBUG(SUFF))
504		printf("defining transformation from `%s' to `%s'\n",
505		    s->name, t->name);
506	return gn;
507}
508
509static void
510make_suffix_known(Suff *s)
511{
512	if ((s->flags & SUFF_ACTIVE) == 0) {
513		s->order = order++;
514		s->flags |= SUFF_ACTIVE;
515		if (s->nameLen > maxLen)
516			maxLen = s->nameLen;
517	}
518}
519
520static Suff *
521new_suffixi(const char *str, const char *eptr)
522{
523	Suff *s;
524
525	s = ohash_create_entry(&suff_info, str, &eptr);
526	s->nameLen = eptr - str;
527	Lst_Init(&s->searchPath);
528	Lst_Init(&s->children);
529	Lst_Init(&s->parents);
530	s->flags = 0;
531	return s;
532}
533
534/*-
535 *-----------------------------------------------------------------------
536 * Suff_AddSuffix --
537 *	Add the suffix in string to the end of the list of known suffixes.
538 *	Should we restructure the suffix graph? Make doesn't...
539 *
540 * Side Effects:
541 *	A GNode is created for the suffix and a Suff structure is created and
542 *	added to the known suffixes, unless it was already known.
543 *-----------------------------------------------------------------------
544 */
545void
546Suff_AddSuffixi(const char *str, const char *end)
547{
548	(void)add_suffixi(str, end);
549}
550
551static Suff *
552add_suffixi(const char *str, const char *end)
553{
554	Suff *s;	    /* new suffix descriptor */
555
556	unsigned int slot;
557
558	slot = reverse_slot(&suffixes, str, &end);
559	s = ohash_find(&suffixes, slot);
560	if (s == NULL) {
561		s = new_suffixi(str, end);
562		ohash_insert(&suffixes, slot, s);
563	}
564	make_suffix_known(s);
565	return s;
566}
567
568Lst
569find_suffix_path(GNode *gn)
570{
571	if (gn->suffix != NULL && gn->suffix != emptySuff)
572		return &(gn->suffix->searchPath);
573	else
574		return defaultPath;
575}
576
577static void
578build_suffixes_graph(void)
579{
580	Suff *s, *s2;
581	GNode *gn;
582	unsigned int i;
583
584	for (gn = ohash_first(&transforms, &i); gn != NULL;
585	    gn = ohash_next(&transforms, &i)) {
586	    	if (Lst_IsEmpty(&gn->commands) && Lst_IsEmpty(&gn->children))
587			continue;
588		if (gn->special == SPECIAL_PATH)
589			continue;
590	    	if (parse_transform(gn->name, &s, &s2)) {
591			SuffInsert(&s2->children, s);
592			SuffInsert(&s->parents, s2);
593		}
594	}
595}
596
597/*-
598 *-----------------------------------------------------------------------
599 * setup_paths
600 *	Extend the search paths for all suffixes to include the default
601 *	search path.
602 *
603 * Side Effects:
604 *	The searchPath field of all the suffixes is extended by the
605 *	directories in defaultPath.
606 *-----------------------------------------------------------------------
607 */
608static void
609setup_paths(void)
610{
611	unsigned int i;
612	Suff *s;
613
614	for (s = ohash_first(&suffixes, &i); s != NULL;
615	    s = ohash_next(&suffixes, &i)) {
616		if (!Lst_IsEmpty(&s->searchPath))
617			Dir_Concat(&s->searchPath, defaultPath);
618		else
619			Lst_Clone(&s->searchPath, defaultPath, Dir_CopyDir);
620	}
621}
622
623void
624process_suffixes_after_makefile_is_read(void)
625{
626	/* once the Makefile is finish reading, we can set up the default PATH
627	 * stuff, and build the final suffixes graph
628	 */
629	setup_paths();
630	/* and we link all transforms to active suffixes at this point. */
631	build_suffixes_graph();
632}
633	  /********** Implicit Source Search Functions *********/
634
635/*-
636 *-----------------------------------------------------------------------
637 * SuffAddSrc  --
638 *	Add a suffix as a Src structure to the given list with its parent
639 *	being the given Src structure. If the suffix is the null suffix,
640 *	the prefix is used unaltered as the file name in the Src structure.
641 *
642 * Side Effects:
643 *	A Src structure is created and tacked onto the end of the list
644 *-----------------------------------------------------------------------
645 */
646static void
647SuffAddSrc(
648    void *sp,		/* suffix for which to create a Src structure */
649    void *lsp)		/* list and parent for the new Src */
650{
651	Suff *s = sp;
652	LstSrc *ls = lsp;
653	Src *s2;	/* new Src structure */
654	Src *targ;	/* Target structure */
655
656	targ = ls->s;
657
658	s2 = emalloc(sizeof(Src));
659	s2->file = Str_concat(targ->prefix, s->name, 0);
660	s2->prefix = targ->prefix;
661	s2->parent = targ;
662	s2->node = NULL;
663	s2->suff = s;
664	s2->children = 0;
665	targ->children++;
666	Lst_AtEnd(ls->l, s2);
667#ifdef DEBUG_SRC
668	Lst_Init(&s2->cp);
669	Lst_AtEnd(&targ->cp, s2);
670	printf("2 add %x %x to %x:", targ, s2, ls->l);
671	Lst_Every(ls->l, PrintAddr);
672	printf("\n");
673#endif
674
675}
676
677/*-
678 *-----------------------------------------------------------------------
679 * SuffAddLevel  --
680 *	Add all the children of targ as Src structures to the given list
681 *
682 * Side Effects:
683 *	Lots of structures are created and added to the list
684 *-----------------------------------------------------------------------
685 */
686static void
687SuffAddLevel(
688    Lst l,	/* list to which to add the new level */
689    Src *targ)	/* Src structure to use as the parent */
690{
691	LstSrc	   ls;
692
693	ls.s = targ;
694	ls.l = l;
695
696	Lst_ForEach(&targ->suff->children, SuffAddSrc, &ls);
697}
698
699/*-
700 *----------------------------------------------------------------------
701 * SuffRemoveSrc --
702 *	Free Src structure with a zero reference count in a list
703 *
704 *	returns true if a src was removed
705 *----------------------------------------------------------------------
706 */
707static bool
708SuffRemoveSrc(Lst l)
709{
710	LstNode ln;
711	Src *s;
712
713#ifdef DEBUG_SRC
714	printf("cleaning %lx: ", (unsigned long)l);
715	Lst_Every(l, PrintAddr);
716	printf("\n");
717#endif
718
719
720	for (ln = Lst_First(l); ln != NULL; ln = Lst_Adv(ln)) {
721		s = Lst_Datum(ln);
722		if (s->children == 0) {
723			free(s->file);
724			if (!s->parent)
725				free(s->prefix);
726			else {
727#ifdef DEBUG_SRC
728				LstNode ln2 = Lst_Member(&s->parent->cp, s);
729				if (ln2 != NULL)
730				    Lst_Remove(&s->parent->cp, ln2);
731#endif
732				--s->parent->children;
733			}
734#ifdef DEBUG_SRC
735			printf("free: [l=%x] p=%x %d\n", l, s, s->children);
736			Lst_Destroy(&s->cp, NOFREE);
737#endif
738			Lst_Remove(l, ln);
739			free(s);
740			return true;
741		}
742#ifdef DEBUG_SRC
743		else {
744			printf("keep: [l=%x] p=%x %d: ", l, s, s->children);
745			Lst_Every(&s->cp, PrintAddr);
746			printf("\n");
747		}
748#endif
749	}
750
751	return false;
752}
753
754/*-
755 *-----------------------------------------------------------------------
756 * SuffFindThem --
757 *	Find the first existing file/target in the list srcs
758 *
759 * Results:
760 *	The lowest structure in the chain of transformations
761 *-----------------------------------------------------------------------
762 */
763static Src *
764SuffFindThem(
765    Lst srcs,	/* list of Src structures to search through */
766    Lst slst)
767{
768	Src *s;		/* current Src */
769	Src *rs; 	/* returned Src */
770	char *ptr;
771
772	rs = NULL;
773
774	while ((s = Lst_DeQueue(srcs)) != NULL) {
775		if (DEBUG(SUFF))
776			printf("\ttrying %s...", s->file);
777
778		/*
779		 * A file is considered to exist if either a node exists in the
780		 * graph for it or the file actually exists.
781		 */
782		if (Targ_FindNode(s->file, TARG_NOCREATE) != NULL) {
783#ifdef DEBUG_SRC
784			printf("remove %x from %x\n", s, srcs);
785#endif
786			rs = s;
787			break;
788		}
789
790		if ((ptr = Dir_FindFile(s->file, &s->suff->searchPath))
791		    != NULL) {
792			rs = s;
793#ifdef DEBUG_SRC
794			printf("remove %x from %x\n", s, srcs);
795#endif
796			free(ptr);
797			break;
798		}
799
800		if (DEBUG(SUFF))
801		    printf("not there\n");
802
803		SuffAddLevel(srcs, s);
804		Lst_AtEnd(slst, s);
805	}
806
807	if (DEBUG(SUFF) && rs)
808	    printf("got it\n");
809	return rs;
810}
811
812/*-
813 *-----------------------------------------------------------------------
814 * SuffFindCmds --
815 *	See if any of the children of the target in the Src structure is
816 *	one from which the target can be transformed. If there is one,
817 *	a Src structure is put together for it and returned.
818 *-----------------------------------------------------------------------
819 */
820static Src *
821SuffFindCmds(Src *targ, Lst slst)
822{
823	LstNode ln;	/* General-purpose list node */
824	GNode *t;	/* Target GNode */
825	GNode *s;	/* Source GNode */
826	int prefixLen;	/* The length of the defined prefix */
827	Suff *suff;	/* Suffix on matching beastie */
828	Src *ret;	/* Return value */
829	const char *cp;
830
831	t = targ->node;
832	prefixLen = strlen(targ->prefix);
833
834	for (ln = Lst_First(&t->children); ln != NULL; ln = Lst_Adv(ln)) {
835		s = Lst_Datum(ln);
836
837		cp = strrchr(s->name, '/');
838		if (cp == NULL)
839			cp = s->name;
840		else
841			cp++;
842		if (strncmp(cp, targ->prefix, prefixLen) != 0)
843			continue;
844		/* The node matches the prefix ok, see if it has a known
845		 * suffix.	*/
846		suff = find_suff(&cp[prefixLen]);
847		if (suff == NULL)
848			continue;
849		/*
850		 * It even has a known suffix, see if there's a transformation
851		 * defined between the node's suffix and the target's suffix.
852		 *
853		 * XXX: Handle multi-stage transformations here, too.
854		 */
855		if (Lst_Member(&suff->parents, targ->suff) == NULL)
856			continue;
857		/*
858		 * Create a new Src structure to describe this transformation
859		 * (making sure to duplicate the source node's name so
860		 * Suff_FindDeps can free it again (ick)), and return the new
861		 * structure.
862		 */
863		ret = emalloc(sizeof(Src));
864		ret->file = estrdup(s->name);
865		ret->prefix = targ->prefix;
866		ret->suff = suff;
867		ret->parent = targ;
868		ret->node = s;
869		ret->children = 0;
870		targ->children++;
871#ifdef DEBUG_SRC
872		Lst_Init(&ret->cp);
873		printf("3 add %x %x\n", targ, ret);
874		Lst_AtEnd(&targ->cp, ret);
875#endif
876		Lst_AtEnd(slst, ret);
877		if (DEBUG(SUFF))
878			printf("\tusing existing source %s\n", s->name);
879		return ret;
880	}
881	return NULL;
882}
883
884/*-
885 *-----------------------------------------------------------------------
886 * SuffApplyTransform --
887 *	Apply a transformation rule, given the source and target nodes
888 *	and suffixes.
889 *
890 * Results:
891 *	true if successful, false if not.
892 *
893 * Side Effects:
894 *	The source and target are linked and the commands from the
895 *	transformation are added to the target node's commands list.
896 *	All attributes but OP_DEPMASK and OP_TRANSFORM are applied
897 *	to the target. The target also inherits all the sources for
898 *	the transformation rule.
899 *-----------------------------------------------------------------------
900 */
901static bool
902SuffApplyTransform(
903    GNode	*tGn,	/* Target node */
904    GNode	*sGn,	/* Source node */
905    Suff	*t,	/* Target suffix */
906    Suff	*s)	/* Source suffix */
907{
908	LstNode	ln;	/* General node */
909	char	*tname; /* Name of transformation rule */
910	GNode	*gn;	/* Node for same */
911
912	if (Lst_AddNew(&tGn->children, sGn)) {
913		/* Not already linked, so form the proper links between the
914		 * target and source.  */
915		LinkParent(sGn, tGn);
916	}
917
918	if ((sGn->type & OP_OPMASK) == OP_DOUBLEDEP) {
919		/* When a :: node is used as the implied source of a node, we
920		 * have to link all its cohorts in as sources as well. There's
921		 * only one implied src, as that will be sufficient to get
922		 * the .IMPSRC variable set for tGn.	*/
923		for (ln=Lst_First(&sGn->cohorts); ln != NULL; ln=Lst_Adv(ln)) {
924			gn = Lst_Datum(ln);
925
926			if (Lst_AddNew(&tGn->children, gn)) {
927				/* Not already linked, so form the proper links
928				 * between the target and source.  */
929				LinkParent(gn, tGn);
930			}
931		}
932	}
933	/* Locate the transformation rule itself.  */
934	tname = Str_concat(s->name, t->name, 0);
935	gn = find_transform(tname);
936	free(tname);
937
938	if (gn == NULL)
939		/*
940		 * Not really such a transformation rule (can happen when we're
941		 * called to link an OP_MEMBER and OP_ARCHV node), so return
942		 * false.
943		 */
944		return false;
945
946	if (DEBUG(SUFF))
947		printf("\tapplying %s -> %s to \"%s\"\n", s->name, t->name,
948		    tGn->name);
949
950	/* Record last child for expansion purposes.  */
951	ln = Lst_Last(&tGn->children);
952
953	/* Pass the buck to Make_HandleUse to apply the rule.  */
954	Make_HandleUse(gn, tGn);
955
956	/* Deal with wildcards and variables in any acquired sources.  */
957	expand_children_from(tGn, Lst_Succ(ln));
958
959	/* Keep track of another parent to which this beast is transformed so
960	 * the .IMPSRC variable can be set correctly for the parent.  */
961	tGn->impliedsrc = sGn;
962
963	return true;
964}
965
966static Suff *
967find_suffix_as_suffix(Lst l, const char *b, const char *e)
968{
969	LstNode ln;
970	Suff *s;
971
972	for (ln = Lst_First(l); ln != NULL; ln = Lst_Adv(ln)) {
973		s = Lst_Datum(ln);
974		if (suffix_is_suffix(s, b, e))
975			return s;
976	}
977	return NULL;
978}
979
980/*-
981 *-----------------------------------------------------------------------
982 * SuffFindArchiveDeps --
983 *	Locate dependencies for an OP_ARCHV node.
984 *
985 * Side Effects:
986 *	Same as Suff_FindDeps
987 *-----------------------------------------------------------------------
988 */
989static void
990SuffFindArchiveDeps(
991    GNode	*gn,    /* Node for which to locate dependencies */
992    Lst 	slst)
993{
994	char *eoarch;	/* End of archive portion */
995	char *eoname;	/* End of member portion */
996	GNode *mem;	/* Node for member */
997	Suff *ms;	/* Suffix descriptor for member */
998	char *name;	/* Start of member's name */
999
1000	/* The node is an archive(member) pair. so we must find a suffix
1001	 * for both of them.  */
1002	eoarch = strchr(gn->name, '(');
1003	if (eoarch == NULL)
1004		return;
1005
1006	name = eoarch + 1;
1007
1008	eoname = strchr(name, ')');
1009	if (eoname == NULL)
1010		return;
1011
1012	/* To simplify things, call Suff_FindDeps recursively on the member now,
1013	 * so we can simply compare the member's .PREFIX and .TARGET variables
1014	 * to locate its suffix. This allows us to figure out the suffix to
1015	 * use for the archive without having to do a quadratic search over the
1016	 * suffix list, backtracking for each one...  */
1017	mem = Targ_FindNodei(name, eoname, TARG_CREATE);
1018	SuffFindDeps(mem, slst);
1019
1020	/* Create the link between the two nodes right off. */
1021	if (Lst_AddNew(&gn->children, mem))
1022		LinkParent(mem, gn);
1023
1024	/* Copy variables from member node to this one.  */
1025	Var(TARGET_INDEX, gn) = Var(TARGET_INDEX, mem);
1026	Var(PREFIX_INDEX, gn) = Var(PREFIX_INDEX, mem);
1027
1028	ms = mem->suffix;
1029	if (ms == NULL) {
1030		/* Didn't know what it was -- use .NULL suffix if not in make
1031		 * mode.  */
1032		if (DEBUG(SUFF))
1033			printf("using empty suffix\n");
1034		ms = emptySuff;
1035	}
1036
1037
1038	/* Set the other two local variables required for this target.  */
1039	Var(MEMBER_INDEX, gn) = mem->name;
1040	Var(ARCHIVE_INDEX, gn) = gn->name;
1041
1042	if (ms != NULL) {
1043		/*
1044		 * Member has a known suffix, so look for a transformation rule
1045		 * from it to a possible suffix of the archive. Rather than
1046		 * searching through the entire list, we just look at suffixes
1047		 * to which the member's suffix may be transformed...
1048		 */
1049
1050		Suff *suff;
1051
1052		suff = find_suffix_as_suffix(&ms->parents, gn->name, eoarch);
1053
1054		if (suff != NULL) {
1055			/* Got one -- apply it.  */
1056			if (!SuffApplyTransform(gn, mem, suff, ms) &&
1057			    DEBUG(SUFF))
1058				printf("\tNo transformation from %s -> %s\n",
1059				   ms->name, suff->name);
1060		}
1061	}
1062
1063	/* Pretend gn appeared to the left of a dependency operator so
1064	 * the user needn't provide a transformation from the member to the
1065	 * archive.  */
1066	if (OP_NOP(gn->type))
1067		gn->type |= OP_DEPENDS;
1068
1069	/* Flag the member as such so we remember to look in the archive for
1070	 * its modification time.  */
1071	mem->type |= OP_MEMBER;
1072}
1073
1074static void
1075record_possible_suffix(Suff *s, GNode *gn, char *eoname, Lst srcs, Lst targs)
1076{
1077	int prefixLen;
1078	Src *targ;
1079
1080	targ = emalloc(sizeof(Src));
1081	targ->file = estrdup(gn->name);
1082	targ->suff = s;
1083	targ->node = gn;
1084	targ->parent = NULL;
1085	targ->children = 0;
1086#ifdef DEBUG_SRC
1087	Lst_Init(&targ->cp);
1088#endif
1089
1090	/* Allocate room for the prefix, whose end is found by
1091	 * subtracting the length of the suffix from the end of
1092	 * the name.  */
1093	prefixLen = (eoname - targ->suff->nameLen) - gn->name;
1094	targ->prefix = emalloc(prefixLen + 1);
1095	memcpy(targ->prefix, gn->name, prefixLen);
1096	targ->prefix[prefixLen] = '\0';
1097
1098	/* Add nodes from which the target can be made.  */
1099	SuffAddLevel(srcs, targ);
1100
1101	/* Record the target so we can nuke it.  */
1102	Lst_AtEnd(targs, targ);
1103}
1104
1105static void
1106record_possible_suffixes(GNode *gn, Lst srcs, Lst targs)
1107{
1108	char *s = gn->name;
1109	char *e =  s + strlen(s);
1110	const char *p;
1111	uint32_t hv;
1112	unsigned int slot;
1113	Suff *suff;
1114
1115	if (e == s)
1116		return;
1117
1118	p = e;
1119	hv = *--p;
1120
1121	while (p != s) {
1122		slot = ohash_lookup_interval(&suffixes, p, e, hv);
1123		suff = ohash_find(&suffixes, slot);
1124		if (suff != NULL && (suff->flags & SUFF_ACTIVE))
1125			record_possible_suffix(suff, gn, e, srcs, targs);
1126		if (e - p >= (ptrdiff_t)maxLen)
1127			break;
1128		reverse_hash_add_char(&hv, --p);
1129	}
1130}
1131
1132/*-
1133 *-----------------------------------------------------------------------
1134 * SuffFindNormalDeps --
1135 *	Locate implicit dependencies for regular targets.
1136 *
1137 * Side Effects:
1138 *	Same as Suff_FindDeps...
1139 *-----------------------------------------------------------------------
1140 */
1141static void
1142SuffFindNormalDeps(
1143    GNode	*gn,	    /* Node for which to find sources */
1144    Lst 	slst)
1145{
1146	LIST srcs;	/* List of sources at which to look */
1147	LIST targs;	/* List of targets to which things can be
1148			 * transformed. They all have the same file,
1149			 * but different suff and prefix fields */
1150	Src *bottom;    /* Start of found transformation path */
1151	Src *src;	/* General Src pointer */
1152	char *prefix;	/* Prefix to use */
1153	Src *targ;	/* General Src target pointer */
1154
1155
1156	Lst_Init(&srcs);
1157	Lst_Init(&targs);
1158
1159	/* We're caught in a catch-22 here. On the one hand, we want to use any
1160	 * transformation implied by the target's sources, but we can't examine
1161	 * the sources until we've expanded any variables/wildcards they may
1162	 * hold, and we can't do that until we've set up the target's local
1163	 * variables and we can't do that until we know what the proper suffix
1164	 * for the target is (in case there are two suffixes one of which is a
1165	 * suffix of the other) and we can't know that until we've found its
1166	 * implied source, which we may not want to use if there's an existing
1167	 * source that implies a different transformation.
1168	 *
1169	 * In an attempt to get around this, which may not work all the time,
1170	 * but should work most of the time, we look for implied sources first,
1171	 * checking transformations to all possible suffixes of the target, use
1172	 * what we find to set the target's local variables, expand the
1173	 * children, then look for any overriding transformations they imply.
1174	 * Should we find one, we discard the one we found before.	*/
1175
1176
1177	record_possible_suffixes(gn, &srcs, &targs);
1178	/* Handle target of unknown suffix...  */
1179	if (Lst_IsEmpty(&srcs)) {
1180		if (DEBUG(SUFF))
1181			printf("\tNo known suffix on %s. Using empty suffix\n",
1182			    gn->name);
1183
1184		targ = emalloc(sizeof(Src));
1185		targ->file = estrdup(gn->name);
1186		targ->suff = emptySuff;
1187		targ->node = gn;
1188		targ->parent = NULL;
1189		targ->children = 0;
1190		targ->prefix = estrdup(gn->name);
1191#ifdef DEBUG_SRC
1192		Lst_Init(&targ->cp);
1193#endif
1194
1195		/* Only use the default suffix rules if we don't have commands
1196		 * or dependencies defined for this gnode.  */
1197		if (Lst_IsEmpty(&gn->commands) && Lst_IsEmpty(&gn->children))
1198			SuffAddLevel(&srcs, targ);
1199		else {
1200			if (DEBUG(SUFF))
1201				printf("not ");
1202		}
1203
1204		if (DEBUG(SUFF))
1205			printf("adding suffix rules\n");
1206
1207		Lst_AtEnd(&targs, targ);
1208	}
1209
1210	/* Using the list of possible sources built up from the target
1211	 * suffix(es), try and find an existing file/target that matches.  */
1212	bottom = SuffFindThem(&srcs, slst);
1213
1214	if (bottom == NULL) {
1215		/* No known transformations -- use the first suffix found for
1216		 * setting the local variables.  */
1217		if (!Lst_IsEmpty(&targs))
1218			targ = Lst_Datum(Lst_First(&targs));
1219		else
1220			targ = NULL;
1221	} else {
1222		/* Work up the transformation path to find the suffix of the
1223		 * target to which the transformation was made.  */
1224		for (targ = bottom; targ->parent != NULL; targ = targ->parent)
1225			continue;
1226	}
1227
1228	/* The .TARGET variable we always set to be the name at this point,
1229	 * since it's only set to the path if the thing is only a source and
1230	 * if it's only a source, it doesn't matter what we put here as far
1231	 * as expanding sources is concerned, since it has none...	*/
1232	Var(TARGET_INDEX, gn) = gn->name;
1233
1234	prefix = targ != NULL ? estrdup(targ->prefix) : gn->name;
1235	Var(PREFIX_INDEX, gn) = prefix;
1236
1237	/* Now we've got the important local variables set, expand any sources
1238	 * that still contain variables or wildcards in their names.  */
1239	expand_all_children(gn);
1240
1241	if (targ == NULL) {
1242		if (DEBUG(SUFF))
1243			printf("\tNo valid suffix on %s\n", gn->name);
1244
1245sfnd_abort:
1246		/* Deal with finding the thing on the default search path if the
1247		 * node is only a source (not on the lhs of a dependency operator
1248		 * or [XXX] it has neither children or commands).  */
1249		if (OP_NOP(gn->type) ||
1250		    (Lst_IsEmpty(&gn->children) &&
1251		    Lst_IsEmpty(&gn->commands))) {
1252			gn->path = Dir_FindFile(gn->name,
1253			    (targ == NULL ? defaultPath :
1254			    &targ->suff->searchPath));
1255			if (gn->path != NULL) {
1256				char *ptr;
1257				Var(TARGET_INDEX, gn) = estrdup(gn->path);
1258
1259				if (targ != NULL) {
1260					/* Suffix known for the thing -- trim
1261					 * the suffix off the path to form the
1262					 * proper .PREFIX variable.  */
1263					int savep = strlen(gn->path) -
1264					    targ->suff->nameLen;
1265					char savec;
1266
1267					gn->suffix = targ->suff;
1268
1269					savec = gn->path[savep];
1270					gn->path[savep] = '\0';
1271
1272					if ((ptr = strrchr(gn->path, '/')) !=
1273					    NULL)
1274						ptr++;
1275					else
1276						ptr = gn->path;
1277
1278					Var(PREFIX_INDEX, gn) = estrdup(ptr);
1279
1280					gn->path[savep] = savec;
1281				} else {
1282					/* The .PREFIX gets the full path if the
1283					 * target has no known suffix.  */
1284					gn->suffix = NULL;
1285
1286					if ((ptr = strrchr(gn->path, '/')) !=
1287					    NULL)
1288						ptr++;
1289					else
1290						ptr = gn->path;
1291
1292					Var(PREFIX_INDEX, gn) = estrdup(ptr);
1293				}
1294			}
1295		} else {
1296			/* Not appropriate to search for the thing -- set the
1297			 * path to be the name so Dir_MTime won't go grovelling
1298			 * for it.  */
1299			gn->suffix = targ == NULL ? NULL : targ->suff;
1300			free(gn->path);
1301			gn->path = estrdup(gn->name);
1302		}
1303
1304		goto sfnd_return;
1305	}
1306
1307	/* Check for overriding transformation rule implied by sources.  */
1308	if (!Lst_IsEmpty(&gn->children)) {
1309		src = SuffFindCmds(targ, slst);
1310
1311		if (src != NULL) {
1312			/* Free up all the Src structures in the transformation
1313			 * path up to, but not including, the parent node.  */
1314			while (bottom && bottom->parent != NULL) {
1315				(void)Lst_AddNew(slst, bottom);
1316				bottom = bottom->parent;
1317			}
1318			bottom = src;
1319		}
1320	}
1321
1322	if (bottom == NULL) {
1323		/* No idea from where it can come -- return now.  */
1324		goto sfnd_abort;
1325	}
1326
1327	/* We now have a list of Src structures headed by 'bottom' and linked
1328	 * via their 'parent' pointers. What we do next is create links between
1329	 * source and target nodes (which may or may not have been created) and
1330	 * set the necessary local variables in each target. The commands for
1331	 * each target are set from the commands of the transformation rule
1332	 * used to get from the src suffix to the targ suffix. Note that this
1333	 * causes the commands list of the original node, gn, to be replaced by
1334	 * the commands of the final transformation rule. Also, the children
1335	 * to build field of gn is incremented.  Etc.  */
1336	if (bottom->node == NULL) {
1337		bottom->node = Targ_FindNode(bottom->file, TARG_CREATE);
1338	}
1339
1340	for (src = bottom; src->parent != NULL; src = src->parent) {
1341		targ = src->parent;
1342
1343		src->node->suffix = src->suff;
1344
1345		if (targ->node == NULL) {
1346			targ->node = Targ_FindNode(targ->file, TARG_CREATE);
1347		}
1348
1349		SuffApplyTransform(targ->node, src->node,
1350				   targ->suff, src->suff);
1351
1352		if (targ->node != gn) {
1353			/* Finish off the dependency-search process for any
1354			 * nodes between bottom and gn (no point in questing
1355			 * around the filesystem for their implicit source when
1356			 * it's already known). Note that the node can't have
1357			 * any sources that need expanding, since SuffFindThem
1358			 * will stop on an existing node, so all we need to do
1359			 * is set the standard and System V variables.  */
1360			targ->node->type |= OP_DEPS_FOUND;
1361
1362			Var(PREFIX_INDEX, targ->node) = estrdup(targ->prefix);
1363
1364			Var(TARGET_INDEX, targ->node) = targ->node->name;
1365		}
1366	}
1367
1368	gn->suffix = src->suff;
1369
1370	/* So Dir_MTime doesn't go questing for it...  */
1371	free(gn->path);
1372	gn->path = estrdup(gn->name);
1373
1374	/* Nuke the transformation path and the Src structures left over in the
1375	 * two lists.  */
1376sfnd_return:
1377	if (bottom)
1378		(void)Lst_AddNew(slst, bottom);
1379
1380	while (SuffRemoveSrc(&srcs) || SuffRemoveSrc(&targs))
1381		continue;
1382
1383	Lst_ConcatDestroy(slst, &srcs);
1384	Lst_ConcatDestroy(slst, &targs);
1385}
1386
1387
1388/*-
1389 *-----------------------------------------------------------------------
1390 * Suff_FindDeps  --
1391 *	Find implicit sources for the target described by the graph node
1392 *	gn
1393 *
1394 * Side Effects:
1395 *	Nodes are added to the graph below the passed-in node. The nodes
1396 *	are marked to have their IMPSRC variable filled in. The
1397 *	PREFIX variable is set for the given node and all its
1398 *	implied children.
1399 *
1400 * Notes:
1401 *	The path found by this target is the shortest path in the
1402 *	transformation graph, which may pass through non-existent targets,
1403 *	to an existing target. The search continues on all paths from the
1404 *	root suffix until a file is found. I.e. if there's a path
1405 *	.o -> .c -> .l -> .l,v from the root and the .l,v file exists but
1406 *	the .c and .l files don't, the search will branch out in
1407 *	all directions from .o and again from all the nodes on the
1408 *	next level until the .l,v node is encountered.
1409 *-----------------------------------------------------------------------
1410 */
1411
1412void
1413Suff_FindDeps(GNode *gn)
1414{
1415
1416	SuffFindDeps(gn, &srclist);
1417	while (SuffRemoveSrc(&srclist))
1418		continue;
1419}
1420
1421
1422static void
1423SuffFindDeps(GNode *gn, Lst slst)
1424{
1425	if (gn->type & OP_DEPS_FOUND) {
1426		/*
1427		 * If dependencies already found, no need to do it again...
1428		 */
1429		return;
1430	} else {
1431		gn->type |= OP_DEPS_FOUND;
1432	}
1433
1434	if (DEBUG(SUFF))
1435		printf("SuffFindDeps (%s)\n", gn->name);
1436
1437	current_node = gn;
1438	if (gn->type & OP_ARCHV)
1439		SuffFindArchiveDeps(gn, slst);
1440	else
1441		SuffFindNormalDeps(gn, slst);
1442	current_node = NULL;
1443}
1444
1445/*-
1446 *-----------------------------------------------------------------------
1447 * Suff_Init --
1448 *	Initialize suffixes module
1449 *
1450 * Side Effects:
1451 *	Many
1452 *-----------------------------------------------------------------------
1453 */
1454void
1455Suff_Init(void)
1456{
1457	Static_Lst_Init(&srclist);
1458	ohash_init(&transforms, 4, &gnode_info);
1459
1460	/* Create null suffix for single-suffix rules (POSIX). The thing doesn't
1461	 * actually go on the suffix list as it matches everything.  */
1462	emptySuff = new_suffix("");
1463	emptySuff->flags = SUFF_ACTIVE;
1464	emptySuff->order = 0;
1465	Dir_Concat(&emptySuff->searchPath, defaultPath);
1466	ohash_init(&suffixes, 4, &suff_info);
1467	special_path_hack();
1468}
1469
1470
1471/********************* DEBUGGING FUNCTIONS **********************/
1472
1473static void
1474SuffPrintName(void *p)
1475{
1476	const Suff *s = p;
1477	printf("%s ", s == emptySuff ? "<empty>" : s->name);
1478}
1479
1480static void
1481SuffPrintSuff(void *sp)
1482{
1483	Suff    *s = sp;
1484
1485	printf("# %-5s ", s->name);
1486
1487	if (!Lst_IsEmpty(&s->parents)) {
1488		printf(" ->");
1489		Lst_Every(&s->parents, SuffPrintName);
1490	}
1491	if (!Lst_IsEmpty(&s->children)) {
1492		printf(" <-");
1493		Lst_Every(&s->children, SuffPrintName);
1494	}
1495	fputc('\n', stdout);
1496}
1497
1498static void
1499SuffPrintTrans(GNode *t)
1500{
1501	printf("%-16s: ", t->name);
1502	Targ_PrintType(t->type);
1503	fputc('\n', stdout);
1504	Lst_Every(&t->commands, Targ_PrintCmd);
1505	fputc('\n', stdout);
1506}
1507
1508static int
1509compare_order(const void *a, const void *b)
1510{
1511	const Suff **pa = (const Suff **)a;
1512	const Suff **pb = (const Suff **)b;
1513	return (*pb)->order - (*pa)->order;
1514}
1515
1516static void
1517print_path(Suff *s)
1518{
1519	/* do we need to print it ? compare against defaultPath */
1520	LstNode ln1, ln2;
1521	bool first = true;
1522
1523	for (ln1 = Lst_First(&s->searchPath), ln2 = Lst_First(defaultPath);
1524	    ln1 != NULL && ln2 != NULL;
1525	    ln1 = Lst_Adv(ln1)) {
1526		if (Lst_Datum(ln1) == Lst_Datum(ln2)) {
1527			ln2 = Lst_Adv(ln2);
1528			continue;
1529		}
1530		if (first) {
1531			printf(".PATH%s:", s->name);
1532			first = false;
1533		}
1534		printf(" %s", PathEntry_name(Lst_Datum(ln1)));
1535	}
1536	if (!first)
1537		printf("\n\n");
1538}
1539
1540void
1541Suff_PrintAll(void)
1542{
1543	Suff **t;
1544	GNode **u;
1545	unsigned int i;
1546	bool reprint;
1547
1548
1549	printf("# Suffixes graph\n");
1550	t = sort_ohash_by_name(&suffixes);
1551	for (i = 0; t[i] != NULL; i++)
1552		if (!(t[i]->flags & SUFF_PATH))
1553			SuffPrintSuff(t[i]);
1554
1555	printf("\n.PATH: ");
1556	Dir_PrintPath(defaultPath);
1557	printf("\n\n");
1558	for (i = 0; t[i] != NULL; i++)
1559		if (!(t[i]->flags & SUFF_PATH))
1560			print_path(t[i]);
1561	free(t);
1562
1563	reprint = false;
1564	t = sort_ohash(&suffixes, compare_order);
1565	printf(".SUFFIXES:");
1566	for (i = 0; t[i] != NULL; i++) {
1567		if (t[i]->flags & SUFF_PATH)
1568			continue;
1569		printf(" %s", t[i]->name);
1570		if (!(t[i]->flags & SUFF_ACTIVE))
1571			reprint = true;
1572	}
1573	printf("\n\n");
1574	u = sort_ohash_by_name(&transforms);
1575	for (i = 0; u[i] != NULL; i++)
1576	    	SuffPrintTrans(u[i]);
1577	free(u);
1578
1579	if (reprint) {
1580		printf(".SUFFIXES:");
1581		for (i = 0; t[i] != NULL; i++)
1582			if (t[i]->flags & SUFF_ACTIVE)
1583				printf(" %s", t[i]->name);
1584		printf("\n");
1585	}
1586	free(t);
1587}
1588
1589#ifdef DEBUG_SRC
1590static void
1591PrintAddr(void *a)
1592{
1593	printf("%lx ", (unsigned long)a);
1594}
1595#endif
1596