1 /* Pattern and suffix rule internals 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
19 #include <assert.h>
20
21 #include "filedef.h"
22 #include "dep.h"
23 #include "job.h"
24 #include "commands.h"
25 #include "variable.h"
26 #include "rule.h"
27
28 static void freerule (struct rule *rule, struct rule *lastrule);
29
30 /* Chain of all pattern rules. */
31
32 struct rule *pattern_rules;
33
34 /* Pointer to last rule in the chain, so we can add onto the end. */
35
36 struct rule *last_pattern_rule;
37
38 /* Number of rules in the chain. */
39
40 unsigned int num_pattern_rules;
41
42 /* Maximum number of target patterns of any pattern rule. */
43
44 unsigned int max_pattern_targets;
45
46 /* Maximum number of dependencies of any pattern rule. */
47
48 unsigned int max_pattern_deps;
49
50 /* Maximum length of the name of a dependencies of any pattern rule. */
51
52 size_t max_pattern_dep_length;
53
54 /* Pointer to structure for the file .SUFFIXES
55 whose dependencies are the suffixes to be searched. */
56
57 struct file *suffix_file;
58
59 /* Maximum length of a suffix. */
60
61 static size_t maxsuffix;
62
63 /* Return the rule definition: space separated rule targets, followed by
64 either a colon or two colons in the case of a terminal rule, followed by
65 space separated rule prerequisites, followed by a pipe, followed by
66 order-only prerequisites, if present. */
67
68 const char *
69 get_rule_defn (struct rule *r)
70 {
71 if (r->_defn == NULL)
72 {
73 size_t len = 8; /* Reserve for ":: ", " | ", and nul. */
74 unsigned int k;
75 char *p;
76 const char *sep = "";
77 const struct dep *dep, *ood = 0;
78
79 for (k = 0; k < r->num; ++k)
80 len += r->lens[k] + 1;
81
82 for (dep = r->deps; dep; dep = dep->next)
83 len += strlen (dep_name (dep)) + (dep->wait_here ? CSTRLEN (" .WAIT") : 0) + 1;
84
85 p = r->_defn = xmalloc (len);
86 for (k = 0; k < r->num; ++k, sep = " ")
87 p = mempcpy (mempcpy (p, sep, strlen (sep)), r->targets[k], r->lens[k]);
88 *p++ = ':';
89 if (r->terminal)
90 *p++ = ':';
91
92 /* Copy all normal dependencies; note any order-only deps. */
93 for (dep = r->deps; dep; dep = dep->next)
94 if (dep->ignore_mtime == 0)
95 {
96 if (dep->wait_here)
97 p = mempcpy (p, " .WAIT", CSTRLEN (" .WAIT"));
98 p = mempcpy (mempcpy (p, " ", 1), dep_name (dep),
99 strlen (dep_name (dep)));
100 }
101 else if (ood == 0)
102 ood = dep;
103
104 /* Copy order-only deps, if we have any. */
105 for (sep = " | "; ood; ood = ood->next, sep = " ")
106 if (ood->ignore_mtime)
107 {
108 p = mempcpy (p, sep, strlen (sep));
109 if (ood->wait_here)
110 p = mempcpy (p, ".WAIT ", CSTRLEN (".WAIT "));
111 p = mempcpy (p, dep_name (ood), strlen (dep_name (ood)));
112 }
113 *p = '\0';
114 }
115
116 return r->_defn;
117 }
118
119
120 /* Compute the maximum dependency length and maximum number of dependencies of
121 all implicit rules. Also sets the subdir flag for a rule when appropriate,
122 possibly removing the rule completely when appropriate.
123
124 Add any global EXTRA_PREREQS here as well. */
125
126 void
127 snap_implicit_rules (void)
128 {
129 char *name = NULL;
130 size_t namelen = 0;
131 struct rule *rule;
132 struct dep *dep;
133 struct dep *prereqs = expand_extra_prereqs (lookup_variable (STRING_SIZE_TUPLE(".EXTRA_PREREQS")));
134 unsigned int pre_deps = 0;
135
136 max_pattern_dep_length = 0;
137
138 for (dep = prereqs; dep; dep = dep->next)
139 {
140 const char *d = dep_name (dep);
141 size_t l = strlen (d);
142
143 if (dep->need_2nd_expansion)
144 /* When pattern_search allocates a buffer, allow 5 bytes per each % to
145 substitute each % with $(*F) while avoiding realloc. */
146 while ((d = strchr (d, '%')) != 0)
147 {
148 l += 4;
149 ++d;
150 }
151
152 if (l > max_pattern_dep_length)
153 max_pattern_dep_length = l;
154 ++pre_deps;
155 }
156
157 num_pattern_rules = max_pattern_targets = max_pattern_deps = 0;
158
159 for (rule = pattern_rules; rule; rule = rule->next)
160 {
161 unsigned int ndeps = pre_deps;
162 struct dep *lastdep = NULL;
163
164 ++num_pattern_rules;
165
166 if (rule->num > max_pattern_targets)
167 max_pattern_targets = rule->num;
168
169 for (dep = rule->deps; dep != 0; dep = dep->next)
170 {
171 const char *dname = dep_name (dep);
172 size_t len = strlen (dname);
173
174 #ifdef VMS
175 const char *p = strrchr (dname, ']');
176 const char *p2;
177 if (p == 0)
178 p = strrchr (dname, ':');
179 p2 = p ? strchr (p, '%') : 0;
180 #else
181 const char *p = strrchr (dname, '/');
182 const char *p2 = p ? strchr (p, '%') : 0;
183 #endif
184 ndeps++;
185
186 if (len > max_pattern_dep_length)
187 max_pattern_dep_length = len;
188
189 if (!dep->next)
190 lastdep = dep;
191
192 if (p2)
193 {
194 /* There is a slash before the % in the dep name.
195 Extract the directory name. */
196 if (p == dname)
197 ++p;
198 if ((size_t) (p - dname) > namelen)
199 {
200 namelen = p - dname;
201 name = xrealloc (name, namelen + 1);
202 }
203 memcpy (name, dname, p - dname);
204 name[p - dname] = '\0';
205
206 /* In the deps of an implicit rule the 'changed' flag
207 actually indicates that the dependency is in a
208 nonexistent subdirectory. */
209
210 dep->changed = !dir_file_exists_p (name, "");
211 }
212 else
213 /* This dependency does not reside in a subdirectory. */
214 dep->changed = 0;
215 }
216
217 if (prereqs)
218 {
219 if (lastdep)
220 lastdep->next = copy_dep_chain (prereqs);
221 else
222 rule->deps = copy_dep_chain (prereqs);
223 }
224
225 if (ndeps > max_pattern_deps)
226 max_pattern_deps = ndeps;
227 }
228
229 free (name);
230 free_dep_chain (prereqs);
231 }
232
233 /* Create a pattern rule from a suffix rule.
234 TARGET is the target suffix; SOURCE is the source suffix.
235 CMDS are the commands.
236 If TARGET is nil, it means the target pattern should be '(%.o)'.
237 If SOURCE is nil, it means there should be no deps. */
238
239 static void
240 convert_suffix_rule (const char *target, const char *source,
241 struct commands *cmds)
242 {
243 const char **names, **percents;
244 struct dep *deps;
245
246 names = xmalloc (sizeof (const char *));
247 percents = xmalloc (sizeof (const char *));
248
249 if (target == 0)
250 {
251 /* Special case: TARGET being nil means we are defining a '.X.a' suffix
252 rule; the target pattern is always '(%.o)'. */
253 #ifdef VMS
254 *names = strcache_add_len ("(%.obj)", 7);
255 #else
256 *names = strcache_add_len ("(%.o)", 5);
257 #endif
258 *percents = *names + 1;
259 }
260 else
261 {
262 /* Construct the target name. */
263 size_t len = strlen (target);
264 char *p = alloca (1 + len + 1);
265 p[0] = '%';
266 memcpy (p + 1, target, len + 1);
267 *names = strcache_add_len (p, len + 1);
268 *percents = *names;
269 }
270
271 if (source == 0)
272 deps = 0;
273 else
274 {
275 /* Construct the dependency name. */
276 size_t len = strlen (source);
277 char *p = alloca (1 + len + 1);
278 p[0] = '%';
279 memcpy (p + 1, source, len + 1);
280 deps = alloc_dep ();
281 deps->name = strcache_add_len (p, len + 1);
282 }
283
284 create_pattern_rule (names, percents, 1, 0, deps, cmds, 0);
285 }
286
287 /* Convert old-style suffix rules to pattern rules.
288 All rules for the suffixes on the .SUFFIXES list are converted and added to
289 the chain of pattern rules. */
290
291 void
292 convert_to_pattern (void)
293 {
294 struct dep *d, *d2;
295 char *rulename;
296
297 /* We will compute every potential suffix rule (.x.y) from the list of
298 suffixes in the .SUFFIXES target's dependencies and see if it exists.
299 First find the longest of the suffixes. */
300
301 maxsuffix = 0;
302 for (d = suffix_file->deps; d != 0; d = d->next)
303 {
304 size_t l = strlen (dep_name (d));
305 if (l > maxsuffix)
306 maxsuffix = l;
307 }
308
309 /* Space to construct the suffix rule target name. */
310 rulename = alloca ((maxsuffix * 2) + 1);
311
312 for (d = suffix_file->deps; d != 0; d = d->next)
313 {
314 size_t slen;
315
316 /* Make a rule that is just the suffix, with no deps or commands.
317 This rule exists solely to disqualify match-anything rules. */
318 convert_suffix_rule (dep_name (d), 0, 0);
319
320 if (d->file->cmds != 0)
321 /* Record a pattern for this suffix's null-suffix rule. */
322 convert_suffix_rule ("", dep_name (d), d->file->cmds);
323
324 /* Add every other suffix to this one and see if it exists as a
325 two-suffix rule. */
326 slen = strlen (dep_name (d));
327 memcpy (rulename, dep_name (d), slen);
328
329 for (d2 = suffix_file->deps; d2 != 0; d2 = d2->next)
330 {
331 struct file *f;
332 size_t s2len;
333
334 s2len = strlen (dep_name (d2));
335
336 /* Can't build something from itself. */
337 if (slen == s2len && streq (dep_name (d), dep_name (d2)))
338 continue;
339
340 memcpy (rulename + slen, dep_name (d2), s2len + 1);
341 f = lookup_file (rulename);
342
343 /* No target, or no commands: it can't be a suffix rule. */
344 if (f == 0 || f->cmds == 0)
345 continue;
346
347 /* POSIX says that suffix rules can't have prerequisites.
348 In POSIX mode, don't make this a suffix rule. Previous versions
349 of GNU make did treat this as a suffix rule and ignored the
350 prerequisites, which is bad. In the future we'll do the same as
351 POSIX, but for now preserve the old behavior and warn about it. */
352 if (f->deps != 0)
353 {
354 if (posix_pedantic)
355 continue;
356 error (&f->cmds->fileinfo, 0,
357 _("warning: ignoring prerequisites on suffix rule definition"));
358 }
359
360 if (s2len == 2 && rulename[slen] == '.' && rulename[slen + 1] == 'a')
361 /* A suffix rule '.X.a:' generates the pattern rule '(%.o): %.X'.
362 It also generates a normal '%.a: %.X' rule below. */
363 convert_suffix_rule (NULL, /* Indicates '(%.o)'. */
364 dep_name (d),
365 f->cmds);
366
367 /* The suffix rule '.X.Y:' is converted
368 to the pattern rule '%.Y: %.X'. */
369 convert_suffix_rule (dep_name (d2), dep_name (d), f->cmds);
370 }
371 }
372 }
373
374
375 /* Install the pattern rule RULE (whose fields have been filled in) at the end
376 of the list (so that any rules previously defined will take precedence).
377 If this rule duplicates a previous one (identical target and dependencies),
378 the old one is replaced if OVERRIDE is nonzero, otherwise this new one is
379 thrown out. When an old rule is replaced, the new one is put at the end of
380 the list. Return nonzero if RULE is used; zero if not. */
381
382 static int
383 new_pattern_rule (struct rule *rule, int override)
384 {
385 struct rule *r, *lastrule;
386 unsigned int i, j;
387
388 rule->in_use = 0;
389 rule->terminal = 0;
390
391 rule->next = 0;
392
393 /* Search for an identical rule. */
394 lastrule = 0;
395 for (r = pattern_rules; r != 0; lastrule = r, r = r->next)
396 for (i = 0; i < rule->num; ++i)
397 {
398 for (j = 0; j < r->num; ++j)
399 if (!streq (rule->targets[i], r->targets[j]))
400 break;
401 /* If all the targets matched... */
402 if (j == r->num)
403 {
404 struct dep *d, *d2;
405 for (d = rule->deps, d2 = r->deps;
406 d != 0 && d2 != 0; d = d->next, d2 = d2->next)
407 if (!streq (dep_name (d), dep_name (d2)))
408 break;
409 if (d == 0 && d2 == 0)
410 {
411 /* All the dependencies matched. */
412 if (override)
413 {
414 /* Remove the old rule. */
415 freerule (r, lastrule);
416 /* Install the new one. */
417 if (pattern_rules == 0)
418 pattern_rules = rule;
419 else
420 last_pattern_rule->next = rule;
421 last_pattern_rule = rule;
422
423 /* We got one. Stop looking. */
424 goto matched;
425 }
426 else
427 {
428 /* The old rule stays intact. Destroy the new one. */
429 freerule (rule, (struct rule *) 0);
430 return 0;
431 }
432 }
433 }
434 }
435
436 matched:;
437
438 if (r == 0)
439 {
440 /* There was no rule to replace. */
441 if (pattern_rules == 0)
442 pattern_rules = rule;
443 else
444 last_pattern_rule->next = rule;
445 last_pattern_rule = rule;
446 }
447
448 return 1;
449 }
450
451
452 /* Install an implicit pattern rule based on the three text strings
453 in the structure P points to. These strings come from one of
454 the arrays of default implicit pattern rules.
455 TERMINAL specifies what the 'terminal' field of the rule should be. */
456
457 void
458 install_pattern_rule (struct pspec *p, int terminal)
459 {
460 struct rule *r;
461 const char *ptr;
462
463 r = xmalloc (sizeof (struct rule));
464
465 r->num = 1;
466 r->targets = xmalloc (sizeof (const char *));
467 r->suffixes = xmalloc (sizeof (const char *));
468 r->lens = xmalloc (sizeof (unsigned int));
469 r->_defn = NULL;
470
471 r->lens[0] = (unsigned int) strlen (p->target);
472 r->targets[0] = p->target;
473 r->suffixes[0] = find_percent_cached (&r->targets[0]);
474 assert (r->suffixes[0] != NULL);
475 ++r->suffixes[0];
476
477 ptr = p->dep;
478 r->deps = PARSE_SIMPLE_SEQ ((char **)&ptr, struct dep);
479
480 if (new_pattern_rule (r, 0))
481 {
482 r->terminal = terminal ? 1 : 0;
483 r->cmds = xmalloc (sizeof (struct commands));
484 r->cmds->fileinfo.filenm = 0;
485 r->cmds->fileinfo.lineno = 0;
486 r->cmds->fileinfo.offset = 0;
487 /* These will all be string literals, but we malloc space for them
488 anyway because somebody might want to free them later. */
489 r->cmds->commands = xstrdup (p->commands);
490 r->cmds->command_lines = 0;
491 r->cmds->recipe_prefix = RECIPEPREFIX_DEFAULT;
492 }
493 }
494
495
496 /* Free all the storage used in RULE and take it out of the
497 pattern_rules chain. LASTRULE is the rule whose next pointer
498 points to RULE. */
499
500 static void
501 freerule (struct rule *rule, struct rule *lastrule)
502 {
503 struct rule *next = rule->next;
504
505 free_dep_chain (rule->deps);
506
507 /* MSVC erroneously warns without a cast here. */
508 free ((void *)rule->targets);
509 free ((void *)rule->suffixes);
510 free (rule->lens);
511 free ((void *) rule->_defn);
512
513 /* We can't free the storage for the commands because there
514 are ways that they could be in more than one place:
515 * If the commands came from a suffix rule, they could also be in
516 the 'struct file's for other suffix rules or plain targets given
517 on the same makefile line.
518 * If two suffixes that together make a two-suffix rule were each
519 given twice in the .SUFFIXES list, and in the proper order, two
520 identical pattern rules would be created and the second one would
521 be discarded here, but both would contain the same 'struct commands'
522 pointer from the 'struct file' for the suffix rule. */
523
524 free (rule);
525
526 if (pattern_rules == rule)
527 if (lastrule != 0)
528 abort ();
529 else
530 pattern_rules = next;
531 else if (lastrule != 0)
532 lastrule->next = next;
533 if (last_pattern_rule == rule)
534 last_pattern_rule = lastrule;
535 }
536
537 /* Create a new pattern rule with the targets in the nil-terminated array
538 TARGETS. TARGET_PERCENTS is an array of pointers to the % in each element
539 of TARGETS. N is the number of items in the array (not counting the nil
540 element). The new rule has dependencies DEPS and commands from COMMANDS.
541 It is a terminal rule if TERMINAL is nonzero. This rule overrides
542 identical rules with different commands if OVERRIDE is nonzero.
543
544 The storage for TARGETS and its elements and TARGET_PERCENTS is used and
545 must not be freed until the rule is destroyed. */
546
547 void
548 create_pattern_rule (const char **targets, const char **target_percents,
549 unsigned short n, int terminal, struct dep *deps,
550 struct commands *commands, int override)
551 {
552 unsigned int i;
553 struct rule *r = xmalloc (sizeof (struct rule));
554
555 r->num = n;
556 r->cmds = commands;
557 r->deps = deps;
558 r->targets = targets;
559 r->suffixes = target_percents;
560 r->lens = xmalloc (n * sizeof (unsigned int));
561 r->_defn = NULL;
562
563 for (i = 0; i < n; ++i)
564 {
565 r->lens[i] = (unsigned int) strlen (targets[i]);
566 assert (r->suffixes[i] != NULL);
567 ++r->suffixes[i];
568 }
569
570 if (new_pattern_rule (r, override))
571 r->terminal = terminal ? 1 : 0;
572 }
573
574 /* Print the data base of rules. */
575
576 static void /* Useful to call from gdb. */
577 print_rule (struct rule *r)
578 {
579 fputs (get_rule_defn (r), stdout);
580 putchar ('\n');
581
582 if (r->cmds != 0)
583 print_commands (r->cmds);
584 }
585
586 void
587 print_rule_data_base (void)
588 {
589 unsigned int rules, terminal;
590 struct rule *r;
591
592 puts (_("\n# Implicit Rules"));
593
594 rules = terminal = 0;
595 for (r = pattern_rules; r != 0; r = r->next)
596 {
597 ++rules;
598
599 putchar ('\n');
600 print_rule (r);
601
602 if (r->terminal)
603 ++terminal;
604 }
605
606 if (rules == 0)
607 puts (_("\n# No implicit rules."));
608 else
609 {
610 printf (_("\n# %u implicit rules, %u (%.1f%%) terminal."),
611 rules, terminal, (double) terminal / (double) rules * 100.0);
612 }
613
614 if (num_pattern_rules != rules)
615 {
616 /* This can happen if a fatal error was detected while reading the
617 makefiles and thus count_implicit_rule_limits wasn't called yet. */
618 if (num_pattern_rules != 0)
619 ONN (fatal, NILF, _("BUG: num_pattern_rules is wrong! %u != %u"),
620 num_pattern_rules, rules);
621 }
622 }