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