Cleanup: remove superfluous `animsys_evaluate_action_ex()` call
[blender.git] / 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