Performance and correctness fix:
authorBenjamin Smedberg <benjamin@smedbergs.us>
Thu, 12 Feb 2009 13:11:13 -0500
changeset 104 b60ef841a8113faefe5d31a713988d91743a74c2
parent 103 f19e091ae2d821a1cba379a88ce96a6c93c25931
child 105 1a5a35701f9388d9d3216f01c21cc565a3d2ff11
push id56
push userbsmedberg@mozilla.com
push dateThu, 12 Feb 2009 19:47:10 +0000
Performance and correctness fix: * We were incorrectly considering match-anything rules when there was a more specific pattern rule that did not have commands. It's common to write %.mk simply to prevent match-anything rules from rebuilding it. * Recalculating dependencies at least twice for each pattern rule was costing. Now we save them in an intermediate PatternRuleInstance which records the stem as well.
pymake/data.py
pymake/parser.py
tests/automatic-variables.mk
tests/matchany.mk
--- a/pymake/data.py
+++ b/pymake/data.py
@@ -379,16 +379,23 @@ class Pattern(object):
             # if we're not a pattern, the replacement is not parsed as a pattern either
             return replacement
 
         return Pattern(replacement).resolve('', stem)
 
     def __repr__(self):
         return "<Pattern with data %r>" % (self.data,)
 
+    backre = re.compile(r'[%\\]')
+    def __str__(self):
+        if not self.ispattern:
+            return self.backre.sub(r'\\\1', self.data[0])
+
+        return self.backre.sub(r'\\\1', self.data[0]) + '%' + self.data[1]
+
 class Target(object):
     """
     An actual (non-pattern) target.
 
     It holds target-specific variables and a list of rules. It may also point to a parent
     PatternTarget, if this target is being created by an implicit rule.
 
     The rules associated with this target may be Rule instances or, in the case of static pattern
@@ -405,27 +412,25 @@ class Target(object):
 
         # self.remade is a tri-state:
         #   None - we haven't remade yet
         #   True - we did something to remake ourself
         #   False - we did nothing to remake ourself
         self.remade = None
 
     def addrule(self, rule):
+        assert isinstance(rule, (Rule, PatternRuleInstance))
         if len(self.rules) and rule.doublecolon != self.rules[0].doublecolon:
-            # TODO: better location for this error
-            raise DataError("Cannot have single- and double-colon rules for the same target.")
+            raise DataError("Cannot have single- and double-colon rules for the same target. Prior rule location: %s" % self.rules[0].loc, rule.loc)
 
-        if isinstance(rule, PatternRule):
-            if len(rule.targetpatterns) != 1:
-                # TODO: better location
-                raise DataError("Static pattern rules must only have one target pattern")
-            if rule.targetpatterns[0].match(self.target) is None:
-                # TODO: better location
-                raise DataError("Static pattern rule doesn't match target")
+        if isinstance(rule, PatternRuleInstance):
+            if len(rule.prule.targetpatterns) != 1:
+                raise DataError("Static pattern rules must only have one target pattern", rule.prule.loc)
+            if rule.prule.targetpatterns[0].match(self.target) is None:
+                raise DataError("Static pattern rule doesn't match target '%s'" % self.target, rule.loc)
 
         self.rules.append(rule)
 
     def isdoublecolon(self):
         return self.rules[0].doublecolon
 
     def isphony(self, makefile):
         """Is this a phony target? We don't check for existence of phony targets."""
@@ -441,67 +446,63 @@ class Target(object):
     def resolveimplicitrule(self, makefile, targetstack, rulestack):
         """
         Try to resolve an implicit rule to build this target.
         """
         # The steps in the GNU make manual Implicit-Rule-Search.html are very detailed. I hope they can be trusted.
 
         log.info("Trying to find implicit rule to make '%s'" % self.target)
 
-        candidates = []
-        hasmatch = False
+        dir, s, file = self.target.rpartition('/')
+        dir = dir + s
+
+        candidates = [] # list of PatternRuleInstance
+
+        hasmatch = any((r.hasmatch(file) for r in makefile.implicitrules))
         for r in makefile.implicitrules:
             if r in rulestack:
                 log.info("%s: Avoiding implicit rule recursion" % (r.loc,))
                 continue
 
             if not len(r.commands):
                 log.info("%s: Has no commands" % (r.loc,))
                 continue
 
-            if r.ismatchany():
-                candidates.append(r)
-            elif r.matchfor(self.target) is not None:
-                hasmatch = True
-                candidates.append(r)
+            for ri in r.matchesfor(dir, file, hasmatch):
+                candidates.append(ri)
             
-        # If there are non match-any candidates, remove nonterminal match-anything rules
-        if hasmatch:
-            candidates = [r for r in candidates
-                          if (not r.ismatchany()) or r.doublecolon]
-
         newcandidates = []
 
         for r in candidates:
             depfailed = None
-            for p in r.prerequisitesfor(self.target):
+            for p in r.prerequisites:
                 t = makefile.gettarget(p)
                 t.resolvevpath(makefile)
                 if not t.explicit and t.mtime is None:
                     depfailed = p
                     break
 
             if depfailed is not None:
                 if r.doublecolon:
-                    log.info("  Rule at %s doesn't match: prerequisite '%s' not mentioned and doesn't exist." % (r.loc, depfailed))
+                    log.info("  Terminal rule at %s doesn't match: prerequisite '%s' not mentioned and doesn't exist." % (r.loc, depfailed))
                 else:
                     newcandidates.append(r)
                 continue
 
             log.info("Found implicit rule at %s for target '%s'" % (r.loc, self.target))
             self.rules.append(r)
             return
 
         # Try again, but this time with chaining and without terminal (double-colon) rules
 
         for r in newcandidates:
-            newrulestack = rulestack + [r]
+            newrulestack = rulestack + [r.prule]
 
             depfailed = None
-            for p in r.prerequisitesfor(self.target):
+            for p in r.prerequisites:
                 t = makefile.gettarget(p)
                 try:
                     t.resolvedeps(makefile, targetstack, newrulestack, True)
                 except ResolutionError:
                     depfailed = p
                     break
 
             if depfailed is not None:
@@ -557,25 +558,25 @@ class Target(object):
         if ruleswithcommands == 0:
             self.resolveimplicitrule(makefile, targetstack, rulestack)
 
         # If a target is mentioned, but doesn't exist, has no commands and no
         # prerequisites, it is special and exists just to say that targets which
         # depend on it are always out of date. This is like .FORCE but more
         # compatible with other makes.
         # Otherwise, we don't know how to make it.
-        if not len(self.rules) and self.mtime is None and not any((len(rule.prerequisitesfor(self.target)) > 0
+        if not len(self.rules) and self.mtime is None and not any((len(rule.prerequisites) > 0
                                                                    for rule in self.rules)):
             if required:
                 raise ResolutionError("No rule to make target '%s' needed by %s" % (self.target,
                     ' -> '.join(targetstack[:-1])))
 
         for r in self.rules:
             newrulestack = rulestack + [r]
-            for d in r.prerequisitesfor(self.target):
+            for d in r.prerequisites:
                 dt = makefile.gettarget(d)
                 if dt.explicit:
                     continue
 
                 dt.resolvedeps(makefile, targetstack, newrulestack, True)
 
         for v in makefile.getpatternvariablesfor(self.target):
             self.variables.merge(v)
@@ -659,17 +660,17 @@ class Target(object):
         if len(self.rules) == 0:
             pass
         elif self.isdoublecolon():
             for r in self.rules:
                 remake = False
                 if self.mtime is None:
                     log.info("Remaking %s using rule at %s because it doesn't exist or is a forced target" % (self.target, r.loc))
                     remake = True
-                for p in r.prerequisitesfor(self.target):
+                for p in r.prerequisites:
                     dep = makefile.gettarget(p)
                     didanything = dep.make(makefile, [], []) or didanything
                     if not remake and mtimeislater(dep.mtime, self.mtime):
                         log.info("Remaking %s using rule at %s because %s is newer." % (self.target, r.loc, p))
                         remake = True
                 if remake:
                     self.remake()
                     r.execute(self, makefile)
@@ -680,17 +681,17 @@ class Target(object):
             if self.mtime is None:
                 log.info("Remaking %s because it doesn't exist or is a forced target" % (self.target,))
                 remake = True
 
             for r in self.rules:
                 if len(r.commands):
                     assert commandrule is None, "Two command rules for a single-colon target?"
                     commandrule = r
-                for p in r.prerequisitesfor(self.target):
+                for p in r.prerequisites:
                     dep = makefile.gettarget(p)
                     didanything = dep.make(makefile, [], []) or didanything
                     if not remake and mtimeislater(dep.mtime, self.mtime):
                         log.info("Remaking %s because %s is newer" % (self.target, p))
                         remake = True
 
             if remake:
                 self.remake()
@@ -793,19 +794,16 @@ class Rule(object):
         self.commands = []
         self.loc = loc
 
     def addcommand(self, c):
         """Append a command expansion."""
         assert(isinstance(c, Expansion))
         self.commands.append(c)
 
-    def prerequisitesfor(self, t):
-        return self.prerequisites
-
     def execute(self, target, makefile):
         assert isinstance(target, Target)
 
         v = Variables(parent=target.variables)
         setautomaticvariables(v, makefile, target, self.prerequisites)
         # TODO: $* in non-pattern rules sucks
 
         env = makefile.getsubenvironment(v)
@@ -817,16 +815,44 @@ class Rule(object):
                 if not len(cline) or cline.isspace():
                     continue
                 if not isHidden:
                     print "%s $ %s" % (self.loc, cline)
                 r = subprocess.call(cline, shell=True, env=env)
                 if r != 0 and not ignoreErrors:
                     raise DataError("command '%s' failed, return code was %s" % (cline, r), self.loc)
 
+class PatternRuleInstance(object):
+    """
+    This represents a pattern rule instance for a particular target. It has the same API as Rule, but
+    different internals, forwarding most information on to the PatternRule.
+    """
+    def __init__(self, prule, dir, stem, ismatchany):
+        assert isinstance(prule, PatternRule)
+
+        self.dir = dir
+        self.stem = stem
+        self.prule = prule
+        self.prerequisites = prule.prerequisitesforstem(dir, stem)
+        self.doublecolon = prule.doublecolon
+        self.loc = prule.loc
+        self.ismatchany = ismatchany
+        self.commands = prule.commands
+
+    def execute(self, target, makefile):
+        assert isinstance(target, Target)
+
+        self.prule.execute(target, makefile, self.dir, self.stem)
+
+    def __str__(self):
+        return "Pattern rule at %s with stem '%s', matchany: %s doublecolon: %s" % (self.loc,
+                                                                                    self.dir + self.stem,
+                                                                                    self.ismatchany,
+                                                                                    self.doublecolon)
+
 class PatternRule(object):
     """
     An implicit rule or static pattern rule containing target patterns, prerequisite patterns,
     and a list of commands.
     """
 
     def __init__(self, targetpatterns, prerequisites, doublecolon, loc):
         self.targetpatterns = targetpatterns
@@ -837,57 +863,51 @@ class PatternRule(object):
 
     def addcommand(self, c):
         assert isinstance(c, Expansion)
         self.commands.append(c)
 
     def ismatchany(self):
         return any((t.ismatchany() for t in self.targetpatterns))
 
-    def matchfor(self, t):
+    def hasmatch(self, file):
+        for p in self.targetpatterns:
+            if p.match(file) is not None:
+                return True
+
+        return False
+
+    def matchesfor(self, dir, file, skipsinglecolonmatchany):
         """
-        Determine whether and how this rule might match target t.
-        @returns a tuple (dir, stem) if this rule matches, or None
+        Determine all the target patterns of this rule that might match target t.
+        @yields a PatternRuleInstance for each.
         """
 
         for p in self.targetpatterns:
-            stem = p.match(t)
-            if stem is not None:
-                return ('', stem)
-
-        dir, s, path = t.rpartition('/')
-        if s == '':
-            return None
-
-        for p in self.targetpatterns:
-            if p.hasslash():
-                continue
-
-            stem = p.match(path)
-            if stem is not None:
-                return (dir + s, stem)
-
-        return None
+            matchany = p.ismatchany()
+            if matchany:
+                if skipsinglecolonmatchany and not self.doublecolon:
+                    continue
+                stem = file
+                yield PatternRuleInstance(self, dir, stem, True)
+            else:
+                stem = p.match(file)
+                if stem is not None:
+                    yield PatternRuleInstance(self, dir, stem, False)
 
     def prerequisitesforstem(self, dir, stem):
         return [p.resolve(dir, stem) for p in self.prerequisites]
 
-    def prerequisitesfor(self, t):
-        dir, stem = self.matchfor(t)
-        return self.prerequisitesforstem(dir, stem)
-
-    def execute(self, target, makefile):
+    def execute(self, target, makefile, dir, stem):
         assert isinstance(target, Target)
 
-        dir, stem = self.matchfor(target.target)
-
         v = Variables(parent=target.variables)
         setautomaticvariables(v, makefile, target,
                               self.prerequisitesforstem(dir, stem))
-        setautomatic(v, '*', [stem])
+        setautomatic(v, '*', [dir + stem])
 
         env = makefile.getsubenvironment(v)
 
         for c in self.commands:
             cstring = c.resolve(v)
             for cline in splitcommand(cstring):
                 cline, isHidden, isRecursive, ignoreErrors = findmodifiers(cline)
                 if not len(cline) or cline.isspace():
@@ -1003,17 +1023,17 @@ class Makefile(object):
             self.vpath = []
         else:
             self.vpath = filter(lambda e: e != '', re.split('[:\s]+', value.resolve(self.variables, ['VPATH'])))
 
         targets = list(self._targets.itervalues())
         for t in targets:
             t.explicit = True
             for r in t.rules:
-                for p in r.prerequisitesfor(t.target):
+                for p in r.prerequisites:
                     self.gettarget(p).explicit = True
 
     def include(self, path, required=True):
         """
         Include the makefile at `path`.
         """
         self.included.append(path)
         if os.path.exists(path):
--- a/pymake/parser.py
+++ b/pymake/parser.py
@@ -715,18 +715,21 @@ def parsestream(fd, filename, makefile):
                     if len(patterns) != 1:
                         raise SyntaxError("A static pattern rule may have only one pattern", d.getloc(offset))
 
                     pattern = data.Pattern(patterns[0])
 
                     e, token, offset = parsemakesyntax(d, offset, (';',), itermakefilechars)
                     prereqs = map(data.Pattern, data.splitwords(e.resolve(makefile.variables)))
                     currule = data.PatternRule([pattern], prereqs, doublecolon, loc=d.getloc(0))
+
                     for t in targets:
-                        makefile.gettarget(t.gettarget()).addrule(currule)
+                        tname = t.gettarget()
+                        pinstance = data.PatternRuleInstance(currule, '', tname, pattern.ismatchany())
+                        makefile.gettarget(tname).addrule(pinstance)
 
                     if len(targets):
                         makefile.foundtarget(targets[0].gettarget())
 
                     if token == ';':
                         offset = d.skipwhitespace(offset)
                         e, token, offset = parsemakesyntax(d, offset, (), itercommandchars)
                         currule.addcommand(e)
--- a/tests/automatic-variables.mk
+++ b/tests/automatic-variables.mk
@@ -47,17 +47,17 @@ prog: subd/test.out subd/test.out2
 	test "$$(cat $<)" = "remade"
 	test "$$(cat $(word 2,$^))" = ""
 
 host_prog: subd/host_test.out subd/host_test.out2
 	@echo TEST-FAIL No need to remake
 
 %.out: %.in dummy
 	test "$@" = "subd/test.out"
-	test "$*" = "subd/test"
+	test "$*" = "subd/test"              # *
 	test "$<" = "src/subd/test.in"       # <
 	test "$^" = "src/subd/test.in dummy" # ^
 	test "$?" = "src/subd/test.in"       # ?
 	test "$+" = "src/subd/test.in dummy" # +
 	test "$(@D)" = "subd"
 	test "$(@F)" = "test.out"
 	test "$(*D)" = "subd"
 	test "$(*F)" = "test"
--- a/tests/matchany.mk
+++ b/tests/matchany.mk
@@ -1,15 +1,14 @@
 #T returncode: 2
 
 # we should fail to make foo.ooo from foo.ooo.test
 all: foo.ooo
 	@echo TEST-FAIL
 
-%.ooo: %.ccc
-	cp $< %@
+%.ooo:
 
 # this match-anything pattern should not apply to %.ooo
 %: %.test
 	cp $< $@
 
 foo.ooo.test:
 	touch $@