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