Initial revision

1 files changed, 586 insertions, 0 deletions

diff --git a/implicit.c b/implicit.c
new file mode 100644
index 0000000..7961e9c
--- /dev/null
+++ b/implicit.c
@@ -0,0 +1,586 @@
+/* Implicit rule searching for GNU Make.
+Copyright (C) 1988, 1989, 1990, 1991 Free Software Foundation, Inc.
+This file is part of GNU Make.
+
+GNU Make is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GNU Make is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU Make; see the file COPYING.  If not, write to
+the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
+
+#include "make.h"
+#include "rule.h"
+#include "dep.h"
+#include "file.h"
+
+static int pattern_search ();
+
+/* For a FILE which has no commands specified, try to figure out some
+   from the implicit pattern rules.
+   Returns 1 if a suitable implicit rule was found,
+   after modifying FILE to contain the appropriate commands and deps,
+   or returns 0 if no implicit rule was found.  */
+
+int
+try_implicit_rule (file, depth)
+     struct file *file;
+     unsigned int depth;
+{
+  DEBUGPR ("Looking for an implicit rule for `%s'.\n");
+
+#ifndef	NO_ARCHIVES
+  /* If this is an archive member reference, use just the
+     archive member name to search for implicit rules.  */
+  if (ar_name (file->name))
+    {
+      DEBUGPR ("Looking for archive-member implicit rule for `%s'.\n");
+      if (pattern_search (file, 1, depth, 0))
+	return 1;
+    }
+#endif
+
+  return pattern_search (file, 0, depth, 0);
+}
+
+#define DEBUGP2(msg, a1, a2) \
+  if (debug_flag) \
+    { print_spaces (depth); printf (msg, a1, a2); fflush (stdout);  } else
+
+/* Search the pattern rules for a rule with an existing dependency to make
+   FILE.  If a rule is found, the appropriate commands and deps are put in FILE
+   and 1 is returned.  If not, 0 is returned.
+
+   If ARCHIVE is nonzero, FILE->name is of the form "LIB(MEMBER)".  A rule for
+   "(MEMBER)" will be searched for, and "(MEMBER)" will not be chopped up into
+   directory and filename parts.
+
+   If an intermediate file is found by pattern search, the intermediate file
+   is set up as a target by the recursive call and is also made a dependency
+   of FILE.
+
+   DEPTH is used for debugging messages.  */
+
+static int
+pattern_search (file, archive, depth, recursions)
+     struct file *file;
+     int archive;
+     unsigned int depth;
+     unsigned int recursions;
+{
+  /* Filename we are searching for a rule for.  */
+  char *filename = archive ? index (file->name, '(') : file->name;
+
+  /* Length of FILENAME.  */
+  unsigned int namelen = strlen (filename);
+
+  /* The last slash in FILENAME (or nil if there is none).  */
+  char *lastslash;
+
+  /* This is a file-object used as an argument in
+     recursive calls.  It never contains any data
+     except during a recursive call.  */
+  struct file *intermediate_file = 0;
+
+  /* List of dependencies found recursively.  */
+  struct file **intermediate_files
+    = (struct file **) alloca (max_pattern_deps * sizeof (struct file *));
+
+  /* List of the patterns used to find intermediate files.  */
+  char **intermediate_patterns
+    = (char **) alloca (max_pattern_deps * sizeof (char *));
+
+  /* This buffer records all the dependencies actually found for a rule.  */
+  char **found_files = (char **) alloca (max_pattern_deps * sizeof (char *));
+  /* Number of dep names now in FOUND_FILES.  */
+  unsigned int deps_found;
+
+  /* Names of possible dependencies are constructed in this buffer.  */
+  register char *depname = (char *) alloca (namelen + max_pattern_dep_length);
+
+  /* The start and length of the stem of FILENAME for the current rule.  */
+  register char *stem;
+  register unsigned int stemlen;
+
+  /* Buffer in which we store all the rules that are possibly applicable.  */
+  struct rule **tryrules
+    = (struct rule **) alloca (num_pattern_rules * sizeof (struct rule *));
+
+  /* Number of valid elements in TRYRULES.  */
+  unsigned int nrules;
+
+  /* The numbers of the rule targets of each rule
+     in TRYRULES that matched the target file.  */
+  unsigned int *matches
+    = (unsigned int *) alloca (num_pattern_rules * sizeof (unsigned int));
+
+  /* Each element is nonzero if LASTSLASH was used in
+     matching the corresponding element of TRYRULES.  */
+  char *checked_lastslash
+    = (char *) alloca (num_pattern_rules * sizeof (char));
+
+  /* The index in TRYRULES of the rule we found.  */
+  unsigned int foundrule;
+
+  /* Nonzero if should consider intermediate files as dependencies.  */
+  int intermed_ok;
+
+  /* Nonzero if we have matched a pattern-rule target
+     that is not just `%'.  */
+  int specific_rule_matched = 0;
+
+  register unsigned int i;
+  register struct rule *rule;
+  register struct dep *dep;
+
+  char *p;
+
+#ifndef	NO_ARCHIVES
+  if (archive || ar_name (filename))
+    lastslash = 0;
+  else
+#endif
+    {
+      /* Set LASTSLASH to point at the last slash in FILENAME
+	 but not counting any slash at the end.  (foo/bar/ counts as
+	 bar/ in directory foo/, not empty in directory foo/bar/.)  */
+      lastslash = rindex (filename, '/');
+      if (lastslash != 0 && lastslash[1] == '\0')
+	lastslash = 0;
+    }
+
+  /* First see which pattern rules match this target
+     and may be considered.  Put them in TRYRULES.  */
+
+  nrules = 0;
+  for (rule = pattern_rules; rule != 0; rule = rule->next)
+    {
+      int specific_rule_may_have_matched = 0;
+      int check_lastslash;
+
+      /* If the pattern rule has deps but no commands, ignore it.
+	 Users cancel built-in rules by redefining them without commands.  */
+      if (rule->deps != 0 && rule->cmds == 0)
+	continue;
+
+      /* If this rule is in use by a parent pattern_search,
+	 don't use it here.  */
+      if (rule->in_use)
+	{
+	  DEBUGP2 ("Avoiding implicit rule recursion.\n", 0, 0);
+	  continue;
+	}
+
+      for (i = 0; rule->targets[i] != 0; ++i)
+	{
+	  char *target = rule->targets[i];
+	  char *suffix = rule->suffixes[i];
+
+	  /* Rules that can match any filename and are not terminal
+	     are ignored if we're recursing, so that they cannot be
+	     intermediate files.  */
+	  if (recursions > 0 && target[1] == '\0' && !rule->terminal)
+	    continue;
+
+	  if (rule->lens[i] > namelen)
+	    /* It can't possibly match.  */
+	    continue;
+
+	  /* From the lengths of the filename and the pattern parts,
+	     find the stem: the part of the filename that matches the %.  */
+	  stem = filename + (suffix - target - 1);
+	  stemlen = namelen - rule->lens[i] + 1;
+
+	  /* Set CHECK_LASTSLASH if FILENAME contains a directory
+	     prefix and the target pattern does not contain a slash.  */
+
+	  check_lastslash = lastslash != 0 && index (target, '/') == 0;
+	  if (check_lastslash)
+	    {
+	      /* In that case, don't include the
+		 directory prefix in STEM here.  */
+	      unsigned int difference = lastslash - filename + 1;
+	      if (difference > stemlen)
+		continue;
+	      stemlen -= difference;
+	      stem += difference;
+	    }
+
+	  /* Check that the rule pattern matches the text before the stem.  */
+	  if (check_lastslash)
+	    {
+	      if (stem > (lastslash + 1)
+		  && strncmp (target, lastslash + 1, stem - lastslash - 1))
+		continue;
+	    }
+	  else if (stem > filename
+		   && strncmp (target, filename, stem - filename))
+	    continue;
+
+	  /* Check that the rule pattern matches the text after the stem.
+	     We could test simply use streq, but this way we compare the
+	     first two characters immediately.  This saves time in the very
+	     common case where the first character matches because it is a
+	     period.  */
+	  if (*suffix != stem[stemlen]
+	      || (*suffix != '\0' && !streq (&suffix[1], &stem[stemlen + 1])))
+	    continue;
+
+	  /* Record if we match a rule that not all filenames will match.  */
+	  if (target[1] != '\0')
+	    specific_rule_may_have_matched = 1;
+
+	  /* We have a matching target.  Don't search for any more.  */
+	  break;
+	}
+
+      /* None of the targets matched.  */
+      if (rule->targets[i] == 0)
+	continue;
+
+      specific_rule_matched |= specific_rule_may_have_matched;
+
+      /* A rule with no dependencies and no commands exists solely to set
+	 specific_rule_matched when it matches.  Don't try to use it.  */
+      if (rule->deps == 0 && rule->cmds == 0)
+	continue;
+
+      /* Record this rule in TRYRULES and the index
+	 of the (first) matching target in MATCHES.  */
+      tryrules[nrules] = rule;
+      matches[nrules] = i;
+      checked_lastslash[nrules] = check_lastslash;
+      ++nrules;
+    }
+
+  /* If we have found a matching rule that won't match all filenames,
+     retroactively reject any "terminal" rules that do always match.  */
+  if (specific_rule_matched)
+    for (i = 0; i < nrules; ++i)
+      if (!tryrules[i]->terminal)
+	{
+	  register unsigned int j;
+	  for (j = 0; tryrules[i]->targets[j] != 0; ++j)
+	    if (tryrules[i]->targets[j][1] == '\0')
+	      break;
+	  if (tryrules[i]->targets[j] != 0)
+	    tryrules[i] = 0;
+	}
+
+  /* Try each rule once without intermediate files, then once with them.  */
+  for (intermed_ok = 0; intermed_ok == !!intermed_ok; ++intermed_ok)
+    {
+      /* Try each pattern rule till we find one that applies.
+	 If it does, copy the names of its dependencies (as substituted)
+	 and store them in FOUND_FILES.  DEPS_FOUND is the number of them.  */
+
+      for (i = 0; i < nrules; i++)
+	{
+	  int check_lastslash;
+
+	  rule = tryrules[i];
+
+	  /* RULE is nil when we discover that a rule,
+	     already placed in TRYRULES, should not be applied.  */
+	  if (rule == 0)
+	    continue;
+
+	  /* Reject any terminal rules if we're
+	     looking to make intermediate files.  */
+	  if (intermed_ok && rule->terminal)
+	    continue;
+
+	  /* Mark this rule as in use so a recursive
+	     pattern_search won't try to use it.  */
+	  rule->in_use = 1;
+
+	  /* From the lengths of the filename and the matching pattern parts,
+	     find the stem: the part of the filename that matches the %.  */
+	  stem = filename
+	    + (rule->suffixes[matches[i]] - rule->targets[matches[i]]) - 1;
+	  stemlen = namelen - rule->lens[matches[i]] + 1;
+	  check_lastslash = (lastslash != 0
+			     && index (rule->targets[matches[i]], '/') == 0);
+	  if (check_lastslash)
+	    {
+	      stem += lastslash - filename + 1;
+	      stemlen -= (lastslash - filename) + 1;
+	    }
+
+	  DEBUGP2 ("Trying pattern rule with stem `%.*s'.\n",
+		   stemlen, stem);
+
+	  /* Try each dependency; see if it "exists".  */
+
+	  deps_found = 0;
+	  for (dep = rule->deps; dep != 0; dep = dep->next)
+	    {
+	      /* If the dependency name has a %, substitute the stem.  */
+	      p = index (dep_name (dep), '%');
+	      if (p != 0)
+		{
+		  register unsigned int i;
+		  if (check_lastslash)
+		    {
+		      i = lastslash - filename + 1;
+		      bcopy (filename, depname, i);
+		    }
+		  else
+		    i = 0;
+		  bcopy (dep_name (dep), depname + i, p - dep_name (dep));
+		  i += p - dep_name (dep);
+		  bcopy (stem, depname + i, stemlen);
+		  i += stemlen;
+		  strcpy (depname + i, p + 1);
+		  p = depname;
+		}
+	      else
+		p = dep_name (dep);
+
+	      /* P is now the actual dependency name as substituted.  */
+
+	      if (file_impossible_p (p))
+		{
+		  /* If this dependency has already been ruled
+		     "impossible", then the rule fails and don't
+		     bother trying it on the second pass either
+		     since we know that will fail too.  */
+		  DEBUGP2 ("Rejecting impossible %s dependent `%s'.\n",
+			   p == depname ? "implicit" : "rule", p);
+		  tryrules[i] = 0;
+		  break;
+		}
+
+	      intermediate_files[deps_found] = 0;
+
+	      DEBUGP2 ("Trying %s dependency `%s'.\n",
+		       p == depname ? "implicit" : "rule", p);
+	      if (!rule->subdir && lookup_file (p) != 0 || file_exists_p (p))
+		{
+		  found_files[deps_found++] = savestring (p, strlen (p));
+		  continue;
+		}
+	      /* This code, given FILENAME = "lib/foo.o", dependency name
+		 "lib/foo.c", and VPATH=src, searches for "src/lib/foo.c".  */
+	      if (vpath_search (&p))
+		{
+		  DEBUGP2 ("Found dependent as `%s'.\n", p, 0);
+		  found_files[deps_found++] = p;
+		  continue;
+		}
+
+	      /* We could not find the file in any place we should look.
+		 Try to make this dependency as an intermediate file,
+		 but only on the second pass.  */
+
+	      if (intermed_ok)
+		{
+		  if (intermediate_file == 0)
+		    intermediate_file
+		      = (struct file *) alloca (sizeof (struct file));
+
+		  DEBUGP2 ("Looking for a rule with intermediate file `%s'.\n",
+			   p, 0);
+
+		  bzero ((char *) intermediate_file, sizeof (struct file));
+		  intermediate_file->name = p;
+		  if (pattern_search (intermediate_file, 0, depth + 1,
+				      recursions + 1))
+		    {
+		      p = savestring (p, strlen (p));
+		      intermediate_patterns[deps_found]
+			= intermediate_file->name;
+		      found_files[deps_found] = p;
+		      intermediate_file->name = p;
+		      intermediate_files[deps_found] = intermediate_file;
+		      intermediate_file = 0;
+		      ++deps_found;
+		      continue;
+		    }
+
+		  /* If we have tried to find P as an intermediate
+		     file and failed, mark that name as impossible
+		     so we won't go through the search again later.  */
+		  file_impossible (p);
+		}
+
+	      /* A dependency of this rule does not exist.
+		 Therefore, this rule fails.  */
+	      break;
+	    }
+
+	  /* This rule is no longer `in use' for recursive searches.  */
+	  rule->in_use = 0;
+
+	  if (dep != 0)
+	    {
+	      /* This pattern rule does not apply.
+		 If some of its dependencies succeeded,
+		 free the data structure describing them.  */
+	      while (deps_found-- > 0)
+		{
+		  register struct file *f = intermediate_files[deps_found];
+		  free (found_files[deps_found]);
+		  if (f != 0
+		      && (f->stem < f->name
+			  || f->stem > f->name + strlen (f->name)))
+		    free (f->stem);
+		}
+	    }
+	  else
+	    /* This pattern rule does apply.  Stop looking for one.  */
+	    break;
+	}
+
+      /* If we found an applicable rule without
+	 intermediate files, don't try with them.  */
+      if (i < nrules)
+	break;
+
+      rule = 0;
+    }
+
+  /* RULE is nil if the loop went all the way
+     through the list and everything failed.  */
+  if (rule == 0)
+    return 0;
+
+  foundrule = i;
+
+  /* If we are recursing, store the pattern that matched
+     FILENAME in FILE->name for use in upper levels.  */
+
+  if (recursions > 0)
+    /* Kludge-o-matic */
+    file->name = rule->targets[matches[foundrule]];
+
+  /* FOUND_FILES lists the dependencies for the rule we found.
+     This includes the intermediate files, if any.
+     Convert them into entries on the deps-chain of FILE.  */
+
+  while (deps_found-- > 0)
+    {
+      register char *s;
+
+      if (intermediate_files[deps_found] != 0)
+	{
+	  /* If we need to use an intermediate file,
+	     make sure it is entered as a target, with the info that was
+	     found for it in the recursive pattern_search call.
+	     We know that the intermediate file did not already exist as
+	     a target; therefore we can assume that the deps and cmds
+	     of F below are null before we change them.  */
+
+	  struct file *imf = intermediate_files[deps_found];
+	  register struct file *f = enter_file (imf->name);
+	  f->deps = imf->deps;
+	  f->cmds = imf->cmds;
+	  f->stem = imf->stem;
+	  imf = lookup_file (intermediate_patterns[deps_found]);
+	  if (imf != 0 && imf->precious)
+	    f->precious = 1;
+	  f->intermediate = 1;
+	  f->tried_implicit = 1;
+	  for (dep = f->deps; dep != 0; dep = dep->next)
+	    {
+	      dep->file = enter_file (dep->name);
+	      dep->name = 0;
+	      dep->file->tried_implicit |= dep->changed;
+	    }
+	  num_intermediates++;
+	}
+
+      dep = (struct dep *) xmalloc (sizeof (struct dep));
+      s = found_files[deps_found];
+      if (recursions == 0)
+	{
+	  dep->name = 0;
+	  dep->file = enter_file (s);	
+	}
+      else
+	{
+	  dep->name = s;
+	  dep->file = 0;
+	  dep->changed = 0;
+	}
+      if (intermediate_files[deps_found] == 0 && tryrules[foundrule]->terminal)
+	{
+	  /* If the file actually existed (was not an intermediate file),
+	     and the rule that found it was a terminal one, then we want
+	     to mark the found file so that it will not have implicit rule
+	     search done for it.  If we are not entering a `struct file' for
+	     it now, we indicate this with the `changed' flag.  */
+	  if (dep->file == 0)
+	    dep->changed = 1;
+	  else
+	    dep->file->tried_implicit = 1;
+	}
+      dep->next = file->deps;
+      file->deps = dep;
+    }
+ 
+  uniquize_deps (file->deps);
+
+  if (!checked_lastslash[foundrule])
+    file->stem = stem[stemlen] == '\0' ? stem : savestring (stem, stemlen);
+  else
+    {
+      file->stem = (char *) xmalloc (((lastslash + 1) - filename)
+				     + stemlen + 1);
+      bcopy (filename, file->stem, (lastslash + 1) - filename);
+      bcopy (stem, file->stem + ((lastslash + 1) - filename), stemlen);
+      file->stem[((lastslash + 1) - filename) + stemlen] = '\0';
+    }
+
+  file->cmds = rule->cmds;
+
+  /* Put the targets other than the one that
+     matched into FILE's `also_make' member.  */
+
+  /* If there was only one target, there is nothing to do.  */
+  if (rule->targets[1] != 0)
+    {
+      unsigned int max_targets = 2;
+      register unsigned int idx;
+
+      file->also_make = (char **) xmalloc (2 * sizeof (char *));
+
+      idx = 0;
+      for (i = 0; rule->targets[i] != 0; ++i)
+	if (i != matches[foundrule])
+	  {
+	    if (idx == max_targets - 1)
+	      {
+		max_targets += 5;
+		file->also_make
+		  = (char **) xrealloc ((char *) file->also_make,
+					max_targets * sizeof (char *));
+	      }
+
+	    p = file->also_make[idx++] = (char *) xmalloc (rule->lens[i] +
+							   stemlen + 1);
+	    bcopy (rule->targets[i], p,
+		   rule->suffixes[i] - rule->targets[i] - 1);
+	    p += rule->suffixes[i] - rule->targets[i] - 1;
+	    bcopy (stem, p, stemlen);
+	    p += stemlen;
+	    bcopy (rule->suffixes[i], p,
+		   rule->lens[i]
+		   - (rule->suffixes[i] - rule->targets[i] - 1) + 1);
+	  }
+
+      file->also_make[idx] = 0;
+      if (idx < max_targets - 1)
+	file->also_make = (char **) xrealloc ((char *) file->also_make,
+					      (idx + 1) * sizeof (char *));
+    }
+
+  return 1;
+}