1 /* $NetBSD: suff.c,v 1.368 2023/02/14 21:38:31 rillig 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.368 2023/02/14 21:38:31 rillig 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 may be used in suffix transformation
149 * rules such as ".c.o:".
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. */
211 * The prefix from which file was formed. Its memory is shared among
215 /* The suffix on the file. */
219 * The candidate that can be made from this, or NULL for the
220 * top-level candidate.
222 struct Candidate *parent;
223 /* The node describing the file. */
227 * Count of existing children, only used for memory management, so we
228 * don't free this candidate too early or too late.
232 CandidateList childrenList;
236 typedef struct CandidateSearcher {
241 * TODO: Add HashSet for seen entries, to avoid endless loops such as
242 * in suff-transform-endless.mk.
248 /* TODO: Document the difference between nullSuff and emptySuff. */
249 /* The NULL suffix is used when a file has no known suffix */
250 static Suffix *nullSuff;
251 /* The empty suffix required for POSIX single-suffix transformation rules */
252 static Suffix *emptySuff;
256 Suffix_Ref(Suffix *suff)
262 /* Change the value of a Suffix variable, adjusting the reference counts. */
264 Suffix_Reassign(Suffix **var, Suffix *suff)
272 /* Set a Suffix variable to NULL, adjusting the reference count. */
274 Suffix_Unassign(Suffix **var)
282 * See if pref is a prefix of str.
283 * Return NULL if it ain't, pointer to character in str after prefix if so.
286 StrTrimPrefix(const char *pref, const char *str)
288 while (*str != '\0' && *pref == *str) {
293 return *pref != '\0' ? NULL : str;
297 * See if suff is a suffix of str, and if so, return the pointer to the suffix
298 * in str, which at the same time marks the end of the prefix.
301 StrTrimSuffix(const char *str, size_t strLen, const char *suff, size_t suffLen)
303 const char *suffInStr;
306 if (strLen < suffLen)
309 suffInStr = str + strLen - suffLen;
310 for (i = 0; i < suffLen; i++)
311 if (suff[i] != suffInStr[i])
318 * See if suff is a suffix of name, and if so, return the end of the prefix
322 Suffix_TrimSuffix(const Suffix *suff, size_t nameLen, const char *nameEnd)
324 return StrTrimSuffix(nameEnd - nameLen, nameLen,
325 suff->name, suff->nameLen);
329 Suffix_IsSuffix(const Suffix *suff, size_t nameLen, const char *nameEnd)
331 return Suffix_TrimSuffix(suff, nameLen, nameEnd) != NULL;
335 FindSuffixByNameLen(const char *name, size_t nameLen)
339 for (ln = sufflist.first; ln != NULL; ln = ln->next) {
340 Suffix *suff = ln->datum;
341 if (suff->nameLen == nameLen &&
342 memcmp(suff->name, name, nameLen) == 0)
349 FindSuffixByName(const char *name)
351 return FindSuffixByNameLen(name, strlen(name));
355 FindTransformByName(const char *name)
359 for (ln = transforms.first; ln != NULL; ln = ln->next) {
360 GNode *gn = ln->datum;
361 if (strcmp(gn->name, name) == 0)
368 SuffixList_Unref(SuffixList *list, Suffix *suff)
370 SuffixListNode *ln = Lst_FindDatum(list, suff);
372 Lst_Remove(list, ln);
377 /* Free up all memory associated with the given suffix structure. */
379 Suffix_Free(Suffix *suff)
382 if (suff == nullSuff)
385 if (suff == emptySuff)
389 /* We don't delete suffixes in order, so we cannot use this */
390 if (suff->refCount != 0)
391 Punt("Internal error deleting suffix `%s' with refcount = %d",
392 suff->name, suff->refCount);
395 Lst_Done(&suff->ref);
396 Lst_Done(&suff->children);
397 Lst_Done(&suff->parents);
398 SearchPath_Free(suff->searchPath);
410 /* Remove the suffix from the list, and free if it is otherwise unused. */
412 SuffixList_Remove(SuffixList *list, Suffix *suff)
414 SuffixList_Unref(list, suff);
415 if (suff->refCount == 0) {
416 /* XXX: can lead to suff->refCount == -1 */
417 SuffixList_Unref(&sufflist, suff);
418 DEBUG1(SUFF, "Removing suffix \"%s\"\n", suff->name);
424 * Insert the suffix into the list, keeping the list ordered by suffix
428 SuffixList_Insert(SuffixList *list, Suffix *suff)
431 Suffix *listSuff = NULL;
433 for (ln = list->first; ln != NULL; ln = ln->next) {
434 listSuff = ln->datum;
435 if (listSuff->sNum >= suff->sNum)
440 DEBUG2(SUFF, "inserting \"%s\" (%d) at end of list\n",
441 suff->name, suff->sNum);
442 Lst_Append(list, Suffix_Ref(suff));
443 Lst_Append(&suff->ref, list);
444 } else if (listSuff->sNum != suff->sNum) {
445 DEBUG4(SUFF, "inserting \"%s\" (%d) before \"%s\" (%d)\n",
446 suff->name, suff->sNum, listSuff->name, listSuff->sNum);
447 Lst_InsertBefore(list, ln, Suffix_Ref(suff));
448 Lst_Append(&suff->ref, list);
450 DEBUG2(SUFF, "\"%s\" (%d) is already there\n",
451 suff->name, suff->sNum);
456 Relate(Suffix *srcSuff, Suffix *targSuff)
458 SuffixList_Insert(&targSuff->children, srcSuff);
459 SuffixList_Insert(&srcSuff->parents, targSuff);
463 Suffix_New(const char *name)
465 Suffix *suff = bmake_malloc(sizeof *suff);
467 suff->name = bmake_strdup(name);
468 suff->nameLen = strlen(suff->name);
469 suff->searchPath = SearchPath_New();
470 Lst_Init(&suff->children);
471 Lst_Init(&suff->parents);
472 Lst_Init(&suff->ref);
474 suff->include = false;
475 suff->library = false;
476 suff->isNull = false;
477 suff->refCount = 1; /* XXX: why 1? It's not assigned anywhere yet. */
483 * Nuke the list of suffixes but keep all transformation rules around. The
484 * transformation graph is destroyed in this process, but we leave the list
485 * of rules so when a new graph is formed, the rules will remain. This
486 * function is called when a line '.SUFFIXES:' with an empty suffixes list is
487 * encountered in a makefile.
490 Suff_ClearSuffixes(void)
493 Lst_MoveAll(&suffClean, &sufflist);
495 DEBUG0(SUFF, "Clearing all suffixes\n");
498 if (nullSuff != NULL)
500 emptySuff = nullSuff = Suffix_New("");
502 SearchPath_AddAll(nullSuff->searchPath, &dirSearchPath);
503 nullSuff->include = false;
504 nullSuff->library = false;
505 nullSuff->isNull = true;
509 * Parse a transformation string such as ".c.o" to find its two component
510 * suffixes (the source ".c" and the target ".o"). If there are no such
511 * suffixes, try a single-suffix transformation as well.
513 * Return true if the string is a valid transformation.
516 ParseTransform(const char *str, Suffix **out_src, Suffix **out_targ)
519 Suffix *single = NULL;
522 * Loop looking first for a suffix that matches the start of the
523 * string and then for one that exactly matches the rest of it. If
524 * we can find two that meet these criteria, we've successfully
527 for (ln = sufflist.first; ln != NULL; ln = ln->next) {
528 Suffix *src = ln->datum;
530 if (StrTrimPrefix(src->name, str) == NULL)
533 if (str[src->nameLen] == '\0') {
536 Suffix *targ = FindSuffixByName(str + src->nameLen);
545 if (single != NULL) {
547 * There was a suffix that encompassed the entire string, so we
548 * assume it was a transformation to the null suffix (thank you
549 * POSIX; search for "single suffix" or "single-suffix").
551 * We still prefer to find a double rule over a singleton,
552 * hence we leave this check until the end.
554 * XXX: Use emptySuff over nullSuff?
557 *out_targ = nullSuff;
564 * Return true if the given string is a transformation rule, that is, a
565 * concatenation of two known suffixes such as ".c.o" or a single suffix
569 Suff_IsTransform(const char *str)
573 return ParseTransform(str, &src, &targ);
577 * Add the transformation rule to the list of rules and place the
578 * transformation itself in the graph.
580 * The transformation is linked to the two suffixes mentioned in the name.
583 * name must have the form ".from.to" or just ".from"
586 * The created or existing transformation node in the transforms list
589 Suff_AddTransform(const char *name)
594 GNode *gn = FindTransformByName(name);
597 * Make a new graph node for the transformation. It will be
598 * filled in by the Parse module.
600 gn = GNode_New(name);
601 Lst_Append(&transforms, gn);
604 * New specification for transformation rule. Just nuke the
605 * old list of commands so they can be filled in again. We
606 * don't actually free the commands themselves, because a
607 * given command can be attached to several different
610 Lst_Done(&gn->commands);
611 Lst_Init(&gn->commands);
612 Lst_Done(&gn->children);
613 Lst_Init(&gn->children);
616 gn->type = OP_TRANSFORM;
619 /* TODO: Avoid the redundant parsing here. */
620 bool ok = ParseTransform(name, &srcSuff, &targSuff);
622 /* LINTED 129 *//* expression has null effect */
626 /* Link the two together in the proper relationship and order. */
627 DEBUG2(SUFF, "defining transformation from `%s' to `%s'\n",
628 srcSuff->name, targSuff->name);
629 Relate(srcSuff, targSuff);
635 * Handle the finish of a transformation definition, removing the
636 * transformation from the graph if it has neither commands nor sources.
638 * If the node has no commands or children, the children and parents lists
639 * of the affected suffixes are altered.
642 * gn Node for transformation
645 Suff_EndTransform(GNode *gn)
647 Suffix *srcSuff, *targSuff;
648 SuffixList *srcSuffParents;
650 if ((gn->type & OP_DOUBLEDEP) && !Lst_IsEmpty(&gn->cohorts))
651 gn = gn->cohorts.last->datum;
653 if (!(gn->type & OP_TRANSFORM))
656 if (!Lst_IsEmpty(&gn->commands) || !Lst_IsEmpty(&gn->children)) {
657 DEBUG1(SUFF, "transformation %s complete\n", gn->name);
662 * SuffParseTransform() may fail for special rules which are not
663 * actual transformation rules. (e.g. .DEFAULT)
665 if (!ParseTransform(gn->name, &srcSuff, &targSuff))
668 DEBUG2(SUFF, "deleting incomplete transformation from `%s' to `%s'\n",
669 srcSuff->name, targSuff->name);
672 * Remember the parents since srcSuff could be deleted in
675 srcSuffParents = &srcSuff->parents;
676 SuffixList_Remove(&targSuff->children, srcSuff);
677 SuffixList_Remove(srcSuffParents, targSuff);
681 * Called from Suff_AddSuffix to search through the list of
682 * existing transformation rules and rebuild the transformation graph when
683 * it has been destroyed by Suff_ClearSuffixes. If the given rule is a
684 * transformation involving this suffix and another, existing suffix, the
685 * proper relationship is established between the two.
687 * The appropriate links will be made between this suffix and others if
688 * transformation rules exist for it.
691 * transform Transformation to test
692 * suff Suffix to rebuild
695 RebuildGraph(GNode *transform, Suffix *suff)
697 const char *name = transform->name;
698 size_t nameLen = strlen(name);
702 * See if it is a transformation from this suffix to another suffix.
704 toName = StrTrimPrefix(suff->name, name);
705 if (toName != NULL) {
706 Suffix *to = FindSuffixByName(toName);
714 * See if it is a transformation from another suffix to this suffix.
716 toName = Suffix_TrimSuffix(suff, nameLen, name + nameLen);
717 if (toName != NULL) {
718 Suffix *from = FindSuffixByNameLen(name,
719 (size_t)(toName - name));
726 * During Suff_AddSuffix, search through the list of existing targets and find
727 * if any of the existing targets can be turned into a transformation rule.
729 * If such a target is found and the target is the current main target, the
730 * main target is set to NULL and the next target examined (if that exists)
731 * becomes the main target.
734 * true iff a new main target has been selected.
737 UpdateTarget(GNode *target, Suffix *suff, bool *inout_removedMain)
739 Suffix *srcSuff, *targSuff;
742 if (mainNode == NULL && *inout_removedMain &&
743 GNode_IsMainCandidate(target)) {
744 DEBUG1(MAKE, "Setting main node to \"%s\"\n", target->name);
747 * XXX: Why could it be a good idea to return true here?
748 * The main task of this function is to turn ordinary nodes
749 * into transformations, no matter whether or not a new .MAIN
750 * node has been found.
753 * XXX: Even when changing this to false, none of the existing
759 if (target->type == OP_TRANSFORM)
763 * XXX: What about a transformation ".cpp.c"? If ".c" is added as
764 * a new suffix, it seems wrong that this transformation would be
765 * skipped just because ".c" happens to be a prefix of ".cpp".
767 ptr = strstr(target->name, suff->name);
772 * XXX: In suff-rebuild.mk, in the line '.SUFFIXES: .c .b .a', this
773 * condition prevents the rule '.b.c' from being added again during
774 * Suff_AddSuffix(".b").
776 * XXX: Removing this paragraph makes suff-add-later.mk use massive
779 if (ptr == target->name)
782 if (ParseTransform(target->name, &srcSuff, &targSuff)) {
783 if (mainNode == target) {
785 "Setting main node from \"%s\" back to null\n",
787 *inout_removedMain = true;
790 Lst_Done(&target->children);
791 Lst_Init(&target->children);
792 target->type = OP_TRANSFORM;
795 * Link the two together in the proper relationship and order.
797 DEBUG2(SUFF, "defining transformation from `%s' to `%s'\n",
798 srcSuff->name, targSuff->name);
799 Relate(srcSuff, targSuff);
805 * Look at all existing targets to see if adding this suffix will make one
806 * of the current targets mutate into a suffix rule.
808 * This is ugly, but other makes treat all targets that start with a '.' as
812 UpdateTargets(Suffix *suff)
814 bool removedMain = false;
817 for (ln = Targ_List()->first; ln != NULL; ln = ln->next) {
818 GNode *gn = ln->datum;
819 if (UpdateTarget(gn, suff, &removedMain))
825 * Add the suffix to the end of the list of known suffixes.
826 * Should we restructure the suffix graph? Make doesn't.
828 * A GNode is created for the suffix (XXX: this sounds completely wrong) and
829 * a Suffix structure is created and added to the suffixes list unless the
830 * suffix was already known.
831 * The mainNode passed can be modified if a target mutated into a
832 * transform and that target happened to be the main target.
835 * name the name of the suffix to add
838 Suff_AddSuffix(const char *name)
842 Suffix *suff = FindSuffixByName(name);
846 suff = Suffix_New(name);
847 Lst_Append(&sufflist, suff);
848 DEBUG1(SUFF, "Adding suffix \"%s\"\n", suff->name);
853 * Look for any existing transformations from or to this suffix.
854 * XXX: Only do this after a Suff_ClearSuffixes?
856 for (ln = transforms.first; ln != NULL; ln = ln->next)
857 RebuildGraph(ln->datum, suff);
860 /* Return the search path for the given suffix, or NULL. */
862 Suff_GetPath(const char *name)
864 Suffix *suff = FindSuffixByName(name);
865 return suff != NULL ? suff->searchPath : NULL;
869 * Extend the search paths for all suffixes to include the default search
870 * path (dirSearchPath).
872 * The default search path can be defined using the special target '.PATH'.
873 * The search path of each suffix can be defined using the special target
876 * If paths were specified for the ".h" suffix, the directories are stuffed
877 * into a global variable called ".INCLUDES" with each directory preceded by
878 * '-I'. The same is done for the ".a" suffix, except the variable is called
879 * ".LIBS" and the flag is '-L'.
882 Suff_ExtendPaths(void)
886 SearchPath *includesPath = SearchPath_New();
887 SearchPath *libsPath = SearchPath_New();
889 for (ln = sufflist.first; ln != NULL; ln = ln->next) {
890 Suffix *suff = ln->datum;
891 if (!Lst_IsEmpty(&suff->searchPath->dirs)) {
894 SearchPath_AddAll(includesPath,
899 SearchPath_AddAll(libsPath, suff->searchPath);
901 SearchPath_AddAll(suff->searchPath, &dirSearchPath);
903 SearchPath_Free(suff->searchPath);
904 suff->searchPath = Dir_CopyDirSearchPath();
908 flags = SearchPath_ToFlags(includesPath, "-I");
909 Global_Set(".INCLUDES", flags);
912 flags = SearchPath_ToFlags(libsPath, "-L");
913 Global_Set(".LIBS", flags);
916 SearchPath_Free(includesPath);
917 SearchPath_Free(libsPath);
921 * Add the given suffix as a type of file which gets included.
922 * Called when a '.INCLUDES: .h' line is parsed.
923 * To have an effect, the suffix must already exist.
924 * This affects the magic variable '.INCLUDES'.
927 Suff_AddInclude(const char *suffName)
929 Suffix *suff = FindSuffixByName(suffName);
931 suff->include = true;
935 * Add the given suffix as a type of file which is a library.
936 * Called when a '.LIBS: .a' line is parsed.
937 * To have an effect, the suffix must already exist.
938 * This affects the magic variable '.LIBS'.
941 Suff_AddLib(const char *suffName)
943 Suffix *suff = FindSuffixByName(suffName);
945 suff->library = true;
948 /********** Implicit Source Search Functions *********/
951 CandidateSearcher_Init(CandidateSearcher *cs)
957 CandidateSearcher_Done(CandidateSearcher *cs)
963 CandidateSearcher_Add(CandidateSearcher *cs, Candidate *cand)
965 /* TODO: filter duplicates */
966 Lst_Append(&cs->list, cand);
970 CandidateSearcher_AddIfNew(CandidateSearcher *cs, Candidate *cand)
972 /* TODO: filter duplicates */
973 if (Lst_FindDatum(&cs->list, cand) == NULL)
974 Lst_Append(&cs->list, cand);
978 CandidateSearcher_MoveAll(CandidateSearcher *cs, CandidateList *list)
980 /* TODO: filter duplicates */
981 Lst_MoveAll(&cs->list, list);
987 CandidateList_PrintAddrs(CandidateList *list)
989 CandidateListNode *ln;
991 for (ln = list->first; ln != NULL; ln = ln->next) {
992 Candidate *cand = ln->datum;
993 debug_printf(" %p:%s", cand, cand->file);
1000 Candidate_New(char *name, char *prefix, Suffix *suff, Candidate *parent,
1003 Candidate *cand = bmake_malloc(sizeof *cand);
1006 cand->prefix = prefix;
1007 cand->suff = Suffix_Ref(suff);
1008 cand->parent = parent;
1010 cand->numChildren = 0;
1012 Lst_Init(&cand->childrenList);
1018 /* Add a new candidate to the list. */
1021 CandidateList_Add(CandidateList *list, char *srcName, Candidate *targ,
1022 Suffix *suff, const char *debug_tag MAKE_ATTR_UNUSED)
1024 Candidate *cand = Candidate_New(srcName, targ->prefix, suff, targ,
1026 targ->numChildren++;
1027 Lst_Append(list, cand);
1030 Lst_Append(&targ->childrenList, cand);
1031 debug_printf("%s add suff %p:%s candidate %p:%s to list %p:",
1032 debug_tag, targ, targ->file, cand, cand->file, list);
1033 CandidateList_PrintAddrs(list);
1038 * Add all candidates to the list that can be formed by applying a suffix to
1042 CandidateList_AddCandidatesFor(CandidateList *list, Candidate *cand)
1045 for (ln = cand->suff->children.first; ln != NULL; ln = ln->next) {
1046 Suffix *suff = ln->datum;
1048 if (suff->isNull && suff->name[0] != '\0') {
1050 * If the suffix has been marked as the NULL suffix,
1051 * also create a candidate for a file with no suffix
1054 CandidateList_Add(list, bmake_strdup(cand->prefix),
1058 CandidateList_Add(list, str_concat2(cand->prefix, suff->name),
1064 * Free the first candidate in the list that is not referenced anymore.
1065 * Return whether a candidate was removed.
1068 RemoveCandidate(CandidateList *srcs)
1070 CandidateListNode *ln;
1073 debug_printf("cleaning list %p:", srcs);
1074 CandidateList_PrintAddrs(srcs);
1077 for (ln = srcs->first; ln != NULL; ln = ln->next) {
1078 Candidate *src = ln->datum;
1080 if (src->numChildren == 0) {
1081 if (src->parent == NULL)
1085 /* XXX: Lst_RemoveDatum */
1086 CandidateListNode *ln2;
1087 ln2 = Lst_FindDatum(&src->parent->childrenList,
1090 Lst_Remove(&src->parent->childrenList,
1093 src->parent->numChildren--;
1096 debug_printf("free: list %p src %p:%s children %d\n",
1097 srcs, src, src->file, src->numChildren);
1098 Lst_Done(&src->childrenList);
1100 Lst_Remove(srcs, ln);
1107 debug_printf("keep: list %p src %p:%s children %d:",
1108 srcs, src, src->file, src->numChildren);
1109 CandidateList_PrintAddrs(&src->childrenList);
1117 /* Find the first existing file/target in srcs. */
1119 FindThem(CandidateList *srcs, CandidateSearcher *cs)
1123 HashSet_Init(&seen);
1125 while (!Lst_IsEmpty(srcs)) {
1126 Candidate *src = Lst_Dequeue(srcs);
1129 debug_printf("remove from list %p src %p:%s\n",
1130 srcs, src, src->file);
1132 DEBUG1(SUFF, "\ttrying %s...", src->file);
1135 * A file is considered to exist if either a node exists in the
1136 * graph for it or the file actually exists.
1138 if (Targ_FindNode(src->file) != NULL) {
1140 HashSet_Done(&seen);
1141 DEBUG0(SUFF, "got it\n");
1146 char *file = Dir_FindFile(src->file,
1147 src->suff->searchPath);
1154 DEBUG0(SUFF, "not there\n");
1156 if (HashSet_Add(&seen, src->file))
1157 CandidateList_AddCandidatesFor(srcs, src);
1159 DEBUG1(SUFF, "FindThem: skipping duplicate \"%s\"\n",
1163 CandidateSearcher_Add(cs, src);
1166 HashSet_Done(&seen);
1171 * See if any of the children of the candidate's GNode is one from which the
1172 * target can be transformed. If there is one, a candidate is put together
1173 * for it and returned.
1176 FindCmds(Candidate *targ, CandidateSearcher *cs)
1179 GNode *tgn; /* Target GNode */
1180 GNode *sgn; /* Source GNode */
1181 size_t prefLen; /* The length of the defined prefix */
1182 Suffix *suff; /* Suffix of the matching candidate */
1183 Candidate *ret; /* Return value */
1186 prefLen = strlen(targ->prefix);
1188 for (gln = tgn->children.first; gln != NULL; gln = gln->next) {
1193 if (sgn->type & OP_OPTIONAL && Lst_IsEmpty(&tgn->commands)) {
1195 * We haven't looked to see if .OPTIONAL files exist
1196 * yet, so don't use one as the implicit source.
1197 * This allows us to use .OPTIONAL in .depend files so
1198 * make won't complain "don't know how to make xxx.h"
1199 * when a dependent file has been moved/deleted.
1204 base = str_basename(sgn->name);
1205 if (strncmp(base, targ->prefix, prefLen) != 0)
1208 * The node matches the prefix, see if it has a known suffix.
1210 suff = FindSuffixByName(base + prefLen);
1215 * It even has a known suffix, see if there's a transformation
1216 * defined between the node's suffix and the target's suffix.
1218 * XXX: Handle multi-stage transformations here, too.
1221 if (Lst_FindDatum(&suff->parents, targ->suff) != NULL)
1228 ret = Candidate_New(bmake_strdup(sgn->name), targ->prefix, suff, targ,
1230 targ->numChildren++;
1232 debug_printf("3 add targ %p:%s ret %p:%s\n",
1233 targ, targ->file, ret, ret->file);
1234 Lst_Append(&targ->childrenList, ret);
1236 CandidateSearcher_Add(cs, ret);
1237 DEBUG1(SUFF, "\tusing existing source %s\n", sgn->name);
1242 ExpandWildcards(GNodeListNode *cln, GNode *pgn)
1244 GNode *cgn = cln->datum;
1245 StringList expansions;
1247 if (!Dir_HasWildcards(cgn->name))
1251 * Expand the word along the chosen path
1253 Lst_Init(&expansions);
1254 SearchPath_Expand(Suff_FindPath(cgn), cgn->name, &expansions);
1256 while (!Lst_IsEmpty(&expansions)) {
1259 * Fetch next expansion off the list and find its GNode
1261 char *cp = Lst_Dequeue(&expansions);
1263 DEBUG1(SUFF, "%s...", cp);
1264 gn = Targ_GetNode(cp);
1266 /* Insert gn before the original child. */
1267 Lst_InsertBefore(&pgn->children, cln, gn);
1268 Lst_Append(&gn->parents, pgn);
1272 Lst_Done(&expansions);
1277 * Now the source is expanded, remove it from the list of children to
1278 * keep it from being processed.
1281 Lst_Remove(&pgn->children, cln);
1282 Lst_Remove(&cgn->parents, Lst_FindDatum(&cgn->parents, pgn));
1286 * Break the result into a vector of strings whose nodes we can find, then
1287 * add those nodes to the members list.
1289 * Unfortunately, we can't use Str_Words because it doesn't understand about
1290 * variable expressions with spaces in them.
1293 ExpandChildrenRegular(char *cp, GNode *pgn, GNodeList *members)
1297 pp_skip_hspace(&cp);
1299 while (*cp != '\0') {
1300 if (*cp == ' ' || *cp == '\t') {
1303 * White-space -- terminate element, find the node,
1304 * add it, skip any further spaces.
1307 gn = Targ_GetNode(start);
1308 Lst_Append(members, gn);
1309 pp_skip_hspace(&cp);
1310 /* Continue at the next non-space. */
1312 } else if (*cp == '$') {
1313 /* Skip over the variable expression. */
1314 const char *nested_p = cp;
1315 FStr junk = Var_Parse(&nested_p, pgn, VARE_PARSE_ONLY);
1316 /* TODO: handle errors */
1317 if (junk.str == var_Error) {
1318 Parse_Error(PARSE_FATAL,
1319 "Malformed variable expression at \"%s\"",
1323 cp += nested_p - cp;
1327 } else if (cp[0] == '\\' && cp[1] != '\0') {
1328 /* Escaped something -- skip over it. */
1330 * XXX: In other places, escaping at this syntactical
1331 * position is done by a '$', not a '\'. The '\' is
1332 * only used in variable modifiers.
1342 * Stuff left over -- add it to the list too
1344 GNode *gn = Targ_GetNode(start);
1345 Lst_Append(members, gn);
1350 * Expand the names of any children of a given node that contain variable
1351 * expressions or file wildcards into actual targets.
1353 * The expanded node is removed from the parent's list of children, and the
1354 * parent's unmade counter is decremented, but other nodes may be added.
1357 * cln Child to examine
1358 * pgn Parent node being processed
1361 ExpandChildren(GNodeListNode *cln, GNode *pgn)
1363 GNode *cgn = cln->datum;
1364 char *cp; /* Expanded value */
1366 if (!Lst_IsEmpty(&cgn->order_pred) || !Lst_IsEmpty(&cgn->order_succ))
1367 /* It is all too hard to process the result of .ORDER */
1370 if (cgn->type & OP_WAIT)
1371 /* Ignore these (& OP_PHONY ?) */
1375 * First do variable expansion -- this takes precedence over wildcard
1376 * expansion. If the result contains wildcards, they'll be gotten to
1377 * later since the resulting words are tacked on to the end of the
1380 if (strchr(cgn->name, '$') == NULL) {
1381 ExpandWildcards(cln, pgn);
1385 DEBUG1(SUFF, "Expanding \"%s\"...", cgn->name);
1386 cp = Var_Subst(cgn->name, pgn, VARE_UNDEFERR);
1387 /* TODO: handle errors */
1390 GNodeList members = LST_INIT;
1392 if (cgn->type & OP_ARCHV) {
1394 * Node was an 'archive(member)' target, so
1395 * call on the Arch module to find the nodes for us,
1396 * expanding variables in the parent's scope.
1399 (void)Arch_ParseArchive(&p, &members, pgn);
1401 ExpandChildrenRegular(cp, pgn, &members);
1405 * Add all elements of the members list to the parent node.
1407 while (!Lst_IsEmpty(&members)) {
1408 GNode *gn = Lst_Dequeue(&members);
1410 DEBUG1(SUFF, "%s...", gn->name);
1412 * Add gn to the parents child list before the
1415 Lst_InsertBefore(&pgn->children, cln, gn);
1416 Lst_Append(&gn->parents, pgn);
1418 /* Expand wildcards on new node */
1419 ExpandWildcards(cln->prev, pgn);
1429 * Now the source is expanded, remove it from the list of children to
1430 * keep it from being processed.
1433 Lst_Remove(&pgn->children, cln);
1434 Lst_Remove(&cgn->parents, Lst_FindDatum(&cgn->parents, pgn));
1438 ExpandAllChildren(GNode *gn)
1440 GNodeListNode *ln, *nln;
1442 for (ln = gn->children.first; ln != NULL; ln = nln) {
1444 ExpandChildren(ln, gn);
1449 * Find a path along which to expand the node.
1451 * If the node has a known suffix, use that path.
1452 * If it has no known suffix, use the default system search path.
1455 * gn Node being examined
1458 * The appropriate path to search for the GNode.
1461 Suff_FindPath(GNode *gn)
1463 Suffix *suff = gn->suffix;
1466 char *name = gn->name;
1467 size_t nameLen = strlen(gn->name);
1469 for (ln = sufflist.first; ln != NULL; ln = ln->next)
1470 if (Suffix_IsSuffix(ln->datum, nameLen, name + nameLen))
1473 DEBUG1(SUFF, "Wildcard expanding \"%s\"...", gn->name);
1477 * XXX: Here we can save the suffix so we don't have to do
1483 DEBUG1(SUFF, "suffix is \"%s\"...\n", suff->name);
1484 return suff->searchPath;
1487 return &dirSearchPath; /* Use default search path */
1492 * Apply a transformation rule, given the source and target nodes and
1495 * The source and target are linked and the commands from the transformation
1496 * are added to the target node's commands list. The target also inherits all
1497 * the sources for the transformation rule.
1500 * true if successful, false if not.
1503 ApplyTransform(GNode *tgn, GNode *sgn, Suffix *tsuff, Suffix *ssuff)
1506 char *tname; /* Name of transformation rule */
1507 GNode *gn; /* Node for the transformation rule */
1509 /* Form the proper links between the target and source. */
1510 Lst_Append(&tgn->children, sgn);
1511 Lst_Append(&sgn->parents, tgn);
1514 /* Locate the transformation rule itself. */
1515 tname = str_concat2(ssuff->name, tsuff->name);
1516 gn = FindTransformByName(tname);
1519 /* This can happen when linking an OP_MEMBER and OP_ARCHV node. */
1523 DEBUG3(SUFF, "\tapplying %s -> %s to \"%s\"\n",
1524 ssuff->name, tsuff->name, tgn->name);
1526 /* Record last child; Make_HandleUse may add child nodes. */
1527 ln = tgn->children.last;
1529 /* Apply the rule. */
1530 Make_HandleUse(gn, tgn);
1532 /* Deal with wildcards and variables in any acquired sources. */
1533 ln = ln != NULL ? ln->next : NULL;
1534 while (ln != NULL) {
1535 GNodeListNode *nln = ln->next;
1536 ExpandChildren(ln, tgn);
1541 * Keep track of another parent to which this node is transformed so
1542 * the .IMPSRC variable can be set correctly for the parent.
1544 Lst_Append(&sgn->implicitParents, tgn);
1550 * Member has a known suffix, so look for a transformation rule from
1551 * it to a possible suffix of the archive.
1553 * Rather than searching through the entire list, we just look at
1554 * suffixes to which the member's suffix may be transformed.
1557 ExpandMember(GNode *gn, const char *eoarch, GNode *mem, Suffix *memSuff)
1560 size_t nameLen = (size_t)(eoarch - gn->name);
1562 /* Use first matching suffix... */
1563 for (ln = memSuff->parents.first; ln != NULL; ln = ln->next)
1564 if (Suffix_IsSuffix(ln->datum, nameLen, eoarch))
1568 /* Got one -- apply it */
1569 Suffix *suff = ln->datum;
1570 if (!ApplyTransform(gn, mem, suff, memSuff)) {
1571 DEBUG2(SUFF, "\tNo transformation from %s -> %s\n",
1572 memSuff->name, suff->name);
1577 static void FindDeps(GNode *, CandidateSearcher *);
1580 * Locate dependencies for an OP_ARCHV node.
1583 * gn Node for which to locate dependencies
1586 * Same as Suff_FindDeps
1589 FindDepsArchive(GNode *gn, CandidateSearcher *cs)
1591 char *eoarch; /* End of archive portion */
1592 char *eoname; /* End of member portion */
1593 GNode *mem; /* Node for member */
1595 const char *name; /* Start of member's name */
1598 * The node is an archive(member) pair. so we must find a
1599 * suffix for both of them.
1601 eoarch = strchr(gn->name, '(');
1602 eoname = strchr(eoarch, ')');
1605 * Caller guarantees the format `libname(member)', via
1606 * Arch_ParseArchive.
1608 assert(eoarch != NULL);
1609 assert(eoname != NULL);
1611 *eoname = '\0'; /* Nuke parentheses during suffix search */
1612 *eoarch = '\0'; /* So a suffix can be found */
1617 * To simplify things, call Suff_FindDeps recursively on the member
1618 * now, so we can simply compare the member's .PREFIX and .TARGET
1619 * variables to locate its suffix. This allows us to figure out the
1620 * suffix to use for the archive without having to do a quadratic
1621 * search over the suffix list, backtracking for each one.
1623 mem = Targ_GetNode(name);
1626 /* Create the link between the two nodes right off. */
1627 Lst_Append(&gn->children, mem);
1628 Lst_Append(&mem->parents, gn);
1631 /* Copy in the variables from the member node to this one. */
1632 Var_Set(gn, PREFIX, GNode_VarPrefix(mem));
1633 Var_Set(gn, TARGET, GNode_VarTarget(mem));
1635 memSuff = mem->suffix;
1636 if (memSuff == NULL) { /* Didn't know what it was. */
1637 DEBUG0(SUFF, "using null suffix\n");
1642 /* Set the other two local variables required for this target. */
1643 Var_Set(gn, MEMBER, name);
1644 Var_Set(gn, ARCHIVE, gn->name);
1645 /* Set $@ for compatibility with other makes. */
1646 Var_Set(gn, TARGET, gn->name);
1649 * Now we've got the important local variables set, expand any sources
1650 * that still contain variables or wildcards in their names.
1652 ExpandAllChildren(gn);
1654 if (memSuff != NULL)
1655 ExpandMember(gn, eoarch, mem, memSuff);
1658 * Replace the opening and closing parens now we've no need of the
1665 * Pretend gn appeared to the left of a dependency operator so the
1666 * user needn't provide a transformation from the member to the
1669 if (!GNode_IsTarget(gn))
1670 gn->type |= OP_DEPENDS;
1673 * Flag the member as such so we remember to look in the archive for
1674 * its modification time. The OP_JOIN | OP_MADE is needed because
1675 * this target should never get made.
1677 mem->type |= OP_MEMBER | OP_JOIN | OP_MADE;
1681 * If the node is a library, it is the arch module's job to find it
1682 * and set the TARGET variable accordingly. We merely provide the
1683 * search path, assuming all libraries end in ".a" (if the suffix
1684 * hasn't been defined, there's nothing we can do for it, so we just
1685 * set the TARGET variable to the node's name in order to give it a
1689 FindDepsLib(GNode *gn)
1691 Suffix *suff = FindSuffixByName(LIBSUFF);
1693 Suffix_Reassign(&gn->suffix, suff);
1694 Arch_FindLib(gn, suff->searchPath);
1696 Suffix_Unassign(&gn->suffix);
1697 Var_Set(gn, TARGET, gn->name);
1701 * Because a library (-lfoo) target doesn't follow the standard
1702 * filesystem conventions, we don't set the regular variables for
1703 * the thing. .PREFIX is simply made empty.
1705 Var_Set(gn, PREFIX, "");
1709 FindDepsRegularKnown(const char *name, size_t nameLen, GNode *gn,
1710 CandidateList *srcs, CandidateList *targs)
1716 for (ln = sufflist.first; ln != NULL; ln = ln->next) {
1717 Suffix *suff = ln->datum;
1718 if (!Suffix_IsSuffix(suff, nameLen, name + nameLen))
1721 pref = bmake_strldup(name, (size_t)(nameLen - suff->nameLen));
1722 targ = Candidate_New(bmake_strdup(gn->name), pref, suff, NULL,
1725 CandidateList_AddCandidatesFor(srcs, targ);
1727 /* Record the target so we can nuke it. */
1728 Lst_Append(targs, targ);
1733 FindDepsRegularUnknown(GNode *gn, const char *sopref,
1734 CandidateList *srcs, CandidateList *targs)
1738 if (!Lst_IsEmpty(targs) || nullSuff == NULL)
1741 DEBUG1(SUFF, "\tNo known suffix on %s. Using .NULL suffix\n", gn->name);
1743 targ = Candidate_New(bmake_strdup(gn->name), bmake_strdup(sopref),
1744 nullSuff, NULL, gn);
1747 * Only use the default suffix rules if we don't have commands
1748 * defined for this gnode; traditional make programs used to not
1749 * define suffix rules if the gnode had children but we don't do
1752 if (Lst_IsEmpty(&gn->commands))
1753 CandidateList_AddCandidatesFor(srcs, targ);
1755 DEBUG0(SUFF, "not ");
1758 DEBUG0(SUFF, "adding suffix rules\n");
1760 Lst_Append(targs, targ);
1764 * Deal with finding the thing on the default search path. We always do
1765 * that, not only if the node is only a source (not on the lhs of a
1766 * dependency operator or [XXX] it has neither children or commands) as
1767 * the old pmake did.
1770 FindDepsRegularPath(GNode *gn, Candidate *targ)
1772 if (gn->type & (OP_PHONY | OP_NOPATH))
1776 gn->path = Dir_FindFile(gn->name,
1777 targ == NULL ? &dirSearchPath : targ->suff->searchPath);
1778 if (gn->path == NULL)
1781 Var_Set(gn, TARGET, gn->path);
1785 * Suffix known for the thing -- trim the suffix off
1786 * the path to form the proper .PREFIX variable.
1788 size_t savep = strlen(gn->path) - targ->suff->nameLen;
1791 Suffix_Reassign(&gn->suffix, targ->suff);
1793 savec = gn->path[savep];
1794 gn->path[savep] = '\0';
1796 Var_Set(gn, PREFIX, str_basename(gn->path));
1798 gn->path[savep] = savec;
1801 * The .PREFIX gets the full path if the target has no
1804 Suffix_Unassign(&gn->suffix);
1805 Var_Set(gn, PREFIX, str_basename(gn->path));
1810 * Locate implicit dependencies for regular targets.
1813 * gn Node for which to find sources
1816 * Same as Suff_FindDeps
1819 FindDepsRegular(GNode *gn, CandidateSearcher *cs)
1821 /* List of sources at which to look */
1822 CandidateList srcs = LST_INIT;
1824 * List of targets to which things can be transformed.
1825 * They all have the same file, but different suff and prefix fields.
1827 CandidateList targs = LST_INIT;
1828 Candidate *bottom; /* Start of found transformation path */
1832 const char *name = gn->name;
1833 size_t nameLen = strlen(name);
1836 DEBUG1(SUFF, "FindDepsRegular \"%s\"\n", gn->name);
1840 * We're caught in a catch-22 here. On the one hand, we want to use
1841 * any transformation implied by the target's sources, but we can't
1842 * examine the sources until we've expanded any variables/wildcards
1843 * they may hold, and we can't do that until we've set up the
1844 * target's local variables and we can't do that until we know what
1845 * the proper suffix for the target is (in case there are two
1846 * suffixes one of which is a suffix of the other) and we can't know
1847 * that until we've found its implied source, which we may not want
1848 * to use if there's an existing source that implies a different
1851 * In an attempt to get around this, which may not work all the time,
1852 * but should work most of the time, we look for implied sources
1853 * first, checking transformations to all possible suffixes of the
1854 * target, use what we find to set the target's local variables,
1855 * expand the children, then look for any overriding transformations
1856 * they imply. Should we find one, we discard the one we found before.
1861 if (!(gn->type & OP_PHONY)) {
1863 FindDepsRegularKnown(name, nameLen, gn, &srcs, &targs);
1865 /* Handle target of unknown suffix... */
1866 FindDepsRegularUnknown(gn, name, &srcs, &targs);
1869 * Using the list of possible sources built up from the target
1870 * suffix(es), try and find an existing file/target that
1873 bottom = FindThem(&srcs, cs);
1875 if (bottom == NULL) {
1877 * No known transformations -- use the first suffix
1878 * found for setting the local variables.
1880 if (targs.first != NULL)
1881 targ = targs.first->datum;
1886 * Work up the transformation path to find the suffix
1887 * of the target to which the transformation was made.
1890 targ->parent != NULL; targ = targ->parent)
1895 Var_Set(gn, TARGET, GNode_Path(gn));
1896 Var_Set(gn, PREFIX, targ != NULL ? targ->prefix : gn->name);
1899 * Now we've got the important local variables set, expand any sources
1900 * that still contain variables or wildcards in their names.
1903 GNodeListNode *ln, *nln;
1904 for (ln = gn->children.first; ln != NULL; ln = nln) {
1906 ExpandChildren(ln, gn);
1911 DEBUG1(SUFF, "\tNo valid suffix on %s\n", gn->name);
1914 FindDepsRegularPath(gn, targ);
1919 * If the suffix indicates that the target is a library, mark that in
1920 * the node's type field.
1922 if (targ->suff->library)
1926 * Check for overriding transformation rule implied by sources
1928 if (!Lst_IsEmpty(&gn->children)) {
1929 src = FindCmds(targ, cs);
1933 * Free up all the candidates in the transformation
1934 * path, up to but not including the parent node.
1936 while (bottom != NULL && bottom->parent != NULL) {
1937 CandidateSearcher_AddIfNew(cs, bottom);
1938 bottom = bottom->parent;
1944 if (bottom == NULL) {
1945 /* No idea from where it can come -- return now. */
1950 * We now have a list of candidates headed by 'bottom' and linked via
1951 * their 'parent' pointers. What we do next is create links between
1952 * source and target nodes (which may or may not have been created)
1953 * and set the necessary local variables in each target.
1955 * The commands for each target are set from the commands of the
1956 * transformation rule used to get from the src suffix to the targ
1957 * suffix. Note that this causes the commands list of the original
1958 * node, gn, to be replaced with the commands of the final
1959 * transformation rule.
1961 if (bottom->node == NULL)
1962 bottom->node = Targ_GetNode(bottom->file);
1964 for (src = bottom; src->parent != NULL; src = src->parent) {
1967 Suffix_Reassign(&src->node->suffix, src->suff);
1969 if (targ->node == NULL)
1970 targ->node = Targ_GetNode(targ->file);
1972 ApplyTransform(targ->node, src->node,
1973 targ->suff, src->suff);
1975 if (targ->node != gn) {
1977 * Finish off the dependency-search process for any
1978 * nodes between bottom and gn (no point in questing
1979 * around the filesystem for their implicit source
1980 * when it's already known). Note that the node
1981 * can't have any sources that need expanding, since
1982 * SuffFindThem will stop on an existing node, so all
1983 * we need to do is set the standard variables.
1985 targ->node->type |= OP_DEPS_FOUND;
1986 Var_Set(targ->node, PREFIX, targ->prefix);
1987 Var_Set(targ->node, TARGET, targ->node->name);
1991 Suffix_Reassign(&gn->suffix, src->suff);
1994 * Nuke the transformation path and the candidates left over in the
1999 CandidateSearcher_AddIfNew(cs, bottom);
2001 while (RemoveCandidate(&srcs) || RemoveCandidate(&targs))
2004 CandidateSearcher_MoveAll(cs, &srcs);
2005 CandidateSearcher_MoveAll(cs, &targs);
2009 CandidateSearcher_CleanUp(CandidateSearcher *cs)
2011 while (RemoveCandidate(&cs->list))
2013 assert(Lst_IsEmpty(&cs->list));
2018 * Find implicit sources for the target.
2020 * Nodes are added to the graph as children of the passed-in node. The nodes
2021 * are marked to have their IMPSRC variable filled in. The PREFIX variable
2022 * is set for the given node and all its implied children.
2024 * The path found by this target is the shortest path in the transformation
2025 * graph, which may pass through nonexistent targets, to an existing target.
2026 * The search continues on all paths from the root suffix until a file is
2027 * found. I.e. if there's a path .o -> .c -> .l -> .l,v from the root and the
2028 * .l,v file exists but the .c and .l files don't, the search will branch out
2029 * in all directions from .o and again from all the nodes on the next level
2030 * until the .l,v node is encountered.
2033 Suff_FindDeps(GNode *gn)
2035 CandidateSearcher cs;
2037 CandidateSearcher_Init(&cs);
2041 CandidateSearcher_CleanUp(&cs);
2042 CandidateSearcher_Done(&cs);
2046 FindDeps(GNode *gn, CandidateSearcher *cs)
2048 if (gn->type & OP_DEPS_FOUND)
2050 gn->type |= OP_DEPS_FOUND;
2052 /* Make sure we have these set, may get revised below. */
2053 Var_Set(gn, TARGET, GNode_Path(gn));
2054 Var_Set(gn, PREFIX, gn->name);
2056 DEBUG1(SUFF, "SuffFindDeps \"%s\"\n", gn->name);
2058 if (gn->type & OP_ARCHV)
2059 FindDepsArchive(gn, cs);
2060 else if (gn->type & OP_LIB)
2063 FindDepsRegular(gn, cs);
2067 * Define which suffix is the null suffix.
2069 * Need to handle the changing of the null suffix gracefully so the old
2070 * transformation rules don't just go away.
2073 * name Name of null suffix
2076 Suff_SetNull(const char *name)
2078 Suffix *suff = FindSuffixByName(name);
2080 Parse_Error(PARSE_WARNING,
2081 "Desired null suffix %s not defined",
2086 if (nullSuff != NULL)
2087 nullSuff->isNull = false;
2088 suff->isNull = true;
2089 /* XXX: Here's where the transformation mangling would take place. */
2093 /* Initialize the suffixes module. */
2098 * Create null suffix for single-suffix rules (POSIX). The thing
2099 * doesn't actually go on the suffix list or everyone will think
2100 * that's its suffix.
2102 Suff_ClearSuffixes();
2106 /* Clean up the suffixes module. */
2111 Lst_DoneCall(&sufflist, SuffFree);
2112 Lst_DoneCall(&suffClean, SuffFree);
2113 if (nullSuff != NULL)
2115 Lst_Done(&transforms);
2121 PrintSuffNames(const char *prefix, const SuffixList *suffs)
2125 debug_printf("#\t%s: ", prefix);
2126 for (ln = suffs->first; ln != NULL; ln = ln->next) {
2127 const Suffix *suff = ln->datum;
2128 debug_printf("%s ", suff->name);
2134 Suffix_Print(const Suffix *suff)
2138 Buf_InitSize(&buf, 16);
2139 Buf_AddFlag(&buf, suff->include, "SUFF_INCLUDE");
2140 Buf_AddFlag(&buf, suff->library, "SUFF_LIBRARY");
2141 Buf_AddFlag(&buf, suff->isNull, "SUFF_NULL");
2143 debug_printf("# \"%s\" (num %d, ref %d)",
2144 suff->name, suff->sNum, suff->refCount);
2146 debug_printf(" (%s)", buf.data);
2151 PrintSuffNames("To", &suff->parents);
2152 PrintSuffNames("From", &suff->children);
2154 debug_printf("#\tSearch Path: ");
2155 SearchPath_Print(suff->searchPath);
2160 PrintTransformation(GNode *t)
2162 debug_printf("%-16s:", t->name);
2163 Targ_PrintType(t->type);
2172 debug_printf("#*** Suffixes:\n");
2175 for (ln = sufflist.first; ln != NULL; ln = ln->next)
2176 Suffix_Print(ln->datum);
2179 debug_printf("#*** Transformations:\n");
2182 for (ln = transforms.first; ln != NULL; ln = ln->next)
2183 PrintTransformation(ln->datum);
2194 Buf_InitSize(&buf, 16);
2195 for (ln = sufflist.first; ln != NULL; ln = ln->next) {
2197 if (ln != sufflist.first)
2198 Buf_AddByte(&buf, ' ');
2199 Buf_AddStr(&buf, suff->name);
2201 return Buf_DoneData(&buf);