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