rule.c

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