Implement the shortest stem first search order for pattern-specific variables and pattern rules.

9 files changed, 179 insertions, 23 deletions

diff --git a/ChangeLog b/ChangeLog
index 5f5750f..3b4a6dc 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,23 @@
+2009-09-28  Boris Kolpackov  <boris@codesynthesis.com>
+
+	* varible.c (create_pattern_var): Insert variables into the
+	PATTERN_VARS list in the shortest patterns first order.
+
+	* implicit.c (tryrule): Add STEMLEN and ORDER members. These are
+	used to sort the rules.
+	(stemlen_compare): Compare two tryrule elements.
+	(pattern_search): Sort the rules so that they are in the shortest
+	stem first order.
+
+	* main.c (.FEATURES): Add a keyword to indicate the new behavior.
+
+	* doc/make.texi (Pattern-specific Variable Values): Describe the
+	new pattern-specific variables application order.
+	(Introduction to Pattern Rules): Describe the new pattern rules
+	search order.
+
+	* NEWS: Add a note about the new behavior.
+
 2009-09-27  Juan Manuel Guerrero  <juan.guerrero@gmx.de>
 
 	* configh.dos.template: Remove unconditional definition of
@@ -42,12 +62,12 @@
 
 	* function.c (string_glob): Free NAME in the nameseq chain.
 
-2009-09-25 Boris Kolpackov  <boris@codesynthesis.com>
+2009-09-25  Boris Kolpackov  <boris@codesynthesis.com>
 
 	* implicit.c (pattern_search): Terminate early if we haven't
 	found any rules to try (performance improvement).
 
-2009-09-25 Boris Kolpackov  <boris@codesynthesis.com>
+2009-09-25  Boris Kolpackov  <boris@codesynthesis.com>
 
 	* implicit.c (pattern_search): Merge three parallel arrays,
 	TRYRULES, MATCHES, and CHECKED_LASTSLASH, into one array
diff --git a/NEWS b/NEWS
index 8004ab9..fd0a254 100644
--- a/NEWS
+++ b/NEWS
@@ -39,6 +39,14 @@ Version 3.81.90
   prerequisites.  This is most useful for target- and pattern-specific
   variables.
 
+* WARNING: Backward-incompatibility!
+  The pattern-specific variables and pattern rules are now applied in the 
+  shortest stem first order instead of the definition order (variables
+  and rules with the same stem length are still applied in the definition
+  order). This produces the usually-desired behavior where more specific
+  patterns are preferred. To detect this feature search for 'shortest-stem'
+  in the .FEATURES special variable.  
+
 
 Version 3.81
 
diff --git a/doc/make.texi b/doc/make.texi
index c2ae06a..82df90a 100644
--- a/doc/make.texi
+++ b/doc/make.texi
@@ -5720,12 +5720,7 @@ In addition to target-specific variable values
 (@pxref{Target-specific, ,Target-specific Variable Values}), GNU
 @code{make} supports pattern-specific variable values.  In this form,
 the variable is defined for any target that matches the pattern
-specified.  If a target matches more than one pattern, all the
-matching pattern-specific variables are interpreted in the order in
-which they were defined in the makefile, and collected together into
-one set.  Variables defined in this way are searched after any
-target-specific variables defined explicitly for that target, and
-before target-specific variables defined for the parent target.
+specified.
 
 Set a pattern-specific variable value like this:
 
@@ -5748,6 +5743,31 @@ For example:
 will assign @code{CFLAGS} the value of @samp{-O} for all targets
 matching the pattern @code{%.o}.
 
+If a target matches more than one pattern, the matching pattern-specific
+variables with longer stems are interpreted first. This results in more
+specific variables taking precedence over the more generic ones, for
+example:
+
+@example
+%.o: %.c
+        $(CC) -c $(CFLAGS) $(CPPFLAGS) $< -o $@@
+
+lib/%.o: CFLAGS := -fPIC -g
+%.o: CFLAGS := -g
+
+all: foo.o lib/bar.o
+@end example
+
+In this example the first definition of the @code{CFLAGS} variable
+will be used to update @file{lib/bar.o} even though the second one
+also applies to this target. Pattern-specific variables which result
+in the same stem length are considered in the order in which they
+were defined in the makefile.
+
+Pattern-specific variables are searched after any target-specific
+variables defined explicitly for that target, and before target-specific
+variables defined for the parent target.
+
 @node Suppressing Inheritance, Special Variables, Pattern-specific, Using Variables
 @section Suppressing Inheritance
 @findex private
@@ -9143,11 +9163,28 @@ updated themselves.
 @cindex multiple targets, in pattern rule
 @cindex target, multiple in pattern rule
 
-The order in which pattern rules appear in the makefile is important
-since this is the order in which they are considered.
-Of equally applicable
-rules, only the first one found is used.  The rules you write take precedence
-over those that are built in.  Note however, that a rule whose
+It is possible that several pattern rules can be used to update a
+target. In this case @code{make} considers rules which produce
+shorter stems first. This results in more specific rules being
+preferred to the more generic ones, for example:
+
+@example
+%.o: %.c
+        $(CC) -c $(CFLAGS) $(CPPFLAGS) $< -o $@@
+
+lib/%.o: lib/%.c
+        $(CC) -fPIC -c $(CFLAGS) $(CPPFLAGS) $< -o $@@
+
+all: foo.o lib/bar.o
+@end example
+
+In this example the second rule will be used to update @file{lib/bar.o}
+even though the first rule can also be used.
+
+Pattern rules which result in the same stem length are considered in
+the order in which they appear in the makefile. Of equally applicable
+rules, only the first one found is used.  The rules you write take
+precedence over those that are built in. Note however, that a rule whose
 prerequisites actually exist or are mentioned always takes priority over a
 rule with prerequisites that must be made by chaining other implicit rules.
 @cindex pattern rules, order of
diff --git a/implicit.c b/implicit.c
index c3e35f7..8ad6395 100644
--- a/implicit.c
+++ b/implicit.c
@@ -167,10 +167,25 @@ struct tryrule
     /* Index of the target in this rule that matched the file. */
     unsigned int matches;
 
+    /* Stem length for this match. */
+    unsigned int stemlen;
+
+    /* Definition order of this rule. Used to implement stable sort.*/
+    unsigned int order;
+
     /* Nonzero if the LASTSLASH logic was used in matching this rule. */
     char checked_lastslash;
   };
 
+int
+stemlen_compare (const void *v1, const void *v2)
+{
+  const struct tryrule *r1 = (const struct tryrule *)v1;
+  const struct tryrule *r2 = (const struct tryrule *)v2;
+  int r = r1->stemlen - r2->stemlen;
+  return r != 0 ? r : (int)(r1->order - r1->order);
+}
+
 /* 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.
@@ -385,6 +400,8 @@ pattern_search (struct file *file, int archive,
              that rule will be in TRYRULES more than once.  */
           tryrules[nrules].rule = rule;
 	  tryrules[nrules].matches = ti;
+          tryrules[nrules].stemlen = stemlen + (check_lastslash ? pathlen : 0);
+          tryrules[nrules].order = nrules;
 	  tryrules[nrules].checked_lastslash = check_lastslash;
           ++nrules;
         }
@@ -394,6 +411,11 @@ pattern_search (struct file *file, int archive,
   if (nrules == 0)
     goto done;
 
+  /* Sort the rules to place matches with the shortest stem first. This
+     way the most specific rules will be tried first. */
+  if (nrules > 1)
+    qsort (tryrules, nrules, sizeof (struct tryrule), stemlen_compare);
+
   /* If we have found a matching rule that won't match all filenames,
      retroactively reject any non-"terminal" rules that do always match.  */
   if (specific_rule_matched)
diff --git a/main.c b/main.c
index f447e57..b79888c 100644
--- a/main.c
+++ b/main.c
@@ -1120,7 +1120,8 @@ main (int argc, char **argv, char **envp)
 
   /* Set up .FEATURES */
   define_variable (".FEATURES", 9,
-                   "target-specific order-only second-expansion else-if",
+                   "target-specific order-only second-expansion else-if"
+                   "shortest-stem",
                    o_default, 0);
 #ifndef NO_ARCHIVES
   do_variable_definition (NILF, ".FEATURES", "archives",
diff --git a/tests/ChangeLog b/tests/ChangeLog
index c56e09a..7110e4a 100644
--- a/tests/ChangeLog
+++ b/tests/ChangeLog
@@ -1,3 +1,11 @@
+2009-09-28  Boris Kolpackov  <boris@codesynthesis.com>
+
+	* scripts/features/patspecific_vars: Add a test for the shortest
+	stem first order.
+
+	* scripts/features/patternrules: Add a test for the shortest stem
+	first order.
+
 2009-09-24  Paul Smith  <psmith@gnu.org>
 
 	* scripts/features/se_implicit: Add a test for order-only
diff --git a/tests/scripts/features/patspecific_vars b/tests/scripts/features/patspecific_vars
index 355e86d..8ca228d 100644
--- a/tests/scripts/features/patspecific_vars
+++ b/tests/scripts/features/patspecific_vars
@@ -131,4 +131,18 @@ ab: ; @echo "$(FOO)"
 
 run_make_test(undef, 'FOO=C', "C f1\n");
 
+# TEST #9: Test shortest stem selection in pattern-specific variables.
+
+run_make_test('
+%-mt.x: x := two
+%.x: x := one
+
+all: foo.x foo-mt.x
+
+foo.x: ;@echo $x
+foo-mt.x: ;@echo $x
+',
+'',
+"one\ntwo");
+
 1;
diff --git a/tests/scripts/features/patternrules b/tests/scripts/features/patternrules
index dcaf0dd..eebe7c0 100644
--- a/tests/scripts/features/patternrules
+++ b/tests/scripts/features/patternrules
@@ -207,6 +207,18 @@ CWEAVE := :
 
 unlink(@f);
 
+# TEST #9: Test shortest stem selection in pattern rules.
+
+run_make_test('
+%.x: ;@echo one
+%-mt.x: ;@echo two
+
+all: foo.x foo-mt.x
+',
+'',
+"one\ntwo");
+
+1;
 
 # This tells the test driver that the perl test script executed properly.
 1;
diff --git a/variable.c b/variable.c
index 90c447c..6a74dcd 100644
--- a/variable.c
+++ b/variable.c
@@ -35,28 +35,62 @@ this program.  If not, see <http://www.gnu.org/licenses/>.  */
 
 static struct pattern_var *pattern_vars;
 
-/* Pointer to last struct in the chain, so we can add onto the end.  */
+/* Pointer to the last struct in the pack of a specific size, from 1 to 255.*/
 
-static struct pattern_var *last_pattern_var;
+static struct pattern_var *last_pattern_vars[256];
 
-/* Create a new pattern-specific variable struct.  */
+/* Create a new pattern-specific variable struct. The new variable is
+   inserted into the PATTERN_VARS list in the shortest patterns first
+   order to support the shortest stem matching (the variables are
+   matched in the reverse order so the ones with the longest pattern
+   will be considered first). Variables with the same pattern length
+   are inserted in the definition order. */
 
 struct pattern_var *
 create_pattern_var (const char *target, const char *suffix)
 {
+  register unsigned int len = strlen (target);
   register struct pattern_var *p = xmalloc (sizeof (struct pattern_var));
 
-  if (last_pattern_var != 0)
-    last_pattern_var->next = p;
+  if (pattern_vars != 0)
+    {
+      if (len < 256 && last_pattern_vars[len] != 0)
+        {
+          p->next = last_pattern_vars[len]->next;
+          last_pattern_vars[len]->next = p;
+        }
+      else
+        {
+          /* Find the position where we can insert this variable. */
+          register struct pattern_var **v;
+
+          for (v = &pattern_vars; ; v = &(*v)->next)
+            {
+              /* Insert at the end of the pack so that patterns with the
+                 same length appear in the order they were defined .*/
+
+              if (*v == 0 || (*v)->len > len)
+                {
+                  p->next = *v;
+                  *v = p;
+                  break;
+                }
+            }
+        }
+    }
   else
-    pattern_vars = p;
-  last_pattern_var = p;
-  p->next = 0;
+    {
+      pattern_vars = p;
+      p->next = 0;
+    }
 
   p->target = target;
-  p->len = strlen (target);
+  p->len = len;
   p->suffix = suffix + 1;
 
+  if (len < 256)
+    last_pattern_vars[len] = p;
+
   return p;
 }