# (make.info)Search Algorithm

Prev: Suffix Rules Up: Implicit Rules

Implicit Rule Search Algorithm
==============================

Here is the procedure `make' uses for searching for an implicit rule
for a target T.  This procedure is followed for each double-colon rule
with no commands, for each target of ordinary rules none of which have
commands, and for each dependency that is not the target of any rule.
It is also followed recursively for dependencies that come from implicit
rules, in the search for a chain of rules.

Suffix rules are not mentioned in this algorithm because suffix
rules are converted to equivalent pattern rules once the makefiles have

For an archive member target of the form `ARCHIVE(MEMBER)', the
following algorithm is run twice, first using the entire target name T,
and second using `(MEMBER)' as the target T if the first run found no
rule.

1. Split T into a directory part, called D, and the rest, called N.
For example, if T is `src/foo.o', then D is `src/' and N is
`foo.o'.

2. Make a list of all the pattern rules one of whose targets matches
T or N.  If the target pattern contains a slash, it is matched
against T; otherwise, against N.

3. If any rule in that list is *not* a match-anything rule, then
remove all nonterminal match-anything rules from the list.

4. Remove from the list all rules with no commands.

5. For each pattern rule in the list:

a. Find the stem S, which is the nonempty part of T or N matched
by the `%' in the target pattern.

b. Compute the dependency names by substituting S for `%'; if
the target pattern does not contain a slash, append D to the
front of each dependency name.

c. Test whether all the dependencies exist or ought to exist.
(If a file name is mentioned in the makefile as a target or
as an explicit dependency, then we say it ought to exist.)

If all dependencies exist or ought to exist, or there are no
dependencies, then this rule applies.

6. If no pattern rule has been found so far, try harder.  For each
pattern rule in the list:

a. If the rule is terminal, ignore it and go on to the next rule.

b. Compute the dependency names as before.

c. Test whether all the dependencies exist or ought to exist.

d. For each dependency that does not exist, follow this algorithm
recursively to see if the dependency can be made by an
implicit rule.

e. If all dependencies exist, ought to exist, or can be made by
implicit rules, then this rule applies.

7. If no implicit rule applies, the rule for `.DEFAULT', if any,
applies.  In that case, give T the same commands that `.DEFAULT'
has.  Otherwise, there are no commands for T.

Once a rule that applies has been found, for each target pattern of
the rule other than the one that matched T or N, the `%' in the pattern
is replaced with S and the resultant file name is stored until the
commands to remake the target file T are executed.  After these
commands are executed, each of these stored file names are entered into
the data base and marked as having been updated and having the same
update status as the file T.

When the commands of a pattern rule are executed for T, the automatic
variables are set corresponding to the target and dependencies.  *Note
Automatic Variables: Automatic.

automatically generated by info2www