Cycles: Ensure order of shader nodes in the dependnecies set

The issue was than nodes dependencies were stored as set<ShaderNode*> which
is actually a so called "strict weak ordered", meaning order of nodes in
the set is strictly defined, but based on the ShaderNode pointer. This means
that between different render invokations order of original nodes could be
different due to different pointers allocated for ShaderNode.

This commit makes it so dependencies and maps used for ShaderNodes are based
on the node->id which has much more predictable order. It's still possible
to trick the system by doing some crazy edits during viewport rendfer and
cause difference between viewport and final render stacks.

Reviewers: brecht

Reviewed By: brecht

Subscribers: LazyDodo

Differential Revision: https://developer.blender.org/D1630

6 files changed, 65 insertions, 51 deletions

diff --git a/intern/cycles/render/graph.cpp b/intern/cycles/render/graph.cpp
index 7e6e960d585..3e417d13d4d 100644
--- a/intern/cycles/render/graph.cpp
+++ b/intern/cycles/render/graph.cpp
@@ -192,11 +192,11 @@ ShaderGraph *ShaderGraph::copy()
 	ShaderGraph *newgraph = new ShaderGraph();
 
 	/* copy nodes */
-	set<ShaderNode*> nodes_all;
+	ShaderNodeSet nodes_all;
 	foreach(ShaderNode *node, nodes)
 		nodes_all.insert(node);
 
-	map<ShaderNode*, ShaderNode*> nodes_copy;
+	ShaderNodeMap nodes_copy;
 	copy_nodes(nodes_all, nodes_copy);
 
 	/* add nodes (in same order, so output is still first) */
@@ -301,7 +301,7 @@ void ShaderGraph::finalize(Scene *scene,
 	}
 }
 
-void ShaderGraph::find_dependencies(set<ShaderNode*>& dependencies, ShaderInput *input)
+void ShaderGraph::find_dependencies(ShaderNodeSet& dependencies, ShaderInput *input)
 {
 	/* find all nodes that this input depends on directly and indirectly */
 	ShaderNode *node = (input->link)? input->link->parent: NULL;
@@ -314,7 +314,7 @@ void ShaderGraph::find_dependencies(set<ShaderNode*>& dependencies, ShaderInput
 	}
 }
 
-void ShaderGraph::copy_nodes(set<ShaderNode*>& nodes, map<ShaderNode*, ShaderNode*>& nnodemap)
+void ShaderGraph::copy_nodes(ShaderNodeSet& nodes, ShaderNodeMap& nnodemap)
 {
 	/* copy a set of nodes, and the links between them. the assumption is
 	 * made that all nodes that inputs are linked to are in the set too. */
@@ -719,14 +719,14 @@ void ShaderGraph::refine_bump_nodes()
 	foreach(ShaderNode *node, nodes) {
 		if(node->name == ustring("bump") && node->input("Height")->link) {
 			ShaderInput *bump_input = node->input("Height");
-			set<ShaderNode*> nodes_bump;
+			ShaderNodeSet nodes_bump;
 
 			/* make 2 extra copies of the subgraph defined in Bump input */
-			map<ShaderNode*, ShaderNode*> nodes_dx;
-			map<ShaderNode*, ShaderNode*> nodes_dy;
+			ShaderNodeMap nodes_dx;
+			ShaderNodeMap nodes_dy;
 
 			/* find dependencies for the given input */
-			find_dependencies(nodes_bump, bump_input );
+			find_dependencies(nodes_bump, bump_input);
 
 			copy_nodes(nodes_bump, nodes_dx);
 			copy_nodes(nodes_bump, nodes_dy);
@@ -785,13 +785,13 @@ void ShaderGraph::bump_from_displacement()
 		return;
 	
 	/* find dependencies for the given input */
-	set<ShaderNode*> nodes_displace;
+	ShaderNodeSet nodes_displace;
 	find_dependencies(nodes_displace, displacement_in);
 
 	/* copy nodes for 3 bump samples */
-	map<ShaderNode*, ShaderNode*> nodes_center;
-	map<ShaderNode*, ShaderNode*> nodes_dx;
-	map<ShaderNode*, ShaderNode*> nodes_dy;
+	ShaderNodeMap nodes_center;
+	ShaderNodeMap nodes_dx;
+	ShaderNodeMap nodes_dy;
 
 	copy_nodes(nodes_displace, nodes_center);
 	copy_nodes(nodes_displace, nodes_dx);
diff --git a/intern/cycles/render/graph.h b/intern/cycles/render/graph.h
index a2c210f4f60..6ad40720d4c 100644
--- a/intern/cycles/render/graph.h
+++ b/intern/cycles/render/graph.h
@@ -254,6 +254,18 @@ public:
 	virtual void compile(SVMCompiler& compiler); \
 	virtual void compile(OSLCompiler& compiler); \
 
+class ShaderNodeIDComparator
+{
+public:
+	bool operator()(const ShaderNode *n1, const ShaderNode *n2) const
+	{
+		return n1->id < n2->id;
+	}
+};
+
+typedef set<ShaderNode*, ShaderNodeIDComparator> ShaderNodeSet;
+typedef map<ShaderNode*, ShaderNode*, ShaderNodeIDComparator> ShaderNodeMap;
+
 /* Graph
  *
  * Shader graph of nodes. Also does graph manipulations for default inputs,
@@ -290,8 +302,8 @@ public:
 protected:
 	typedef pair<ShaderNode* const, ShaderNode*> NodePair;
 
-	void find_dependencies(set<ShaderNode*>& dependencies, ShaderInput *input);
-	void copy_nodes(set<ShaderNode*>& nodes, map<ShaderNode*, ShaderNode*>& nnodemap);
+	void find_dependencies(ShaderNodeSet& dependencies, ShaderInput *input);
+	void copy_nodes(ShaderNodeSet& nodes, ShaderNodeMap& nnodemap);
 
 	void break_cycles(ShaderNode *node, vector<bool>& visited, vector<bool>& on_stack);
 	void clean(Scene *scene);
diff --git a/intern/cycles/render/osl.cpp b/intern/cycles/render/osl.cpp
index c73deb15edd..4306931e683 100644
--- a/intern/cycles/render/osl.cpp
+++ b/intern/cycles/render/osl.cpp
@@ -698,7 +698,7 @@ void OSLCompiler::parameter_array(const char *name, const Transform tfm[], int a
 	ss->Parameter(name, type, (const float *)tfm);
 }
 
-void OSLCompiler::find_dependencies(set<ShaderNode*>& dependencies, ShaderInput *input)
+void OSLCompiler::find_dependencies(ShaderNodeSet& dependencies, ShaderInput *input)
 {
 	ShaderNode *node = (input->link)? input->link->parent: NULL;
 
@@ -711,9 +711,9 @@ void OSLCompiler::find_dependencies(set<ShaderNode*>& dependencies, ShaderInput
 	}
 }
 
-void OSLCompiler::generate_nodes(const set<ShaderNode*>& nodes)
+void OSLCompiler::generate_nodes(const ShaderNodeSet& nodes)
 {
-	set<ShaderNode*> done;
+	ShaderNodeSet done;
 	bool nodes_done;
 
 	do {
@@ -764,7 +764,7 @@ OSL::ShadingAttribStateRef OSLCompiler::compile_type(Shader *shader, ShaderGraph
 	OSL::ShadingAttribStateRef group = ss->ShaderGroupBegin(shader->name.c_str());
 
 	ShaderNode *output = graph->output();
-	set<ShaderNode*> dependencies;
+	ShaderNodeSet dependencies;
 
 	if(type == SHADER_TYPE_SURFACE) {
 		/* generate surface shader */
diff --git a/intern/cycles/render/osl.h b/intern/cycles/render/osl.h
index e915f830202..3ff37c56e50 100644
--- a/intern/cycles/render/osl.h
+++ b/intern/cycles/render/osl.h
@@ -21,6 +21,7 @@
 #include "util_string.h"
 #include "util_thread.h"
 
+#include "graph.h"
 #include "shader.h"
 
 #ifdef WITH_OSL
@@ -149,8 +150,8 @@ private:
 	string compatible_name(ShaderNode *node, ShaderInput *input);
 	string compatible_name(ShaderNode *node, ShaderOutput *output);
 
-	void find_dependencies(set<ShaderNode*>& dependencies, ShaderInput *input);
-	void generate_nodes(const set<ShaderNode*>& nodes);
+	void find_dependencies(ShaderNodeSet& dependencies, ShaderInput *input);
+	void generate_nodes(const ShaderNodeSet& nodes);
 #endif
 
 	void *shadingsys;
diff --git a/intern/cycles/render/svm.cpp b/intern/cycles/render/svm.cpp
index ad0ef959d22..fa22287d342 100644
--- a/intern/cycles/render/svm.cpp
+++ b/intern/cycles/render/svm.cpp
@@ -180,7 +180,7 @@ void SVMCompiler::stack_clear_offset(ShaderSocketType type, int offset)
 		active_stack.users[offset + i]--;
 }
 
-void SVMCompiler::stack_backup(StackBackup& backup, set<ShaderNode*>& done)
+void SVMCompiler::stack_backup(StackBackup& backup, ShaderNodeSet& done)
 {
 	backup.done = done;
 	backup.stack = active_stack;
@@ -193,7 +193,7 @@ void SVMCompiler::stack_backup(StackBackup& backup, set<ShaderNode*>& done)
 	}
 }
 
-void SVMCompiler::stack_restore(StackBackup& backup, set<ShaderNode*>& done)
+void SVMCompiler::stack_restore(StackBackup& backup, ShaderNodeSet& done)
 {
 	int i = 0;
 
@@ -263,7 +263,7 @@ void SVMCompiler::stack_link(ShaderInput *input, ShaderOutput *output)
 	}
 }
 
-void SVMCompiler::stack_clear_users(ShaderNode *node, set<ShaderNode*>& done)
+void SVMCompiler::stack_clear_users(ShaderNode *node, ShaderNodeSet& done)
 {
 	/* optimization we should add:
 	 * find and lower user counts for outputs for which all inputs are done.
@@ -366,8 +366,8 @@ bool SVMCompiler::node_skip_input(ShaderNode * /*node*/, ShaderInput *input)
 	return false;
 }
 
-void SVMCompiler::find_dependencies(set<ShaderNode*>& dependencies,
-                                    const set<ShaderNode*>& done,
+void SVMCompiler::find_dependencies(ShaderNodeSet& dependencies,
+                                    const ShaderNodeSet& done,
                                     ShaderInput *input,
                                     ShaderNode *skip_node)
 {
@@ -382,7 +382,7 @@ void SVMCompiler::find_dependencies(set<ShaderNode*>& dependencies,
 	}
 }
 
-void SVMCompiler::generate_node(ShaderNode *node, set<ShaderNode*>& done)
+void SVMCompiler::generate_node(ShaderNode *node, ShaderNodeSet& done)
 {
 	node->compile(*this);
 	stack_clear_users(node, done);
@@ -402,7 +402,7 @@ void SVMCompiler::generate_node(ShaderNode *node, set<ShaderNode*>& done)
 	}
 }
 
-void SVMCompiler::generate_svm_nodes(const set<ShaderNode*>& nodes, set<ShaderNode*>& done)
+void SVMCompiler::generate_svm_nodes(const ShaderNodeSet& nodes, ShaderNodeSet& done)
 {
 	bool nodes_done;
 
@@ -429,12 +429,12 @@ void SVMCompiler::generate_svm_nodes(const set<ShaderNode*>& nodes, set<ShaderNo
 	} while(!nodes_done);
 }
 
-void SVMCompiler::generate_closure_node(ShaderNode *node, set<ShaderNode*>& done)
+void SVMCompiler::generate_closure_node(ShaderNode *node, ShaderNodeSet& done)
 {
 	/* execute dependencies for closure */
 	foreach(ShaderInput *in, node->inputs) {
 		if(!node_skip_input(node, in) && in->link) {
-			set<ShaderNode*> dependencies;
+			ShaderNodeSet dependencies;
 			find_dependencies(dependencies, done, in);
 			generate_svm_nodes(dependencies, done);
 		}
@@ -471,9 +471,9 @@ void SVMCompiler::generate_closure_node(ShaderNode *node, set<ShaderNode*>& done
 
 void SVMCompiler::generated_shared_closure_nodes(ShaderNode *root_node,
                                                  ShaderNode *node,
-                                                 set<ShaderNode*>& done,
-                                                 set<ShaderNode*>& closure_done,
-                                                 const set<ShaderNode*>& shared)
+                                                 ShaderNodeSet& done,
+                                                 ShaderNodeSet& closure_done,
+                                                 const ShaderNodeSet& shared)
 {
 	if(shared.find(node) != shared.end()) {
 		generate_multi_closure(root_node, node, done, closure_done);
@@ -489,8 +489,8 @@ void SVMCompiler::generated_shared_closure_nodes(ShaderNode *root_node,
 
 void SVMCompiler::generate_multi_closure(ShaderNode *root_node,
                                          ShaderNode *node,
-                                         set<ShaderNode*>& done,
-                                         set<ShaderNode*>& closure_done)
+                                         ShaderNodeSet& done,
+                                         ShaderNodeSet& closure_done)
 {
 	/* only generate once */
 	if(closure_done.find(node) != closure_done.end())
@@ -510,7 +510,7 @@ void SVMCompiler::generate_multi_closure(ShaderNode *root_node,
 
 		if(facin && facin->link) {
 			/* mix closure: generate instructions to compute mix weight */
-			set<ShaderNode*> dependencies;
+			ShaderNodeSet dependencies;
 			find_dependencies(dependencies, done, facin);
 			generate_svm_nodes(dependencies, done);
 
@@ -519,7 +519,7 @@ void SVMCompiler::generate_multi_closure(ShaderNode *root_node,
 			/* execute shared dependencies. this is needed to allow skipping
 			 * of zero weight closures and their dependencies later, so we
 			 * ensure that they only skip dependencies that are unique to them */
-			set<ShaderNode*> cl1deps, cl2deps, shareddeps;
+			ShaderNodeSet cl1deps, cl2deps, shareddeps;
 
 			find_dependencies(cl1deps, done, cl1in);
 			find_dependencies(cl2deps, done, cl2in);
@@ -534,7 +534,7 @@ void SVMCompiler::generate_multi_closure(ShaderNode *root_node,
 			 * node or so */
 			if(root_node != node) {
 				foreach(ShaderInput *in, root_node->inputs) {
-					set<ShaderNode*> rootdeps;
+					ShaderNodeSet rootdeps;
 					find_dependencies(rootdeps, done, in, node);
 					set_intersection(rootdeps.begin(), rootdeps.end(),
 					                 cl1deps.begin(), cl1deps.end(),
@@ -676,7 +676,7 @@ void SVMCompiler::compile_type(Shader *shader, ShaderGraph *graph, ShaderType ty
 			}
 
 			if(generate) {
-				set<ShaderNode*> done, closure_done;
+				ShaderNodeSet done, closure_done;
 				generate_multi_closure(clin->link->parent, clin->link->parent,
 				                       done, closure_done);
 			}
diff --git a/intern/cycles/render/svm.h b/intern/cycles/render/svm.h
index e48fe5e32ed..02855f22fb3 100644
--- a/intern/cycles/render/svm.h
+++ b/intern/cycles/render/svm.h
@@ -112,35 +112,36 @@ protected:
 	struct StackBackup {
 		Stack stack;
 		vector<int> offsets;
-		set<ShaderNode*> done;
+		ShaderNodeSet done;
 	};
 
-	void stack_backup(StackBackup& backup, set<ShaderNode*>& done);
-	void stack_restore(StackBackup& backup, set<ShaderNode*>& done);
+	void stack_backup(StackBackup& backup, ShaderNodeSet& done);
+	void stack_restore(StackBackup& backup, ShaderNodeSet& done);
 
 	void stack_clear_temporary(ShaderNode *node);
 	int stack_size(ShaderSocketType type);
-	void stack_clear_users(ShaderNode *node, set<ShaderNode*>& done);
+	void stack_clear_users(ShaderNode *node, ShaderNodeSet& done);
 
 	bool node_skip_input(ShaderNode *node, ShaderInput *input);
 
 	/* single closure */
-	void find_dependencies(set<ShaderNode*>& dependencies,
-	                       const set<ShaderNode*>& done,
+	void find_dependencies(ShaderNodeSet& dependencies,
+	                       const ShaderNodeSet& done,
 	                       ShaderInput *input,
 	                       ShaderNode *skip_node = NULL);
-	void generate_node(ShaderNode *node, set<ShaderNode*>& done);
-	void generate_closure_node(ShaderNode *node, set<ShaderNode*>& done);
+	void generate_node(ShaderNode *node, ShaderNodeSet& done);
+	void generate_closure_node(ShaderNode *node, ShaderNodeSet& done);
 	void generated_shared_closure_nodes(ShaderNode *root_node, ShaderNode *node,
-	                                    set<ShaderNode*>& done,
-		set<ShaderNode*>& closure_done, const set<ShaderNode*>& shared);
-	void generate_svm_nodes(const set<ShaderNode*>& nodes, set<ShaderNode*>& done);
+	                                    ShaderNodeSet& done,
+	                                    ShaderNodeSet& closure_done,
+	                                    const ShaderNodeSet& shared);
+	void generate_svm_nodes(const ShaderNodeSet& nodes, ShaderNodeSet& done);
 
 	/* multi closure */
 	void generate_multi_closure(ShaderNode *root_node,
 	                            ShaderNode *node,
-	                            set<ShaderNode*>& done,
-	                            set<ShaderNode*>& closure_done);
+	                            ShaderNodeSet& done,
+	                            ShaderNodeSet& closure_done);
 
 	/* compile */
 	void compile_type(Shader *shader, ShaderGraph *graph, ShaderType type);