1 /* $NetBSD: suff.c,v 1.357 2021/12/12 20:45:48 sjg Exp $ */
4 * Copyright (c) 1988, 1989, 1990, 1993
5 * The Regents of the University of California. All rights reserved.
7 * This code is derived from software contributed to Berkeley by
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
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.
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
36 * Copyright (c) 1989 by Berkeley Softworks
37 * All rights reserved.
39 * This code is derived from software contributed to Berkeley by
42 * Redistribution and use in source and binary forms, with or without
43 * modification, are permitted provided that the following conditions
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.
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
72 * Maintain suffix lists and find implicit dependents using suffix
73 * transformation rules such as ".c.o".
76 * Suff_Init Initialize the module.
78 * Suff_End Clean up the module.
81 * Extend the search path of each suffix to include the
82 * default search path.
85 * Clear out all the suffixes and transformations.
88 * See if the passed string is a transformation rule.
90 * Suff_AddSuffix Add the passed string as another known suffix.
92 * Suff_GetPath Return the search path for the given suffix.
95 * Mark the given suffix as denoting an include file.
97 * Suff_AddLib Mark the given suffix as denoting a library.
100 * Add another transformation to the suffix graph.
102 * Suff_SetNull Define the suffix to consider the suffix of
103 * any file that doesn't have a known one.
105 * Suff_FindDeps Find implicit sources for and the location of
106 * a target based on its suffix. Returns the
107 * bottom-most node added to the graph or NULL
108 * if the target had no implicit sources.
110 * Suff_FindPath Return the appropriate path to search in order to
117 /* "@(#)suff.c 8.4 (Berkeley) 3/21/94" */
118 MAKE_RCSID("$NetBSD: suff.c,v 1.357 2021/12/12 20:45:48 sjg Exp $");
120 typedef List SuffixList;
121 typedef ListNode SuffixListNode;
123 typedef List CandidateList;
124 typedef ListNode CandidateListNode;
126 /* The defined suffixes, such as '.c', '.o', '.l'. */
127 static SuffixList sufflist = LST_INIT;
129 /* The suffixes to be cleaned up at the end. */
130 static SuffixList suffClean = LST_INIT;
134 * The transformation rules, such as '.c.o' to transform '.c' into '.o',
135 * or simply '.c' to transform 'file.c' into 'file'.
137 static GNodeList transforms = LST_INIT;
140 * Counter for assigning suffix numbers.
141 * TODO: What are these suffix numbers used for?
145 typedef List SuffixListList;
148 * A suffix such as ".c" or ".o" that is used in suffix transformation rules
151 typedef struct Suffix {
152 /* The suffix itself, such as ".c" */
154 /* Length of the name, to avoid strlen calls */
157 * This suffix marks include files. Their search path ends up in the
158 * undocumented special variable '.INCLUDES'.
162 * This suffix marks library files. Their search path ends up in the
163 * undocumented special variable '.LIBS'.
169 * XXX: What is the difference between the empty suffix and the null
172 * XXX: Why is SUFF_NULL needed at all? Wouldn't nameLen == 0 mean
176 /* The path along which files of this suffix may be found */
177 SearchPath *searchPath;
179 /* The suffix number; TODO: document the purpose of this number */
181 /* Reference count of list membership and several other places */
184 /* Suffixes we have a transformation to */
186 /* Suffixes we have a transformation from */
189 * Lists in which this suffix is referenced.
191 * XXX: These lists are used nowhere, they are just appended to, for
192 * no apparent reason. They do have the side effect of increasing
199 * A candidate when searching for implied sources.
201 * For example, when "src.o" is to be made, a typical candidate is "src.c"
202 * via the transformation rule ".c.o". If that doesn't exist, maybe there is
203 * another transformation rule ".pas.c" that would make "src.pas" an indirect
204 * candidate as well. The first such chain that leads to an existing file or
205 * node is finally chosen to be made.
207 typedef struct Candidate {
208 /* The file or node to look for. */
210 /* The prefix from which file was formed.
211 * Its memory is shared among all candidates. */
213 /* The suffix on the file. */
216 /* The candidate that can be made from this,
217 * or NULL for the top-level candidate. */
218 struct Candidate *parent;
219 /* The node describing the file. */
222 /* Count of existing children, only used for memory management, so we
223 * don't free this candidate too early or too late. */
226 CandidateList childrenList;
230 typedef struct CandidateSearcher {
235 * TODO: Add HashSet for seen entries, to avoid endless loops such as
236 * in suff-transform-endless.mk.
242 /* TODO: Document the difference between nullSuff and emptySuff. */
243 /* The NULL suffix for this run */
244 static Suffix *nullSuff;
245 /* The empty suffix required for POSIX single-suffix transformation rules */
246 static Suffix *emptySuff;
250 Suffix_Ref(Suffix *suff)
256 /* Change the value of a Suffix variable, adjusting the reference counts. */
258 Suffix_Reassign(Suffix **var, Suffix *suff)
266 /* Set a Suffix variable to NULL, adjusting the reference count. */
268 Suffix_Unassign(Suffix **var)
276 * See if pref is a prefix of str.
277 * Return NULL if it ain't, pointer to character in str after prefix if so.
280 StrTrimPrefix(const char *pref, const char *str)
282 while (*str != '\0' && *pref == *str) {
287 return *pref != '\0' ? NULL : str;
291 * See if suff is a suffix of str, and if so, return the pointer to the suffix
292 * in str, which at the same time marks the end of the prefix.
295 StrTrimSuffix(const char *str, size_t strLen, const char *suff, size_t suffLen)
297 const char *suffInStr;
300 if (strLen < suffLen)
303 suffInStr = str + strLen - suffLen;
304 for (i = 0; i < suffLen; i++)
305 if (suff[i] != suffInStr[i])
312 * See if suff is a suffix of name, and if so, return the end of the prefix
316 Suffix_TrimSuffix(const Suffix *suff, size_t nameLen, const char *nameEnd)
318 return StrTrimSuffix(nameEnd - nameLen, nameLen,
319 suff->name, suff->nameLen);
323 Suffix_IsSuffix(const Suffix *suff, size_t nameLen, const char *nameEnd)
325 return Suffix_TrimSuffix(suff, nameLen, nameEnd) != NULL;
329 FindSuffixByNameLen(const char *name, size_t nameLen)
333 for (ln = sufflist.first; ln != NULL; ln = ln->next) {
334 Suffix *suff = ln->datum;
335 if (suff->nameLen == nameLen &&
336 memcmp(suff->name, name, nameLen) == 0)
343 FindSuffixByName(const char *name)
345 return FindSuffixByNameLen(name, strlen(name));
349 FindTransformByName(const char *name)
353 for (ln = transforms.first; ln != NULL; ln = ln->next) {
354 GNode *gn = ln->datum;
355 if (strcmp(gn->name, name) == 0)
362 SuffixList_Unref(SuffixList *list, Suffix *suff)
364 SuffixListNode *ln = Lst_FindDatum(list, suff);
366 Lst_Remove(list, ln);
371 /* Free up all memory associated with the given suffix structure. */
373 Suffix_Free(Suffix *suff)
376 if (suff == nullSuff)
379 if (suff == emptySuff)
383 /* We don't delete suffixes in order, so we cannot use this */
384 if (suff->refCount != 0)
385 Punt("Internal error deleting suffix `%s' with refcount = %d",
386 suff->name, suff->refCount);
389 Lst_Done(&suff->ref);
390 Lst_Done(&suff->children);
391 Lst_Done(&suff->parents);
392 SearchPath_Free(suff->searchPath);
404 /* Remove the suffix from the list, and free if it is otherwise unused. */
406 SuffixList_Remove(SuffixList *list, Suffix *suff)
408 SuffixList_Unref(list, suff);
409 if (suff->refCount == 0) {
410 /* XXX: can lead to suff->refCount == -1 */
411 SuffixList_Unref(&sufflist, suff);
412 DEBUG1(SUFF, "Removing suffix \"%s\"\n", suff->name);
418 * Insert the suffix into the list, keeping the list ordered by suffix
422 SuffixList_Insert(SuffixList *list, Suffix *suff)
425 Suffix *listSuff = NULL;
427 for (ln = list->first; ln != NULL; ln = ln->next) {
428 listSuff = ln->datum;
429 if (listSuff->sNum >= suff->sNum)
434 DEBUG2(SUFF, "inserting \"%s\" (%d) at end of list\n",
435 suff->name, suff->sNum);
436 Lst_Append(list, Suffix_Ref(suff));
437 Lst_Append(&suff->ref, list);
438 } else if (listSuff->sNum != suff->sNum) {
439 DEBUG4(SUFF, "inserting \"%s\" (%d) before \"%s\" (%d)\n",
440 suff->name, suff->sNum, listSuff->name, listSuff->sNum);
441 Lst_InsertBefore(list, ln, Suffix_Ref(suff));
442 Lst_Append(&suff->ref, list);
444 DEBUG2(SUFF, "\"%s\" (%d) is already there\n",
445 suff->name, suff->sNum);
450 Relate(Suffix *srcSuff, Suffix *targSuff)
452 SuffixList_Insert(&targSuff->children, srcSuff);
453 SuffixList_Insert(&srcSuff->parents, targSuff);
457 Suffix_New(const char *name)
459 Suffix *suff = bmake_malloc(sizeof *suff);
461 suff->name = bmake_strdup(name);
462 suff->nameLen = strlen(suff->name);
463 suff->searchPath = SearchPath_New();
464 Lst_Init(&suff->children);
465 Lst_Init(&suff->parents);
466 Lst_Init(&suff->ref);
468 suff->include = false;
469 suff->library = false;
470 suff->isNull = false;
471 suff->refCount = 1; /* XXX: why 1? It's not assigned anywhere yet. */
477 * Nuke the list of suffixes but keep all transformation rules around. The
478 * transformation graph is destroyed in this process, but we leave the list
479 * of rules so when a new graph is formed, the rules will remain. This
480 * function is called when a line '.SUFFIXES:' with an empty suffixes list is
481 * encountered in a makefile.
484 Suff_ClearSuffixes(void)
487 Lst_MoveAll(&suffClean, &sufflist);
489 DEBUG0(SUFF, "Clearing all suffixes\n");
492 if (nullSuff != NULL)
494 emptySuff = nullSuff = Suffix_New("");
496 SearchPath_AddAll(nullSuff->searchPath, &dirSearchPath);
497 nullSuff->include = false;
498 nullSuff->library = false;
499 nullSuff->isNull = true;
503 * Parse a transformation string such as ".c.o" to find its two component
504 * suffixes (the source ".c" and the target ".o"). If there are no such
505 * suffixes, try a single-suffix transformation as well.
507 * Return true if the string is a valid transformation.
510 ParseTransform(const char *str, Suffix **out_src, Suffix **out_targ)
513 Suffix *single = NULL;
516 * Loop looking first for a suffix that matches the start of the
517 * string and then for one that exactly matches the rest of it. If
518 * we can find two that meet these criteria, we've successfully
521 for (ln = sufflist.first; ln != NULL; ln = ln->next) {
522 Suffix *src = ln->datum;
524 if (StrTrimPrefix(src->name, str) == NULL)
527 if (str[src->nameLen] == '\0') {
530 Suffix *targ = FindSuffixByName(str + src->nameLen);
539 if (single != NULL) {
541 * There was a suffix that encompassed the entire string, so we
542 * assume it was a transformation to the null suffix (thank you
543 * POSIX; search for "single suffix" or "single-suffix").
545 * We still prefer to find a double rule over a singleton,
546 * hence we leave this check until the end.
548 * XXX: Use emptySuff over nullSuff?
551 *out_targ = nullSuff;
558 * Return true if the given string is a transformation rule, that is, a
559 * concatenation of two known suffixes such as ".c.o" or a single suffix
563 Suff_IsTransform(const char *str)
567 return ParseTransform(str, &src, &targ);
571 * Add the transformation rule to the list of rules and place the
572 * transformation itself in the graph.
574 * The transformation is linked to the two suffixes mentioned in the name.
577 * name must have the form ".from.to" or just ".from"
580 * The created or existing transformation node in the transforms list
583 Suff_AddTransform(const char *name)
588 GNode *gn = FindTransformByName(name);
591 * Make a new graph node for the transformation. It will be
592 * filled in by the Parse module.
594 gn = GNode_New(name);
595 Lst_Append(&transforms, gn);
598 * New specification for transformation rule. Just nuke the
599 * old list of commands so they can be filled in again. We
600 * don't actually free the commands themselves, because a
601 * given command can be attached to several different
604 Lst_Done(&gn->commands);
605 Lst_Init(&gn->commands);
606 Lst_Done(&gn->children);
607 Lst_Init(&gn->children);
610 gn->type = OP_TRANSFORM;
613 /* TODO: Avoid the redundant parsing here. */
614 bool ok = ParseTransform(name, &srcSuff, &targSuff);
616 /* LINTED 129 *//* expression has null effect */
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);
629 * Handle the finish of a transformation definition, removing the
630 * transformation from the graph if it has neither commands nor sources.
632 * If the node has no commands or children, the children and parents lists
633 * of the affected suffixes are altered.
636 * gn Node for transformation
639 Suff_EndTransform(GNode *gn)
641 Suffix *srcSuff, *targSuff;
642 SuffixList *srcSuffParents;
644 if ((gn->type & OP_DOUBLEDEP) && !Lst_IsEmpty(&gn->cohorts))
645 gn = gn->cohorts.last->datum;
647 if (!(gn->type & OP_TRANSFORM))
650 if (!Lst_IsEmpty(&gn->commands) || !Lst_IsEmpty(&gn->children)) {
651 DEBUG1(SUFF, "transformation %s complete\n", gn->name);
656 * SuffParseTransform() may fail for special rules which are not
657 * actual transformation rules. (e.g. .DEFAULT)
659 if (!ParseTransform(gn->name, &srcSuff, &targSuff))
662 DEBUG2(SUFF, "deleting incomplete transformation from `%s' to `%s'\n",
663 srcSuff->name, targSuff->name);
666 * Remember the parents since srcSuff could be deleted in
669 srcSuffParents = &srcSuff->parents;
670 SuffixList_Remove(&targSuff->children, srcSuff);
671 SuffixList_Remove(srcSuffParents, targSuff);
675 * Called from Suff_AddSuffix to search through the list of
676 * existing transformation rules and rebuild the transformation graph when
677 * it has been destroyed by Suff_ClearSuffixes. If the given rule is a
678 * transformation involving this suffix and another, existing suffix, the
679 * proper relationship is established between the two.
681 * The appropriate links will be made between this suffix and others if
682 * transformation rules exist for it.
685 * transform Transformation to test
686 * suff Suffix to rebuild
689 RebuildGraph(GNode *transform, Suffix *suff)
691 const char *name = transform->name;
692 size_t nameLen = strlen(name);
695 /* See if it is a transformation from this suffix to another suffix. */
696 toName = StrTrimPrefix(suff->name, name);
697 if (toName != NULL) {
698 Suffix *to = FindSuffixByName(toName);
705 /* See if it is a transformation from another suffix to this suffix. */
706 toName = Suffix_TrimSuffix(suff, nameLen, name + nameLen);
707 if (toName != NULL) {
708 Suffix *from = FindSuffixByNameLen(name,
709 (size_t)(toName - name));
716 * During Suff_AddSuffix, search through the list of existing targets and find
717 * if any of the existing targets can be turned into a transformation rule.
719 * If such a target is found and the target is the current main target, the
720 * main target is set to NULL and the next target examined (if that exists)
721 * becomes the main target.
724 * true iff a new main target has been selected.
727 UpdateTarget(GNode *target, GNode **inout_main, Suffix *suff,
728 bool *inout_removedMain)
730 Suffix *srcSuff, *targSuff;
733 if (*inout_main == NULL && *inout_removedMain &&
734 !(target->type & OP_NOTARGET)) {
735 DEBUG1(MAKE, "Setting main node to \"%s\"\n", target->name);
736 *inout_main = target;
737 Targ_SetMain(target);
739 * XXX: Why could it be a good idea to return true here?
740 * The main task of this function is to turn ordinary nodes
741 * into transformations, no matter whether or not a new .MAIN
742 * node has been found.
745 * XXX: Even when changing this to false, none of the existing
751 if (target->type == OP_TRANSFORM)
755 * XXX: What about a transformation ".cpp.c"? If ".c" is added as
756 * a new suffix, it seems wrong that this transformation would be
757 * skipped just because ".c" happens to be a prefix of ".cpp".
759 ptr = strstr(target->name, suff->name);
764 * XXX: In suff-rebuild.mk, in the line '.SUFFIXES: .c .b .a', this
765 * condition prevents the rule '.b.c' from being added again during
766 * Suff_AddSuffix(".b").
768 * XXX: Removing this paragraph makes suff-add-later.mk use massive
771 if (ptr == target->name)
774 if (ParseTransform(target->name, &srcSuff, &targSuff)) {
775 if (*inout_main == target) {
777 "Setting main node from \"%s\" back to null\n",
779 *inout_removedMain = true;
783 Lst_Done(&target->children);
784 Lst_Init(&target->children);
785 target->type = OP_TRANSFORM;
788 * Link the two together in the proper relationship and order.
790 DEBUG2(SUFF, "defining transformation from `%s' to `%s'\n",
791 srcSuff->name, targSuff->name);
792 Relate(srcSuff, targSuff);
798 * Look at all existing targets to see if adding this suffix will make one
799 * of the current targets mutate into a suffix rule.
801 * This is ugly, but other makes treat all targets that start with a '.' as
805 UpdateTargets(GNode **inout_main, Suffix *suff)
807 bool removedMain = false;
810 for (ln = Targ_List()->first; ln != NULL; ln = ln->next) {
811 GNode *gn = ln->datum;
812 if (UpdateTarget(gn, inout_main, suff, &removedMain))
818 * Add the suffix to the end of the list of known suffixes.
819 * Should we restructure the suffix graph? Make doesn't.
821 * A GNode is created for the suffix (XXX: this sounds completely wrong) and
822 * a Suffix structure is created and added to the suffixes list unless the
823 * suffix was already known.
824 * The mainNode passed can be modified if a target mutated into a
825 * transform and that target happened to be the main target.
828 * name the name of the suffix to add
831 Suff_AddSuffix(const char *name, GNode **inout_main)
835 Suffix *suff = FindSuffixByName(name);
839 suff = Suffix_New(name);
840 Lst_Append(&sufflist, suff);
841 DEBUG1(SUFF, "Adding suffix \"%s\"\n", suff->name);
843 UpdateTargets(inout_main, suff);
846 * Look for any existing transformations from or to this suffix.
847 * XXX: Only do this after a Suff_ClearSuffixes?
849 for (ln = transforms.first; ln != NULL; ln = ln->next)
850 RebuildGraph(ln->datum, suff);
853 /* Return the search path for the given suffix, or NULL. */
855 Suff_GetPath(const char *sname)
857 Suffix *suff = FindSuffixByName(sname);
858 return suff != NULL ? suff->searchPath : NULL;
862 * Extend the search paths for all suffixes to include the default search
863 * path (dirSearchPath).
865 * The default search path can be defined using the special target '.PATH'.
866 * The search path of each suffix can be defined using the special target
869 * If paths were specified for the ".h" suffix, the directories are stuffed
870 * into a global variable called ".INCLUDES" with each directory preceded by
871 * '-I'. The same is done for the ".a" suffix, except the variable is called
872 * ".LIBS" and the flag is '-L'.
875 Suff_ExtendPaths(void)
879 SearchPath *includesPath = SearchPath_New();
880 SearchPath *libsPath = SearchPath_New();
882 for (ln = sufflist.first; ln != NULL; ln = ln->next) {
883 Suffix *suff = ln->datum;
884 if (!Lst_IsEmpty(&suff->searchPath->dirs)) {
887 SearchPath_AddAll(includesPath,
892 SearchPath_AddAll(libsPath, suff->searchPath);
894 SearchPath_AddAll(suff->searchPath, &dirSearchPath);
896 SearchPath_Free(suff->searchPath);
897 suff->searchPath = Dir_CopyDirSearchPath();
901 flags = SearchPath_ToFlags(includesPath, "-I");
902 Global_Set(".INCLUDES", flags);
905 flags = SearchPath_ToFlags(libsPath, "-L");
906 Global_Set(".LIBS", flags);
909 SearchPath_Free(includesPath);
910 SearchPath_Free(libsPath);
914 * Add the given suffix as a type of file which gets included.
915 * Called when a '.INCLUDES: .h' line is parsed.
916 * To have an effect, the suffix must already exist.
917 * This affects the magic variable '.INCLUDES'.
920 Suff_AddInclude(const char *suffName)
922 Suffix *suff = FindSuffixByName(suffName);
924 suff->include = true;
928 * Add the given suffix as a type of file which is a library.
929 * Called when a '.LIBS: .a' line is parsed.
930 * To have an effect, the suffix must already exist.
931 * This affects the magic variable '.LIBS'.
934 Suff_AddLib(const char *suffName)
936 Suffix *suff = FindSuffixByName(suffName);
938 suff->library = true;
941 /********** Implicit Source Search Functions *********/
944 CandidateSearcher_Init(CandidateSearcher *cs)
950 CandidateSearcher_Done(CandidateSearcher *cs)
956 CandidateSearcher_Add(CandidateSearcher *cs, Candidate *cand)
958 /* TODO: filter duplicates */
959 Lst_Append(&cs->list, cand);
963 CandidateSearcher_AddIfNew(CandidateSearcher *cs, Candidate *cand)
965 /* TODO: filter duplicates */
966 if (Lst_FindDatum(&cs->list, cand) == NULL)
967 Lst_Append(&cs->list, cand);
971 CandidateSearcher_MoveAll(CandidateSearcher *cs, CandidateList *list)
973 /* TODO: filter duplicates */
974 Lst_MoveAll(&cs->list, list);
980 CandidateList_PrintAddrs(CandidateList *list)
982 CandidateListNode *ln;
984 for (ln = list->first; ln != NULL; ln = ln->next) {
985 Candidate *cand = ln->datum;
986 debug_printf(" %p:%s", cand, cand->file);
993 Candidate_New(char *name, char *prefix, Suffix *suff, Candidate *parent,
996 Candidate *cand = bmake_malloc(sizeof *cand);
999 cand->prefix = prefix;
1000 cand->suff = Suffix_Ref(suff);
1001 cand->parent = parent;
1003 cand->numChildren = 0;
1005 Lst_Init(&cand->childrenList);
1011 /* Add a new candidate to the list. */
1014 CandidateList_Add(CandidateList *list, char *srcName, Candidate *targ,
1015 Suffix *suff, const char *debug_tag)
1017 Candidate *cand = Candidate_New(srcName, targ->prefix, suff, targ,
1019 targ->numChildren++;
1020 Lst_Append(list, cand);
1023 Lst_Append(&targ->childrenList, cand);
1024 debug_printf("%s add suff %p:%s candidate %p:%s to list %p:",
1025 debug_tag, targ, targ->file, cand, cand->file, list);
1026 CandidateList_PrintAddrs(list);
1031 * Add all candidates to the list that can be formed by applying a suffix to
1035 CandidateList_AddCandidatesFor(CandidateList *list, Candidate *cand)
1038 for (ln = cand->suff->children.first; ln != NULL; ln = ln->next) {
1039 Suffix *suff = ln->datum;
1041 if (suff->isNull && suff->name[0] != '\0') {
1043 * If the suffix has been marked as the NULL suffix,
1044 * also create a candidate for a file with no suffix
1047 CandidateList_Add(list, bmake_strdup(cand->prefix),
1051 CandidateList_Add(list, str_concat2(cand->prefix, suff->name),
1057 * Free the first candidate in the list that is not referenced anymore.
1058 * Return whether a candidate was removed.
1061 RemoveCandidate(CandidateList *srcs)
1063 CandidateListNode *ln;
1066 debug_printf("cleaning list %p:", srcs);
1067 CandidateList_PrintAddrs(srcs);
1070 for (ln = srcs->first; ln != NULL; ln = ln->next) {
1071 Candidate *src = ln->datum;
1073 if (src->numChildren == 0) {
1074 if (src->parent == NULL)
1078 /* XXX: Lst_RemoveDatum */
1079 CandidateListNode *ln2;
1080 ln2 = Lst_FindDatum(&src->parent->childrenList,
1083 Lst_Remove(&src->parent->childrenList,
1086 src->parent->numChildren--;
1089 debug_printf("free: list %p src %p:%s children %d\n",
1090 srcs, src, src->file, src->numChildren);
1091 Lst_Done(&src->childrenList);
1093 Lst_Remove(srcs, ln);
1100 debug_printf("keep: list %p src %p:%s children %d:",
1101 srcs, src, src->file, src->numChildren);
1102 CandidateList_PrintAddrs(&src->childrenList);
1110 /* Find the first existing file/target in srcs. */
1112 FindThem(CandidateList *srcs, CandidateSearcher *cs)
1116 HashSet_Init(&seen);
1118 while (!Lst_IsEmpty(srcs)) {
1119 Candidate *src = Lst_Dequeue(srcs);
1122 debug_printf("remove from list %p src %p:%s\n",
1123 srcs, src, src->file);
1125 DEBUG1(SUFF, "\ttrying %s...", src->file);
1128 * A file is considered to exist if either a node exists in the
1129 * graph for it or the file actually exists.
1131 if (Targ_FindNode(src->file) != NULL) {
1133 HashSet_Done(&seen);
1134 DEBUG0(SUFF, "got it\n");
1139 char *file = Dir_FindFile(src->file,
1140 src->suff->searchPath);
1147 DEBUG0(SUFF, "not there\n");
1149 if (HashSet_Add(&seen, src->file))
1150 CandidateList_AddCandidatesFor(srcs, src);
1152 DEBUG1(SUFF, "FindThem: skipping duplicate \"%s\"\n",
1156 CandidateSearcher_Add(cs, src);
1159 HashSet_Done(&seen);
1164 * See if any of the children of the candidate's GNode is one from which the
1165 * target can be transformed. If there is one, a candidate is put together
1166 * for it and returned.
1169 FindCmds(Candidate *targ, CandidateSearcher *cs)
1172 GNode *tgn; /* Target GNode */
1173 GNode *sgn; /* Source GNode */
1174 size_t prefLen; /* The length of the defined prefix */
1175 Suffix *suff; /* Suffix of the matching candidate */
1176 Candidate *ret; /* Return value */
1179 prefLen = strlen(targ->prefix);
1181 for (gln = tgn->children.first; gln != NULL; gln = gln->next) {
1186 if (sgn->type & OP_OPTIONAL && Lst_IsEmpty(&tgn->commands)) {
1188 * We haven't looked to see if .OPTIONAL files exist
1189 * yet, so don't use one as the implicit source.
1190 * This allows us to use .OPTIONAL in .depend files so
1191 * make won't complain "don't know how to make xxx.h"
1192 * when a dependent file has been moved/deleted.
1197 base = str_basename(sgn->name);
1198 if (strncmp(base, targ->prefix, prefLen) != 0)
1200 /* The node matches the prefix, see if it has a known suffix. */
1201 suff = FindSuffixByName(base + prefLen);
1206 * It even has a known suffix, see if there's a transformation
1207 * defined between the node's suffix and the target's suffix.
1209 * XXX: Handle multi-stage transformations here, too.
1212 if (Lst_FindDatum(&suff->parents, targ->suff) != NULL)
1219 ret = Candidate_New(bmake_strdup(sgn->name), targ->prefix, suff, targ,
1221 targ->numChildren++;
1223 debug_printf("3 add targ %p:%s ret %p:%s\n",
1224 targ, targ->file, ret, ret->file);
1225 Lst_Append(&targ->childrenList, ret);
1227 CandidateSearcher_Add(cs, ret);
1228 DEBUG1(SUFF, "\tusing existing source %s\n", sgn->name);
1233 ExpandWildcards(GNodeListNode *cln, GNode *pgn)
1235 GNode *cgn = cln->datum;
1236 StringList expansions;
1238 if (!Dir_HasWildcards(cgn->name))
1242 * Expand the word along the chosen path
1244 Lst_Init(&expansions);
1245 SearchPath_Expand(Suff_FindPath(cgn), cgn->name, &expansions);
1247 while (!Lst_IsEmpty(&expansions)) {
1250 * Fetch next expansion off the list and find its GNode
1252 char *cp = Lst_Dequeue(&expansions);
1254 DEBUG1(SUFF, "%s...", cp);
1255 gn = Targ_GetNode(cp);
1257 /* Add gn to the parents child list before the original child */
1258 Lst_InsertBefore(&pgn->children, cln, gn);
1259 Lst_Append(&gn->parents, pgn);
1263 Lst_Done(&expansions);
1268 * Now the source is expanded, remove it from the list of children to
1269 * keep it from being processed.
1272 Lst_Remove(&pgn->children, cln);
1273 Lst_Remove(&cgn->parents, Lst_FindDatum(&cgn->parents, pgn));
1277 * Break the result into a vector of strings whose nodes we can find, then
1278 * add those nodes to the members list.
1280 * Unfortunately, we can't use Str_Words because it doesn't understand about
1281 * variable expressions with spaces in them.
1284 ExpandChildrenRegular(char *cp, GNode *pgn, GNodeList *members)
1288 pp_skip_hspace(&cp);
1290 while (*cp != '\0') {
1291 if (*cp == ' ' || *cp == '\t') {
1294 * White-space -- terminate element, find the node,
1295 * add it, skip any further spaces.
1298 gn = Targ_GetNode(start);
1299 Lst_Append(members, gn);
1300 pp_skip_hspace(&cp);
1301 /* Continue at the next non-space. */
1303 } else if (*cp == '$') {
1304 /* Skip over the variable expression. */
1305 const char *nested_p = cp;
1308 (void)Var_Parse(&nested_p, pgn, VARE_PARSE_ONLY, &junk);
1309 /* TODO: handle errors */
1310 if (junk.str == var_Error) {
1311 Parse_Error(PARSE_FATAL,
1312 "Malformed variable expression at \"%s\"",
1316 cp += nested_p - cp;
1320 } else if (cp[0] == '\\' && cp[1] != '\0') {
1321 /* Escaped something -- skip over it. */
1323 * XXX: In other places, escaping at this syntactical
1324 * position is done by a '$', not a '\'. The '\' is
1325 * only used in variable modifiers.
1335 * Stuff left over -- add it to the list too
1337 GNode *gn = Targ_GetNode(start);
1338 Lst_Append(members, gn);
1343 * Expand the names of any children of a given node that contain variable
1344 * expressions or file wildcards into actual targets.
1346 * The expanded node is removed from the parent's list of children, and the
1347 * parent's unmade counter is decremented, but other nodes may be added.
1350 * cln Child to examine
1351 * pgn Parent node being processed
1354 ExpandChildren(GNodeListNode *cln, GNode *pgn)
1356 GNode *cgn = cln->datum;
1357 char *cp; /* Expanded value */
1359 if (!Lst_IsEmpty(&cgn->order_pred) || !Lst_IsEmpty(&cgn->order_succ))
1360 /* It is all too hard to process the result of .ORDER */
1363 if (cgn->type & OP_WAIT)
1364 /* Ignore these (& OP_PHONY ?) */
1368 * First do variable expansion -- this takes precedence over wildcard
1369 * expansion. If the result contains wildcards, they'll be gotten to
1370 * later since the resulting words are tacked on to the end of the
1373 if (strchr(cgn->name, '$') == NULL) {
1374 ExpandWildcards(cln, pgn);
1378 DEBUG1(SUFF, "Expanding \"%s\"...", cgn->name);
1379 (void)Var_Subst(cgn->name, pgn, VARE_UNDEFERR, &cp);
1380 /* TODO: handle errors */
1383 GNodeList members = LST_INIT;
1385 if (cgn->type & OP_ARCHV) {
1387 * Node was an 'archive(member)' target, so
1388 * call on the Arch module to find the nodes for us,
1389 * expanding variables in the parent's scope.
1392 (void)Arch_ParseArchive(&p, &members, pgn);
1394 ExpandChildrenRegular(cp, pgn, &members);
1398 * Add all elements of the members list to the parent node.
1400 while (!Lst_IsEmpty(&members)) {
1401 GNode *gn = Lst_Dequeue(&members);
1403 DEBUG1(SUFF, "%s...", gn->name);
1405 * Add gn to the parents child list before the
1408 Lst_InsertBefore(&pgn->children, cln, gn);
1409 Lst_Append(&gn->parents, pgn);
1411 /* Expand wildcards on new node */
1412 ExpandWildcards(cln->prev, pgn);
1422 * Now the source is expanded, remove it from the list of children to
1423 * keep it from being processed.
1426 Lst_Remove(&pgn->children, cln);
1427 Lst_Remove(&cgn->parents, Lst_FindDatum(&cgn->parents, pgn));
1431 ExpandAllChildren(GNode *gn)
1433 GNodeListNode *ln, *nln;
1435 for (ln = gn->children.first; ln != NULL; ln = nln) {
1437 ExpandChildren(ln, gn);
1442 * Find a path along which to expand the node.
1444 * If the node has a known suffix, use that path.
1445 * If it has no known suffix, use the default system search path.
1448 * gn Node being examined
1451 * The appropriate path to search for the GNode.
1454 Suff_FindPath(GNode *gn)
1456 Suffix *suff = gn->suffix;
1459 char *name = gn->name;
1460 size_t nameLen = strlen(gn->name);
1462 for (ln = sufflist.first; ln != NULL; ln = ln->next)
1463 if (Suffix_IsSuffix(ln->datum, nameLen, name + nameLen))
1466 DEBUG1(SUFF, "Wildcard expanding \"%s\"...", gn->name);
1470 * XXX: Here we can save the suffix so we don't have to do
1476 DEBUG1(SUFF, "suffix is \"%s\"...\n", suff->name);
1477 return suff->searchPath;
1480 return &dirSearchPath; /* Use default search path */
1485 * Apply a transformation rule, given the source and target nodes and
1488 * The source and target are linked and the commands from the transformation
1489 * are added to the target node's commands list. The target also inherits all
1490 * the sources for the transformation rule.
1493 * true if successful, false if not.
1496 ApplyTransform(GNode *tgn, GNode *sgn, Suffix *tsuff, Suffix *ssuff)
1499 char *tname; /* Name of transformation rule */
1500 GNode *gn; /* Node for the transformation rule */
1502 /* Form the proper links between the target and source. */
1503 Lst_Append(&tgn->children, sgn);
1504 Lst_Append(&sgn->parents, tgn);
1507 /* Locate the transformation rule itself. */
1508 tname = str_concat2(ssuff->name, tsuff->name);
1509 gn = FindTransformByName(tname);
1512 /* This can happen when linking an OP_MEMBER and OP_ARCHV node. */
1516 DEBUG3(SUFF, "\tapplying %s -> %s to \"%s\"\n",
1517 ssuff->name, tsuff->name, tgn->name);
1519 /* Record last child; Make_HandleUse may add child nodes. */
1520 ln = tgn->children.last;
1522 /* Apply the rule. */
1523 Make_HandleUse(gn, tgn);
1525 /* Deal with wildcards and variables in any acquired sources. */
1526 ln = ln != NULL ? ln->next : NULL;
1527 while (ln != NULL) {
1528 GNodeListNode *nln = ln->next;
1529 ExpandChildren(ln, tgn);
1534 * Keep track of another parent to which this node is transformed so
1535 * the .IMPSRC variable can be set correctly for the parent.
1537 Lst_Append(&sgn->implicitParents, tgn);
1543 * Member has a known suffix, so look for a transformation rule from
1544 * it to a possible suffix of the archive.
1546 * Rather than searching through the entire list, we just look at
1547 * suffixes to which the member's suffix may be transformed.
1550 ExpandMember(GNode *gn, const char *eoarch, GNode *mem, Suffix *memSuff)
1553 size_t nameLen = (size_t)(eoarch - gn->name);
1555 /* Use first matching suffix... */
1556 for (ln = memSuff->parents.first; ln != NULL; ln = ln->next)
1557 if (Suffix_IsSuffix(ln->datum, nameLen, eoarch))
1561 /* Got one -- apply it */
1562 Suffix *suff = ln->datum;
1563 if (!ApplyTransform(gn, mem, suff, memSuff)) {
1564 DEBUG2(SUFF, "\tNo transformation from %s -> %s\n",
1565 memSuff->name, suff->name);
1570 static void FindDeps(GNode *, CandidateSearcher *);
1573 * Locate dependencies for an OP_ARCHV node.
1576 * gn Node for which to locate dependencies
1579 * Same as Suff_FindDeps
1582 FindDepsArchive(GNode *gn, CandidateSearcher *cs)
1584 char *eoarch; /* End of archive portion */
1585 char *eoname; /* End of member portion */
1586 GNode *mem; /* Node for member */
1588 const char *name; /* Start of member's name */
1591 * The node is an archive(member) pair. so we must find a
1592 * suffix for both of them.
1594 eoarch = strchr(gn->name, '(');
1595 eoname = strchr(eoarch, ')');
1598 * Caller guarantees the format `libname(member)', via
1599 * Arch_ParseArchive.
1601 assert(eoarch != NULL);
1602 assert(eoname != NULL);
1604 *eoname = '\0'; /* Nuke parentheses during suffix search */
1605 *eoarch = '\0'; /* So a suffix can be found */
1610 * To simplify things, call Suff_FindDeps recursively on the member
1611 * now, so we can simply compare the member's .PREFIX and .TARGET
1612 * variables to locate its suffix. This allows us to figure out the
1613 * suffix to use for the archive without having to do a quadratic
1614 * search over the suffix list, backtracking for each one.
1616 mem = Targ_GetNode(name);
1619 /* Create the link between the two nodes right off. */
1620 Lst_Append(&gn->children, mem);
1621 Lst_Append(&mem->parents, gn);
1624 /* Copy in the variables from the member node to this one. */
1625 Var_Set(gn, PREFIX, GNode_VarPrefix(mem));
1626 Var_Set(gn, TARGET, GNode_VarTarget(mem));
1628 memSuff = mem->suffix;
1629 if (memSuff == NULL) { /* Didn't know what it was. */
1630 DEBUG0(SUFF, "using null suffix\n");
1635 /* Set the other two local variables required for this target. */
1636 Var_Set(gn, MEMBER, name);
1637 Var_Set(gn, ARCHIVE, gn->name);
1638 /* Set $@ for compatibility with other makes. */
1639 Var_Set(gn, TARGET, gn->name);
1642 * Now we've got the important local variables set, expand any sources
1643 * that still contain variables or wildcards in their names.
1645 ExpandAllChildren(gn);
1647 if (memSuff != NULL)
1648 ExpandMember(gn, eoarch, mem, memSuff);
1651 * Replace the opening and closing parens now we've no need of the
1658 * Pretend gn appeared to the left of a dependency operator so the
1659 * user needn't provide a transformation from the member to the
1662 if (!GNode_IsTarget(gn))
1663 gn->type |= OP_DEPENDS;
1666 * Flag the member as such so we remember to look in the archive for
1667 * its modification time. The OP_JOIN | OP_MADE is needed because
1668 * this target should never get made.
1670 mem->type |= OP_MEMBER | OP_JOIN | OP_MADE;
1674 * If the node is a library, it is the arch module's job to find it
1675 * and set the TARGET variable accordingly. We merely provide the
1676 * search path, assuming all libraries end in ".a" (if the suffix
1677 * hasn't been defined, there's nothing we can do for it, so we just
1678 * set the TARGET variable to the node's name in order to give it a
1682 FindDepsLib(GNode *gn)
1684 Suffix *suff = FindSuffixByName(LIBSUFF);
1686 Suffix_Reassign(&gn->suffix, suff);
1687 Arch_FindLib(gn, suff->searchPath);
1689 Suffix_Unassign(&gn->suffix);
1690 Var_Set(gn, TARGET, gn->name);
1694 * Because a library (-lfoo) target doesn't follow the standard
1695 * filesystem conventions, we don't set the regular variables for
1696 * the thing. .PREFIX is simply made empty.
1698 Var_Set(gn, PREFIX, "");
1702 FindDepsRegularKnown(const char *name, size_t nameLen, GNode *gn,
1703 CandidateList *srcs, CandidateList *targs)
1709 for (ln = sufflist.first; ln != NULL; ln = ln->next) {
1710 Suffix *suff = ln->datum;
1711 if (!Suffix_IsSuffix(suff, nameLen, name + nameLen))
1714 pref = bmake_strldup(name, (size_t)(nameLen - suff->nameLen));
1715 targ = Candidate_New(bmake_strdup(gn->name), pref, suff, NULL,
1718 CandidateList_AddCandidatesFor(srcs, targ);
1720 /* Record the target so we can nuke it. */
1721 Lst_Append(targs, targ);
1726 FindDepsRegularUnknown(GNode *gn, const char *sopref,
1727 CandidateList *srcs, CandidateList *targs)
1731 if (!Lst_IsEmpty(targs) || nullSuff == NULL)
1734 DEBUG1(SUFF, "\tNo known suffix on %s. Using .NULL suffix\n", gn->name);
1736 targ = Candidate_New(bmake_strdup(gn->name), bmake_strdup(sopref),
1737 nullSuff, NULL, gn);
1740 * Only use the default suffix rules if we don't have commands
1741 * defined for this gnode; traditional make programs used to not
1742 * define suffix rules if the gnode had children but we don't do
1745 if (Lst_IsEmpty(&gn->commands))
1746 CandidateList_AddCandidatesFor(srcs, targ);
1748 DEBUG0(SUFF, "not ");
1751 DEBUG0(SUFF, "adding suffix rules\n");
1753 Lst_Append(targs, targ);
1757 * Deal with finding the thing on the default search path. We always do
1758 * that, not only if the node is only a source (not on the lhs of a
1759 * dependency operator or [XXX] it has neither children or commands) as
1760 * the old pmake did.
1763 FindDepsRegularPath(GNode *gn, Candidate *targ)
1765 if (gn->type & (OP_PHONY | OP_NOPATH))
1769 gn->path = Dir_FindFile(gn->name,
1770 (targ == NULL ? &dirSearchPath :
1771 targ->suff->searchPath));
1772 if (gn->path == NULL)
1775 Var_Set(gn, TARGET, gn->path);
1779 * Suffix known for the thing -- trim the suffix off
1780 * the path to form the proper .PREFIX variable.
1782 size_t savep = strlen(gn->path) - targ->suff->nameLen;
1785 Suffix_Reassign(&gn->suffix, targ->suff);
1787 savec = gn->path[savep];
1788 gn->path[savep] = '\0';
1790 Var_Set(gn, PREFIX, str_basename(gn->path));
1792 gn->path[savep] = savec;
1795 * The .PREFIX gets the full path if the target has no
1798 Suffix_Unassign(&gn->suffix);
1799 Var_Set(gn, PREFIX, str_basename(gn->path));
1804 * Locate implicit dependencies for regular targets.
1807 * gn Node for which to find sources
1810 * Same as Suff_FindDeps
1813 FindDepsRegular(GNode *gn, CandidateSearcher *cs)
1815 /* List of sources at which to look */
1816 CandidateList srcs = LST_INIT;
1818 * List of targets to which things can be transformed.
1819 * They all have the same file, but different suff and prefix fields.
1821 CandidateList targs = LST_INIT;
1822 Candidate *bottom; /* Start of found transformation path */
1826 const char *name = gn->name;
1827 size_t nameLen = strlen(name);
1830 DEBUG1(SUFF, "FindDepsRegular \"%s\"\n", gn->name);
1834 * We're caught in a catch-22 here. On the one hand, we want to use
1835 * any transformation implied by the target's sources, but we can't
1836 * examine the sources until we've expanded any variables/wildcards
1837 * they may hold, and we can't do that until we've set up the
1838 * target's local variables and we can't do that until we know what
1839 * the proper suffix for the target is (in case there are two
1840 * suffixes one of which is a suffix of the other) and we can't know
1841 * that until we've found its implied source, which we may not want
1842 * to use if there's an existing source that implies a different
1845 * In an attempt to get around this, which may not work all the time,
1846 * but should work most of the time, we look for implied sources
1847 * first, checking transformations to all possible suffixes of the
1848 * target, use what we find to set the target's local variables,
1849 * expand the children, then look for any overriding transformations
1850 * they imply. Should we find one, we discard the one we found before.
1855 if (!(gn->type & OP_PHONY)) {
1857 FindDepsRegularKnown(name, nameLen, gn, &srcs, &targs);
1859 /* Handle target of unknown suffix... */
1860 FindDepsRegularUnknown(gn, name, &srcs, &targs);
1863 * Using the list of possible sources built up from the target
1864 * suffix(es), try and find an existing file/target that
1867 bottom = FindThem(&srcs, cs);
1869 if (bottom == NULL) {
1871 * No known transformations -- use the first suffix
1872 * found for setting the local variables.
1874 if (targs.first != NULL)
1875 targ = targs.first->datum;
1880 * Work up the transformation path to find the suffix
1881 * of the target to which the transformation was made.
1884 targ->parent != NULL; targ = targ->parent)
1889 Var_Set(gn, TARGET, GNode_Path(gn));
1890 Var_Set(gn, PREFIX, targ != NULL ? targ->prefix : gn->name);
1893 * Now we've got the important local variables set, expand any sources
1894 * that still contain variables or wildcards in their names.
1897 GNodeListNode *ln, *nln;
1898 for (ln = gn->children.first; ln != NULL; ln = nln) {
1900 ExpandChildren(ln, gn);
1905 DEBUG1(SUFF, "\tNo valid suffix on %s\n", gn->name);
1908 FindDepsRegularPath(gn, targ);
1913 * If the suffix indicates that the target is a library, mark that in
1914 * the node's type field.
1916 if (targ->suff->library)
1920 * Check for overriding transformation rule implied by sources
1922 if (!Lst_IsEmpty(&gn->children)) {
1923 src = FindCmds(targ, cs);
1927 * Free up all the candidates in the transformation
1928 * path, up to but not including the parent node.
1930 while (bottom != NULL && bottom->parent != NULL) {
1931 CandidateSearcher_AddIfNew(cs, bottom);
1932 bottom = bottom->parent;
1938 if (bottom == NULL) {
1939 /* No idea from where it can come -- return now. */
1944 * We now have a list of candidates headed by 'bottom' and linked via
1945 * their 'parent' pointers. What we do next is create links between
1946 * source and target nodes (which may or may not have been created)
1947 * and set the necessary local variables in each target.
1949 * The commands for each target are set from the commands of the
1950 * transformation rule used to get from the src suffix to the targ
1951 * suffix. Note that this causes the commands list of the original
1952 * node, gn, to be replaced with the commands of the final
1953 * transformation rule.
1955 if (bottom->node == NULL)
1956 bottom->node = Targ_GetNode(bottom->file);
1958 for (src = bottom; src->parent != NULL; src = src->parent) {
1961 Suffix_Reassign(&src->node->suffix, src->suff);
1963 if (targ->node == NULL)
1964 targ->node = Targ_GetNode(targ->file);
1966 ApplyTransform(targ->node, src->node,
1967 targ->suff, src->suff);
1969 if (targ->node != gn) {
1971 * Finish off the dependency-search process for any
1972 * nodes between bottom and gn (no point in questing
1973 * around the filesystem for their implicit source
1974 * when it's already known). Note that the node
1975 * can't have any sources that need expanding, since
1976 * SuffFindThem will stop on an existing node, so all
1977 * we need to do is set the standard variables.
1979 targ->node->type |= OP_DEPS_FOUND;
1980 Var_Set(targ->node, PREFIX, targ->prefix);
1981 Var_Set(targ->node, TARGET, targ->node->name);
1985 Suffix_Reassign(&gn->suffix, src->suff);
1988 * Nuke the transformation path and the candidates left over in the
1993 CandidateSearcher_AddIfNew(cs, bottom);
1995 while (RemoveCandidate(&srcs) || RemoveCandidate(&targs))
1998 CandidateSearcher_MoveAll(cs, &srcs);
1999 CandidateSearcher_MoveAll(cs, &targs);
2003 CandidateSearcher_CleanUp(CandidateSearcher *cs)
2005 while (RemoveCandidate(&cs->list))
2007 assert(Lst_IsEmpty(&cs->list));
2012 * Find implicit sources for the target.
2014 * Nodes are added to the graph as children of the passed-in node. The nodes
2015 * are marked to have their IMPSRC variable filled in. The PREFIX variable
2016 * is set for the given node and all its implied children.
2018 * The path found by this target is the shortest path in the transformation
2019 * graph, which may pass through nonexistent targets, to an existing target.
2020 * The search continues on all paths from the root suffix until a file is
2021 * found. I.e. if there's a path .o -> .c -> .l -> .l,v from the root and the
2022 * .l,v file exists but the .c and .l files don't, the search will branch out
2023 * in all directions from .o and again from all the nodes on the next level
2024 * until the .l,v node is encountered.
2027 Suff_FindDeps(GNode *gn)
2029 CandidateSearcher cs;
2031 CandidateSearcher_Init(&cs);
2035 CandidateSearcher_CleanUp(&cs);
2036 CandidateSearcher_Done(&cs);
2040 FindDeps(GNode *gn, CandidateSearcher *cs)
2042 if (gn->type & OP_DEPS_FOUND)
2044 gn->type |= OP_DEPS_FOUND;
2046 /* Make sure we have these set, may get revised below. */
2047 Var_Set(gn, TARGET, GNode_Path(gn));
2048 Var_Set(gn, PREFIX, gn->name);
2050 DEBUG1(SUFF, "SuffFindDeps \"%s\"\n", gn->name);
2052 if (gn->type & OP_ARCHV)
2053 FindDepsArchive(gn, cs);
2054 else if (gn->type & OP_LIB)
2057 FindDepsRegular(gn, cs);
2061 * Define which suffix is the null suffix.
2063 * Need to handle the changing of the null suffix gracefully so the old
2064 * transformation rules don't just go away.
2067 * name Name of null suffix
2070 Suff_SetNull(const char *name)
2072 Suffix *suff = FindSuffixByName(name);
2074 Parse_Error(PARSE_WARNING,
2075 "Desired null suffix %s not defined",
2080 if (nullSuff != NULL)
2081 nullSuff->isNull = false;
2082 suff->isNull = true;
2083 /* XXX: Here's where the transformation mangling would take place. */
2087 /* Initialize the suffixes module. */
2092 * Create null suffix for single-suffix rules (POSIX). The thing
2093 * doesn't actually go on the suffix list or everyone will think
2094 * that's its suffix.
2096 Suff_ClearSuffixes();
2100 /* Clean up the suffixes module. */
2105 Lst_DoneCall(&sufflist, SuffFree);
2106 Lst_DoneCall(&suffClean, SuffFree);
2107 if (nullSuff != NULL)
2109 Lst_Done(&transforms);
2115 PrintSuffNames(const char *prefix, const SuffixList *suffs)
2119 debug_printf("#\t%s: ", prefix);
2120 for (ln = suffs->first; ln != NULL; ln = ln->next) {
2121 const Suffix *suff = ln->datum;
2122 debug_printf("%s ", suff->name);
2128 Suffix_Print(const Suffix *suff)
2132 Buf_InitSize(&buf, 16);
2133 Buf_AddFlag(&buf, suff->include, "SUFF_INCLUDE");
2134 Buf_AddFlag(&buf, suff->library, "SUFF_LIBRARY");
2135 Buf_AddFlag(&buf, suff->isNull, "SUFF_NULL");
2137 debug_printf("# \"%s\" (num %d, ref %d)",
2138 suff->name, suff->sNum, suff->refCount);
2140 debug_printf(" (%s)", buf.data);
2145 PrintSuffNames("To", &suff->parents);
2146 PrintSuffNames("From", &suff->children);
2148 debug_printf("#\tSearch Path: ");
2149 SearchPath_Print(suff->searchPath);
2154 PrintTransformation(GNode *t)
2156 debug_printf("%-16s:", t->name);
2157 Targ_PrintType(t->type);
2166 debug_printf("#*** Suffixes:\n");
2169 for (ln = sufflist.first; ln != NULL; ln = ln->next)
2170 Suffix_Print(ln->datum);
2173 debug_printf("#*** Transformations:\n");
2176 for (ln = transforms.first; ln != NULL; ln = ln->next)
2177 PrintTransformation(ln->datum);
2188 Buf_InitSize(&buf, 16);
2189 for (ln = sufflist.first; ln != NULL; ln = ln->next) {
2191 if (ln != sufflist.first)
2192 Buf_AddByte(&buf, ' ');
2193 Buf_AddStr(&buf, suff->name);
2195 return Buf_DoneData(&buf);