implicit.c

   1 /* Implicit rule searching 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,
   4 2010 Free 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 #include "filedef.h"
  21 #include "rule.h"
  22 #include "dep.h"
  23 #include "debug.h"
  24 #include "variable.h"
  25 #include "job.h"      /* struct child, used inside commands.h */
  26 #include "commands.h" /* set_file_variables */
  27
  28 static int pattern_search (struct file *file, int archive,
  29                            unsigned int depth, unsigned int recursions);
  30 \f
  31 /* For a FILE which has no commands specified, try to figure out some
  32    from the implicit pattern rules.
  33    Returns 1 if a suitable implicit rule was found,
  34    after modifying FILE to contain the appropriate commands and deps,
  35    or returns 0 if no implicit rule was found.  */
  36
  37 int
  38 try_implicit_rule (struct file *file, unsigned int depth)
  39 {
  40   DBF (DB_IMPLICIT, _("Looking for an implicit rule for `%s'.\n"));
  41
  42   /* The order of these searches was previously reversed.  My logic now is
  43      that since the non-archive search uses more information in the target
  44      (the archive search omits the archive name), it is more specific and
  45      should come first.  */
  46
  47   if (pattern_search (file, 0, depth, 0))
  48     return 1;
  49
  50 #ifndef NO_ARCHIVES
  51   /* If this is an archive member reference, use just the
  52      archive member name to search for implicit rules.  */
  53   if (ar_name (file->name))
  54     {
  55       DBF (DB_IMPLICIT,
  56            _("Looking for archive-member implicit rule for `%s'.\n"));
  57       if (pattern_search (file, 1, depth, 0))
  58         return 1;
  59     }
  60 #endif
  61
  62   return 0;
  63 }
  64 \f
  65
  66 /* Scans the BUFFER for the next word with whitespace as a separator.
  67    Returns the pointer to the beginning of the word. LENGTH hold the
  68    length of the word.  */
  69
  70 static const char *
  71 get_next_word (const char *buffer, unsigned int *length)
  72 {
  73   const char *p = buffer, *beg;
  74   char c;
  75
  76   /* Skip any leading whitespace.  */
  77   while (isblank ((unsigned char)*p))
  78     ++p;
  79
  80   beg = p;
  81   c = *(p++);
  82
  83   if (c == '\0')
  84     return 0;
  85
  86
  87   /* We already found the first value of "c", above.  */
  88   while (1)
  89     {
  90       char closeparen;
  91       int count;
  92
  93       switch (c)
  94         {
  95         case '\0':
  96         case ' ':
  97         case '\t':
  98           goto done_word;
  99
 100         case '$':
 101           c = *(p++);
 102           if (c == '$')
 103             break;
 104
 105           /* This is a variable reference, so read it to the matching
 106              close paren.  */
 107
 108           if (c == '(')
 109             closeparen = ')';
 110           else if (c == '{')
 111             closeparen = '}';
 112           else
 113             /* This is a single-letter variable reference.  */
 114             break;
 115
 116           for (count = 0; *p != '\0'; ++p)
 117             {
 118               if (*p == c)
 119                 ++count;
 120               else if (*p == closeparen && --count < 0)
 121                 {
 122                   ++p;
 123                   break;
 124                 }
 125             }
 126           break;
 127
 128         case '|':
 129           goto done;
 130
 131         default:
 132           break;
 133         }
 134
 135       c = *(p++);
 136     }
 137  done_word:
 138   --p;
 139
 140  done:
 141   if (length)
 142     *length = p - beg;
 143
 144   return beg;
 145 }
 146
 147 /* This structure stores information about the expanded prerequisites for a
 148    pattern rule.  NAME is always set to the strcache'd name of the prereq.
 149    FILE and PATTERN will be set for intermediate files only.  IGNORE_MTIME is
 150    copied from the prerequisite we expanded.
 151  */
 152 struct patdeps
 153   {
 154     const char *name;
 155     const char *pattern;
 156     struct file *file;
 157     unsigned int ignore_mtime : 1;
 158   };
 159
 160 /* This structure stores information about pattern rules that we need
 161    to try.
 162 */
 163 struct tryrule
 164   {
 165     struct rule *rule;
 166
 167     /* Index of the target in this rule that matched the file. */
 168     unsigned int matches;
 169
 170     /* Stem length for this match. */
 171     unsigned int stemlen;
 172
 173     /* Definition order of this rule. Used to implement stable sort.*/
 174     unsigned int order;
 175
 176     /* Nonzero if the LASTSLASH logic was used in matching this rule. */
 177     char checked_lastslash;
 178   };
 179
 180 int
 181 stemlen_compare (const void *v1, const void *v2)
 182 {
 183   const struct tryrule *r1 = v1;
 184   const struct tryrule *r2 = v2;
 185   int r = r1->stemlen - r2->stemlen;
 186   return r != 0 ? r : (int)(r1->order - r2->order);
 187 }
 188
 189 /* Search the pattern rules for a rule with an existing dependency to make
 190    FILE.  If a rule is found, the appropriate commands and deps are put in FILE
 191    and 1 is returned.  If not, 0 is returned.
 192
 193    If ARCHIVE is nonzero, FILE->name is of the form "LIB(MEMBER)".  A rule for
 194    "(MEMBER)" will be searched for, and "(MEMBER)" will not be chopped up into
 195    directory and filename parts.
 196
 197    If an intermediate file is found by pattern search, the intermediate file
 198    is set up as a target by the recursive call and is also made a dependency
 199    of FILE.
 200
 201    DEPTH is used for debugging messages.  */
 202
 203 static int
 204 pattern_search (struct file *file, int archive,
 205                 unsigned int depth, unsigned int recursions)
 206 {
 207   /* Filename we are searching for a rule for.  */
 208   const char *filename = archive ? strchr (file->name, '(') : file->name;
 209
 210   /* Length of FILENAME.  */
 211   unsigned int namelen = strlen (filename);
 212
 213   /* The last slash in FILENAME (or nil if there is none).  */
 214   const char *lastslash;
 215
 216   /* This is a file-object used as an argument in
 217      recursive calls.  It never contains any data
 218      except during a recursive call.  */
 219   struct file *int_file = 0;
 220
 221   /* List of dependencies found recursively.  */
 222   struct patdeps *deplist
 223     = xmalloc (max_pattern_deps * sizeof (struct patdeps));
 224   struct patdeps *pat = deplist;
 225
 226   /* All the prerequisites actually found for a rule, after expansion.  */
 227   struct dep *deps;
 228
 229   /* Names of possible dependencies are constructed in this buffer.  */
 230   char *depname = alloca (namelen + max_pattern_dep_length);
 231
 232   /* The start and length of the stem of FILENAME for the current rule.  */
 233   const char *stem = 0;
 234   unsigned int stemlen = 0;
 235   unsigned int fullstemlen = 0;
 236
 237   /* Buffer in which we store all the rules that are possibly applicable.  */
 238   struct tryrule *tryrules = xmalloc (num_pattern_rules * max_pattern_targets
 239                                       * sizeof (struct tryrule));
 240
 241   /* Number of valid elements in TRYRULES.  */
 242   unsigned int nrules;
 243
 244   /* The index in TRYRULES of the rule we found.  */
 245   unsigned int foundrule;
 246
 247   /* Nonzero if should consider intermediate files as dependencies.  */
 248   int intermed_ok;
 249
 250   /* Nonzero if we have initialized file variables for this target.  */
 251   int file_vars_initialized = 0;
 252
 253   /* Nonzero if we have matched a pattern-rule target
 254      that is not just `%'.  */
 255   int specific_rule_matched = 0;
 256
 257   struct dep dep_simple;
 258
 259   unsigned int ri;  /* uninit checks OK */
 260   struct rule *rule;
 261
 262   char *pathdir = NULL;
 263   unsigned long pathlen;
 264
 265   PATH_VAR (stem_str); /* @@ Need to get rid of stem, stemlen, etc. */
 266
 267 #ifndef NO_ARCHIVES
 268   if (archive || ar_name (filename))
 269     lastslash = 0;
 270   else
 271 #endif
 272     {
 273       /* Set LASTSLASH to point at the last slash in FILENAME
 274          but not counting any slash at the end.  (foo/bar/ counts as
 275          bar/ in directory foo/, not empty in directory foo/bar/.)  */
 276 #ifdef VMS
 277       lastslash = strrchr (filename, ']');
 278       if (lastslash == 0)
 279         lastslash = strrchr (filename, ':');
 280 #else
 281       lastslash = strrchr (filename, '/');
 282 #ifdef HAVE_DOS_PATHS
 283       /* Handle backslashes (possibly mixed with forward slashes)
 284          and the case of "d:file".  */
 285       {
 286         char *bslash = strrchr (filename, '\\');
 287         if (lastslash == 0 || bslash > lastslash)
 288           lastslash = bslash;
 289         if (lastslash == 0 && filename[0] && filename[1] == ':')
 290           lastslash = filename + 1;
 291       }
 292 #endif
 293 #endif
 294       if (lastslash != 0 && lastslash[1] == '\0')
 295         lastslash = 0;
 296     }
 297
 298   pathlen = lastslash - filename + 1;
 299
 300   /* First see which pattern rules match this target and may be considered.
 301      Put them in TRYRULES.  */
 302
 303   nrules = 0;
 304   for (rule = pattern_rules; rule != 0; rule = rule->next)
 305     {
 306       unsigned int ti;
 307
 308       /* If the pattern rule has deps but no commands, ignore it.
 309          Users cancel built-in rules by redefining them without commands.  */
 310       if (rule->deps != 0 && rule->cmds == 0)
 311         continue;
 312
 313       /* If this rule is in use by a parent pattern_search,
 314          don't use it here.  */
 315       if (rule->in_use)
 316         {
 317           DBS (DB_IMPLICIT, (_("Avoiding implicit rule recursion.\n")));
 318           continue;
 319         }
 320
 321       for (ti = 0; ti < rule->num; ++ti)
 322         {
 323           const char *target = rule->targets[ti];
 324           const char *suffix = rule->suffixes[ti];
 325           int check_lastslash;
 326
 327           /* Rules that can match any filename and are not terminal
 328              are ignored if we're recursing, so that they cannot be
 329              intermediate files.  */
 330           if (recursions > 0 && target[1] == '\0' && !rule->terminal)
 331             continue;
 332
 333           if (rule->lens[ti] > namelen)
 334             /* It can't possibly match.  */
 335             continue;
 336
 337           /* From the lengths of the filename and the pattern parts,
 338              find the stem: the part of the filename that matches the %.  */
 339           stem = filename + (suffix - target - 1);
 340           stemlen = namelen - rule->lens[ti] + 1;
 341
 342           /* Set CHECK_LASTSLASH if FILENAME contains a directory
 343              prefix and the target pattern does not contain a slash.  */
 344
 345           check_lastslash = 0;
 346           if (lastslash)
 347             {
 348 #ifdef VMS
 349               check_lastslash = (strchr (target, ']') == 0
 350                                  && strchr (target, ':') == 0);
 351 #else
 352               check_lastslash = strchr (target, '/') == 0;
 353 #ifdef HAVE_DOS_PATHS
 354               /* Didn't find it yet: check for DOS-type directories.  */
 355               if (check_lastslash)
 356                 {
 357                   char *b = strchr (target, '\\');
 358                   check_lastslash = !(b || (target[0] && target[1] == ':'));
 359                 }
 360 #endif
 361 #endif
 362             }
 363           if (check_lastslash)
 364             {
 365               /* If so, don't include the directory prefix in STEM here.  */
 366               if (pathlen > stemlen)
 367                 continue;
 368               stemlen -= pathlen;
 369               stem += pathlen;
 370             }
 371
 372           /* Check that the rule pattern matches the text before the stem.  */
 373           if (check_lastslash)
 374             {
 375               if (stem > (lastslash + 1)
 376                   && !strneq (target, lastslash + 1, stem - lastslash - 1))
 377                 continue;
 378             }
 379           else if (stem > filename
 380                    && !strneq (target, filename, stem - filename))
 381             continue;
 382
 383           /* Check that the rule pattern matches the text after the stem.
 384              We could test simply use streq, but this way we compare the
 385              first two characters immediately.  This saves time in the very
 386              common case where the first character matches because it is a
 387              period.  */
 388           if (*suffix != stem[stemlen]
 389               || (*suffix != '\0' && !streq (&suffix[1], &stem[stemlen + 1])))
 390             continue;
 391
 392           /* Record if we match a rule that not all filenames will match.  */
 393           if (target[1] != '\0')
 394             specific_rule_matched = 1;
 395
 396           /* A rule with no dependencies and no commands exists solely to set
 397              specific_rule_matched when it matches.  Don't try to use it.  */
 398           if (rule->deps == 0 && rule->cmds == 0)
 399             continue;
 400
 401           /* Record this rule in TRYRULES and the index of the matching
 402              target in MATCHES.  If several targets of the same rule match,
 403              that rule will be in TRYRULES more than once.  */
 404           tryrules[nrules].rule = rule;
 405           tryrules[nrules].matches = ti;
 406           tryrules[nrules].stemlen = stemlen + (check_lastslash ? pathlen : 0);
 407           tryrules[nrules].order = nrules;
 408           tryrules[nrules].checked_lastslash = check_lastslash;
 409           ++nrules;
 410         }
 411     }
 412
 413   /* Bail out early if we haven't found any rules. */
 414   if (nrules == 0)
 415     goto done;
 416
 417   /* Sort the rules to place matches with the shortest stem first. This
 418      way the most specific rules will be tried first. */
 419   if (nrules > 1)
 420     qsort (tryrules, nrules, sizeof (struct tryrule), stemlen_compare);
 421
 422   /* If we have found a matching rule that won't match all filenames,
 423      retroactively reject any non-"terminal" rules that do always match.  */
 424   if (specific_rule_matched)
 425     for (ri = 0; ri < nrules; ++ri)
 426       if (!tryrules[ri].rule->terminal)
 427         {
 428           unsigned int j;
 429           for (j = 0; j < tryrules[ri].rule->num; ++j)
 430             if (tryrules[ri].rule->targets[j][1] == '\0')
 431               {
 432                 tryrules[ri].rule = 0;
 433                 break;
 434               }
 435         }
 436
 437   /* Try each rule once without intermediate files, then once with them.  */
 438   for (intermed_ok = 0; intermed_ok < 2; ++intermed_ok)
 439     {
 440       pat = deplist;
 441
 442       /* Try each pattern rule till we find one that applies.  If it does,
 443          expand its dependencies (as substituted) and chain them in DEPS.  */
 444       for (ri = 0; ri < nrules; ri++)
 445         {
 446           struct dep *dep;
 447           int check_lastslash;
 448           unsigned int failed = 0;
 449           int file_variables_set = 0;
 450           unsigned int deps_found = 0;
 451           /* NPTR points to the part of the prereq we haven't processed.  */
 452           const char *nptr = 0;
 453           const char *dir = NULL;
 454           int order_only = 0;
 455           unsigned int matches;
 456
 457           rule = tryrules[ri].rule;
 458
 459           /* RULE is nil when we discover that a rule, already placed in
 460              TRYRULES, should not be applied.  */
 461           if (rule == 0)
 462             continue;
 463
 464           /* Reject any terminal rules if we're looking to make intermediate
 465              files.  */
 466           if (intermed_ok && rule->terminal)
 467             continue;
 468
 469           /* From the lengths of the filename and the matching pattern parts,
 470              find the stem: the part of the filename that matches the %.  */
 471           matches = tryrules[ri].matches;
 472           stem = filename + (rule->suffixes[matches]
 473                              - rule->targets[matches]) - 1;
 474           stemlen = (namelen - rule->lens[matches]) + 1;
 475           check_lastslash = tryrules[ri].checked_lastslash;
 476           if (check_lastslash)
 477             {
 478               stem += pathlen;
 479               stemlen -= pathlen;
 480
 481               /* We need to add the directory prefix, so set it up.  */
 482               if (! pathdir)
 483                 {
 484                   pathdir = alloca (pathlen + 1);
 485                   memcpy (pathdir, filename, pathlen);
 486                   pathdir[pathlen] = '\0';
 487                 }
 488               dir = pathdir;
 489             }
 490
 491           DBS (DB_IMPLICIT, (_("Trying pattern rule with stem `%.*s'.\n"),
 492                              (int) stemlen, stem));
 493
 494           strncpy (stem_str, stem, stemlen);
 495           stem_str[stemlen] = '\0';
 496
 497           /* If there are no prerequisites, then this rule matches.  */
 498           if (rule->deps == 0)
 499             break;
 500
 501           /* Temporary assign STEM to file->stem (needed to set file
 502              variables below).   */
 503           file->stem = stem_str;
 504
 505           /* Mark this rule as in use so a recursive pattern_search won't try
 506              to use it.  */
 507           rule->in_use = 1;
 508
 509           /* Try each prerequisite; see if it exists or can be created.  We'll
 510              build a list of prereq info in DEPLIST.  Due to 2nd expansion we
 511              may have to process multiple prereqs for a single dep entry.  */
 512
 513           pat = deplist;
 514           dep = rule->deps;
 515           nptr = dep_name (dep);
 516           while (1)
 517             {
 518               struct dep *dl, *d;
 519               char *p;
 520
 521               /* If we're out of name to parse, start the next prereq.  */
 522               if (! nptr)
 523                 {
 524                   dep = dep->next;
 525                   if (dep == 0)
 526                     break;
 527                   nptr = dep_name (dep);
 528                 }
 529
 530               /* If we don't need a second expansion, just replace the %.  */
 531               if (! dep->need_2nd_expansion)
 532                 {
 533                   dep_simple = *dep;
 534                   dep_simple.next = 0;
 535                   p = strchr (nptr, '%');
 536                   if (p == 0)
 537                     dep_simple.name = nptr;
 538                   else
 539                     {
 540                       char *o = depname;
 541                       if (check_lastslash)
 542                         {
 543                           memcpy (o, filename, pathlen);
 544                           o += pathlen;
 545                         }
 546                       memcpy (o, nptr, p - nptr);
 547                       o += p - nptr;
 548                       memcpy (o, stem_str, stemlen);
 549                       o += stemlen;
 550                       strcpy (o, p + 1);
 551                       dep_simple.name = strcache_add (depname);
 552                     }
 553                   dl = &dep_simple;
 554
 555                   /* We've used up this dep, so next time get a new one.  */
 556                   nptr = 0;
 557                   ++deps_found;
 558                 }
 559
 560               /* We have to perform second expansion on this prereq.  In an
 561                  ideal world we would take the dependency line, substitute the
 562                  stem, re-expand the whole line and chop it into individual
 563                  prerequisites.  Unfortunately this won't work because of the
 564                  "check_lastslash" twist.  Instead, we will have to go word by
 565                  word, taking $()'s into account.  For each word we will
 566                  substitute the stem, re-expand, chop it up, and, if
 567                  check_lastslash != 0, add the directory part to each
 568                  resulting prerequisite.  */
 569               else
 570                 {
 571                   int add_dir = 0;
 572                   unsigned int len;
 573
 574                   nptr = get_next_word (nptr, &len);
 575                   if (nptr == 0)
 576                     continue;
 577
 578                   /* See this is a transition to order-only prereqs.  */
 579                   if (! order_only && len == 1 && nptr[0] == '|')
 580                     {
 581                       order_only = 1;
 582                       nptr += len;
 583                       continue;
 584                     }
 585
 586                   /* If the dependency name has %, substitute the stem.  If we
 587                      just replace % with the stem value then later, when we do
 588                      the 2nd expansion, we will re-expand this stem value
 589                      again.  This is not good if you have certain characters
 590                      in your stem (like $).
 591
 592                      Instead, we will replace % with $* and allow the second
 593                      expansion to take care of it for us.  This way (since $*
 594                      is a simple variable) there won't be additional
 595                      re-expansion of the stem.  */
 596
 597                   p = lindex (nptr, nptr + len, '%');
 598                   if (p == 0)
 599                     {
 600                       memcpy (depname, nptr, len);
 601                       depname[len] = '\0';
 602                     }
 603                   else
 604                     {
 605                       unsigned int i = p - nptr;
 606                       memcpy (depname, nptr, i);
 607                       memcpy (depname + i, "$*", 2);
 608                       memcpy (depname + i + 2, p + 1, len - i - 1);
 609                       depname[len + 2 - 1] = '\0';
 610
 611                       if (check_lastslash)
 612                         add_dir = 1;
 613                     }
 614
 615                   /* Initialize and set file variables if we haven't already
 616                      done so. */
 617                   if (!file_vars_initialized)
 618                     {
 619                       initialize_file_variables (file, 0);
 620                       set_file_variables (file);
 621                       file_vars_initialized = 1;
 622                     }
 623                   /* Update the stem value in $* for this rule.  */
 624                   else if (!file_variables_set)
 625                     {
 626                       define_variable_for_file (
 627                         "*", 1, file->stem, o_automatic, 0, file);
 628                       file_variables_set = 1;
 629                     }
 630
 631                   /* Perform the 2nd expansion.  */
 632                   p = variable_expand_for_file (depname, file);
 633
 634                   /* Parse the expanded string. */
 635                   dl = PARSE_FILE_SEQ (&p, struct dep, order_only ? '\0' : '|',
 636                                        add_dir ? dir : NULL, 0);
 637
 638                   for (d = dl; d != NULL; d = d->next)
 639                     {
 640                       ++deps_found;
 641                       if (order_only)
 642                         d->ignore_mtime = 1;
 643                     }
 644
 645                   /* Set up for the next word.  */
 646                   nptr += len;
 647                 }
 648
 649               /* If there are more than max_pattern_deps prerequisites (due to
 650                  2nd expansion), reset it and realloc the arrays.  */
 651
 652               if (deps_found > max_pattern_deps)
 653                 {
 654                   unsigned int l = pat - deplist;
 655                   deplist = xrealloc (deplist,
 656                                       deps_found * sizeof (struct patdeps));
 657                   pat = deplist + l;
 658                   max_pattern_deps = deps_found;
 659                 }
 660
 661               /* Go through the nameseq and handle each as a prereq name.  */
 662               for (d = dl; d != 0; d = d->next)
 663                 {
 664                   struct dep *expl_d;
 665                   int is_rule = d->name == dep_name (dep);
 666
 667                   if (file_impossible_p (d->name))
 668                     {
 669                       /* If this prereq has already been ruled "impossible",
 670                          then the rule fails.  Don't bother trying it on the
 671                          second pass either since we know that will fail.  */
 672                       DBS (DB_IMPLICIT,
 673                            (is_rule
 674                             ? _("Rejecting impossible rule prerequisite `%s'.\n")
 675                             : _("Rejecting impossible implicit prerequisite `%s'.\n"),
 676                             d->name));
 677                       tryrules[ri].rule = 0;
 678
 679                       failed = 1;
 680                       break;
 681                     }
 682
 683                   memset (pat, '\0', sizeof (struct patdeps));
 684                   pat->ignore_mtime = d->ignore_mtime;
 685
 686                   DBS (DB_IMPLICIT,
 687                        (is_rule
 688                         ? _("Trying rule prerequisite `%s'.\n")
 689                         : _("Trying implicit prerequisite `%s'.\n"), d->name));
 690
 691                   /* If this prereq is also explicitly mentioned for FILE,
 692                      skip all tests below since it must be built no matter
 693                      which implicit rule we choose. */
 694
 695                   for (expl_d = file->deps; expl_d != 0; expl_d = expl_d->next)
 696                     if (streq (dep_name (expl_d), d->name))
 697                       break;
 698                   if (expl_d != 0)
 699                     {
 700                       (pat++)->name = d->name;
 701                       continue;
 702                     }
 703
 704                   /* The DEP->changed flag says that this dependency resides
 705                      in a nonexistent directory.  So we normally can skip
 706                      looking for the file.  However, if CHECK_LASTSLASH is
 707                      set, then the dependency file we are actually looking for
 708                      is in a different directory (the one gotten by prepending
 709                      FILENAME's directory), so it might actually exist.  */
 710
 711                   /* @@ dep->changed check is disabled. */
 712                   if (lookup_file (d->name) != 0
 713                       /*|| ((!dep->changed || check_lastslash) && */
 714                       || file_exists_p (d->name))
 715                     {
 716                       (pat++)->name = d->name;
 717                       continue;
 718                     }
 719
 720                   /* This code, given FILENAME = "lib/foo.o", dependency name
 721                      "lib/foo.c", and VPATH=src, searches for
 722                      "src/lib/foo.c".  */
 723                   {
 724                     const char *vname = vpath_search (d->name, 0, NULL, NULL);
 725                     if (vname)
 726                       {
 727                         DBS (DB_IMPLICIT,
 728                              (_("Found prerequisite `%s' as VPATH `%s'\n"),
 729                               d->name, vname));
 730                         (pat++)->name = d->name;
 731                         continue;
 732                       }
 733                   }
 734
 735                   /* We could not find the file in any place we should look.
 736                      Try to make this dependency as an intermediate file, but
 737                      only on the second pass.  */
 738
 739                   if (intermed_ok)
 740                     {
 741                       DBS (DB_IMPLICIT,
 742                            (_("Looking for a rule with intermediate file `%s'.\n"),
 743                             d->name));
 744
 745                       if (int_file == 0)
 746                         int_file = alloca (sizeof (struct file));
 747                       memset (int_file, '\0', sizeof (struct file));
 748                       int_file->name = d->name;
 749
 750                       if (pattern_search (int_file,
 751                                           0,
 752                                           depth + 1,
 753                                           recursions + 1))
 754                         {
 755                           pat->pattern = int_file->name;
 756                           int_file->name = d->name;
 757                           pat->file = int_file;
 758                           (pat++)->name = d->name;
 759                           int_file = 0;
 760                           continue;
 761                         }
 762
 763                       /* If we have tried to find P as an intermediate file
 764                          and failed, mark that name as impossible so we won't
 765                          go through the search again later.  */
 766                       if (int_file->variables)
 767                         free_variable_set (int_file->variables);
 768                       if (int_file->pat_variables)
 769                         free_variable_set (int_file->pat_variables);
 770                       file_impossible (d->name);
 771                     }
 772
 773                   /* A dependency of this rule does not exist. Therefore, this
 774                      rule fails.  */
 775                   failed = 1;
 776                   break;
 777                 }
 778
 779               /* Free the ns chain.  */
 780               if (dl != &dep_simple)
 781                 free_dep_chain (dl);
 782
 783               if (failed)
 784                 break;
 785             }
 786
 787           /* Reset the stem in FILE. */
 788
 789           file->stem = 0;
 790
 791           /* This rule is no longer `in use' for recursive searches.  */
 792           rule->in_use = 0;
 793
 794           if (! failed)
 795             /* This pattern rule does apply.  Stop looking for one.  */
 796             break;
 797
 798           /* This pattern rule does not apply. If some of its dependencies
 799              succeeded, free the data structure describing them.  */
 800           /* free_idep_chain (deps); */
 801           deps = 0;
 802         }
 803
 804       /* If we found an applicable rule without intermediate files, don't try
 805          with them.  */
 806       if (ri < nrules)
 807         break;
 808
 809       rule = 0;
 810     }
 811
 812   /* RULE is nil if the loop went through the list but everything failed.  */
 813   if (rule == 0)
 814     goto done;
 815
 816   foundrule = ri;
 817
 818   /* If we are recursing, store the pattern that matched FILENAME in
 819      FILE->name for use in upper levels.  */
 820
 821   if (recursions > 0)
 822     /* Kludge-o-matic */
 823     file->name = rule->targets[tryrules[foundrule].matches];
 824
 825   /* DEPLIST lists the prerequisites for the rule we found.  This includes the
 826      intermediate files, if any.  Convert them into entries on the deps-chain
 827      of FILE.  */
 828
 829   while (pat-- > deplist)
 830     {
 831       struct dep *dep;
 832       const char *s;
 833
 834       if (pat->file != 0)
 835         {
 836           /* If we need to use an intermediate file, make sure it is entered
 837              as a target, with the info that was found for it in the recursive
 838              pattern_search call.  We know that the intermediate file did not
 839              already exist as a target; therefore we can assume that the deps
 840              and cmds of F below are null before we change them.  */
 841
 842           struct file *imf = pat->file;
 843           struct file *f = lookup_file (imf->name);
 844
 845           /* We don't want to delete an intermediate file that happened
 846              to be a prerequisite of some (other) target. Mark it as
 847              precious.  */
 848           if (f != 0)
 849             f->precious = 1;
 850           else
 851             f = enter_file (imf->name);
 852
 853           f->deps = imf->deps;
 854           f->cmds = imf->cmds;
 855           f->stem = imf->stem;
 856           f->variables = imf->variables;
 857           f->pat_variables = imf->pat_variables;
 858           f->pat_searched = imf->pat_searched;
 859           f->also_make = imf->also_make;
 860           f->is_target = 1;
 861           f->intermediate = 1;
 862           f->tried_implicit = 1;
 863
 864           imf = lookup_file (pat->pattern);
 865           if (imf != 0 && imf->precious)
 866             f->precious = 1;
 867
 868           for (dep = f->deps; dep != 0; dep = dep->next)
 869             {
 870               dep->file = enter_file (dep->name);
 871               dep->name = 0;
 872               dep->file->tried_implicit |= dep->changed;
 873             }
 874         }
 875
 876       dep = alloc_dep ();
 877       dep->ignore_mtime = pat->ignore_mtime;
 878       s = strcache_add (pat->name);
 879       if (recursions)
 880         dep->name = s;
 881       else
 882         {
 883           dep->file = lookup_file (s);
 884           if (dep->file == 0)
 885             dep->file = enter_file (s);
 886         }
 887
 888       if (pat->file == 0 && tryrules[foundrule].rule->terminal)
 889         {
 890           /* If the file actually existed (was not an intermediate file), and
 891              the rule that found it was a terminal one, then we want to mark
 892              the found file so that it will not have implicit rule search done
 893              for it.  If we are not entering a `struct file' for it now, we
 894              indicate this with the `changed' flag.  */
 895           if (dep->file == 0)
 896             dep->changed = 1;
 897           else
 898             dep->file->tried_implicit = 1;
 899         }
 900
 901       dep->next = file->deps;
 902       file->deps = dep;
 903     }
 904
 905   if (!tryrules[foundrule].checked_lastslash)
 906     {
 907       /* Always allocate new storage, since STEM might be on the stack for an
 908          intermediate file.  */
 909       file->stem = strcache_add_len (stem, stemlen);
 910       fullstemlen = stemlen;
 911     }
 912   else
 913     {
 914       int dirlen = (lastslash + 1) - filename;
 915       char *sp;
 916
 917       /* We want to prepend the directory from
 918          the original FILENAME onto the stem.  */
 919       fullstemlen = dirlen + stemlen;
 920       sp = alloca (fullstemlen + 1);
 921       memcpy (sp, filename, dirlen);
 922       memcpy (sp + dirlen, stem, stemlen);
 923       sp[fullstemlen] = '\0';
 924       file->stem = strcache_add (sp);
 925     }
 926
 927   file->cmds = rule->cmds;
 928   file->is_target = 1;
 929
 930   /* Set precious flag. */
 931   {
 932     struct file *f = lookup_file (rule->targets[tryrules[foundrule].matches]);
 933     if (f && f->precious)
 934       file->precious = 1;
 935   }
 936
 937   /* If this rule builds other targets, too, put the others into FILE's
 938      `also_make' member.  */
 939
 940   if (rule->num > 1)
 941     for (ri = 0; ri < rule->num; ++ri)
 942       if (ri != tryrules[foundrule].matches)
 943         {
 944           char *nm = alloca (rule->lens[ri] + fullstemlen + 1);
 945           char *p = nm;
 946           struct file *f;
 947           struct dep *new = alloc_dep ();
 948
 949           /* GKM FIMXE: handle '|' here too */
 950           memcpy (p, rule->targets[ri],
 951                   rule->suffixes[ri] - rule->targets[ri] - 1);
 952           p += rule->suffixes[ri] - rule->targets[ri] - 1;
 953           memcpy (p, file->stem, fullstemlen);
 954           p += fullstemlen;
 955           memcpy (p, rule->suffixes[ri],
 956                   rule->lens[ri] - (rule->suffixes[ri] - rule->targets[ri])+1);
 957           new->name = strcache_add (nm);
 958           new->file = enter_file (new->name);
 959           new->next = file->also_make;
 960
 961           /* Set precious flag. */
 962           f = lookup_file (rule->targets[ri]);
 963           if (f && f->precious)
 964             new->file->precious = 1;
 965
 966           /* Set the is_target flag so that this file is not treated as
 967              intermediate by the pattern rule search algorithm and
 968              file_exists_p cannot pick it up yet.  */
 969           new->file->is_target = 1;
 970
 971           file->also_make = new;
 972         }
 973
 974  done:
 975   free (tryrules);
 976   free (deplist);
 977
 978   return rule != 0;
 979 }