1
/* Implicit rule searching for GNU Make.
2
Copyright (C) 1988,89,90,91,92,93,94,97 Free Software Foundation, Inc.
3
This file is part of GNU Make.
5
GNU Make is free software; you can redistribute it and/or modify
6
it under the terms of the GNU General Public License as published by
7
the Free Software Foundation; either version 2, or (at your option)
10
GNU Make is distributed in the hope that it will be useful,
11
but WITHOUT ANY WARRANTY; without even the implied warranty of
12
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13
GNU General Public License for more details.
15
You should have received a copy of the GNU General Public License
16
along with GNU Make; see the file COPYING. If not, write to
17
the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18
Boston, MA 02111-1307, USA. */
25
static int pattern_search PARAMS ((struct file *file, int archive, unsigned int depth,
26
unsigned int recursions));
28
/* For a FILE which has no commands specified, try to figure out some
29
from the implicit pattern rules.
30
Returns 1 if a suitable implicit rule was found,
31
after modifying FILE to contain the appropriate commands and deps,
32
or returns 0 if no implicit rule was found. */
35
try_implicit_rule (file, depth)
39
DEBUGPR (_("Looking for an implicit rule for `%s'.\n"));
41
/* The order of these searches was previously reversed. My logic now is
42
that since the non-archive search uses more information in the target
43
(the archive search omits the archive name), it is more specific and
46
if (pattern_search (file, 0, depth, 0))
50
/* If this is an archive member reference, use just the
51
archive member name to search for implicit rules. */
52
if (ar_name (file->name))
54
DEBUGPR (_("Looking for archive-member implicit rule for `%s'.\n"));
55
if (pattern_search (file, 1, depth, 0))
63
#define DEBUGP2(msg, a1, a2) \
66
{ print_spaces (depth); printf (msg, a1, a2); fflush (stdout); } \
69
/* Search the pattern rules for a rule with an existing dependency to make
70
FILE. If a rule is found, the appropriate commands and deps are put in FILE
71
and 1 is returned. If not, 0 is returned.
73
If ARCHIVE is nonzero, FILE->name is of the form "LIB(MEMBER)". A rule for
74
"(MEMBER)" will be searched for, and "(MEMBER)" will not be chopped up into
75
directory and filename parts.
77
If an intermediate file is found by pattern search, the intermediate file
78
is set up as a target by the recursive call and is also made a dependency
81
DEPTH is used for debugging messages. */
84
pattern_search (file, archive, depth, recursions)
88
unsigned int recursions;
90
/* Filename we are searching for a rule for. */
91
char *filename = archive ? index (file->name, '(') : file->name;
93
/* Length of FILENAME. */
94
unsigned int namelen = strlen (filename);
96
/* The last slash in FILENAME (or nil if there is none). */
99
/* This is a file-object used as an argument in
100
recursive calls. It never contains any data
101
except during a recursive call. */
102
struct file *intermediate_file = 0;
104
/* List of dependencies found recursively. */
105
struct file **intermediate_files
106
= (struct file **) alloca (max_pattern_deps * sizeof (struct file *));
108
/* List of the patterns used to find intermediate files. */
109
char **intermediate_patterns
110
= (char **) alloca (max_pattern_deps * sizeof (char *));
112
/* This buffer records all the dependencies actually found for a rule. */
113
char **found_files = (char **) alloca (max_pattern_deps * sizeof (char *));
114
/* Number of dep names now in FOUND_FILES. */
115
unsigned int deps_found = 0;
117
/* Names of possible dependencies are constructed in this buffer. */
118
register char *depname = (char *) alloca (namelen + max_pattern_dep_length);
120
/* The start and length of the stem of FILENAME for the current rule. */
121
register char *stem = 0;
122
register unsigned int stemlen = 0;
124
/* Buffer in which we store all the rules that are possibly applicable. */
125
struct rule **tryrules
126
= (struct rule **) alloca (num_pattern_rules * max_pattern_targets
127
* sizeof (struct rule *));
129
/* Number of valid elements in TRYRULES. */
132
/* The numbers of the rule targets of each rule
133
in TRYRULES that matched the target file. */
134
unsigned int *matches
135
= (unsigned int *) alloca (num_pattern_rules * sizeof (unsigned int));
137
/* Each element is nonzero if LASTSLASH was used in
138
matching the corresponding element of TRYRULES. */
139
char *checked_lastslash
140
= (char *) alloca (num_pattern_rules * sizeof (char));
142
/* The index in TRYRULES of the rule we found. */
143
unsigned int foundrule;
145
/* Nonzero if should consider intermediate files as dependencies. */
148
/* Nonzero if we have matched a pattern-rule target
149
that is not just `%'. */
150
int specific_rule_matched = 0;
152
register unsigned int i = 0; /* uninit checks OK */
153
register struct rule *rule;
154
register struct dep *dep;
159
if (archive || ar_name (filename))
164
/* Set LASTSLASH to point at the last slash in FILENAME
165
but not counting any slash at the end. (foo/bar/ counts as
166
bar/ in directory foo/, not empty in directory foo/bar/.) */
168
lastslash = rindex (filename, ']');
170
lastslash = rindex (filename, '/');
171
#if defined(__MSDOS__) || defined(WINDOWS32)
172
/* Handle backslashes (possibly mixed with forward slashes)
173
and the case of "d:file". */
175
char *bslash = rindex (filename, '\\');
176
if (lastslash == 0 || bslash > lastslash)
178
if (lastslash == 0 && filename[0] && filename[1] == ':')
179
lastslash = filename + 1;
183
if (lastslash != 0 && lastslash[1] == '\0')
187
/* First see which pattern rules match this target
188
and may be considered. Put them in TRYRULES. */
191
for (rule = pattern_rules; rule != 0; rule = rule->next)
193
/* If the pattern rule has deps but no commands, ignore it.
194
Users cancel built-in rules by redefining them without commands. */
195
if (rule->deps != 0 && rule->cmds == 0)
198
/* If this rule is in use by a parent pattern_search,
199
don't use it here. */
202
DEBUGP2 (_("Avoiding implicit rule recursion.%s%s\n"), "", "");
206
for (i = 0; rule->targets[i] != 0; ++i)
208
char *target = rule->targets[i];
209
char *suffix = rule->suffixes[i];
212
/* Rules that can match any filename and are not terminal
213
are ignored if we're recursing, so that they cannot be
214
intermediate files. */
215
if (recursions > 0 && target[1] == '\0' && !rule->terminal)
218
if (rule->lens[i] > namelen)
219
/* It can't possibly match. */
222
/* From the lengths of the filename and the pattern parts,
223
find the stem: the part of the filename that matches the %. */
224
stem = filename + (suffix - target - 1);
225
stemlen = namelen - rule->lens[i] + 1;
227
/* Set CHECK_LASTSLASH if FILENAME contains a directory
228
prefix and the target pattern does not contain a slash. */
231
check_lastslash = lastslash != 0 && index (target, ']') == 0;
233
check_lastslash = lastslash != 0 && index (target, '/') == 0;
237
/* In that case, don't include the
238
directory prefix in STEM here. */
239
unsigned int difference = lastslash - filename + 1;
240
if (difference > stemlen)
242
stemlen -= difference;
246
/* Check that the rule pattern matches the text before the stem. */
249
if (stem > (lastslash + 1)
250
&& !strneq (target, lastslash + 1, stem - lastslash - 1))
253
else if (stem > filename
254
&& !strneq (target, filename, stem - filename))
257
/* Check that the rule pattern matches the text after the stem.
258
We could test simply use streq, but this way we compare the
259
first two characters immediately. This saves time in the very
260
common case where the first character matches because it is a
262
if (*suffix != stem[stemlen]
263
|| (*suffix != '\0' && !streq (&suffix[1], &stem[stemlen + 1])))
266
/* Record if we match a rule that not all filenames will match. */
267
if (target[1] != '\0')
268
specific_rule_matched = 1;
270
/* A rule with no dependencies and no commands exists solely to set
271
specific_rule_matched when it matches. Don't try to use it. */
272
if (rule->deps == 0 && rule->cmds == 0)
275
/* Record this rule in TRYRULES and the index of the matching
276
target in MATCHES. If several targets of the same rule match,
277
that rule will be in TRYRULES more than once. */
278
tryrules[nrules] = rule;
280
checked_lastslash[nrules] = check_lastslash;
285
/* If we have found a matching rule that won't match all filenames,
286
retroactively reject any non-"terminal" rules that do always match. */
287
if (specific_rule_matched)
288
for (i = 0; i < nrules; ++i)
289
if (!tryrules[i]->terminal)
291
register unsigned int j;
292
for (j = 0; tryrules[i]->targets[j] != 0; ++j)
293
if (tryrules[i]->targets[j][1] == '\0')
295
if (tryrules[i]->targets[j] != 0)
299
/* Try each rule once without intermediate files, then once with them. */
300
for (intermed_ok = 0; intermed_ok == !!intermed_ok; ++intermed_ok)
302
/* Try each pattern rule till we find one that applies.
303
If it does, copy the names of its dependencies (as substituted)
304
and store them in FOUND_FILES. DEPS_FOUND is the number of them. */
306
for (i = 0; i < nrules; i++)
312
/* RULE is nil when we discover that a rule,
313
already placed in TRYRULES, should not be applied. */
317
/* Reject any terminal rules if we're
318
looking to make intermediate files. */
319
if (intermed_ok && rule->terminal)
322
/* Mark this rule as in use so a recursive
323
pattern_search won't try to use it. */
326
/* From the lengths of the filename and the matching pattern parts,
327
find the stem: the part of the filename that matches the %. */
329
+ (rule->suffixes[matches[i]] - rule->targets[matches[i]]) - 1;
330
stemlen = namelen - rule->lens[matches[i]] + 1;
331
check_lastslash = checked_lastslash[i];
334
stem += lastslash - filename + 1;
335
stemlen -= (lastslash - filename) + 1;
338
DEBUGP2 (_("Trying pattern rule with stem `%.*s'.\n"),
339
(int) stemlen, stem);
341
/* Try each dependency; see if it "exists". */
344
for (dep = rule->deps; dep != 0; dep = dep->next)
348
/* If the dependency name has a %, substitute the stem. */
349
p = index (dep_name (dep), '%');
352
register unsigned int i;
355
/* Copy directory name from the original FILENAME. */
356
i = lastslash - filename + 1;
357
bcopy (filename, depname, i);
361
bcopy (dep_name (dep), depname + i, p - dep_name (dep));
362
i += p - dep_name (dep);
363
bcopy (stem, depname + i, stemlen);
365
strcpy (depname + i, p + 1);
371
/* P is now the actual dependency name as substituted. */
373
if (file_impossible_p (p))
375
/* If this dependency has already been ruled
376
"impossible", then the rule fails and don't
377
bother trying it on the second pass either
378
since we know that will fail too. */
379
DEBUGP2 (_("Rejecting impossible %s prerequisite `%s'.\n"),
380
p == depname ? _("implicit") : _("rule"), p);
385
intermediate_files[deps_found] = 0;
387
DEBUGP2 (_("Trying %s prerequisite `%s'.\n"),
388
p == depname ? _("implicit") : _("rule"), p);
390
/* The DEP->changed flag says that this dependency resides in a
391
nonexistent directory. So we normally can skip looking for
392
the file. However, if CHECK_LASTSLASH is set, then the
393
dependency file we are actually looking for is in a different
394
directory (the one gotten by prepending FILENAME's directory),
395
so it might actually exist. */
396
/* If we find a file but the intermediate flag is set, then it
397
was put here by a .INTERMEDIATE: rule so ignore it. */
399
if ((!dep->changed || check_lastslash)
400
&& (((fp = lookup_file (p)) != 0 && !fp->intermediate)
401
|| file_exists_p (p)))
403
found_files[deps_found++] = xstrdup (p);
406
/* This code, given FILENAME = "lib/foo.o", dependency name
407
"lib/foo.c", and VPATH=src, searches for "src/lib/foo.c". */
409
if (vpath_search (&vp, (FILE_TIMESTAMP *) 0))
411
DEBUGP2 (_("Found prerequisite `%s' as VPATH `%s'\n"),
414
found_files[deps_found++] = vp;
418
/* We could not find the file in any place we should look.
419
Try to make this dependency as an intermediate file,
420
but only on the second pass. */
424
if (intermediate_file == 0)
426
= (struct file *) alloca (sizeof (struct file));
428
DEBUGP2 (_("Looking for a rule with %s file `%s'.\n"),
429
_("intermediate"), p);
431
bzero ((char *) intermediate_file, sizeof (struct file));
432
intermediate_file->name = p;
433
if (pattern_search (intermediate_file, 0, depth + 1,
437
intermediate_patterns[deps_found]
438
= intermediate_file->name;
439
intermediate_file->name = p;
440
intermediate_files[deps_found] = intermediate_file;
441
intermediate_file = 0;
442
/* Allocate an extra copy to go in FOUND_FILES,
443
because every elt of FOUND_FILES is consumed
445
found_files[deps_found] = xstrdup (p);
450
/* If we have tried to find P as an intermediate
451
file and failed, mark that name as impossible
452
so we won't go through the search again later. */
456
/* A dependency of this rule does not exist.
457
Therefore, this rule fails. */
461
/* This rule is no longer `in use' for recursive searches. */
466
/* This pattern rule does not apply.
467
If some of its dependencies succeeded,
468
free the data structure describing them. */
469
while (deps_found-- > 0)
471
register struct file *f = intermediate_files[deps_found];
472
free (found_files[deps_found]);
474
&& (f->stem < f->name
475
|| f->stem > f->name + strlen (f->name)))
480
/* This pattern rule does apply. Stop looking for one. */
484
/* If we found an applicable rule without
485
intermediate files, don't try with them. */
492
/* RULE is nil if the loop went all the way
493
through the list and everything failed. */
499
/* If we are recursing, store the pattern that matched
500
FILENAME in FILE->name for use in upper levels. */
504
file->name = rule->targets[matches[foundrule]];
506
/* FOUND_FILES lists the dependencies for the rule we found.
507
This includes the intermediate files, if any.
508
Convert them into entries on the deps-chain of FILE. */
510
while (deps_found-- > 0)
514
if (intermediate_files[deps_found] != 0)
516
/* If we need to use an intermediate file,
517
make sure it is entered as a target, with the info that was
518
found for it in the recursive pattern_search call.
519
We know that the intermediate file did not already exist as
520
a target; therefore we can assume that the deps and cmds
521
of F below are null before we change them. */
523
struct file *imf = intermediate_files[deps_found];
524
register struct file *f = enter_file (imf->name);
528
f->also_make = imf->also_make;
529
imf = lookup_file (intermediate_patterns[deps_found]);
530
if (imf != 0 && imf->precious)
533
f->tried_implicit = 1;
534
for (dep = f->deps; dep != 0; dep = dep->next)
536
dep->file = enter_file (dep->name);
537
/* enter_file uses dep->name _if_ we created a new file. */
538
if (dep->name != dep->file->name)
541
dep->file->tried_implicit |= dep->changed;
546
dep = (struct dep *) xmalloc (sizeof (struct dep));
547
s = found_files[deps_found];
551
dep->file = lookup_file (s);
553
/* enter_file consumes S's storage. */
554
dep->file = enter_file (s);
556
/* A copy of S is already allocated in DEP->file->name.
566
if (intermediate_files[deps_found] == 0 && tryrules[foundrule]->terminal)
568
/* If the file actually existed (was not an intermediate file),
569
and the rule that found it was a terminal one, then we want
570
to mark the found file so that it will not have implicit rule
571
search done for it. If we are not entering a `struct file' for
572
it now, we indicate this with the `changed' flag. */
576
dep->file->tried_implicit = 1;
578
dep->next = file->deps;
582
if (!checked_lastslash[foundrule])
583
/* Always allocate new storage, since STEM might be
584
on the stack for an intermediate file. */
585
file->stem = savestring (stem, stemlen);
588
/* We want to prepend the directory from
589
the original FILENAME onto the stem. */
590
file->stem = (char *) xmalloc (((lastslash + 1) - filename)
592
bcopy (filename, file->stem, (lastslash + 1) - filename);
593
bcopy (stem, file->stem + ((lastslash + 1) - filename), stemlen);
594
file->stem[((lastslash + 1) - filename) + stemlen] = '\0';
597
file->cmds = rule->cmds;
599
/* If this rule builds other targets, too, put the others into FILE's
600
`also_make' member. */
602
if (rule->targets[1] != 0)
603
for (i = 0; rule->targets[i] != 0; ++i)
604
if (i != matches[foundrule])
606
struct dep *new = (struct dep *) xmalloc (sizeof (struct dep));
607
new->name = p = (char *) xmalloc (rule->lens[i] + stemlen + 1);
608
bcopy (rule->targets[i], p,
609
rule->suffixes[i] - rule->targets[i] - 1);
610
p += rule->suffixes[i] - rule->targets[i] - 1;
611
bcopy (stem, p, stemlen);
613
bcopy (rule->suffixes[i], p,
614
rule->lens[i] - (rule->suffixes[i] - rule->targets[i]) + 1);
615
new->file = enter_file (new->name);
616
new->next = file->also_make;
617
file->also_make = new;