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