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 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 2, or (at your option) any later version.
  10
  11 GNU Make is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
  13 A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
  14
  15 You should have received a copy of the GNU General Public License along with
  16 GNU Make; see the file COPYING.  If not, write to the Free Software
  17 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.  */
  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           struct file *f;
 427           unsigned int failed = 0;
 428           int check_lastslash;
 429           int file_variables_set = 0;
 430
 431           rule = tryrules[ri];
 432
 433           remove_explicit_deps = 0;
 434
 435           /* RULE is nil when we discover that a rule,
 436              already placed in TRYRULES, should not be applied.  */
 437           if (rule == 0)
 438             continue;
 439
 440           /* Reject any terminal rules if we're
 441              looking to make intermediate files.  */
 442           if (intermed_ok && rule->terminal)
 443             continue;
 444
 445           /* Mark this rule as in use so a recursive
 446              pattern_search won't try to use it.  */
 447           rule->in_use = 1;
 448
 449           /* From the lengths of the filename and the matching pattern parts,
 450              find the stem: the part of the filename that matches the %.  */
 451           stem = filename
 452             + (rule->suffixes[matches[ri]] - rule->targets[matches[ri]]) - 1;
 453           stemlen = namelen - rule->lens[matches[ri]] + 1;
 454           check_lastslash = checked_lastslash[ri];
 455           if (check_lastslash)
 456             {
 457               stem += lastslash - filename + 1;
 458               stemlen -= (lastslash - filename) + 1;
 459             }
 460
 461           DBS (DB_IMPLICIT, (_("Trying pattern rule with stem `%.*s'.\n"),
 462                              (int) stemlen, stem));
 463
 464           strncpy (stem_str, stem, stemlen);
 465           stem_str[stemlen] = '\0';
 466
 467           /* Temporary assign STEM to file->stem (needed to set file
 468              variables below).   */
 469           file->stem = stem_str;
 470
 471           /* Try each dependency; see if it "exists".  */
 472
 473           for (dep = rule->deps; dep != 0; dep = dep->next)
 474             {
 475               unsigned int len;
 476               char *p;
 477               char *p2;
 478               unsigned int order_only = 0; /* Set if '|' was seen. */
 479
 480               /* In an ideal world we would take the dependency line,
 481                  substitute the stem, re-expand the whole line and chop it
 482                  into individual prerequisites. Unfortunately this won't work
 483                  because of the "check_lastslash" twist.  Instead, we will
 484                  have to go word by word, taking $()'s into account, for each
 485                  word we will substitute the stem, re-expand, chop it up, and,
 486                  if check_lastslash != 0, add the directory part to each
 487                  resulting prerequisite.  */
 488
 489               p = get_next_word (dep->name, &len);
 490
 491               while (1)
 492                 {
 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                   /* Parse the dependencies. */
 575
 576                   while (1)
 577                     {
 578                       id_ptr = &deps;
 579
 580                       for (; *id_ptr; id_ptr = &(*id_ptr)->next)
 581                         ;
 582
 583                       *id_ptr = (struct idep *)
 584                         multi_glob (
 585                           parse_file_seq (&p2,
 586                                           order_only ? '\0' : '|',
 587                                           sizeof (struct idep),
 588                                           1), sizeof (struct idep));
 589
 590                       /* @@ It would be nice to teach parse_file_seq or
 591                          multi_glob to add prefix. This would save us some
 592                          reallocations. */
 593
 594                       if (order_only || add_dir || had_stem)
 595                         {
 596                           unsigned long l = lastslash - filename + 1;
 597
 598                           for (d = *id_ptr; d != 0; d = d->next)
 599                             {
 600                               if (order_only)
 601                                 d->ignore_mtime = 1;
 602
 603                               if (add_dir)
 604                                 {
 605                                   char *n = alloca (strlen (d->name) + l + 1);
 606                                   memcpy (n, filename, l);
 607                                   memcpy (n+l, d->name, strlen (d->name) + 1);
 608                                   d->name = strcache_add (n);
 609                                 }
 610
 611                               if (had_stem)
 612                                 d->had_stem = 1;
 613                             }
 614                         }
 615
 616                       if (!order_only && *p2)
 617                       {
 618                         ++p2;
 619                         order_only = 1;
 620                         continue;
 621                       }
 622
 623                       break;
 624                     }
 625
 626                   p += len;
 627                   p = get_next_word (p, &len);
 628                 }
 629             }
 630
 631           /* Reset the stem in FILE. */
 632
 633           file->stem = 0;
 634
 635           /* @@ This loop can be combined with the previous one. I do
 636              it separately for now for transparency.*/
 637
 638           for (d = deps; d != 0; d = d->next)
 639             {
 640               const char *name = d->name;
 641
 642               if (file_impossible_p (name))
 643                 {
 644                   /* If this dependency has already been ruled "impossible",
 645                      then the rule fails and don't bother trying it on the
 646                      second pass either since we know that will fail too.  */
 647                   DBS (DB_IMPLICIT,
 648                        (d->had_stem
 649                         ? _("Rejecting impossible implicit prerequisite `%s'.\n")
 650                         : _("Rejecting impossible rule prerequisite `%s'.\n"),
 651                         name));
 652                   tryrules[ri] = 0;
 653
 654                   failed = 1;
 655                   break;
 656                 }
 657
 658               DBS (DB_IMPLICIT,
 659                    (d->had_stem
 660                     ? _("Trying implicit prerequisite `%s'.\n")
 661                     : _("Trying rule prerequisite `%s'.\n"), name));
 662
 663               /* If this prerequisite also happened to be explicitly mentioned
 664                  for FILE skip all the test below since it it has to be built
 665                  anyway, no matter which implicit rule we choose. */
 666
 667               for (expl_d = file->deps; expl_d != 0; expl_d = expl_d->next)
 668                 if (streq (dep_name (expl_d), name))
 669                   break;
 670               if (expl_d != 0)
 671                 continue;
 672
 673               /* The DEP->changed flag says that this dependency resides in a
 674                  nonexistent directory.  So we normally can skip looking for
 675                  the file.  However, if CHECK_LASTSLASH is set, then the
 676                  dependency file we are actually looking for is in a different
 677                  directory (the one gotten by prepending FILENAME's directory),
 678                  so it might actually exist.  */
 679
 680               /* @@ dep->changed check is disabled. */
 681               if (((f = lookup_file (name)) != 0 && f->is_target)
 682                   /*|| ((!dep->changed || check_lastslash) && */
 683                   || file_exists_p (name))
 684                 continue;
 685
 686               /* This code, given FILENAME = "lib/foo.o", dependency name
 687                  "lib/foo.c", and VPATH=src, searches for "src/lib/foo.c".  */
 688               {
 689                 const char *vname = vpath_search (name, 0);
 690                 if (vname)
 691                   {
 692                     DBS (DB_IMPLICIT,
 693                          (_("Found prerequisite `%s' as VPATH `%s'\n"),
 694                           name, vname));
 695                     continue;
 696                   }
 697               }
 698
 699
 700               /* We could not find the file in any place we should look.  Try
 701                  to make this dependency as an intermediate file, but only on
 702                  the second pass.  */
 703
 704               if (intermed_ok)
 705                 {
 706                   if (intermediate_file == 0)
 707                     intermediate_file = alloca (sizeof (struct file));
 708
 709                   DBS (DB_IMPLICIT,
 710                        (_("Looking for a rule with intermediate file `%s'.\n"),
 711                         name));
 712
 713                   memset (intermediate_file, '\0', sizeof (struct file));
 714                   intermediate_file->name = name;
 715                   if (pattern_search (intermediate_file,
 716                                       0,
 717                                       depth + 1,
 718                                       recursions + 1))
 719                     {
 720                       d->intermediate_pattern = intermediate_file->name;
 721                       intermediate_file->name = strcache_add (name);
 722                       d->intermediate_file = intermediate_file;
 723                       intermediate_file = 0;
 724
 725                       continue;
 726                     }
 727
 728                   /* If we have tried to find P as an intermediate
 729                      file and failed, mark that name as impossible
 730                      so we won't go through the search again later.  */
 731                   if (intermediate_file->variables)
 732                     free_variable_set (intermediate_file->variables);
 733                   file_impossible (name);
 734                 }
 735
 736               /* A dependency of this rule does not exist. Therefore,
 737                  this rule fails.  */
 738               failed = 1;
 739               break;
 740             }
 741
 742           /* This rule is no longer `in use' for recursive searches.  */
 743           rule->in_use = 0;
 744
 745           if (failed)
 746             {
 747               /* This pattern rule does not apply. If some of its
 748                  dependencies succeeded, free the data structure
 749                  describing them.  */
 750               free_idep_chain (deps);
 751               deps = 0;
 752             }
 753           else
 754             /* This pattern rule does apply.  Stop looking for one.  */
 755             break;
 756         }
 757
 758       /* If we found an applicable rule without
 759          intermediate files, don't try with them.  */
 760       if (ri < nrules)
 761         break;
 762
 763       rule = 0;
 764     }
 765
 766   /* RULE is nil if the loop went all the way
 767      through the list and everything failed.  */
 768   if (rule == 0)
 769     goto done;
 770
 771   foundrule = ri;
 772
 773   /* If we are recursing, store the pattern that matched
 774      FILENAME in FILE->name for use in upper levels.  */
 775
 776   if (recursions > 0)
 777     /* Kludge-o-matic */
 778     file->name = rule->targets[matches[foundrule]];
 779
 780   /* FOUND_FILES lists the dependencies for the rule we found.
 781      This includes the intermediate files, if any.
 782      Convert them into entries on the deps-chain of FILE.  */
 783
 784   if (remove_explicit_deps)
 785     {
 786       /* Remove all the dependencies that didn't come from
 787          this implicit rule. */
 788
 789       dep = file->deps;
 790       while (dep != 0)
 791         {
 792           struct dep *next = dep->next;
 793           free_dep (dep);
 794           dep = next;
 795         }
 796       file->deps = 0;
 797   }
 798
 799   expl_d = file->deps; /* We will add them at the end. */
 800   d_ptr = &file->deps;
 801
 802   for (d = deps; d != 0; d = d->next)
 803     {
 804       const char *s;
 805
 806       if (d->intermediate_file != 0)
 807         {
 808           /* If we need to use an intermediate file,
 809              make sure it is entered as a target, with the info that was
 810              found for it in the recursive pattern_search call.
 811              We know that the intermediate file did not already exist as
 812              a target; therefore we can assume that the deps and cmds
 813              of F below are null before we change them.  */
 814
 815           struct file *imf = d->intermediate_file;
 816           register struct file *f = lookup_file (imf->name);
 817
 818           /* We don't want to delete an intermediate file that happened
 819              to be a prerequisite of some (other) target. Mark it as
 820              precious.  */
 821           if (f != 0)
 822             f->precious = 1;
 823           else
 824             f = enter_file (strcache_add (imf->name));
 825
 826           f->deps = imf->deps;
 827           f->cmds = imf->cmds;
 828           f->stem = imf->stem;
 829           f->also_make = imf->also_make;
 830           f->is_target = 1;
 831
 832           if (!f->precious)
 833             {
 834               imf = lookup_file (d->intermediate_pattern);
 835               if (imf != 0 && imf->precious)
 836                 f->precious = 1;
 837             }
 838
 839           f->intermediate = 1;
 840           f->tried_implicit = 1;
 841           for (dep = f->deps; dep != 0; dep = dep->next)
 842             {
 843               dep->file = enter_file (dep->name);
 844               dep->name = 0;
 845               dep->file->tried_implicit |= dep->changed;
 846             }
 847         }
 848
 849       dep = alloc_dep ();
 850       dep->ignore_mtime = d->ignore_mtime;
 851       s = d->name; /* Hijacking the name. */
 852       d->name = 0;
 853       if (recursions == 0)
 854         {
 855           dep->file = lookup_file (s);
 856           if (dep->file == 0)
 857             dep->file = enter_file (s);
 858         }
 859       else
 860         dep->name = s;
 861
 862       if (d->intermediate_file == 0 && tryrules[foundrule]->terminal)
 863         {
 864           /* If the file actually existed (was not an intermediate file),
 865              and the rule that found it was a terminal one, then we want
 866              to mark the found file so that it will not have implicit rule
 867              search done for it.  If we are not entering a `struct file' for
 868              it now, we indicate this with the `changed' flag.  */
 869           if (dep->file == 0)
 870             dep->changed = 1;
 871           else
 872             dep->file->tried_implicit = 1;
 873         }
 874
 875       *d_ptr = dep;
 876       d_ptr = &dep->next;
 877     }
 878
 879   *d_ptr = expl_d;
 880
 881   if (!checked_lastslash[foundrule])
 882     {
 883       /* Always allocate new storage, since STEM might be
 884          on the stack for an intermediate file.  */
 885       file->stem = strcache_add_len (stem, stemlen);
 886       fullstemlen = stemlen;
 887     }
 888   else
 889     {
 890       int dirlen = (lastslash + 1) - filename;
 891       char *sp;
 892
 893       /* We want to prepend the directory from
 894          the original FILENAME onto the stem.  */
 895       fullstemlen = dirlen + stemlen;
 896       sp = alloca (fullstemlen + 1);
 897       memcpy (sp, filename, dirlen);
 898       memcpy (sp + dirlen, stem, stemlen);
 899       sp[fullstemlen] = '\0';
 900       file->stem = strcache_add (sp);
 901     }
 902
 903   file->cmds = rule->cmds;
 904   file->is_target = 1;
 905
 906   /* Set precious flag. */
 907   {
 908     struct file *f = lookup_file (rule->targets[matches[foundrule]]);
 909     if (f && f->precious)
 910       file->precious = 1;
 911   }
 912
 913   /* If this rule builds other targets, too, put the others into FILE's
 914      `also_make' member.  */
 915
 916   if (rule->num > 1)
 917     for (ri = 0; ri < rule->num; ++ri)
 918       if (ri != matches[foundrule])
 919         {
 920           char *p = alloca (rule->lens[ri] + fullstemlen + 1);
 921           struct file *f;
 922           struct dep *new = alloc_dep ();
 923
 924           /* GKM FIMXE: handle '|' here too */
 925           memcpy (p, rule->targets[ri],
 926                   rule->suffixes[ri] - rule->targets[ri] - 1);
 927           p += rule->suffixes[ri] - rule->targets[ri] - 1;
 928           memcpy (p, file->stem, fullstemlen);
 929           p += fullstemlen;
 930           memcpy (p, rule->suffixes[ri],
 931                   rule->lens[ri] - (rule->suffixes[ri] - rule->targets[ri])+1);
 932           new->name = strcache_add (p);
 933           new->file = enter_file (new->name);
 934           new->next = file->also_make;
 935
 936           /* Set precious flag. */
 937           f = lookup_file (rule->targets[ri]);
 938           if (f && f->precious)
 939             new->file->precious = 1;
 940
 941           /* Set the is_target flag so that this file is not treated
 942              as intermediate by the pattern rule search algorithm and
 943              file_exists_p cannot pick it up yet.  */
 944           new->file->is_target = 1;
 945
 946           file->also_make = new;
 947         }
 948
 949  done:
 950   free_idep_chain (deps);
 951   free (tryrules);
 952
 953   return rule != 0;
 954 }