I noticed Expansion.resolve still comes up really high on perf charts. This patch makes it much easier to resolve expansions which are just literals, which is very common for variable names. Unfortunately, this makes the code a fair bit more complex, and doesn't help nearly as much as I'd like. resolve-perf
authorBenjamin Smedberg <benjamin@smedbergs.us>
Thu, 26 Feb 2009 20:32:19 -0500
branchresolve-perf
changeset 191 7a8dc41115d6
parent 190 e36530da06f1
child 203 b5ecea7cc212
push id111
push userbsmedberg@mozilla.com
push dateFri, 27 Feb 2009 01:32:32 +0000
I noticed Expansion.resolve still comes up really high on perf charts. This patch makes it much easier to resolve expansions which are just literals, which is very common for variable names. Unfortunately, this makes the code a fair bit more complex, and doesn't help nearly as much as I'd like. I'm beginning to wonder if getting gmake performance parity is impossible, or at least improbable given the current architecture: but I can't think of an alternate architecture that is better.
pymake/data.py
pymake/functions.py
pymake/parser.py
pymake/parserdata.py
tests/var-set.mk
--- a/pymake/data.py
+++ b/pymake/data.py
@@ -55,44 +55,92 @@ def stripdotslashes(sl):
 def getindent(stack):
     return ''.ljust(len(stack) - 1)
 
 def _if_else(c, t, f):
     if c:
         return t()
     return f()
 
+class StringExpansion(object):
+    __slots__ = ('s', 't')
+    loc = None
+    
+    def __init__(self, s):
+        assert isinstance(s, str)
+        self.s = s
+        self.t = tuple(s)
+
+    def lstrip(self):
+        self.s = self.s.lstrip()
+
+    def rstrip(self):
+        self.s = self.s.rstrip()
+
+    def _firstisstring(self):
+        return True
+
+    def _firststring(self):
+        return self.s
+
+    def _afterfirst(self):
+        return ()
+
+    def isempty(self):
+        return self.s == ''
+
+    def resolve(self, i, j, k=None):
+        return self.t
+
+    def resolvestr(self, i, j, k=None):
+        return self.s
+
+    def resolvesplit(self, i, j, k=None):
+        return self.s.split()
+
+    def clone(self):
+        e = Expansion()
+        e.appendstr(self.s)
+        return e
+
 class Expansion(list):
     """
     A representation of expanded data, such as that for a recursively-expanded variable, a command, etc.
     """
 
     __slots__ = ('loc',)
 
     def __init__(self, loc=None):
         # A list of (element, isfunc) tuples
         # element is either a string or a function
         self.loc = loc
 
     @staticmethod
     def fromstring(s):
-        e = Expansion()
-        e.appendstr(s)
-        return e
+        return StringExpansion(s)
 
     def clone(self):
         e = Expansion()
         e.extend(self)
         return e
 
+    def _firstisstring(self):
+        return len(self) and not self[0][1]
+
+    def _firststring(self):
+        return self[0][0]
+
+    def _afterfirst(self):
+        return self[1:]
+
     def _lastisstring(self):
         return len(self) and not self[-1][1]
 
-    def _firstisstring(self):
-        return len(self) and not self[0][1]
+    def _laststring(self):
+        return self[-1][0]
 
     def append(self, e):
         raise NotImplementedError("Don't call me!")
 
     _append = list.append
 
     def appendstr(self, s):
         assert isinstance(s, str)
@@ -107,20 +155,18 @@ class Expansion(list):
 
     def appendfunc(self, func):
         assert isinstance(func, functions.Function)
         self._append((func, True))
 
     def concat(self, o):
         """Concatenate the other expansion on to this one."""
         if o._firstisstring() and self._lastisstring():
-            mystr = self[-1][0]
-            ostr = o[0][0]
-            self[-1] = mystr + ostr, False
-            self.extend(o[1:])
+            self[-1] = self._laststring() + o._firststring(), False
+            self.extend(o._afterfirst())
         else:
             self.extend(o)
 
     def isempty(self):
         return (not len(self)) or self[0] == ('', False)
 
     def lstrip(self):
         """Strip leading literal whitespace from this expansion."""
@@ -129,16 +175,25 @@ class Expansion(list):
             self[0] = s, False
 
     def rstrip(self):
         """Strip trailing literal whitespace from this expansion."""
         if self._lastisstring():
             s = self[-1][0].rstrip()
             self[-1] = s, False
 
+    def finish(self):
+        if len(self) == 0:
+            return StringExpansion('')
+
+        if len(self) == 1 and not self[0][1]:
+            return StringExpansion(self[0][0])
+
+        return self
+
     def resolve(self, makefile, variables, setting=[]):
         """
         Resolve this variable into a value, by interpolating the value
         of other variables.
 
         @param setting (Variable instance) the variable currently
                being set, if any. Setting variables must avoid self-referential
                loops.
@@ -167,17 +222,17 @@ class Expansion(list):
                 print "error appending i: %r" % (i,)
                 raise
         return s
 
     def resolvesplit(self, makefile, variables, setting=[]):
         return util.itersplit(self.resolve(makefile, variables, setting))
 
     def __repr__(self):
-        return "<Expansion with elements: %r>" % ([repr(e) for e, isfunc in self],)
+        return "<Expansion with elements: %r>" % ([e for e, isfunc in self],)
 
 class Variables(object):
     """
     A mapping from variable names to variables. Variables have flavor, source, and value. The value is an 
     expansion object.
     """
 
     FLAVOR_RECURSIVE = 0
@@ -379,19 +434,22 @@ class Pattern(object):
         @returns None if the word doesn't match, or the matching stem.
                       If this is a %-less pattern, the stem will always be ''
         """
         if not self.ispattern():
             if word == self.data[0]:
                 return word
             return None
 
-        l1 = len(self.data[0])
-        l2 = len(self.data[1])
-        if len(word) >= l1 + l2 and word.startswith(self.data[0]) and word.endswith(self.data[1]):
+        if word.startswith(self.data[0]) and word.endswith(self.data[1]):
+            l1 = len(self.data[0])
+            l2 = len(self.data[1])
+            if len(word) < l1 + l2:
+                return None
+
             if l2 == 0:
                 return word[l1:]
             return word[l1:-l2]
 
         return None
 
     def resolve(self, dir, stem):
         if self.ispattern():
@@ -974,17 +1032,17 @@ class Rule(object):
 
     def __init__(self, prereqs, doublecolon, loc):
         self.prerequisites = prereqs
         self.doublecolon = doublecolon
         self.commands = []
         self.loc = loc
 
     def addcommand(self, c):
-        assert isinstance(c, Expansion)
+        assert isinstance(c, (Expansion, StringExpansion))
         self.commands.append(c)
 
     def getcommands(self, target, makefile):
         assert isinstance(target, Target)
 
         return getcommandsforrule(self, target, makefile, self.prerequisites, stem=None)
         # TODO: $* in non-pattern rules?
 
@@ -1024,17 +1082,17 @@ class PatternRule(object):
     def __init__(self, targetpatterns, prerequisites, doublecolon, loc):
         self.targetpatterns = targetpatterns
         self.prerequisites = prerequisites
         self.doublecolon = doublecolon
         self.loc = loc
         self.commands = []
 
     def addcommand(self, c):
-        assert isinstance(c, Expansion)
+        assert isinstance(c, (Expansion, StringExpansion))
         self.commands.append(c)
 
     def ismatchany(self):
         return util.any((t.ismatchany() for t in self.targetpatterns))
 
     def hasspecificmatch(self, file):
         for p in self.targetpatterns:
             if not p.ismatchany() and p.match(file) is not None:
--- a/pymake/functions.py
+++ b/pymake/functions.py
@@ -33,26 +33,26 @@ class Function(object):
         argc = len(self._arguments)
 
         if argc < self.minargs:
             raise data.DataError("Not enough arguments to function %s, requires %s" % (self.name, self.minargs), self.loc)
 
         assert self.maxargs == 0 or argc <= self.maxargs, "Parser screwed up, gave us too many args"
 
     def append(self, arg):
-        assert isinstance(arg, data.Expansion)
+        assert isinstance(arg, (data.Expansion, data.StringExpansion))
         self._arguments.append(arg)
 
     def __len__(self):
         return len(self._arguments)
 
 class VariableRef(Function):
     def __init__(self, loc, vname):
         self.loc = loc
-        assert isinstance(vname, data.Expansion)
+        assert isinstance(vname, (data.Expansion, data.StringExpansion))
         self.vname = vname
         
     def setup(self):
         assert False, "Shouldn't get here"
 
     def resolve(self, makefile, variables, setting):
         vname = self.vname.resolvestr(makefile, variables, setting)
         if vname in setting:
@@ -379,16 +379,17 @@ class IfFunction(Function):
 
     def setup(self):
         Function.setup(self)
         self._arguments[0].lstrip()
         self._arguments[0].rstrip()
 
     def resolve(self, makefile, variables, setting):
         condition = self._arguments[0].resolvestr(makefile, variables, setting)
+
         if len(condition):
             return self._arguments[1].resolve(makefile, variables, setting)
 
         if len(self._arguments) > 2:
             return self._arguments[2].resolve(makefile, variables, setting)
 
         return ()
 
@@ -454,16 +455,17 @@ class CallFunction(Function):
 
         v = data.Variables(parent=variables)
         v.set('0', data.Variables.FLAVOR_SIMPLE, data.Variables.SOURCE_AUTOMATIC, vname)
         for i in xrange(1, len(self._arguments)):
             param = self._arguments[i].resolvestr(makefile, variables, setting)
             v.set(str(i), data.Variables.FLAVOR_SIMPLE, data.Variables.SOURCE_AUTOMATIC, param)
 
         flavor, source, e = variables.get(vname)
+
         if e is None:
             return ()
 
         if flavor == data.Variables.FLAVOR_SIMPLE:
             log.warning("%s: calling variable '%s' which is simply-expanded" % (self.loc, vname))
 
         # but we'll do it anyway
         return e.resolve(makefile, v, setting + [vname])
--- a/pymake/parser.py
+++ b/pymake/parser.py
@@ -745,18 +745,17 @@ def parsemakesyntax(d, startat, stopon, 
             elif c in ('(', '{'):
                 closebrace = _matchingbrace[c]
 
                 # look forward for a function name
                 fname, offset = d.findtoken(offset + 1, _functiontokenlist, True)
                 if fname is not None:
                     fn = functions.functionmap[fname](loc)
                     e = data.Expansion()
-                    fn.append(e)
-                    if len(fn) == fn.maxargs:
+                    if len(fn) + 1 == fn.maxargs:
                         tokenlist = TokenList.get((c, closebrace, '$'))
                     else:
                         tokenlist = TokenList.get((',', c, closebrace, '$'))
 
                     stack.append(ParseStackFrame(PARSESTATE_FUNCTION,
                                                  e, tokenlist, function=fn,
                                                  openbrace=c, closebrace=closebrace))
                     di = iterfunc(d, offset, tokenlist)
@@ -781,68 +780,69 @@ def parsemakesyntax(d, startat, stopon, 
                                          TokenList.get((token, stacktop.closebrace,)),
                                          openbrace=token, closebrace=stacktop.closebrace, loc=d.getloc(tokenoffset)))
         elif stacktop.parsestate == PARSESTATE_PARENMATCH:
             assert token == stacktop.closebrace
             stacktop.expansion.appendstr(token)
             stack.pop()
         elif stacktop.parsestate == PARSESTATE_TOPLEVEL:
             assert len(stack) == 1
-            return stacktop.expansion, token, offset
+            return stacktop.expansion.finish(), token, offset
         elif stacktop.parsestate == PARSESTATE_FUNCTION:
             if token == ',':
+                stacktop.function.append(stacktop.expansion.finish())
+
                 stacktop.expansion = data.Expansion()
-                stacktop.function.append(stacktop.expansion)
-
-                if len(stacktop.function) == stacktop.function.maxargs:
+                if len(stacktop.function) + 1 == stacktop.function.maxargs:
                     tokenlist = TokenList.get((stacktop.openbrace, stacktop.closebrace, '$'))
                     stacktop.tokenlist = tokenlist
             elif token in (')', '}'):
-                    stacktop.function.setup()
-                    stack.pop()
-                    stack[-1].expansion.appendfunc(stacktop.function)
+                stacktop.function.append(stacktop.expansion.finish())
+                stacktop.function.setup()
+                stack.pop()
+                stack[-1].expansion.appendfunc(stacktop.function)
             else:
                 assert False, "Not reached, PARSESTATE_FUNCTION"
         elif stacktop.parsestate == PARSESTATE_VARNAME:
             if token == ':':
                 stacktop.varname = stacktop.expansion
                 stacktop.parsestate = PARSESTATE_SUBSTFROM
                 stacktop.expansion = data.Expansion()
                 stacktop.tokenlist = TokenList.get(('=', stacktop.openbrace, stacktop.closebrace, '$'))
             elif token in (')', '}'):
                 stack.pop()
-                stack[-1].expansion.appendfunc(functions.VariableRef(stacktop.loc, stacktop.expansion))
+                stack[-1].expansion.appendfunc(functions.VariableRef(stacktop.loc, stacktop.expansion.finish()))
             else:
                 assert False, "Not reached, PARSESTATE_VARNAME"
         elif stacktop.parsestate == PARSESTATE_SUBSTFROM:
             if token == '=':
                 stacktop.substfrom = stacktop.expansion
                 stacktop.parsestate = PARSESTATE_SUBSTTO
                 stacktop.expansion = data.Expansion()
                 stacktop.tokenlist = TokenList.get((stacktop.openbrace, stacktop.closebrace, '$'))
             elif token in (')', '}'):
                 # A substitution of the form $(VARNAME:.ee) is probably a mistake, but make
                 # parses it. Issue a warning. Combine the varname and substfrom expansions to
                 # make the compatible varname. See tests/var-substitutions.mk SIMPLE3SUBSTNAME
                 _log.warning("%s: Variable reference looks like substitution without =", stacktop.loc)
                 stacktop.varname.appendstr(':')
                 stacktop.varname.concat(stacktop.expansion)
                 stack.pop()
-                stack[-1].expansion.appendfunc(functions.VariableRef(stacktop.loc, stacktop.varname))
+                stack[-1].expansion.appendfunc(functions.VariableRef(stacktop.loc, stacktop.varname.finish()))
             else:
                 assert False, "Not reached, PARSESTATE_SUBSTFROM"
         elif stacktop.parsestate == PARSESTATE_SUBSTTO:
             assert token in  (')','}'), "Not reached, PARSESTATE_SUBSTTO"
 
             stack.pop()
-            stack[-1].expansion.appendfunc(functions.SubstitutionRef(stacktop.loc, stacktop.varname,
-                                                                     stacktop.substfrom, stacktop.expansion))
+            stack[-1].expansion.appendfunc(functions.SubstitutionRef(stacktop.loc, stacktop.varname.finish(),
+                                                                     stacktop.substfrom.finish(), stacktop.expansion.finish()))
         else:
             assert False, "Unexpected parse state %s" % stacktop.parsestate
 
         di = iterfunc(d, offset, stack[-1].tokenlist)
 
     if len(stack) != 1:
         raise SyntaxError("Unterminated function call", d.getloc(offset))
 
     assert stack[0].parsestate == PARSESTATE_TOPLEVEL
 
-    return stack[0].expansion, None, None
+    return stack[0].expansion.finish(), None, None
--- a/pymake/parserdata.py
+++ b/pymake/parserdata.py
@@ -102,18 +102,18 @@ class Override(Statement):
         print >>fd, indent, "Override: %r" % (self.s,)
 
 class DummyRule(object):
     def addcommand(self, r):
         pass
 
 class Rule(Statement):
     def __init__(self, targetexp, depexp, doublecolon):
-        assert isinstance(targetexp, data.Expansion)
-        assert isinstance(depexp, data.Expansion)
+        assert isinstance(targetexp, (data.Expansion, data.StringExpansion))
+        assert isinstance(depexp, (data.Expansion, data.StringExpansion))
         
         self.targetexp = targetexp
         self.depexp = depexp
         self.doublecolon = doublecolon
 
     def execute(self, makefile, context):
         atargets = data.stripdotslashes(self.targetexp.resolvesplit(makefile, makefile.variables))
         targets = [data.Pattern(p) for p in _expandwildcards(makefile, atargets)]
@@ -139,19 +139,19 @@ class Rule(Statement):
 
         context.currule = rule
 
     def dump(self, fd, indent):
         print >>fd, indent, "Rule %s: %s" % (self.targetexp, self.depexp)
 
 class StaticPatternRule(Statement):
     def __init__(self, targetexp, patternexp, depexp, doublecolon):
-        assert isinstance(targetexp, data.Expansion)
-        assert isinstance(patternexp, data.Expansion)
-        assert isinstance(depexp, data.Expansion)
+        assert isinstance(targetexp, (data.Expansion, data.StringExpansion))
+        assert isinstance(patternexp, (data.Expansion, data.StringExpansion))
+        assert isinstance(depexp, (data.Expansion, data.StringExpansion))
 
         self.targetexp = targetexp
         self.patternexp = patternexp
         self.depexp = depexp
         self.doublecolon = doublecolon
 
     def execute(self, makefile, context):
         targets = list(_expandwildcards(makefile, data.stripdotslashes(self.targetexp.resolvesplit(makefile, makefile.variables))))
@@ -180,31 +180,31 @@ class StaticPatternRule(Statement):
         makefile.foundtarget(targets[0])
         context.currule = rule
 
     def dump(self, fd, indent):
         print >>fd, indent, "StaticPatternRule %r: %r: %r" % (self.targetexp, self.patternexp, self.depexp)
 
 class Command(Statement):
     def __init__(self, exp):
-        assert isinstance(exp, data.Expansion)
+        assert isinstance(exp, (data.Expansion, data.StringExpansion))
         self.exp = exp
 
     def execute(self, makefile, context):
         assert context.currule is not None
         context.currule.addcommand(self.exp)
 
     def dump(self, fd, indent):
         print >>fd, indent, "Command %r" % (self.exp,)
 
 class SetVariable(Statement):
     def __init__(self, vnameexp, token, value, valueloc, targetexp, source=None):
-        assert isinstance(vnameexp, data.Expansion)
+        assert isinstance(vnameexp, (data.Expansion, data.StringExpansion))
         assert isinstance(value, str)
-        assert targetexp is None or isinstance(targetexp, data.Expansion)
+        assert targetexp is None or isinstance(targetexp, (data.Expansion, data.StringExpansion))
 
         if source is None:
             source = data.Variables.SOURCE_MAKEFILE
 
         self.vnameexp = vnameexp
         self.token = token
         self.value = value
         self.valueloc = valueloc
@@ -261,35 +261,35 @@ class Condition(object):
 
     def evaluate(self, makefile)
     """
 
 class EqCondition(Condition):
     expected = True
 
     def __init__(self, exp1, exp2):
-        assert isinstance(exp1, data.Expansion)
-        assert isinstance(exp2, data.Expansion)
+        assert isinstance(exp1, (data.Expansion, data.StringExpansion))
+        assert isinstance(exp2, (data.Expansion, data.StringExpansion))
 
         self.exp1 = exp1
         self.exp2 = exp2
 
     def evaluate(self, makefile):
         r1 = self.exp1.resolvestr(makefile, makefile.variables)
         r2 = self.exp2.resolvestr(makefile, makefile.variables)
         return (r1 == r2) == self.expected
 
     def __str__(self):
         return "ifeq (expected=%s) %r %r" % (self.expected, self.exp1, self.exp2)
 
 class IfdefCondition(Condition):
     expected = True
 
     def __init__(self, exp):
-        assert isinstance(exp, data.Expansion)
+        assert isinstance(exp, (data.Expansion, data.StringExpansion))
         self.exp = exp
 
     def evaluate(self, makefile):
         vname = self.exp.resolvestr(makefile, makefile.variables)
         flavor, source, value = makefile.variables.get(vname, expand=False)
 
         if value is None:
             return not self.expected
@@ -347,31 +347,31 @@ class ConditionBlock(Statement):
         for c, statements in self._groups:
             print >>fd, indent1, "Condition %s" % (c,)
             for s in statements:
                 s.dump(fd, indent2)
         print >>fd, indent, "~ConditionBlock"
 
 class Include(Statement):
     def __init__(self, exp, required):
-        assert isinstance(exp, data.Expansion)
+        assert isinstance(exp, (data.Expansion, data.StringExpansion))
         self.exp = exp
         self.required = required
 
     def execute(self, makefile, context):
         files = self.exp.resolvesplit(makefile, makefile.variables)
         for f in files:
             makefile.include(f, self.required, loc=self.exp.loc)
 
     def dump(self, fd, indent):
         print >>fd, indent, "Include %r" % (self.exp,)
 
 class VPathDirective(Statement):
     def __init__(self, exp):
-        assert isinstance(exp, data.Expansion)
+        assert isinstance(exp, (data.Expansion, data.StringExpansion))
         self.exp = exp
 
     def execute(self, makefile, context):
         words = list(data.stripdotslashes(self.exp.resolvesplit(makefile, makefile.variables)))
         if len(words) == 0:
             makefile.clearallvpaths()
         else:
             pattern = data.Pattern(words[0])
@@ -387,17 +387,17 @@ class VPathDirective(Statement):
                 if len(dirs):
                     makefile.addvpath(pattern, dirs)
 
     def dump(self, fd, indent):
         print >>fd, indent, "VPath %r" % (self.exp,)
 
 class ExportDirective(Statement):
     def __init__(self, exp, single):
-        assert isinstance(exp, data.Expansion)
+        assert isinstance(exp, (data.Expansion, data.StringExpansion))
         self.exp = exp
         self.single = single
 
     def execute(self, makefile, context):
         if self.single:
             vlist = [self.exp.resolvestr(makefile, makefile.variables)]
         else:
             vlist = list(self.exp.resolvesplit(makefile, makefile.variables))
@@ -407,17 +407,17 @@ class ExportDirective(Statement):
         for v in vlist:
             makefile.exportedvars.add(v)
 
     def dump(self, fd, indent):
         print >>fd, indent, "Export (single=%s) %r" % (self.single, self.exp)
 
 class EmptyDirective(Statement):
     def __init__(self, exp):
-        assert isinstance(exp, data.Expansion)
+        assert isinstance(exp, (data.Expansion, data.StringExpansion))
         self.exp = exp
 
     def execute(self, makefile, context):
         v = self.exp.resolvestr(makefile, makefile.variables)
         if v.strip() != '':
             raise data.DataError("Line expands to non-empty value", self.exp.loc)
 
     def dump(self, fd, indent):
--- a/tests/var-set.mk
+++ b/tests/var-set.mk
@@ -18,28 +18,32 @@ IMMVAR += $(RECVAR)
 BASIC ?= notval
 
 all: BASIC = valall
 all: RECVAR += $(BASIC)
 all: IMMVAR += $(BASIC)
 all: UNSET += more
 all: OBASIC += allmore
 
+CHECKLIT = $(NULL) check
+all: CHECKLIT += appendliteral
+
 RECVAR = blimey
 
 TESTEMPTY = \
 	$(NULL)
 
 all: other
 	test "$(TEST2)" = "val"
 	test '$(value TEST2)' = '$$(TES T)'
 	test "$(RECVAR)" = "blimey valall"
 	test "$(IMMVAR)" = "bloo foo var baz  valall"
 	test "$(UNSET)" = "more"
 	test "$(OBASIC)" = "oval"
+	test "$(CHECKLIT)" = " check appendliteral"
 	test "$(TESTEMPTY)" = ""
 	@echo TEST-PASS
 
 OVAR = oval
 OVAR ?= onotval
 
 other: OVAR ?= ooval
 other: LATERVAR ?= lateroverride