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
)
90 struct file
*f
= p
->intermediate_file
;
93 && (f
->stem
< f
->name
|| f
->stem
> f
->name
+ strlen (f
->name
)))
104 /* Scans the BUFFER for the next word with whitespace as a separator.
105 Returns the pointer to the beginning of the word. LENGTH hold the
106 length of the word. */
109 get_next_word (char *buffer
, unsigned int *length
)
111 char *p
= buffer
, *beg
;
114 /* Skip any leading whitespace. */
115 while (isblank ((unsigned char)*p
))
125 /* We already found the first value of "c", above. */
143 /* This is a variable reference, so read it to the matching
151 /* This is a single-letter variable reference. */
154 for (count
= 0; *p
!= '\0'; ++p
)
158 else if (*p
== closeparen
&& --count
< 0)
185 /* Search the pattern rules for a rule with an existing dependency to make
186 FILE. If a rule is found, the appropriate commands and deps are put in FILE
187 and 1 is returned. If not, 0 is returned.
189 If ARCHIVE is nonzero, FILE->name is of the form "LIB(MEMBER)". A rule for
190 "(MEMBER)" will be searched for, and "(MEMBER)" will not be chopped up into
191 directory and filename parts.
193 If an intermediate file is found by pattern search, the intermediate file
194 is set up as a target by the recursive call and is also made a dependency
197 DEPTH is used for debugging messages. */
200 pattern_search (struct file
*file
, int archive
,
201 unsigned int depth
, unsigned int recursions
)
203 /* Filename we are searching for a rule for. */
204 char *filename
= archive
? strchr (file
->name
, '(') : file
->name
;
206 /* Length of FILENAME. */
207 unsigned int namelen
= strlen (filename
);
209 /* The last slash in FILENAME (or nil if there is none). */
212 /* This is a file-object used as an argument in
213 recursive calls. It never contains any data
214 except during a recursive call. */
215 struct file
*intermediate_file
= 0;
217 /* This linked list records all the prerequisites actually
218 found for a rule along with some other useful information
219 (see struct idep for details). */
220 struct idep
* deps
= 0;
222 /* 1 if we need to remove explicit prerequisites, 0 otherwise. */
223 unsigned int remove_explicit_deps
= 0;
225 /* Names of possible dependencies are constructed in this buffer. */
226 register char *depname
= (char *) alloca (namelen
+ max_pattern_dep_length
);
228 /* The start and length of the stem of FILENAME for the current rule. */
229 register char *stem
= 0;
230 register unsigned int stemlen
= 0;
231 register unsigned int fullstemlen
= 0;
233 /* Buffer in which we store all the rules that are possibly applicable. */
234 struct rule
**tryrules
235 = (struct rule
**) xmalloc (num_pattern_rules
* max_pattern_targets
236 * sizeof (struct rule
*));
238 /* Number of valid elements in TRYRULES. */
241 /* The numbers of the rule targets of each rule
242 in TRYRULES that matched the target file. */
243 unsigned int *matches
244 = (unsigned int *) alloca (num_pattern_rules
* sizeof (unsigned int));
246 /* Each element is nonzero if LASTSLASH was used in
247 matching the corresponding element of TRYRULES. */
248 char *checked_lastslash
249 = (char *) alloca (num_pattern_rules
* sizeof (char));
251 /* The index in TRYRULES of the rule we found. */
252 unsigned int foundrule
;
254 /* Nonzero if should consider intermediate files as dependencies. */
257 /* Nonzero if we have matched a pattern-rule target
258 that is not just `%'. */
259 int specific_rule_matched
= 0;
261 unsigned int i
= 0; /* uninit checks OK */
263 struct dep
*dep
, *expl_d
;
268 struct idep
**id_ptr
;
271 PATH_VAR (stem_str
); /* @@ Need to get rid of stem, stemlen, etc. */
274 if (archive
|| ar_name (filename
))
279 /* Set LASTSLASH to point at the last slash in FILENAME
280 but not counting any slash at the end. (foo/bar/ counts as
281 bar/ in directory foo/, not empty in directory foo/bar/.) */
283 lastslash
= strrchr (filename
, ']');
285 lastslash
= strrchr (filename
, ':');
287 lastslash
= strrchr (filename
, '/');
288 #ifdef HAVE_DOS_PATHS
289 /* Handle backslashes (possibly mixed with forward slashes)
290 and the case of "d:file". */
292 char *bslash
= strrchr (filename
, '\\');
293 if (lastslash
== 0 || bslash
> lastslash
)
295 if (lastslash
== 0 && filename
[0] && filename
[1] == ':')
296 lastslash
= filename
+ 1;
300 if (lastslash
!= 0 && lastslash
[1] == '\0')
304 /* First see which pattern rules match this target
305 and may be considered. Put them in TRYRULES. */
308 for (rule
= pattern_rules
; rule
!= 0; rule
= rule
->next
)
310 /* If the pattern rule has deps but no commands, ignore it.
311 Users cancel built-in rules by redefining them without commands. */
312 if (rule
->deps
!= 0 && rule
->cmds
== 0)
315 /* If this rule is in use by a parent pattern_search,
316 don't use it here. */
319 DBS (DB_IMPLICIT
, (_("Avoiding implicit rule recursion.\n")));
323 for (i
= 0; rule
->targets
[i
] != 0; ++i
)
325 char *target
= rule
->targets
[i
];
326 char *suffix
= rule
->suffixes
[i
];
329 /* Rules that can match any filename and are not terminal
330 are ignored if we're recursing, so that they cannot be
331 intermediate files. */
332 if (recursions
> 0 && target
[1] == '\0' && !rule
->terminal
)
335 if (rule
->lens
[i
] > namelen
)
336 /* It can't possibly match. */
339 /* From the lengths of the filename and the pattern parts,
340 find the stem: the part of the filename that matches the %. */
341 stem
= filename
+ (suffix
- target
- 1);
342 stemlen
= namelen
- rule
->lens
[i
] + 1;
344 /* Set CHECK_LASTSLASH if FILENAME contains a directory
345 prefix and the target pattern does not contain a slash. */
351 check_lastslash
= (strchr (target
, ']') == 0
352 && strchr (target
, ':') == 0);
354 check_lastslash
= strchr (target
, '/') == 0;
355 #ifdef HAVE_DOS_PATHS
356 /* Didn't find it yet: check for DOS-type directories. */
359 char *b
= strchr (target
, '\\');
360 check_lastslash
= !(b
|| (target
[0] && target
[1] == ':'));
367 /* If so, don't include the directory prefix in STEM here. */
368 unsigned int difference
= lastslash
- filename
+ 1;
369 if (difference
> stemlen
)
371 stemlen
-= difference
;
375 /* Check that the rule pattern matches the text before the stem. */
378 if (stem
> (lastslash
+ 1)
379 && !strneq (target
, lastslash
+ 1, stem
- lastslash
- 1))
382 else if (stem
> filename
383 && !strneq (target
, filename
, stem
- filename
))
386 /* Check that the rule pattern matches the text after the stem.
387 We could test simply use streq, but this way we compare the
388 first two characters immediately. This saves time in the very
389 common case where the first character matches because it is a
391 if (*suffix
!= stem
[stemlen
]
392 || (*suffix
!= '\0' && !streq (&suffix
[1], &stem
[stemlen
+ 1])))
395 /* Record if we match a rule that not all filenames will match. */
396 if (target
[1] != '\0')
397 specific_rule_matched
= 1;
399 /* A rule with no dependencies and no commands exists solely to set
400 specific_rule_matched when it matches. Don't try to use it. */
401 if (rule
->deps
== 0 && rule
->cmds
== 0)
404 /* Record this rule in TRYRULES and the index of the matching
405 target in MATCHES. If several targets of the same rule match,
406 that rule will be in TRYRULES more than once. */
407 tryrules
[nrules
] = rule
;
409 checked_lastslash
[nrules
] = check_lastslash
;
414 /* If we have found a matching rule that won't match all filenames,
415 retroactively reject any non-"terminal" rules that do always match. */
416 if (specific_rule_matched
)
417 for (i
= 0; i
< nrules
; ++i
)
418 if (!tryrules
[i
]->terminal
)
420 register unsigned int j
;
421 for (j
= 0; tryrules
[i
]->targets
[j
] != 0; ++j
)
422 if (tryrules
[i
]->targets
[j
][1] == '\0')
424 if (tryrules
[i
]->targets
[j
] != 0)
428 /* We are going to do second expansion so initialize file variables
430 initialize_file_variables (file
, 0);
432 /* Try each rule once without intermediate files, then once with them. */
433 for (intermed_ok
= 0; intermed_ok
== !!intermed_ok
; ++intermed_ok
)
435 /* Try each pattern rule till we find one that applies.
436 If it does, expand its dependencies (as substituted)
437 and chain them in DEPS. */
439 for (i
= 0; i
< nrules
; i
++)
442 unsigned int failed
= 0;
444 int file_variables_set
= 0;
448 remove_explicit_deps
= 0;
450 /* RULE is nil when we discover that a rule,
451 already placed in TRYRULES, should not be applied. */
455 /* Reject any terminal rules if we're
456 looking to make intermediate files. */
457 if (intermed_ok
&& rule
->terminal
)
460 /* Mark this rule as in use so a recursive
461 pattern_search won't try to use it. */
464 /* From the lengths of the filename and the matching pattern parts,
465 find the stem: the part of the filename that matches the %. */
467 + (rule
->suffixes
[matches
[i
]] - rule
->targets
[matches
[i
]]) - 1;
468 stemlen
= namelen
- rule
->lens
[matches
[i
]] + 1;
469 check_lastslash
= checked_lastslash
[i
];
472 stem
+= lastslash
- filename
+ 1;
473 stemlen
-= (lastslash
- filename
) + 1;
476 DBS (DB_IMPLICIT
, (_("Trying pattern rule with stem `%.*s'.\n"),
477 (int) stemlen
, stem
));
479 strncpy (stem_str
, stem
, stemlen
);
480 stem_str
[stemlen
] = '\0';
482 /* Temporary assign STEM to file->stem (needed to set file
484 file
->stem
= stem_str
;
486 /* Try each dependency; see if it "exists". */
488 for (dep
= rule
->deps
; dep
!= 0; dep
= dep
->next
)
492 unsigned int order_only
= 0; /* Set if '|' was seen. */
494 /* In an ideal world we would take the dependency line,
495 substitute the stem, re-expand the whole line and chop it
496 into individual prerequisites. Unfortunately this won't work
497 because of the "check_lastslash" twist. Instead, we will
498 have to go word by word, taking $()'s into account, for each
499 word we will substitute the stem, re-expand, chop it up, and,
500 if check_lastslash != 0, add the directory part to each
501 resulting prerequisite. */
503 p
= get_next_word (dep
->name
, &len
);
511 break; /* No more words */
513 /* Is there a pattern in this prerequisite? */
515 for (p2
= p
; p2
< p
+ len
&& *p2
!= '%'; ++p2
)
518 if (dep
->need_2nd_expansion
)
520 /* If the dependency name has %, substitute the stem.
522 Watch out, we are going to do something tricky
523 here. If we just replace % with the stem value,
524 later, when we do the second expansion, we will
525 re-expand this stem value once again. This is not
526 good especially if you have certain characters in
529 Instead, we will replace % with $* and allow the
530 second expansion to take care of it for us. This way
531 (since $* is a simple variable) there won't be
532 additional re-expansion of the stem. */
536 register unsigned int i
= p2
- p
;
537 bcopy (p
, depname
, i
);
538 bcopy ("$*", depname
+ i
, 2);
539 bcopy (p2
+ 1, depname
+ i
+ 2, len
- i
- 1);
540 depname
[len
+ 2 - 1] = '\0';
549 bcopy (p
, depname
, len
);
553 /* Set file variables. Note that we cannot do it once
554 at the beginning of the function because of the stem
556 if (!file_variables_set
)
558 set_file_variables (file
);
559 file_variables_set
= 1;
562 p2
= variable_expand_for_file (depname
, file
);
568 register unsigned int i
= p2
- p
;
569 bcopy (p
, depname
, i
);
570 bcopy (stem_str
, depname
+ i
, stemlen
);
571 bcopy (p2
+ 1, depname
+ i
+ stemlen
, len
- i
- 1);
572 depname
[len
+ stemlen
- 1] = '\0';
581 bcopy (p
, depname
, len
);
588 /* Parse the dependencies. */
594 for (; *id_ptr
; id_ptr
= &(*id_ptr
)->next
)
597 *id_ptr
= (struct idep
*)
600 order_only
? '\0' : '|',
601 sizeof (struct idep
),
602 1), sizeof (struct idep
));
604 /* @@ It would be nice to teach parse_file_seq or
605 multi_glob to add prefix. This would save us some
608 if (order_only
|| add_dir
|| had_stem
)
610 unsigned long l
= lastslash
- filename
+ 1;
612 for (d
= *id_ptr
; d
!= 0; d
= d
->next
)
621 d
->name
= xmalloc (strlen (p
) + l
+ 1);
623 bcopy (filename
, d
->name
, l
);
624 bcopy (p
, d
->name
+ l
, strlen (p
) + 1);
634 if (!order_only
&& *p2
)
645 p
= get_next_word (p
, &len
);
649 /* Reset the stem in FILE. */
653 /* @@ This loop can be combined with the previous one. I do
654 it separately for now for transparency.*/
656 for (d
= deps
; d
!= 0; d
= d
->next
)
658 char *name
= d
->name
;
660 if (file_impossible_p (name
))
662 /* If this dependency has already been ruled "impossible",
663 then the rule fails and don't bother trying it on the
664 second pass either since we know that will fail too. */
667 ? _("Rejecting impossible implicit prerequisite `%s'.\n")
668 : _("Rejecting impossible rule prerequisite `%s'.\n"),
678 ? _("Trying implicit prerequisite `%s'.\n")
679 : _("Trying rule prerequisite `%s'.\n"), name
));
681 /* If this prerequisite also happened to be explicitly mentioned
682 for FILE skip all the test below since it it has to be built
683 anyway, no matter which implicit rule we choose. */
685 for (expl_d
= file
->deps
; expl_d
!= 0; expl_d
= expl_d
->next
)
686 if (streq (dep_name (expl_d
), name
))
691 /* The DEP->changed flag says that this dependency resides in a
692 nonexistent directory. So we normally can skip looking for
693 the file. However, if CHECK_LASTSLASH is set, then the
694 dependency file we are actually looking for is in a different
695 directory (the one gotten by prepending FILENAME's directory),
696 so it might actually exist. */
698 /* @@ dep->changed check is disabled. */
699 if (((f
= lookup_file (name
)) != 0 && f
->is_target
)
700 /*|| ((!dep->changed || check_lastslash) && */
701 || file_exists_p (name
))
704 /* This code, given FILENAME = "lib/foo.o", dependency name
705 "lib/foo.c", and VPATH=src, searches for "src/lib/foo.c". */
707 if (vpath_search (&vname
, (FILE_TIMESTAMP
*) 0))
710 (_("Found prerequisite `%s' as VPATH `%s'\n"),
719 /* We could not find the file in any place we should look. Try
720 to make this dependency as an intermediate file, but only on
725 if (intermediate_file
== 0)
727 = (struct file
*) alloca (sizeof (struct file
));
730 (_("Looking for a rule with intermediate file `%s'.\n"),
733 bzero ((char *) intermediate_file
, sizeof (struct file
));
734 intermediate_file
->name
= name
;
735 if (pattern_search (intermediate_file
,
740 d
->intermediate_file
= intermediate_file
;
741 d
->intermediate_pattern
= intermediate_file
->name
;
743 intermediate_file
->name
= xstrdup (name
);
744 intermediate_file
= 0;
749 /* If we have tried to find P as an intermediate
750 file and failed, mark that name as impossible
751 so we won't go through the search again later. */
752 if (intermediate_file
->variables
)
753 free_variable_set (intermediate_file
->variables
);
754 file_impossible (name
);
757 /* A dependency of this rule does not exist. Therefore,
763 /* This rule is no longer `in use' for recursive searches. */
768 /* This pattern rule does not apply. If some of its
769 dependencies succeeded, free the data structure
771 free_idep_chain (deps
);
775 /* This pattern rule does apply. Stop looking for one. */
779 /* If we found an applicable rule without
780 intermediate files, don't try with them. */
787 /* RULE is nil if the loop went all the way
788 through the list and everything failed. */
794 /* If we are recursing, store the pattern that matched
795 FILENAME in FILE->name for use in upper levels. */
799 file
->name
= rule
->targets
[matches
[foundrule
]];
801 /* FOUND_FILES lists the dependencies for the rule we found.
802 This includes the intermediate files, if any.
803 Convert them into entries on the deps-chain of FILE. */
805 if (remove_explicit_deps
)
807 /* Remove all the dependencies that didn't come from
808 this implicit rule. */
813 struct dep
*next
= dep
->next
;
820 expl_d
= file
->deps
; /* We will add them at the end. */
823 for (d
= deps
; d
!= 0; d
= d
->next
)
827 if (d
->intermediate_file
!= 0)
829 /* If we need to use an intermediate file,
830 make sure it is entered as a target, with the info that was
831 found for it in the recursive pattern_search call.
832 We know that the intermediate file did not already exist as
833 a target; therefore we can assume that the deps and cmds
834 of F below are null before we change them. */
836 struct file
*imf
= d
->intermediate_file
;
837 register struct file
*f
= lookup_file (imf
->name
);
839 /* We don't want to delete an intermediate file that happened
840 to be a prerequisite of some (other) target. Mark it as
845 f
= enter_file (imf
->name
);
850 f
->also_make
= imf
->also_make
;
855 imf
= lookup_file (d
->intermediate_pattern
);
856 if (imf
!= 0 && imf
->precious
)
861 f
->tried_implicit
= 1;
862 for (dep
= f
->deps
; dep
!= 0; dep
= dep
->next
)
864 dep
->file
= enter_file (dep
->name
);
865 /* enter_file uses dep->name _if_ we created a new file. */
866 if (dep
->name
!= dep
->file
->name
)
869 dep
->file
->tried_implicit
|= dep
->changed
;
874 dep
->ignore_mtime
= d
->ignore_mtime
;
875 s
= d
->name
; /* Hijacking the name. */
879 dep
->file
= lookup_file (s
);
881 /* enter_file consumes S's storage. */
882 dep
->file
= enter_file (s
);
884 /* A copy of S is already allocated in DEP->file->name.
893 if (d
->intermediate_file
== 0 && tryrules
[foundrule
]->terminal
)
895 /* If the file actually existed (was not an intermediate file),
896 and the rule that found it was a terminal one, then we want
897 to mark the found file so that it will not have implicit rule
898 search done for it. If we are not entering a `struct file' for
899 it now, we indicate this with the `changed' flag. */
903 dep
->file
->tried_implicit
= 1;
912 if (!checked_lastslash
[foundrule
])
914 /* Always allocate new storage, since STEM might be
915 on the stack for an intermediate file. */
916 file
->stem
= savestring (stem
, stemlen
);
917 fullstemlen
= stemlen
;
921 int dirlen
= (lastslash
+ 1) - filename
;
923 /* We want to prepend the directory from
924 the original FILENAME onto the stem. */
925 fullstemlen
= dirlen
+ stemlen
;
926 file
->stem
= (char *) xmalloc (fullstemlen
+ 1);
927 bcopy (filename
, file
->stem
, dirlen
);
928 bcopy (stem
, file
->stem
+ dirlen
, stemlen
);
929 file
->stem
[fullstemlen
] = '\0';
932 file
->cmds
= rule
->cmds
;
935 /* Set precious flag. */
937 struct file
*f
= lookup_file (rule
->targets
[matches
[foundrule
]]);
938 if (f
&& f
->precious
)
942 /* If this rule builds other targets, too, put the others into FILE's
943 `also_make' member. */
945 if (rule
->targets
[1] != 0)
946 for (i
= 0; rule
->targets
[i
] != 0; ++i
)
947 if (i
!= matches
[foundrule
])
950 struct dep
*new = alloc_dep ();
952 /* GKM FIMXE: handle '|' here too */
953 new->name
= p
= (char *) xmalloc (rule
->lens
[i
] + fullstemlen
+ 1);
954 bcopy (rule
->targets
[i
], p
,
955 rule
->suffixes
[i
] - rule
->targets
[i
] - 1);
956 p
+= rule
->suffixes
[i
] - rule
->targets
[i
] - 1;
957 bcopy (file
->stem
, p
, fullstemlen
);
959 bcopy (rule
->suffixes
[i
], p
,
960 rule
->lens
[i
] - (rule
->suffixes
[i
] - rule
->targets
[i
]) + 1);
961 new->file
= enter_file (new->name
);
962 new->next
= file
->also_make
;
964 /* Set precious flag. */
965 f
= lookup_file (rule
->targets
[i
]);
966 if (f
&& f
->precious
)
967 new->file
->precious
= 1;
969 /* Set the is_target flag so that this file is not treated
970 as intermediate by the pattern rule search algorithm and
971 file_exists_p cannot pick it up yet. */
972 new->file
->is_target
= 1;
974 file
->also_make
= new;
978 free_idep_chain (deps
);