Merged revisions 1441-1539 via svnmerge from

http://scons.tigris.org/svn/scons/branches/core

........
  r1441 | stevenknight | 2006-04-22 23:06:53 -0400 (Sat, 22 Apr 2006) | 1 line

  0.96.D397 - The scons command, branch 0.96.91.
........
  r1442 | stevenknight | 2006-04-27 00:45:12 -0400 (Thu, 27 Apr 2006) | 1 line

  0.96.D398 - The scons command, branch 0.96.92.
........
  r1443 | stevenknight | 2006-04-27 00:49:25 -0400 (Thu, 27 Apr 2006) | 1 line

  0.96.D399 - Taskmaster clean-ups in anticipation of refactoring speedups.
........
  r1450 | stevenknight | 2006-05-02 00:04:55 -0400 (Tue, 02 May 2006) | 1 line

  0.96.D400 - Fix VC+++ 2005 Express detection. (Atul Varma) Fix parsing Intel C compiler Li
........
  r1451 | stevenknight | 2006-05-02 01:14:24 -0400 (Tue, 02 May 2006) | 1 line

  0.96.D401 - Enhance ParseConfig() to understand -arch and -isysroot options. (Gary Oberbrun
........
  r1458 | stevenknight | 2006-05-02 23:21:04 -0400 (Tue, 02 May 2006) | 1 line

  0.96.D402 - Make strfunction handling consistent. (David Gruener)
........
  r1459 | stevenknight | 2006-05-02 23:37:08 -0400 (Tue, 02 May 2006) | 1 line

  0.96.D403 - Comment out the test of CVS checkout from the old tigris.org repository.
........
  r1460 | stevenknight | 2006-05-03 23:47:54 -0400 (Wed, 03 May 2006) | 1 line

  0.96.D404 - Preserve white space in display Action string. (David Gruener)
........
  r1461 | stevenknight | 2006-05-04 09:16:15 -0400 (Thu, 04 May 2006) | 1 line

  0.96.D405 - Add MergeFlags() and AddFlags() methods. (Greg Noel) Support recognizing compi
........
  r1462 | stevenknight | 2006-05-04 23:46:53 -0400 (Thu, 04 May 2006) | 1 line

  0.96.D406 - Fix stack trace when ParseFlags has a null string.
........
  r1464 | stevenknight | 2006-05-05 17:21:27 -0400 (Fri, 05 May 2006) | 1 line

  0.96.D408 - Fix the string displayed by InstallAs() when called through the default construc
........
  r1465 | stevenknight | 2006-05-05 18:30:28 -0400 (Fri, 05 May 2006) | 1 line

  0.96.D409 - Fix test/ParseConfig.py, broken in the previous checkin by ParseFlags() changes.
........
  r1466 | stevenknight | 2006-05-05 20:42:35 -0400 (Fri, 05 May 2006) | 1 line

  0.96.D407 - Avoid recursive calls to main() in SConf test programs. (Karol Pietrzak)
........
  r1467 | stevenknight | 2006-05-06 00:27:21 -0400 (Sat, 06 May 2006) | 1 line

  0.96.D410 - Catch errors from commands that ParseConfig() calls. (John Pye)
........
  r1468 | stevenknight | 2006-05-06 10:55:38 -0400 (Sat, 06 May 2006) | 1 line

  0.96.D411 - Significant taskmaster speedup by using reference counts, not list manipulation.
........
  r1469 | stevenknight | 2006-05-06 18:38:02 -0400 (Sat, 06 May 2006) | 1 line

  0.96.D413 - TeX improvements.
........
  r1471 | stevenknight | 2006-05-07 09:07:58 -0400 (Sun, 07 May 2006) | 2 lines

  Delete properties interfering with clean .jpg checkout.
........
  r1472 | stevenknight | 2006-05-07 09:23:54 -0400 (Sun, 07 May 2006) | 1 line

  0.96.D412 - Windows portability fixes for two tests and ParseConfig() execution.
........
  r1473 | stevenknight | 2006-05-07 09:30:11 -0400 (Sun, 07 May 2006) | 1 line

  0.96.D414 - Various man page and documentation updates.
........
  r1474 | stevenknight | 2006-05-07 23:53:12 -0400 (Sun, 07 May 2006) | 1 line

  0.96.D415 - Initial infrastructure for executing tests under QMTest. (Stefan Seefeld)
........
  r1476 | stevenknight | 2006-05-09 00:03:47 -0400 (Tue, 09 May 2006) | 1 line

  0.96.D416 - Fix QMTest infrastructure to avoid listing directories with no tests and to find
........
  r1477 | stevenknight | 2006-05-16 06:47:51 -0400 (Tue, 16 May 2006) | 1 line

  0.96.D417 - Fix Alias turning Entries into Nodes or Dirs too soon.
........
  r1478 | stevenknight | 2006-05-17 08:32:58 -0400 (Wed, 17 May 2006) | 1 line

  0.96.D418 - Next QMTest changes (including fixing copyrights).
........
  r1479 | stevenknight | 2006-05-18 05:07:06 -0400 (Thu, 18 May 2006) | 1 line

  0.96.D419 - Fix DVIPDF tests after recent changes.
........
  r1497 | stevenknight | 2006-05-23 08:47:01 -0400 (Tue, 23 May 2006) | 1 line

  0.96.D420 - Better error message when trying to build a file from an unknown sufix. (Gary O
........
  r1498 | stevenknight | 2006-05-23 09:38:52 -0400 (Tue, 23 May 2006) | 1 line

  0.96.D421 - Suppress duplicate entries in latest TeX patch. (Joel B. Mohler)
........
  r1499 | stevenknight | 2006-05-23 22:00:06 -0400 (Tue, 23 May 2006) | 1 line

  0.96.D422 - Add tests for tuple variable expansion. (Gary Oberbrunner)
........
  r1515 | stevenknight | 2006-06-12 06:44:24 -0400 (Mon, 12 Jun 2006) | 1 line

  0.96.D423 - More QMTest work: start giving runtest.py its own tests, more functionality for
........
  r1517 | stevenknight | 2006-06-21 07:34:30 -0400 (Wed, 21 Jun 2006) | 1 line

  0.96.D424 - Move test/Configure.py and test/Options.py to avoid confusion with similarly-nam
........
  r1518 | stevenknight | 2006-06-21 12:40:37 -0400 (Wed, 21 Jun 2006) | 1 line

  0.96.D425 - Change the QMTest infrastructure to use File naming, not Python. Rename tests w
........
  r1533 | stevenknight | 2006-07-23 20:10:08 -0400 (Sun, 23 Jul 2006) | 1 line

  0.96.D426 - Fix ramifications of changing when Node disambiguation happens.
........
  r1535 | stevenknight | 2006-07-24 06:40:43 -0400 (Mon, 24 Jul 2006) | 3 lines

  Initialized merge tracking via "svnmerge" with revisions "1-1534" from
  http://scons.tigris.org/svn/scons/trunk
........
  r1536 | stevenknight | 2006-07-24 21:45:40 -0400 (Mon, 24 Jul 2006) | 2 lines

  Remove svnmerge-integrated property to start over.
........
  r1538 | stevenknight | 2006-07-24 21:51:32 -0400 (Mon, 24 Jul 2006) | 3 lines

  Initialized merge tracking via "svnmerge" with revisions "1-1440" from
  http://scons.tigris.org/svn/scons/trunk
........

1 files changed, 136 insertions, 106 deletions

diff --git a/src/engine/SCons/Taskmaster.py b/src/engine/SCons/Taskmaster.py
index ecd6b07..7cdecf3 100644
--- a/src/engine/SCons/Taskmaster.py
+++ b/src/engine/SCons/Taskmaster.py
@@ -1,9 +1,3 @@
-"""SCons.Taskmaster
-
-Generic Taskmaster.
-
-"""
-
 #
 # __COPYRIGHT__
 #
@@ -27,6 +21,32 @@ Generic Taskmaster.
 # WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 #
 
+__doc__ = """
+Generic Taskmaster module for the SCons build engine.
+
+This module contains the primary interface(s) between a wrapping user
+interface and the SCons build engine.  There are two key classes here:
+
+    Taskmaster
+        This is the main engine for walking the dependency graph and
+        calling things to decide what does or doesn't need to be built.
+
+    Task
+        This is the base class for allowing a wrapping interface to
+        decide what does or doesn't actually need to be done.  The
+        intention is for a wrapping interface to subclass this as
+        appropriate for different types of behavior it may need.
+
+        The canonical example is the SCons native Python interface,
+        which has Task subclasses that handle its specific behavior,
+        like printing "`foo' is up to date" when a top-level target
+        doesn't need to be built, and handling the -c option by removing
+        targets as its "build" action.
+
+        The Taskmaster instantiates a Task object for each (set of)
+        target(s) that it decides need to be evaluated and/or built.
+"""
+
 __revision__ = "__FILE__ __REVISION__ __DATE__ __DEVELOPER__"
 
 import string
@@ -36,6 +56,8 @@ import traceback
 import SCons.Node
 import SCons.Errors
 
+StateString = SCons.Node.StateString
+
 # A subsystem for recording stats about how different Nodes are handled by
 # the main Taskmaster loop.  There's no external control here (no need for
 # a --debug= option); enable it by changing the value of CollectStats.
@@ -43,12 +65,22 @@ import SCons.Errors
 CollectStats = None
 
 class Stats:
+    """
+    A simple class for holding statistics about the disposition of a
+    Node by the Taskmaster.  If we're collecting statistics, each Node
+    processed by the Taskmaster gets one of these attached, in which
+    the Taskmaster records its decision each time it processes the Node.
+    (Ideally, that's just once per Node.)
+    """
     def __init__(self):
+        """
+        Instantiates a Taskmaster.Stats object, initializing all
+        appropriate counters to zero.
+        """
         self.considered  = 0
         self.already_handled  = 0
         self.problem  = 0
         self.child_failed  = 0
-        self.not_started  = 0
         self.not_built  = 0
         self.side_effects  = 0
         self.build  = 0
@@ -59,7 +91,6 @@ fmt = "%(considered)3d "\
       "%(already_handled)3d " \
       "%(problem)3d " \
       "%(child_failed)3d " \
-      "%(not_started)3d " \
       "%(not_built)3d " \
       "%(side_effects)3d " \
       "%(build)3d "
@@ -118,6 +149,11 @@ class Task:
             for s in t.side_effects:
                 s.prepare()
 
+    def get_target(self):
+        """Fetch the target being built or updated by this task.
+        """
+        return self.node
+
     def execute(self):
         """Called to execute the task.
 
@@ -146,11 +182,6 @@ class Task:
             raise SCons.Errors.TaskmasterException(self.targets[0],
                                                    sys.exc_info())
 
-    def get_target(self):
-        """Fetch the target being built or updated by this task.
-        """
-        return self.node
-
     def executed(self):
         """Called when the task has been successfully executed.
 
@@ -161,8 +192,6 @@ class Task:
         back on the pending list."""
         for t in self.targets:
             if t.get_state() == SCons.Node.executing:
-                for side_effect in t.side_effects:
-                    side_effect.set_state(SCons.Node.no_state)
                 t.set_state(SCons.Node.executed)
                 t.built()
             else:
@@ -179,15 +208,13 @@ class Task:
         for t in self.targets:
             t.set_state(SCons.Node.failed)
         self.tm.failed(self.node)
-        next_top = self.tm.next_top_level_candidate()
         self.tm.stop()
 
-        if next_top:
-            # We're stopping because of a build failure, but give the
-            # calling Task class a chance to postprocess() the top-level
-            # target under which the build failure occurred.
-            self.targets = [next_top]
-            self.top = 1
+        # We're stopping because of a build failure, but give the
+        # calling Task class a chance to postprocess() the top-level
+        # target under which the build failure occurred.
+        self.targets = [self.tm.current_top]
+        self.top = 1
 
     def fail_continue(self):
         """Explicit continue-the-build failure.
@@ -211,9 +238,9 @@ class Task:
         """
         self.out_of_date = self.targets[:]
         for t in self.targets:
+            t.disambiguate().set_state(SCons.Node.executing)
             for s in t.side_effects:
-                s.set_state(SCons.Node.executing)
-            t.set_state(SCons.Node.executing)
+                s.set_state(SCons.Node.pending)
 
     def make_ready_current(self):
         """Mark all targets in a task ready for execution if any target
@@ -227,14 +254,32 @@ class Task:
                 t.set_state(SCons.Node.up_to_date)
             else:
                 self.out_of_date.append(t)
-                for s in t.side_effects:
-                    s.set_state(SCons.Node.executing)
                 t.set_state(SCons.Node.executing)
+                for s in t.side_effects:
+                    s.set_state(SCons.Node.pending)
 
     make_ready = make_ready_current
 
     def postprocess(self):
         """Post process a task after it's been executed."""
+        parents = {}
+        for t in self.targets:
+            for p in t.waiting_parents.keys():
+                parents[p] = parents.get(p, 0) + 1
+        for t in self.targets:
+            for s in t.side_effects:
+                if s.get_state() == SCons.Node.pending:
+                    s.set_state(SCons.Node.no_state)
+                    for p in s.waiting_parents.keys():
+                        if not parents.has_key(p):
+                            parents[p] = 1
+                for p in s.waiting_s_e.keys():
+                    if p.ref_count == 0:
+                        self.tm.candidates.append(p)
+        for p, subtract in parents.items():
+            p.ref_count = p.ref_count - subtract
+            if p.ref_count == 0:
+                self.tm.candidates.append(p)
         for t in self.targets:
             t.postprocess()
 
@@ -265,6 +310,17 @@ def order(dependencies):
     return dependencies
 
 
+def find_cycle(stack):
+    if stack[0] == stack[-1]:
+        return stack
+    for n in stack[-1].waiting_parents.keys():
+        stack.append(n)
+        if find_cycle(stack):
+            return stack
+        stack.pop()
+    return None
+
+
 class Taskmaster:
     """A generic Taskmaster for handling a bunch of targets.
 
@@ -273,25 +329,36 @@ class Taskmaster:
     """
 
     def __init__(self, targets=[], tasker=Task, order=order, trace=None):
-        self.targets = targets # top level targets
-        self.candidates = targets[:] # nodes that might be ready to be executed
-        self.candidates.reverse()
-        self.executing = [] # nodes that are currently executing
-        self.pending = [] # nodes that depend on a currently executing node
+        self.top_targets = targets[:]
+        self.top_targets.reverse()
+        self.candidates = []
         self.tasker = tasker
         self.ready = None # the next task that is ready to be executed
         self.order = order
         self.message = None
         self.trace = trace
+        self.next_candidate = self.find_next_candidate
 
-        # See if we can alter the target list to find any
-        # corresponding targets in linked build directories
-        for node in self.targets:
-            alt, message = node.alter_targets()
-            if alt:
-                self.message = message
-                self.candidates.extend(self.order(alt))
-                continue
+    def find_next_candidate(self):
+        try:
+            return self.candidates.pop()
+        except IndexError:
+            pass
+        try:
+            node = self.top_targets.pop()
+        except IndexError:
+            return None
+        self.current_top = node
+        alt, message = node.alter_targets()
+        if alt:
+            self.message = message
+            self.candidates.append(node)
+            self.candidates.extend(self.order(alt))
+            node = self.candidates.pop()
+        return node
+
+    def no_next_candidate(self):
+        return None
 
     def _find_next_ready_node(self):
         """Find the next node that is ready to be built"""
@@ -303,8 +370,13 @@ class Taskmaster:
 
         T = self.trace
 
-        while self.candidates:
-            node = self.candidates.pop().disambiguate()
+        while 1:
+            node = self.next_candidate()
+            if node is None:
+                self.ready = None
+                break
+
+            node = node.disambiguate()
             state = node.get_state()
 
             if CollectStats:
@@ -318,14 +390,14 @@ class Taskmaster:
 
             if T: T.write('Taskmaster: %s:' % repr(str(node)))
 
-            # Skip this node if it has already been handled:
-            if not state in [ SCons.Node.no_state, SCons.Node.stack ]:
+            # Skip this node if it has already been evaluated:
+            if state > SCons.Node.pending:
                 if S: S.already_handled = S.already_handled + 1
-                if T: T.write(' already handled\n')
+                if T: T.write(' already handled (%s)\n' % StateString[state])
                 continue
 
             # Mark this node as being on the execution stack:
-            node.set_state(SCons.Node.stack)
+            node.set_state(SCons.Node.pending)
 
             try:
                 children = node.children()
@@ -349,10 +421,11 @@ class Taskmaster:
                 if S: S.problem = S.problem + 1
                 if T: T.write(' exception\n')
                 break
-            else:
+
+            if T and children:
                 c = map(str, children)
                 c.sort()
-                if T: T.write(' children:\n    %s\n   ' % c)
+                T.write(' children:\n    %s\n   ' % c)
 
             childinfo = map(lambda N: (N.get_state(),
                                        N.is_derived() or N.is_pseudo_derived(),
@@ -374,19 +447,14 @@ class Taskmaster:
                 continue
 
             # Detect dependency cycles:
-            cycle = filter(lambda I: I[0] == SCons.Node.stack, childinfo)
-            if cycle:
-                # The node we popped from the candidate stack is part of
-                # the cycle we detected, so put it back before generating
-                # the message to report.
-                self.candidates.append(node)
-                nodes = filter(lambda N: N.get_state() == SCons.Node.stack,
-                               self.candidates) + \
-                               map(lambda I: I[2], cycle)
-                nodes.reverse()
-                desc = "Dependency cycle: " + string.join(map(str, nodes), " -> ")
-                if T: T.write(' dependency cycle\n')
-                raise SCons.Errors.UserError, desc
+            pending_nodes = filter(lambda I: I[0] == SCons.Node.pending, childinfo)
+            if pending_nodes:
+                for p in pending_nodes:
+                    cycle = find_cycle([p[2], node])
+                    if cycle:
+                        desc = "Dependency cycle: " + string.join(map(str, cycle), " -> ")
+                        if T: T.write(' dependency cycle\n')
+                        raise SCons.Errors.UserError, desc
 
             # Select all of the dependencies that are derived targets
             # (that is, children who have builders or are side effects).
@@ -403,6 +471,7 @@ class Taskmaster:
                 # list will get cleared and we'll re-scan the newly-built
                 # file(s) for updated implicit dependencies.
                 map(lambda n, P=node: n.add_to_waiting_parents(P), not_started)
+                node.ref_count = len(not_started)
 
                 # Now we add these derived targets to the candidates
                 # list so they can be examined and built.  We have to
@@ -418,6 +487,7 @@ class Taskmaster:
                 self.candidates.append(node)
                 not_started.reverse()
                 self.candidates.extend(self.order(not_started))
+
                 if S: S.not_started = S.not_started + 1
                 if T:
                     c = map(str, not_started)
@@ -436,11 +506,8 @@ class Taskmaster:
                 # dependency list will get cleared and we'll re-scan the
                 # newly-built file(s) for updated implicit dependencies.
                 map(lambda n, P=node: n.add_to_waiting_parents(P), not_built)
+                node.ref_count = len(not_built)
 
-                # And add this node to the "pending" list, so it can get
-                # put back on the candidates list when appropriate.
-                self.pending.append(node)
-                node.set_state(SCons.Node.pending)
                 if S: S.not_built = S.not_built + 1
                 if T:
                     c = map(str, not_built)
@@ -455,8 +522,7 @@ class Taskmaster:
                                   node.side_effects,
                                   0)
             if side_effects:
-                self.pending.append(node)
-                node.set_state(SCons.Node.pending)
+                map(lambda n, P=node: n.add_to_waiting_s_e(P), side_effects)
                 if S: S.side_effects = S.side_effects + 1
                 if T:
                     c = map(str, side_effects)
@@ -468,7 +534,7 @@ class Taskmaster:
             # this node is ready to be built.
             self.ready = node
             if S: S.build = S.build + 1
-            if T: T.write(' evaluating\n')
+            if T: T.write(' evaluating %s\n' % node)
             break
 
     def next_task(self):
@@ -485,10 +551,8 @@ class Taskmaster:
             tlist = node.builder.targets(node)
         except AttributeError:
             tlist = [node]
-        self.executing.extend(tlist)
-        self.executing.extend(node.side_effects)
 
-        task = self.tasker(self, tlist, node in self.targets, node)
+        task = self.tasker(self, tlist, node is self.current_top, node)
         try:
             task.make_ready()
         except KeyboardInterrupt:
@@ -508,53 +572,19 @@ class Taskmaster:
 
         return task
 
-    def is_blocked(self):
-        self._find_next_ready_node()
-
-        return not self.ready and (self.pending or self.executing)
-
-    def next_top_level_candidate(self):
-        candidates = self.candidates[:]
-        candidates.reverse()
-        for c in candidates:
-            if c in self.targets:
-                return c
-        return None
-
     def stop(self):
         """Stop the current build completely."""
-        self.candidates = []
+        self.next_candidate = self.no_next_candidate
         self.ready = None
-        self.pending = []
 
     def failed(self, node):
-        try:
-            tlist = node.builder.targets(node)
-        except AttributeError:
-            tlist = [node]
-        for t in tlist:
-            self.executing.remove(t)
-        for side_effect in node.side_effects:
-            self.executing.remove(side_effect)
+        pass
 
     def executed(self, node):
         try:
             tlist = node.builder.targets(node)
         except AttributeError:
             tlist = [node]
-        for t in tlist:
-            self.executing.remove(t)
-        for side_effect in node.side_effects:
-            self.executing.remove(side_effect)
-
-        # move the current pending nodes to the candidates list:
-        # (they may not all be ready to build, but _find_next_ready_node()
-        #  will figure out which ones are really ready)
-        for node in self.pending:
-            node.set_state(SCons.Node.no_state)
-        self.pending.reverse()
-        self.candidates.extend(self.pending)
-        self.pending = []
 
     def exception_raise(self, exception):
         exc = exception[:]