From b9c983dee3c6aff460532d9b4fd7aaea079c672b Mon Sep 17 00:00:00 2001 From: Roland McGrath Date: Sun, 15 Sep 1991 21:20:45 +0000 Subject: Initial revision --- implicit.c | 586 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 586 insertions(+) create mode 100644 implicit.c diff --git a/implicit.c b/implicit.c new file mode 100644 index 0000000..7961e9c --- /dev/null +++ b/implicit.c @@ -0,0 +1,586 @@ +/* Implicit rule searching for GNU Make. +Copyright (C) 1988, 1989, 1990, 1991 Free Software Foundation, Inc. +This file is part of GNU Make. + +GNU Make is free software; you can redistribute it and/or modify +it under the terms of the GNU General Public License as published by +the Free Software Foundation; either version 2, or (at your option) +any later version. + +GNU Make is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public License +along with GNU Make; see the file COPYING. If not, write to +the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ + +#include "make.h" +#include "rule.h" +#include "dep.h" +#include "file.h" + +static int pattern_search (); + +/* For a FILE which has no commands specified, try to figure out some + from the implicit pattern rules. + Returns 1 if a suitable implicit rule was found, + after modifying FILE to contain the appropriate commands and deps, + or returns 0 if no implicit rule was found. */ + +int +try_implicit_rule (file, depth) + struct file *file; + unsigned int depth; +{ + DEBUGPR ("Looking for an implicit rule for `%s'.\n"); + +#ifndef NO_ARCHIVES + /* If this is an archive member reference, use just the + archive member name to search for implicit rules. */ + if (ar_name (file->name)) + { + DEBUGPR ("Looking for archive-member implicit rule for `%s'.\n"); + if (pattern_search (file, 1, depth, 0)) + return 1; + } +#endif + + return pattern_search (file, 0, depth, 0); +} + +#define DEBUGP2(msg, a1, a2) \ + if (debug_flag) \ + { print_spaces (depth); printf (msg, a1, a2); fflush (stdout); } else + +/* Search the pattern rules for a rule with an existing dependency to make + FILE. If a rule is found, the appropriate commands and deps are put in FILE + and 1 is returned. If not, 0 is returned. + + If ARCHIVE is nonzero, FILE->name is of the form "LIB(MEMBER)". A rule for + "(MEMBER)" will be searched for, and "(MEMBER)" will not be chopped up into + directory and filename parts. + + If an intermediate file is found by pattern search, the intermediate file + is set up as a target by the recursive call and is also made a dependency + of FILE. + + DEPTH is used for debugging messages. */ + +static int +pattern_search (file, archive, depth, recursions) + struct file *file; + int archive; + unsigned int depth; + unsigned int recursions; +{ + /* Filename we are searching for a rule for. */ + char *filename = archive ? index (file->name, '(') : file->name; + + /* Length of FILENAME. */ + unsigned int namelen = strlen (filename); + + /* The last slash in FILENAME (or nil if there is none). */ + char *lastslash; + + /* This is a file-object used as an argument in + recursive calls. It never contains any data + except during a recursive call. */ + struct file *intermediate_file = 0; + + /* List of dependencies found recursively. */ + struct file **intermediate_files + = (struct file **) alloca (max_pattern_deps * sizeof (struct file *)); + + /* List of the patterns used to find intermediate files. */ + char **intermediate_patterns + = (char **) alloca (max_pattern_deps * sizeof (char *)); + + /* This buffer records all the dependencies actually found for a rule. */ + char **found_files = (char **) alloca (max_pattern_deps * sizeof (char *)); + /* Number of dep names now in FOUND_FILES. */ + unsigned int deps_found; + + /* Names of possible dependencies are constructed in this buffer. */ + register char *depname = (char *) alloca (namelen + max_pattern_dep_length); + + /* The start and length of the stem of FILENAME for the current rule. */ + register char *stem; + register unsigned int stemlen; + + /* Buffer in which we store all the rules that are possibly applicable. */ + struct rule **tryrules + = (struct rule **) alloca (num_pattern_rules * sizeof (struct rule *)); + + /* Number of valid elements in TRYRULES. */ + unsigned int nrules; + + /* The numbers of the rule targets of each rule + in TRYRULES that matched the target file. */ + unsigned int *matches + = (unsigned int *) alloca (num_pattern_rules * sizeof (unsigned int)); + + /* Each element is nonzero if LASTSLASH was used in + matching the corresponding element of TRYRULES. */ + char *checked_lastslash + = (char *) alloca (num_pattern_rules * sizeof (char)); + + /* The index in TRYRULES of the rule we found. */ + unsigned int foundrule; + + /* Nonzero if should consider intermediate files as dependencies. */ + int intermed_ok; + + /* Nonzero if we have matched a pattern-rule target + that is not just `%'. */ + int specific_rule_matched = 0; + + register unsigned int i; + register struct rule *rule; + register struct dep *dep; + + char *p; + +#ifndef NO_ARCHIVES + if (archive || ar_name (filename)) + lastslash = 0; + else +#endif + { + /* Set LASTSLASH to point at the last slash in FILENAME + but not counting any slash at the end. (foo/bar/ counts as + bar/ in directory foo/, not empty in directory foo/bar/.) */ + lastslash = rindex (filename, '/'); + if (lastslash != 0 && lastslash[1] == '\0') + lastslash = 0; + } + + /* First see which pattern rules match this target + and may be considered. Put them in TRYRULES. */ + + nrules = 0; + for (rule = pattern_rules; rule != 0; rule = rule->next) + { + int specific_rule_may_have_matched = 0; + int check_lastslash; + + /* If the pattern rule has deps but no commands, ignore it. + Users cancel built-in rules by redefining them without commands. */ + if (rule->deps != 0 && rule->cmds == 0) + continue; + + /* If this rule is in use by a parent pattern_search, + don't use it here. */ + if (rule->in_use) + { + DEBUGP2 ("Avoiding implicit rule recursion.\n", 0, 0); + continue; + } + + for (i = 0; rule->targets[i] != 0; ++i) + { + char *target = rule->targets[i]; + char *suffix = rule->suffixes[i]; + + /* Rules that can match any filename and are not terminal + are ignored if we're recursing, so that they cannot be + intermediate files. */ + if (recursions > 0 && target[1] == '\0' && !rule->terminal) + continue; + + if (rule->lens[i] > namelen) + /* It can't possibly match. */ + continue; + + /* From the lengths of the filename and the pattern parts, + find the stem: the part of the filename that matches the %. */ + stem = filename + (suffix - target - 1); + stemlen = namelen - rule->lens[i] + 1; + + /* Set CHECK_LASTSLASH if FILENAME contains a directory + prefix and the target pattern does not contain a slash. */ + + check_lastslash = lastslash != 0 && index (target, '/') == 0; + if (check_lastslash) + { + /* In that case, don't include the + directory prefix in STEM here. */ + unsigned int difference = lastslash - filename + 1; + if (difference > stemlen) + continue; + stemlen -= difference; + stem += difference; + } + + /* Check that the rule pattern matches the text before the stem. */ + if (check_lastslash) + { + if (stem > (lastslash + 1) + && strncmp (target, lastslash + 1, stem - lastslash - 1)) + continue; + } + else if (stem > filename + && strncmp (target, filename, stem - filename)) + continue; + + /* Check that the rule pattern matches the text after the stem. + We could test simply use streq, but this way we compare the + first two characters immediately. This saves time in the very + common case where the first character matches because it is a + period. */ + if (*suffix != stem[stemlen] + || (*suffix != '\0' && !streq (&suffix[1], &stem[stemlen + 1]))) + continue; + + /* Record if we match a rule that not all filenames will match. */ + if (target[1] != '\0') + specific_rule_may_have_matched = 1; + + /* We have a matching target. Don't search for any more. */ + break; + } + + /* None of the targets matched. */ + if (rule->targets[i] == 0) + continue; + + specific_rule_matched |= specific_rule_may_have_matched; + + /* A rule with no dependencies and no commands exists solely to set + specific_rule_matched when it matches. Don't try to use it. */ + if (rule->deps == 0 && rule->cmds == 0) + continue; + + /* Record this rule in TRYRULES and the index + of the (first) matching target in MATCHES. */ + tryrules[nrules] = rule; + matches[nrules] = i; + checked_lastslash[nrules] = check_lastslash; + ++nrules; + } + + /* If we have found a matching rule that won't match all filenames, + retroactively reject any "terminal" rules that do always match. */ + if (specific_rule_matched) + for (i = 0; i < nrules; ++i) + if (!tryrules[i]->terminal) + { + register unsigned int j; + for (j = 0; tryrules[i]->targets[j] != 0; ++j) + if (tryrules[i]->targets[j][1] == '\0') + break; + if (tryrules[i]->targets[j] != 0) + tryrules[i] = 0; + } + + /* Try each rule once without intermediate files, then once with them. */ + for (intermed_ok = 0; intermed_ok == !!intermed_ok; ++intermed_ok) + { + /* Try each pattern rule till we find one that applies. + If it does, copy the names of its dependencies (as substituted) + and store them in FOUND_FILES. DEPS_FOUND is the number of them. */ + + for (i = 0; i < nrules; i++) + { + int check_lastslash; + + rule = tryrules[i]; + + /* RULE is nil when we discover that a rule, + already placed in TRYRULES, should not be applied. */ + if (rule == 0) + continue; + + /* Reject any terminal rules if we're + looking to make intermediate files. */ + if (intermed_ok && rule->terminal) + continue; + + /* Mark this rule as in use so a recursive + pattern_search won't try to use it. */ + rule->in_use = 1; + + /* From the lengths of the filename and the matching pattern parts, + find the stem: the part of the filename that matches the %. */ + stem = filename + + (rule->suffixes[matches[i]] - rule->targets[matches[i]]) - 1; + stemlen = namelen - rule->lens[matches[i]] + 1; + check_lastslash = (lastslash != 0 + && index (rule->targets[matches[i]], '/') == 0); + if (check_lastslash) + { + stem += lastslash - filename + 1; + stemlen -= (lastslash - filename) + 1; + } + + DEBUGP2 ("Trying pattern rule with stem `%.*s'.\n", + stemlen, stem); + + /* Try each dependency; see if it "exists". */ + + deps_found = 0; + for (dep = rule->deps; dep != 0; dep = dep->next) + { + /* If the dependency name has a %, substitute the stem. */ + p = index (dep_name (dep), '%'); + if (p != 0) + { + register unsigned int i; + if (check_lastslash) + { + i = lastslash - filename + 1; + bcopy (filename, depname, i); + } + else + i = 0; + bcopy (dep_name (dep), depname + i, p - dep_name (dep)); + i += p - dep_name (dep); + bcopy (stem, depname + i, stemlen); + i += stemlen; + strcpy (depname + i, p + 1); + p = depname; + } + else + p = dep_name (dep); + + /* P is now the actual dependency name as substituted. */ + + if (file_impossible_p (p)) + { + /* If this dependency has already been ruled + "impossible", then the rule fails and don't + bother trying it on the second pass either + since we know that will fail too. */ + DEBUGP2 ("Rejecting impossible %s dependent `%s'.\n", + p == depname ? "implicit" : "rule", p); + tryrules[i] = 0; + break; + } + + intermediate_files[deps_found] = 0; + + DEBUGP2 ("Trying %s dependency `%s'.\n", + p == depname ? "implicit" : "rule", p); + if (!rule->subdir && lookup_file (p) != 0 || file_exists_p (p)) + { + found_files[deps_found++] = savestring (p, strlen (p)); + continue; + } + /* This code, given FILENAME = "lib/foo.o", dependency name + "lib/foo.c", and VPATH=src, searches for "src/lib/foo.c". */ + if (vpath_search (&p)) + { + DEBUGP2 ("Found dependent as `%s'.\n", p, 0); + found_files[deps_found++] = p; + continue; + } + + /* We could not find the file in any place we should look. + Try to make this dependency as an intermediate file, + but only on the second pass. */ + + if (intermed_ok) + { + if (intermediate_file == 0) + intermediate_file + = (struct file *) alloca (sizeof (struct file)); + + DEBUGP2 ("Looking for a rule with intermediate file `%s'.\n", + p, 0); + + bzero ((char *) intermediate_file, sizeof (struct file)); + intermediate_file->name = p; + if (pattern_search (intermediate_file, 0, depth + 1, + recursions + 1)) + { + p = savestring (p, strlen (p)); + intermediate_patterns[deps_found] + = intermediate_file->name; + found_files[deps_found] = p; + intermediate_file->name = p; + intermediate_files[deps_found] = intermediate_file; + intermediate_file = 0; + ++deps_found; + continue; + } + + /* If we have tried to find P as an intermediate + file and failed, mark that name as impossible + so we won't go through the search again later. */ + file_impossible (p); + } + + /* A dependency of this rule does not exist. + Therefore, this rule fails. */ + break; + } + + /* This rule is no longer `in use' for recursive searches. */ + rule->in_use = 0; + + if (dep != 0) + { + /* This pattern rule does not apply. + If some of its dependencies succeeded, + free the data structure describing them. */ + while (deps_found-- > 0) + { + register struct file *f = intermediate_files[deps_found]; + free (found_files[deps_found]); + if (f != 0 + && (f->stem < f->name + || f->stem > f->name + strlen (f->name))) + free (f->stem); + } + } + else + /* This pattern rule does apply. Stop looking for one. */ + break; + } + + /* If we found an applicable rule without + intermediate files, don't try with them. */ + if (i < nrules) + break; + + rule = 0; + } + + /* RULE is nil if the loop went all the way + through the list and everything failed. */ + if (rule == 0) + return 0; + + foundrule = i; + + /* If we are recursing, store the pattern that matched + FILENAME in FILE->name for use in upper levels. */ + + if (recursions > 0) + /* Kludge-o-matic */ + file->name = rule->targets[matches[foundrule]]; + + /* FOUND_FILES lists the dependencies for the rule we found. + This includes the intermediate files, if any. + Convert them into entries on the deps-chain of FILE. */ + + while (deps_found-- > 0) + { + register char *s; + + if (intermediate_files[deps_found] != 0) + { + /* If we need to use an intermediate file, + make sure it is entered as a target, with the info that was + found for it in the recursive pattern_search call. + We know that the intermediate file did not already exist as + a target; therefore we can assume that the deps and cmds + of F below are null before we change them. */ + + struct file *imf = intermediate_files[deps_found]; + register struct file *f = enter_file (imf->name); + f->deps = imf->deps; + f->cmds = imf->cmds; + f->stem = imf->stem; + imf = lookup_file (intermediate_patterns[deps_found]); + if (imf != 0 && imf->precious) + f->precious = 1; + f->intermediate = 1; + f->tried_implicit = 1; + for (dep = f->deps; dep != 0; dep = dep->next) + { + dep->file = enter_file (dep->name); + dep->name = 0; + dep->file->tried_implicit |= dep->changed; + } + num_intermediates++; + } + + dep = (struct dep *) xmalloc (sizeof (struct dep)); + s = found_files[deps_found]; + if (recursions == 0) + { + dep->name = 0; + dep->file = enter_file (s); + } + else + { + dep->name = s; + dep->file = 0; + dep->changed = 0; + } + if (intermediate_files[deps_found] == 0 && tryrules[foundrule]->terminal) + { + /* If the file actually existed (was not an intermediate file), + and the rule that found it was a terminal one, then we want + to mark the found file so that it will not have implicit rule + search done for it. If we are not entering a `struct file' for + it now, we indicate this with the `changed' flag. */ + if (dep->file == 0) + dep->changed = 1; + else + dep->file->tried_implicit = 1; + } + dep->next = file->deps; + file->deps = dep; + } + + uniquize_deps (file->deps); + + if (!checked_lastslash[foundrule]) + file->stem = stem[stemlen] == '\0' ? stem : savestring (stem, stemlen); + else + { + file->stem = (char *) xmalloc (((lastslash + 1) - filename) + + stemlen + 1); + bcopy (filename, file->stem, (lastslash + 1) - filename); + bcopy (stem, file->stem + ((lastslash + 1) - filename), stemlen); + file->stem[((lastslash + 1) - filename) + stemlen] = '\0'; + } + + file->cmds = rule->cmds; + + /* Put the targets other than the one that + matched into FILE's `also_make' member. */ + + /* If there was only one target, there is nothing to do. */ + if (rule->targets[1] != 0) + { + unsigned int max_targets = 2; + register unsigned int idx; + + file->also_make = (char **) xmalloc (2 * sizeof (char *)); + + idx = 0; + for (i = 0; rule->targets[i] != 0; ++i) + if (i != matches[foundrule]) + { + if (idx == max_targets - 1) + { + max_targets += 5; + file->also_make + = (char **) xrealloc ((char *) file->also_make, + max_targets * sizeof (char *)); + } + + p = file->also_make[idx++] = (char *) xmalloc (rule->lens[i] + + stemlen + 1); + bcopy (rule->targets[i], p, + rule->suffixes[i] - rule->targets[i] - 1); + p += rule->suffixes[i] - rule->targets[i] - 1; + bcopy (stem, p, stemlen); + p += stemlen; + bcopy (rule->suffixes[i], p, + rule->lens[i] + - (rule->suffixes[i] - rule->targets[i] - 1) + 1); + } + + file->also_make[idx] = 0; + if (idx < max_targets - 1) + file->also_make = (char **) xrealloc ((char *) file->also_make, + (idx + 1) * sizeof (char *)); + } + + return 1; +} -- cgit v1.2.3