1 files changed, 139 insertions, 142 deletions

diff --git a/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc b/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc
index a6d86f5178f..af5c4e7130b 100644
--- a/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc
+++ b/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc
@@ -41,89 +41,88 @@ namespace DEG {
 namespace {
 
 enum eCyclicCheckVisitedState {
-	/* Not is not visited at all during traversal. */
-	NODE_NOT_VISITED = 0,
-	/* Node has been visited during traversal and not in current stack. */
-	NODE_VISITED = 1,
-	/* Node has been visited during traversal and is in current stack. */
-	NODE_IN_STACK = 2,
+  /* Not is not visited at all during traversal. */
+  NODE_NOT_VISITED = 0,
+  /* Node has been visited during traversal and not in current stack. */
+  NODE_VISITED = 1,
+  /* Node has been visited during traversal and is in current stack. */
+  NODE_IN_STACK = 2,
 };
 
 struct StackEntry {
-	OperationNode *node;
-	StackEntry *from;
-	Relation *via_relation;
+  OperationNode *node;
+  StackEntry *from;
+  Relation *via_relation;
 };
 
 struct CyclesSolverState {
-	CyclesSolverState(Depsgraph *graph)
-		: graph(graph),
-		  traversal_stack(BLI_stack_new(sizeof(StackEntry),
-		                                "DEG detect cycles stack")),
-		  num_cycles(0)
-	{
-		/* pass */
-	}
-	~CyclesSolverState() {
-		BLI_stack_free(traversal_stack);
-		if (num_cycles != 0) {
-			printf("Detected %d dependency cycles\n", num_cycles);
-		}
-	}
-	Depsgraph *graph;
-	BLI_Stack *traversal_stack;
-	int num_cycles;
+  CyclesSolverState(Depsgraph *graph)
+      : graph(graph),
+        traversal_stack(BLI_stack_new(sizeof(StackEntry), "DEG detect cycles stack")),
+        num_cycles(0)
+  {
+    /* pass */
+  }
+  ~CyclesSolverState()
+  {
+    BLI_stack_free(traversal_stack);
+    if (num_cycles != 0) {
+      printf("Detected %d dependency cycles\n", num_cycles);
+    }
+  }
+  Depsgraph *graph;
+  BLI_Stack *traversal_stack;
+  int num_cycles;
 };
 
-BLI_INLINE void set_node_visited_state(Node *node,
-                                       eCyclicCheckVisitedState state)
+BLI_INLINE void set_node_visited_state(Node *node, eCyclicCheckVisitedState state)
 {
-	node->custom_flags = (node->custom_flags & ~0x3) | (int)state;
+  node->custom_flags = (node->custom_flags & ~0x3) | (int)state;
 }
 
 BLI_INLINE eCyclicCheckVisitedState get_node_visited_state(Node *node)
 {
-	return (eCyclicCheckVisitedState)(node->custom_flags & 0x3);
+  return (eCyclicCheckVisitedState)(node->custom_flags & 0x3);
 }
 
 BLI_INLINE void set_node_num_visited_children(Node *node, int num_children)
 {
-	node->custom_flags = (node->custom_flags & 0x3) | (num_children << 2);
+  node->custom_flags = (node->custom_flags & 0x3) | (num_children << 2);
 }
 
 BLI_INLINE int get_node_num_visited_children(Node *node)
 {
-	return node->custom_flags >> 2;
+  return node->custom_flags >> 2;
 }
 
 void schedule_node_to_stack(CyclesSolverState *state, OperationNode *node)
 {
-	StackEntry entry;
-	entry.node = node;
-	entry.from = NULL;
-	entry.via_relation = NULL;
-	BLI_stack_push(state->traversal_stack, &entry);
-	set_node_visited_state(node, NODE_IN_STACK);
+  StackEntry entry;
+  entry.node = node;
+  entry.from = NULL;
+  entry.via_relation = NULL;
+  BLI_stack_push(state->traversal_stack, &entry);
+  set_node_visited_state(node, NODE_IN_STACK);
 }
 
 /* Schedule leaf nodes (node without input links) for traversal. */
 void schedule_leaf_nodes(CyclesSolverState *state)
 {
-	for (OperationNode *node : state->graph->operations) {
-		bool has_inlinks = false;
-		for (Relation *rel : node->inlinks) {
-			if (rel->from->type == NodeType::OPERATION) {
-				has_inlinks = true;
-			}
-		}
-		node->custom_flags = 0;
-		if (has_inlinks == false) {
-			schedule_node_to_stack(state, node);
-		}
-		else {
-			set_node_visited_state(node, NODE_NOT_VISITED);
-		}
-	}
+  for (OperationNode *node : state->graph->operations) {
+    bool has_inlinks = false;
+    for (Relation *rel : node->inlinks) {
+      if (rel->from->type == NodeType::OPERATION) {
+        has_inlinks = true;
+      }
+    }
+    node->custom_flags = 0;
+    if (has_inlinks == false) {
+      schedule_node_to_stack(state, node);
+    }
+    else {
+      set_node_visited_state(node, NODE_NOT_VISITED);
+    }
+  }
 }
 
 /* Schedule node which was not checked yet for being belong to
@@ -131,113 +130,111 @@ void schedule_leaf_nodes(CyclesSolverState *state)
  */
 bool schedule_non_checked_node(CyclesSolverState *state)
 {
-	for (OperationNode *node : state->graph->operations) {
-		if (get_node_visited_state(node) == NODE_NOT_VISITED) {
-			schedule_node_to_stack(state, node);
-			return true;
-		}
-	}
-	return false;
+  for (OperationNode *node : state->graph->operations) {
+    if (get_node_visited_state(node) == NODE_NOT_VISITED) {
+      schedule_node_to_stack(state, node);
+      return true;
+    }
+  }
+  return false;
 }
 
 bool check_relation_can_murder(Relation *relation)
 {
-	if (relation->flag & RELATION_FLAG_GODMODE) {
-		return false;
-	}
-	return true;
+  if (relation->flag & RELATION_FLAG_GODMODE) {
+    return false;
+  }
+  return true;
 }
 
-Relation *select_relation_to_murder(Relation *relation,
-                                    StackEntry *cycle_start_entry)
+Relation *select_relation_to_murder(Relation *relation, StackEntry *cycle_start_entry)
 {
-	/* More or less russian roulette solver, which will make sure only
-	 * specially marked relations are kept alive.
-	 *
-	 * TODO(sergey): There might be better strategies here. */
-	if (check_relation_can_murder(relation)) {
-		return relation;
-	}
-	StackEntry *current = cycle_start_entry;
-	OperationNode *to_node = (OperationNode *)relation->to;
-	while (current->node != to_node) {
-		if (check_relation_can_murder(current->via_relation)) {
-			return current->via_relation;
-		}
-		current = current->from;
-	}
-	return relation;
+  /* More or less russian roulette solver, which will make sure only
+   * specially marked relations are kept alive.
+   *
+   * TODO(sergey): There might be better strategies here. */
+  if (check_relation_can_murder(relation)) {
+    return relation;
+  }
+  StackEntry *current = cycle_start_entry;
+  OperationNode *to_node = (OperationNode *)relation->to;
+  while (current->node != to_node) {
+    if (check_relation_can_murder(current->via_relation)) {
+      return current->via_relation;
+    }
+    current = current->from;
+  }
+  return relation;
 }
 
 /* Solve cycles with all nodes which are scheduled for traversal. */
 void solve_cycles(CyclesSolverState *state)
 {
-	BLI_Stack *traversal_stack = state->traversal_stack;
-	while (!BLI_stack_is_empty(traversal_stack)) {
-		StackEntry *entry = (StackEntry *)BLI_stack_peek(traversal_stack);
-		OperationNode *node = entry->node;
-		bool all_child_traversed = true;
-		const int num_visited = get_node_num_visited_children(node);
-		for (int i = num_visited; i < node->outlinks.size(); ++i) {
-			Relation *rel = node->outlinks[i];
-			if (rel->to->type == NodeType::OPERATION) {
-				OperationNode *to = (OperationNode *)rel->to;
-				eCyclicCheckVisitedState to_state = get_node_visited_state(to);
-				if (to_state == NODE_IN_STACK) {
-					printf("Dependency cycle detected:\n");
-					printf("  '%s' depends on '%s' through '%s'\n",
-					       to->full_identifier().c_str(),
-					       node->full_identifier().c_str(),
-					       rel->name);
-					StackEntry *current = entry;
-					while (current->node != to) {
-						BLI_assert(current != NULL);
-						printf("  '%s' depends on '%s' through '%s'\n",
-						       current->node->full_identifier().c_str(),
-						       current->from->node->full_identifier().c_str(),
-						       current->via_relation->name);
-						current = current->from;
-					}
-					Relation *sacrificial_relation =
-					        select_relation_to_murder(rel, entry);
-					sacrificial_relation->flag |= RELATION_FLAG_CYCLIC;
-					++state->num_cycles;
-				}
-				else if (to_state == NODE_NOT_VISITED) {
-					StackEntry new_entry;
-					new_entry.node = to;
-					new_entry.from = entry;
-					new_entry.via_relation = rel;
-					BLI_stack_push(traversal_stack, &new_entry);
-					set_node_visited_state(node, NODE_IN_STACK);
-					all_child_traversed = false;
-					set_node_num_visited_children(node, i);
-					break;
-				}
-			}
-		}
-		if (all_child_traversed) {
-			set_node_visited_state(node, NODE_VISITED);
-			BLI_stack_discard(traversal_stack);
-		}
-	}
+  BLI_Stack *traversal_stack = state->traversal_stack;
+  while (!BLI_stack_is_empty(traversal_stack)) {
+    StackEntry *entry = (StackEntry *)BLI_stack_peek(traversal_stack);
+    OperationNode *node = entry->node;
+    bool all_child_traversed = true;
+    const int num_visited = get_node_num_visited_children(node);
+    for (int i = num_visited; i < node->outlinks.size(); ++i) {
+      Relation *rel = node->outlinks[i];
+      if (rel->to->type == NodeType::OPERATION) {
+        OperationNode *to = (OperationNode *)rel->to;
+        eCyclicCheckVisitedState to_state = get_node_visited_state(to);
+        if (to_state == NODE_IN_STACK) {
+          printf("Dependency cycle detected:\n");
+          printf("  '%s' depends on '%s' through '%s'\n",
+                 to->full_identifier().c_str(),
+                 node->full_identifier().c_str(),
+                 rel->name);
+          StackEntry *current = entry;
+          while (current->node != to) {
+            BLI_assert(current != NULL);
+            printf("  '%s' depends on '%s' through '%s'\n",
+                   current->node->full_identifier().c_str(),
+                   current->from->node->full_identifier().c_str(),
+                   current->via_relation->name);
+            current = current->from;
+          }
+          Relation *sacrificial_relation = select_relation_to_murder(rel, entry);
+          sacrificial_relation->flag |= RELATION_FLAG_CYCLIC;
+          ++state->num_cycles;
+        }
+        else if (to_state == NODE_NOT_VISITED) {
+          StackEntry new_entry;
+          new_entry.node = to;
+          new_entry.from = entry;
+          new_entry.via_relation = rel;
+          BLI_stack_push(traversal_stack, &new_entry);
+          set_node_visited_state(node, NODE_IN_STACK);
+          all_child_traversed = false;
+          set_node_num_visited_children(node, i);
+          break;
+        }
+      }
+    }
+    if (all_child_traversed) {
+      set_node_visited_state(node, NODE_VISITED);
+      BLI_stack_discard(traversal_stack);
+    }
+  }
 }
 
 }  // namespace
 
 void deg_graph_detect_cycles(Depsgraph *graph)
 {
-	CyclesSolverState state(graph);
-	/* First we solve cycles which are reachable from leaf nodes. */
-	schedule_leaf_nodes(&state);
-	solve_cycles(&state);
-	/* We are not done yet. It is possible to have closed loop cycle,
-	 * for example A -> B -> C -> A. These nodes were not scheduled
-	 * yet (since they all have inlinks), and were not traversed since
-	 * nobody else points to them. */
-	while (schedule_non_checked_node(&state)) {
-		solve_cycles(&state);
-	}
+  CyclesSolverState state(graph);
+  /* First we solve cycles which are reachable from leaf nodes. */
+  schedule_leaf_nodes(&state);
+  solve_cycles(&state);
+  /* We are not done yet. It is possible to have closed loop cycle,
+   * for example A -> B -> C -> A. These nodes were not scheduled
+   * yet (since they all have inlinks), and were not traversed since
+   * nobody else points to them. */
+  while (schedule_non_checked_node(&state)) {
+    solve_cycles(&state);
+  }
 }
 
 }  // namespace DEG