1 /* Implicit rule searching for GNU Make.
2 Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993 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, 675 Mass Ave, Cambridge, MA 02139, USA. */
24 static int pattern_search ();
26 /* For a FILE which has no commands specified, try to figure out some
27 from the implicit pattern rules.
28 Returns 1 if a suitable implicit rule was found,
29 after modifying FILE to contain the appropriate commands and deps,
30 or returns 0 if no implicit rule was found. */
33 try_implicit_rule (file
, depth
)
37 DEBUGPR ("Looking for an implicit rule for `%s'.\n");
40 /* If this is an archive member reference, use just the
41 archive member name to search for implicit rules. */
42 if (ar_name (file
->name
))
44 DEBUGPR ("Looking for archive-member implicit rule for `%s'.\n");
45 if (pattern_search (file
, 1, depth
, 0))
50 return pattern_search (file
, 0, depth
, 0);
53 #define DEBUGP2(msg, a1, a2) \
56 { print_spaces (depth); printf (msg, a1, a2); fflush (stdout); } \
59 /* Search the pattern rules for a rule with an existing dependency to make
60 FILE. If a rule is found, the appropriate commands and deps are put in FILE
61 and 1 is returned. If not, 0 is returned.
63 If ARCHIVE is nonzero, FILE->name is of the form "LIB(MEMBER)". A rule for
64 "(MEMBER)" will be searched for, and "(MEMBER)" will not be chopped up into
65 directory and filename parts.
67 If an intermediate file is found by pattern search, the intermediate file
68 is set up as a target by the recursive call and is also made a dependency
71 DEPTH is used for debugging messages. */
74 pattern_search (file
, archive
, depth
, recursions
)
78 unsigned int recursions
;
80 /* Filename we are searching for a rule for. */
81 char *filename
= archive
? index (file
->name
, '(') : file
->name
;
83 /* Length of FILENAME. */
84 unsigned int namelen
= strlen (filename
);
86 /* The last slash in FILENAME (or nil if there is none). */
89 /* This is a file-object used as an argument in
90 recursive calls. It never contains any data
91 except during a recursive call. */
92 struct file
*intermediate_file
= 0;
94 /* List of dependencies found recursively. */
95 struct file
**intermediate_files
96 = (struct file
**) alloca (max_pattern_deps
* sizeof (struct file
*));
98 /* List of the patterns used to find intermediate files. */
99 char **intermediate_patterns
100 = (char **) alloca (max_pattern_deps
* sizeof (char *));
102 /* This buffer records all the dependencies actually found for a rule. */
103 char **found_files
= (char **) alloca (max_pattern_deps
* sizeof (char *));
104 /* Number of dep names now in FOUND_FILES. */
105 unsigned int deps_found
;
107 /* Names of possible dependencies are constructed in this buffer. */
108 register char *depname
= (char *) alloca (namelen
+ max_pattern_dep_length
);
110 /* The start and length of the stem of FILENAME for the current rule. */
112 register unsigned int stemlen
;
114 /* Buffer in which we store all the rules that are possibly applicable. */
115 struct rule
**tryrules
116 = (struct rule
**) alloca (num_pattern_rules
* max_pattern_targets
117 * sizeof (struct rule
*));
119 /* Number of valid elements in TRYRULES. */
122 /* The numbers of the rule targets of each rule
123 in TRYRULES that matched the target file. */
124 unsigned int *matches
125 = (unsigned int *) alloca (num_pattern_rules
* sizeof (unsigned int));
127 /* Each element is nonzero if LASTSLASH was used in
128 matching the corresponding element of TRYRULES. */
129 char *checked_lastslash
130 = (char *) alloca (num_pattern_rules
* sizeof (char));
132 /* The index in TRYRULES of the rule we found. */
133 unsigned int foundrule
;
135 /* Nonzero if should consider intermediate files as dependencies. */
138 /* Nonzero if we have matched a pattern-rule target
139 that is not just `%'. */
140 int specific_rule_matched
= 0;
142 register unsigned int i
;
143 register struct rule
*rule
;
144 register struct dep
*dep
;
149 if (archive
|| ar_name (filename
))
154 /* Set LASTSLASH to point at the last slash in FILENAME
155 but not counting any slash at the end. (foo/bar/ counts as
156 bar/ in directory foo/, not empty in directory foo/bar/.) */
157 lastslash
= rindex (filename
, '/');
158 if (lastslash
!= 0 && lastslash
[1] == '\0')
162 /* First see which pattern rules match this target
163 and may be considered. Put them in TRYRULES. */
166 for (rule
= pattern_rules
; rule
!= 0; rule
= rule
->next
)
168 /* If the pattern rule has deps but no commands, ignore it.
169 Users cancel built-in rules by redefining them without commands. */
170 if (rule
->deps
!= 0 && rule
->cmds
== 0)
173 /* If this rule is in use by a parent pattern_search,
174 don't use it here. */
177 DEBUGP2 ("Avoiding implicit rule recursion.%s%s\n", "", "");
181 for (i
= 0; rule
->targets
[i
] != 0; ++i
)
183 char *target
= rule
->targets
[i
];
184 char *suffix
= rule
->suffixes
[i
];
187 /* Rules that can match any filename and are not terminal
188 are ignored if we're recursing, so that they cannot be
189 intermediate files. */
190 if (recursions
> 0 && target
[1] == '\0' && !rule
->terminal
)
193 if (rule
->lens
[i
] > namelen
)
194 /* It can't possibly match. */
197 /* From the lengths of the filename and the pattern parts,
198 find the stem: the part of the filename that matches the %. */
199 stem
= filename
+ (suffix
- target
- 1);
200 stemlen
= namelen
- rule
->lens
[i
] + 1;
202 /* Set CHECK_LASTSLASH if FILENAME contains a directory
203 prefix and the target pattern does not contain a slash. */
205 check_lastslash
= lastslash
!= 0 && index (target
, '/') == 0;
208 /* In that case, don't include the
209 directory prefix in STEM here. */
210 unsigned int difference
= lastslash
- filename
+ 1;
211 if (difference
> stemlen
)
213 stemlen
-= difference
;
217 /* Check that the rule pattern matches the text before the stem. */
220 if (stem
> (lastslash
+ 1)
221 && strncmp (target
, lastslash
+ 1, stem
- lastslash
- 1))
224 else if (stem
> filename
225 && strncmp (target
, filename
, stem
- filename
))
228 /* Check that the rule pattern matches the text after the stem.
229 We could test simply use streq, but this way we compare the
230 first two characters immediately. This saves time in the very
231 common case where the first character matches because it is a
233 if (*suffix
!= stem
[stemlen
]
234 || (*suffix
!= '\0' && !streq (&suffix
[1], &stem
[stemlen
+ 1])))
237 /* Record if we match a rule that not all filenames will match. */
238 if (target
[1] != '\0')
239 specific_rule_matched
= 1;
241 /* A rule with no dependencies and no commands exists solely to set
242 specific_rule_matched when it matches. Don't try to use it. */
243 if (rule
->deps
== 0 && rule
->cmds
== 0)
246 /* Record this rule in TRYRULES and the index of the matching
247 target in MATCHES. If several targets of the same rule match,
248 that rule will be in TRYRULES more than once. */
249 tryrules
[nrules
] = rule
;
251 checked_lastslash
[nrules
] = check_lastslash
;
256 /* If we have found a matching rule that won't match all filenames,
257 retroactively reject any "terminal" rules that do always match. */
258 if (specific_rule_matched
)
259 for (i
= 0; i
< nrules
; ++i
)
260 if (!tryrules
[i
]->terminal
)
262 register unsigned int j
;
263 for (j
= 0; tryrules
[i
]->targets
[j
] != 0; ++j
)
264 if (tryrules
[i
]->targets
[j
][1] == '\0')
266 if (tryrules
[i
]->targets
[j
] != 0)
270 /* Try each rule once without intermediate files, then once with them. */
271 for (intermed_ok
= 0; intermed_ok
== !!intermed_ok
; ++intermed_ok
)
273 /* Try each pattern rule till we find one that applies.
274 If it does, copy the names of its dependencies (as substituted)
275 and store them in FOUND_FILES. DEPS_FOUND is the number of them. */
277 for (i
= 0; i
< nrules
; i
++)
283 /* RULE is nil when we discover that a rule,
284 already placed in TRYRULES, should not be applied. */
288 /* Reject any terminal rules if we're
289 looking to make intermediate files. */
290 if (intermed_ok
&& rule
->terminal
)
293 /* Mark this rule as in use so a recursive
294 pattern_search won't try to use it. */
297 /* From the lengths of the filename and the matching pattern parts,
298 find the stem: the part of the filename that matches the %. */
300 + (rule
->suffixes
[matches
[i
]] - rule
->targets
[matches
[i
]]) - 1;
301 stemlen
= namelen
- rule
->lens
[matches
[i
]] + 1;
302 check_lastslash
= checked_lastslash
[i
];
305 stem
+= lastslash
- filename
+ 1;
306 stemlen
-= (lastslash
- filename
) + 1;
309 DEBUGP2 ("Trying pattern rule with stem `%.*s'.\n",
310 (int) stemlen
, stem
);
312 /* Try each dependency; see if it "exists". */
315 for (dep
= rule
->deps
; dep
!= 0; dep
= dep
->next
)
317 /* If the dependency name has a %, substitute the stem. */
318 p
= index (dep_name (dep
), '%');
321 register unsigned int i
;
324 /* Copy directory name from the original FILENAME. */
325 i
= lastslash
- filename
+ 1;
326 bcopy (filename
, depname
, i
);
330 bcopy (dep_name (dep
), depname
+ i
, p
- dep_name (dep
));
331 i
+= p
- dep_name (dep
);
332 bcopy (stem
, depname
+ i
, stemlen
);
334 strcpy (depname
+ i
, p
+ 1);
340 /* P is now the actual dependency name as substituted. */
342 if (file_impossible_p (p
))
344 /* If this dependency has already been ruled
345 "impossible", then the rule fails and don't
346 bother trying it on the second pass either
347 since we know that will fail too. */
348 DEBUGP2 ("Rejecting impossible %s dependency `%s'.\n",
349 p
== depname
? "implicit" : "rule", p
);
354 intermediate_files
[deps_found
] = 0;
356 DEBUGP2 ("Trying %s dependency `%s'.\n",
357 p
== depname
? "implicit" : "rule", p
);
359 /* The DEP->changed flag says that this dependency resides in a
360 nonexistent directory. So we normally can skip looking for
361 the file. However, if CHECK_LASTSLASH is set, then the
362 dependency file we are actually looking for is in a different
363 directory (the one gotten by prepending FILENAME's directory),
364 so it might actually exist. */
366 if ((!dep
->changed
|| check_lastslash
)
367 && (lookup_file (p
) != 0 || file_exists_p (p
)))
369 found_files
[deps_found
++] = savestring (p
, strlen (p
));
372 /* This code, given FILENAME = "lib/foo.o", dependency name
373 "lib/foo.c", and VPATH=src, searches for "src/lib/foo.c". */
374 if (vpath_search (&p
, (time_t *) 0))
376 DEBUGP2 ("Found dependency as `%s'.%s\n", p
, "");
377 found_files
[deps_found
++] = p
;
381 /* We could not find the file in any place we should look.
382 Try to make this dependency as an intermediate file,
383 but only on the second pass. */
387 if (intermediate_file
== 0)
389 = (struct file
*) alloca (sizeof (struct file
));
391 DEBUGP2 ("Looking for a rule with %s file `%s'.\n",
394 bzero ((char *) intermediate_file
, sizeof (struct file
));
395 intermediate_file
->name
= p
;
396 if (pattern_search (intermediate_file
, 0, depth
+ 1,
399 p
= savestring (p
, strlen (p
));
400 intermediate_patterns
[deps_found
]
401 = intermediate_file
->name
;
402 intermediate_file
->name
= p
;
403 intermediate_files
[deps_found
] = intermediate_file
;
404 intermediate_file
= 0;
405 /* Allocate an extra copy to go in FOUND_FILES,
406 because every elt of FOUND_FILES is consumed
408 found_files
[deps_found
] = savestring (p
, strlen (p
));
413 /* If we have tried to find P as an intermediate
414 file and failed, mark that name as impossible
415 so we won't go through the search again later. */
419 /* A dependency of this rule does not exist.
420 Therefore, this rule fails. */
424 /* This rule is no longer `in use' for recursive searches. */
429 /* This pattern rule does not apply.
430 If some of its dependencies succeeded,
431 free the data structure describing them. */
432 while (deps_found
-- > 0)
434 register struct file
*f
= intermediate_files
[deps_found
];
435 free (found_files
[deps_found
]);
437 && (f
->stem
< f
->name
438 || f
->stem
> f
->name
+ strlen (f
->name
)))
443 /* This pattern rule does apply. Stop looking for one. */
447 /* If we found an applicable rule without
448 intermediate files, don't try with them. */
455 /* RULE is nil if the loop went all the way
456 through the list and everything failed. */
462 /* If we are recursing, store the pattern that matched
463 FILENAME in FILE->name for use in upper levels. */
467 file
->name
= rule
->targets
[matches
[foundrule
]];
469 /* FOUND_FILES lists the dependencies for the rule we found.
470 This includes the intermediate files, if any.
471 Convert them into entries on the deps-chain of FILE. */
473 while (deps_found
-- > 0)
477 if (intermediate_files
[deps_found
] != 0)
479 /* If we need to use an intermediate file,
480 make sure it is entered as a target, with the info that was
481 found for it in the recursive pattern_search call.
482 We know that the intermediate file did not already exist as
483 a target; therefore we can assume that the deps and cmds
484 of F below are null before we change them. */
486 struct file
*imf
= intermediate_files
[deps_found
];
487 register struct file
*f
= enter_file (imf
->name
);
491 imf
= lookup_file (intermediate_patterns
[deps_found
]);
492 if (imf
!= 0 && imf
->precious
)
495 f
->tried_implicit
= 1;
496 for (dep
= f
->deps
; dep
!= 0; dep
= dep
->next
)
498 dep
->file
= enter_file (dep
->name
);
500 dep
->file
->tried_implicit
|= dep
->changed
;
505 dep
= (struct dep
*) xmalloc (sizeof (struct dep
));
506 s
= found_files
[deps_found
];
510 dep
->file
= lookup_file (s
);
512 /* enter_file consumes S's storage. */
513 dep
->file
= enter_file (s
);
515 /* A copy of S is already allocated in DEP->file->name.
525 if (intermediate_files
[deps_found
] == 0 && tryrules
[foundrule
]->terminal
)
527 /* If the file actually existed (was not an intermediate file),
528 and the rule that found it was a terminal one, then we want
529 to mark the found file so that it will not have implicit rule
530 search done for it. If we are not entering a `struct file' for
531 it now, we indicate this with the `changed' flag. */
535 dep
->file
->tried_implicit
= 1;
537 dep
->next
= file
->deps
;
541 if (!checked_lastslash
[foundrule
])
542 file
->stem
= stem
[stemlen
] == '\0' ? stem
: savestring (stem
, stemlen
);
545 /* We want to prepend the directory from
546 the original FILENAME onto the stem. */
547 file
->stem
= (char *) xmalloc (((lastslash
+ 1) - filename
)
549 bcopy (filename
, file
->stem
, (lastslash
+ 1) - filename
);
550 bcopy (stem
, file
->stem
+ ((lastslash
+ 1) - filename
), stemlen
);
551 file
->stem
[((lastslash
+ 1) - filename
) + stemlen
] = '\0';
554 file
->cmds
= rule
->cmds
;
556 /* Put the targets other than the one that
557 matched into FILE's `also_make' member. */
559 /* If there was only one target, there is nothing to do. */
560 if (rule
->targets
[1] != 0)
561 for (i
= 0; rule
->targets
[i
] != 0; ++i
)
562 if (i
!= matches
[foundrule
])
564 struct dep
*new = (struct dep
*) xmalloc (sizeof (struct dep
));
565 new->name
= p
= (char *) xmalloc (rule
->lens
[i
] + stemlen
+ 1);
566 bcopy (rule
->targets
[i
], p
,
567 rule
->suffixes
[i
] - rule
->targets
[i
] - 1);
568 p
+= rule
->suffixes
[i
] - rule
->targets
[i
] - 1;
569 bcopy (stem
, p
, stemlen
);
571 bcopy (rule
->suffixes
[i
], p
,
572 rule
->lens
[i
] - (rule
->suffixes
[i
] - rule
->targets
[i
]) + 1);
573 new->file
= enter_file (new->name
);
574 new->next
= file
->also_make
;
575 file
->also_make
= new;