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