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