Nodes: efficient node tree queries and inlining

This adds two data structures that wrap a node tree. However, they work
on different abstraction levels.

`NodeTreeRef` is an immutable structure that makes working with a node
tree in C++ much more efficient and convenient. It supports various
queries efficiently, that are not easily possible using just `bNodeTree`.

`DerivedNodeTree` builds on top of `NodeTreeRef`. It contains a flattened
view on the node tree, i.e. with node groups being inlined. Every inlined
node still knows its "call stack". It supports pretty much the same queries
as `NodeTreeRef`.

Both data structures come with a dot graph exporter for debugging purposes.

Reviewers: brecht

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

5 files changed, 1525 insertions, 0 deletions

diff --git a/source/blender/blenkernel/BKE_derived_node_tree.hh b/source/blender/blenkernel/BKE_derived_node_tree.hh
new file mode 100644
index 00000000000..009d9b747f9
--- /dev/null
+++ b/source/blender/blenkernel/BKE_derived_node_tree.hh
@@ -0,0 +1,453 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#ifndef __BKE_DERIVED_NODE_TREE_HH__
+#define __BKE_DERIVED_NODE_TREE_HH__
+
+/** \file
+ * \ingroup bke
+ *
+ * DerivedNodeTree provides a flattened view on a bNodeTree, i.e. node groups are inlined. It
+ * builds on top of NodeTreeRef and supports similar queries efficiently.
+ *
+ * Every inlined node remembers its path to the parent ("call stack").
+ *
+ * Unlinked group node inputs are handled separately from other sockets.
+ *
+ * There is a dot graph exporter for debugging purposes.
+ */
+
+#include "BKE_node_tree_ref.hh"
+
+namespace BKE {
+
+class DSocket;
+class DInputSocket;
+class DOutputSocket;
+class DNode;
+class DParentNode;
+class DGroupInput;
+class DerivedNodeTree;
+
+class DSocket : blender::NonCopyable, blender::NonMovable {
+ protected:
+  DNode *m_node;
+  const SocketRef *m_socket_ref;
+  uint m_id;
+
+  friend DerivedNodeTree;
+
+ public:
+  const DNode &node() const;
+
+  uint id() const;
+  uint index() const;
+
+  bool is_input() const;
+  bool is_output() const;
+
+  const DSocket &as_base() const;
+  const DInputSocket &as_input() const;
+  const DOutputSocket &as_output() const;
+
+  PointerRNA *rna() const;
+  StringRefNull idname() const;
+  StringRefNull name() const;
+};
+
+class DInputSocket : public DSocket {
+ private:
+  Vector<DOutputSocket *> m_linked_sockets;
+  Vector<DGroupInput *> m_linked_group_inputs;
+
+  friend DerivedNodeTree;
+
+ public:
+  const InputSocketRef &socket_ref() const;
+
+  Span<const DOutputSocket *> linked_sockets() const;
+  Span<const DGroupInput *> linked_group_inputs() const;
+
+  bool is_linked() const;
+};
+
+class DOutputSocket : public DSocket {
+ private:
+  Vector<DInputSocket *> m_linked_sockets;
+
+  friend DerivedNodeTree;
+
+ public:
+  const OutputSocketRef &socket_ref() const;
+  Span<const DInputSocket *> linked_sockets() const;
+};
+
+class DGroupInput : blender::NonCopyable, blender::NonMovable {
+ private:
+  const InputSocketRef *m_socket_ref;
+  DParentNode *m_parent;
+  Vector<DInputSocket *> m_linked_sockets;
+  uint m_id;
+
+  friend DerivedNodeTree;
+
+ public:
+  const InputSocketRef &socket_ref() const;
+  const DParentNode *parent() const;
+  Span<const DInputSocket *> linked_sockets() const;
+  uint id() const;
+  StringRefNull name() const;
+};
+
+class DNode : blender::NonCopyable, blender::NonMovable {
+ private:
+  const NodeRef *m_node_ref;
+  DParentNode *m_parent;
+
+  Span<DInputSocket *> m_inputs;
+  Span<DOutputSocket *> m_outputs;
+
+  uint m_id;
+
+  friend DerivedNodeTree;
+
+ public:
+  const NodeRef &node_ref() const;
+  const DParentNode *parent() const;
+
+  Span<const DInputSocket *> inputs() const;
+  Span<const DOutputSocket *> outputs() const;
+
+  const DInputSocket &input(uint index) const;
+  const DOutputSocket &output(uint index) const;
+
+  uint id() const;
+
+  PointerRNA *rna() const;
+  StringRefNull idname() const;
+  StringRefNull name() const;
+
+ private:
+  void destruct_with_sockets();
+};
+
+class DParentNode : blender::NonCopyable, blender::NonMovable {
+ private:
+  const NodeRef *m_node_ref;
+  DParentNode *m_parent;
+  uint m_id;
+
+  friend DerivedNodeTree;
+
+ public:
+  const DParentNode *parent() const;
+  const NodeRef &node_ref() const;
+  uint id() const;
+};
+
+using NodeTreeRefMap = Map<bNodeTree *, std::unique_ptr<const NodeTreeRef>>;
+
+class DerivedNodeTree : blender::NonCopyable, blender::NonMovable {
+ private:
+  LinearAllocator<> m_allocator;
+  bNodeTree *m_btree;
+  Vector<DNode *> m_nodes_by_id;
+  Vector<DGroupInput *> m_group_inputs;
+  Vector<DParentNode *> m_parent_nodes;
+
+  Vector<DSocket *> m_sockets_by_id;
+  Vector<DInputSocket *> m_input_sockets;
+  Vector<DOutputSocket *> m_output_sockets;
+
+  Map<std::string, Vector<DNode *>> m_nodes_by_idname;
+
+ public:
+  DerivedNodeTree(bNodeTree *btree, NodeTreeRefMap &node_tree_refs);
+  ~DerivedNodeTree();
+
+  Span<const DNode *> nodes() const;
+  Span<const DNode *> nodes_with_idname(StringRef idname) const;
+
+  Span<const DSocket *> sockets() const;
+  Span<const DInputSocket *> input_sockets() const;
+  Span<const DOutputSocket *> output_sockets() const;
+
+  std::string to_dot() const;
+
+ private:
+  /* Utility functions used during construction. */
+  void insert_nodes_and_links_in_id_order(const NodeTreeRef &tree_ref,
+                                          DParentNode *parent,
+                                          Vector<DNode *> &all_nodes);
+  DNode &create_node(const NodeRef &node_ref,
+                     DParentNode *parent,
+                     MutableSpan<DSocket *> r_sockets_map);
+  void expand_groups(Vector<DNode *> &all_nodes,
+                     Vector<DGroupInput *> &all_group_inputs,
+                     Vector<DParentNode *> &all_parent_nodes,
+                     NodeTreeRefMap &node_tree_refs);
+  void expand_group_node(DNode &group_node,
+                         Vector<DNode *> &all_nodes,
+                         Vector<DGroupInput *> &all_group_inputs,
+                         Vector<DParentNode *> &all_parent_nodes,
+                         NodeTreeRefMap &node_tree_refs);
+  void create_group_inputs_for_unlinked_inputs(DNode &node,
+                                               Vector<DGroupInput *> &all_group_inputs);
+  void relink_group_inputs(const NodeTreeRef &group_ref,
+                           Span<DNode *> nodes_by_id,
+                           DNode &group_node);
+  void relink_group_outputs(const NodeTreeRef &group_ref,
+                            Span<DNode *> nodes_by_id,
+                            DNode &group_node);
+  void remove_expanded_group_interfaces(Vector<DNode *> &all_nodes);
+  void remove_unused_group_inputs(Vector<DGroupInput *> &all_group_inputs);
+  void store_in_this_and_init_ids(Vector<DNode *> &&all_nodes,
+                                  Vector<DGroupInput *> &&all_group_inputs,
+                                  Vector<DParentNode *> &&all_parent_nodes);
+};
+
+/* --------------------------------------------------------------------
+ * DSocket inline methods.
+ */
+
+inline const DNode &DSocket::node() const
+{
+  return *m_node;
+}
+
+inline uint DSocket::id() const
+{
+  return m_id;
+}
+
+inline uint DSocket::index() const
+{
+  return m_socket_ref->index();
+}
+
+inline bool DSocket::is_input() const
+{
+  return m_socket_ref->is_input();
+}
+
+inline bool DSocket::is_output() const
+{
+  return m_socket_ref->is_output();
+}
+
+inline const DSocket &DSocket::as_base() const
+{
+  return *this;
+}
+
+inline const DInputSocket &DSocket::as_input() const
+{
+  return *(DInputSocket *)this;
+}
+
+inline const DOutputSocket &DSocket::as_output() const
+{
+  return *(DOutputSocket *)this;
+}
+
+inline PointerRNA *DSocket::rna() const
+{
+  return m_socket_ref->rna();
+}
+
+inline StringRefNull DSocket::idname() const
+{
+  return m_socket_ref->idname();
+}
+
+inline StringRefNull DSocket::name() const
+{
+  return m_socket_ref->name();
+}
+
+/* --------------------------------------------------------------------
+ * DInputSocket inline methods.
+ */
+
+inline const InputSocketRef &DInputSocket::socket_ref() const
+{
+  return m_socket_ref->as_input();
+}
+
+inline Span<const DOutputSocket *> DInputSocket::linked_sockets() const
+{
+  return m_linked_sockets.as_span();
+}
+
+inline Span<const DGroupInput *> DInputSocket::linked_group_inputs() const
+{
+  return m_linked_group_inputs.as_span();
+}
+
+inline bool DInputSocket::is_linked() const
+{
+  return m_linked_sockets.size() > 0 || m_linked_group_inputs.size() > 0;
+}
+
+/* --------------------------------------------------------------------
+ * DOutputSocket inline methods.
+ */
+
+inline const OutputSocketRef &DOutputSocket::socket_ref() const
+{
+  return m_socket_ref->as_output();
+}
+
+inline Span<const DInputSocket *> DOutputSocket::linked_sockets() const
+{
+  return m_linked_sockets.as_span();
+}
+
+/* --------------------------------------------------------------------
+ * DGroupInput inline methods.
+ */
+
+inline const InputSocketRef &DGroupInput::socket_ref() const
+{
+  return *m_socket_ref;
+}
+
+inline const DParentNode *DGroupInput::parent() const
+{
+  return m_parent;
+}
+
+inline Span<const DInputSocket *> DGroupInput::linked_sockets() const
+{
+  return m_linked_sockets.as_span();
+}
+
+inline uint DGroupInput::id() const
+{
+  return m_id;
+}
+
+inline StringRefNull DGroupInput::name() const
+{
+  return m_socket_ref->name();
+}
+
+/* --------------------------------------------------------------------
+ * DNode inline methods.
+ */
+
+inline const NodeRef &DNode::node_ref() const
+{
+  return *m_node_ref;
+}
+
+inline const DParentNode *DNode::parent() const
+{
+  return m_parent;
+}
+
+inline Span<const DInputSocket *> DNode::inputs() const
+{
+  return m_inputs;
+}
+
+inline Span<const DOutputSocket *> DNode::outputs() const
+{
+  return m_outputs;
+}
+
+inline const DInputSocket &DNode::input(uint index) const
+{
+  return *m_inputs[index];
+}
+
+inline const DOutputSocket &DNode::output(uint index) const
+{
+  return *m_outputs[index];
+}
+
+inline uint DNode::id() const
+{
+  return m_id;
+}
+
+inline PointerRNA *DNode::rna() const
+{
+  return m_node_ref->rna();
+}
+
+inline StringRefNull DNode::idname() const
+{
+  return m_node_ref->idname();
+}
+
+inline StringRefNull DNode::name() const
+{
+  return m_node_ref->name();
+}
+
+/* --------------------------------------------------------------------
+ * DParentNode inline methods.
+ */
+
+inline const DParentNode *DParentNode::parent() const
+{
+  return m_parent;
+}
+
+inline const NodeRef &DParentNode::node_ref() const
+{
+  return *m_node_ref;
+}
+
+inline uint DParentNode::id() const
+{
+  return m_id;
+}
+
+/* --------------------------------------------------------------------
+ * DerivedNodeTree inline methods.
+ */
+
+inline Span<const DNode *> DerivedNodeTree::nodes() const
+{
+  return m_nodes_by_id.as_span();
+}
+
+inline Span<const DNode *> DerivedNodeTree::nodes_with_idname(StringRef idname) const
+{
+  const Vector<DNode *> *nodes = m_nodes_by_idname.lookup_ptr(idname);
+  if (nodes == nullptr) {
+    return {};
+  }
+  else {
+    return nodes->as_span();
+  }
+}
+
+inline Span<const DInputSocket *> DerivedNodeTree::input_sockets() const
+{
+  return m_input_sockets.as_span();
+}
+
+inline Span<const DOutputSocket *> DerivedNodeTree::output_sockets() const
+{
+  return m_output_sockets.as_span();
+}
+
+}  // namespace BKE
+
+#endif /* __BKE_DERIVED_NODE_TREE_HH__ */
diff --git a/source/blender/blenkernel/BKE_node_tree_ref.hh b/source/blender/blenkernel/BKE_node_tree_ref.hh
new file mode 100644
index 00000000000..043ef957af7
--- /dev/null
+++ b/source/blender/blenkernel/BKE_node_tree_ref.hh
@@ -0,0 +1,448 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#ifndef __BKE_NODE_TREE_REF_HH__
+#define __BKE_NODE_TREE_REF_HH__
+
+/** \file
+ * \ingroup bke
+ *
+ * NodeTreeRef makes querying information about a bNodeTree more efficient. It is an immutable data
+ * structure. It should not be used after anymore, after the underlying node tree changed.
+ *
+ * The following queries are supported efficiently:
+ *  - socket -> index of socket
+ *  - socket -> directly linked sockets
+ *  - socket -> linked sockets when skipping reroutes
+ *  - socket -> node
+ *  - socket/node -> rna pointer
+ *  - node -> inputs/outputs
+ *  - node -> tree
+ *  - tree -> all nodes
+ *  - tree -> all (input/output) sockets
+ *  - idname -> nodes
+ *
+ * Every socket has an id. The id-space is shared between input and output sockets.
+ * When storing data per socket, it is often better to use the id as index into an array, instead
+ * of a hash table.
+ *
+ * Every node has an id as well. The same rule regarding hash tables applies.
+ *
+ * There is an utility to export this data structure as graph in dot format.
+ */
+
+#include "BLI_array.hh"
+#include "BLI_linear_allocator.hh"
+#include "BLI_map.hh"
+#include "BLI_string_ref.hh"
+#include "BLI_timeit.hh"
+#include "BLI_utility_mixins.hh"
+#include "BLI_vector.hh"
+
+#include "BKE_node.h"
+
+#include "DNA_node_types.h"
+
+#include "RNA_access.h"
+
+namespace BKE {
+
+using blender::Array;
+using blender::IndexRange;
+using blender::LinearAllocator;
+using blender::Map;
+using blender::MutableSpan;
+using blender::Span;
+using blender::StringRef;
+using blender::StringRefNull;
+using blender::Vector;
+
+class SocketRef;
+class InputSocketRef;
+class OutputSocketRef;
+class NodeRef;
+class NodeTreeRef;
+
+class SocketRef : blender::NonCopyable, blender::NonMovable {
+ protected:
+  NodeRef *m_node;
+  bNodeSocket *m_bsocket;
+  bool m_is_input;
+  uint m_id;
+  uint m_index;
+  PointerRNA m_rna;
+  Vector<SocketRef *> m_linked_sockets;
+  Vector<SocketRef *> m_directly_linked_sockets;
+
+  friend NodeTreeRef;
+
+ public:
+  Span<const SocketRef *> linked_sockets() const;
+  Span<const SocketRef *> directly_linked_sockets() const;
+  bool is_linked() const;
+
+  const NodeRef &node() const;
+  const NodeTreeRef &tree() const;
+
+  uint id() const;
+  uint index() const;
+
+  bool is_input() const;
+  bool is_output() const;
+
+  const SocketRef &as_base() const;
+  const InputSocketRef &as_input() const;
+  const OutputSocketRef &as_output() const;
+
+  PointerRNA *rna() const;
+
+  StringRefNull idname() const;
+  StringRefNull name() const;
+
+  bNodeSocket *bsocket() const;
+  bNode *bnode() const;
+  bNodeTree *btree() const;
+};
+
+class InputSocketRef final : public SocketRef {
+ public:
+  Span<const OutputSocketRef *> linked_sockets() const;
+  Span<const OutputSocketRef *> directly_linked_sockets() const;
+};
+
+class OutputSocketRef final : public SocketRef {
+ public:
+  Span<const InputSocketRef *> linked_sockets() const;
+  Span<const InputSocketRef *> directly_linked_sockets() const;
+};
+
+class NodeRef : blender::NonCopyable, blender::NonMovable {
+ private:
+  NodeTreeRef *m_tree;
+  bNode *m_bnode;
+  PointerRNA m_rna;
+  uint m_id;
+  Vector<InputSocketRef *> m_inputs;
+  Vector<OutputSocketRef *> m_outputs;
+
+  friend NodeTreeRef;
+
+ public:
+  const NodeTreeRef &tree() const;
+
+  Span<const InputSocketRef *> inputs() const;
+  Span<const OutputSocketRef *> outputs() const;
+
+  const InputSocketRef &input(uint index) const;
+  const OutputSocketRef &output(uint index) const;
+
+  bNode *bnode() const;
+  bNodeTree *btree() const;
+
+  PointerRNA *rna() const;
+  StringRefNull idname() const;
+  StringRefNull name() const;
+
+  uint id() const;
+
+  bool is_reroute_node() const;
+  bool is_group_node() const;
+  bool is_group_input_node() const;
+  bool is_group_output_node() const;
+};
+
+class NodeTreeRef : blender::NonCopyable, blender::NonMovable {
+ private:
+  LinearAllocator<> m_allocator;
+  bNodeTree *m_btree;
+  Vector<NodeRef *> m_nodes_by_id;
+  Vector<SocketRef *> m_sockets_by_id;
+  Vector<InputSocketRef *> m_input_sockets;
+  Vector<OutputSocketRef *> m_output_sockets;
+  Map<std::string, Vector<NodeRef *>> m_nodes_by_idname;
+
+ public:
+  NodeTreeRef(bNodeTree *btree);
+  ~NodeTreeRef();
+
+  Span<const NodeRef *> nodes() const;
+  Span<const NodeRef *> nodes_with_idname(StringRef idname) const;
+
+  Span<const SocketRef *> sockets() const;
+  Span<const InputSocketRef *> input_sockets() const;
+  Span<const OutputSocketRef *> output_sockets() const;
+
+  bNodeTree *btree() const;
+
+  std::string to_dot() const;
+
+ private:
+  /* Utility functions used during construction. */
+  InputSocketRef &find_input_socket(Map<bNode *, NodeRef *> &node_mapping,
+                                    bNode *bnode,
+                                    bNodeSocket *bsocket);
+  OutputSocketRef &find_output_socket(Map<bNode *, NodeRef *> &node_mapping,
+                                      bNode *bnode,
+                                      bNodeSocket *bsocket);
+  void find_targets_skipping_reroutes(OutputSocketRef &socket_ref, Vector<SocketRef *> &r_targets);
+};
+
+/* --------------------------------------------------------------------
+ * SocketRef inline methods.
+ */
+
+inline Span<const SocketRef *> SocketRef::linked_sockets() const
+{
+  return m_linked_sockets.as_span();
+}
+
+inline Span<const SocketRef *> SocketRef::directly_linked_sockets() const
+{
+  return m_directly_linked_sockets.as_span();
+}
+
+inline bool SocketRef::is_linked() const
+{
+  return m_linked_sockets.size() > 0;
+}
+
+inline const NodeRef &SocketRef::node() const
+{
+  return *m_node;
+}
+
+inline const NodeTreeRef &SocketRef::tree() const
+{
+  return m_node->tree();
+}
+
+inline uint SocketRef::id() const
+{
+  return m_id;
+}
+
+inline uint SocketRef::index() const
+{
+  return m_index;
+}
+
+inline bool SocketRef::is_input() const
+{
+  return m_is_input;
+}
+
+inline bool SocketRef::is_output() const
+{
+  return !m_is_input;
+}
+
+inline const SocketRef &SocketRef::as_base() const
+{
+  return *this;
+}
+
+inline const InputSocketRef &SocketRef::as_input() const
+{
+  BLI_assert(this->is_input());
+  return *(const InputSocketRef *)this;
+}
+
+inline const OutputSocketRef &SocketRef::as_output() const
+{
+  BLI_assert(this->is_output());
+  return *(const OutputSocketRef *)this;
+}
+
+inline PointerRNA *SocketRef::rna() const
+{
+  return const_cast<PointerRNA *>(&m_rna);
+}
+
+inline StringRefNull SocketRef::idname() const
+{
+  return m_bsocket->idname;
+}
+
+inline StringRefNull SocketRef::name() const
+{
+  return m_bsocket->name;
+}
+
+inline bNodeSocket *SocketRef::bsocket() const
+{
+  return m_bsocket;
+}
+
+inline bNode *SocketRef::bnode() const
+{
+  return m_node->bnode();
+}
+
+inline bNodeTree *SocketRef::btree() const
+{
+  return m_node->btree();
+}
+
+/* --------------------------------------------------------------------
+ * InputSocketRef inline methods.
+ */
+
+inline Span<const OutputSocketRef *> InputSocketRef::linked_sockets() const
+{
+  return m_linked_sockets.as_span().cast<const OutputSocketRef *>();
+}
+
+inline Span<const OutputSocketRef *> InputSocketRef::directly_linked_sockets() const
+{
+  return m_directly_linked_sockets.as_span().cast<const OutputSocketRef *>();
+}
+
+/* --------------------------------------------------------------------
+ * OutputSocketRef inline methods.
+ */
+
+inline Span<const InputSocketRef *> OutputSocketRef::linked_sockets() const
+{
+  return m_linked_sockets.as_span().cast<const InputSocketRef *>();
+}
+
+inline Span<const InputSocketRef *> OutputSocketRef::directly_linked_sockets() const
+{
+  return m_directly_linked_sockets.as_span().cast<const InputSocketRef *>();
+}
+
+/* --------------------------------------------------------------------
+ * NodeRef inline methods.
+ */
+
+inline const NodeTreeRef &NodeRef::tree() const
+{
+  return *m_tree;
+}
+
+inline Span<const InputSocketRef *> NodeRef::inputs() const
+{
+  return m_inputs.as_span();
+}
+
+inline Span<const OutputSocketRef *> NodeRef::outputs() const
+{
+  return m_outputs.as_span();
+}
+
+inline const InputSocketRef &NodeRef::input(uint index) const
+{
+  return *m_inputs[index];
+}
+
+inline const OutputSocketRef &NodeRef::output(uint index) const
+{
+  return *m_outputs[index];
+}
+
+inline bNode *NodeRef::bnode() const
+{
+  return m_bnode;
+}
+
+inline bNodeTree *NodeRef::btree() const
+{
+  return m_tree->btree();
+}
+
+inline PointerRNA *NodeRef::rna() const
+{
+  return const_cast<PointerRNA *>(&m_rna);
+}
+
+inline StringRefNull NodeRef::idname() const
+{
+  return m_bnode->idname;
+}
+
+inline StringRefNull NodeRef::name() const
+{
+  return m_bnode->name;
+}
+
+inline uint NodeRef::id() const
+{
+  return m_id;
+}
+
+inline bool NodeRef::is_reroute_node() const
+{
+  return m_bnode->type == NODE_REROUTE;
+}
+
+inline bool NodeRef::is_group_node() const
+{
+  return m_bnode->type == NODE_GROUP;
+}
+
+inline bool NodeRef::is_group_input_node() const
+{
+  return m_bnode->type == NODE_GROUP_INPUT;
+}
+
+inline bool NodeRef::is_group_output_node() const
+{
+  return m_bnode->type == NODE_GROUP_OUTPUT;
+}
+
+/* --------------------------------------------------------------------
+ * NodeRef inline methods.
+ */
+
+inline Span<const NodeRef *> NodeTreeRef::nodes() const
+{
+  return m_nodes_by_id.as_span();
+}
+
+inline Span<const NodeRef *> NodeTreeRef::nodes_with_idname(StringRef idname) const
+{
+  const Vector<NodeRef *> *nodes = m_nodes_by_idname.lookup_ptr(idname);
+  if (nodes == nullptr) {
+    return {};
+  }
+  else {
+    return nodes->as_span();
+  }
+}
+
+inline Span<const SocketRef *> NodeTreeRef::sockets() const
+{
+  return m_sockets_by_id.as_span();
+}
+
+inline Span<const InputSocketRef *> NodeTreeRef::input_sockets() const
+{
+  return m_input_sockets.as_span();
+}
+
+inline Span<const OutputSocketRef *> NodeTreeRef::output_sockets() const
+{
+  return m_output_sockets.as_span();
+}
+
+inline bNodeTree *NodeTreeRef::btree() const
+{
+  return m_btree;
+}
+
+}  // namespace BKE
+
+#endif /* __BKE_NODE_TREE_REF_HH__ */
diff --git a/source/blender/blenkernel/CMakeLists.txt b/source/blender/blenkernel/CMakeLists.txt
index 817fe849eab..89712a1aed2 100644
--- a/source/blender/blenkernel/CMakeLists.txt
+++ b/source/blender/blenkernel/CMakeLists.txt
@@ -104,6 +104,7 @@ set(SRC
   intern/customdata_file.c
   intern/data_transfer.c
   intern/deform.c
+  intern/derived_node_tree.cc
   intern/displist.c
   intern/displist_tangent.c
   intern/dynamicpaint.c
@@ -183,6 +184,7 @@ set(SRC
   intern/multires_unsubdivide.c
   intern/nla.c
   intern/node.c
+  intern/node_tree_ref.cc
   intern/object.c
   intern/object_deform.c
   intern/object_dupli.c
@@ -291,6 +293,7 @@ set(SRC
   BKE_customdata_file.h
   BKE_data_transfer.h
   BKE_deform.h
+  BKE_derived_node_tree.hh
   BKE_displist.h
   BKE_displist_tangent.h
   BKE_duplilist.h
@@ -349,6 +352,7 @@ set(SRC
   BKE_multires.h
   BKE_nla.h
   BKE_node.h
+  BKE_node_tree_ref.hh
   BKE_object.h
   BKE_object_deform.h
   BKE_object_facemap.h
diff --git a/source/blender/blenkernel/intern/derived_node_tree.cc b/source/blender/blenkernel/intern/derived_node_tree.cc
new file mode 100644
index 00000000000..80ae521642e
--- /dev/null
+++ b/source/blender/blenkernel/intern/derived_node_tree.cc
@@ -0,0 +1,442 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#include "BKE_derived_node_tree.hh"
+
+#include "BLI_dot_export.hh"
+
+#define UNINITIALIZED_ID UINT32_MAX
+
+namespace BKE {
+
+static const NodeTreeRef &get_tree_ref(NodeTreeRefMap &node_tree_refs, bNodeTree *btree)
+{
+  return *node_tree_refs.lookup_or_add(btree,
+                                       [&]() { return blender::make_unique<NodeTreeRef>(btree); });
+}
+
+DerivedNodeTree::DerivedNodeTree(bNodeTree *btree, NodeTreeRefMap &node_tree_refs) : m_btree(btree)
+{
+  const NodeTreeRef &main_tree_ref = get_tree_ref(node_tree_refs, btree);
+
+  Vector<DNode *> all_nodes;
+  Vector<DGroupInput *> all_group_inputs;
+  Vector<DParentNode *> all_parent_nodes;
+
+  this->insert_nodes_and_links_in_id_order(main_tree_ref, nullptr, all_nodes);
+  this->expand_groups(all_nodes, all_group_inputs, all_parent_nodes, node_tree_refs);
+  this->remove_expanded_group_interfaces(all_nodes);
+  this->remove_unused_group_inputs(all_group_inputs);
+  this->store_in_this_and_init_ids(
+      std::move(all_nodes), std::move(all_group_inputs), std::move(all_parent_nodes));
+}
+
+BLI_NOINLINE void DerivedNodeTree::insert_nodes_and_links_in_id_order(const NodeTreeRef &tree_ref,
+                                                                      DParentNode *parent,
+                                                                      Vector<DNode *> &all_nodes)
+{
+  Array<DSocket *, 64> sockets_map(tree_ref.sockets().size());
+
+  /* Insert nodes. */
+  for (const NodeRef *node_ref : tree_ref.nodes()) {
+    DNode &node = this->create_node(*node_ref, parent, sockets_map);
+    all_nodes.append(&node);
+  }
+
+  /* Insert links. */
+  for (const NodeRef *node_ref : tree_ref.nodes()) {
+    for (const InputSocketRef *to_socket_ref : node_ref->inputs()) {
+      DInputSocket *to_socket = (DInputSocket *)sockets_map[to_socket_ref->id()];
+      for (const OutputSocketRef *from_socket_ref : to_socket_ref->linked_sockets()) {
+        DOutputSocket *from_socket = (DOutputSocket *)sockets_map[from_socket_ref->id()];
+        to_socket->m_linked_sockets.append(from_socket);
+        from_socket->m_linked_sockets.append(to_socket);
+      }
+    }
+  }
+}
+
+DNode &DerivedNodeTree::create_node(const NodeRef &node_ref,
+                                    DParentNode *parent,
+                                    MutableSpan<DSocket *> r_sockets_map)
+{
+  DNode &node = *m_allocator.construct<DNode>();
+  node.m_node_ref = &node_ref;
+  node.m_parent = parent;
+  node.m_id = UNINITIALIZED_ID;
+
+  node.m_inputs = m_allocator.construct_elements_and_pointer_array<DInputSocket>(
+      node_ref.inputs().size());
+  node.m_outputs = m_allocator.construct_elements_and_pointer_array<DOutputSocket>(
+      node_ref.outputs().size());
+
+  for (uint i : node.m_inputs.index_range()) {
+    const InputSocketRef &socket_ref = node_ref.input(i);
+    DInputSocket &socket = *node.m_inputs[i];
+
+    socket.m_id = UNINITIALIZED_ID;
+    socket.m_node = &node;
+    socket.m_socket_ref = &socket_ref;
+
+    r_sockets_map[socket_ref.id()] = &socket;
+  }
+
+  for (uint i : node.m_outputs.index_range()) {
+    const OutputSocketRef &socket_ref = node_ref.output(i);
+    DOutputSocket &socket = *node.m_outputs[i];
+
+    socket.m_id = UNINITIALIZED_ID;
+    socket.m_node = &node;
+    socket.m_socket_ref = &socket_ref;
+
+    r_sockets_map[socket_ref.id()] = &socket;
+  }
+
+  return node;
+}
+
+BLI_NOINLINE void DerivedNodeTree::expand_groups(Vector<DNode *> &all_nodes,
+                                                 Vector<DGroupInput *> &all_group_inputs,
+                                                 Vector<DParentNode *> &all_parent_nodes,
+                                                 NodeTreeRefMap &node_tree_refs)
+{
+  for (uint i = 0; i < all_nodes.size(); i++) {
+    DNode &node = *all_nodes[i];
+    if (node.m_node_ref->is_group_node()) {
+      this->expand_group_node(node, all_nodes, all_group_inputs, all_parent_nodes, node_tree_refs);
+    }
+  }
+}
+
+BLI_NOINLINE void DerivedNodeTree::expand_group_node(DNode &group_node,
+                                                     Vector<DNode *> &all_nodes,
+                                                     Vector<DGroupInput *> &all_group_inputs,
+                                                     Vector<DParentNode *> &all_parent_nodes,
+                                                     NodeTreeRefMap &node_tree_refs)
+{
+  const NodeRef &group_node_ref = *group_node.m_node_ref;
+  BLI_assert(group_node_ref.is_group_node());
+
+  bNodeTree *btree = (bNodeTree *)group_node_ref.bnode()->id;
+  if (btree == nullptr) {
+    return;
+  }
+
+  const NodeTreeRef &group_ref = get_tree_ref(node_tree_refs, btree);
+
+  DParentNode &parent = *m_allocator.construct<DParentNode>();
+  parent.m_id = all_parent_nodes.append_and_get_index(&parent);
+  parent.m_parent = group_node.m_parent;
+  parent.m_node_ref = &group_node_ref;
+
+  this->insert_nodes_and_links_in_id_order(group_ref, &parent, all_nodes);
+  Span<DNode *> new_nodes_by_id = all_nodes.as_span().take_back(group_ref.nodes().size());
+
+  this->create_group_inputs_for_unlinked_inputs(group_node, all_group_inputs);
+  this->relink_group_inputs(group_ref, new_nodes_by_id, group_node);
+  this->relink_group_outputs(group_ref, new_nodes_by_id, group_node);
+}
+
+BLI_NOINLINE void DerivedNodeTree::create_group_inputs_for_unlinked_inputs(
+    DNode &node, Vector<DGroupInput *> &all_group_inputs)
+{
+  for (DInputSocket *input_socket : node.m_inputs) {
+    if (input_socket->is_linked()) {
+      continue;
+    }
+
+    DGroupInput &group_input = *m_allocator.construct<DGroupInput>();
+    group_input.m_id = UNINITIALIZED_ID;
+    group_input.m_socket_ref = &input_socket->socket_ref();
+    group_input.m_parent = node.m_parent;
+
+    group_input.m_linked_sockets.append(input_socket);
+    input_socket->m_linked_group_inputs.append(&group_input);
+    all_group_inputs.append(&group_input);
+  }
+}
+
+BLI_NOINLINE void DerivedNodeTree::relink_group_inputs(const NodeTreeRef &group_ref,
+                                                       Span<DNode *> nodes_by_id,
+                                                       DNode &group_node)
+{
+  Span<const NodeRef *> node_refs = group_ref.nodes_with_idname("NodeGroupInput");
+  if (node_refs.size() == 0) {
+    return;
+  }
+  /* TODO: Pick correct group input node if there are more than one. */
+  const NodeRef &input_node_ref = *node_refs[0];
+  DNode &input_node = *nodes_by_id[input_node_ref.id()];
+
+  uint input_amount = group_node.inputs().size();
+  BLI_assert(input_amount == input_node_ref.outputs().size() - 1);
+
+  for (uint input_index : IndexRange(input_amount)) {
+    DInputSocket *outside_group = group_node.m_inputs[input_index];
+    DOutputSocket *inside_group = input_node.m_outputs[input_index];
+
+    for (DOutputSocket *outside_connected : outside_group->m_linked_sockets) {
+      outside_connected->m_linked_sockets.remove_first_occurrence_and_reorder(outside_group);
+    }
+
+    for (DGroupInput *outside_connected : outside_group->m_linked_group_inputs) {
+      outside_connected->m_linked_sockets.remove_first_occurrence_and_reorder(outside_group);
+    }
+
+    for (DInputSocket *inside_connected : inside_group->m_linked_sockets) {
+      inside_connected->m_linked_sockets.remove_first_occurrence_and_reorder(inside_group);
+
+      for (DOutputSocket *outside_connected : outside_group->m_linked_sockets) {
+        inside_connected->m_linked_sockets.append(outside_connected);
+        outside_connected->m_linked_sockets.append(inside_connected);
+      }
+
+      for (DGroupInput *outside_connected : outside_group->m_linked_group_inputs) {
+        inside_connected->m_linked_group_inputs.append(outside_connected);
+        outside_connected->m_linked_sockets.append(inside_connected);
+      }
+    }
+
+    inside_group->m_linked_sockets.clear();
+    outside_group->m_linked_sockets.clear();
+    outside_group->m_linked_group_inputs.clear();
+  }
+}
+
+BLI_NOINLINE void DerivedNodeTree::relink_group_outputs(const NodeTreeRef &group_ref,
+                                                        Span<DNode *> nodes_by_id,
+                                                        DNode &group_node)
+{
+  Span<const NodeRef *> node_refs = group_ref.nodes_with_idname("NodeGroupOutput");
+  if (node_refs.size() == 0) {
+    return;
+  }
+  /* TODO: Pick correct group output node if there are more than one. */
+  const NodeRef &output_node_ref = *node_refs[0];
+  DNode &output_node = *nodes_by_id[output_node_ref.id()];
+
+  uint output_amount = group_node.outputs().size();
+  BLI_assert(output_amount == output_node_ref.inputs().size() - 1);
+
+  for (uint output_index : IndexRange(output_amount)) {
+    DOutputSocket *outside_group = group_node.m_outputs[output_index];
+    DInputSocket *inside_group = output_node.m_inputs[output_index];
+
+    for (DInputSocket *outside_connected : outside_group->m_linked_sockets) {
+      outside_connected->m_linked_sockets.remove_first_occurrence_and_reorder(outside_group);
+    }
+
+    for (DOutputSocket *inside_connected : inside_group->m_linked_sockets) {
+      inside_connected->m_linked_sockets.remove_first_occurrence_and_reorder(inside_group);
+
+      for (DInputSocket *outside_connected : outside_group->m_linked_sockets) {
+        inside_connected->m_linked_sockets.append(outside_connected);
+        outside_connected->m_linked_sockets.append(inside_connected);
+      }
+    }
+
+    for (DGroupInput *inside_connected : inside_group->m_linked_group_inputs) {
+      inside_connected->m_linked_sockets.remove_first_occurrence_and_reorder(inside_group);
+
+      for (DInputSocket *outside_connected : outside_group->m_linked_sockets) {
+        inside_connected->m_linked_sockets.append(outside_connected);
+        outside_connected->m_linked_group_inputs.append(inside_connected);
+      }
+    }
+
+    outside_group->m_linked_sockets.clear();
+    inside_group->m_linked_sockets.clear();
+  }
+}
+
+BLI_NOINLINE void DerivedNodeTree::remove_expanded_group_interfaces(Vector<DNode *> &all_nodes)
+{
+  int index = 0;
+  while (index < all_nodes.size()) {
+    DNode &node = *all_nodes[index];
+    const NodeRef &node_ref = *node.m_node_ref;
+    if (node_ref.is_group_node() ||
+        (node.m_parent != nullptr &&
+         (node_ref.is_group_input_node() || node_ref.is_group_output_node()))) {
+      all_nodes.remove_and_reorder(index);
+      node.destruct_with_sockets();
+    }
+    else {
+      index++;
+    }
+  }
+}
+
+BLI_NOINLINE void DerivedNodeTree::remove_unused_group_inputs(
+    Vector<DGroupInput *> &all_group_inputs)
+{
+  int index = 0;
+  while (index < all_group_inputs.size()) {
+    DGroupInput &group_input = *all_group_inputs[index];
+    if (group_input.m_linked_sockets.is_empty()) {
+      all_group_inputs.remove_and_reorder(index);
+      group_input.~DGroupInput();
+    }
+    else {
+      index++;
+    }
+  }
+}
+
+void DNode::destruct_with_sockets()
+{
+  for (DInputSocket *socket : m_inputs) {
+    socket->~DInputSocket();
+  }
+  for (DOutputSocket *socket : m_outputs) {
+    socket->~DOutputSocket();
+  }
+  this->~DNode();
+}
+
+BLI_NOINLINE void DerivedNodeTree::store_in_this_and_init_ids(
+    Vector<DNode *> &&all_nodes,
+    Vector<DGroupInput *> &&all_group_inputs,
+    Vector<DParentNode *> &&all_parent_nodes)
+{
+  m_nodes_by_id = std::move(all_nodes);
+  m_group_inputs = std::move(all_group_inputs);
+  m_parent_nodes = std::move(all_parent_nodes);
+
+  for (uint node_index : m_nodes_by_id.index_range()) {
+    DNode *node = m_nodes_by_id[node_index];
+    node->m_id = node_index;
+
+    m_nodes_by_idname.lookup_or_add_default(node->idname()).append(node);
+
+    for (DInputSocket *socket : node->m_inputs) {
+      socket->m_id = m_sockets_by_id.append_and_get_index(socket);
+      m_input_sockets.append(socket);
+    }
+    for (DOutputSocket *socket : node->m_outputs) {
+      socket->m_id = m_sockets_by_id.append_and_get_index(socket);
+      m_output_sockets.append(socket);
+    }
+  }
+
+  for (uint i : m_group_inputs.index_range()) {
+    m_group_inputs[i]->m_id = i;
+  }
+}
+
+DerivedNodeTree::~DerivedNodeTree()
+{
+  for (DInputSocket *socket : m_input_sockets) {
+    socket->~DInputSocket();
+  }
+  for (DOutputSocket *socket : m_output_sockets) {
+    socket->~DOutputSocket();
+  }
+  for (DNode *node : m_nodes_by_id) {
+    node->~DNode();
+  }
+  for (DGroupInput *group_input : m_group_inputs) {
+    group_input->~DGroupInput();
+  }
+  for (DParentNode *parent : m_parent_nodes) {
+    parent->~DParentNode();
+  }
+}
+
+namespace Dot = blender::DotExport;
+
+static Dot::Cluster *get_cluster_for_parent(Dot::DirectedGraph &graph,
+                                            Map<const DParentNode *, Dot::Cluster *> &clusters,
+                                            const DParentNode *parent)
+{
+  if (parent == nullptr) {
+    return nullptr;
+  }
+  return clusters.lookup_or_add(parent, [&]() {
+    Dot::Cluster *parent_cluster = get_cluster_for_parent(graph, clusters, parent->parent());
+    bNodeTree *btree = (bNodeTree *)parent->node_ref().bnode()->id;
+    Dot::Cluster *new_cluster = &graph.new_cluster(parent->node_ref().name() + " / " +
+                                                   StringRef(btree->id.name + 2));
+    new_cluster->set_parent_cluster(parent_cluster);
+    return new_cluster;
+  });
+}
+
+std::string DerivedNodeTree::to_dot() const
+{
+  Dot::DirectedGraph digraph;
+  digraph.set_rankdir(Dot::Attr_rankdir::LeftToRight);
+
+  Map<const DNode *, Dot::NodeWithSocketsRef> dot_nodes;
+  Map<const DGroupInput *, Dot::NodeWithSocketsRef> dot_group_inputs;
+  Map<const DParentNode *, Dot::Cluster *> dot_clusters;
+
+  for (const DNode *node : m_nodes_by_id) {
+    Dot::Node &dot_node = digraph.new_node("");
+    dot_node.set_background_color("white");
+
+    Vector<std::string> input_names;
+    for (const DInputSocket *socket : node->inputs()) {
+      input_names.append(socket->name());
+    }
+    Vector<std::string> output_names;
+    for (const DOutputSocket *socket : node->outputs()) {
+      output_names.append(socket->name());
+    }
+
+    dot_nodes.add_new(node,
+                      Dot::NodeWithSocketsRef(dot_node, node->name(), input_names, output_names));
+
+    Dot::Cluster *cluster = get_cluster_for_parent(digraph, dot_clusters, node->parent());
+    dot_node.set_parent_cluster(cluster);
+  }
+
+  for (const DGroupInput *group_input : m_group_inputs) {
+    Dot::Node &dot_node = digraph.new_node("");
+    dot_node.set_background_color("white");
+
+    std::string group_input_name = group_input->name();
+    dot_group_inputs.add_new(
+        group_input, Dot::NodeWithSocketsRef(dot_node, "Group Input", {}, {group_input_name}));
+
+    Dot::Cluster *cluster = get_cluster_for_parent(digraph, dot_clusters, group_input->parent());
+    dot_node.set_parent_cluster(cluster);
+  }
+
+  for (const DNode *to_node : m_nodes_by_id) {
+    Dot::NodeWithSocketsRef &to_dot_node = dot_nodes.lookup(to_node);
+
+    for (const DInputSocket *to_socket : to_node->inputs()) {
+      for (const DOutputSocket *from_socket : to_socket->linked_sockets()) {
+        const DNode *from_node = &from_socket->node();
+        Dot::NodeWithSocketsRef &from_dot_node = dot_nodes.lookup(from_node);
+
+        digraph.new_edge(from_dot_node.output(from_socket->index()),
+                         to_dot_node.input(to_socket->index()));
+      }
+      for (const DGroupInput *group_input : to_socket->linked_group_inputs()) {
+        Dot::NodeWithSocketsRef &from_dot_node = dot_group_inputs.lookup(group_input);
+
+        digraph.new_edge(from_dot_node.output(0), to_dot_node.input(to_socket->index()));
+      }
+    }
+  }
+
+  digraph.set_random_cluster_bgcolors();
+  return digraph.to_dot_string();
+}
+
+}  // namespace BKE
diff --git a/source/blender/blenkernel/intern/node_tree_ref.cc b/source/blender/blenkernel/intern/node_tree_ref.cc
new file mode 100644
index 00000000000..517c1b85aff
--- /dev/null
+++ b/source/blender/blenkernel/intern/node_tree_ref.cc
@@ -0,0 +1,178 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#include "BKE_node_tree_ref.hh"
+
+#include "BLI_dot_export.hh"
+
+namespace BKE {
+
+NodeTreeRef::NodeTreeRef(bNodeTree *btree) : m_btree(btree)
+{
+  Map<bNode *, NodeRef *> node_mapping;
+
+  LISTBASE_FOREACH (bNode *, bnode, &btree->nodes) {
+    NodeRef &node = *m_allocator.construct<NodeRef>();
+
+    node.m_tree = this;
+    node.m_bnode = bnode;
+    node.m_id = m_nodes_by_id.append_and_get_index(&node);
+    RNA_pointer_create(&btree->id, &RNA_Node, bnode, &node.m_rna);
+
+    LISTBASE_FOREACH (bNodeSocket *, bsocket, &bnode->inputs) {
+      InputSocketRef &socket = *m_allocator.construct<InputSocketRef>();
+      socket.m_node = &node;
+      socket.m_index = node.m_inputs.append_and_get_index(&socket);
+      socket.m_is_input = true;
+      socket.m_bsocket = bsocket;
+      socket.m_id = m_sockets_by_id.append_and_get_index(&socket);
+      RNA_pointer_create(&btree->id, &RNA_NodeSocket, bsocket, &socket.m_rna);
+    }
+
+    LISTBASE_FOREACH (bNodeSocket *, bsocket, &bnode->outputs) {
+      OutputSocketRef &socket = *m_allocator.construct<OutputSocketRef>();
+      socket.m_node = &node;
+      socket.m_index = node.m_outputs.append_and_get_index(&socket);
+      socket.m_is_input = false;
+      socket.m_bsocket = bsocket;
+      socket.m_id = m_sockets_by_id.append_and_get_index(&socket);
+      RNA_pointer_create(&btree->id, &RNA_NodeSocket, bsocket, &socket.m_rna);
+    }
+
+    m_input_sockets.extend(node.m_inputs);
+    m_output_sockets.extend(node.m_outputs);
+
+    node_mapping.add_new(bnode, &node);
+  }
+
+  LISTBASE_FOREACH (bNodeLink *, blink, &btree->links) {
+    OutputSocketRef &from_socket = this->find_output_socket(
+        node_mapping, blink->fromnode, blink->fromsock);
+    InputSocketRef &to_socket = this->find_input_socket(
+        node_mapping, blink->tonode, blink->tosock);
+
+    from_socket.m_directly_linked_sockets.append(&to_socket);
+    to_socket.m_directly_linked_sockets.append(&from_socket);
+  }
+
+  for (OutputSocketRef *socket : m_output_sockets) {
+    if (!socket->m_node->is_reroute_node()) {
+      this->find_targets_skipping_reroutes(*socket, socket->m_linked_sockets);
+      for (SocketRef *target : socket->m_linked_sockets) {
+        target->m_linked_sockets.append(socket);
+      }
+    }
+  }
+
+  for (NodeRef *node : m_nodes_by_id) {
+    m_nodes_by_idname.lookup_or_add_default(node->idname()).append(node);
+  }
+}
+
+NodeTreeRef::~NodeTreeRef()
+{
+  for (NodeRef *node : m_nodes_by_id) {
+    node->~NodeRef();
+  }
+  for (InputSocketRef *socket : m_input_sockets) {
+    socket->~InputSocketRef();
+  }
+  for (OutputSocketRef *socket : m_output_sockets) {
+    socket->~OutputSocketRef();
+  }
+}
+
+InputSocketRef &NodeTreeRef::find_input_socket(Map<bNode *, NodeRef *> &node_mapping,
+                                               bNode *bnode,
+                                               bNodeSocket *bsocket)
+{
+  NodeRef *node = node_mapping.lookup(bnode);
+  for (SocketRef *socket : node->m_inputs) {
+    if (socket->m_bsocket == bsocket) {
+      return *(InputSocketRef *)socket;
+    }
+  }
+  BLI_assert(false);
+  return *node->m_inputs[0];
+}
+
+OutputSocketRef &NodeTreeRef::find_output_socket(Map<bNode *, NodeRef *> &node_mapping,
+                                                 bNode *bnode,
+                                                 bNodeSocket *bsocket)
+{
+  NodeRef *node = node_mapping.lookup(bnode);
+  for (SocketRef *socket : node->m_outputs) {
+    if (socket->m_bsocket == bsocket) {
+      return *(OutputSocketRef *)socket;
+    }
+  }
+  BLI_assert(false);
+  return *node->m_outputs[0];
+}
+
+void NodeTreeRef::find_targets_skipping_reroutes(OutputSocketRef &socket,
+                                                 Vector<SocketRef *> &r_targets)
+{
+  for (SocketRef *direct_target : socket.m_directly_linked_sockets) {
+    if (direct_target->m_node->is_reroute_node()) {
+      this->find_targets_skipping_reroutes(*direct_target->m_node->m_outputs[0], r_targets);
+    }
+    else {
+      r_targets.append_non_duplicates(direct_target);
+    }
+  }
+}
+
+std::string NodeTreeRef::to_dot() const
+{
+  namespace Dot = blender::DotExport;
+
+  Dot::DirectedGraph digraph;
+  digraph.set_rankdir(Dot::Attr_rankdir::LeftToRight);
+
+  Map<const NodeRef *, Dot::NodeWithSocketsRef> dot_nodes;
+
+  for (const NodeRef *node : m_nodes_by_id) {
+    Dot::Node &dot_node = digraph.new_node("");
+    dot_node.set_background_color("white");
+
+    Vector<std::string> input_names;
+    Vector<std::string> output_names;
+    for (const InputSocketRef *socket : node->inputs()) {
+      input_names.append(socket->name());
+    }
+    for (const OutputSocketRef *socket : node->outputs()) {
+      output_names.append(socket->name());
+    }
+
+    dot_nodes.add_new(node,
+                      Dot::NodeWithSocketsRef(dot_node, node->name(), input_names, output_names));
+  }
+
+  for (const OutputSocketRef *from_socket : m_output_sockets) {
+    for (const InputSocketRef *to_socket : from_socket->directly_linked_sockets()) {
+      Dot::NodeWithSocketsRef &from_dot_node = dot_nodes.lookup(&from_socket->node());
+      Dot::NodeWithSocketsRef &to_dot_node = dot_nodes.lookup(&to_socket->node());
+
+      digraph.new_edge(from_dot_node.output(from_socket->index()),
+                       to_dot_node.input(to_socket->index()));
+    }
+  }
+
+  return digraph.to_dot_string();
+}
+
+}  // namespace BKE