implicit.c

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