[Bf-blender-cvs] [d47b643] object_nodes: Added a topological sorting pass to make sure nodes are compiled in the right order.

[Lukas Tönne]

Commit: d47b643874bb2c7db07d8c44f9b8a55061e9467d
Author: Lukas Tönne
Date:   Mon Oct 19 16:38:05 2015 +0200
Branches: object_nodes
https://developer.blender.org/rBd47b643874bb2c7db07d8c44f9b8a55061e9467d

Added a topological sorting pass to make sure nodes are compiled in the right order.

===================================================================

M	source/blender/blenvm/intern/bvm_codegen.cc

===================================================================

diff --git a/source/blender/blenvm/intern/bvm_codegen.cc b/source/blender/blenvm/intern/bvm_codegen.cc
index a7eaa57..c340574 100644
--- a/source/blender/blenvm/intern/bvm_codegen.cc
+++ b/source/blender/blenvm/intern/bvm_codegen.cc
@@ -30,6 +30,7 @@
  */
 
 #include <cstdio>
+#include <set>
 
 #include "bvm_codegen.h"
 #include "bvm_eval.h"
@@ -150,6 +151,34 @@ StackIndex BVMCompiler::codegen_link(const TypeDesc &from, StackIndex stack_from
 }
 #endif
 
+typedef std::vector<const NodeInstance *> NodeList;
+typedef std::set<const NodeInstance *> NodeSet;
+
+static void sort_nodes_append(const NodeInstance *node, NodeList &result, NodeSet &visited)
+{
+	if (visited.find(node) != visited.end())
+		return;
+	visited.insert(node);
+	
+	for (size_t i = 0; i < node->inputs.size(); ++i) {
+		const NodeInstance *link_node = node->find_input_link_node(i);
+		if (link_node) {
+			sort_nodes_append(link_node, result, visited);
+		}
+	}
+	
+	result.push_back(node);
+}
+
+static void sort_nodes(const NodeGraph &graph, NodeList &result)
+{
+	NodeSet visited;
+	
+	for (NodeGraph::NodeInstanceMap::const_iterator it = graph.nodes.begin(); it != graph.nodes.end(); ++it) {
+		sort_nodes_append(&it->second, result, visited);
+	}
+}
+
 Expression *BVMCompiler::codegen_expression(const NodeGraph &graph)
 {
 	typedef std::pair<const NodeInstance *, const NodeSocket *> SocketPair;
@@ -157,12 +186,13 @@ Expression *BVMCompiler::codegen_expression(const NodeGraph &graph)
 	
 	expr = new Expression();
 	
+	NodeList sorted_nodes;
+	sort_nodes(graph, sorted_nodes);
+	
 	SocketIndexMap socket_index;
 	
-	for (NodeGraph::NodeInstanceMap::const_iterator it = graph.nodes.begin();
-	     it != graph.nodes.end();
-	     ++it) {
-		const NodeInstance &node = it->second;
+	for (NodeList::const_iterator it = sorted_nodes.begin(); it != sorted_nodes.end(); ++it) {
+		const NodeInstance &node = **it;
 		
 		for (int i = 0; i < node.type->inputs.size(); ++i) {
 			const NodeSocket &input = node.type->inputs[i];