From f5891a26d8d3ed87b059856650b2bdb0c7ea355e Mon Sep 17 00:00:00 2001 From: Boris Kolpackov Date: Mon, 28 Sep 2009 12:31:55 +0000 Subject: Implement the shortest stem first search order for pattern-specific variables and pattern rules. --- ChangeLog | 24 ++++++++++++-- NEWS | 8 +++++ doc/make.texi | 59 +++++++++++++++++++++++++++------ implicit.c | 22 ++++++++++++ main.c | 3 +- tests/ChangeLog | 8 +++++ tests/scripts/features/patspecific_vars | 14 ++++++++ tests/scripts/features/patternrules | 12 +++++++ variable.c | 52 ++++++++++++++++++++++++----- 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 + + * 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 * 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 +2009-09-25 Boris Kolpackov * implicit.c (pattern_search): Terminate early if we haven't found any rules to try (performance improvement). -2009-09-25 Boris Kolpackov +2009-09-25 Boris Kolpackov * 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 + + * 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 * 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 . */ 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; } -- cgit v1.2.3