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 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 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           unsigned int len = strlen (dep->name);
  98
  99 #ifdef VMS
 100           const char *p = strrchr (dep->name, ']');
 101           const char *p2;
 102           if (p == 0)
 103             p = strrchr (dep->name, ':');
 104           p2 = p != 0 ? strchr (dep->name, '%') : 0;
 105 #else
 106           const char *p = strrchr (dep->name, '/');
 107           const char *p2 = p != 0 ? strchr (dep->name, '%') : 0;
 108 #endif
 109           ndeps++;
 110
 111           if (len > max_pattern_dep_length)
 112             max_pattern_dep_length = len;
 113
 114           if (p != 0 && p2 > p)
 115             {
 116               /* There is a slash before the % in the dep name.
 117                  Extract the directory name.  */
 118               if (p == dep->name)
 119                 ++p;
 120               if (p - dep->name > namelen)
 121                 {
 122                   namelen = p - dep->name;
 123                   name = xrealloc (name, namelen + 1);
 124                 }
 125               memcpy (name, dep->name, p - dep->name);
 126               name[p - dep->name] = '\0';
 127
 128               /* In the deps of an implicit rule the `changed' flag
 129                  actually indicates that the dependency is in a
 130                  nonexistent subdirectory.  */
 131
 132               dep->changed = !dir_file_exists_p (name, "");
 133             }
 134           else
 135             /* This dependency does not reside in a subdirectory.  */
 136             dep->changed = 0;
 137         }
 138
 139       if (ndeps > max_pattern_deps)
 140         max_pattern_deps = ndeps;
 141
 142       lastrule = rule;
 143       rule = next;
 144     }
 145
 146   if (name != 0)
 147     free (name);
 148 }
 149 \f
 150 /* Create a pattern rule from a suffix rule.
 151    TARGET is the target suffix; SOURCE is the source suffix.
 152    CMDS are the commands.
 153    If TARGET is nil, it means the target pattern should be `(%.o)'.
 154    If SOURCE is nil, it means there should be no deps.  */
 155
 156 static void
 157 convert_suffix_rule (const char *target, const char *source,
 158                      struct commands *cmds)
 159 {
 160   const char **names, **percents;
 161   struct dep *deps;
 162
 163   names = xmalloc (sizeof (const char *));
 164   percents = xmalloc (sizeof (const char *));
 165
 166   if (target == 0)
 167     {
 168       /* Special case: TARGET being nil means we are defining a `.X.a' suffix
 169          rule; the target pattern is always `(%.o)'.  */
 170 #ifdef VMS
 171       *names = strcache_add_len ("(%.obj)", 7);
 172 #else
 173       *names = strcache_add_len ("(%.o)", 5);
 174 #endif
 175       *percents = *names + 1;
 176     }
 177   else
 178     {
 179       /* Construct the target name.  */
 180       unsigned int len = strlen (target);
 181       char *p = alloca (1 + len + 1);
 182       p[0] = '%';
 183       memcpy (p + 1, target, len + 1);
 184       *names = strcache_add_len (p, len + 1);
 185       *percents = *names;
 186     }
 187
 188   if (source == 0)
 189     deps = 0;
 190   else
 191     {
 192       /* Construct the dependency name.  */
 193       unsigned int len = strlen (source);
 194       char *p = alloca (1 + len + 1);
 195       p[0] = '%';
 196       memcpy (p + 1, source, len + 1);
 197       deps = alloc_dep ();
 198       deps->name = strcache_add_len (p, len + 1);
 199     }
 200
 201   create_pattern_rule (names, percents, 1, 0, deps, cmds, 0);
 202 }
 203
 204 /* Convert old-style suffix rules to pattern rules.
 205    All rules for the suffixes on the .SUFFIXES list are converted and added to
 206    the chain of pattern rules.  */
 207
 208 void
 209 convert_to_pattern (void)
 210 {
 211   struct dep *d, *d2;
 212   char *rulename;
 213
 214   /* We will compute every potential suffix rule (.x.y) from the list of
 215      suffixes in the .SUFFIXES target's dependencies and see if it exists.
 216      First find the longest of the suffixes.  */
 217
 218   maxsuffix = 0;
 219   for (d = suffix_file->deps; d != 0; d = d->next)
 220     {
 221       unsigned int l = strlen (dep_name (d));
 222       if (l > maxsuffix)
 223         maxsuffix = l;
 224     }
 225
 226   /* Space to construct the suffix rule target name.  */
 227   rulename = alloca ((maxsuffix * 2) + 1);
 228
 229   for (d = suffix_file->deps; d != 0; d = d->next)
 230     {
 231       unsigned int slen;
 232
 233       /* Make a rule that is just the suffix, with no deps or commands.
 234          This rule exists solely to disqualify match-anything rules.  */
 235       convert_suffix_rule (dep_name (d), 0, 0);
 236
 237       if (d->file->cmds != 0)
 238         /* Record a pattern for this suffix's null-suffix rule.  */
 239         convert_suffix_rule ("", dep_name (d), d->file->cmds);
 240
 241       /* Add every other suffix to this one and see if it exists as a
 242          two-suffix rule.  */
 243       slen = strlen (dep_name (d));
 244       memcpy (rulename, dep_name (d), slen);
 245
 246       for (d2 = suffix_file->deps; d2 != 0; d2 = d2->next)
 247         {
 248           struct file *f;
 249           unsigned int s2len;
 250
 251           s2len = strlen (dep_name (d2));
 252
 253           /* Can't build something from itself.  */
 254           if (slen == s2len && streq (dep_name (d), dep_name (d2)))
 255             continue;
 256
 257           memcpy (rulename + slen, dep_name (d2), s2len + 1);
 258           f = lookup_file (rulename);
 259           if (f == 0 || f->cmds == 0)
 260             continue;
 261
 262           if (s2len == 2 && rulename[slen] == '.' && rulename[slen + 1] == 'a')
 263             /* A suffix rule `.X.a:' generates the pattern rule `(%.o): %.X'.
 264                It also generates a normal `%.a: %.X' rule below.  */
 265             convert_suffix_rule (NULL, /* Indicates `(%.o)'.  */
 266                                  dep_name (d),
 267                                  f->cmds);
 268
 269           /* The suffix rule `.X.Y:' is converted
 270              to the pattern rule `%.Y: %.X'.  */
 271           convert_suffix_rule (dep_name (d2), dep_name (d), f->cmds);
 272         }
 273     }
 274 }
 275
 276
 277 /* Install the pattern rule RULE (whose fields have been filled in) at the end
 278    of the list (so that any rules previously defined will take precedence).
 279    If this rule duplicates a previous one (identical target and dependencies),
 280    the old one is replaced if OVERRIDE is nonzero, otherwise this new one is
 281    thrown out.  When an old rule is replaced, the new one is put at the end of
 282    the list.  Return nonzero if RULE is used; zero if not.  */
 283
 284 static int
 285 new_pattern_rule (struct rule *rule, int override)
 286 {
 287   struct rule *r, *lastrule;
 288   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; i < rule->num; ++i)
 299       {
 300         for (j = 0; j < r->num; ++j)
 301           if (!streq (rule->targets[i], r->targets[j]))
 302             break;
 303         /* If all the targets matched...  */
 304         if (j == r->num)
 305           {
 306             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
 360 install_pattern_rule (struct pspec *p, int terminal)
 361 {
 362   struct rule *r;
 363   char *ptr;
 364
 365   r = xmalloc (sizeof (struct rule));
 366
 367   r->num = 1;
 368   r->targets = xmalloc (sizeof (const char *));
 369   r->suffixes = xmalloc (sizeof (const char *));
 370   r->lens = xmalloc (sizeof (unsigned int));
 371
 372   r->lens[0] = strlen (p->target);
 373   r->targets[0] = p->target;
 374   r->suffixes[0] = find_percent_cached (&r->targets[0]);
 375   assert (r->suffixes[0] != NULL);
 376   ++r->suffixes[0];
 377
 378   ptr = p->dep;
 379   r->deps = (struct dep *) multi_glob (parse_file_seq (&ptr, '\0',
 380                                                        sizeof (struct dep), 1),
 381                                        sizeof (struct dep), 0);
 382
 383   if (new_pattern_rule (r, 0))
 384     {
 385       r->terminal = terminal;
 386       r->cmds = xmalloc (sizeof (struct commands));
 387       r->cmds->fileinfo.filenm = 0;
 388       r->cmds->fileinfo.lineno = 0;
 389       /* These will all be string literals, but we malloc space for them
 390          anyway because somebody might want to free them later.  */
 391       r->cmds->commands = xstrdup (p->commands);
 392       r->cmds->command_lines = 0;
 393     }
 394 }
 395
 396
 397 /* Free all the storage used in RULE and take it out of the
 398    pattern_rules chain.  LASTRULE is the rule whose next pointer
 399    points to RULE.  */
 400
 401 static void
 402 freerule (struct rule *rule, struct rule *lastrule)
 403 {
 404   struct rule *next = rule->next;
 405   struct dep *dep;
 406
 407   dep = rule->deps;
 408   while (dep)
 409     {
 410       struct dep *t = dep->next;
 411       free_dep (dep);
 412       dep = t;
 413     }
 414
 415   free (rule->targets);
 416   free (rule->suffixes);
 417   free (rule->lens);
 418
 419   /* We can't free the storage for the commands because there
 420      are ways that they could be in more than one place:
 421        * If the commands came from a suffix rule, they could also be in
 422        the `struct file's for other suffix rules or plain targets given
 423        on the same makefile line.
 424        * If two suffixes that together make a two-suffix rule were each
 425        given twice in the .SUFFIXES list, and in the proper order, two
 426        identical pattern rules would be created and the second one would
 427        be discarded here, but both would contain the same `struct commands'
 428        pointer from the `struct file' for the suffix rule.  */
 429
 430   free (rule);
 431
 432   if (pattern_rules == rule)
 433     if (lastrule != 0)
 434       abort ();
 435     else
 436       pattern_rules = next;
 437   else if (lastrule != 0)
 438     lastrule->next = next;
 439   if (last_pattern_rule == rule)
 440     last_pattern_rule = lastrule;
 441 }
 442 \f
 443 /* Create a new pattern rule with the targets in the nil-terminated array
 444    TARGETS.  TARGET_PERCENTS is an array of pointers to the % in each element
 445    of TARGETS.  N is the number of items in the array (not counting the nil
 446    element).  The new rule has dependencies DEPS and commands from COMMANDS.
 447    It is a terminal rule if TERMINAL is nonzero.  This rule overrides
 448    identical rules with different commands if OVERRIDE is nonzero.
 449
 450    The storage for TARGETS and its elements and TARGET_PERCENTS is used and
 451    must not be freed until the rule is destroyed.  */
 452
 453 void
 454 create_pattern_rule (const char **targets, const char **target_percents,
 455                      unsigned int n, int terminal, struct dep *deps,
 456                      struct commands *commands, int override)
 457 {
 458   unsigned int i;
 459   struct rule *r = xmalloc (sizeof (struct rule));
 460
 461   r->num = n;
 462   r->cmds = commands;
 463   r->deps = deps;
 464   r->targets = targets;
 465   r->suffixes = target_percents;
 466   r->lens = xmalloc (n * sizeof (unsigned int));
 467
 468   for (i = 0; i < n; ++i)
 469     {
 470       r->lens[i] = strlen (targets[i]);
 471       assert (r->suffixes[i] != NULL);
 472       ++r->suffixes[i];
 473     }
 474
 475   if (new_pattern_rule (r, override))
 476     r->terminal = terminal;
 477 }
 478 \f
 479 /* Print the data base of rules.  */
 480
 481 static void                     /* Useful to call from gdb.  */
 482 print_rule (struct rule *r)
 483 {
 484   unsigned int i;
 485   struct dep *d;
 486
 487   for (i = 0; i < r->num; ++i)
 488     {
 489       fputs (r->targets[i], stdout);
 490       putchar ((i + 1 == r->num) ? ':' : ' ');
 491     }
 492   if (r->terminal)
 493     putchar (':');
 494
 495   for (d = r->deps; d != 0; d = d->next)
 496     printf (" %s", dep_name (d));
 497   putchar ('\n');
 498
 499   if (r->cmds != 0)
 500     print_commands (r->cmds);
 501 }
 502
 503 void
 504 print_rule_data_base (void)
 505 {
 506   unsigned int rules, terminal;
 507   struct rule *r;
 508
 509   puts (_("\n# Implicit Rules"));
 510
 511   rules = terminal = 0;
 512   for (r = pattern_rules; r != 0; r = r->next)
 513     {
 514       ++rules;
 515
 516       putchar ('\n');
 517       print_rule (r);
 518
 519       if (r->terminal)
 520         ++terminal;
 521     }
 522
 523   if (rules == 0)
 524     puts (_("\n# No implicit rules."));
 525   else
 526     {
 527       printf (_("\n# %u implicit rules, %u"), rules, terminal);
 528 #ifndef NO_FLOAT
 529       printf (" (%.1f%%)", (double) terminal / (double) rules * 100.0);
 530 #else
 531       {
 532         int f = (terminal * 1000 + 5) / rules;
 533         printf (" (%d.%d%%)", f/10, f%10);
 534       }
 535 #endif
 536       puts (_(" terminal."));
 537     }
 538
 539   if (num_pattern_rules != rules)
 540     {
 541       /* This can happen if a fatal error was detected while reading the
 542          makefiles and thus count_implicit_rule_limits wasn't called yet.  */
 543       if (num_pattern_rules != 0)
 544         fatal (NILF, _("BUG: num_pattern_rules is wrong!  %u != %u"),
 545                num_pattern_rules, rules);
 546     }
 547 }