implicit.c

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