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