source/blender/nodes/intern/derived_node_tree.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_derived_node_tree.hh"
  18
  19 #include "BLI_dot_export.hh"
  20
  21 #define UNINITIALIZED_ID UINT32_MAX
  22
  23 namespace blender::nodes {
  24
  25 static const NodeTreeRef &get_tree_ref(NodeTreeRefMap &node_tree_refs, bNodeTree *btree)
  26 {
  27   return *node_tree_refs.lookup_or_add_cb(btree,
  28                                           [&]() { return std::make_unique<NodeTreeRef>(btree); });
  29 }
  30
  31 DerivedNodeTree::DerivedNodeTree(bNodeTree *btree, NodeTreeRefMap &node_tree_refs) : btree_(btree)
  32 {
  33   BLI_assert(btree != nullptr);
  34
  35   const NodeTreeRef &main_tree_ref = get_tree_ref(node_tree_refs, btree);
  36   used_node_tree_refs_.add_new(&main_tree_ref);
  37
  38   Vector<DNode *> all_nodes;
  39   Vector<DGroupInput *> all_group_inputs;
  40   Vector<DParentNode *> all_parent_nodes;
  41
  42   this->insert_nodes_and_links_in_id_order(main_tree_ref, nullptr, all_nodes);
  43   this->expand_groups(all_nodes, all_group_inputs, all_parent_nodes, node_tree_refs);
  44   this->relink_and_remove_muted_nodes(all_nodes);
  45   this->remove_expanded_group_interfaces(all_nodes);
  46   this->remove_unused_group_inputs(all_group_inputs);
  47   this->store_in_this_and_init_ids(
  48       std::move(all_nodes), std::move(all_group_inputs), std::move(all_parent_nodes));
  49 }
  50
  51 BLI_NOINLINE void DerivedNodeTree::insert_nodes_and_links_in_id_order(const NodeTreeRef &tree_ref,
  52                                                                       DParentNode *parent,
  53                                                                       Vector<DNode *> &all_nodes)
  54 {
  55   Array<DSocket *, 64> sockets_map(tree_ref.sockets().size());
  56
  57   /* Insert nodes. */
  58   for (const NodeRef *node_ref : tree_ref.nodes()) {
  59     DNode &node = this->create_node(*node_ref, parent, sockets_map);
  60     all_nodes.append(&node);
  61   }
  62
  63   /* Insert links. */
  64   for (const NodeRef *node_ref : tree_ref.nodes()) {
  65     for (const InputSocketRef *to_socket_ref : node_ref->inputs()) {
  66       DInputSocket *to_socket = static_cast<DInputSocket *>(sockets_map[to_socket_ref->id()]);
  67       for (const OutputSocketRef *from_socket_ref : to_socket_ref->linked_sockets()) {
  68         DOutputSocket *from_socket = static_cast<DOutputSocket *>(
  69             sockets_map[from_socket_ref->id()]);
  70         to_socket->linked_sockets_.append(from_socket);
  71         from_socket->linked_sockets_.append(to_socket);
  72       }
  73     }
  74   }
  75 }
  76
  77 DNode &DerivedNodeTree::create_node(const NodeRef &node_ref,
  78                                     DParentNode *parent,
  79                                     MutableSpan<DSocket *> r_sockets_map)
  80 {
  81   DNode &node = *allocator_.construct<DNode>();
  82   node.node_ref_ = &node_ref;
  83   node.parent_ = parent;
  84   node.id_ = UNINITIALIZED_ID;
  85
  86   node.inputs_ = allocator_.construct_elements_and_pointer_array<DInputSocket>(
  87       node_ref.inputs().size());
  88   node.outputs_ = allocator_.construct_elements_and_pointer_array<DOutputSocket>(
  89       node_ref.outputs().size());
  90
  91   for (int i : node.inputs_.index_range()) {
  92     const InputSocketRef &socket_ref = node_ref.input(i);
  93     DInputSocket &socket = *node.inputs_[i];
  94     socket.is_multi_input_socket_ = socket_ref.bsocket()->flag & SOCK_MULTI_INPUT;
  95     socket.id_ = UNINITIALIZED_ID;
  96     socket.node_ = &node;
  97     socket.socket_ref_ = &socket_ref;
  98
  99     r_sockets_map[socket_ref.id()] = &socket;
 100   }
 101
 102   for (int i : node.outputs_.index_range()) {
 103     const OutputSocketRef &socket_ref = node_ref.output(i);
 104     DOutputSocket &socket = *node.outputs_[i];
 105
 106     socket.id_ = UNINITIALIZED_ID;
 107     socket.node_ = &node;
 108     socket.socket_ref_ = &socket_ref;
 109
 110     r_sockets_map[socket_ref.id()] = &socket;
 111   }
 112
 113   return node;
 114 }
 115
 116 BLI_NOINLINE void DerivedNodeTree::expand_groups(Vector<DNode *> &all_nodes,
 117                                                  Vector<DGroupInput *> &all_group_inputs,
 118                                                  Vector<DParentNode *> &all_parent_nodes,
 119                                                  NodeTreeRefMap &node_tree_refs)
 120 {
 121   for (int i = 0; i < all_nodes.size(); i++) {
 122     DNode &node = *all_nodes[i];
 123     if (node.node_ref_->is_group_node()) {
 124       /* Muted nodes are relinked in a separate step. */
 125       if (!node.node_ref_->is_muted()) {
 126         this->expand_group_node(
 127             node, all_nodes, all_group_inputs, all_parent_nodes, node_tree_refs);
 128       }
 129     }
 130   }
 131 }
 132
 133 BLI_NOINLINE void DerivedNodeTree::expand_group_node(DNode &group_node,
 134                                                      Vector<DNode *> &all_nodes,
 135                                                      Vector<DGroupInput *> &all_group_inputs,
 136                                                      Vector<DParentNode *> &all_parent_nodes,
 137                                                      NodeTreeRefMap &node_tree_refs)
 138 {
 139   const NodeRef &group_node_ref = *group_node.node_ref_;
 140   BLI_assert(group_node_ref.is_group_node());
 141
 142   bNodeTree *btree = reinterpret_cast<bNodeTree *>(group_node_ref.bnode()->id);
 143   if (btree == nullptr) {
 144     return;
 145   }
 146
 147   const NodeTreeRef &group_ref = get_tree_ref(node_tree_refs, btree);
 148   used_node_tree_refs_.add(&group_ref);
 149
 150   DParentNode &parent = *allocator_.construct<DParentNode>();
 151   parent.id_ = all_parent_nodes.append_and_get_index(&parent);
 152   parent.parent_ = group_node.parent_;
 153   parent.node_ref_ = &group_node_ref;
 154
 155   this->insert_nodes_and_links_in_id_order(group_ref, &parent, all_nodes);
 156   Span<DNode *> new_nodes_by_id = all_nodes.as_span().take_back(group_ref.nodes().size());
 157
 158   this->create_group_inputs_for_unlinked_inputs(group_node, all_group_inputs);
 159   this->relink_group_inputs(group_ref, new_nodes_by_id, group_node);
 160   this->relink_group_outputs(group_ref, new_nodes_by_id, group_node);
 161 }
 162
 163 BLI_NOINLINE void DerivedNodeTree::create_group_inputs_for_unlinked_inputs(
 164     DNode &node, Vector<DGroupInput *> &all_group_inputs)
 165 {
 166   for (DInputSocket *input_socket : node.inputs_) {
 167     if (input_socket->is_linked()) {
 168       continue;
 169     }
 170
 171     DGroupInput &group_input = *allocator_.construct<DGroupInput>();
 172     group_input.id_ = UNINITIALIZED_ID;
 173     group_input.socket_ref_ = &input_socket->socket_ref();
 174     group_input.parent_ = node.parent_;
 175
 176     group_input.linked_sockets_.append(input_socket);
 177     input_socket->linked_group_inputs_.append(&group_input);
 178     all_group_inputs.append(&group_input);
 179   }
 180 }
 181
 182 BLI_NOINLINE void DerivedNodeTree::relink_group_inputs(const NodeTreeRef &group_ref,
 183                                                        Span<DNode *> nodes_by_id,
 184                                                        DNode &group_node)
 185 {
 186   Span<const NodeRef *> node_refs = group_ref.nodes_by_type("NodeGroupInput");
 187   if (node_refs.size() == 0) {
 188     return;
 189   }
 190   /* TODO: Pick correct group input node if there are more than one. */
 191   const NodeRef &input_node_ref = *node_refs[0];
 192   DNode &input_node = *nodes_by_id[input_node_ref.id()];
 193
 194   int input_amount = group_node.inputs().size();
 195   BLI_assert(input_amount == input_node_ref.outputs().size() - 1);
 196
 197   for (int input_index : IndexRange(input_amount)) {
 198     DInputSocket *outside_group = group_node.inputs_[input_index];
 199     DOutputSocket *inside_group = input_node.outputs_[input_index];
 200
 201     for (DOutputSocket *outside_connected : outside_group->linked_sockets_) {
 202       outside_connected->linked_sockets_.remove_first_occurrence_and_reorder(outside_group);
 203     }
 204
 205     for (DGroupInput *outside_connected : outside_group->linked_group_inputs_) {
 206       outside_connected->linked_sockets_.remove_first_occurrence_and_reorder(outside_group);
 207     }
 208
 209     for (DInputSocket *inside_connected : inside_group->linked_sockets_) {
 210       inside_connected->linked_sockets_.remove_first_occurrence_and_reorder(inside_group);
 211
 212       for (DOutputSocket *outside_connected : outside_group->linked_sockets_) {
 213         inside_connected->linked_sockets_.append(outside_connected);
 214         outside_connected->linked_sockets_.append(inside_connected);
 215       }
 216
 217       for (DGroupInput *outside_connected : outside_group->linked_group_inputs_) {
 218         inside_connected->linked_group_inputs_.append(outside_connected);
 219         outside_connected->linked_sockets_.append(inside_connected);
 220       }
 221     }
 222
 223     inside_group->linked_sockets_.clear();
 224     outside_group->linked_sockets_.clear();
 225     outside_group->linked_group_inputs_.clear();
 226   }
 227 }
 228
 229 BLI_NOINLINE void DerivedNodeTree::relink_group_outputs(const NodeTreeRef &group_ref,
 230                                                         Span<DNode *> nodes_by_id,
 231                                                         DNode &group_node)
 232 {
 233   Span<const NodeRef *> node_refs = group_ref.nodes_by_type("NodeGroupOutput");
 234   if (node_refs.size() == 0) {
 235     return;
 236   }
 237   /* TODO: Pick correct group output node if there are more than one. */
 238   const NodeRef &output_node_ref = *node_refs[0];
 239   DNode &output_node = *nodes_by_id[output_node_ref.id()];
 240
 241   int output_amount = group_node.outputs().size();
 242   BLI_assert(output_amount == output_node_ref.inputs().size() - 1);
 243
 244   for (int output_index : IndexRange(output_amount)) {
 245     DOutputSocket *outside_group = group_node.outputs_[output_index];
 246     DInputSocket *inside_group = output_node.inputs_[output_index];
 247
 248     for (DInputSocket *outside_connected : outside_group->linked_sockets_) {
 249       outside_connected->linked_sockets_.remove_first_occurrence_and_reorder(outside_group);
 250     }
 251
 252     for (DOutputSocket *inside_connected : inside_group->linked_sockets_) {
 253       inside_connected->linked_sockets_.remove_first_occurrence_and_reorder(inside_group);
 254
 255       for (DInputSocket *outside_connected : outside_group->linked_sockets_) {
 256         inside_connected->linked_sockets_.append(outside_connected);
 257         outside_connected->linked_sockets_.append(inside_connected);
 258       }
 259     }
 260
 261     for (DGroupInput *inside_connected : inside_group->linked_group_inputs_) {
 262       inside_connected->linked_sockets_.remove_first_occurrence_and_reorder(inside_group);
 263
 264       for (DInputSocket *outside_connected : outside_group->linked_sockets_) {
 265         inside_connected->linked_sockets_.append(outside_connected);
 266         outside_connected->linked_group_inputs_.append(inside_connected);
 267       }
 268     }
 269
 270     outside_group->linked_sockets_.clear();
 271     inside_group->linked_sockets_.clear();
 272   }
 273 }
 274
 275 BLI_NOINLINE void DerivedNodeTree::remove_expanded_group_interfaces(Vector<DNode *> &all_nodes)
 276 {
 277   int index = 0;
 278   while (index < all_nodes.size()) {
 279     DNode &node = *all_nodes[index];
 280     const NodeRef &node_ref = *node.node_ref_;
 281     if (node_ref.is_group_node() ||
 282         (node.parent_ != nullptr &&
 283          (node_ref.is_group_input_node() || node_ref.is_group_output_node()))) {
 284       all_nodes.remove_and_reorder(index);
 285       node.destruct_with_sockets();
 286     }
 287     else {
 288       index++;
 289     }
 290   }
 291 }
 292
 293 BLI_NOINLINE void DerivedNodeTree::remove_unused_group_inputs(
 294     Vector<DGroupInput *> &all_group_inputs)
 295 {
 296   int index = 0;
 297   while (index < all_group_inputs.size()) {
 298     DGroupInput &group_input = *all_group_inputs[index];
 299     if (group_input.linked_sockets_.is_empty()) {
 300       all_group_inputs.remove_and_reorder(index);
 301       group_input.~DGroupInput();
 302     }
 303     else {
 304       index++;
 305     }
 306   }
 307 }
 308
 309 BLI_NOINLINE void DerivedNodeTree::relink_and_remove_muted_nodes(Vector<DNode *> &all_nodes)
 310 {
 311   int index = 0;
 312   while (index < all_nodes.size()) {
 313     DNode &node = *all_nodes[index];
 314     const NodeRef &node_ref = *node.node_ref_;
 315     if (node_ref.is_muted()) {
 316       this->relink_muted_node(node);
 317       all_nodes.remove_and_reorder(index);
 318       node.destruct_with_sockets();
 319     }
 320     else {
 321       index++;
 322     }
 323   }
 324 }
 325
 326 BLI_NOINLINE void DerivedNodeTree::relink_muted_node(DNode &node)
 327 {
 328   const bNode &bnode = *node.bnode();
 329   LISTBASE_FOREACH (const bNodeLink *, internal_link, &bnode.internal_links) {
 330     BLI_assert(internal_link->fromnode == &bnode);
 331     BLI_assert(internal_link->tonode == &bnode);
 332     bNodeSocket *input_bsocket = internal_link->fromsock;
 333     bNodeSocket *output_bsocket = internal_link->tosock;
 334
 335     /* Find internally linked sockets. */
 336     DInputSocket *input_socket = nullptr;
 337     DOutputSocket *output_socket = nullptr;
 338     for (DInputSocket *socket : node.inputs_) {
 339       if (socket->bsocket() == input_bsocket) {
 340         input_socket = socket;
 341         break;
 342       }
 343     }
 344     for (DOutputSocket *socket : node.outputs_) {
 345       if (socket->bsocket() == output_bsocket) {
 346         output_socket = socket;
 347         break;
 348       }
 349     }
 350     BLI_assert(input_socket != nullptr);
 351     BLI_assert(output_socket != nullptr);
 352
 353     /* Link sockets connected to the input to sockets that are connected to the internally linked
 354      * output. */
 355     for (DInputSocket *to_socket : output_socket->linked_sockets_) {
 356       for (DOutputSocket *from_socket : input_socket->linked_sockets_) {
 357         from_socket->linked_sockets_.append_non_duplicates(to_socket);
 358         to_socket->linked_sockets_.append_non_duplicates(from_socket);
 359       }
 360       for (DGroupInput *group_input : input_socket->linked_group_inputs_) {
 361         group_input->linked_sockets_.append_non_duplicates(to_socket);
 362         to_socket->linked_group_inputs_.append_non_duplicates(group_input);
 363       }
 364     }
 365   }
 366
 367   /* Remove remaining links from muted node. */
 368   for (DInputSocket *to_socket : node.inputs_) {
 369     for (DOutputSocket *from_socket : to_socket->linked_sockets_) {
 370       from_socket->linked_sockets_.remove_first_occurrence_and_reorder(to_socket);
 371     }
 372     for (DGroupInput *from_group_input : to_socket->linked_group_inputs_) {
 373       from_group_input->linked_sockets_.remove_first_occurrence_and_reorder(to_socket);
 374     }
 375     to_socket->linked_sockets_.clear();
 376     to_socket->linked_group_inputs_.clear();
 377   }
 378   for (DOutputSocket *from_socket : node.outputs_) {
 379     for (DInputSocket *to_socket : from_socket->linked_sockets_) {
 380       to_socket->linked_sockets_.remove_first_occurrence_and_reorder(from_socket);
 381     }
 382     from_socket->linked_sockets_.clear();
 383   }
 384 }
 385
 386 void DNode::destruct_with_sockets()
 387 {
 388   for (DInputSocket *socket : inputs_) {
 389     socket->~DInputSocket();
 390   }
 391   for (DOutputSocket *socket : outputs_) {
 392     socket->~DOutputSocket();
 393   }
 394   this->~DNode();
 395 }
 396
 397 BLI_NOINLINE void DerivedNodeTree::store_in_this_and_init_ids(
 398     Vector<DNode *> &&all_nodes,
 399     Vector<DGroupInput *> &&all_group_inputs,
 400     Vector<DParentNode *> &&all_parent_nodes)
 401 {
 402   nodes_by_id_ = std::move(all_nodes);
 403   group_inputs_ = std::move(all_group_inputs);
 404   parent_nodes_ = std::move(all_parent_nodes);
 405
 406   for (int node_index : nodes_by_id_.index_range()) {
 407     DNode *node = nodes_by_id_[node_index];
 408     node->id_ = node_index;
 409
 410     const bNodeType *nodetype = node->node_ref_->bnode()->typeinfo;
 411     nodes_by_type_.add(nodetype, node);
 412
 413     for (DInputSocket *socket : node->inputs_) {
 414       socket->id_ = sockets_by_id_.append_and_get_index(socket);
 415       input_sockets_.append(socket);
 416     }
 417     for (DOutputSocket *socket : node->outputs_) {
 418       socket->id_ = sockets_by_id_.append_and_get_index(socket);
 419       output_sockets_.append(socket);
 420     }
 421   }
 422
 423   for (int i : group_inputs_.index_range()) {
 424     group_inputs_[i]->id_ = i;
 425   }
 426 }
 427
 428 DerivedNodeTree::~DerivedNodeTree()
 429 {
 430   for (DInputSocket *socket : input_sockets_) {
 431     socket->~DInputSocket();
 432   }
 433   for (DOutputSocket *socket : output_sockets_) {
 434     socket->~DOutputSocket();
 435   }
 436   for (DNode *node : nodes_by_id_) {
 437     node->~DNode();
 438   }
 439   for (DGroupInput *group_input : group_inputs_) {
 440     group_input->~DGroupInput();
 441   }
 442   for (DParentNode *parent : parent_nodes_) {
 443     parent->~DParentNode();
 444   }
 445 }
 446
 447 bool DerivedNodeTree::has_link_cycles() const
 448 {
 449   for (const NodeTreeRef *tree : used_node_tree_refs_) {
 450     if (tree->has_link_cycles()) {
 451       return true;
 452     }
 453   }
 454   return false;
 455 }
 456
 457 static dot::Cluster *get_cluster_for_parent(dot::DirectedGraph &graph,
 458                                             Map<const DParentNode *, dot::Cluster *> &clusters,
 459                                             const DParentNode *parent)
 460 {
 461   if (parent == nullptr) {
 462     return nullptr;
 463   }
 464   return clusters.lookup_or_add_cb(parent, [&]() {
 465     dot::Cluster *parent_cluster = get_cluster_for_parent(graph, clusters, parent->parent());
 466     bNodeTree *btree = reinterpret_cast<bNodeTree *>(parent->node_ref().bnode()->id);
 467     dot::Cluster *new_cluster = &graph.new_cluster(parent->node_ref().name() + " / " +
 468                                                    StringRef(btree->id.name + 2));
 469     new_cluster->set_parent_cluster(parent_cluster);
 470     return new_cluster;
 471   });
 472 }
 473
 474 std::string DerivedNodeTree::to_dot() const
 475 {
 476   dot::DirectedGraph digraph;
 477   digraph.set_rankdir(dot::Attr_rankdir::LeftToRight);
 478
 479   Map<const DNode *, dot::NodeWithSocketsRef> dot_nodes;
 480   Map<const DGroupInput *, dot::NodeWithSocketsRef> dot_group_inputs;
 481   Map<const DParentNode *, dot::Cluster *> dot_clusters;
 482
 483   for (const DNode *node : nodes_by_id_) {
 484     dot::Node &dot_node = digraph.new_node("");
 485     dot_node.set_background_color("white");
 486
 487     Vector<std::string> input_names;
 488     for (const DInputSocket *socket : node->inputs()) {
 489       input_names.append(socket->name());
 490     }
 491     Vector<std::string> output_names;
 492     for (const DOutputSocket *socket : node->outputs()) {
 493       output_names.append(socket->name());
 494     }
 495
 496     dot_nodes.add_new(node,
 497                       dot::NodeWithSocketsRef(dot_node, node->name(), input_names, output_names));
 498
 499     dot::Cluster *cluster = get_cluster_for_parent(digraph, dot_clusters, node->parent());
 500     dot_node.set_parent_cluster(cluster);
 501   }
 502
 503   for (const DGroupInput *group_input : group_inputs_) {
 504     dot::Node &dot_node = digraph.new_node("");
 505     dot_node.set_background_color("white");
 506
 507     std::string group_input_name = group_input->name();
 508     dot_group_inputs.add_new(
 509         group_input, dot::NodeWithSocketsRef(dot_node, "Group Input", {}, {group_input_name}));
 510
 511     dot::Cluster *cluster = get_cluster_for_parent(digraph, dot_clusters, group_input->parent());
 512     dot_node.set_parent_cluster(cluster);
 513   }
 514
 515   for (const DNode *to_node : nodes_by_id_) {
 516     dot::NodeWithSocketsRef &to_dot_node = dot_nodes.lookup(to_node);
 517
 518     for (const DInputSocket *to_socket : to_node->inputs()) {
 519       for (const DOutputSocket *from_socket : to_socket->linked_sockets()) {
 520         const DNode *from_node = &from_socket->node();
 521         dot::NodeWithSocketsRef &from_dot_node = dot_nodes.lookup(from_node);
 522
 523         digraph.new_edge(from_dot_node.output(from_socket->index()),
 524                          to_dot_node.input(to_socket->index()));
 525       }
 526       for (const DGroupInput *group_input : to_socket->linked_group_inputs()) {
 527         dot::NodeWithSocketsRef &from_dot_node = dot_group_inputs.lookup(group_input);
 528
 529         digraph.new_edge(from_dot_node.output(0), to_dot_node.input(to_socket->index()));
 530       }
 531     }
 532   }
 533
 534   digraph.set_random_cluster_bgcolors();
 535   return digraph.to_dot_string();
 536 }
 537
 538 }  // namespace blender::nodes