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 *) parse_file_seq (&ptr, sizeof (struct dep), '\0',
 380                                            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   struct dep *dep;
 405
 406   dep = rule->deps;
 407   while (dep)
 408     {
 409       struct dep *t = dep->next;
 410       free_dep (dep);
 411       dep = t;
 412     }
 413
 414   free (rule->targets);
 415   free (rule->suffixes);
 416   free (rule->lens);
 417
 418   /* We can't free the storage for the commands because there
 419      are ways that they could be in more than one place:
 420        * If the commands came from a suffix rule, they could also be in
 421        the `struct file's for other suffix rules or plain targets given
 422        on the same makefile line.
 423        * If two suffixes that together make a two-suffix rule were each
 424        given twice in the .SUFFIXES list, and in the proper order, two
 425        identical pattern rules would be created and the second one would
 426        be discarded here, but both would contain the same `struct commands'
 427        pointer from the `struct file' for the suffix rule.  */
 428
 429   free (rule);
 430
 431   if (pattern_rules == rule)
 432     if (lastrule != 0)
 433       abort ();
 434     else
 435       pattern_rules = next;
 436   else if (lastrule != 0)
 437     lastrule->next = next;
 438   if (last_pattern_rule == rule)
 439     last_pattern_rule = lastrule;
 440 }
 441 \f
 442 /* Create a new pattern rule with the targets in the nil-terminated array
 443    TARGETS.  TARGET_PERCENTS is an array of pointers to the % in each element
 444    of TARGETS.  N is the number of items in the array (not counting the nil
 445    element).  The new rule has dependencies DEPS and commands from COMMANDS.
 446    It is a terminal rule if TERMINAL is nonzero.  This rule overrides
 447    identical rules with different commands if OVERRIDE is nonzero.
 448
 449    The storage for TARGETS and its elements and TARGET_PERCENTS is used and
 450    must not be freed until the rule is destroyed.  */
 451
 452 void
 453 create_pattern_rule (const char **targets, const char **target_percents,
 454                      unsigned int n, int terminal, struct dep *deps,
 455                      struct commands *commands, int override)
 456 {
 457   unsigned int i;
 458   struct rule *r = xmalloc (sizeof (struct rule));
 459
 460   r->num = n;
 461   r->cmds = commands;
 462   r->deps = deps;
 463   r->targets = targets;
 464   r->suffixes = target_percents;
 465   r->lens = xmalloc (n * sizeof (unsigned int));
 466
 467   for (i = 0; i < n; ++i)
 468     {
 469       r->lens[i] = strlen (targets[i]);
 470       assert (r->suffixes[i] != NULL);
 471       ++r->suffixes[i];
 472     }
 473
 474   if (new_pattern_rule (r, override))
 475     r->terminal = terminal;
 476 }
 477 \f
 478 /* Print the data base of rules.  */
 479
 480 static void                     /* Useful to call from gdb.  */
 481 print_rule (struct rule *r)
 482 {
 483   unsigned int i;
 484   struct dep *d;
 485
 486   for (i = 0; i < r->num; ++i)
 487     {
 488       fputs (r->targets[i], stdout);
 489       putchar ((i + 1 == r->num) ? ':' : ' ');
 490     }
 491   if (r->terminal)
 492     putchar (':');
 493
 494   for (d = r->deps; d != 0; d = d->next)
 495     printf (" %s", dep_name (d));
 496   putchar ('\n');
 497
 498   if (r->cmds != 0)
 499     print_commands (r->cmds);
 500 }
 501
 502 void
 503 print_rule_data_base (void)
 504 {
 505   unsigned int rules, terminal;
 506   struct rule *r;
 507
 508   puts (_("\n# Implicit Rules"));
 509
 510   rules = terminal = 0;
 511   for (r = pattern_rules; r != 0; r = r->next)
 512     {
 513       ++rules;
 514
 515       putchar ('\n');
 516       print_rule (r);
 517
 518       if (r->terminal)
 519         ++terminal;
 520     }
 521
 522   if (rules == 0)
 523     puts (_("\n# No implicit rules."));
 524   else
 525     {
 526       printf (_("\n# %u implicit rules, %u"), rules, terminal);
 527 #ifndef NO_FLOAT
 528       printf (" (%.1f%%)", (double) terminal / (double) rules * 100.0);
 529 #else
 530       {
 531         int f = (terminal * 1000 + 5) / rules;
 532         printf (" (%d.%d%%)", f/10, f%10);
 533       }
 534 #endif
 535       puts (_(" terminal."));
 536     }
 537
 538   if (num_pattern_rules != rules)
 539     {
 540       /* This can happen if a fatal error was detected while reading the
 541          makefiles and thus count_implicit_rule_limits wasn't called yet.  */
 542       if (num_pattern_rules != 0)
 543         fatal (NILF, _("BUG: num_pattern_rules is wrong!  %u != %u"),
 544                num_pattern_rules, rules);
 545     }
 546 }