GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: usr.bin/make/suff.c Lines: 437 605 72.2 %
Date: 2017-11-13 Branches: 213 352 60.5 %

Line Branch Exec Source
1
/*	$OpenBSD: suff.c,v 1.92 2017/07/24 12:07:46 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
 * Interface:
44
 *	Suff_Init		Initialize all things to do with suffixes.
45
 *
46
 *	Suff_ClearSuffixes	Clear out all the suffixes.
47
 *
48
 *	Suff_AddSuffix		Add the passed string as another known suffix.
49
 *
50
 *	Suff_ParseAsTransform	Line might be a suffix line, check it.
51
 *				If it's not, return NULL. Otherwise, add
52
 *				another transformation to the suffix graph.
53
 *				Returns	GNode suitable for framing, I mean,
54
 *				tacking commands, attributes, etc. on.
55
 *
56
 *	Suff_FindDeps		Find implicit sources for and the location of
57
 *				a target based on its suffix. Returns the
58
 *				bottom-most node added to the graph or NULL
59
 *				if the target had no implicit sources.
60
 */
61
62
#include <ctype.h>
63
#include <signal.h>
64
#include <stddef.h>
65
#include <stdint.h>
66
#include <stdio.h>
67
#include <stdlib.h>
68
#include <string.h>
69
#include <ohash.h>
70
#include "config.h"
71
#include "defines.h"
72
#include "dir.h"
73
#include "direxpand.h"
74
#include "engine.h"
75
#include "arch.h"
76
#include "suff.h"
77
#include "var.h"
78
#include "targ.h"
79
#include "error.h"
80
#include "str.h"
81
#include "lst.h"
82
#include "memory.h"
83
#include "gnode.h"
84
#include "make.h"
85
#include "stats.h"
86
#include "dump.h"
87
88
/* XXX the suffixes hash is stored using a specific hash function, suitable
89
 * for looking up suffixes in reverse.
90
 */
91
static struct ohash suffixes;
92
93
/* We remember the longest suffix, so we don't need to look beyond that.  */
94
size_t maxLen;
95
static LIST srclist;
96
97
/* Transforms (.c.o) are stored in another hash, independently from suffixes.
98
 * When make sees a target, it checks whether it's currently parsable as a
99
 * transform (according to the active suffixes). If yes, it's stored as a
100
 * new transform.
101
 *
102
 * XXX
103
 * But transforms DO NOT have a canonical decomposition as a set of suffixes,
104
 * and will be used as necessary later, when looking up implicit rules for
105
 * actual targets.
106
 *
107
 * For instance, a transform .a.b.c  can be parsed as .a -> .b.c if suffixes
108
 * .a and .b.c are active, and then LATER, reused as .a.b -> .c if suffixes
109
 * .a.b and .c are active.
110
 */
111
static struct ohash transforms;
112
113
/* conflicts between suffixes are solved by suffix declaration order. */
114
static int order = 0;
115
116
/*
117
 * Structure describing an individual suffix.
118
 */
119
struct Suff_ {
120
	size_t nameLen;		/* optimisation: strlen(name) */
121
	short flags;
122
#define SUFF_ACTIVE	  0x08	/* We never destroy suffixes and rules, */
123
				/* we just deactivate them. */
124
#define SUFF_PATH	  0x10	/* False suffix: actually, the path keyword */
125
	LIST searchPath;	/* The path along which files of this suffix
126
			     	 * may be found */
127
	int order;		/* order of declaration for conflict
128
				 * resolution. */
129
	LIST parents;		/* List of Suff we have a transformation to */
130
	LIST children;		/* List of Suff we have a transformation from */
131
	char name[1];
132
};
133
134
static struct ohash_info suff_info = {
135
	offsetof(struct Suff_, name), NULL,
136
	hash_calloc, hash_free, element_alloc
137
};
138
139
/*
140
 * Structure used in the search for implied sources.
141
 */
142
typedef struct Src_ {
143
	char *file;		/* The file to look for */
144
	char *prefix;		/* Prefix from which file was formed */
145
	Suff *suff;		/* The suffix on the file */
146
	struct Src_ *parent;	/* The Src for which this is a source */
147
	GNode *node;		/* The node describing the file */
148
	int children;		/* Count of existing children (so we don't free
149
				 * this thing too early or never nuke it) */
150
#ifdef DEBUG_SRC
151
	LIST	    cp; 	/* Debug; children list */
152
#endif
153
} Src;
154
155
/*
156
 * A structure for passing more than one argument to the Lst-library-invoked
157
 * function...
158
 */
159
typedef struct {
160
	Lst l;
161
	Src *s;
162
} LstSrc;
163
164
static Suff *emptySuff; /* The empty suffix required for POSIX
165
			 * single-suffix transformation rules */
166
167
168
#define parse_transform(s, p, q) parse_transformi(s, s + strlen(s), p, q)
169
static bool parse_transformi(const char *, const char *, Suff **, Suff **);
170
#define new_suffix(s)	new_suffixi(s, NULL)
171
static Suff *new_suffixi(const char *, const char *);
172
static void reverse_hash_add_char(uint32_t *, const char *);
173
static uint32_t reverse_hashi(const char *, const char **);
174
static unsigned int reverse_slot(struct ohash *, const char *, const char **);
175
static void clear_suffixes(void);
176
static void record_possible_suffix(Suff *, GNode *, char *, Lst, Lst);
177
static void record_possible_suffixes(GNode *, Lst, Lst);
178
static Suff *find_suffix_as_suffix(Lst, const char *, const char *);
179
static Suff *add_suffixi(const char *, const char *);
180
181
static void SuffInsert(Lst, Suff *);
182
static void SuffAddSrc(void *, void *);
183
static int SuffRemoveSrc(Lst);
184
static void SuffAddLevel(Lst, Src *);
185
static Src *SuffFindThem(Lst, Lst);
186
static Src *SuffFindCmds(Src *, Lst);
187
static void SuffExpandChildren(LstNode, GNode *);
188
static void SuffExpandVarChildren(LstNode, GNode *, GNode *);
189
static void SuffExpandWildChildren(LstNode, GNode *, GNode *);
190
static bool SuffApplyTransform(GNode *, GNode *, Suff *, Suff *);
191
static void SuffFindDeps(GNode *, Lst);
192
static void SuffFindArchiveDeps(GNode *, Lst);
193
static void SuffFindNormalDeps(GNode *, Lst);
194
static void SuffPrintName(void *);
195
static void SuffPrintSuff(void *);
196
static void SuffPrintTrans(GNode *);
197
198
#define find_suff(name)	find_suffi(name, NULL)
199
static Suff *find_suffi(const char *, const char *);
200
static Suff *find_best_suffix(const char *, const char *);
201
static GNode *find_transform(const char *);
202
static GNode *find_or_create_transformi(const char *, const char *);
203
static void setup_paths(void);
204
static void build_suffixes_graph(void);
205
static void special_path_hack(void);
206
207
#ifdef DEBUG_SRC
208
static void PrintAddr(void *);
209
#endif
210
211
/* hash functions for the suffixes hash */
212
/* add one char to the hash */
213
static void
214
reverse_hash_add_char(uint32_t *pk, const char *s)
215
{
216
28986460
	*pk =  ((*pk << 2) | (*pk >> 30)) ^ *s;
217
14493230
}
218
219
/* build a full hash from end to start */
220
static uint32_t
221
reverse_hashi(const char *s, const char **e)
222
{
223
	const char *p;
224
3444748
	uint32_t k;
225
226
1722374
	if (*e == NULL)
227
50646
		*e = s + strlen(s);
228
1722374
	p = *e;
229
1722374
	if (p == s)
230
		k = 0;
231
	else
232
1722374
		k = *--p;
233
10963850
	while (p != s) {
234
3759551
		reverse_hash_add_char(&k, --p);
235
	}
236
3444748
	return k;
237
1722374
}
238
239
static unsigned int
240
reverse_slot(struct ohash *h, const char *s, const char **e)
241
{
242
	uint32_t hv;
243
244
3444748
	hv = reverse_hashi(s, e);
245
1722374
	return ohash_lookup_interval(h, s, *e, hv);
246
}
247
248
249
static char *
250
suffix_is_suffix(Suff *s, const char *str, const char *estr)
251
{
252
	const char *p1; 	/* Pointer into suffix name */
253
	const char *p2; 	/* Pointer into string being examined */
254
255
	if (estr - str < (ptrdiff_t) s->nameLen)
256
		return NULL;
257
	p1 = s->name + s->nameLen;
258
	p2 = estr;
259
260
	while (p1 != s->name) {
261
		p1--;
262
		p2--;
263
		if (*p1 != *p2)
264
			return NULL;
265
	}
266
267
	return (char *)p2;
268
}
269
270
static Suff *
271
find_suffi(const char *name, const char *ename)
272
{
273
	unsigned int slot;
274
#ifdef STATS_SUFF
275
	STAT_SUFF_LOOKUP_NAME++;
276
#endif
277
1141073
	slot = reverse_slot(&suffixes, name, &ename);
278
1141073
	return ohash_find(&suffixes, slot);
279
}
280
281
static GNode *
282
find_transform(const char *name)
283
{
284
	unsigned int slot;
285
286
#ifdef STATS_SUFF
287
	STAT_TRANSFORM_LOOKUP_NAME++;
288
#endif
289
68498
	slot = ohash_qlookup(&transforms, name);
290
291
34249
	return ohash_find(&transforms, slot);
292
}
293
294
static GNode *
295
find_or_create_transformi(const char *name, const char *end)
296
{
297
	GNode *r;
298
	unsigned int slot;
299
300
#ifdef STATS_SUFF
301
	STAT_TRANSFORM_LOOKUP_NAME++;
302
#endif
303
775964
	slot = ohash_qlookupi(&transforms, name, &end);
304
305
775964
	r = ohash_find(&transforms, slot);
306
307
775964
	if (r == NULL) {
308
724663
		r = Targ_NewGNi(name, end);
309
724663
		ohash_insert(&transforms, slot, r);
310
724663
	}
311
775964
	return r;
312
}
313
314
/*-
315
 *-----------------------------------------------------------------------
316
 * SuffInsert  --
317
 *	Insert the suffix into the list keeping the list ordered by suffix
318
 *	numbers.
319
 *
320
 * Side Effects:
321
 *	The reference count of the suffix is incremented
322
 *-----------------------------------------------------------------------
323
 */
324
static void
325
SuffInsert(Lst l, Suff *s)
326
{
327
	LstNode ln;		/* current element in l we're examining */
328
	Suff *s2 = NULL;	/* the suffix descriptor in this element */
329
330
8716458
	for (ln = Lst_First(l); ln != NULL; ln = Lst_Adv(ln)) {
331
2967294
		s2 = Lst_Datum(ln);
332
2967294
		if (s2->order >= s->order)
333
			break;
334
	}
335
336
1436632
	if (DEBUG(SUFF))
337
		printf("inserting %s(%d)...", s->name, s->order);
338
1436632
	if (ln == NULL) {
339
672619
		if (DEBUG(SUFF))
340
			printf("at end of list\n");
341
672619
		Lst_AtEnd(l, s);
342
1436632
	} else if (s2->order != s->order) {
343
764013
		if (DEBUG(SUFF))
344
			printf("before %s(%d)\n", s2->name, s2->order);
345
764013
		Lst_Insert(l, ln, s);
346
764013
	} else if (DEBUG(SUFF)) {
347
		printf("already there\n");
348
	}
349
1436632
}
350
351
/*-
352
 *-----------------------------------------------------------------------
353
 * Suff_ClearSuffixes --
354
 *	Nuke the list of suffixes but keep all transformation
355
 *	rules around.
356
 *
357
 * Side Effects:
358
 *	Current suffixes are reset
359
 *-----------------------------------------------------------------------
360
 */
361
static void
362
clear_suffixes(void)
363
{
364
34340
	unsigned int i;
365
	Suff *s;
366
367
47654
	for (s = ohash_first(&suffixes, &i); s != NULL;
368
6657
	    s = ohash_next(&suffixes, &i))
369
6657
		s->flags &= ~SUFF_ACTIVE;
370
371
17170
	order = 0;
372
17170
	maxLen = 0;
373
17170
}
374
375
void
376
Suff_ClearSuffixes(void)
377
{
378
634
	clear_suffixes();
379
317
}
380
381
382
/* okay = parse_transform(str, &src, &targ);
383
 * 	try parsing a string as a transformation rule, returns true if
384
 *	successful. Fills &src, &targ with the constituent suffixes.
385
 * Special hack: source suffixes must exist OR be the special SUFF_PATH
386
 * pseudo suffix (.PATH)
387
 */
388
static bool
389
parse_transformi(const char *str, const char *e, Suff **srcPtr, Suff **targPtr)
390
{
391
	Suff *src, *target, *best_src, *best_target;
392
	const char *p;
393
394
	size_t len;
395
13218180
	uint32_t hv;
396
	unsigned int slot;
397
398
	/* empty string -> no suffix */
399
6609090
	if (e == str)
400
78
		return false;
401
402
6609012
	len = e - str;
403
404
6609012
	if (len > 2 * maxLen)
405
4220153
		return false;
406
407
	p = e;
408
	best_src = best_target = NULL;
409
410
2388859
	hv = *--p;
411
24324736
	while (p != str) {
412
10456793
		slot = ohash_lookup_interval(&suffixes, p, e, hv);
413
		/* no double suffix in there */
414
10456793
		if (p - str <= (ptrdiff_t)maxLen) {
415
9215254
			target = ohash_find(&suffixes, slot);
416

10328225
			if (target != NULL && (target->flags & SUFF_ACTIVE)) {
417
1107280
				src = find_suffi(str, p);
418

2130025
				if (src != NULL &&
419
1022745
				    (src->flags & (SUFF_ACTIVE | SUFF_PATH))) {
420
				/* XXX even if we find a set of suffixes, we
421
				 * have to keep going to find the best one,
422
				 * namely, the one whose src appears first in
423
				 * .SUFFIXES
424
				 */
425

1021794
					if (best_src == NULL ||
426
					    src->order < best_src->order) {
427
						best_src = src;
428
						best_target = target;
429
1021794
					}
430
				}
431
			}
432
		}
433
		/* can't be a suffix anyways */
434
10456793
		if (e - p >= (ptrdiff_t)maxLen)
435
			break;
436
9773509
		reverse_hash_add_char(&hv, --p);
437
	}
438
439
2388859
	if (p == str && best_src == NULL) {
440
		/* no double suffix transformation, resort to single suffix if
441
		 * we find one.  */
442
866923
		slot = ohash_lookup_interval(&suffixes, p, e, hv);
443
866923
		src = ohash_find(&suffixes, slot);
444

1340767
		if (src != NULL && (src->flags & (SUFF_ACTIVE | SUFF_PATH))) {
445
			best_src = src;
446
472486
			best_target = emptySuff;
447
472486
		}
448
	}
449
2388859
	if (best_src != NULL) {
450
1494280
		*srcPtr = best_src;
451
1494280
		*targPtr = best_target;
452
1494280
		return true;
453
	} else {
454
894579
		return false;
455
	}
456
6609090
}
457
458
static void
459
special_path_hack(void)
460
{
461
33706
	Suff *path = add_suffixi(".PATH", NULL);
462
16853
	path->flags |= SUFF_PATH;
463
16853
}
464
465
static Suff *
466
find_best_suffix(const char *s, const char *e)
467
{
468
	const char *p;
469
4
	uint32_t hv;
470
	unsigned int slot;
471
	Suff *best = NULL;
472
	Suff *suff;
473
474
2
	if (e == s)
475
		return NULL;
476
	p = e;
477
2
	hv = *--p;
478
20
	while (p != s) {
479
10
		slot = ohash_lookup_interval(&suffixes, p, e, hv);
480
10
		suff = ohash_find(&suffixes, slot);
481
10
		if (suff != NULL)
482
			if (best == NULL || suff->order < best->order)
483
				best = suff;
484
10
		if (e - p >= (ptrdiff_t)maxLen)
485
			break;
486
8
		reverse_hash_add_char(&hv, --p);
487
	}
488
2
	return best;
489
2
}
490
491
/*-
492
 *-----------------------------------------------------------------------
493
 * Suff_ParseAsTransform --
494
 *	Try parsing a target line as a transformation rule, depending on
495
 *	existing suffixes.
496
 *
497
 *	Possibly create a new transform, or reset an existing one.
498
 *-----------------------------------------------------------------------
499
 */
500
GNode *
501
Suff_ParseAsTransform(const char *line, const char *end)
502
{
503
	GNode *gn;	/* GNode of transformation rule */
504
11770136
	Suff *s;	/* source suffix */
505
5885068
	Suff *t;	/* target suffix */
506
507
5885068
	if (!parse_transformi(line, end, &s, &t))
508
5109104
		return NULL;
509
510
775964
	gn = find_or_create_transformi(line, end);
511
	/* In case the transform already exists, nuke old commands and children.
512
	 * Note we can't free them, since there might be stuff that references
513
	 * them elsewhere
514
	 */
515
775964
	if (!Lst_IsEmpty(&gn->commands)) {
516
51032
		Lst_Destroy(&gn->commands, NOFREE);
517
51032
		Lst_Init(&gn->commands);
518
51032
	}
519
775964
	if (!Lst_IsEmpty(&gn->children)) {
520
		Lst_Destroy(&gn->children, NOFREE);
521
		Lst_Init(&gn->children);
522
	}
523
524
775964
	gn->type = OP_TRANSFORM;
525
775964
	if (s->flags & SUFF_PATH) {
526
910
		gn->special = SPECIAL_PATH | SPECIAL_TARGET;
527
910
		gn->suffix = t;
528
910
	}
529
530
775964
	if (DEBUG(SUFF))
531
		printf("defining transformation from `%s' to `%s'\n",
532
		    s->name, t->name);
533
775964
	return gn;
534
5885068
}
535
536
static void
537
make_suffix_known(Suff *s)
538
{
539
1196308
	if ((s->flags & SUFF_ACTIVE) == 0) {
540
438149
		s->order = order++;
541
438149
		s->flags |= SUFF_ACTIVE;
542
438149
		if (s->nameLen > maxLen)
543
28143
			maxLen = s->nameLen;
544
	}
545
598154
}
546
547
static Suff *
548
new_suffixi(const char *str, const char *eptr)
549
{
550
	Suff *s;
551
552
434023
	s = ohash_create_entry(&suff_info, str, &eptr);
553
434023
	s->nameLen = eptr - str;
554
434023
	Lst_Init(&s->searchPath);
555
434023
	Lst_Init(&s->children);
556
434023
	Lst_Init(&s->parents);
557
434023
	s->flags = 0;
558
434023
	return s;
559
}
560
561
/*-
562
 *-----------------------------------------------------------------------
563
 * Suff_AddSuffix --
564
 *	Add the suffix in string to the end of the list of known suffixes.
565
 *	Should we restructure the suffix graph? Make doesn't...
566
 *
567
 * Side Effects:
568
 *	A GNode is created for the suffix and a Suff structure is created and
569
 *	added to the known suffixes, unless it was already known.
570
 *-----------------------------------------------------------------------
571
 */
572
void
573
Suff_AddSuffixi(const char *str, const char *end)
574
{
575
1128896
	(void)add_suffixi(str, end);
576
564448
}
577
578
static Suff *
579
add_suffixi(const char *str, const char *end)
580
{
581
	Suff *s;	    /* new suffix descriptor */
582
583
	unsigned int slot;
584
585
581301
	slot = reverse_slot(&suffixes, str, &end);
586
581301
	s = ohash_find(&suffixes, slot);
587
581301
	if (s == NULL) {
588
417170
		s = new_suffixi(str, end);
589
417170
		ohash_insert(&suffixes, slot, s);
590
417170
	}
591
581301
	make_suffix_known(s);
592
581301
	return s;
593
}
594
595
Lst
596
find_suffix_path(GNode *gn)
597
{
598

8625
	if (gn->suffix != NULL && gn->suffix != emptySuff)
599
1545
		return &(gn->suffix->searchPath);
600
	else
601
1540
		return defaultPath;
602
3085
}
603
604
static void
605
build_suffixes_graph(void)
606
{
607
33706
	Suff *s, *s2;
608
	GNode *gn;
609
16853
	unsigned int i;
610
611
1483032
	for (gn = ohash_first(&transforms, &i); gn != NULL;
612
724663
	    gn = ohash_next(&transforms, &i)) {
613

725304
	    	if (Lst_IsEmpty(&gn->commands) && Lst_IsEmpty(&gn->children))
614
			continue;
615
724022
		if ((gn->special & SPECIAL_MASK) == SPECIAL_PATH)
616
			continue;
617
724022
	    	if (parse_transform(gn->name, &s, &s2)) {
618
718316
			SuffInsert(&s2->children, s);
619
718316
			SuffInsert(&s->parents, s2);
620
718316
		}
621
	}
622
16853
}
623
624
/*-
625
 *-----------------------------------------------------------------------
626
 * setup_paths
627
 *	Extend the search paths for all suffixes to include the default
628
 *	search path.
629
 *
630
 * Side Effects:
631
 *	The searchPath field of all the suffixes is extended by the
632
 *	directories in defaultPath. If paths were specified for the
633
 *	".h" suffix, the directories are stuffed into a global variable
634
 *	called ".INCLUDES" with each directory preceded by a -I. The same
635
 *	is done for the ".a" suffix, except the variable is called
636
 *	".LIBS" and the flag is -L.
637
 *-----------------------------------------------------------------------
638
 */
639
static void
640
setup_paths(void)
641
{
642
33706
	unsigned int i;
643
	Suff *s;
644
645
868046
	for (s = ohash_first(&suffixes, &i); s != NULL;
646
417170
	    s = ohash_next(&suffixes, &i)) {
647
417170
		if (!Lst_IsEmpty(&s->searchPath))
648
			Dir_Concat(&s->searchPath, defaultPath);
649
		else
650
417170
			Lst_Clone(&s->searchPath, defaultPath, Dir_CopyDir);
651
	}
652
16853
}
653
654
void
655
process_suffixes_after_makefile_is_read(void)
656
{
657
	/* once the Makefile is finish reading, we can set up the default PATH
658
	 * stuff, and build the final suffixes graph
659
	 */
660
33706
	setup_paths();
661
	/* and we link all transforms to active suffixes at this point. */
662
16853
	build_suffixes_graph();
663
16853
}
664
	  /********** Implicit Source Search Functions *********/
665
666
/*-
667
 *-----------------------------------------------------------------------
668
 * SuffAddSrc  --
669
 *	Add a suffix as a Src structure to the given list with its parent
670
 *	being the given Src structure. If the suffix is the null suffix,
671
 *	the prefix is used unaltered as the file name in the Src structure.
672
 *
673
 * Side Effects:
674
 *	A Src structure is created and tacked onto the end of the list
675
 *-----------------------------------------------------------------------
676
 */
677
static void
678
SuffAddSrc(
679
    void *sp,		/* suffix for which to create a Src structure */
680
    void *lsp)		/* list and parent for the new Src */
681
{
682
4710680
	Suff *s = sp;
683
2355340
	LstSrc *ls = lsp;
684
	Src *s2;	/* new Src structure */
685
	Src *targ;	/* Target structure */
686
687
2355340
	targ = ls->s;
688
689
2355340
	s2 = emalloc(sizeof(Src));
690
2355340
	s2->file = Str_concat(targ->prefix, s->name, 0);
691
2355340
	s2->prefix = targ->prefix;
692
2355340
	s2->parent = targ;
693
2355340
	s2->node = NULL;
694
2355340
	s2->suff = s;
695
2355340
	s2->children = 0;
696
2355340
	targ->children++;
697
2355340
	Lst_AtEnd(ls->l, s2);
698
#ifdef DEBUG_SRC
699
	Lst_Init(&s2->cp);
700
	Lst_AtEnd(&targ->cp, s2);
701
	printf("2 add %x %x to %x:", targ, s2, ls->l);
702
	Lst_Every(ls->l, PrintAddr);
703
	printf("\n");
704
#endif
705
706
2355340
}
707
708
/*-
709
 *-----------------------------------------------------------------------
710
 * SuffAddLevel  --
711
 *	Add all the children of targ as Src structures to the given list
712
 *
713
 * Side Effects:
714
 *	Lots of structures are created and added to the list
715
 *-----------------------------------------------------------------------
716
 */
717
static void
718
SuffAddLevel(
719
    Lst l,	/* list to which to add the new level */
720
    Src *targ)	/* Src structure to use as the parent */
721
{
722
4866220
	LstSrc	   ls;
723
724
2433110
	ls.s = targ;
725
2433110
	ls.l = l;
726
727
2433110
	Lst_ForEach(&targ->suff->children, SuffAddSrc, &ls);
728
2433110
}
729
730
/*-
731
 *----------------------------------------------------------------------
732
 * SuffRemoveSrc --
733
 *	Free all src structures in list that don't have a reference count
734
 *
735
 * Results:
736
 *	Ture if an src was removed
737
 *
738
 * Side Effects:
739
 *	The memory is free'd.
740
 *----------------------------------------------------------------------
741
 */
742
static int
743
SuffRemoveSrc(Lst l)
744
{
745
	LstNode ln;
746
	Src *s;
747
	int t = 0;
748
749
#ifdef DEBUG_SRC
750
	printf("cleaning %lx: ", (unsigned long)l);
751
	Lst_Every(l, PrintAddr);
752
	printf("\n");
753
#endif
754
755
756
14718943
	for (ln = Lst_First(l); ln != NULL; ln = Lst_Adv(ln)) {
757
4818376
		s = Lst_Datum(ln);
758
4818376
		if (s->children == 0) {
759
2700197
			free(s->file);
760
2700197
			if (!s->parent)
761
323308
				free(s->prefix);
762
			else {
763
#ifdef DEBUG_SRC
764
				LstNode ln2 = Lst_Member(&s->parent->cp, s);
765
				if (ln2 != NULL)
766
				    Lst_Remove(&s->parent->cp, ln2);
767
#endif
768
2376889
				--s->parent->children;
769
			}
770
#ifdef DEBUG_SRC
771
			printf("free: [l=%x] p=%x %d\n", l, s, s->children);
772
			Lst_Destroy(&s->cp, NOFREE);
773
#endif
774
2700197
			Lst_Remove(l, ln);
775
2700197
			free(s);
776
			t |= 1;
777
2700197
			return true;
778
		}
779
#ifdef DEBUG_SRC
780
		else {
781
			printf("keep: [l=%x] p=%x %d: ", l, s, s->children);
782
			Lst_Every(&s->cp, PrintAddr);
783
			printf("\n");
784
		}
785
#endif
786
	}
787
788
793998
	return t;
789
3494195
}
790
791
/*-
792
 *-----------------------------------------------------------------------
793
 * SuffFindThem --
794
 *	Find the first existing file/target in the list srcs
795
 *
796
 * Results:
797
 *	The lowest structure in the chain of transformations
798
 *-----------------------------------------------------------------------
799
 */
800
static Src *
801
SuffFindThem(
802
    Lst srcs,	/* list of Src structures to search through */
803
    Lst slst)
804
{
805
	Src *s;		/* current Src */
806
	Src *rs; 	/* returned Src */
807
	char *ptr;
808
809
	rs = NULL;
810
811
4934496
	while ((s = Lst_DeQueue(srcs)) != NULL) {
812
2176467
		if (DEBUG(SUFF))
813
			printf("\ttrying %s...", s->file);
814
815
		/*
816
		 * A file is considered to exist if either a node exists in the
817
		 * graph for it or the file actually exists.
818
		 */
819
2176467
		if (Targ_FindNode(s->file, TARG_NOCREATE) != NULL) {
820
#ifdef DEBUG_SRC
821
			printf("remove %x from %x\n", s, srcs);
822
#endif
823
			rs = s;
824
27660
			break;
825
		}
826
827
4297614
		if ((ptr = Dir_FindFile(s->file, &s->suff->searchPath))
828
2148807
		    != NULL) {
829
			rs = s;
830
#ifdef DEBUG_SRC
831
			printf("remove %x from %x\n", s, srcs);
832
#endif
833
3030
			free(ptr);
834
3030
			break;
835
		}
836
837
2145777
		if (DEBUG(SUFF))
838
		    printf("not there\n");
839
840
2145777
		SuffAddLevel(srcs, s);
841
2145777
		Lst_AtEnd(slst, s);
842
	}
843
844
214314
	if (DEBUG(SUFF) && rs)
845
	    printf("got it\n");
846
214314
	return rs;
847
}
848
849
/*-
850
 *-----------------------------------------------------------------------
851
 * SuffFindCmds --
852
 *	See if any of the children of the target in the Src structure is
853
 *	one from which the target can be transformed. If there is one,
854
 *	a Src structure is put together for it and returned.
855
 *-----------------------------------------------------------------------
856
 */
857
static Src *
858
SuffFindCmds(Src *targ, Lst slst)
859
{
860
	LstNode ln;	/* General-purpose list node */
861
	GNode *t;	/* Target GNode */
862
	GNode *s;	/* Source GNode */
863
	int prefixLen;	/* The length of the defined prefix */
864
	Suff *suff;	/* Suffix on matching beastie */
865
	Src *ret;	/* Return value */
866
	const char *cp;
867
868
98904
	t = targ->node;
869
49452
	prefixLen = strlen(targ->prefix);
870
871
278922
	for (ln = Lst_First(&t->children); ln != NULL; ln = Lst_Adv(ln)) {
872
111558
		s = Lst_Datum(ln);
873
874
111558
		cp = strrchr(s->name, '/');
875
111558
		if (cp == NULL)
876
90701
			cp = s->name;
877
		else
878
20857
			cp++;
879
111558
		if (strncmp(cp, targ->prefix, prefixLen) != 0)
880
			continue;
881
		/* The node matches the prefix ok, see if it has a known
882
		 * suffix.	*/
883
33793
		suff = find_suff(&cp[prefixLen]);
884
33793
		if (suff == NULL)
885
			continue;
886
		/*
887
		 * It even has a known suffix, see if there's a transformation
888
		 * defined between the node's suffix and the target's suffix.
889
		 *
890
		 * XXX: Handle multi-stage transformations here, too.
891
		 */
892
32653
		if (Lst_Member(&suff->parents, targ->suff) == NULL)
893
			continue;
894
		/*
895
		 * Create a new Src structure to describe this transformation
896
		 * (making sure to duplicate the source node's name so
897
		 * Suff_FindDeps can free it again (ick)), and return the new
898
		 * structure.
899
		 */
900
21549
		ret = emalloc(sizeof(Src));
901
21549
		ret->file = estrdup(s->name);
902
21549
		ret->prefix = targ->prefix;
903
21549
		ret->suff = suff;
904
21549
		ret->parent = targ;
905
21549
		ret->node = s;
906
21549
		ret->children = 0;
907
21549
		targ->children++;
908
#ifdef DEBUG_SRC
909
		Lst_Init(&ret->cp);
910
		printf("3 add %x %x\n", targ, ret);
911
		Lst_AtEnd(&targ->cp, ret);
912
#endif
913
21549
		Lst_AtEnd(slst, ret);
914
21549
		if (DEBUG(SUFF))
915
			printf("\tusing existing source %s\n", s->name);
916
21549
		return ret;
917
	}
918
27903
	return NULL;
919
49452
}
920
921
static void
922
SuffLinkParent(GNode *cgn, GNode *pgn)
923
{
924
26806
	Lst_AtEnd(&cgn->parents, pgn);
925

26806
	if (!has_been_built(cgn))
926
9889
		pgn->unmade++;
927
3514
	else if ( ! (cgn->type & (OP_EXEC|OP_USE))) {
928
3514
		if (cgn->built_status == MADE)
929
			pgn->childMade = true;
930
3514
		(void)Make_TimeStamp(pgn, cgn);
931
3514
	}
932
13403
}
933
934
static void
935
SuffExpandVarChildren(LstNode after, GNode *cgn, GNode *pgn)
936
{
937
	GNode *gn;		/* New source 8) */
938
	char *cp;		/* Expanded value */
939
656
	LIST members;
940
941
942
328
	if (DEBUG(SUFF))
943
		printf("Expanding \"%s\"...", cgn->name);
944
945
328
	cp = Var_Subst(cgn->name, &pgn->context, true);
946
328
	if (cp == NULL) {
947
		printf("Problem substituting in %s", cgn->name);
948
		printf("\n");
949
		return;
950
	}
951
952
328
	Lst_Init(&members);
953
954
328
	if (cgn->type & OP_ARCHV) {
955
		/*
956
		 * Node was an archive(member) target, so we want to call
957
		 * on the Arch module to find the nodes for us, expanding
958
		 * variables in the parent's context.
959
		 */
960
		const char *sacrifice = (const char *)cp;
961
962
		(void)Arch_ParseArchive(&sacrifice, &members, &pgn->context);
963
	} else {
964
		/* Break the result into a vector of strings whose nodes
965
		 * we can find, then add those nodes to the members list.
966
		 * Unfortunately, we can't use brk_string because it
967
		 * doesn't understand about variable specifications with
968
		 * spaces in them...  */
969
328
		const char *start, *cp2;
970
971

984
		for (start = cp; *start == ' ' || *start == '\t'; start++)
972
			continue;
973
7216
		for (cp2 = start; *cp2 != '\0';) {
974
3280
			if (ISSPACE(*cp2)) {
975
				/* White-space -- terminate element, find the
976
				 * node, add it, skip any further spaces.  */
977
				gn = Targ_FindNodei(start, cp2, TARG_CREATE);
978
				cp2++;
979
				Lst_AtEnd(&members, gn);
980
				while (ISSPACE(*cp2))
981
					cp2++;
982
				/* Adjust cp2 for increment at start of loop,
983
				 * but set start to first non-space.  */
984
				start = cp2;
985
3280
			} else if (*cp2 == '$')
986
				/* Start of a variable spec -- contact variable
987
				 * module to find the end so we can skip over
988
				 * it.  */
989
				Var_ParseSkip(&cp2, &pgn->context);
990

3280
			else if (*cp2 == '\\' && cp2[1] != '\0')
991
				/* Escaped something -- skip over it.  */
992
				cp2+=2;
993
			else
994
3280
				cp2++;
995
	    }
996
997
328
	    if (cp2 != start) {
998
		    /* Stuff left over -- add it to the list too.  */
999
328
		    gn = Targ_FindNodei(start, cp2, TARG_CREATE);
1000
328
		    Lst_AtEnd(&members, gn);
1001
328
	    }
1002
328
	}
1003
	/* Add all elements of the members list to the parent node.  */
1004
1312
	while ((gn = Lst_DeQueue(&members)) != NULL) {
1005
328
		if (DEBUG(SUFF))
1006
			printf("%s...", gn->name);
1007
328
		if (Lst_Member(&pgn->children, gn) == NULL) {
1008
328
			Lst_Append(&pgn->children, after, gn);
1009
328
			after = Lst_Adv(after);
1010
328
			SuffLinkParent(gn, pgn);
1011
328
		}
1012
	}
1013
	/* Free the result.  */
1014
328
	free(cp);
1015
328
	if (DEBUG(SUFF))
1016
		printf("\n");
1017
656
}
1018
1019
static void
1020
SuffExpandWildChildren(LstNode after, GNode *cgn, GNode *pgn)
1021
{
1022
	Suff *s;
1023
	char *cp;	/* Expanded value */
1024
1025
4
	LIST exp;	/* List of expansions */
1026
	Lst path;	/* Search path along which to expand */
1027
1028
2
	if (DEBUG(SUFF))
1029
		printf("Wildcard expanding \"%s\"...", cgn->name);
1030
1031
	/* Find a path along which to expand the word.
1032
	 *
1033
	 * If the word has a known suffix, use that path.
1034
	 * If it has no known suffix and we're allowed to use the null
1035
	 *	 suffix, use its path.
1036
	 * Else use the default system search path.  */
1037
2
	s = find_best_suffix(cgn->name, cgn->name + strlen(cgn->name));
1038
1039
2
	if (s != NULL) {
1040
		if (DEBUG(SUFF))
1041
			printf("suffix is \"%s\"...", s->name);
1042
		path = &s->searchPath;
1043
	} else
1044
		/* Use default search path.  */
1045
2
		path = defaultPath;
1046
1047
	/* Expand the word along the chosen path. */
1048
2
	Lst_Init(&exp);
1049
2
	Dir_Expand(cgn->name, path, &exp);
1050
1051
	/* Fetch next expansion off the list and find its GNode.  */
1052
840
	while ((cp = Lst_DeQueue(&exp)) != NULL) {
1053
		GNode *gn;		/* New source 8) */
1054
418
		if (DEBUG(SUFF))
1055
			printf("%s...", cp);
1056
418
		gn = Targ_FindNode(cp, TARG_CREATE);
1057
1058
		/* If gn isn't already a child of the parent, make it so and
1059
		 * up the parent's count of unmade children.  */
1060
418
		if (Lst_Member(&pgn->children, gn) == NULL) {
1061
418
			Lst_Append(&pgn->children, after, gn);
1062
418
			after = Lst_Adv(after);
1063
418
			SuffLinkParent(gn, pgn);
1064
418
		}
1065
	}
1066
1067
2
	if (DEBUG(SUFF))
1068
		printf("\n");
1069
2
}
1070
1071
/*-
1072
 *-----------------------------------------------------------------------
1073
 * SuffExpandChildren --
1074
 *	Expand the names of any children of a given node that contain
1075
 *	variable invocations or file wildcards into actual targets.
1076
 *
1077
 * Side Effects:
1078
 *	The expanded node is removed from the parent's list of children,
1079
 *	and the parent's unmade counter is decremented, but other nodes
1080
 *	may be added.
1081
 *-----------------------------------------------------------------------
1082
 */
1083
static void
1084
SuffExpandChildren(LstNode ln, /* LstNode of child, so we can replace it */
1085
    GNode *pgn)
1086
{
1087
944546
	GNode	*cgn = Lst_Datum(ln);
1088
1089
	/* First do variable expansion -- this takes precedence over wildcard
1090
	 * expansion. If the result contains wildcards, they'll be gotten to
1091
	 * later since the resulting words are tacked on to the end of the
1092
	 * children list.  */
1093
472273
	if (strchr(cgn->name, '$') != NULL)
1094
328
		SuffExpandVarChildren(ln, cgn, pgn);
1095
471945
	else if (Dir_HasWildcards(cgn->name))
1096
2
		SuffExpandWildChildren(ln, cgn, pgn);
1097
	else
1098
	    /* Third case: nothing to expand.  */
1099
471943
		return;
1100
1101
	/* Since the source was expanded, remove it from the list of children to
1102
	 * keep it from being processed.  */
1103
330
	pgn->unmade--;
1104
330
	Lst_Remove(&pgn->children, ln);
1105
472603
}
1106
1107
void
1108
expand_children_from(GNode *parent, LstNode from)
1109
{
1110
	LstNode np, ln;
1111
1112
1690235
	for (ln = from; ln != NULL; ln = np) {
1113
472273
		np = Lst_Adv(ln);
1114
472273
		SuffExpandChildren(ln, parent);
1115
	}
1116
248563
}
1117
1118
/*-
1119
 *-----------------------------------------------------------------------
1120
 * SuffApplyTransform --
1121
 *	Apply a transformation rule, given the source and target nodes
1122
 *	and suffixes.
1123
 *
1124
 * Results:
1125
 *	true if successful, false if not.
1126
 *
1127
 * Side Effects:
1128
 *	The source and target are linked and the commands from the
1129
 *	transformation are added to the target node's commands list.
1130
 *	All attributes but OP_DEPMASK and OP_TRANSFORM are applied
1131
 *	to the target. The target also inherits all the sources for
1132
 *	the transformation rule.
1133
 *-----------------------------------------------------------------------
1134
 */
1135
static bool
1136
SuffApplyTransform(
1137
    GNode	*tGn,	/* Target node */
1138
    GNode	*sGn,	/* Source node */
1139
    Suff	*t,	/* Target suffix */
1140
    Suff	*s)	/* Source suffix */
1141
{
1142
	LstNode	ln;	/* General node */
1143
	char	*tname; /* Name of transformation rule */
1144
	GNode	*gn;	/* Node for same */
1145
1146
68498
	if (Lst_AddNew(&tGn->children, sGn)) {
1147
		/* Not already linked, so form the proper links between the
1148
		 * target and source.  */
1149
12657
		SuffLinkParent(sGn, tGn);
1150
12657
	}
1151
1152
34249
	if ((sGn->type & OP_OPMASK) == OP_DOUBLEDEP) {
1153
		/* When a :: node is used as the implied source of a node, we
1154
		 * have to link all its cohorts in as sources as well. There's
1155
		 * only one implied src, as that will be sufficient to get
1156
		 * the .IMPSRC variable set for tGn.	*/
1157
		for (ln=Lst_First(&sGn->cohorts); ln != NULL; ln=Lst_Adv(ln)) {
1158
			gn = Lst_Datum(ln);
1159
1160
			if (Lst_AddNew(&tGn->children, gn)) {
1161
				/* Not already linked, so form the proper links
1162
				 * between the target and source.  */
1163
				SuffLinkParent(gn, tGn);
1164
			}
1165
		}
1166
	}
1167
	/* Locate the transformation rule itself.  */
1168
34249
	tname = Str_concat(s->name, t->name, 0);
1169
34249
	gn = find_transform(tname);
1170
34249
	free(tname);
1171
1172
34249
	if (gn == NULL)
1173
		/*
1174
		 * Not really such a transformation rule (can happen when we're
1175
		 * called to link an OP_MEMBER and OP_ARCHV node), so return
1176
		 * false.
1177
		 */
1178
		return false;
1179
1180
34249
	if (DEBUG(SUFF))
1181
		printf("\tapplying %s -> %s to \"%s\"\n", s->name, t->name,
1182
		    tGn->name);
1183
1184
	/* Record last child for expansion purposes.  */
1185
34249
	ln = Lst_Last(&tGn->children);
1186
1187
	/* Pass the buck to Make_HandleUse to apply the rule.  */
1188
34249
	Make_HandleUse(gn, tGn);
1189
1190
	/* Deal with wildcards and variables in any acquired sources.  */
1191
34249
	expand_children_from(tGn, Lst_Succ(ln));
1192
1193
	/* Keep track of another parent to which this beast is transformed so
1194
	 * the .IMPSRC variable can be set correctly for the parent.  */
1195
34249
	tGn->impliedsrc = sGn;
1196
1197
34249
	return true;
1198
34249
}
1199
1200
static Suff *
1201
find_suffix_as_suffix(Lst l, const char *b, const char *e)
1202
{
1203
	LstNode ln;
1204
	Suff *s;
1205
1206
	for (ln = Lst_First(l); ln != NULL; ln = Lst_Adv(ln)) {
1207
		s = Lst_Datum(ln);
1208
		if (suffix_is_suffix(s, b, e))
1209
			return s;
1210
	}
1211
	return NULL;
1212
}
1213
1214
/*-
1215
 *-----------------------------------------------------------------------
1216
 * SuffFindArchiveDeps --
1217
 *	Locate dependencies for an OP_ARCHV node.
1218
 *
1219
 * Side Effects:
1220
 *	Same as Suff_FindDeps
1221
 *-----------------------------------------------------------------------
1222
 */
1223
static void
1224
SuffFindArchiveDeps(
1225
    GNode	*gn,    /* Node for which to locate dependencies */
1226
    Lst 	slst)
1227
{
1228
	char *eoarch;	/* End of archive portion */
1229
	char *eoname;	/* End of member portion */
1230
	GNode *mem;	/* Node for member */
1231
	Suff *ms;	/* Suffix descriptor for member */
1232
	char *name;	/* Start of member's name */
1233
1234
	/* The node is an archive(member) pair. so we must find a suffix
1235
	 * for both of them.  */
1236
	eoarch = strchr(gn->name, '(');
1237
	if (eoarch == NULL)
1238
		return;
1239
1240
	name = eoarch + 1;
1241
1242
	eoname = strchr(name, ')');
1243
	if (eoname == NULL)
1244
		return;
1245
1246
	/* To simplify things, call Suff_FindDeps recursively on the member now,
1247
	 * so we can simply compare the member's .PREFIX and .TARGET variables
1248
	 * to locate its suffix. This allows us to figure out the suffix to
1249
	 * use for the archive without having to do a quadratic search over the
1250
	 * suffix list, backtracking for each one...  */
1251
	mem = Targ_FindNodei(name, eoname, TARG_CREATE);
1252
	SuffFindDeps(mem, slst);
1253
1254
	/* Create the link between the two nodes right off. */
1255
	if (Lst_AddNew(&gn->children, mem))
1256
		SuffLinkParent(mem, gn);
1257
1258
	/* Copy variables from member node to this one.  */
1259
	Var(TARGET_INDEX, gn) = Var(TARGET_INDEX, mem);
1260
	Var(PREFIX_INDEX, gn) = Var(PREFIX_INDEX, mem);
1261
1262
	ms = mem->suffix;
1263
	if (ms == NULL) {
1264
		/* Didn't know what it was -- use .NULL suffix if not in make
1265
		 * mode.  */
1266
		if (DEBUG(SUFF))
1267
			printf("using empty suffix\n");
1268
		ms = emptySuff;
1269
	}
1270
1271
1272
	/* Set the other two local variables required for this target.  */
1273
	Var(MEMBER_INDEX, gn) = mem->name;
1274
	Var(ARCHIVE_INDEX, gn) = gn->name;
1275
1276
	if (ms != NULL) {
1277
		/*
1278
		 * Member has a known suffix, so look for a transformation rule
1279
		 * from it to a possible suffix of the archive. Rather than
1280
		 * searching through the entire list, we just look at suffixes
1281
		 * to which the member's suffix may be transformed...
1282
		 */
1283
1284
		Suff *suff;
1285
1286
		suff = find_suffix_as_suffix(&ms->parents, gn->name, eoarch);
1287
1288
		if (suff != NULL) {
1289
			/* Got one -- apply it.  */
1290
			if (!SuffApplyTransform(gn, mem, suff, ms) &&
1291
			    DEBUG(SUFF))
1292
				printf("\tNo transformation from %s -> %s\n",
1293
				   ms->name, suff->name);
1294
		}
1295
	}
1296
1297
	/* Pretend gn appeared to the left of a dependency operator so
1298
	 * the user needn't provide a transformation from the member to the
1299
	 * archive.  */
1300
	if (OP_NOP(gn->type))
1301
		gn->type |= OP_DEPENDS;
1302
1303
	/* Flag the member as such so we remember to look in the archive for
1304
	 * its modification time.  */
1305
	mem->type |= OP_MEMBER;
1306
}
1307
1308
static void
1309
record_possible_suffix(Suff *s, GNode *gn, char *eoname, Lst srcs, Lst targs)
1310
{
1311
	int prefixLen;
1312
	Src *targ;
1313
1314
337290
	targ = emalloc(sizeof(Src));
1315
168645
	targ->file = estrdup(gn->name);
1316
168645
	targ->suff = s;
1317
168645
	targ->node = gn;
1318
168645
	targ->parent = NULL;
1319
168645
	targ->children = 0;
1320
#ifdef DEBUG_SRC
1321
	Lst_Init(&targ->cp);
1322
#endif
1323
1324
	/* Allocate room for the prefix, whose end is found by
1325
	 * subtracting the length of the suffix from the end of
1326
	 * the name.  */
1327
168645
	prefixLen = (eoname - targ->suff->nameLen) - gn->name;
1328
168645
	targ->prefix = emalloc(prefixLen + 1);
1329
168645
	memcpy(targ->prefix, gn->name, prefixLen);
1330
168645
	targ->prefix[prefixLen] = '\0';
1331
1332
	/* Add nodes from which the target can be made.  */
1333
168645
	SuffAddLevel(srcs, targ);
1334
1335
	/* Record the target so we can nuke it.  */
1336
168645
	Lst_AtEnd(targs, targ);
1337
168645
}
1338
1339
static void
1340
record_possible_suffixes(GNode *gn, Lst srcs, Lst targs)
1341
{
1342
428628
	char *s = gn->name;
1343
214314
	char *e =  s + strlen(s);
1344
	const char *p;
1345
214314
	uint32_t hv;
1346
	unsigned int slot;
1347
	Suff *suff;
1348
1349
214314
	if (e == s)
1350
		return;
1351
1352
	p = e;
1353
214314
	hv = *--p;
1354
1355
2348952
	while (p != s) {
1356
1151295
		slot = ohash_lookup_interval(&suffixes, p, e, hv);
1357
1151295
		suff = ohash_find(&suffixes, slot);
1358

1321432
		if (suff != NULL && (suff->flags & SUFF_ACTIVE))
1359
168645
			record_possible_suffix(suff, gn, e, srcs, targs);
1360
1151295
		if (e - p >= (ptrdiff_t)maxLen)
1361
			break;
1362
960162
		reverse_hash_add_char(&hv, --p);
1363
	}
1364
428628
}
1365
1366
/*-
1367
 *-----------------------------------------------------------------------
1368
 * SuffFindNormalDeps --
1369
 *	Locate implicit dependencies for regular targets.
1370
 *
1371
 * Side Effects:
1372
 *	Same as Suff_FindDeps...
1373
 *-----------------------------------------------------------------------
1374
 */
1375
static void
1376
SuffFindNormalDeps(
1377
    GNode	*gn,	    /* Node for which to find sources */
1378
    Lst 	slst)
1379
{
1380
428628
	LIST srcs;	/* List of sources at which to look */
1381
214314
	LIST targs;	/* List of targets to which things can be
1382
			 * transformed. They all have the same file,
1383
			 * but different suff and prefix fields */
1384
	Src *bottom;    /* Start of found transformation path */
1385
	Src *src;	/* General Src pointer */
1386
	char *prefix;	/* Prefix to use */
1387
	Src *targ;	/* General Src target pointer */
1388
1389
1390
214314
	Lst_Init(&srcs);
1391
214314
	Lst_Init(&targs);
1392
1393
	/* We're caught in a catch-22 here. On the one hand, we want to use any
1394
	 * transformation implied by the target's sources, but we can't examine
1395
	 * the sources until we've expanded any variables/wildcards they may
1396
	 * hold, and we can't do that until we've set up the target's local
1397
	 * variables and we can't do that until we know what the proper suffix
1398
	 * for the target is (in case there are two suffixes one of which is a
1399
	 * suffix of the other) and we can't know that until we've found its
1400
	 * implied source, which we may not want to use if there's an existing
1401
	 * source that implies a different transformation.
1402
	 *
1403
	 * In an attempt to get around this, which may not work all the time,
1404
	 * but should work most of the time, we look for implied sources first,
1405
	 * checking transformations to all possible suffixes of the target, use
1406
	 * what we find to set the target's local variables, expand the
1407
	 * children, then look for any overriding transformations they imply.
1408
	 * Should we find one, we discard the one we found before.	*/
1409
1410
1411
214314
	record_possible_suffixes(gn, &srcs, &targs);
1412
	/* Handle target of unknown suffix...  */
1413
214314
	if (Lst_IsEmpty(&srcs)) {
1414
154663
		if (DEBUG(SUFF))
1415
			printf("\tNo known suffix on %s. Using empty suffix\n",
1416
			    gn->name);
1417
1418
154663
		targ = emalloc(sizeof(Src));
1419
154663
		targ->file = estrdup(gn->name);
1420
154663
		targ->suff = emptySuff;
1421
154663
		targ->node = gn;
1422
154663
		targ->parent = NULL;
1423
154663
		targ->children = 0;
1424
154663
		targ->prefix = estrdup(gn->name);
1425
#ifdef DEBUG_SRC
1426
		Lst_Init(&targ->cp);
1427
#endif
1428
1429
		/* Only use the default suffix rules if we don't have commands
1430
		 * or dependencies defined for this gnode.  */
1431

281288
		if (Lst_IsEmpty(&gn->commands) && Lst_IsEmpty(&gn->children))
1432
118688
			SuffAddLevel(&srcs, targ);
1433
		else {
1434
35975
			if (DEBUG(SUFF))
1435
				printf("not ");
1436
		}
1437
1438
154663
		if (DEBUG(SUFF))
1439
			printf("adding suffix rules\n");
1440
1441
154663
		Lst_AtEnd(&targs, targ);
1442
154663
	}
1443
1444
	/* Using the list of possible sources built up from the target
1445
	 * suffix(es), try and find an existing file/target that matches.  */
1446
214314
	bottom = SuffFindThem(&srcs, slst);
1447
1448
214314
	if (bottom == NULL) {
1449
		/* No known transformations -- use the first suffix found for
1450
		 * setting the local variables.  */
1451
183624
		if (!Lst_IsEmpty(&targs))
1452
183624
			targ = Lst_Datum(Lst_First(&targs));
1453
		else
1454
			targ = NULL;
1455
	} else {
1456
		/* Work up the transformation path to find the suffix of the
1457
		 * target to which the transformation was made.  */
1458
129846
		for (targ = bottom; targ->parent != NULL; targ = targ->parent)
1459
			continue;
1460
	}
1461
1462
	/* The .TARGET variable we always set to be the name at this point,
1463
	 * since it's only set to the path if the thing is only a source and
1464
	 * if it's only a source, it doesn't matter what we put here as far
1465
	 * as expanding sources is concerned, since it has none...	*/
1466
214314
	Var(TARGET_INDEX, gn) = gn->name;
1467
1468
642942
	prefix = targ != NULL ? estrdup(targ->prefix) : gn->name;
1469
214314
	Var(PREFIX_INDEX, gn) = prefix;
1470
1471
	/* Now we've got the important local variables set, expand any sources
1472
	 * that still contain variables or wildcards in their names.  */
1473
214314
	expand_all_children(gn);
1474
1475
214314
	if (targ == NULL) {
1476
		if (DEBUG(SUFF))
1477
			printf("\tNo valid suffix on %s\n", gn->name);
1478
1479
sfnd_abort:
1480
		/* Deal with finding the thing on the default search path if the
1481
		 * node is only a source (not on the lhs of a dependency operator
1482
		 * or [XXX] it has neither children or commands).  */
1483

296927
		if (OP_NOP(gn->type) ||
1484
141177
		    (Lst_IsEmpty(&gn->children) &&
1485
113319
		    Lst_IsEmpty(&gn->commands))) {
1486
437841
			gn->path = Dir_FindFile(gn->name,
1487
			    (targ == NULL ? defaultPath :
1488
			    &targ->suff->searchPath));
1489
145947
			if (gn->path != NULL) {
1490
				char *ptr;
1491
141640
				Var(TARGET_INDEX, gn) = estrdup(gn->path);
1492
1493
141640
				if (targ != NULL) {
1494
					/* Suffix known for the thing -- trim
1495
					 * the suffix off the path to form the
1496
					 * proper .PREFIX variable.  */
1497
283280
					int savep = strlen(gn->path) -
1498
141640
					    targ->suff->nameLen;
1499
					char savec;
1500
1501
141640
					gn->suffix = targ->suff;
1502
1503
141640
					savec = gn->path[savep];
1504
141640
					gn->path[savep] = '\0';
1505
1506
141640
					if ((ptr = strrchr(gn->path, '/')) !=
1507
					    NULL)
1508
122012
						ptr++;
1509
					else
1510
19628
						ptr = gn->path;
1511
1512
141640
					Var(PREFIX_INDEX, gn) = estrdup(ptr);
1513
1514
141640
					gn->path[savep] = savec;
1515
141640
				} else {
1516
					/* The .PREFIX gets the full path if the
1517
					 * target has no known suffix.  */
1518
					gn->suffix = NULL;
1519
1520
					if ((ptr = strrchr(gn->path, '/')) !=
1521
					    NULL)
1522
						ptr++;
1523
					else
1524
						ptr = gn->path;
1525
1526
					Var(PREFIX_INDEX, gn) = estrdup(ptr);
1527
				}
1528
141640
			}
1529
		} else {
1530
			/* Not appropriate to search for the thing -- set the
1531
			 * path to be the name so Dir_MTime won't go grovelling
1532
			 * for it.  */
1533
112983
			gn->suffix = targ == NULL ? NULL : targ->suff;
1534
37661
			free(gn->path);
1535
37661
			gn->path = estrdup(gn->name);
1536
		}
1537
1538
		goto sfnd_return;
1539
	}
1540
1541
	/* Check for overriding transformation rule implied by sources.  */
1542
214314
	if (!Lst_IsEmpty(&gn->children)) {
1543
49452
		src = SuffFindCmds(targ, slst);
1544
1545
49452
		if (src != NULL) {
1546
			/* Free up all the Src structures in the transformation
1547
			 * path up to, but not including, the parent node.  */
1548

129230
			while (bottom && bottom->parent != NULL) {
1549
21533
				(void)Lst_AddNew(slst, bottom);
1550
21533
				bottom = bottom->parent;
1551
			}
1552
			bottom = src;
1553
21549
		}
1554
	}
1555
1556
214314
	if (bottom == NULL) {
1557
		/* No idea from where it can come -- return now.  */
1558
		goto sfnd_abort;
1559
	}
1560
1561
	/* We now have a list of Src structures headed by 'bottom' and linked
1562
	 * via their 'parent' pointers. What we do next is create links between
1563
	 * source and target nodes (which may or may not have been created) and
1564
	 * set the necessary local variables in each target. The commands for
1565
	 * each target are set from the commands of the transformation rule
1566
	 * used to get from the src suffix to the targ suffix. Note that this
1567
	 * causes the commands list of the original node, gn, to be replaced by
1568
	 * the commands of the final transformation rule. Also, the unmade
1569
	 * field of gn is incremented.  Etc.  */
1570
30706
	if (bottom->node == NULL) {
1571
9157
		bottom->node = Targ_FindNode(bottom->file, TARG_CREATE);
1572
9157
	}
1573
1574
129910
	for (src = bottom; src->parent != NULL; src = src->parent) {
1575
		targ = src->parent;
1576
1577
34249
		src->node->suffix = src->suff;
1578
1579
34249
		if (targ->node == NULL) {
1580
3543
			targ->node = Targ_FindNode(targ->file, TARG_CREATE);
1581
3543
		}
1582
1583
68498
		SuffApplyTransform(targ->node, src->node,
1584
34249
				   targ->suff, src->suff);
1585
1586
34249
		if (targ->node != gn) {
1587
			/* Finish off the dependency-search process for any
1588
			 * nodes between bottom and gn (no point in questing
1589
			 * around the filesystem for their implicit source when
1590
			 * it's already known). Note that the node can't have
1591
			 * any sources that need expanding, since SuffFindThem
1592
			 * will stop on an existing node, so all we need to do
1593
			 * is set the standard and System V variables.  */
1594
3543
			targ->node->type |= OP_DEPS_FOUND;
1595
1596
3543
			Var(PREFIX_INDEX, targ->node) = estrdup(targ->prefix);
1597
1598
3543
			Var(TARGET_INDEX, targ->node) = targ->node->name;
1599
3543
		}
1600
	}
1601
1602
30706
	gn->suffix = src->suff;
1603
1604
	/* So Dir_MTime doesn't go questing for it...  */
1605
30706
	free(gn->path);
1606
30706
	gn->path = estrdup(gn->name);
1607
1608
	/* Nuke the transformation path and the Src structures left over in the
1609
	 * two lists.  */
1610
sfnd_return:
1611
214314
	if (bottom)
1612
30706
		(void)Lst_AddNew(slst, bottom);
1613
1614

1111721
	while (SuffRemoveSrc(&srcs) || SuffRemoveSrc(&targs))
1615
323826
		continue;
1616
1617
214314
	Lst_ConcatDestroy(slst, &srcs);
1618
214314
	Lst_ConcatDestroy(slst, &targs);
1619
214314
}
1620
1621
1622
/*-
1623
 *-----------------------------------------------------------------------
1624
 * Suff_FindDeps  --
1625
 *	Find implicit sources for the target described by the graph node
1626
 *	gn
1627
 *
1628
 * Side Effects:
1629
 *	Nodes are added to the graph below the passed-in node. The nodes
1630
 *	are marked to have their IMPSRC variable filled in. The
1631
 *	PREFIX variable is set for the given node and all its
1632
 *	implied children.
1633
 *
1634
 * Notes:
1635
 *	The path found by this target is the shortest path in the
1636
 *	transformation graph, which may pass through non-existent targets,
1637
 *	to an existing target. The search continues on all paths from the
1638
 *	root suffix until a file is found. I.e. if there's a path
1639
 *	.o -> .c -> .l -> .l,v from the root and the .l,v file exists but
1640
 *	the .c and .l files don't, the search will branch out in
1641
 *	all directions from .o and again from all the nodes on the
1642
 *	next level until the .l,v node is encountered.
1643
 *-----------------------------------------------------------------------
1644
 */
1645
1646
void
1647
Suff_FindDeps(GNode *gn)
1648
{
1649
1650
440834
	SuffFindDeps(gn, &srclist);
1651
2817205
	while (SuffRemoveSrc(&srclist))
1652
2376371
		continue;
1653
220417
}
1654
1655
1656
static void
1657
SuffFindDeps(GNode *gn, Lst slst)
1658
{
1659
440834
	if (gn->type & OP_DEPS_FOUND) {
1660
		/*
1661
		 * If dependencies already found, no need to do it again...
1662
		 */
1663
		return;
1664
	} else {
1665
214314
		gn->type |= OP_DEPS_FOUND;
1666
	}
1667
1668
214314
	if (DEBUG(SUFF))
1669
		printf("SuffFindDeps (%s)\n", gn->name);
1670
1671
214314
	current_node = gn;
1672
214314
	if (gn->type & OP_ARCHV)
1673
		SuffFindArchiveDeps(gn, slst);
1674
	else
1675
214314
		SuffFindNormalDeps(gn, slst);
1676
214314
	current_node = NULL;
1677
434731
}
1678
1679
/*-
1680
 *-----------------------------------------------------------------------
1681
 * Suff_Init --
1682
 *	Initialize suffixes module
1683
 *
1684
 * Side Effects:
1685
 *	Many
1686
 *-----------------------------------------------------------------------
1687
 */
1688
void
1689
Suff_Init(void)
1690
{
1691
	Static_Lst_Init(&srclist);
1692
33706
	ohash_init(&transforms, 4, &gnode_info);
1693
1694
	/*
1695
	 * Create null suffix for single-suffix rules (POSIX). The thing doesn't
1696
	 * actually go on the suffix list or everyone will think that's its
1697
	 * suffix.
1698
	 */
1699
16853
	emptySuff = new_suffix("");
1700
16853
	make_suffix_known(emptySuff);
1701
16853
	Dir_Concat(&emptySuff->searchPath, defaultPath);
1702
16853
	ohash_init(&suffixes, 4, &suff_info);
1703
16853
	order = 0;
1704
16853
	clear_suffixes();
1705
16853
	special_path_hack();
1706
1707
16853
}
1708
1709
1710
/********************* DEBUGGING FUNCTIONS **********************/
1711
1712
static void
1713
SuffPrintName(void *p)
1714
{
1715
	const Suff *s = p;
1716
	printf("%s ", s == emptySuff ? "<empty>" : s->name);
1717
}
1718
1719
static void
1720
SuffPrintSuff(void *sp)
1721
{
1722
	Suff    *s = sp;
1723
1724
	printf("# %-5s ", s->name);
1725
1726
	if (!Lst_IsEmpty(&s->parents)) {
1727
		printf(" ->");
1728
		Lst_Every(&s->parents, SuffPrintName);
1729
	}
1730
	if (!Lst_IsEmpty(&s->children)) {
1731
		printf(" <-");
1732
		Lst_Every(&s->children, SuffPrintName);
1733
	}
1734
	fputc('\n', stdout);
1735
}
1736
1737
static void
1738
SuffPrintTrans(GNode *t)
1739
{
1740
	printf("%-16s: ", t->name);
1741
	Targ_PrintType(t->type);
1742
	fputc('\n', stdout);
1743
	Lst_Every(&t->commands, Targ_PrintCmd);
1744
	fputc('\n', stdout);
1745
}
1746
1747
static int
1748
compare_order(const void *a, const void *b)
1749
{
1750
	const Suff **pa = (const Suff **)a;
1751
	const Suff **pb = (const Suff **)b;
1752
	return (*pb)->order - (*pa)->order;
1753
}
1754
1755
static void
1756
print_path(Suff *s)
1757
{
1758
	/* do we need to print it ? compare against defaultPath */
1759
	LstNode ln1, ln2;
1760
	bool first = true;
1761
1762
	for (ln1 = Lst_First(&s->searchPath), ln2 = Lst_First(defaultPath);
1763
	    ln1 != NULL && ln2 != NULL;
1764
	    ln1 = Lst_Adv(ln1)) {
1765
		if (Lst_Datum(ln1) == Lst_Datum(ln2)) {
1766
			ln2 = Lst_Adv(ln2);
1767
			continue;
1768
		}
1769
		if (first) {
1770
			printf(".PATH%s:", s->name);
1771
			first = false;
1772
		}
1773
		printf(" %s", PathEntry_name(Lst_Datum(ln1)));
1774
	}
1775
	if (!first)
1776
		printf("\n\n");
1777
}
1778
1779
void
1780
Suff_PrintAll(void)
1781
{
1782
	Suff **t;
1783
	GNode **u;
1784
	unsigned int i;
1785
	bool reprint;
1786
1787
1788
	printf("# Suffixes graph\n");
1789
	t = sort_ohash_by_name(&suffixes);
1790
	for (i = 0; t[i] != NULL; i++)
1791
		if (!(t[i]->flags & SUFF_PATH))
1792
			SuffPrintSuff(t[i]);
1793
1794
	printf("\n.PATH: ");
1795
	Dir_PrintPath(defaultPath);
1796
	printf("\n\n");
1797
	for (i = 0; t[i] != NULL; i++)
1798
		if (!(t[i]->flags & SUFF_PATH))
1799
			print_path(t[i]);
1800
	free(t);
1801
1802
	reprint = false;
1803
	t = sort_ohash(&suffixes, compare_order);
1804
	printf(".SUFFIXES:");
1805
	for (i = 0; t[i] != NULL; i++) {
1806
		if (t[i]->flags & SUFF_PATH)
1807
			continue;
1808
		printf(" %s", t[i]->name);
1809
		if (!(t[i]->flags & SUFF_ACTIVE))
1810
			reprint = true;
1811
	}
1812
	printf("\n\n");
1813
	u = sort_ohash_by_name(&transforms);
1814
	for (i = 0; u[i] != NULL; i++)
1815
	    	SuffPrintTrans(u[i]);
1816
	free(u);
1817
1818
	if (reprint) {
1819
		printf(".SUFFIXES:");
1820
		for (i = 0; t[i] != NULL; i++)
1821
			if (t[i]->flags & SUFF_ACTIVE)
1822
				printf(" %s", t[i]->name);
1823
		printf("\n");
1824
	}
1825
	free(t);
1826
}
1827
1828
#ifdef DEBUG_SRC
1829
static void
1830
PrintAddr(void *a)
1831
{
1832
	printf("%lx ", (unsigned long)a);
1833
}
1834
#endif