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                   /* If the dependency name has %, substitute the stem.
 506                      Watch out, we are going to do something tricky here. If
 507                      we just replace % with the stem value, later, when we do
 508                      the second expansion, we will re-expand this stem value
 509                      once again. This is not good especially if you have
 510                      certain characters in your stem (like $).
 511
 512                      Instead, we will replace % with $* and allow the second
 513                      expansion to take care of it for us. This way (since $*
 514                      is a simple variable) there won't be additional
 515                      re-expansion of the stem.  */
 516
 517                   for (p2 = p; p2 < p + len && *p2 != '%'; ++p2)
 518                     ;
 519
 520                   if (p2 < p + len)
 521                     {
 522                       register unsigned int i = p2 - p;
 523                       bcopy (p, depname, i);
 524                       bcopy ("$*", depname + i, 2);
 525                       bcopy (p2 + 1, depname + i + 2, len - i - 1);
 526                       depname[len + 2 - 1] = '\0';
 527
 528                       if (check_lastslash)
 529                         add_dir = 1;
 530
 531                       had_stem = 1;
 532                     }
 533                   else
 534                     {
 535                       bcopy (p, depname, len);
 536                       depname[len] = '\0';
 537                     }
 538
 539                   p2 = variable_expand_for_file (depname, file);
 540
 541                   /* Parse the dependencies. */
 542
 543                   while (1)
 544                     {
 545                       id_ptr = &deps;
 546
 547                       for (; *id_ptr; id_ptr = &(*id_ptr)->next)
 548                         ;
 549
 550                       *id_ptr = (struct idep *)
 551                         multi_glob (
 552                           parse_file_seq (&p2,
 553                                           order_only ? '\0' : '|',
 554                                           sizeof (struct idep),
 555                                           1), sizeof (struct idep));
 556
 557                       /* @@ It would be nice to teach parse_file_seq or
 558                          multi_glob to add prefix. This would save us some
 559                          reallocations. */
 560
 561                       if (order_only || add_dir || had_stem)
 562                         {
 563                           unsigned long l = lastslash - filename + 1;
 564
 565                           for (d = *id_ptr; d != 0; d = d->next)
 566                             {
 567                               if (order_only)
 568                                 d->ignore_mtime = 1;
 569
 570                               if (add_dir)
 571                                 {
 572                                   char *p = d->name;
 573
 574                                   d->name = xmalloc (strlen (p) + l + 1);
 575
 576                                   bcopy (filename, d->name, l);
 577                                   bcopy (p, d->name + l, strlen (p) + 1);
 578
 579                                   free (p);
 580                                 }
 581
 582                               if (had_stem)
 583                                 d->had_stem = 1;
 584                             }
 585                         }
 586
 587                       if (!order_only && *p2)
 588                       {
 589                         ++p2;
 590                         order_only = 1;
 591                         continue;
 592                       }
 593
 594                       break;
 595                     }
 596
 597                   p += len;
 598                   p = get_next_word (p, &len);
 599                 }
 600             }
 601
 602           /* Reset the stem in FILE. */
 603
 604           file->stem = 0;
 605
 606           /* @@ This loop can be combined with the previous one. I do
 607              it separately for now for transparency.*/
 608
 609           for (d = deps; d != 0; d = d->next)
 610             {
 611               char *name = d->name;
 612
 613               if (file_impossible_p (name))
 614                 {
 615                   /* If this dependency has already been ruled "impossible",
 616                      then the rule fails and don't bother trying it on the
 617                      second pass either since we know that will fail too.  */
 618                   DBS (DB_IMPLICIT,
 619                        (d->had_stem
 620                         ? _("Rejecting impossible implicit prerequisite `%s'.\n")
 621                         : _("Rejecting impossible rule prerequisite `%s'.\n"),
 622                         name));
 623                   tryrules[i] = 0;
 624
 625                   failed = 1;
 626                   break;
 627                 }
 628
 629               DBS (DB_IMPLICIT,
 630                    (d->had_stem
 631                     ? _("Trying implicit prerequisite `%s'.\n")
 632                     : _("Trying rule prerequisite `%s'.\n"), name));
 633
 634               /* If this prerequisite also happened to be explicitly mentioned
 635                  for FILE skip all the test below since it it has to be built
 636                  anyway, no matter which implicit rule we choose. */
 637
 638               for (expl_d = file->deps; expl_d != 0; expl_d = expl_d->next)
 639                 if (strcmp (dep_name (expl_d), name) == 0) break;
 640
 641               if (expl_d != 0)
 642                 continue;
 643
 644
 645
 646               /* The DEP->changed flag says that this dependency resides in a
 647                  nonexistent directory.  So we normally can skip looking for
 648                  the file.  However, if CHECK_LASTSLASH is set, then the
 649                  dependency file we are actually looking for is in a different
 650                  directory (the one gotten by prepending FILENAME's directory),
 651                  so it might actually exist.  */
 652
 653               /* @@ dep->changed check is disabled. */
 654               if (((f = lookup_file (name)) != 0 && f->is_target)
 655                   /*|| ((!dep->changed || check_lastslash) && */
 656                   || file_exists_p (name))
 657                 {
 658                   continue;
 659                 }
 660
 661               /* This code, given FILENAME = "lib/foo.o", dependency name
 662                  "lib/foo.c", and VPATH=src, searches for "src/lib/foo.c".  */
 663               vname = name;
 664               if (vpath_search (&vname, (FILE_TIMESTAMP *) 0))
 665                 {
 666                   DBS (DB_IMPLICIT,
 667                        (_("Found prerequisite `%s' as VPATH `%s'\n"),
 668                         name,
 669                         vname));
 670
 671                   free (vname);
 672                   continue;
 673                 }
 674
 675
 676               /* We could not find the file in any place we should look.  Try
 677                  to make this dependency as an intermediate file, but only on
 678                  the second pass.  */
 679
 680               if (intermed_ok)
 681                 {
 682                   if (intermediate_file == 0)
 683                     intermediate_file
 684                       = (struct file *) alloca (sizeof (struct file));
 685
 686                   DBS (DB_IMPLICIT,
 687                        (_("Looking for a rule with intermediate file `%s'.\n"),
 688                         name));
 689
 690                   bzero ((char *) intermediate_file, sizeof (struct file));
 691                   intermediate_file->name = name;
 692                   if (pattern_search (intermediate_file,
 693                                       0,
 694                                       depth + 1,
 695                                       recursions + 1))
 696                     {
 697                       d->intermediate_file = intermediate_file;
 698                       d->intermediate_pattern = intermediate_file->name;
 699
 700                       intermediate_file->name = xstrdup (name);
 701                       intermediate_file = 0;
 702
 703                       continue;
 704                     }
 705
 706                   /* If we have tried to find P as an intermediate
 707                      file and failed, mark that name as impossible
 708                      so we won't go through the search again later.  */
 709                   file_impossible (name);
 710                 }
 711
 712               /* A dependency of this rule does not exist. Therefore,
 713                  this rule fails.  */
 714               failed = 1;
 715               break;
 716             }
 717
 718           /* This rule is no longer `in use' for recursive searches.  */
 719           rule->in_use = 0;
 720
 721           if (failed)
 722             {
 723               /* This pattern rule does not apply. If some of its
 724                  dependencies succeeded, free the data structure
 725                  describing them.  */
 726               free_idep_chain (deps);
 727               deps = 0;
 728             }
 729           else
 730             /* This pattern rule does apply.  Stop looking for one.  */
 731             break;
 732         }
 733
 734       /* If we found an applicable rule without
 735          intermediate files, don't try with them.  */
 736       if (i < nrules)
 737         break;
 738
 739       rule = 0;
 740     }
 741
 742   /* RULE is nil if the loop went all the way
 743      through the list and everything failed.  */
 744   if (rule == 0)
 745     goto done;
 746
 747   foundrule = i;
 748
 749   /* If we are recursing, store the pattern that matched
 750      FILENAME in FILE->name for use in upper levels.  */
 751
 752   if (recursions > 0)
 753     /* Kludge-o-matic */
 754     file->name = rule->targets[matches[foundrule]];
 755
 756   /* FOUND_FILES lists the dependencies for the rule we found.
 757      This includes the intermediate files, if any.
 758      Convert them into entries on the deps-chain of FILE.  */
 759
 760   if (remove_explicit_deps)
 761     {
 762       /* Remove all the dependencies that didn't come from
 763          this implicit rule. */
 764
 765       dep = file->deps;
 766       while (dep != 0)
 767         {
 768           struct dep *next = dep->next;
 769           free (dep->name);
 770           free ((char *)dep);
 771           dep = next;
 772         }
 773       file->deps = 0;
 774   }
 775
 776   expl_d = file->deps; /* We will add them at the end. */
 777   d_ptr = &file->deps;
 778
 779   for (d = deps; d != 0; d = d->next)
 780     {
 781       register char *s;
 782
 783       if (d->intermediate_file != 0)
 784         {
 785           /* If we need to use an intermediate file,
 786              make sure it is entered as a target, with the info that was
 787              found for it in the recursive pattern_search call.
 788              We know that the intermediate file did not already exist as
 789              a target; therefore we can assume that the deps and cmds
 790              of F below are null before we change them.  */
 791
 792           struct file *imf = d->intermediate_file;
 793           register struct file *f = lookup_file (imf->name);
 794
 795           /* We don't want to delete an intermediate file that happened
 796              to be a prerequisite of some (other) target. Mark it as
 797              precious.  */
 798           if (f != 0)
 799             f->precious = 1;
 800           else
 801             f = enter_file (imf->name);
 802
 803           f->deps = imf->deps;
 804           f->cmds = imf->cmds;
 805           f->stem = imf->stem;
 806           f->also_make = imf->also_make;
 807           f->is_target = 1;
 808
 809           if (!f->precious)
 810             {
 811               imf = lookup_file (d->intermediate_pattern);
 812               if (imf != 0 && imf->precious)
 813                 f->precious = 1;
 814             }
 815
 816           f->intermediate = 1;
 817           f->tried_implicit = 1;
 818           for (dep = f->deps; dep != 0; dep = dep->next)
 819             {
 820               dep->file = enter_file (dep->name);
 821               /* enter_file uses dep->name _if_ we created a new file.  */
 822               if (dep->name != dep->file->name)
 823                 free (dep->name);
 824               dep->name = 0;
 825               dep->file->tried_implicit |= dep->changed;
 826             }
 827         }
 828
 829       dep = (struct dep *) xmalloc (sizeof (struct dep));
 830       dep->ignore_mtime = d->ignore_mtime;
 831       dep->staticpattern = 0;
 832       dep->need_2nd_expansion = 0;
 833       s = d->name; /* Hijacking the name. */
 834       d->name = 0;
 835       if (recursions == 0)
 836         {
 837           dep->name = 0;
 838           dep->file = lookup_file (s);
 839           if (dep->file == 0)
 840             /* enter_file consumes S's storage.  */
 841             dep->file = enter_file (s);
 842           else
 843             /* A copy of S is already allocated in DEP->file->name.
 844                So we can free S.  */
 845             free (s);
 846         }
 847       else
 848         {
 849           dep->name = s;
 850           dep->file = 0;
 851           dep->changed = 0;
 852         }
 853       if (d->intermediate_file == 0 && tryrules[foundrule]->terminal)
 854         {
 855           /* If the file actually existed (was not an intermediate file),
 856              and the rule that found it was a terminal one, then we want
 857              to mark the found file so that it will not have implicit rule
 858              search done for it.  If we are not entering a `struct file' for
 859              it now, we indicate this with the `changed' flag.  */
 860           if (dep->file == 0)
 861             dep->changed = 1;
 862           else
 863             dep->file->tried_implicit = 1;
 864         }
 865
 866       *d_ptr = dep;
 867       d_ptr = &dep->next;
 868     }
 869
 870   *d_ptr = expl_d;
 871
 872   if (!checked_lastslash[foundrule])
 873     {
 874       /* Always allocate new storage, since STEM might be
 875          on the stack for an intermediate file.  */
 876       file->stem = savestring (stem, stemlen);
 877       fullstemlen = stemlen;
 878     }
 879   else
 880     {
 881       int dirlen = (lastslash + 1) - filename;
 882
 883       /* We want to prepend the directory from
 884          the original FILENAME onto the stem.  */
 885       fullstemlen = dirlen + stemlen;
 886       file->stem = (char *) xmalloc (fullstemlen + 1);
 887       bcopy (filename, file->stem, dirlen);
 888       bcopy (stem, file->stem + dirlen, stemlen);
 889       file->stem[fullstemlen] = '\0';
 890     }
 891
 892   file->cmds = rule->cmds;
 893   file->is_target = 1;
 894
 895   /* Set precious flag. */
 896   {
 897     struct file *f = lookup_file (rule->targets[matches[foundrule]]);
 898     if (f && f->precious)
 899       file->precious = 1;
 900   }
 901
 902   /* If this rule builds other targets, too, put the others into FILE's
 903      `also_make' member.  */
 904
 905   if (rule->targets[1] != 0)
 906     for (i = 0; rule->targets[i] != 0; ++i)
 907       if (i != matches[foundrule])
 908         {
 909           struct file *f;
 910           struct dep *new = (struct dep *) xmalloc (sizeof (struct dep));
 911           /* GKM FIMXE: handle '|' here too */
 912           new->ignore_mtime = 0;
 913           new->staticpattern = 0;
 914           new->need_2nd_expansion = 0;
 915           new->name = p = (char *) xmalloc (rule->lens[i] + fullstemlen + 1);
 916           bcopy (rule->targets[i], p,
 917                  rule->suffixes[i] - rule->targets[i] - 1);
 918           p += rule->suffixes[i] - rule->targets[i] - 1;
 919           bcopy (file->stem, p, fullstemlen);
 920           p += fullstemlen;
 921           bcopy (rule->suffixes[i], p,
 922                  rule->lens[i] - (rule->suffixes[i] - rule->targets[i]) + 1);
 923           new->file = enter_file (new->name);
 924           new->next = file->also_make;
 925
 926           /* Set precious flag. */
 927           f = lookup_file (rule->targets[i]);
 928           if (f && f->precious)
 929             new->file->precious = 1;
 930
 931           file->also_make = new;
 932         }
 933
 934  done:
 935   free_idep_chain (deps);
 936   free (tryrules);
 937
 938   return rule != 0;
 939 }