1 /* Implicit rule searching for GNU Make.
2 Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1997,
3 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006 Free Software
5 This file is part of GNU Make.
7 GNU Make is free software; you can redistribute it and/or modify it under the
8 terms of the GNU General Public License as published by the Free Software
9 Foundation; either version 2, or (at your option) any later version.
11 GNU Make is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
13 A PARTICULAR PURPOSE. See the GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License along with
16 GNU Make; see the file COPYING. If not, write to the Free Software
17 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. */
25 #include "job.h" /* struct child, used inside commands.h */
26 #include "commands.h" /* set_file_variables */
29 pattern_search
PARAMS ((struct file
*file
, int archive
,
30 unsigned int depth
, unsigned int recursions
));
32 /* For a FILE which has no commands specified, try to figure out some
33 from the implicit pattern rules.
34 Returns 1 if a suitable implicit rule was found,
35 after modifying FILE to contain the appropriate commands and deps,
36 or returns 0 if no implicit rule was found. */
39 try_implicit_rule (struct file
*file
, unsigned int depth
)
41 DBF (DB_IMPLICIT
, _("Looking for an implicit rule for `%s'.\n"));
43 /* The order of these searches was previously reversed. My logic now is
44 that since the non-archive search uses more information in the target
45 (the archive search omits the archive name), it is more specific and
48 if (pattern_search (file
, 0, depth
, 0))
52 /* If this is an archive member reference, use just the
53 archive member name to search for implicit rules. */
54 if (ar_name (file
->name
))
57 _("Looking for archive-member implicit rule for `%s'.\n"));
58 if (pattern_search (file
, 1, depth
, 0))
67 /* Struct idep captures information about implicit prerequisites
68 that come from implicit rules. */
71 struct idep
*next
; /* struct dep -compatible interface */
72 char *name
; /* name of the prerequisite */
73 struct file
*intermediate_file
; /* intermediate file, 0 otherwise */
74 char *intermediate_pattern
; /* pattern for intermediate file */
75 unsigned char had_stem
; /* had % substituted with stem */
76 unsigned char ignore_mtime
; /* ignore_mtime flag */
80 free_idep_chain (struct idep
*p
)
92 f
= p
->intermediate_file
;
94 && (f
->stem
< f
->name
|| f
->stem
> f
->name
+ strlen (f
->name
)))
102 /* Scans the BUFFER for the next word with whitespace as a separator.
103 Returns the pointer to the beginning of the word. LENGTH hold the
104 length of the word. */
107 get_next_word (char *buffer
, unsigned int *length
)
109 char *p
= buffer
, *beg
;
112 /* Skip any leading whitespace. */
113 while (isblank ((unsigned char)*p
))
123 /* We already found the first value of "c", above. */
141 /* This is a variable reference, so read it to the matching
149 /* This is a single-letter variable reference. */
152 for (count
= 0; *p
!= '\0'; ++p
)
156 else if (*p
== closeparen
&& --count
< 0)
183 /* Search the pattern rules for a rule with an existing dependency to make
184 FILE. If a rule is found, the appropriate commands and deps are put in FILE
185 and 1 is returned. If not, 0 is returned.
187 If ARCHIVE is nonzero, FILE->name is of the form "LIB(MEMBER)". A rule for
188 "(MEMBER)" will be searched for, and "(MEMBER)" will not be chopped up into
189 directory and filename parts.
191 If an intermediate file is found by pattern search, the intermediate file
192 is set up as a target by the recursive call and is also made a dependency
195 DEPTH is used for debugging messages. */
198 pattern_search (struct file
*file
, int archive
,
199 unsigned int depth
, unsigned int recursions
)
201 /* Filename we are searching for a rule for. */
202 char *filename
= archive
? strchr (file
->name
, '(') : file
->name
;
204 /* Length of FILENAME. */
205 unsigned int namelen
= strlen (filename
);
207 /* The last slash in FILENAME (or nil if there is none). */
210 /* This is a file-object used as an argument in
211 recursive calls. It never contains any data
212 except during a recursive call. */
213 struct file
*intermediate_file
= 0;
215 /* This linked list records all the prerequisites actually
216 found for a rule along with some other useful information
217 (see struct idep for details). */
218 struct idep
* deps
= 0;
220 /* 1 if we need to remove explicit prerequisites, 0 otherwise. */
221 unsigned int remove_explicit_deps
= 0;
223 /* Names of possible dependencies are constructed in this buffer. */
224 register char *depname
= (char *) alloca (namelen
+ max_pattern_dep_length
);
226 /* The start and length of the stem of FILENAME for the current rule. */
227 register char *stem
= 0;
228 register unsigned int stemlen
= 0;
229 register unsigned int fullstemlen
= 0;
231 /* Buffer in which we store all the rules that are possibly applicable. */
232 struct rule
**tryrules
233 = (struct rule
**) xmalloc (num_pattern_rules
* max_pattern_targets
234 * sizeof (struct rule
*));
236 /* Number of valid elements in TRYRULES. */
239 /* The numbers of the rule targets of each rule
240 in TRYRULES that matched the target file. */
241 unsigned int *matches
242 = (unsigned int *) alloca (num_pattern_rules
* sizeof (unsigned int));
244 /* Each element is nonzero if LASTSLASH was used in
245 matching the corresponding element of TRYRULES. */
246 char *checked_lastslash
247 = (char *) alloca (num_pattern_rules
* sizeof (char));
249 /* The index in TRYRULES of the rule we found. */
250 unsigned int foundrule
;
252 /* Nonzero if should consider intermediate files as dependencies. */
255 /* Nonzero if we have matched a pattern-rule target
256 that is not just `%'. */
257 int specific_rule_matched
= 0;
259 unsigned int i
= 0; /* uninit checks OK */
261 struct dep
*dep
, *expl_d
;
266 struct idep
**id_ptr
;
269 PATH_VAR (stem_str
); /* @@ Need to get rid of stem, stemlen, etc. */
272 if (archive
|| ar_name (filename
))
277 /* Set LASTSLASH to point at the last slash in FILENAME
278 but not counting any slash at the end. (foo/bar/ counts as
279 bar/ in directory foo/, not empty in directory foo/bar/.) */
281 lastslash
= strrchr (filename
, ']');
283 lastslash
= strrchr (filename
, ':');
285 lastslash
= strrchr (filename
, '/');
286 #ifdef HAVE_DOS_PATHS
287 /* Handle backslashes (possibly mixed with forward slashes)
288 and the case of "d:file". */
290 char *bslash
= strrchr (filename
, '\\');
291 if (lastslash
== 0 || bslash
> lastslash
)
293 if (lastslash
== 0 && filename
[0] && filename
[1] == ':')
294 lastslash
= filename
+ 1;
298 if (lastslash
!= 0 && lastslash
[1] == '\0')
302 /* First see which pattern rules match this target
303 and may be considered. Put them in TRYRULES. */
306 for (rule
= pattern_rules
; rule
!= 0; rule
= rule
->next
)
308 /* If the pattern rule has deps but no commands, ignore it.
309 Users cancel built-in rules by redefining them without commands. */
310 if (rule
->deps
!= 0 && rule
->cmds
== 0)
313 /* If this rule is in use by a parent pattern_search,
314 don't use it here. */
317 DBS (DB_IMPLICIT
, (_("Avoiding implicit rule recursion.\n")));
321 for (i
= 0; rule
->targets
[i
] != 0; ++i
)
323 char *target
= rule
->targets
[i
];
324 char *suffix
= rule
->suffixes
[i
];
327 /* Rules that can match any filename and are not terminal
328 are ignored if we're recursing, so that they cannot be
329 intermediate files. */
330 if (recursions
> 0 && target
[1] == '\0' && !rule
->terminal
)
333 if (rule
->lens
[i
] > namelen
)
334 /* It can't possibly match. */
337 /* From the lengths of the filename and the pattern parts,
338 find the stem: the part of the filename that matches the %. */
339 stem
= filename
+ (suffix
- target
- 1);
340 stemlen
= namelen
- rule
->lens
[i
] + 1;
342 /* Set CHECK_LASTSLASH if FILENAME contains a directory
343 prefix and the target pattern does not contain a slash. */
349 check_lastslash
= (strchr (target
, ']') == 0
350 && strchr (target
, ':') == 0);
352 check_lastslash
= strchr (target
, '/') == 0;
353 #ifdef HAVE_DOS_PATHS
354 /* Didn't find it yet: check for DOS-type directories. */
355 if (!check_lastslash
)
357 char *b
= strrchr (target
, '\\');
358 check_lastslash
= !(b
? b
> lastslash
359 : (target
[0] && target
[1] == ':'));
366 /* If so, don't include the directory prefix in STEM here. */
367 unsigned int difference
= lastslash
- filename
+ 1;
368 if (difference
> stemlen
)
370 stemlen
-= difference
;
374 /* Check that the rule pattern matches the text before the stem. */
377 if (stem
> (lastslash
+ 1)
378 && !strneq (target
, lastslash
+ 1, stem
- lastslash
- 1))
381 else if (stem
> filename
382 && !strneq (target
, filename
, stem
- filename
))
385 /* Check that the rule pattern matches the text after the stem.
386 We could test simply use streq, but this way we compare the
387 first two characters immediately. This saves time in the very
388 common case where the first character matches because it is a
390 if (*suffix
!= stem
[stemlen
]
391 || (*suffix
!= '\0' && !streq (&suffix
[1], &stem
[stemlen
+ 1])))
394 /* Record if we match a rule that not all filenames will match. */
395 if (target
[1] != '\0')
396 specific_rule_matched
= 1;
398 /* A rule with no dependencies and no commands exists solely to set
399 specific_rule_matched when it matches. Don't try to use it. */
400 if (rule
->deps
== 0 && rule
->cmds
== 0)
403 /* Record this rule in TRYRULES and the index of the matching
404 target in MATCHES. If several targets of the same rule match,
405 that rule will be in TRYRULES more than once. */
406 tryrules
[nrules
] = rule
;
408 checked_lastslash
[nrules
] = check_lastslash
;
413 /* If we have found a matching rule that won't match all filenames,
414 retroactively reject any non-"terminal" rules that do always match. */
415 if (specific_rule_matched
)
416 for (i
= 0; i
< nrules
; ++i
)
417 if (!tryrules
[i
]->terminal
)
419 register unsigned int j
;
420 for (j
= 0; tryrules
[i
]->targets
[j
] != 0; ++j
)
421 if (tryrules
[i
]->targets
[j
][1] == '\0')
423 if (tryrules
[i
]->targets
[j
] != 0)
427 /* We are going to do second expansion so initialize file variables
429 initialize_file_variables (file
, 0);
431 /* Try each rule once without intermediate files, then once with them. */
432 for (intermed_ok
= 0; intermed_ok
== !!intermed_ok
; ++intermed_ok
)
434 /* Try each pattern rule till we find one that applies.
435 If it does, expand its dependencies (as substituted)
436 and chain them in DEPS. */
438 for (i
= 0; i
< nrules
; i
++)
441 unsigned int failed
= 0;
446 remove_explicit_deps
= 0;
448 /* RULE is nil when we discover that a rule,
449 already placed in TRYRULES, should not be applied. */
453 /* Reject any terminal rules if we're
454 looking to make intermediate files. */
455 if (intermed_ok
&& rule
->terminal
)
458 /* Mark this rule as in use so a recursive
459 pattern_search won't try to use it. */
462 /* From the lengths of the filename and the matching pattern parts,
463 find the stem: the part of the filename that matches the %. */
465 + (rule
->suffixes
[matches
[i
]] - rule
->targets
[matches
[i
]]) - 1;
466 stemlen
= namelen
- rule
->lens
[matches
[i
]] + 1;
467 check_lastslash
= checked_lastslash
[i
];
470 stem
+= lastslash
- filename
+ 1;
471 stemlen
-= (lastslash
- filename
) + 1;
474 DBS (DB_IMPLICIT
, (_("Trying pattern rule with stem `%.*s'.\n"),
475 (int) stemlen
, stem
));
477 strncpy (stem_str
, stem
, stemlen
);
478 stem_str
[stemlen
] = '\0';
480 /* Temporary assign STEM to file->stem and set file variables. */
481 file
->stem
= stem_str
;
482 set_file_variables (file
);
484 /* Try each dependency; see if it "exists". */
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 chop it
494 into individual prerequisites. Unfortunately this won't work
495 because of the "check_lastslash" twist. Instead, we will
496 have to go word by word, taking $()'s into account, for each
497 word we will substitute the stem, re-expand, chop it up, and,
498 if check_lastslash != 0, add the directory part to each
499 resulting prerequisite. */
501 p
= get_next_word (dep
->name
, &len
);
509 break; /* No more words */
511 /* Is there a pattern in this prerequisite? */
513 for (p2
= p
; p2
< p
+ len
&& *p2
!= '%'; ++p2
)
516 if (dep
->need_2nd_expansion
)
518 /* If the dependency name has %, substitute the stem.
520 Watch out, we are going to do something tricky
521 here. If we just replace % with the stem value,
522 later, when we do the second expansion, we will
523 re-expand this stem value once again. This is not
524 good especially if you have certain characters in
527 Instead, we will replace % with $* and allow the
528 second expansion to take care of it for us. This way
529 (since $* is a simple variable) there won't be
530 additional re-expansion of the stem. */
534 register unsigned int i
= p2
- p
;
535 bcopy (p
, depname
, i
);
536 bcopy ("$*", depname
+ i
, 2);
537 bcopy (p2
+ 1, depname
+ i
+ 2, len
- i
- 1);
538 depname
[len
+ 2 - 1] = '\0';
547 bcopy (p
, depname
, len
);
551 p2
= variable_expand_for_file (depname
, file
);
557 register unsigned int i
= p2
- p
;
558 bcopy (p
, depname
, i
);
559 bcopy (stem_str
, depname
+ i
, stemlen
);
560 bcopy (p2
+ 1, depname
+ i
+ stemlen
, len
- i
- 1);
561 depname
[len
+ stemlen
- 1] = '\0';
570 bcopy (p
, depname
, len
);
577 /* Parse the dependencies. */
583 for (; *id_ptr
; id_ptr
= &(*id_ptr
)->next
)
586 *id_ptr
= (struct idep
*)
589 order_only
? '\0' : '|',
590 sizeof (struct idep
),
591 1), sizeof (struct idep
));
593 /* @@ It would be nice to teach parse_file_seq or
594 multi_glob to add prefix. This would save us some
597 if (order_only
|| add_dir
|| had_stem
)
599 unsigned long l
= lastslash
- filename
+ 1;
601 for (d
= *id_ptr
; d
!= 0; d
= d
->next
)
610 d
->name
= xmalloc (strlen (p
) + l
+ 1);
612 bcopy (filename
, d
->name
, l
);
613 bcopy (p
, d
->name
+ l
, strlen (p
) + 1);
623 if (!order_only
&& *p2
)
634 p
= get_next_word (p
, &len
);
638 /* Reset the stem in FILE. */
642 /* @@ This loop can be combined with the previous one. I do
643 it separately for now for transparency.*/
645 for (d
= deps
; d
!= 0; d
= d
->next
)
647 char *name
= d
->name
;
649 if (file_impossible_p (name
))
651 /* If this dependency has already been ruled "impossible",
652 then the rule fails and don't bother trying it on the
653 second pass either since we know that will fail too. */
656 ? _("Rejecting impossible implicit prerequisite `%s'.\n")
657 : _("Rejecting impossible rule prerequisite `%s'.\n"),
667 ? _("Trying implicit prerequisite `%s'.\n")
668 : _("Trying rule prerequisite `%s'.\n"), name
));
670 /* If this prerequisite also happened to be explicitly mentioned
671 for FILE skip all the test below since it it has to be built
672 anyway, no matter which implicit rule we choose. */
674 for (expl_d
= file
->deps
; expl_d
!= 0; expl_d
= expl_d
->next
)
675 if (streq (dep_name (expl_d
), name
))
680 /* The DEP->changed flag says that this dependency resides in a
681 nonexistent directory. So we normally can skip looking for
682 the file. However, if CHECK_LASTSLASH is set, then the
683 dependency file we are actually looking for is in a different
684 directory (the one gotten by prepending FILENAME's directory),
685 so it might actually exist. */
687 /* @@ dep->changed check is disabled. */
688 if (((f
= lookup_file (name
)) != 0 && f
->is_target
)
689 /*|| ((!dep->changed || check_lastslash) && */
690 || file_exists_p (name
))
693 /* This code, given FILENAME = "lib/foo.o", dependency name
694 "lib/foo.c", and VPATH=src, searches for "src/lib/foo.c". */
696 if (vpath_search (&vname
, (FILE_TIMESTAMP
*) 0))
699 (_("Found prerequisite `%s' as VPATH `%s'\n"),
708 /* We could not find the file in any place we should look. Try
709 to make this dependency as an intermediate file, but only on
714 if (intermediate_file
== 0)
716 = (struct file
*) alloca (sizeof (struct file
));
719 (_("Looking for a rule with intermediate file `%s'.\n"),
722 bzero ((char *) intermediate_file
, sizeof (struct file
));
723 intermediate_file
->name
= name
;
724 if (pattern_search (intermediate_file
,
729 d
->intermediate_file
= intermediate_file
;
730 d
->intermediate_pattern
= intermediate_file
->name
;
732 intermediate_file
->name
= xstrdup (name
);
733 intermediate_file
= 0;
738 /* If we have tried to find P as an intermediate
739 file and failed, mark that name as impossible
740 so we won't go through the search again later. */
741 if (intermediate_file
->variables
)
742 free_variable_set (intermediate_file
->variables
);
743 file_impossible (name
);
746 /* A dependency of this rule does not exist. Therefore,
752 /* This rule is no longer `in use' for recursive searches. */
757 /* This pattern rule does not apply. If some of its
758 dependencies succeeded, free the data structure
760 free_idep_chain (deps
);
764 /* This pattern rule does apply. Stop looking for one. */
768 /* If we found an applicable rule without
769 intermediate files, don't try with them. */
776 /* RULE is nil if the loop went all the way
777 through the list and everything failed. */
783 /* If we are recursing, store the pattern that matched
784 FILENAME in FILE->name for use in upper levels. */
788 file
->name
= rule
->targets
[matches
[foundrule
]];
790 /* FOUND_FILES lists the dependencies for the rule we found.
791 This includes the intermediate files, if any.
792 Convert them into entries on the deps-chain of FILE. */
794 if (remove_explicit_deps
)
796 /* Remove all the dependencies that didn't come from
797 this implicit rule. */
802 struct dep
*next
= dep
->next
;
810 expl_d
= file
->deps
; /* We will add them at the end. */
813 for (d
= deps
; d
!= 0; d
= d
->next
)
817 if (d
->intermediate_file
!= 0)
819 /* If we need to use an intermediate file,
820 make sure it is entered as a target, with the info that was
821 found for it in the recursive pattern_search call.
822 We know that the intermediate file did not already exist as
823 a target; therefore we can assume that the deps and cmds
824 of F below are null before we change them. */
826 struct file
*imf
= d
->intermediate_file
;
827 register struct file
*f
= lookup_file (imf
->name
);
829 /* We don't want to delete an intermediate file that happened
830 to be a prerequisite of some (other) target. Mark it as
835 f
= enter_file (imf
->name
);
839 f
->stem
= xstrdup (imf
->stem
);
840 f
->also_make
= imf
->also_make
;
845 imf
= lookup_file (d
->intermediate_pattern
);
846 if (imf
!= 0 && imf
->precious
)
851 f
->tried_implicit
= 1;
852 for (dep
= f
->deps
; dep
!= 0; dep
= dep
->next
)
854 dep
->file
= enter_file (dep
->name
);
855 /* enter_file uses dep->name _if_ we created a new file. */
856 if (dep
->name
!= dep
->file
->name
)
859 dep
->file
->tried_implicit
|= dep
->changed
;
863 dep
= (struct dep
*) xmalloc (sizeof (struct dep
));
864 dep
->ignore_mtime
= d
->ignore_mtime
;
865 dep
->staticpattern
= 0;
866 dep
->need_2nd_expansion
= 0;
867 s
= d
->name
; /* Hijacking the name. */
872 dep
->file
= lookup_file (s
);
874 /* enter_file consumes S's storage. */
875 dep
->file
= enter_file (s
);
877 /* A copy of S is already allocated in DEP->file->name.
887 if (d
->intermediate_file
== 0 && tryrules
[foundrule
]->terminal
)
889 /* If the file actually existed (was not an intermediate file),
890 and the rule that found it was a terminal one, then we want
891 to mark the found file so that it will not have implicit rule
892 search done for it. If we are not entering a `struct file' for
893 it now, we indicate this with the `changed' flag. */
897 dep
->file
->tried_implicit
= 1;
906 if (!checked_lastslash
[foundrule
])
908 /* Always allocate new storage, since STEM might be
909 on the stack for an intermediate file. */
910 file
->stem
= savestring (stem
, stemlen
);
911 fullstemlen
= stemlen
;
915 int dirlen
= (lastslash
+ 1) - filename
;
917 /* We want to prepend the directory from
918 the original FILENAME onto the stem. */
919 fullstemlen
= dirlen
+ stemlen
;
920 file
->stem
= (char *) xmalloc (fullstemlen
+ 1);
921 bcopy (filename
, file
->stem
, dirlen
);
922 bcopy (stem
, file
->stem
+ dirlen
, stemlen
);
923 file
->stem
[fullstemlen
] = '\0';
926 file
->cmds
= rule
->cmds
;
929 /* Set precious flag. */
931 struct file
*f
= lookup_file (rule
->targets
[matches
[foundrule
]]);
932 if (f
&& f
->precious
)
936 /* If this rule builds other targets, too, put the others into FILE's
937 `also_make' member. */
939 if (rule
->targets
[1] != 0)
940 for (i
= 0; rule
->targets
[i
] != 0; ++i
)
941 if (i
!= matches
[foundrule
])
944 struct dep
*new = (struct dep
*) xmalloc (sizeof (struct dep
));
945 /* GKM FIMXE: handle '|' here too */
946 new->ignore_mtime
= 0;
947 new->staticpattern
= 0;
948 new->need_2nd_expansion
= 0;
949 new->name
= p
= (char *) xmalloc (rule
->lens
[i
] + fullstemlen
+ 1);
950 bcopy (rule
->targets
[i
], p
,
951 rule
->suffixes
[i
] - rule
->targets
[i
] - 1);
952 p
+= rule
->suffixes
[i
] - rule
->targets
[i
] - 1;
953 bcopy (file
->stem
, p
, fullstemlen
);
955 bcopy (rule
->suffixes
[i
], p
,
956 rule
->lens
[i
] - (rule
->suffixes
[i
] - rule
->targets
[i
]) + 1);
957 new->file
= enter_file (new->name
);
958 new->next
= file
->also_make
;
960 /* Set precious flag. */
961 f
= lookup_file (rule
->targets
[i
]);
962 if (f
&& f
->precious
)
963 new->file
->precious
= 1;
965 /* Set the is_target flag so that this file is not treated
966 as intermediate by the pattern rule search algorithm and
967 file_exists_p cannot pick it up yet. */
968 new->file
->is_target
= 1;
970 file
->also_make
= new;
974 free_idep_chain (deps
);