implicit.c

   1 /* Implicit rule searching for GNU Make.
   2 Copyright (C) 1988, 89, 90, 91, 92, 93, 94 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
   6 it under the terms of the GNU General Public License as published by
   7 the Free Software Foundation; either version 2, or (at your option)
   8 any later version.
   9
  10 GNU Make is distributed in the hope that it will be useful,
  11 but WITHOUT ANY WARRANTY; without even the implied warranty of
  12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13 GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License
  16 along with GNU Make; see the file COPYING.  If not, write to
  17 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  18
  19 #include "make.h"
  20 #include "rule.h"
  21 #include "dep.h"
  22 #include "file.h"
  23
  24 static int pattern_search ();
  25 \f
  26 /* For a FILE which has no commands specified, try to figure out some
  27    from the implicit pattern rules.
  28    Returns 1 if a suitable implicit rule was found,
  29    after modifying FILE to contain the appropriate commands and deps,
  30    or returns 0 if no implicit rule was found.  */
  31
  32 int
  33 try_implicit_rule (file, depth)
  34      struct file *file;
  35      unsigned int depth;
  36 {
  37   DEBUGPR ("Looking for an implicit rule for `%s'.\n");
  38
  39   /* The order of these searches was previously reversed.  My logic now is
  40      that since the non-archive search uses more information in the target
  41      (the archive search omits the archive name), it is more specific and
  42      should come first.  */
  43
  44   if (pattern_search (file, 0, depth, 0))
  45     return 1;
  46
  47 #ifndef NO_ARCHIVES
  48   /* If this is an archive member reference, use just the
  49      archive member name to search for implicit rules.  */
  50   if (ar_name (file->name))
  51     {
  52       DEBUGPR ("Looking for archive-member implicit rule for `%s'.\n");
  53       if (pattern_search (file, 1, depth, 0))
  54         return 1;
  55     }
  56 #endif
  57
  58   return 0;
  59 }
  60 \f
  61 #define DEBUGP2(msg, a1, a2)                                                  \
  62   do {                                                                        \
  63     if (debug_flag)                                                           \
  64       { print_spaces (depth); printf (msg, a1, a2); fflush (stdout); }        \
  65   } while (0)
  66
  67 /* Search the pattern rules for a rule with an existing dependency to make
  68    FILE.  If a rule is found, the appropriate commands and deps are put in FILE
  69    and 1 is returned.  If not, 0 is returned.
  70
  71    If ARCHIVE is nonzero, FILE->name is of the form "LIB(MEMBER)".  A rule for
  72    "(MEMBER)" will be searched for, and "(MEMBER)" will not be chopped up into
  73    directory and filename parts.
  74
  75    If an intermediate file is found by pattern search, the intermediate file
  76    is set up as a target by the recursive call and is also made a dependency
  77    of FILE.
  78
  79    DEPTH is used for debugging messages.  */
  80
  81 static int
  82 pattern_search (file, archive, depth, recursions)
  83      struct file *file;
  84      int archive;
  85      unsigned int depth;
  86      unsigned int recursions;
  87 {
  88   /* Filename we are searching for a rule for.  */
  89   char *filename = archive ? index (file->name, '(') : file->name;
  90
  91   /* Length of FILENAME.  */
  92   unsigned int namelen = strlen (filename);
  93
  94   /* The last slash in FILENAME (or nil if there is none).  */
  95   char *lastslash;
  96
  97   /* This is a file-object used as an argument in
  98      recursive calls.  It never contains any data
  99      except during a recursive call.  */
 100   struct file *intermediate_file = 0;
 101
 102   /* List of dependencies found recursively.  */
 103   struct file **intermediate_files
 104     = (struct file **) alloca (max_pattern_deps * sizeof (struct file *));
 105
 106   /* List of the patterns used to find intermediate files.  */
 107   char **intermediate_patterns
 108     = (char **) alloca (max_pattern_deps * sizeof (char *));
 109
 110   /* This buffer records all the dependencies actually found for a rule.  */
 111   char **found_files = (char **) alloca (max_pattern_deps * sizeof (char *));
 112   /* Number of dep names now in FOUND_FILES.  */
 113   unsigned int deps_found;
 114
 115   /* Names of possible dependencies are constructed in this buffer.  */
 116   register char *depname = (char *) alloca (namelen + max_pattern_dep_length);
 117
 118   /* The start and length of the stem of FILENAME for the current rule.  */
 119   register char *stem;
 120   register unsigned int stemlen;
 121
 122   /* Buffer in which we store all the rules that are possibly applicable.  */
 123   struct rule **tryrules
 124     = (struct rule **) alloca (num_pattern_rules * max_pattern_targets
 125                                * sizeof (struct rule *));
 126
 127   /* Number of valid elements in TRYRULES.  */
 128   unsigned int nrules;
 129
 130   /* The numbers of the rule targets of each rule
 131      in TRYRULES that matched the target file.  */
 132   unsigned int *matches
 133     = (unsigned int *) alloca (num_pattern_rules * sizeof (unsigned int));
 134
 135   /* Each element is nonzero if LASTSLASH was used in
 136      matching the corresponding element of TRYRULES.  */
 137   char *checked_lastslash
 138     = (char *) alloca (num_pattern_rules * sizeof (char));
 139
 140   /* The index in TRYRULES of the rule we found.  */
 141   unsigned int foundrule;
 142
 143   /* Nonzero if should consider intermediate files as dependencies.  */
 144   int intermed_ok;
 145
 146   /* Nonzero if we have matched a pattern-rule target
 147      that is not just `%'.  */
 148   int specific_rule_matched = 0;
 149
 150   register unsigned int i;
 151   register struct rule *rule;
 152   register struct dep *dep;
 153
 154   char *p;
 155
 156 #ifndef NO_ARCHIVES
 157   if (archive || ar_name (filename))
 158     lastslash = 0;
 159   else
 160 #endif
 161     {
 162       /* Set LASTSLASH to point at the last slash in FILENAME
 163          but not counting any slash at the end.  (foo/bar/ counts as
 164          bar/ in directory foo/, not empty in directory foo/bar/.)  */
 165       lastslash = rindex (filename, '/');
 166       if (lastslash != 0 && lastslash[1] == '\0')
 167         lastslash = 0;
 168     }
 169
 170   /* First see which pattern rules match this target
 171      and may be considered.  Put them in TRYRULES.  */
 172
 173   nrules = 0;
 174   for (rule = pattern_rules; rule != 0; rule = rule->next)
 175     {
 176       /* If the pattern rule has deps but no commands, ignore it.
 177          Users cancel built-in rules by redefining them without commands.  */
 178       if (rule->deps != 0 && rule->cmds == 0)
 179         continue;
 180
 181       /* If this rule is in use by a parent pattern_search,
 182          don't use it here.  */
 183       if (rule->in_use)
 184         {
 185           DEBUGP2 ("Avoiding implicit rule recursion.%s%s\n", "", "");
 186           continue;
 187         }
 188
 189       for (i = 0; rule->targets[i] != 0; ++i)
 190         {
 191           char *target = rule->targets[i];
 192           char *suffix = rule->suffixes[i];
 193           int check_lastslash;
 194
 195           /* Rules that can match any filename and are not terminal
 196              are ignored if we're recursing, so that they cannot be
 197              intermediate files.  */
 198           if (recursions > 0 && target[1] == '\0' && !rule->terminal)
 199             continue;
 200
 201           if (rule->lens[i] > namelen)
 202             /* It can't possibly match.  */
 203             continue;
 204
 205           /* From the lengths of the filename and the pattern parts,
 206              find the stem: the part of the filename that matches the %.  */
 207           stem = filename + (suffix - target - 1);
 208           stemlen = namelen - rule->lens[i] + 1;
 209
 210           /* Set CHECK_LASTSLASH if FILENAME contains a directory
 211              prefix and the target pattern does not contain a slash.  */
 212
 213           check_lastslash = lastslash != 0 && index (target, '/') == 0;
 214           if (check_lastslash)
 215             {
 216               /* In that case, don't include the
 217                  directory prefix in STEM here.  */
 218               unsigned int difference = lastslash - filename + 1;
 219               if (difference > stemlen)
 220                 continue;
 221               stemlen -= difference;
 222               stem += difference;
 223             }
 224
 225           /* Check that the rule pattern matches the text before the stem.  */
 226           if (check_lastslash)
 227             {
 228               if (stem > (lastslash + 1)
 229                   && strncmp (target, lastslash + 1, stem - lastslash - 1))
 230                 continue;
 231             }
 232           else if (stem > filename
 233                    && strncmp (target, filename, stem - filename))
 234             continue;
 235
 236           /* Check that the rule pattern matches the text after the stem.
 237              We could test simply use streq, but this way we compare the
 238              first two characters immediately.  This saves time in the very
 239              common case where the first character matches because it is a
 240              period.  */
 241           if (*suffix != stem[stemlen]
 242               || (*suffix != '\0' && !streq (&suffix[1], &stem[stemlen + 1])))
 243             continue;
 244
 245           /* Record if we match a rule that not all filenames will match.  */
 246           if (target[1] != '\0')
 247             specific_rule_matched = 1;
 248
 249           /* A rule with no dependencies and no commands exists solely to set
 250              specific_rule_matched when it matches.  Don't try to use it.  */
 251           if (rule->deps == 0 && rule->cmds == 0)
 252             continue;
 253
 254           /* Record this rule in TRYRULES and the index of the matching
 255              target in MATCHES.  If several targets of the same rule match,
 256              that rule will be in TRYRULES more than once.  */
 257           tryrules[nrules] = rule;
 258           matches[nrules] = i;
 259           checked_lastslash[nrules] = check_lastslash;
 260           ++nrules;
 261         }
 262     }
 263
 264   /* If we have found a matching rule that won't match all filenames,
 265      retroactively reject any non-"terminal" rules that do always match.  */
 266   if (specific_rule_matched)
 267     for (i = 0; i < nrules; ++i)
 268       if (!tryrules[i]->terminal)
 269         {
 270           register unsigned int j;
 271           for (j = 0; tryrules[i]->targets[j] != 0; ++j)
 272             if (tryrules[i]->targets[j][1] == '\0')
 273               break;
 274           if (tryrules[i]->targets[j] != 0)
 275             tryrules[i] = 0;
 276         }
 277
 278   /* Try each rule once without intermediate files, then once with them.  */
 279   for (intermed_ok = 0; intermed_ok == !!intermed_ok; ++intermed_ok)
 280     {
 281       /* Try each pattern rule till we find one that applies.
 282          If it does, copy the names of its dependencies (as substituted)
 283          and store them in FOUND_FILES.  DEPS_FOUND is the number of them.  */
 284
 285       for (i = 0; i < nrules; i++)
 286         {
 287           int check_lastslash;
 288
 289           rule = tryrules[i];
 290
 291           /* RULE is nil when we discover that a rule,
 292              already placed in TRYRULES, should not be applied.  */
 293           if (rule == 0)
 294             continue;
 295
 296           /* Reject any terminal rules if we're
 297              looking to make intermediate files.  */
 298           if (intermed_ok && rule->terminal)
 299             continue;
 300
 301           /* Mark this rule as in use so a recursive
 302              pattern_search won't try to use it.  */
 303           rule->in_use = 1;
 304
 305           /* From the lengths of the filename and the matching pattern parts,
 306              find the stem: the part of the filename that matches the %.  */
 307           stem = filename
 308             + (rule->suffixes[matches[i]] - rule->targets[matches[i]]) - 1;
 309           stemlen = namelen - rule->lens[matches[i]] + 1;
 310           check_lastslash = checked_lastslash[i];
 311           if (check_lastslash)
 312             {
 313               stem += lastslash - filename + 1;
 314               stemlen -= (lastslash - filename) + 1;
 315             }
 316
 317           DEBUGP2 ("Trying pattern rule with stem `%.*s'.\n",
 318                    (int) stemlen, stem);
 319
 320           /* Try each dependency; see if it "exists".  */
 321
 322           deps_found = 0;
 323           for (dep = rule->deps; dep != 0; dep = dep->next)
 324             {
 325               /* If the dependency name has a %, substitute the stem.  */
 326               p = index (dep_name (dep), '%');
 327               if (p != 0)
 328                 {
 329                   register unsigned int i;
 330                   if (check_lastslash)
 331                     {
 332                       /* Copy directory name from the original FILENAME.  */
 333                       i = lastslash - filename + 1;
 334                       bcopy (filename, depname, i);
 335                     }
 336                   else
 337                     i = 0;
 338                   bcopy (dep_name (dep), depname + i, p - dep_name (dep));
 339                   i += p - dep_name (dep);
 340                   bcopy (stem, depname + i, stemlen);
 341                   i += stemlen;
 342                   strcpy (depname + i, p + 1);
 343                   p = depname;
 344                 }
 345               else
 346                 p = dep_name (dep);
 347
 348               /* P is now the actual dependency name as substituted.  */
 349
 350               if (file_impossible_p (p))
 351                 {
 352                   /* If this dependency has already been ruled
 353                      "impossible", then the rule fails and don't
 354                      bother trying it on the second pass either
 355                      since we know that will fail too.  */
 356                   DEBUGP2 ("Rejecting impossible %s dependency `%s'.\n",
 357                            p == depname ? "implicit" : "rule", p);
 358                   tryrules[i] = 0;
 359                   break;
 360                 }
 361
 362               intermediate_files[deps_found] = 0;
 363
 364               DEBUGP2 ("Trying %s dependency `%s'.\n",
 365                        p == depname ? "implicit" : "rule", p);
 366
 367               /* The DEP->changed flag says that this dependency resides in a
 368                  nonexistent directory.  So we normally can skip looking for
 369                  the file.  However, if CHECK_LASTSLASH is set, then the
 370                  dependency file we are actually looking for is in a different
 371                  directory (the one gotten by prepending FILENAME's directory),
 372                  so it might actually exist.  */
 373
 374               if ((!dep->changed || check_lastslash)
 375                   && (lookup_file (p) != 0 || file_exists_p (p)))
 376                 {
 377                   found_files[deps_found++] = savestring (p, strlen (p));
 378                   continue;
 379                 }
 380               /* This code, given FILENAME = "lib/foo.o", dependency name
 381                  "lib/foo.c", and VPATH=src, searches for "src/lib/foo.c".  */
 382               if (vpath_search (&p, (time_t *) 0))
 383                 {
 384                   DEBUGP2 ("Found dependency as `%s'.%s\n", p, "");
 385                   found_files[deps_found++] = p;
 386                   continue;
 387                 }
 388
 389               /* We could not find the file in any place we should look.
 390                  Try to make this dependency as an intermediate file,
 391                  but only on the second pass.  */
 392
 393               if (intermed_ok)
 394                 {
 395                   if (intermediate_file == 0)
 396                     intermediate_file
 397                       = (struct file *) alloca (sizeof (struct file));
 398
 399                   DEBUGP2 ("Looking for a rule with %s file `%s'.\n",
 400                            "intermediate", p);
 401
 402                   bzero ((char *) intermediate_file, sizeof (struct file));
 403                   intermediate_file->name = p;
 404                   if (pattern_search (intermediate_file, 0, depth + 1,
 405                                       recursions + 1))
 406                     {
 407                       p = savestring (p, strlen (p));
 408                       intermediate_patterns[deps_found]
 409                         = intermediate_file->name;
 410                       intermediate_file->name = p;
 411                       intermediate_files[deps_found] = intermediate_file;
 412                       intermediate_file = 0;
 413                       /* Allocate an extra copy to go in FOUND_FILES,
 414                          because every elt of FOUND_FILES is consumed
 415                          or freed later.  */
 416                       found_files[deps_found] = savestring (p, strlen (p));
 417                       ++deps_found;
 418                       continue;
 419                     }
 420
 421                   /* If we have tried to find P as an intermediate
 422                      file and failed, mark that name as impossible
 423                      so we won't go through the search again later.  */
 424                   file_impossible (p);
 425                 }
 426
 427               /* A dependency of this rule does not exist.
 428                  Therefore, this rule fails.  */
 429               break;
 430             }
 431
 432           /* This rule is no longer `in use' for recursive searches.  */
 433           rule->in_use = 0;
 434
 435           if (dep != 0)
 436             {
 437               /* This pattern rule does not apply.
 438                  If some of its dependencies succeeded,
 439                  free the data structure describing them.  */
 440               while (deps_found-- > 0)
 441                 {
 442                   register struct file *f = intermediate_files[deps_found];
 443                   free (found_files[deps_found]);
 444                   if (f != 0
 445                       && (f->stem < f->name
 446                           || f->stem > f->name + strlen (f->name)))
 447                     free (f->stem);
 448                 }
 449             }
 450           else
 451             /* This pattern rule does apply.  Stop looking for one.  */
 452             break;
 453         }
 454
 455       /* If we found an applicable rule without
 456          intermediate files, don't try with them.  */
 457       if (i < nrules)
 458         break;
 459
 460       rule = 0;
 461     }
 462
 463   /* RULE is nil if the loop went all the way
 464      through the list and everything failed.  */
 465   if (rule == 0)
 466     return 0;
 467
 468   foundrule = i;
 469
 470   /* If we are recursing, store the pattern that matched
 471      FILENAME in FILE->name for use in upper levels.  */
 472
 473   if (recursions > 0)
 474     /* Kludge-o-matic */
 475     file->name = rule->targets[matches[foundrule]];
 476
 477   /* FOUND_FILES lists the dependencies for the rule we found.
 478      This includes the intermediate files, if any.
 479      Convert them into entries on the deps-chain of FILE.  */
 480
 481   while (deps_found-- > 0)
 482     {
 483       register char *s;
 484
 485       if (intermediate_files[deps_found] != 0)
 486         {
 487           /* If we need to use an intermediate file,
 488              make sure it is entered as a target, with the info that was
 489              found for it in the recursive pattern_search call.
 490              We know that the intermediate file did not already exist as
 491              a target; therefore we can assume that the deps and cmds
 492              of F below are null before we change them.  */
 493
 494           struct file *imf = intermediate_files[deps_found];
 495           register struct file *f = enter_file (imf->name);
 496           f->deps = imf->deps;
 497           f->cmds = imf->cmds;
 498           f->stem = imf->stem;
 499           imf = lookup_file (intermediate_patterns[deps_found]);
 500           if (imf != 0 && imf->precious)
 501             f->precious = 1;
 502           f->intermediate = 1;
 503           f->tried_implicit = 1;
 504           for (dep = f->deps; dep != 0; dep = dep->next)
 505             {
 506               dep->file = enter_file (dep->name);
 507               dep->name = 0;
 508               dep->file->tried_implicit |= dep->changed;
 509             }
 510           num_intermediates++;
 511         }
 512
 513       dep = (struct dep *) xmalloc (sizeof (struct dep));
 514       s = found_files[deps_found];
 515       if (recursions == 0)
 516         {
 517           dep->name = 0;
 518           dep->file = lookup_file (s);
 519           if (dep->file == 0)
 520             /* enter_file consumes S's storage.  */
 521             dep->file = enter_file (s);
 522           else
 523             /* A copy of S is already allocated in DEP->file->name.
 524                So we can free S.  */
 525             free (s);
 526         }
 527       else
 528         {
 529           dep->name = s;
 530           dep->file = 0;
 531           dep->changed = 0;
 532         }
 533       if (intermediate_files[deps_found] == 0 && tryrules[foundrule]->terminal)
 534         {
 535           /* If the file actually existed (was not an intermediate file),
 536              and the rule that found it was a terminal one, then we want
 537              to mark the found file so that it will not have implicit rule
 538              search done for it.  If we are not entering a `struct file' for
 539              it now, we indicate this with the `changed' flag.  */
 540           if (dep->file == 0)
 541             dep->changed = 1;
 542           else
 543             dep->file->tried_implicit = 1;
 544         }
 545       dep->next = file->deps;
 546       file->deps = dep;
 547     }
 548
 549   if (!checked_lastslash[foundrule])
 550     /* Always allocate new storage, since STEM might be
 551        on the stack for an intermediate file.  */
 552     file->stem = savestring (stem, stemlen);
 553   else
 554     {
 555       /* We want to prepend the directory from
 556          the original FILENAME onto the stem.  */
 557       file->stem = (char *) xmalloc (((lastslash + 1) - filename)
 558                                      + stemlen + 1);
 559       bcopy (filename, file->stem, (lastslash + 1) - filename);
 560       bcopy (stem, file->stem + ((lastslash + 1) - filename), stemlen);
 561       file->stem[((lastslash + 1) - filename) + stemlen] = '\0';
 562     }
 563
 564   file->cmds = rule->cmds;
 565
 566   /* Put the targets other than the one that
 567      matched into FILE's `also_make' member.  */
 568
 569   /* If there was only one target, there is nothing to do.  */
 570   if (rule->targets[1] != 0)
 571     for (i = 0; rule->targets[i] != 0; ++i)
 572       if (i != matches[foundrule])
 573         {
 574           struct dep *new = (struct dep *) xmalloc (sizeof (struct dep));
 575           new->name = p = (char *) xmalloc (rule->lens[i] + stemlen + 1);
 576           bcopy (rule->targets[i], p,
 577                  rule->suffixes[i] - rule->targets[i] - 1);
 578           p += rule->suffixes[i] - rule->targets[i] - 1;
 579           bcopy (stem, p, stemlen);
 580           p += stemlen;
 581           bcopy (rule->suffixes[i], p,
 582                  rule->lens[i] - (rule->suffixes[i] - rule->targets[i]) + 1);
 583           new->file = enter_file (new->name);
 584           new->next = file->also_make;
 585           file->also_make = new;
 586         }
 587
 588
 589   return 1;
 590 }