source/blender/nodes/intern/node_tree_ref.cc

   1 /*
   2  * This program is free software; you can redistribute it and/or
   3  * modify it under the terms of the GNU General Public License
   4  * as published by the Free Software Foundation; either version 2
   5  * of the License, or (at your option) any later version.
   6  *
   7  * This program is distributed in the hope that it will be useful,
   8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
   9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  10  * GNU General Public License for more details.
  11  *
  12  * You should have received a copy of the GNU General Public License
  13  * along with this program; if not, write to the Free Software Foundation,
  14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  15  */
  16
  17 #include "NOD_node_tree_ref.hh"
  18
  19 #include "BLI_dot_export.hh"
  20
  21 namespace blender::nodes {
  22
  23 NodeTreeRef::NodeTreeRef(bNodeTree *btree) : btree_(btree)
  24 {
  25   Map<bNode *, NodeRef *> node_mapping;
  26
  27   LISTBASE_FOREACH (bNode *, bnode, &btree->nodes) {
  28     NodeRef &node = *allocator_.construct<NodeRef>();
  29
  30     node.tree_ = this;
  31     node.bnode_ = bnode;
  32     node.id_ = nodes_by_id_.append_and_get_index(&node);
  33     RNA_pointer_create(&btree->id, &RNA_Node, bnode, &node.rna_);
  34
  35     LISTBASE_FOREACH (bNodeSocket *, bsocket, &bnode->inputs) {
  36       InputSocketRef &socket = *allocator_.construct<InputSocketRef>();
  37       socket.node_ = &node;
  38       socket.index_ = node.inputs_.append_and_get_index(&socket);
  39       socket.is_input_ = true;
  40       socket.bsocket_ = bsocket;
  41       socket.id_ = sockets_by_id_.append_and_get_index(&socket);
  42       RNA_pointer_create(&btree->id, &RNA_NodeSocket, bsocket, &socket.rna_);
  43     }
  44
  45     LISTBASE_FOREACH (bNodeSocket *, bsocket, &bnode->outputs) {
  46       OutputSocketRef &socket = *allocator_.construct<OutputSocketRef>();
  47       socket.node_ = &node;
  48       socket.index_ = node.outputs_.append_and_get_index(&socket);
  49       socket.is_input_ = false;
  50       socket.bsocket_ = bsocket;
  51       socket.id_ = sockets_by_id_.append_and_get_index(&socket);
  52       RNA_pointer_create(&btree->id, &RNA_NodeSocket, bsocket, &socket.rna_);
  53     }
  54
  55     input_sockets_.extend(node.inputs_.as_span());
  56     output_sockets_.extend(node.outputs_.as_span());
  57
  58     node_mapping.add_new(bnode, &node);
  59   }
  60
  61   LISTBASE_FOREACH (bNodeLink *, blink, &btree->links) {
  62     OutputSocketRef &from_socket = this->find_output_socket(
  63         node_mapping, blink->fromnode, blink->fromsock);
  64     InputSocketRef &to_socket = this->find_input_socket(
  65         node_mapping, blink->tonode, blink->tosock);
  66
  67     from_socket.directly_linked_sockets_.append(&to_socket);
  68     to_socket.directly_linked_sockets_.append(&from_socket);
  69   }
  70
  71   for (OutputSocketRef *socket : output_sockets_) {
  72     if (!socket->node_->is_reroute_node()) {
  73       this->find_targets_skipping_reroutes(*socket, socket->linked_sockets_);
  74       for (SocketRef *target : socket->linked_sockets_) {
  75         target->linked_sockets_.append(socket);
  76       }
  77     }
  78   }
  79
  80   for (NodeRef *node : nodes_by_id_) {
  81     const bNodeType *nodetype = node->bnode_->typeinfo;
  82     nodes_by_type_.add(nodetype, node);
  83   }
  84 }
  85
  86 NodeTreeRef::~NodeTreeRef()
  87 {
  88   for (NodeRef *node : nodes_by_id_) {
  89     node->~NodeRef();
  90   }
  91   for (InputSocketRef *socket : input_sockets_) {
  92     socket->~InputSocketRef();
  93   }
  94   for (OutputSocketRef *socket : output_sockets_) {
  95     socket->~OutputSocketRef();
  96   }
  97 }
  98
  99 InputSocketRef &NodeTreeRef::find_input_socket(Map<bNode *, NodeRef *> &node_mapping,
 100                                                bNode *bnode,
 101                                                bNodeSocket *bsocket)
 102 {
 103   NodeRef *node = node_mapping.lookup(bnode);
 104   for (InputSocketRef *socket : node->inputs_) {
 105     if (socket->bsocket_ == bsocket) {
 106       return *socket;
 107     }
 108   }
 109   BLI_assert(false);
 110   return *node->inputs_[0];
 111 }
 112
 113 OutputSocketRef &NodeTreeRef::find_output_socket(Map<bNode *, NodeRef *> &node_mapping,
 114                                                  bNode *bnode,
 115                                                  bNodeSocket *bsocket)
 116 {
 117   NodeRef *node = node_mapping.lookup(bnode);
 118   for (OutputSocketRef *socket : node->outputs_) {
 119     if (socket->bsocket_ == bsocket) {
 120       return *socket;
 121     }
 122   }
 123   BLI_assert(false);
 124   return *node->outputs_[0];
 125 }
 126
 127 void NodeTreeRef::find_targets_skipping_reroutes(OutputSocketRef &socket,
 128                                                  Vector<SocketRef *> &r_targets)
 129 {
 130   for (SocketRef *direct_target : socket.directly_linked_sockets_) {
 131     if (direct_target->node_->is_reroute_node()) {
 132       this->find_targets_skipping_reroutes(*direct_target->node_->outputs_[0], r_targets);
 133     }
 134     else {
 135       r_targets.append_non_duplicates(direct_target);
 136     }
 137   }
 138 }
 139
 140 static bool has_link_cycles_recursive(const NodeRef &node,
 141                                       MutableSpan<bool> visited,
 142                                       MutableSpan<bool> is_in_stack)
 143 {
 144   const int node_id = node.id();
 145   if (is_in_stack[node_id]) {
 146     return true;
 147   }
 148   if (visited[node_id]) {
 149     return false;
 150   }
 151
 152   visited[node_id] = true;
 153   is_in_stack[node_id] = true;
 154
 155   for (const OutputSocketRef *from_socket : node.outputs()) {
 156     for (const InputSocketRef *to_socket : from_socket->directly_linked_sockets()) {
 157       const NodeRef &to_node = to_socket->node();
 158       if (has_link_cycles_recursive(to_node, visited, is_in_stack)) {
 159         return true;
 160       }
 161     }
 162   }
 163
 164   is_in_stack[node_id] = false;
 165   return false;
 166 }
 167
 168 bool NodeTreeRef::has_link_cycles() const
 169 {
 170   const int node_amount = nodes_by_id_.size();
 171   Array<bool> visited(node_amount, false);
 172   Array<bool> is_in_stack(node_amount, false);
 173
 174   for (const NodeRef *node : nodes_by_id_) {
 175     if (has_link_cycles_recursive(*node, visited, is_in_stack)) {
 176       return true;
 177     }
 178   }
 179   return false;
 180 }
 181
 182 std::string NodeTreeRef::to_dot() const
 183 {
 184   dot::DirectedGraph digraph;
 185   digraph.set_rankdir(dot::Attr_rankdir::LeftToRight);
 186
 187   Map<const NodeRef *, dot::NodeWithSocketsRef> dot_nodes;
 188
 189   for (const NodeRef *node : nodes_by_id_) {
 190     dot::Node &dot_node = digraph.new_node("");
 191     dot_node.set_background_color("white");
 192
 193     Vector<std::string> input_names;
 194     Vector<std::string> output_names;
 195     for (const InputSocketRef *socket : node->inputs()) {
 196       input_names.append(socket->name());
 197     }
 198     for (const OutputSocketRef *socket : node->outputs()) {
 199       output_names.append(socket->name());
 200     }
 201
 202     dot_nodes.add_new(node,
 203                       dot::NodeWithSocketsRef(dot_node, node->name(), input_names, output_names));
 204   }
 205
 206   for (const OutputSocketRef *from_socket : output_sockets_) {
 207     for (const InputSocketRef *to_socket : from_socket->directly_linked_sockets()) {
 208       dot::NodeWithSocketsRef &from_dot_node = dot_nodes.lookup(&from_socket->node());
 209       dot::NodeWithSocketsRef &to_dot_node = dot_nodes.lookup(&to_socket->node());
 210
 211       digraph.new_edge(from_dot_node.output(from_socket->index()),
 212                        to_dot_node.input(to_socket->index()));
 213     }
 214   }
 215
 216   return digraph.to_dot_string();
 217 }
 218
 219 }  // namespace blender::nodes