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

1 files changed, 22 insertions, 0 deletions

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)