1 /* Implicit rule searching for GNU Make.
2 Copyright (C) 1988-2022 Free Software Foundation, Inc.
3 This file is part of GNU Make.
4
5 GNU Make is free software; you can redistribute it and/or modify it under the
6 terms of the GNU General Public License as published by the Free Software
7 Foundation; either version 3 of the License, or (at your option) any later
8 version.
9
10 GNU Make is distributed in the hope that it will be useful, but WITHOUT ANY
11 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
12 A PARTICULAR PURPOSE. See the GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License along with
15 this program. If not, see <https://www.gnu.org/licenses/>. */
16
17 #include "makeint.h"
18 #include "filedef.h"
19 #include "rule.h"
20 #include "dep.h"
21 #include "debug.h"
22 #include "variable.h"
23 #include "job.h" /* struct child, used inside commands.h */
24 #include "commands.h" /* set_file_variables */
25 #include "shuffle.h"
26 #include <assert.h>
27
28 static int pattern_search (struct file *file, int archive,
29 unsigned int depth, unsigned int recursions,
30 int allow_compat_rules);
31
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. */
37
38 int
39 try_implicit_rule (struct file *file, unsigned int depth)
40 {
41 DBF (DB_IMPLICIT, _("Looking for an implicit rule for '%s'.\n"));
42
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
46 should come first. */
47
48 if (pattern_search (file, 0, depth, 0, 0))
49 return 1;
50
51 #ifndef NO_ARCHIVES
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))
55 {
56 DBF (DB_IMPLICIT,
57 _("Looking for archive-member implicit rule for '%s'.\n"));
58 if (pattern_search (file, 1, depth, 0, 0))
59 return 1;
60 DBS (DB_IMPLICIT,
61 (_("No archive-member implicit rule found for '%s'.\n"),
62 file->name));
63 }
64 #endif
65
66 return 0;
67 }
68
69
70 /* Scans the BUFFER for the next word with whitespace as a separator.
71 Returns the pointer to the beginning of the word. LENGTH hold the
72 length of the word. */
73
74 static const char *
75 get_next_word (const char *buffer, size_t *length)
76 {
77 const char *p = buffer, *beg;
78 char c;
79
80 /* Skip any leading whitespace. */
81 NEXT_TOKEN (p);
82
83 beg = p;
84 c = *(p++);
85
86 if (c == '\0')
87 return 0;
88
89
90 /* We already found the first value of "c", above. */
91 while (1)
92 {
93 char closeparen;
94 int count;
95
96 switch (c)
97 {
98 case '\0':
99 case ' ':
100 case '\t':
101 goto done_word;
102
103 case '$':
104 c = *(p++);
105 if (c == '$')
106 break;
107
108 /* This is a variable reference, so read it to the matching
109 close paren. */
110
111 if (c == '(')
112 closeparen = ')';
113 else if (c == '{')
114 closeparen = '}';
115 else
116 /* This is a single-letter variable reference. */
117 break;
118
119 for (count = 0; *p != '\0'; ++p)
120 {
121 if (*p == c)
122 ++count;
123 else if (*p == closeparen && --count < 0)
124 {
125 ++p;
126 break;
127 }
128 }
129 break;
130
131 case '|':
132 goto done;
133
134 default:
135 break;
136 }
137
138 c = *(p++);
139 }
140 done_word:
141 --p;
142
143 done:
144 if (length)
145 *length = p - beg;
146
147 return beg;
148 }
149
150 /* This structure stores information about the expanded prerequisites for a
151 pattern rule. NAME is always set to the strcache'd name of the prereq.
152 FILE and PATTERN will be set for intermediate files only. IGNORE_MTIME is
153 copied from the prerequisite we expanded.
154 */
155 struct patdeps
156 {
157 const char *name;
158 const char *pattern;
159 struct file *file;
160 unsigned int ignore_mtime : 1;
161 unsigned int ignore_automatic_vars : 1;
162 unsigned int is_explicit : 1;
163 unsigned int wait_here : 1;
164 };
165
166 /* This structure stores information about pattern rules that we need
167 to try.
168 */
169 struct tryrule
170 {
171 struct rule *rule;
172
173 /* Stem length for this match. */
174 size_t stemlen;
175
176 /* Index of the target in this rule that matched the file. */
177 unsigned int matches;
178
179 /* Definition order of this rule. Used to implement stable sort.*/
180 unsigned int order;
181
182 /* Nonzero if the LASTSLASH logic was used in matching this rule. */
183 char checked_lastslash;
184 };
185
186 int
187 stemlen_compare (const void *v1, const void *v2)
188 {
189 const struct tryrule *r1 = v1;
190 const struct tryrule *r2 = v2;
191 int r = (int) (r1->stemlen - r2->stemlen);
192 return r != 0 ? r : (int) (r1->order - r2->order);
193 }
194
195 /* Search the pattern rules for a rule with an existing dependency to make
196 FILE. If a rule is found, the appropriate commands and deps are put in FILE
197 and 1 is returned. If not, 0 is returned.
198
199 If ARCHIVE is nonzero, FILE->name is of the form "LIB(MEMBER)". A rule for
200 "(MEMBER)" will be searched for, and "(MEMBER)" will not be chopped up into
201 directory and filename parts.
202
203 If an intermediate file is found by pattern search, the intermediate file
204 is set up as a target by the recursive call and is also made a dependency
205 of FILE.
206
207 DEPTH is used for debugging messages. */
208
209 static int
210 pattern_search (struct file *file, int archive,
211 unsigned int depth, unsigned int recursions,
212 int allow_compat_rules)
213 {
214 /* Filename we are searching for a rule for. */
215 const char *filename = archive ? strchr (file->name, '(') : file->name;
216
217 /* Length of FILENAME. */
218 size_t namelen = strlen (filename);
219
220 /* The last slash in FILENAME (or nil if there is none). */
221 const char *lastslash;
222
223 /* This is a file-object used as an argument in
224 recursive calls. It never contains any data
225 except during a recursive call. */
226 struct file *int_file = 0;
227
228 /* List of dependencies found recursively. */
229 unsigned int max_deps = max_pattern_deps;
230 struct patdeps *deplist = xmalloc (max_deps * sizeof (struct patdeps));
231 struct patdeps *pat = deplist;
232
233 /* Names of possible dependencies are constructed in this buffer.
234 We may replace % by $(*F) for second expansion, increasing the length. */
235 size_t deplen = namelen + max_pattern_dep_length + 4;
236 char *depname = alloca (deplen);
237 #ifndef NDEBUG
238 char *dend = depname + deplen;
239 #endif
240
241 /* The start and length of the stem of FILENAME for the current rule. */
242 const char *stem = 0;
243 size_t stemlen = 0;
244 size_t fullstemlen = 0;
245
246 /* Buffer in which we store all the rules that are possibly applicable. */
247 struct tryrule *tryrules = xmalloc (num_pattern_rules * max_pattern_targets
248 * sizeof (struct tryrule));
249
250 /* Number of valid elements in TRYRULES. */
251 unsigned int nrules;
252
253 /* The index in TRYRULES of the rule we found. */
254 unsigned int foundrule;
255
256 /* Nonzero if should consider intermediate files as dependencies. */
257 int intermed_ok;
258
259 /* Nonzero if we have initialized file variables for this target. */
260 int file_vars_initialized = 0;
261
262 /* Nonzero if we have matched a pattern-rule target
263 that is not just '%'. */
264 int specific_rule_matched = 0;
265
266 unsigned int ri; /* uninit checks OK */
267 int found_compat_rule = 0;
268 struct rule *rule;
269
270 char *pathdir = NULL;
271 size_t pathlen;
272
273 PATH_VAR (stem_str); /* @@ Need to get rid of stem, stemlen, etc. */
274
275 #ifndef NO_ARCHIVES
276 if (archive || ar_name (filename))
277 lastslash = 0;
278 else
279 #endif
280 {
281 /* Set LASTSLASH to point at the last slash in FILENAME
282 but not counting any slash at the end. (foo/bar/ counts as
283 bar/ in directory foo/, not empty in directory foo/bar/.) */
284 lastslash = memrchr (filename, '/', namelen - 1);
285 #ifdef VMS
286 if (lastslash == NULL)
287 lastslash = strrchr (filename, ']');
288 if (lastslash == NULL)
289 lastslash = strrchr (filename, '>');
290 if (lastslash == NULL)
291 lastslash = strrchr (filename, ':');
292 #endif
293 #ifdef HAVE_DOS_PATHS
294 /* Handle backslashes (possibly mixed with forward slashes)
295 and the case of "d:file". */
296 {
297 char *bslash = memrchr (filename, '\\', namelen - 1);
298 if (lastslash == 0 || bslash > lastslash)
299 lastslash = bslash;
300 if (lastslash == 0 && filename[0] && filename[1] == ':')
301 lastslash = filename + 1;
302 }
303 #endif
304 }
305
306 pathlen = lastslash ? lastslash - filename + 1 : 0;
307
308 /* First see which pattern rules match this target and may be considered.
309 Put them in TRYRULES. */
310
311 nrules = 0;
312 for (rule = pattern_rules; rule != 0; rule = rule->next)
313 {
314 unsigned int ti;
315
316 /* If the pattern rule has deps but no commands, ignore it.
317 Users cancel built-in rules by redefining them without commands. */
318 if (rule->deps != 0 && rule->cmds == 0)
319 continue;
320
321 /* If this rule is in use by a parent pattern_search,
322 don't use it here. */
323 if (rule->in_use)
324 {
325 DBS (DB_IMPLICIT,
326 (_("Avoiding implicit rule recursion for rule '%s'.\n"),
327 get_rule_defn (rule)));
328 continue;
329 }
330
331 for (ti = 0; ti < rule->num; ++ti)
332 {
333 const char *target = rule->targets[ti];
334 const char *suffix = rule->suffixes[ti];
335 char check_lastslash;
336
337 /* Rules that can match any filename and are not terminal
338 are ignored if we're recursing, so that they cannot be
339 intermediate files. */
340 if (recursions > 0 && target[1] == '\0' && !rule->terminal)
341 continue;
342
343 if (rule->lens[ti] > namelen)
344 /* It can't possibly match. */
345 continue;
346
347 /* From the lengths of the filename and the pattern parts,
348 find the stem: the part of the filename that matches the %. */
349 stem = filename + (suffix - target - 1);
350 stemlen = namelen - rule->lens[ti] + 1;
351
352 /* Set CHECK_LASTSLASH if FILENAME contains a directory
353 prefix and the target pattern does not contain a slash. */
354
355 check_lastslash = 0;
356 if (lastslash)
357 {
358 #ifdef VMS
359 check_lastslash = strpbrk (target, "/]>:") == NULL;
360 #else
361 check_lastslash = strchr (target, '/') == 0;
362 #endif
363 #ifdef HAVE_DOS_PATHS
364 /* Didn't find it yet: check for DOS-type directories. */
365 if (check_lastslash)
366 {
367 char *b = strchr (target, '\\');
368 check_lastslash = !(b || (target[0] && target[1] == ':'));
369 }
370 #endif
371 }
372 if (check_lastslash)
373 {
374 /* If so, don't include the directory prefix in STEM here. */
375 if (pathlen > stemlen)
376 continue;
377 stemlen -= pathlen;
378 stem += pathlen;
379 }
380
381 /* Check that the rule pattern matches the text before the stem. */
382 if (check_lastslash)
383 {
384 if (stem > (lastslash + 1)
385 && !strneq (target, lastslash + 1, stem - lastslash - 1))
386 continue;
387 }
388 else if (stem > filename
389 && !strneq (target, filename, stem - filename))
390 continue;
391
392 /* Check that the rule pattern matches the text after the stem.
393 We could test simply use streq, but this way we compare the
394 first two characters immediately. This saves time in the very
395 common case where the first character matches because it is a
396 period. */
397 if (*suffix != stem[stemlen]
398 || (*suffix != '\0' && !streq (&suffix[1], &stem[stemlen + 1])))
399 continue;
400
401 /* Record if we match a rule that not all filenames will match. */
402 if (target[1] != '\0')
403 specific_rule_matched = 1;
404
405 /* A rule with no dependencies and no commands exists solely to set
406 specific_rule_matched when it matches. Don't try to use it. */
407 if (rule->deps == 0 && rule->cmds == 0)
408 continue;
409
410 /* Record this rule in TRYRULES and the index of the matching
411 target in MATCHES. If several targets of the same rule match,
412 that rule will be in TRYRULES more than once. */
413 tryrules[nrules].rule = rule;
414 tryrules[nrules].matches = ti;
415 tryrules[nrules].stemlen = stemlen + (check_lastslash ? pathlen : 0);
416 tryrules[nrules].order = nrules;
417 tryrules[nrules].checked_lastslash = check_lastslash;
418 ++nrules;
419 }
420 }
421
422 /* Bail out early if we haven't found any rules. */
423 if (nrules == 0)
424 goto done;
425
426 /* Sort the rules to place matches with the shortest stem first. This
427 way the most specific rules will be tried first. */
428 if (nrules > 1)
429 qsort (tryrules, nrules, sizeof (struct tryrule), stemlen_compare);
430
431 /* If we have found a matching rule that won't match all filenames,
432 retroactively reject any non-"terminal" rules that do always match. */
433 if (specific_rule_matched)
434 for (ri = 0; ri < nrules; ++ri)
435 if (!tryrules[ri].rule->terminal)
436 {
437 unsigned int j;
438 for (j = 0; j < tryrules[ri].rule->num; ++j)
439 if (tryrules[ri].rule->targets[j][1] == '\0')
440 {
441 tryrules[ri].rule = 0;
442 break;
443 }
444 }
445
446 /* Try each rule once without intermediate files, then once with them. */
447 for (intermed_ok = 0; intermed_ok < 2; ++intermed_ok)
448 {
449 pat = deplist;
450 if (intermed_ok)
451 DBS (DB_IMPLICIT, (_("Trying harder.\n")));
452
453 /* Try each pattern rule till we find one that applies. If it does,
454 expand its dependencies (as substituted) and chain them in DEPS. */
455 for (ri = 0; ri < nrules; ri++)
456 {
457 struct dep *dep;
458 char check_lastslash;
459 unsigned int failed = 0;
460 int file_variables_set = 0;
461 unsigned int deps_found = 0;
462 /* NPTR points to the part of the prereq we haven't processed. */
463 const char *nptr = 0;
464 int order_only = 0;
465 unsigned int matches;
466
467 rule = tryrules[ri].rule;
468
469 /* RULE is nil when we discover that a rule, already placed in
470 TRYRULES, should not be applied. */
471 if (rule == 0)
472 continue;
473
474 /* Reject any terminal rules if we're looking to make intermediate
475 files. */
476 if (intermed_ok && rule->terminal)
477 continue;
478
479 /* From the lengths of the filename and the matching pattern parts,
480 find the stem: the part of the filename that matches the %. */
481 matches = tryrules[ri].matches;
482 stem = filename + (rule->suffixes[matches]
483 - rule->targets[matches]) - 1;
484 stemlen = (namelen - rule->lens[matches]) + 1;
485 check_lastslash = tryrules[ri].checked_lastslash;
486 if (check_lastslash)
487 {
488 stem += pathlen;
489 stemlen -= pathlen;
490
491 /* We need to add the directory prefix, so set it up. */
492 if (! pathdir)
493 {
494 pathdir = alloca (pathlen + 1);
495 memcpy (pathdir, filename, pathlen);
496 pathdir[pathlen] = '\0';
497 }
498 }
499
500 DBS (DB_IMPLICIT,
501 (_("Trying pattern rule '%s' with stem '%.*s'.\n"),
502 get_rule_defn (rule), (int) stemlen, stem));
503
504 if (stemlen + (check_lastslash ? pathlen : 0) > GET_PATH_MAX)
505 {
506 DBS (DB_IMPLICIT, (_("Stem too long: '%s%.*s'.\n"),
507 check_lastslash ? pathdir : "",
508 (int) stemlen, stem));
509 continue;
510 }
511
512 if (!check_lastslash)
513 {
514 memcpy (stem_str, stem, stemlen);
515 stem_str[stemlen] = '\0';
516 }
517 else
518 {
519 /* We want to prepend the directory from
520 the original FILENAME onto the stem. */
521 memcpy (stem_str, filename, pathlen);
522 memcpy (stem_str + pathlen, stem, stemlen);
523 stem_str[pathlen + stemlen] = '\0';
524 }
525
526 /* If there are no prerequisites, then this rule matches. */
527 if (rule->deps == 0)
528 break;
529
530 /* Mark this rule as in use so a recursive pattern_search won't try
531 to use it. */
532 rule->in_use = 1;
533
534 /* Try each prerequisite; see if it exists or can be created. We'll
535 build a list of prereq info in DEPLIST. Due to 2nd expansion we
536 may have to process multiple prereqs for a single dep entry. */
537
538 pat = deplist;
539 dep = rule->deps;
540 nptr = dep_name (dep);
541 while (1)
542 {
543 struct dep *dl, *d;
544
545 /* If we're out of name to parse, start the next prereq. */
546 if (! nptr)
547 {
548 dep = dep->next;
549 if (dep == 0)
550 break;
551 nptr = dep_name (dep);
552 }
553
554 /* If we don't need a second expansion, just replace the %. */
555 if (! dep->need_2nd_expansion)
556 {
557 char *p;
558 int is_explicit = 1;
559 const char *cp = strchr (nptr, '%');
560 if (cp == 0)
561 strcpy (depname, nptr);
562 else
563 {
564 char *o = depname;
565 if (check_lastslash)
566 o = mempcpy (o, filename, pathlen);
567 o = mempcpy (o, nptr, cp - nptr);
568 o = mempcpy (o, stem, stemlen);
569 strcpy (o, cp + 1);
570 is_explicit = 0;
571 }
572
573 /* Parse the expanded string. It might have wildcards. */
574 p = depname;
575 dl = PARSE_FILE_SEQ (&p, struct dep, MAP_NUL, NULL,
576 PARSEFS_ONEWORD|PARSEFS_WAIT);
577 for (d = dl; d != NULL; d = d->next)
578 {
579 ++deps_found;
580 d->ignore_mtime = dep->ignore_mtime;
581 d->ignore_automatic_vars = dep->ignore_automatic_vars;
582 d->wait_here |= dep->wait_here;
583 d->is_explicit = is_explicit;
584 }
585
586 /* We've used up this dep, so next time get a new one. */
587 nptr = 0;
588 }
589
590 /* We have to perform second expansion on this prereq. In an
591 ideal world we would take the dependency line, substitute the
592 stem, re-expand the whole line and chop it into individual
593 prerequisites. Unfortunately this won't work because of the
594 "check_lastslash" twist. Instead, we will have to go word by
595 word, taking $()'s into account. For each word we will
596 substitute the stem, re-expand, chop it up, and, if
597 check_lastslash != 0, add the directory part to each
598 resulting prerequisite. */
599 else
600 {
601 int add_dir = 0;
602 size_t len;
603 const char *end;
604 struct dep **dptr;
605 int is_explicit;
606 const char *cp;
607 char *p;
608
609 nptr = get_next_word (nptr, &len);
610 if (nptr == 0)
611 continue;
612 end = nptr + len;
613
614 /* See if this is a transition to order-only prereqs. */
615 if (! order_only && len == 1 && nptr[0] == '|')
616 {
617 order_only = 1;
618 nptr = end;
619 continue;
620 }
621
622 /* If the dependency name has %, substitute the stem. If we
623 just replace % with the stem value then later, when we do
624 the 2nd expansion, we will re-expand this stem value
625 again. This is not good if you have certain characters
626 in your stem (like $).
627
628 Instead, we will replace % with $* or $(*F) and allow the
629 second expansion to take care of it for us. This way
630 (since $* and $(*F) are simple variables) there won't be
631 additional re-expansion of the stem. */
632
633 cp = lindex (nptr, end, '%');
634 if (cp == 0)
635 {
636 memcpy (depname, nptr, len);
637 depname[len] = '\0';
638 is_explicit = 1;
639 }
640 else
641 {
642 /* Go through all % between NPTR and END.
643 Copy contents of [NPTR, END) to depname, with the
644 first % after NPTR and then each first % after white
645 space replaced with $* or $(*F). depname has enough
646 room to substitute each % with $(*F). */
647 char *o = depname;
648
649 is_explicit = 0;
650 for (;;)
651 {
652 size_t i = cp - nptr;
653 assert (o + i < dend);
654 o = mempcpy (o, nptr, i);
655 if (check_lastslash)
656 {
657 add_dir = 1;
658 assert (o + 5 < dend);
659 o = mempcpy (o, "$(*F)", 5);
660 }
661 else
662 {
663 assert (o + 2 < dend);
664 o = mempcpy (o, "$*", 2);
665 }
666 assert (o < dend);
667 ++cp;
668 assert (cp <= end);
669 nptr = cp;
670 if (nptr == end)
671 break;
672
673 /* Skip the rest of this word then find the next %.
674 No need to worry about order-only, or nested
675 functions: NPTR went though get_next_word. */
676 while (cp < end && ! END_OF_TOKEN (*cp))
677 ++cp;
678 cp = lindex (cp, end, '%');
679 if (cp == 0)
680 break;
681 }
682 len = end - nptr;
683 memcpy (o, nptr, len);
684 o[len] = '\0';
685 }
686
687 /* Set up for the next word. */
688 nptr = end;
689
690 /* Initialize and set file variables if we haven't already
691 done so. */
692 if (!file_vars_initialized)
693 {
694 initialize_file_variables (file, 0);
695 set_file_variables (file, stem_str);
696 file_vars_initialized = 1;
697 }
698 /* Update the stem value in $* for this rule. */
699 else if (!file_variables_set)
700 {
701 define_variable_for_file (
702 "*", 1, stem_str, o_automatic, 0, file);
703 file_variables_set = 1;
704 }
705
706 /* Perform the 2nd expansion. */
707 p = variable_expand_for_file (depname, file);
708 dptr = &dl;
709
710 /* Parse the results into a deps list. */
711 do
712 {
713 /* Parse the expanded string. */
714 struct dep *dp = PARSE_FILE_SEQ (&p, struct dep,
715 order_only ? MAP_NUL : MAP_PIPE,
716 add_dir ? pathdir : NULL,
717 PARSEFS_WAIT);
718 *dptr = dp;
719
720 for (d = dp; d != NULL; d = d->next)
721 {
722 ++deps_found;
723 if (order_only)
724 d->ignore_mtime = 1;
725 d->is_explicit = is_explicit;
726 dptr = &d->next;
727 }
728
729 /* If we stopped due to an order-only token, note it. */
730 if (*p == '|')
731 {
732 order_only = 1;
733 ++p;
734 }
735 }
736 while (*p != '\0');
737 }
738
739 /* If there are more than max_pattern_deps prerequisites (due to
740 2nd expansion), reset it and realloc the arrays. */
741
742 if (deps_found > max_deps)
743 {
744 size_t l = pat - deplist;
745 /* This might have changed due to recursion. */
746 max_pattern_deps = MAX(max_pattern_deps, deps_found);
747 max_deps = max_pattern_deps;
748 deplist = xrealloc (deplist,
749 max_deps * sizeof (struct patdeps));
750 pat = deplist + l;
751 }
752
753 /* Go through the nameseq and handle each as a prereq name. */
754 for (d = dl; d != 0; d = d->next)
755 {
756 struct file *df;
757 int is_rule = d->name == dep_name (dep);
758 int explicit = 0;
759 struct dep *dp = 0;
760
761 if (file_impossible_p (d->name))
762 {
763 /* If this prereq has already been ruled "impossible",
764 then the rule fails. Don't bother trying it on the
765 second pass either since we know that will fail. */
766 DBS (DB_IMPLICIT,
767 (is_rule
768 ? _("Rejecting rule '%s' due to impossible rule"
769 " prerequisite '%s'.\n")
770 : _("Rejecting rule '%s' due to impossible implicit"
771 " prerequisite '%s'.\n"),
772 get_rule_defn (rule), d->name));
773 tryrules[ri].rule = 0;
774
775 failed = 1;
776 break;
777 }
778
779 memset (pat, '\0', sizeof (struct patdeps));
780 pat->ignore_mtime = d->ignore_mtime;
781 pat->ignore_automatic_vars = d->ignore_automatic_vars;
782 pat->wait_here = d->wait_here;
783 pat->is_explicit = d->is_explicit;
784
785 DBS (DB_IMPLICIT,
786 (is_rule
787 ? _("Trying rule prerequisite '%s'.\n")
788 : _("Trying implicit prerequisite '%s'.\n"), d->name));
789
790 df = lookup_file (d->name);
791
792 if (df && df->is_explicit)
793 pat->is_explicit = 1;
794
795 /* If we found a file for the dep, set its intermediate flag.
796 df->is_explicit is set when the dep file is mentioned
797 explicitly on some other rule. d->is_explicit is set when
798 the dep file is mentioned explicitly on this rule. E.g.:
799 %.x : %.y ; ...
800 then:
801 one.x:
802 one.y: # df->is_explicit
803 vs.
804 one.x: one.y # d->is_explicit
805 */
806 if (df && !df->is_explicit && !d->is_explicit)
807 df->intermediate = 1;
808
809 /* If the pattern prereq is also explicitly mentioned for
810 FILE, skip all tests below since it must be built no
811 matter which implicit rule we choose. */
812 if (df && df->is_target)
813 /* This prerequisite is mentioned explicitly as a target of
814 some rule. */
815 explicit = 1;
816 else
817 for (dp = file->deps; dp != 0; dp = dp->next)
818 if (streq (d->name, dep_name (dp)))
819 break;
820
821 /* If dp is set, this prerequisite is mentioned explicitly as
822 a prerequisite of the current target. */
823
824 if (explicit || dp)
825 {
826 (pat++)->name = d->name;
827 DBS (DB_IMPLICIT, (_("'%s' ought to exist.\n"), d->name));
828 continue;
829 }
830
831 if (file_exists_p (d->name))
832 {
833 (pat++)->name = d->name;
834 DBS (DB_IMPLICIT, (_("Found '%s'.\n"), d->name));
835 continue;
836 }
837
838 if (df && allow_compat_rules)
839 {
840 (pat++)->name = d->name;
841 DBS (DB_IMPLICIT,
842 (_("Using compatibility rule '%s' due to '%s'.\n"),
843 get_rule_defn (rule), d->name));
844 continue;
845 }
846
847 if (df)
848 {
849 /* This prerequisite is mentioned explicitly as a
850 prerequisite on some rule, but it is not a
851 prerequisite of the current target. Therefore, this
852 prerequisite does not qualify as ought-to-exist. Keep
853 note of this rule and continue the search. If a more
854 suitable rule is not found, then use this rule. */
855 DBS (DB_IMPLICIT,
856 (_("Prerequisite '%s' of rule '%s' does not qualify"
857 " as ought to exist.\n"),
858 d->name, get_rule_defn (rule)));
859 found_compat_rule = 1;
860 }
861
862 /* This code, given FILENAME = "lib/foo.o", dependency name
863 "lib/foo.c", and VPATH=src, searches for
864 "src/lib/foo.c". */
865 {
866 const char *vname = vpath_search (d->name, 0, NULL, NULL);
867 if (vname)
868 {
869 DBS (DB_IMPLICIT,
870 (_("Found prerequisite '%s' as VPATH '%s'.\n"),
871 d->name, vname));
872 (pat++)->name = d->name;
873 continue;
874 }
875 }
876
877 /* We could not find the file in any place we should look.
878 Look for an implicit rule to make this dependency, but
879 only on the second pass. */
880
881 if (intermed_ok)
882 {
883 DBS (DB_IMPLICIT,
884 (d->is_explicit || (df && df->is_explicit)
885 ? _("Looking for a rule with explicit file '%s'.\n")
886 : _("Looking for a rule with intermediate file '%s'.\n"),
887 d->name));
888
889 if (int_file == 0)
890 int_file = alloca (sizeof (struct file));
891 memset (int_file, '\0', sizeof (struct file));
892 int_file->name = d->name;
893
894 if (pattern_search (int_file,
895 0,
896 depth + 1,
897 recursions + 1,
898 allow_compat_rules))
899 {
900 pat->pattern = int_file->name;
901 int_file->name = d->name;
902 pat->file = int_file;
903 int_file = 0;
904 (pat++)->name = d->name;
905 continue;
906 }
907
908 /* If we have tried to find P as an intermediate file
909 and failed, mark that name as impossible so we won't
910 go through the search again later. */
911 if (int_file->variables)
912 free_variable_set (int_file->variables);
913 if (int_file->pat_variables)
914 free_variable_set (int_file->pat_variables);
915
916 /* Keep prerequisites explicitly mentioned on unrelated
917 rules as "possible" to let compatibility search find
918 such prerequisites. */
919 if (df == 0)
920 file_impossible (d->name);
921 }
922
923 /* A dependency of this rule does not exist. Therefore, this
924 rule fails. */
925 if (intermed_ok)
926 DBS (DB_IMPLICIT,
927 (_("Rejecting rule '%s' "
928 "due to impossible prerequisite '%s'.\n"),
929 get_rule_defn (rule), d->name));
930 else
931 DBS (DB_IMPLICIT, (_("Not found '%s'.\n"), d->name));
932
933 failed = 1;
934 break;
935 }
936
937 /* Free the ns chain. */
938 free_dep_chain (dl);
939
940 if (failed)
941 break;
942 }
943
944 /* This rule is no longer 'in use' for recursive searches. */
945 rule->in_use = 0;
946
947 if (! failed)
948 /* This pattern rule does apply. Stop looking for one. */
949 break;
950
951 /* This pattern rule does not apply. Keep looking. */
952 }
953
954 /* If we found an applicable rule without intermediate files, don't try
955 with them. */
956 if (ri < nrules)
957 break;
958
959 rule = 0;
960 }
961
962 /* RULE is nil if the loop went through the list but everything failed. */
963 if (rule == 0)
964 goto done;
965
966 foundrule = ri;
967
968 /* If we are recursing, store the pattern that matched FILENAME in
969 FILE->name for use in upper levels. */
970
971 if (recursions > 0)
972 /* Kludge-o-matic */
973 file->name = rule->targets[tryrules[foundrule].matches];
974
975 /* DEPLIST lists the prerequisites for the rule we found. This includes the
976 intermediate files, if any. Convert them into entries on the deps-chain
977 of FILE. */
978
979 while (pat-- > deplist)
980 {
981 struct dep *dep;
982 const char *s;
983
984 if (pat->file != 0)
985 {
986 /* If we need to use an intermediate file, make sure it is entered
987 as a target, with the info that was found for it in the recursive
988 pattern_search call. We know that the intermediate file did not
989 already exist as a target; therefore we can assume that the deps
990 and cmds of F below are null before we change them. */
991
992 struct file *imf = pat->file;
993 struct file *f = lookup_file (imf->name);
994
995 if (!f)
996 f = enter_file (imf->name);
997
998 f->deps = imf->deps;
999 f->cmds = imf->cmds;
1000 f->stem = imf->stem;
1001 /* Setting target specific variables for a file causes the file to be
1002 entered to the database as a prerequisite. Implicit search then
1003 treats this file as explicitly mentioned. Preserve target specific
1004 variables of this file. */
1005 merge_variable_set_lists(&f->variables, imf->variables);
1006 f->pat_variables = imf->pat_variables;
1007 f->pat_searched = imf->pat_searched;
1008 f->also_make = imf->also_make;
1009 f->is_target = 1;
1010 f->is_explicit |= imf->is_explicit || pat->is_explicit;
1011 f->notintermediate |= imf->notintermediate;
1012 f->intermediate |= !f->is_explicit && !f->notintermediate;
1013 f->tried_implicit = 1;
1014
1015 imf = lookup_file (pat->pattern);
1016 if (imf != 0 && imf->precious)
1017 f->precious = 1;
1018
1019 for (dep = f->deps; dep != 0; dep = dep->next)
1020 {
1021 dep->file = enter_file (dep->name);
1022 dep->name = 0;
1023 dep->file->tried_implicit |= dep->changed;
1024 }
1025 }
1026
1027 dep = alloc_dep ();
1028 dep->ignore_mtime = pat->ignore_mtime;
1029 dep->is_explicit = pat->is_explicit;
1030 dep->ignore_automatic_vars = pat->ignore_automatic_vars;
1031 dep->wait_here = pat->wait_here;
1032 s = strcache_add (pat->name);
1033 if (recursions)
1034 dep->name = s;
1035 else
1036 {
1037 dep->file = lookup_file (s);
1038 if (dep->file == 0)
1039 dep->file = enter_file (s);
1040 }
1041
1042 if (pat->file == 0 && tryrules[foundrule].rule->terminal)
1043 {
1044 /* If the file actually existed (was not an intermediate file), and
1045 the rule that found it was a terminal one, then we want to mark
1046 the found file so that it will not have implicit rule search done
1047 for it. If we are not entering a 'struct file' for it now, we
1048 indicate this with the 'changed' flag. */
1049 if (dep->file == 0)
1050 dep->changed = 1;
1051 else
1052 dep->file->tried_implicit = 1;
1053 }
1054
1055 dep->next = file->deps;
1056 file->deps = dep;
1057
1058 /* The file changed its dependencies; schedule the shuffle. */
1059 file->was_shuffled = 0;
1060 }
1061
1062 if (!file->was_shuffled)
1063 shuffle_deps_recursive (file->deps);
1064
1065 if (!tryrules[foundrule].checked_lastslash)
1066 {
1067 /* Always allocate new storage, since STEM might be on the stack for an
1068 intermediate file. */
1069 file->stem = strcache_add_len (stem, stemlen);
1070 fullstemlen = stemlen;
1071 }
1072 else
1073 {
1074 /* We want to prepend the directory from
1075 the original FILENAME onto the stem. */
1076 fullstemlen = pathlen + stemlen;
1077 memcpy (stem_str, filename, pathlen);
1078 memcpy (stem_str + pathlen, stem, stemlen);
1079 stem_str[fullstemlen] = '\0';
1080 file->stem = strcache_add (stem_str);
1081 }
1082
1083 file->cmds = rule->cmds;
1084 file->is_target = 1;
1085
1086 /* Set precious and notintermediate flags. */
1087 {
1088 struct file *f = lookup_file (rule->targets[tryrules[foundrule].matches]);
1089 if (f)
1090 {
1091 if (f->precious)
1092 file->precious = 1;
1093 if (f->notintermediate)
1094 file->notintermediate = 1;
1095 }
1096 }
1097
1098 /* If this rule builds other targets, too, put the others into FILE's
1099 'also_make' member. */
1100
1101 if (rule->num > 1)
1102 for (ri = 0; ri < rule->num; ++ri)
1103 if (ri != tryrules[foundrule].matches)
1104 {
1105 char *nm = alloca (rule->lens[ri] + fullstemlen + 1);
1106 char *p = nm;
1107 struct file *f;
1108 struct dep *new = alloc_dep ();
1109
1110 /* GKM FIMXE: handle '|' here too */
1111 p = mempcpy (p, rule->targets[ri],
1112 rule->suffixes[ri] - rule->targets[ri] - 1);
1113 p = mempcpy (p, file->stem, fullstemlen);
1114 memcpy (p, rule->suffixes[ri],
1115 rule->lens[ri] - (rule->suffixes[ri] - rule->targets[ri])+1);
1116 new->name = strcache_add (nm);
1117 new->file = enter_file (new->name);
1118 new->next = file->also_make;
1119
1120 /* Set precious flag. */
1121 f = lookup_file (rule->targets[ri]);
1122 if (f)
1123 {
1124 if (f->precious)
1125 new->file->precious = 1;
1126 if (f->notintermediate)
1127 new->file->notintermediate = 1;
1128 }
1129
1130 /* Set the is_target flag so that this file is not treated as
1131 intermediate by the pattern rule search algorithm and
1132 file_exists_p cannot pick it up yet. */
1133 new->file->is_target = 1;
1134
1135 file->also_make = new;
1136 }
1137
1138 done:
1139 free (tryrules);
1140 free (deplist);
1141
1142 if (rule)
1143 {
1144 DBS (DB_IMPLICIT, (_("Found implicit rule '%s' for '%s'.\n"),
1145 get_rule_defn (rule), filename));
1146 return 1;
1147 }
1148
1149 if (found_compat_rule)
1150 {
1151 DBS (DB_IMPLICIT, (_("Searching for a compatibility rule for '%s'.\n"),
1152 filename));
1153 assert (allow_compat_rules == 0);
1154 return pattern_search (file, archive, depth, recursions, 1);
1155 }
1156
1157 DBS (DB_IMPLICIT, (_("No implicit rule found for '%s'.\n"), filename));
1158 return 0;
1159 }