Anonymous avatar Anonymous committed c3b816e

Add a node Walker for descending the dependency tree.

Comments (0)

Files changed (2)

src/engine/SCons/Node/NodeTests.py

 	node.add_dependency(['four', 'five', 'six'])
 	kids = node.children()
 	kids.sort()
-	print kids
 	assert kids == ['five', 'four', 'one', 'six', 'three', 'two']
 
+    def test_walker(self):
+	"""Test walking a Node tree.
+	"""
+
+	class MyNode(SCons.Node.Node):
+	    def __init__(self, name):
+		SCons.Node.Node.__init__(self)
+		self.name = name
+
+    	n1 = MyNode("n1")
+
+	nw = SCons.Node.Walker(n1)
+	assert nw.next().name ==  "n1"
+	assert nw.next() == None
+
+    	n2 = MyNode("n2")
+    	n3 = MyNode("n3")
+	n1.add_source([n2, n3])
+
+	nw = SCons.Node.Walker(n1)
+	assert nw.next().name ==  "n2"
+	assert nw.next().name ==  "n3"
+	assert nw.next().name ==  "n1"
+	assert nw.next() == None
+
+	n4 = MyNode("n4")
+	n5 = MyNode("n5")
+	n6 = MyNode("n6")
+	n7 = MyNode("n7")
+	n2.add_source([n4, n5])
+	n3.add_dependency([n6, n7])
+
+	nw = SCons.Node.Walker(n1)
+	assert nw.next().name ==  "n4"
+	assert nw.next().name ==  "n5"
+	assert nw.next().name ==  "n2"
+	assert nw.next().name ==  "n6"
+	assert nw.next().name ==  "n7"
+	assert nw.next().name ==  "n3"
+	assert nw.next().name ==  "n1"
+	assert nw.next() == None
+
 
 
 if __name__ == "__main__":

src/engine/SCons/Node/__init__.py

 
     def children(self):
 	return self.sources + self.depends
+
+
+
+
+class Wrapper:
+    def __init__(self, node):
+        self.node = node
+        self.kids = node.children()
+        # XXX randomize kids here, if requested
+
+class Walker:
+    """An iterator for walking a Node tree.
+    
+    This is depth-first, children are visited before the parent.
+    The Walker object can be initialized with any node, and 
+    returns the next node on the descent with each next() call.
+    """
+    def __init__(self, node):
+	self.current = Wrapper(node)
+	self.stack = []
+	self.top = self.current
+
+    def next(self):
+	"""Return the next node for this walk of the tree.
+
+	This function is intentionally iterative, not recursive,
+	to sidestep any issues of stack size limitations.
+	"""
+	if not self.current:
+	    return None
+
+	while 1:
+	    if self.current.kids:
+	    	k = Wrapper(self.current.kids[0])
+	    	self.current.kids = self.current.kids[1:]
+		if k.kids:
+		    self.stack.append(self.current)
+		    self.current = k
+		else:
+		    return k.node
+	    else:
+		n = self.current.node
+	        if self.stack:
+		    self.current = self.stack[-1]
+		    self.stack = self.stack[0:-1]
+		else:
+		    self.current = None
+		return n
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.