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