Optimize out N*M suffix matching in Builder.py.
[scons.git] / src / engine / SCons / Builder.py
index e6e7822094ee3394bcb2a4599e49b9c87466afee..8d99a32583041ec717a5df432bf512713ca5b9a0 100644 (file)
@@ -126,6 +126,7 @@ import SCons.Action
 from SCons.Debug import logInstanceCreation
 from SCons.Errors import InternalError, UserError
 import SCons.Executor
+import SCons.Node
 import SCons.Node.FS
 import SCons.Util
 import SCons.Warnings
@@ -221,6 +222,7 @@ class OverrideWarner(UserDict.UserDict):
     """
     def __init__(self, dict):
         UserDict.UserDict.__init__(self, dict)
+        if __debug__: logInstanceCreation(self, 'Builder.OverrideWarner')
         self.already_warned = None
     def warn(self):
         if self.already_warned:
@@ -274,7 +276,7 @@ def Builder(**kw):
 
     return ret
 
-def _init_nodes(builder, env, overrides, tlist, slist):
+def _init_nodes(builder, env, overrides, executor_kw, tlist, slist):
     """Initialize lists of target and source nodes with all of
     the proper Builder information.
     """
@@ -284,32 +286,28 @@ def _init_nodes(builder, env, overrides, tlist, slist):
     for t in tlist:
         if t.side_effect:
             raise UserError, "Multiple ways to build the same target were specified for: %s" % str(t)
-        if t.has_builder():
+        if t.has_explicit_builder():
             if not t.env is None and not t.env is env:
                 t_contents = t.builder.action.get_contents(tlist, slist, t.env)
                 contents = t.builder.action.get_contents(tlist, slist, env)
 
                 if t_contents == contents:
                     SCons.Warnings.warn(SCons.Warnings.DuplicateEnvironmentWarning,
-                                        "Two different environments were specified for target %s,\n\tbut they appear to have the same action: %s"%(str(t), t.builder.action.strfunction(tlist, slist, t.env)))
+                                        "Two different environments were specified for target %s,\n\tbut they appear to have the same action: %s"%(str(t), t.builder.action.genstring(tlist, slist, t.env)))
 
                 else:
                     raise UserError, "Two environments with different actions were specified for the same target: %s"%str(t)
 
-            elif t.overrides != overrides:
-                raise UserError, "Two different sets of overrides were specified for the same target: %s"%str(t)
-
-            elif builder.target_scanner and t.target_scanner and builder.target_scanner != t.target_scanner:
-                raise UserError, "Two different scanners were specified for the same target: %s"%str(t)
-
             if builder.multi:
                 if t.builder != builder:
                     if isinstance(t.builder, ListBuilder) and isinstance(builder, ListBuilder) and t.builder.builder == builder.builder:
                         raise UserError, "Two different target sets have a target in common: %s"%str(t)
                     else:
                         raise UserError, "Two different builders (%s and %s) were specified for the same target: %s"%(t.builder.get_name(env), builder.get_name(env), str(t))
+                elif isinstance(t.builder, ListBuilder) ^ isinstance(builder, ListBuilder):
+                    raise UserError, "Cannot build same target `%s' as singular and list"%str(t)
             elif t.sources != slist:
-                raise UserError, "Multiple ways to build the same target were specified for: %s" % str(t)
+                raise UserError, "Multiple ways to build the same target were specified for: %s  (from %s and from %s)" % (str(t), map(str,t.sources), map(str,slist))
 
     if builder.single_source:
         if len(slist) > 1:
@@ -327,36 +325,23 @@ def _init_nodes(builder, env, overrides, tlist, slist):
         else:
             executor.add_sources(slist)
     if executor is None:
+        if not builder.action:
+            raise UserError, "Builder %s must have an action to build %s."%(builder.get_name(env or builder.env), map(str,tlist))
         executor = SCons.Executor.Executor(builder.action,
                                            env or builder.env,
-                                           [builder.overrides, overrides],
+                                           [],  # env already has overrides
                                            tlist,
-                                           slist)
+                                           slist,
+                                           executor_kw)
 
     # Now set up the relevant information in the target Nodes themselves.
     for t in tlist:
-        t.overrides = overrides
         t.cwd = SCons.Node.FS.default_fs.getcwd()
         t.builder_set(builder)
         t.env_set(env)
         t.add_source(slist)
         t.set_executor(executor)
-        if builder.target_scanner:
-            t.target_scanner = builder.target_scanner
-        if t.source_scanner is None:
-            t.source_scanner = builder.source_scanner
-
-    # Add backup source scanners from the environment to the source
-    # nodes.  This may not be necessary if the node will have a real
-    # source scanner added later (which is why these are the "backup"
-    # source scanners, not the real ones), but because source nodes may
-    # be used multiple times for different targets, it ends up being
-    # more efficient to do this calculation once here, as opposed to
-    # delaying it until later when we potentially have to calculate it
-    # over and over and over.
-    for s in slist:
-        if s.source_scanner is None and s.backup_source_scanner is None:
-            s.backup_source_scanner = env.get_scanner(s.scanner_key())
+        t.set_explicit(builder.is_explicit)
 
 class EmitterProxy:
     """This is a callable class that can act as a
@@ -393,6 +378,8 @@ class BuilderBase:
     nodes (files) from input nodes (files).
     """
 
+    __metaclass__ = SCons.Memoize.Memoized_Metaclass
+
     def __init__(self,  action = None,
                         prefix = '',
                         suffix = '',
@@ -405,8 +392,11 @@ class BuilderBase:
                         multi = 0,
                         env = None,
                         single_source = 0,
+                        name = None,
+                        chdir = _null,
+                        is_explicit = 1,
                         **overrides):
-        if __debug__: logInstanceCreation(self, 'BuilderBase')
+        if __debug__: logInstanceCreation(self, 'Builder.BuilderBase')
         self.action = SCons.Action.Action(action)
         self.multi = multi
         if SCons.Util.is_Dict(prefix):
@@ -423,6 +413,11 @@ class BuilderBase:
                 "\tspecify the items as keyword arguments to the Builder() call instead.")
             overrides.update(overrides['overrides'])
             del overrides['overrides']
+        if overrides.has_key('scanner'):
+            SCons.Warnings.warn(SCons.Warnings.DeprecatedWarning,
+                                "The \"scanner\" keyword to Builder() creation has been deprecated;\n"
+                                "\tuse: source_scanner or target_scanner as appropriate.")
+            del overrides['scanner']
         self.overrides = overrides
 
         self.set_src_suffix(src_suffix)
@@ -434,6 +429,15 @@ class BuilderBase:
 
         self.emitter = emitter
 
+        # Optional Builder name should only be used for Builders
+        # that don't get attached to construction environments.
+        if name:
+            self.name = name
+        self.executor_kw = {}
+        if not chdir is _null:
+            self.executor_kw['chdir'] = chdir
+        self.is_explicit = is_explicit
+
     def __nonzero__(self):
         raise InternalError, "Do not test for the Node.builder attribute directly; use Node.has_builder() instead"
 
@@ -442,18 +446,30 @@ class BuilderBase:
 
         Look at the BUILDERS variable of env, expecting it to be a
         dictionary containing this Builder, and return the key of the
-        dictionary."""
+        dictionary.  If there's no key, then return a directly-configured
+        name (if there is one) or the name of the class (by default)."""
 
         try:
             index = env['BUILDERS'].values().index(self)
             return env['BUILDERS'].keys()[index]
         except (AttributeError, KeyError, ValueError):
-            return str(self.__class__)
+            try:
+                return self.name
+            except AttributeError:
+                return str(self.__class__)
 
     def __cmp__(self, other):
         return cmp(self.__dict__, other.__dict__)
 
-    def splitext(self, path):
+    def splitext(self, path, env=None):
+        if not env:
+            env = self.env
+        if env:
+            matchsuf = filter(lambda S,path=path: path[-len(S):] == S,
+                              self.src_suffixes(env))
+            if matchsuf:
+                suf = max(map(None, map(len, matchsuf), matchsuf))[1]
+                return [path[:-len(suf)], path[-len(suf):]]
         return SCons.Util.splitext(path)
 
     def _create_nodes(self, env, overwarn, target = None, source = None):
@@ -474,8 +490,6 @@ class BuilderBase:
 
         overwarn.warn()
 
-        env = env.Override(overwarn.data)
-
         src_suf = self.get_src_suffix(env)
 
         source = _adjustixes(source, None, src_suf)
@@ -489,7 +503,8 @@ class BuilderBase:
                 t_from_s = slist[0].target_from_source
             except AttributeError:
                 raise UserError("Do not know how to create a target from source `%s'" % slist[0])
-            tlist = [ t_from_s(pre, suf, self.splitext) ]
+            splitext = lambda S,self=self,env=env: self.splitext(S,env)
+            tlist = [ t_from_s(pre, suf, splitext) ]
         else:
             target = _adjustixes(target, pre, suf)
             tlist = env.arg2nodes(target, self.target_factory)
@@ -503,7 +518,7 @@ class BuilderBase:
             new_targets = []
             for t in tlist:
                 if not t.is_derived():
-                    t.builder = self
+                    t.builder_set(self)
                     new_targets.append(t)
 
             target, source = self.emitter(target=tlist, source=slist, env=env)
@@ -515,7 +530,7 @@ class BuilderBase:
                 if t.builder is self:
                     # Only delete the temporary builder if the emitter
                     # didn't change it on us.
-                    t.builder = None
+                    t.builder_set(None)
 
             # Have to call arg2nodes yet again, since it is legal for
             # emitters to spit out strings as well as Node instances.
@@ -524,23 +539,15 @@ class BuilderBase:
 
         return tlist, slist
 
-    def _execute(self, env, target = None, source = _null, overwarn={}):
-        if source is _null:
-            source = target
-            target = None
-
-        if(self.single_source and
-           SCons.Util.is_List(source) and
-           len(source) > 1 and
-           target is None):
+    def _execute(self, env, target, source, overwarn={}, executor_kw={}):
+        # We now assume that target and source are lists or None.
+        if self.single_source and len(source) > 1 and target is None:
             result = []
             if target is None: target = [None]*len(source)
-            for k in range(len(source)):
-                t = self._execute(env, target[k], source[k], overwarn)
-                if SCons.Util.is_List(t):
-                    result.extend(t)
-                else:
-                    result.append(t)
+            for tgt, src in zip(target, source):
+                if not tgt is None: tgt = [tgt]
+                if not src is None: src = [src]
+                result.extend(self._execute(env, tgt, src, overwarn))
             return result
         
         tlist, slist = self._create_nodes(env, overwarn, target, source)
@@ -549,12 +556,29 @@ class BuilderBase:
             builder = self
         else:
             builder = ListBuilder(self, env, tlist)
-        _init_nodes(builder, env, overwarn.data, tlist, slist)
+        _init_nodes(builder, env, overwarn.data, executor_kw, tlist, slist)
 
-        return tlist
+        return SCons.Node.NodeList(tlist)
 
-    def __call__(self, env, target = None, source = _null, **kw):
-        return self._execute(env, target, source, OverrideWarner(kw))
+    def __call__(self, env, target=None, source=None, chdir=_null, **kw):
+        # We now assume that target and source are lists or None.
+        # The caller (typically Environment.BuilderWrapper) is
+        # responsible for converting any scalar values to lists.
+        if chdir is _null:
+            ekw = self.executor_kw
+        else:
+            ekw = self.executor_kw.copy()
+            ekw['chdir'] = chdir
+        if kw:
+            if self.overrides:
+                env_kw = self.overrides.copy()
+                env_kw.update(kw)
+            else:
+                env_kw = kw
+        else:
+            env_kw = self.overrides
+        env = env.Override(env_kw)
+        return self._execute(env, target, source, OverrideWarner(kw), ekw)
 
     def adjust_suffix(self, suff):
         if suff and not suff[0] in [ '.', '_', '$' ]:
@@ -610,13 +634,21 @@ class BuilderBase:
         """
         self.emitter[suffix] = emitter
 
+if not SCons.Memoize.has_metaclass:
+    _Base = BuilderBase
+    class BuilderBase(SCons.Memoize.Memoizer, _Base):
+        "Cache-backed version of BuilderBase"
+        def __init__(self, *args, **kw):
+            apply(_Base.__init__, (self,)+args, kw)
+            SCons.Memoize.Memoizer.__init__(self)
+
 class ListBuilder(SCons.Util.Proxy):
     """A Proxy to support building an array of targets (for example,
     foo.o and foo.h from foo.y) from a single Action execution.
     """
 
     def __init__(self, builder, env, tlist):
-        if __debug__: logInstanceCreation(self)
+        if __debug__: logInstanceCreation(self, 'Builder.ListBuilder')
         SCons.Util.Proxy.__init__(self, builder)
         self.builder = builder
         self.target_scanner = builder.target_scanner
@@ -631,9 +663,6 @@ class ListBuilder(SCons.Util.Proxy):
         """
         return self.tlist
 
-    def __cmp__(self, other):
-        return cmp(self.__dict__, other.__dict__)
-
     def get_name(self, env):
         """Attempts to get the name of the Builder."""
 
@@ -661,7 +690,7 @@ class MultiStepBuilder(BuilderBase):
                         source_scanner = None,
                         emitter=None,
                         single_source=0):
-        if __debug__: logInstanceCreation(self)
+        if __debug__: logInstanceCreation(self, 'Builder.MultiStepBuilder')
         BuilderBase.__init__(self, action, prefix, suffix, src_suffix,
                              target_factory, source_factory,
                              target_scanner, source_scanner, emitter,
@@ -669,54 +698,54 @@ class MultiStepBuilder(BuilderBase):
         if not SCons.Util.is_List(src_builder):
             src_builder = [ src_builder ]
         self.src_builder = src_builder
-        self.sdict = {}
-        self.cached_src_suffixes = {} # source suffixes keyed on id(env)
-
-    def _execute(self, env, target = None, source = _null, overwarn={}):
-        if source is _null:
-            source = target
-            target = None
 
+    def _get_sdict(self, env):
+        "__cacheable__"
+        sdict = {}
+        for bld in self.src_builder:
+            if SCons.Util.is_String(bld):
+                try:
+                    bld = env['BUILDERS'][bld]
+                except KeyError:
+                    continue
+            for suf in bld.src_suffixes(env):
+                sdict[suf] = bld
+        return sdict
+        
+    def _execute(self, env, target, source, overwarn={}, executor_kw={}):
+        # We now assume that target and source are lists or None.
         slist = env.arg2nodes(source, self.source_factory)
         final_sources = []
 
-        try:
-            sdict = self.sdict[id(env)]
-        except KeyError:
-            sdict = {}
-            self.sdict[id(env)] = sdict
-            for bld in self.src_builder:
-                if SCons.Util.is_String(bld):
-                    try:
-                        bld = env['BUILDERS'][bld]
-                    except KeyError:
-                        continue
-                for suf in bld.src_suffixes(env):
-                    sdict[suf] = bld
+        sdict = self._get_sdict(env)
 
         src_suffixes = self.src_suffixes(env)
 
+        def match_src_suffix(node, src_suffixes=src_suffixes):
+            # This reaches directly into the Node.name attribute (instead
+            # of using an accessor function) for performance reasons.
+            return filter(lambda s, n=node.name:
+                                 n[-len(s):] == s,
+                          src_suffixes)
+
         for snode in slist:
-            try:
-                get_suffix = snode.get_suffix
-            except AttributeError:
-                ext = self.splitext(str(snode))
+            name = snode.name
+            match = match_src_suffix(snode)
+            if match:
+                try:
+                    bld = sdict[match[0]]
+                except KeyError:
+                    final_sources.append(snode)
+                else:
+                    tlist = bld._execute(env, None, [snode], overwarn)
+                    # If the subsidiary Builder returned more than one
+                    # target, then filter out any sources that this
+                    # Builder isn't capable of building.
+                    if len(tlist) > 1:
+                        tlist = filter(match_src_suffix, tlist)
+                    final_sources.extend(tlist)
             else:
-                ext = get_suffix()
-            try:
-                subsidiary_builder = sdict[ext]
-            except KeyError:
                 final_sources.append(snode)
-            else:
-                tgt = subsidiary_builder._execute(env, None, snode, overwarn)
-                # If the subsidiary Builder returned more than one target,
-                # then filter out any sources that this Builder isn't
-                # capable of building.
-                if len(tgt) > 1:
-                    tgt = filter(lambda x, self=self, suf=src_suffixes:
-                                 self.splitext(SCons.Util.to_String(x))[1] in suf,
-                                 tgt)
-                final_sources.extend(tgt)
 
         return BuilderBase._execute(self, env, target, final_sources, overwarn)
 
@@ -740,15 +769,12 @@ class MultiStepBuilder(BuilderBase):
     def src_suffixes(self, env):
         """Return a list of the src_suffix attributes for all
         src_builders of this Builder.
+        __cacheable__
         """
-        try:
-            return self.cached_src_suffixes[id(env)]
-        except KeyError:
-            suffixes = BuilderBase.src_suffixes(self, env)
-            for builder in self.get_src_builders(env):
-                suffixes.extend(builder.src_suffixes(env))
-            self.cached_src_suffixes[id(env)] = suffixes
-            return suffixes
+        suffixes = BuilderBase.src_suffixes(self, env)
+        for builder in self.get_src_builders(env):
+            suffixes.extend(builder.src_suffixes(env))
+        return suffixes
 
 class CompositeBuilder(SCons.Util.Proxy):
     """A Builder Proxy whose main purpose is to always have
@@ -757,7 +783,7 @@ class CompositeBuilder(SCons.Util.Proxy):
     """
 
     def __init__(self, builder, cmdgen):
-        if __debug__: logInstanceCreation(self)
+        if __debug__: logInstanceCreation(self, 'Builder.CompositeBuilder')
         SCons.Util.Proxy.__init__(self, builder)
 
         # cmdgen should always be an instance of DictCmdGenerator.
@@ -767,6 +793,3 @@ class CompositeBuilder(SCons.Util.Proxy):
     def add_action(self, suffix, action):
         self.cmdgen.add_action(suffix, action)
         self.set_src_suffix(self.cmdgen.src_suffixes())
-
-    def __cmp__(self, other):
-        return cmp(self.__dict__, other.__dict__)