1 /* Implicit rule searching for GNU Make.
2 Copyright (C) 1988,1989,1990,1991,1992,1993,1994,1997,2000,2004,2005 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. */
26 #include "job.h" /* struct child, used inside commands.h */
27 #include "commands.h" /* set_file_variables */
30 pattern_search
PARAMS ((struct file
*file
, int archive
,
31 unsigned int depth
, unsigned int recursions
));
33 /* For a FILE which has no commands specified, try to figure out some
34 from the implicit pattern rules.
35 Returns 1 if a suitable implicit rule was found,
36 after modifying FILE to contain the appropriate commands and deps,
37 or returns 0 if no implicit rule was found. */
40 try_implicit_rule (struct file
*file
, unsigned int depth
)
42 DBF (DB_IMPLICIT
, _("Looking for an implicit rule for `%s'.\n"));
44 /* The order of these searches was previously reversed. My logic now is
45 that since the non-archive search uses more information in the target
46 (the archive search omits the archive name), it is more specific and
49 if (pattern_search (file
, 0, depth
, 0))
53 /* If this is an archive member reference, use just the
54 archive member name to search for implicit rules. */
55 if (ar_name (file
->name
))
58 _("Looking for archive-member implicit rule for `%s'.\n"));
59 if (pattern_search (file
, 1, depth
, 0))
68 /* Struct idep captures information about implicit prerequisites
69 that come from implicit rules. */
72 struct idep
*next
; /* struct dep -compatible interface */
73 char *name
; /* name of the prerequisite */
74 struct file
*intermediate_file
; /* intermediate file, 0 otherwise */
75 char *intermediate_pattern
; /* pattern for intermediate file */
76 unsigned char had_stem
; /* had % substituted with stem */
77 unsigned char ignore_mtime
; /* ignore_mtime flag */
81 free_idep_chain (struct idep
* p
)
83 register struct idep
* n
;
84 register struct file
*f
;
94 f
= p
->intermediate_file
;
98 || f
->stem
> f
->name
+ strlen (f
->name
)))
107 /* Scans the BUFFER for the next word with whitespace as a separator.
108 Returns the pointer to the beginning of the word. LENGTH hold the
109 length of the word. */
112 get_next_word (char *buffer
, unsigned int *length
)
114 char *p
= buffer
, *beg
;
117 /* Skip any leading whitespace. */
118 while (isblank ((unsigned char)*p
))
128 /* We already found the first value of "c", above. */
146 /* This is a variable reference, so read it to the matching
154 /* This is a single-letter variable reference. */
157 for (count
= 0; *p
!= '\0'; ++p
)
161 else if (*p
== closeparen
&& --count
< 0)
188 /* Search the pattern rules for a rule with an existing dependency to make
189 FILE. If a rule is found, the appropriate commands and deps are put in FILE
190 and 1 is returned. If not, 0 is returned.
192 If ARCHIVE is nonzero, FILE->name is of the form "LIB(MEMBER)". A rule for
193 "(MEMBER)" will be searched for, and "(MEMBER)" will not be chopped up into
194 directory and filename parts.
196 If an intermediate file is found by pattern search, the intermediate file
197 is set up as a target by the recursive call and is also made a dependency
200 DEPTH is used for debugging messages. */
203 pattern_search (struct file
*file
, int archive
,
204 unsigned int depth
, unsigned int recursions
)
206 /* Filename we are searching for a rule for. */
207 char *filename
= archive
? strchr (file
->name
, '(') : file
->name
;
209 /* Length of FILENAME. */
210 unsigned int namelen
= strlen (filename
);
212 /* The last slash in FILENAME (or nil if there is none). */
215 /* This is a file-object used as an argument in
216 recursive calls. It never contains any data
217 except during a recursive call. */
218 struct file
*intermediate_file
= 0;
220 /* This linked list records all the prerequisites actually
221 found for a rule along with some other useful information
222 (see struct idep for details). */
223 struct idep
* deps
= 0;
225 /* 1 if we need to remove explicit prerequisites, 0 otherwise. */
226 unsigned int remove_explicit_deps
= 0;
228 /* Names of possible dependencies are constructed in this buffer. */
229 register char *depname
= (char *) alloca (namelen
+ max_pattern_dep_length
);
231 /* The start and length of the stem of FILENAME for the current rule. */
232 register char *stem
= 0;
233 register unsigned int stemlen
= 0;
234 register unsigned int fullstemlen
= 0;
236 /* Buffer in which we store all the rules that are possibly applicable. */
237 struct rule
**tryrules
238 = (struct rule
**) xmalloc (num_pattern_rules
* max_pattern_targets
239 * sizeof (struct rule
*));
241 /* Number of valid elements in TRYRULES. */
244 /* The numbers of the rule targets of each rule
245 in TRYRULES that matched the target file. */
246 unsigned int *matches
247 = (unsigned int *) alloca (num_pattern_rules
* sizeof (unsigned int));
249 /* Each element is nonzero if LASTSLASH was used in
250 matching the corresponding element of TRYRULES. */
251 char *checked_lastslash
252 = (char *) alloca (num_pattern_rules
* sizeof (char));
254 /* The index in TRYRULES of the rule we found. */
255 unsigned int foundrule
;
257 /* Nonzero if should consider intermediate files as dependencies. */
260 /* Nonzero if we have matched a pattern-rule target
261 that is not just `%'. */
262 int specific_rule_matched
= 0;
264 register unsigned int i
= 0; /* uninit checks OK */
265 register struct rule
*rule
;
266 register struct dep
*dep
, *expl_d
;
271 struct idep
**id_ptr
;
274 PATH_VAR (stem_str
); /* @@ Need to get rid of stem, stemlen, etc. */
277 if (archive
|| ar_name (filename
))
282 /* Set LASTSLASH to point at the last slash in FILENAME
283 but not counting any slash at the end. (foo/bar/ counts as
284 bar/ in directory foo/, not empty in directory foo/bar/.) */
286 lastslash
= strrchr (filename
, ']');
288 lastslash
= strrchr (filename
, ':');
290 lastslash
= strrchr (filename
, '/');
291 #ifdef HAVE_DOS_PATHS
292 /* Handle backslashes (possibly mixed with forward slashes)
293 and the case of "d:file". */
295 char *bslash
= strrchr (filename
, '\\');
296 if (lastslash
== 0 || bslash
> lastslash
)
298 if (lastslash
== 0 && filename
[0] && filename
[1] == ':')
299 lastslash
= filename
+ 1;
303 if (lastslash
!= 0 && lastslash
[1] == '\0')
307 /* First see which pattern rules match this target
308 and may be considered. Put them in TRYRULES. */
311 for (rule
= pattern_rules
; rule
!= 0; rule
= rule
->next
)
313 /* If the pattern rule has deps but no commands, ignore it.
314 Users cancel built-in rules by redefining them without commands. */
315 if (rule
->deps
!= 0 && rule
->cmds
== 0)
318 /* If this rule is in use by a parent pattern_search,
319 don't use it here. */
322 DBS (DB_IMPLICIT
, (_("Avoiding implicit rule recursion.\n")));
326 for (i
= 0; rule
->targets
[i
] != 0; ++i
)
328 char *target
= rule
->targets
[i
];
329 char *suffix
= rule
->suffixes
[i
];
332 /* Rules that can match any filename and are not terminal
333 are ignored if we're recursing, so that they cannot be
334 intermediate files. */
335 if (recursions
> 0 && target
[1] == '\0' && !rule
->terminal
)
338 if (rule
->lens
[i
] > namelen
)
339 /* It can't possibly match. */
342 /* From the lengths of the filename and the pattern parts,
343 find the stem: the part of the filename that matches the %. */
344 stem
= filename
+ (suffix
- target
- 1);
345 stemlen
= namelen
- rule
->lens
[i
] + 1;
347 /* Set CHECK_LASTSLASH if FILENAME contains a directory
348 prefix and the target pattern does not contain a slash. */
351 check_lastslash
= lastslash
!= 0
352 && ((strchr (target
, ']') == 0)
353 && (strchr (target
, ':') == 0));
355 check_lastslash
= lastslash
!= 0 && strchr (target
, '/') == 0;
359 /* In that case, don't include the
360 directory prefix in STEM here. */
361 unsigned int difference
= lastslash
- filename
+ 1;
362 if (difference
> stemlen
)
364 stemlen
-= difference
;
368 /* Check that the rule pattern matches the text before the stem. */
371 if (stem
> (lastslash
+ 1)
372 && !strneq (target
, lastslash
+ 1, stem
- lastslash
- 1))
375 else if (stem
> filename
376 && !strneq (target
, filename
, stem
- filename
))
379 /* Check that the rule pattern matches the text after the stem.
380 We could test simply use streq, but this way we compare the
381 first two characters immediately. This saves time in the very
382 common case where the first character matches because it is a
384 if (*suffix
!= stem
[stemlen
]
385 || (*suffix
!= '\0' && !streq (&suffix
[1], &stem
[stemlen
+ 1])))
388 /* Record if we match a rule that not all filenames will match. */
389 if (target
[1] != '\0')
390 specific_rule_matched
= 1;
392 /* A rule with no dependencies and no commands exists solely to set
393 specific_rule_matched when it matches. Don't try to use it. */
394 if (rule
->deps
== 0 && rule
->cmds
== 0)
397 /* Record this rule in TRYRULES and the index of the matching
398 target in MATCHES. If several targets of the same rule match,
399 that rule will be in TRYRULES more than once. */
400 tryrules
[nrules
] = rule
;
402 checked_lastslash
[nrules
] = check_lastslash
;
407 /* If we have found a matching rule that won't match all filenames,
408 retroactively reject any non-"terminal" rules that do always match. */
409 if (specific_rule_matched
)
410 for (i
= 0; i
< nrules
; ++i
)
411 if (!tryrules
[i
]->terminal
)
413 register unsigned int j
;
414 for (j
= 0; tryrules
[i
]->targets
[j
] != 0; ++j
)
415 if (tryrules
[i
]->targets
[j
][1] == '\0')
417 if (tryrules
[i
]->targets
[j
] != 0)
421 /* We are going to do second expansion so initialize file variables
423 initialize_file_variables (file
, 0);
425 /* Try each rule once without intermediate files, then once with them. */
426 for (intermed_ok
= 0; intermed_ok
== !!intermed_ok
; ++intermed_ok
)
428 /* Try each pattern rule till we find one that applies.
429 If it does, expand its dependencies (as substituted)
430 and chain them in DEPS. */
432 for (i
= 0; i
< nrules
; i
++)
435 unsigned int failed
= 0;
440 remove_explicit_deps
= 0;
442 /* RULE is nil when we discover that a rule,
443 already placed in TRYRULES, should not be applied. */
447 /* Reject any terminal rules if we're
448 looking to make intermediate files. */
449 if (intermed_ok
&& rule
->terminal
)
452 /* Mark this rule as in use so a recursive
453 pattern_search won't try to use it. */
456 /* From the lengths of the filename and the matching pattern parts,
457 find the stem: the part of the filename that matches the %. */
459 + (rule
->suffixes
[matches
[i
]] - rule
->targets
[matches
[i
]]) - 1;
460 stemlen
= namelen
- rule
->lens
[matches
[i
]] + 1;
461 check_lastslash
= checked_lastslash
[i
];
464 stem
+= lastslash
- filename
+ 1;
465 stemlen
-= (lastslash
- filename
) + 1;
468 DBS (DB_IMPLICIT
, (_("Trying pattern rule with stem `%.*s'.\n"),
469 (int) stemlen
, stem
));
471 strncpy (stem_str
, stem
, stemlen
);
472 stem_str
[stemlen
] = '\0';
474 /* Temporary assign STEM to file->stem and set file variables. */
475 file
->stem
= stem_str
;
476 set_file_variables (file
);
478 /* Try each dependency; see if it "exists". */
480 /* @@ There is always only one dep line for any given implicit
481 rule. So the loop is not necessary. Can rule->deps be 0?
483 Watch out for conversion of suffix rules to implicit rules.
486 for (dep
= rule
->deps
; dep
!= 0; dep
= dep
->next
)
490 unsigned int order_only
= 0; /* Set if '|' was seen. */
492 /* In an ideal world we would take the dependency line,
493 substitute the stem, re-expand the whole line and
494 chop it into individual prerequisites. Unfortunately
495 this won't work because of the "check_lastslash" twist.
496 Instead, we will have to go word by word, taking $()'s
497 into account, for each word we will substitute the stem,
498 re-expand, chop it up, and, if check_lastslash != 0,
499 add the directory part to each resulting prerequisite. */
501 p
= get_next_word (dep
->name
, &len
);
509 break; /* No more words */
511 /* If the dependency name has %, substitute the stem.
512 Watch out, we are going to do something tricky here. If
513 we just replace % with the stem value, later, when we do
514 the second expansion, we will re-expand this stem value
515 once again. This is not good especially if you have
516 certain characters in your setm (like $).
518 Instead, we will replace % with $* and allow the second
519 expansion to take care of it for us. This way (since $*
520 is a simple variable) there won't be additional
521 re-expansion of the stem. */
523 for (p2
= p
; p2
< p
+ len
&& *p2
!= '%'; ++p2
)
528 register unsigned int i
= p2
- p
;
529 bcopy (p
, depname
, i
);
530 bcopy ("$*", depname
+ i
, 2);
531 bcopy (p2
+ 1, depname
+ i
+ 2, len
- i
- 1);
532 depname
[len
+ 2 - 1] = '\0';
541 bcopy (p
, depname
, len
);
545 p2
= variable_expand_for_file (depname
, file
);
547 /* Parse the dependencies. */
553 for (; *id_ptr
; id_ptr
= &(*id_ptr
)->next
)
556 *id_ptr
= (struct idep
*)
559 order_only
? '\0' : '|',
560 sizeof (struct idep
),
561 1), sizeof (struct idep
));
563 /* @@ It would be nice to teach parse_file_seq or
564 multi_glob to add prefix. This would save us
565 some reallocations. */
567 if (order_only
|| add_dir
|| had_stem
)
569 unsigned long l
= lastslash
- filename
+ 1;
571 for (d
= *id_ptr
; d
!= 0; d
= d
->next
)
580 d
->name
= xmalloc (strlen (p
) + l
+ 1);
582 bcopy (filename
, d
->name
, l
);
583 bcopy (p
, d
->name
+ l
, strlen (p
) + 1);
593 if (!order_only
&& *p2
)
604 p
= get_next_word (p
, &len
);
608 /* Reset the stem in FILE. */
612 /* @@ This loop can be combined with the previous one. I do
613 it separately for now for transparency.*/
615 for (d
= deps
; d
!= 0; d
= d
->next
)
617 char *name
= d
->name
;
619 if (file_impossible_p (name
))
621 /* If this dependency has already been ruled
622 "impossible", then the rule fails and don't
623 bother trying it on the second pass either
624 since we know that will fail too. */
627 ? _("Rejecting impossible implicit prerequisite `%s'.\n")
628 : _("Rejecting impossible rule prerequisite `%s'.\n"),
638 ? _("Trying implicit prerequisite `%s'.\n")
639 : _("Trying rule prerequisite `%s'.\n"), name
));
641 /* If this prerequisite also happened to be explicitly
642 mentioned for FILE skip all the test below since it
643 it has to be built anyway, no matter which implicit
646 for (expl_d
= file
->deps
; expl_d
!= 0; expl_d
= expl_d
->next
)
647 if (strcmp (dep_name (expl_d
), name
) == 0) break;
654 /* The DEP->changed flag says that this dependency resides in a
655 nonexistent directory. So we normally can skip looking for
656 the file. However, if CHECK_LASTSLASH is set, then the
657 dependency file we are actually looking for is in a different
658 directory (the one gotten by prepending FILENAME's directory),
659 so it might actually exist. */
661 /* @@ dep->changed check is disabled. */
662 if (((f
= lookup_file (name
)) != 0 && f
->is_target
)
663 /*|| ((!dep->changed || check_lastslash) && */
664 || file_exists_p (name
))
669 /* This code, given FILENAME = "lib/foo.o", dependency name
670 "lib/foo.c", and VPATH=src, searches for "src/lib/foo.c". */
672 if (vpath_search (&vname
, (FILE_TIMESTAMP
*) 0))
675 (_("Found prerequisite `%s' as VPATH `%s'\n"),
684 /* We could not find the file in any place we should look.
685 Try to make this dependency as an intermediate file,
686 but only on the second pass. */
690 if (intermediate_file
== 0)
692 = (struct file
*) alloca (sizeof (struct file
));
695 (_("Looking for a rule with intermediate file `%s'.\n"),
698 bzero ((char *) intermediate_file
, sizeof (struct file
));
699 intermediate_file
->name
= name
;
700 if (pattern_search (intermediate_file
,
705 d
->intermediate_file
= intermediate_file
;
706 d
->intermediate_pattern
= intermediate_file
->name
;
708 intermediate_file
->name
= xstrdup (name
);
709 intermediate_file
= 0;
714 /* If we have tried to find P as an intermediate
715 file and failed, mark that name as impossible
716 so we won't go through the search again later. */
717 file_impossible (name
);
720 /* A dependency of this rule does not exist. Therefore,
726 /* This rule is no longer `in use' for recursive searches. */
731 /* This pattern rule does not apply. If some of its
732 dependencies succeeded, free the data structure
734 free_idep_chain (deps
);
738 /* This pattern rule does apply. Stop looking for one. */
742 /* If we found an applicable rule without
743 intermediate files, don't try with them. */
750 /* RULE is nil if the loop went all the way
751 through the list and everything failed. */
757 /* If we are recursing, store the pattern that matched
758 FILENAME in FILE->name for use in upper levels. */
762 file
->name
= rule
->targets
[matches
[foundrule
]];
764 /* FOUND_FILES lists the dependencies for the rule we found.
765 This includes the intermediate files, if any.
766 Convert them into entries on the deps-chain of FILE. */
768 if (remove_explicit_deps
)
770 /* Remove all the dependencies that didn't come from
771 this implicit rule. */
776 struct dep
*next
= dep
->next
;
784 expl_d
= file
->deps
; /* We will add them at the end. */
787 for (d
= deps
; d
!= 0; d
= d
->next
)
791 if (d
->intermediate_file
!= 0)
793 /* If we need to use an intermediate file,
794 make sure it is entered as a target, with the info that was
795 found for it in the recursive pattern_search call.
796 We know that the intermediate file did not already exist as
797 a target; therefore we can assume that the deps and cmds
798 of F below are null before we change them. */
800 struct file
*imf
= d
->intermediate_file
;
801 register struct file
*f
= lookup_file (imf
->name
);
803 /* We don't want to delete an intermediate file that happened
804 to be a prerequisite of some (other) target. Mark it as
809 f
= enter_file (imf
->name
);
814 f
->also_make
= imf
->also_make
;
819 imf
= lookup_file (d
->intermediate_pattern
);
820 if (imf
!= 0 && imf
->precious
)
825 f
->tried_implicit
= 1;
826 for (dep
= f
->deps
; dep
!= 0; dep
= dep
->next
)
828 dep
->file
= enter_file (dep
->name
);
829 /* enter_file uses dep->name _if_ we created a new file. */
830 if (dep
->name
!= dep
->file
->name
)
833 dep
->file
->tried_implicit
|= dep
->changed
;
837 dep
= (struct dep
*) xmalloc (sizeof (struct dep
));
838 dep
->ignore_mtime
= d
->ignore_mtime
;
839 dep
->need_2nd_expansion
= 0;
840 s
= d
->name
; /* Hijacking the name. */
845 dep
->file
= lookup_file (s
);
847 /* enter_file consumes S's storage. */
848 dep
->file
= enter_file (s
);
850 /* A copy of S is already allocated in DEP->file->name.
860 if (d
->intermediate_file
== 0 && tryrules
[foundrule
]->terminal
)
862 /* If the file actually existed (was not an intermediate file),
863 and the rule that found it was a terminal one, then we want
864 to mark the found file so that it will not have implicit rule
865 search done for it. If we are not entering a `struct file' for
866 it now, we indicate this with the `changed' flag. */
870 dep
->file
->tried_implicit
= 1;
879 if (!checked_lastslash
[foundrule
])
881 /* Always allocate new storage, since STEM might be
882 on the stack for an intermediate file. */
883 file
->stem
= savestring (stem
, stemlen
);
884 fullstemlen
= stemlen
;
888 int dirlen
= (lastslash
+ 1) - filename
;
890 /* We want to prepend the directory from
891 the original FILENAME onto the stem. */
892 fullstemlen
= dirlen
+ stemlen
;
893 file
->stem
= (char *) xmalloc (fullstemlen
+ 1);
894 bcopy (filename
, file
->stem
, dirlen
);
895 bcopy (stem
, file
->stem
+ dirlen
, stemlen
);
896 file
->stem
[fullstemlen
] = '\0';
899 file
->cmds
= rule
->cmds
;
902 /* Set precious flag. */
904 struct file
*f
= lookup_file (rule
->targets
[matches
[foundrule
]]);
905 if (f
&& f
->precious
)
909 /* If this rule builds other targets, too, put the others into FILE's
910 `also_make' member. */
912 if (rule
->targets
[1] != 0)
913 for (i
= 0; rule
->targets
[i
] != 0; ++i
)
914 if (i
!= matches
[foundrule
])
917 struct dep
*new = (struct dep
*) xmalloc (sizeof (struct dep
));
918 /* GKM FIMXE: handle '|' here too */
919 new->ignore_mtime
= 0;
920 new->need_2nd_expansion
= 0;
921 new->name
= p
= (char *) xmalloc (rule
->lens
[i
] + fullstemlen
+ 1);
922 bcopy (rule
->targets
[i
], p
,
923 rule
->suffixes
[i
] - rule
->targets
[i
] - 1);
924 p
+= rule
->suffixes
[i
] - rule
->targets
[i
] - 1;
925 bcopy (file
->stem
, p
, fullstemlen
);
927 bcopy (rule
->suffixes
[i
], p
,
928 rule
->lens
[i
] - (rule
->suffixes
[i
] - rule
->targets
[i
]) + 1);
929 new->file
= enter_file (new->name
);
930 new->next
= file
->also_make
;
932 /* Set precious flag. */
933 f
= lookup_file (rule
->targets
[i
]);
934 if (f
&& f
->precious
)
935 new->file
->precious
= 1;
937 file
->also_make
= new;
941 free_idep_chain (deps
);