implicit.c

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