Cleanup: comments (long lines) in blenkernel
[blender.git] / source / blender / blenkernel / intern / node.c
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  * The Original Code is Copyright (C) 2005 Blender Foundation.
17  * All rights reserved.
18  */
19
20 /** \file
21  * \ingroup bke
22  */
23
24 #include "CLG_log.h"
25
26 #include "MEM_guardedalloc.h"
27
28 #include <stdlib.h>
29 #include <stddef.h>
30 #include <string.h>
31 #include <limits.h>
32
33 #include "DNA_action_types.h"
34 #include "DNA_anim_types.h"
35 #include "DNA_light_types.h"
36 #include "DNA_material_types.h"
37 #include "DNA_node_types.h"
38 #include "DNA_scene_types.h"
39 #include "DNA_texture_types.h"
40 #include "DNA_world_types.h"
41 #include "DNA_linestyle_types.h"
42
43 #include "BLI_listbase.h"
44 #include "BLI_math.h"
45 #include "BLI_path_util.h"
46 #include "BLI_string.h"
47 #include "BLI_string_utils.h"
48 #include "BLI_utildefines.h"
49
50 #include "BLT_translation.h"
51
52 #include "BKE_animsys.h"
53 #include "BKE_global.h"
54 #include "BKE_idprop.h"
55 #include "BKE_library.h"
56 #include "BKE_main.h"
57 #include "BKE_node.h"
58
59 #include "BLI_ghash.h"
60 #include "BLI_threads.h"
61 #include "RNA_access.h"
62 #include "RNA_define.h"
63
64 #include "NOD_socket.h"
65 #include "NOD_common.h"
66 #include "NOD_composite.h"
67 #include "NOD_shader.h"
68 #include "NOD_texture.h"
69
70 #include "DEG_depsgraph.h"
71 #include "DEG_depsgraph_build.h"
72
73 #define NODE_DEFAULT_MAX_WIDTH 700
74
75 /* Fallback types for undefined tree, nodes, sockets */
76 static bNodeTreeType NodeTreeTypeUndefined;
77 bNodeType NodeTypeUndefined;
78 bNodeSocketType NodeSocketTypeUndefined;
79
80 static CLG_LogRef LOG = {"bke.node"};
81
82 static void node_add_sockets_from_type(bNodeTree *ntree, bNode *node, bNodeType *ntype)
83 {
84   bNodeSocketTemplate *sockdef;
85   /* bNodeSocket *sock; */ /* UNUSED */
86
87   if (ntype->inputs) {
88     sockdef = ntype->inputs;
89     while (sockdef->type != -1) {
90       /* sock = */ node_add_socket_from_template(ntree, node, sockdef, SOCK_IN);
91
92       sockdef++;
93     }
94   }
95   if (ntype->outputs) {
96     sockdef = ntype->outputs;
97     while (sockdef->type != -1) {
98       /* sock = */ node_add_socket_from_template(ntree, node, sockdef, SOCK_OUT);
99
100       sockdef++;
101     }
102   }
103 }
104
105 /* Note: This function is called to initialize node data based on the type.
106  * The bNodeType may not be registered at creation time of the node,
107  * so this can be delayed until the node type gets registered.
108  */
109 static void node_init(const struct bContext *C, bNodeTree *ntree, bNode *node)
110 {
111   bNodeType *ntype = node->typeinfo;
112   if (ntype == &NodeTypeUndefined) {
113     return;
114   }
115
116   /* only do this once */
117   if (node->flag & NODE_INIT) {
118     return;
119   }
120
121   node->flag = NODE_SELECT | NODE_OPTIONS | ntype->flag;
122   node->width = ntype->width;
123   node->miniwidth = 42.0f;
124   node->height = ntype->height;
125   node->color[0] = node->color[1] = node->color[2] = 0.608; /* default theme color */
126   /* initialize the node name with the node label.
127    * note: do this after the initfunc so nodes get their data set which may be used in naming
128    * (node groups for example) */
129   /* XXX Do not use nodeLabel() here, it returns translated content for UI,
130    *     which should *only* be used in UI, *never* in data...
131    *     Data have their own translation option!
132    *     This solution may be a bit rougher than nodeLabel()'s returned string, but it's simpler
133    *     than adding "do_translate" flags to this func (and labelfunc() as well). */
134   BLI_strncpy(node->name, DATA_(ntype->ui_name), NODE_MAXSTR);
135   nodeUniqueName(ntree, node);
136
137   node_add_sockets_from_type(ntree, node, ntype);
138
139   if (ntype->initfunc != NULL) {
140     ntype->initfunc(ntree, node);
141   }
142
143   if (ntree->typeinfo->node_add_init != NULL) {
144     ntree->typeinfo->node_add_init(ntree, node);
145   }
146
147   if (node->id) {
148     id_us_plus(node->id);
149   }
150
151   /* extra init callback */
152   if (ntype->initfunc_api) {
153     PointerRNA ptr;
154     RNA_pointer_create((ID *)ntree, &RNA_Node, node, &ptr);
155
156     /* XXX Warning: context can be NULL in case nodes are added in do_versions.
157      * Delayed init is not supported for nodes with context-based initfunc_api atm.
158      */
159     BLI_assert(C != NULL);
160     ntype->initfunc_api(C, &ptr);
161   }
162
163   node->flag |= NODE_INIT;
164 }
165
166 static void ntree_set_typeinfo(bNodeTree *ntree, bNodeTreeType *typeinfo)
167 {
168   if (typeinfo) {
169     ntree->typeinfo = typeinfo;
170
171     /* deprecated integer type */
172     ntree->type = typeinfo->type;
173   }
174   else {
175     ntree->typeinfo = &NodeTreeTypeUndefined;
176
177     ntree->init &= ~NTREE_TYPE_INIT;
178   }
179 }
180
181 static void node_set_typeinfo(const struct bContext *C,
182                               bNodeTree *ntree,
183                               bNode *node,
184                               bNodeType *typeinfo)
185 {
186   /* for nodes saved in older versions storage can get lost, make undefined then */
187   if (node->flag & NODE_INIT) {
188     if (typeinfo && typeinfo->storagename[0] && !node->storage) {
189       typeinfo = NULL;
190     }
191   }
192
193   if (typeinfo) {
194     node->typeinfo = typeinfo;
195
196     /* deprecated integer type */
197     node->type = typeinfo->type;
198
199     /* initialize the node if necessary */
200     node_init(C, ntree, node);
201   }
202   else {
203     node->typeinfo = &NodeTypeUndefined;
204
205     ntree->init &= ~NTREE_TYPE_INIT;
206   }
207 }
208
209 static void node_socket_set_typeinfo(bNodeTree *ntree,
210                                      bNodeSocket *sock,
211                                      bNodeSocketType *typeinfo)
212 {
213   if (typeinfo) {
214     sock->typeinfo = typeinfo;
215
216     /* deprecated integer type */
217     sock->type = typeinfo->type;
218
219     if (sock->default_value == NULL) {
220       /* initialize the default_value pointer used by standard socket types */
221       node_socket_init_default_value(sock);
222     }
223   }
224   else {
225     sock->typeinfo = &NodeSocketTypeUndefined;
226
227     ntree->init &= ~NTREE_TYPE_INIT;
228   }
229 }
230
231 /* Set specific typeinfo pointers in all node trees on register/unregister */
232 static void update_typeinfo(Main *bmain,
233                             const struct bContext *C,
234                             bNodeTreeType *treetype,
235                             bNodeType *nodetype,
236                             bNodeSocketType *socktype,
237                             bool unregister)
238 {
239   if (!bmain) {
240     return;
241   }
242
243   FOREACH_NODETREE_BEGIN (bmain, ntree, id) {
244     bNode *node;
245     bNodeSocket *sock;
246
247     ntree->init |= NTREE_TYPE_INIT;
248
249     if (treetype && STREQ(ntree->idname, treetype->idname)) {
250       ntree_set_typeinfo(ntree, unregister ? NULL : treetype);
251     }
252
253     /* initialize nodes */
254     for (node = ntree->nodes.first; node; node = node->next) {
255       if (nodetype && STREQ(node->idname, nodetype->idname)) {
256         node_set_typeinfo(C, ntree, node, unregister ? NULL : nodetype);
257       }
258
259       /* initialize node sockets */
260       for (sock = node->inputs.first; sock; sock = sock->next) {
261         if (socktype && STREQ(sock->idname, socktype->idname)) {
262           node_socket_set_typeinfo(ntree, sock, unregister ? NULL : socktype);
263         }
264       }
265       for (sock = node->outputs.first; sock; sock = sock->next) {
266         if (socktype && STREQ(sock->idname, socktype->idname)) {
267           node_socket_set_typeinfo(ntree, sock, unregister ? NULL : socktype);
268         }
269       }
270     }
271
272     /* initialize tree sockets */
273     for (sock = ntree->inputs.first; sock; sock = sock->next) {
274       if (socktype && STREQ(sock->idname, socktype->idname)) {
275         node_socket_set_typeinfo(ntree, sock, unregister ? NULL : socktype);
276       }
277     }
278     for (sock = ntree->outputs.first; sock; sock = sock->next) {
279       if (socktype && STREQ(sock->idname, socktype->idname)) {
280         node_socket_set_typeinfo(ntree, sock, unregister ? NULL : socktype);
281       }
282     }
283   }
284   FOREACH_NODETREE_END;
285 }
286
287 /* Try to initialize all typeinfo in a node tree.
288  * NB: In general undefined typeinfo is a perfectly valid case,
289  * the type may just be registered later.
290  * In that case the update_typeinfo function will set typeinfo on registration
291  * and do necessary updates.
292  */
293 void ntreeSetTypes(const struct bContext *C, bNodeTree *ntree)
294 {
295   bNode *node;
296   bNodeSocket *sock;
297
298   ntree->init |= NTREE_TYPE_INIT;
299
300   ntree_set_typeinfo(ntree, ntreeTypeFind(ntree->idname));
301
302   for (node = ntree->nodes.first; node; node = node->next) {
303     node_set_typeinfo(C, ntree, node, nodeTypeFind(node->idname));
304
305     for (sock = node->inputs.first; sock; sock = sock->next) {
306       node_socket_set_typeinfo(ntree, sock, nodeSocketTypeFind(sock->idname));
307     }
308     for (sock = node->outputs.first; sock; sock = sock->next) {
309       node_socket_set_typeinfo(ntree, sock, nodeSocketTypeFind(sock->idname));
310     }
311   }
312
313   for (sock = ntree->inputs.first; sock; sock = sock->next) {
314     node_socket_set_typeinfo(ntree, sock, nodeSocketTypeFind(sock->idname));
315   }
316   for (sock = ntree->outputs.first; sock; sock = sock->next) {
317     node_socket_set_typeinfo(ntree, sock, nodeSocketTypeFind(sock->idname));
318   }
319 }
320
321 static GHash *nodetreetypes_hash = NULL;
322 static GHash *nodetypes_hash = NULL;
323 static GHash *nodesockettypes_hash = NULL;
324 static SpinLock spin;
325
326 bNodeTreeType *ntreeTypeFind(const char *idname)
327 {
328   bNodeTreeType *nt;
329
330   if (idname[0]) {
331     nt = BLI_ghash_lookup(nodetreetypes_hash, idname);
332     if (nt) {
333       return nt;
334     }
335   }
336
337   return NULL;
338 }
339
340 void ntreeTypeAdd(bNodeTreeType *nt)
341 {
342   BLI_ghash_insert(nodetreetypes_hash, nt->idname, nt);
343   /* XXX pass Main to register function? */
344   /* Probably not. It is pretty much expected we want to update G_MAIN here I think -
345    * or we'd want to update *all* active Mains, which we cannot do anyway currently. */
346   update_typeinfo(G_MAIN, NULL, nt, NULL, NULL, false);
347 }
348
349 /* callback for hash value free function */
350 static void ntree_free_type(void *treetype_v)
351 {
352   bNodeTreeType *treetype = treetype_v;
353   /* XXX pass Main to unregister function? */
354   /* Probably not. It is pretty much expected we want to update G_MAIN here I think -
355    * or we'd want to update *all* active Mains, which we cannot do anyway currently. */
356   update_typeinfo(G_MAIN, NULL, treetype, NULL, NULL, true);
357   MEM_freeN(treetype);
358 }
359
360 void ntreeTypeFreeLink(const bNodeTreeType *nt)
361 {
362   BLI_ghash_remove(nodetreetypes_hash, nt->idname, NULL, ntree_free_type);
363 }
364
365 bool ntreeIsRegistered(bNodeTree *ntree)
366 {
367   return (ntree->typeinfo != &NodeTreeTypeUndefined);
368 }
369
370 GHashIterator *ntreeTypeGetIterator(void)
371 {
372   return BLI_ghashIterator_new(nodetreetypes_hash);
373 }
374
375 bNodeType *nodeTypeFind(const char *idname)
376 {
377   bNodeType *nt;
378
379   if (idname[0]) {
380     nt = BLI_ghash_lookup(nodetypes_hash, idname);
381     if (nt) {
382       return nt;
383     }
384   }
385
386   return NULL;
387 }
388
389 static void free_dynamic_typeinfo(bNodeType *ntype)
390 {
391   if (ntype->type == NODE_DYNAMIC) {
392     if (ntype->inputs) {
393       MEM_freeN(ntype->inputs);
394     }
395     if (ntype->outputs) {
396       MEM_freeN(ntype->outputs);
397     }
398   }
399 }
400
401 /* callback for hash value free function */
402 static void node_free_type(void *nodetype_v)
403 {
404   bNodeType *nodetype = nodetype_v;
405   /* XXX pass Main to unregister function? */
406   /* Probably not. It is pretty much expected we want to update G_MAIN here I think -
407    * or we'd want to update *all* active Mains, which we cannot do anyway currently. */
408   update_typeinfo(G_MAIN, NULL, NULL, nodetype, NULL, true);
409
410   /* XXX deprecated */
411   if (nodetype->type == NODE_DYNAMIC) {
412     free_dynamic_typeinfo(nodetype);
413   }
414
415   if (nodetype->needs_free) {
416     MEM_freeN(nodetype);
417   }
418 }
419
420 void nodeRegisterType(bNodeType *nt)
421 {
422   /* debug only: basic verification of registered types */
423   BLI_assert(nt->idname[0] != '\0');
424   BLI_assert(nt->poll != NULL);
425
426   BLI_ghash_insert(nodetypes_hash, nt->idname, nt);
427   /* XXX pass Main to register function? */
428   /* Probably not. It is pretty much expected we want to update G_MAIN here I think -
429    * or we'd want to update *all* active Mains, which we cannot do anyway currently. */
430   update_typeinfo(G_MAIN, NULL, NULL, nt, NULL, false);
431 }
432
433 void nodeUnregisterType(bNodeType *nt)
434 {
435   BLI_ghash_remove(nodetypes_hash, nt->idname, NULL, node_free_type);
436 }
437
438 bool nodeIsRegistered(bNode *node)
439 {
440   return (node->typeinfo != &NodeTypeUndefined);
441 }
442
443 GHashIterator *nodeTypeGetIterator(void)
444 {
445   return BLI_ghashIterator_new(nodetypes_hash);
446 }
447
448 bNodeSocketType *nodeSocketTypeFind(const char *idname)
449 {
450   bNodeSocketType *st;
451
452   if (idname[0]) {
453     st = BLI_ghash_lookup(nodesockettypes_hash, idname);
454     if (st) {
455       return st;
456     }
457   }
458
459   return NULL;
460 }
461
462 /* callback for hash value free function */
463 static void node_free_socket_type(void *socktype_v)
464 {
465   bNodeSocketType *socktype = socktype_v;
466   /* XXX pass Main to unregister function? */
467   /* Probably not. It is pretty much expected we want to update G_MAIN here I think -
468    * or we'd want to update *all* active Mains, which we cannot do anyway currently. */
469   update_typeinfo(G_MAIN, NULL, NULL, NULL, socktype, true);
470
471   MEM_freeN(socktype);
472 }
473
474 void nodeRegisterSocketType(bNodeSocketType *st)
475 {
476   BLI_ghash_insert(nodesockettypes_hash, (void *)st->idname, st);
477   /* XXX pass Main to register function? */
478   /* Probably not. It is pretty much expected we want to update G_MAIN here I think -
479    * or we'd want to update *all* active Mains, which we cannot do anyway currently. */
480   update_typeinfo(G_MAIN, NULL, NULL, NULL, st, false);
481 }
482
483 void nodeUnregisterSocketType(bNodeSocketType *st)
484 {
485   BLI_ghash_remove(nodesockettypes_hash, st->idname, NULL, node_free_socket_type);
486 }
487
488 bool nodeSocketIsRegistered(bNodeSocket *sock)
489 {
490   return (sock->typeinfo != &NodeSocketTypeUndefined);
491 }
492
493 GHashIterator *nodeSocketTypeGetIterator(void)
494 {
495   return BLI_ghashIterator_new(nodesockettypes_hash);
496 }
497
498 struct bNodeSocket *nodeFindSocket(bNode *node, int in_out, const char *identifier)
499 {
500   bNodeSocket *sock = (in_out == SOCK_IN ? node->inputs.first : node->outputs.first);
501   for (; sock; sock = sock->next) {
502     if (STREQ(sock->identifier, identifier)) {
503       return sock;
504     }
505   }
506   return NULL;
507 }
508
509 /* find unique socket identifier */
510 static bool unique_identifier_check(void *arg, const char *identifier)
511 {
512   struct ListBase *lb = arg;
513   bNodeSocket *sock;
514   for (sock = lb->first; sock; sock = sock->next) {
515     if (STREQ(sock->identifier, identifier)) {
516       return true;
517     }
518   }
519   return false;
520 }
521
522 static bNodeSocket *make_socket(bNodeTree *ntree,
523                                 bNode *UNUSED(node),
524                                 int in_out,
525                                 ListBase *lb,
526                                 const char *idname,
527                                 const char *identifier,
528                                 const char *name)
529 {
530   bNodeSocket *sock;
531   char auto_identifier[MAX_NAME];
532
533   if (identifier && identifier[0] != '\0') {
534     /* use explicit identifier */
535     BLI_strncpy(auto_identifier, identifier, sizeof(auto_identifier));
536   }
537   else {
538     /* if no explicit identifier is given, assign a unique identifier based on the name */
539     BLI_strncpy(auto_identifier, name, sizeof(auto_identifier));
540   }
541   /* make the identifier unique */
542   BLI_uniquename_cb(
543       unique_identifier_check, lb, "socket", '.', auto_identifier, sizeof(auto_identifier));
544
545   sock = MEM_callocN(sizeof(bNodeSocket), "sock");
546   sock->in_out = in_out;
547
548   BLI_strncpy(sock->identifier, auto_identifier, NODE_MAXSTR);
549   sock->limit = (in_out == SOCK_IN ? 1 : 0xFFF);
550
551   BLI_strncpy(sock->name, name, NODE_MAXSTR);
552   sock->storage = NULL;
553   sock->flag |= SOCK_COLLAPSED;
554   sock->type = SOCK_CUSTOM; /* int type undefined by default */
555
556   BLI_strncpy(sock->idname, idname, sizeof(sock->idname));
557   node_socket_set_typeinfo(ntree, sock, nodeSocketTypeFind(idname));
558
559   return sock;
560 }
561
562 void nodeModifySocketType(
563     bNodeTree *ntree, bNode *UNUSED(node), bNodeSocket *sock, int type, int subtype)
564 {
565   const char *idname = nodeStaticSocketType(type, subtype);
566
567   if (!idname) {
568     CLOG_ERROR(&LOG, "static node socket type %d undefined", type);
569     return;
570   }
571
572   if (sock->default_value) {
573     MEM_freeN(sock->default_value);
574     sock->default_value = NULL;
575   }
576
577   sock->type = type;
578   BLI_strncpy(sock->idname, idname, sizeof(sock->idname));
579   node_socket_set_typeinfo(ntree, sock, nodeSocketTypeFind(idname));
580 }
581
582 bNodeSocket *nodeAddSocket(bNodeTree *ntree,
583                            bNode *node,
584                            int in_out,
585                            const char *idname,
586                            const char *identifier,
587                            const char *name)
588 {
589   ListBase *lb = (in_out == SOCK_IN ? &node->inputs : &node->outputs);
590   bNodeSocket *sock = make_socket(ntree, node, in_out, lb, idname, identifier, name);
591
592   BLI_remlink(lb, sock); /* does nothing for new socket */
593   BLI_addtail(lb, sock);
594
595   node->update |= NODE_UPDATE;
596
597   return sock;
598 }
599
600 bNodeSocket *nodeInsertSocket(bNodeTree *ntree,
601                               bNode *node,
602                               int in_out,
603                               const char *idname,
604                               bNodeSocket *next_sock,
605                               const char *identifier,
606                               const char *name)
607 {
608   ListBase *lb = (in_out == SOCK_IN ? &node->inputs : &node->outputs);
609   bNodeSocket *sock = make_socket(ntree, node, in_out, lb, idname, identifier, name);
610
611   BLI_remlink(lb, sock); /* does nothing for new socket */
612   BLI_insertlinkbefore(lb, next_sock, sock);
613
614   node->update |= NODE_UPDATE;
615
616   return sock;
617 }
618
619 const char *nodeStaticSocketType(int type, int subtype)
620 {
621   switch (type) {
622     case SOCK_FLOAT:
623       switch (subtype) {
624         case PROP_UNSIGNED:
625           return "NodeSocketFloatUnsigned";
626         case PROP_PERCENTAGE:
627           return "NodeSocketFloatPercentage";
628         case PROP_FACTOR:
629           return "NodeSocketFloatFactor";
630         case PROP_ANGLE:
631           return "NodeSocketFloatAngle";
632         case PROP_TIME:
633           return "NodeSocketFloatTime";
634         case PROP_NONE:
635         default:
636           return "NodeSocketFloat";
637       }
638     case SOCK_INT:
639       switch (subtype) {
640         case PROP_UNSIGNED:
641           return "NodeSocketIntUnsigned";
642         case PROP_PERCENTAGE:
643           return "NodeSocketIntPercentage";
644         case PROP_FACTOR:
645           return "NodeSocketIntFactor";
646         case PROP_NONE:
647         default:
648           return "NodeSocketInt";
649       }
650     case SOCK_BOOLEAN:
651       return "NodeSocketBool";
652     case SOCK_VECTOR:
653       switch (subtype) {
654         case PROP_TRANSLATION:
655           return "NodeSocketVectorTranslation";
656         case PROP_DIRECTION:
657           return "NodeSocketVectorDirection";
658         case PROP_VELOCITY:
659           return "NodeSocketVectorVelocity";
660         case PROP_ACCELERATION:
661           return "NodeSocketVectorAcceleration";
662         case PROP_EULER:
663           return "NodeSocketVectorEuler";
664         case PROP_XYZ:
665           return "NodeSocketVectorXYZ";
666         case PROP_NONE:
667         default:
668           return "NodeSocketVector";
669       }
670     case SOCK_RGBA:
671       return "NodeSocketColor";
672     case SOCK_STRING:
673       return "NodeSocketString";
674     case SOCK_SHADER:
675       return "NodeSocketShader";
676   }
677   return NULL;
678 }
679
680 const char *nodeStaticSocketInterfaceType(int type, int subtype)
681 {
682   switch (type) {
683     case SOCK_FLOAT:
684       switch (subtype) {
685         case PROP_UNSIGNED:
686           return "NodeSocketInterfaceFloatUnsigned";
687         case PROP_PERCENTAGE:
688           return "NodeSocketInterfaceFloatPercentage";
689         case PROP_FACTOR:
690           return "NodeSocketInterfaceFloatFactor";
691         case PROP_ANGLE:
692           return "NodeSocketInterfaceFloatAngle";
693         case PROP_TIME:
694           return "NodeSocketInterfaceFloatTime";
695         case PROP_NONE:
696         default:
697           return "NodeSocketInterfaceFloat";
698       }
699     case SOCK_INT:
700       switch (subtype) {
701         case PROP_UNSIGNED:
702           return "NodeSocketInterfaceIntUnsigned";
703         case PROP_PERCENTAGE:
704           return "NodeSocketInterfaceIntPercentage";
705         case PROP_FACTOR:
706           return "NodeSocketInterfaceIntFactor";
707         case PROP_NONE:
708         default:
709           return "NodeSocketInterfaceInt";
710       }
711     case SOCK_BOOLEAN:
712       return "NodeSocketInterfaceBool";
713     case SOCK_VECTOR:
714       switch (subtype) {
715         case PROP_TRANSLATION:
716           return "NodeSocketInterfaceVectorTranslation";
717         case PROP_DIRECTION:
718           return "NodeSocketInterfaceVectorDirection";
719         case PROP_VELOCITY:
720           return "NodeSocketInterfaceVectorVelocity";
721         case PROP_ACCELERATION:
722           return "NodeSocketInterfaceVectorAcceleration";
723         case PROP_EULER:
724           return "NodeSocketInterfaceVectorEuler";
725         case PROP_XYZ:
726           return "NodeSocketInterfaceVectorXYZ";
727         case PROP_NONE:
728         default:
729           return "NodeSocketInterfaceVector";
730       }
731     case SOCK_RGBA:
732       return "NodeSocketInterfaceColor";
733     case SOCK_STRING:
734       return "NodeSocketInterfaceString";
735     case SOCK_SHADER:
736       return "NodeSocketInterfaceShader";
737   }
738   return NULL;
739 }
740
741 bNodeSocket *nodeAddStaticSocket(bNodeTree *ntree,
742                                  bNode *node,
743                                  int in_out,
744                                  int type,
745                                  int subtype,
746                                  const char *identifier,
747                                  const char *name)
748 {
749   const char *idname = nodeStaticSocketType(type, subtype);
750   bNodeSocket *sock;
751
752   if (!idname) {
753     CLOG_ERROR(&LOG, "static node socket type %d undefined", type);
754     return NULL;
755   }
756
757   sock = nodeAddSocket(ntree, node, in_out, idname, identifier, name);
758   sock->type = type;
759   return sock;
760 }
761
762 bNodeSocket *nodeInsertStaticSocket(bNodeTree *ntree,
763                                     bNode *node,
764                                     int in_out,
765                                     int type,
766                                     int subtype,
767                                     bNodeSocket *next_sock,
768                                     const char *identifier,
769                                     const char *name)
770 {
771   const char *idname = nodeStaticSocketType(type, subtype);
772   bNodeSocket *sock;
773
774   if (!idname) {
775     CLOG_ERROR(&LOG, "static node socket type %d undefined", type);
776     return NULL;
777   }
778
779   sock = nodeInsertSocket(ntree, node, in_out, idname, next_sock, identifier, name);
780   sock->type = type;
781   return sock;
782 }
783
784 static void node_socket_free(bNodeTree *UNUSED(ntree),
785                              bNodeSocket *sock,
786                              bNode *UNUSED(node),
787                              const bool do_id_user)
788 {
789   if (sock->prop) {
790     IDP_FreeProperty_ex(sock->prop, do_id_user);
791     MEM_freeN(sock->prop);
792   }
793
794   if (sock->default_value) {
795     MEM_freeN(sock->default_value);
796   }
797 }
798
799 void nodeRemoveSocket(bNodeTree *ntree, bNode *node, bNodeSocket *sock)
800 {
801   bNodeLink *link, *next;
802
803   for (link = ntree->links.first; link; link = next) {
804     next = link->next;
805     if (link->fromsock == sock || link->tosock == sock) {
806       nodeRemLink(ntree, link);
807     }
808   }
809
810   /* this is fast, this way we don't need an in_out argument */
811   BLI_remlink(&node->inputs, sock);
812   BLI_remlink(&node->outputs, sock);
813
814   node_socket_free(ntree, sock, node, true);
815   MEM_freeN(sock);
816
817   node->update |= NODE_UPDATE;
818 }
819
820 void nodeRemoveAllSockets(bNodeTree *ntree, bNode *node)
821 {
822   bNodeSocket *sock, *sock_next;
823   bNodeLink *link, *next;
824
825   for (link = ntree->links.first; link; link = next) {
826     next = link->next;
827     if (link->fromnode == node || link->tonode == node) {
828       nodeRemLink(ntree, link);
829     }
830   }
831
832   for (sock = node->inputs.first; sock; sock = sock_next) {
833     sock_next = sock->next;
834     node_socket_free(ntree, sock, node, true);
835     MEM_freeN(sock);
836   }
837   BLI_listbase_clear(&node->inputs);
838
839   for (sock = node->outputs.first; sock; sock = sock_next) {
840     sock_next = sock->next;
841     node_socket_free(ntree, sock, node, true);
842     MEM_freeN(sock);
843   }
844   BLI_listbase_clear(&node->outputs);
845
846   node->update |= NODE_UPDATE;
847 }
848
849 /* finds a node based on its name */
850 bNode *nodeFindNodebyName(bNodeTree *ntree, const char *name)
851 {
852   return BLI_findstring(&ntree->nodes, name, offsetof(bNode, name));
853 }
854
855 /* finds a node based on given socket */
856 int nodeFindNode(bNodeTree *ntree, bNodeSocket *sock, bNode **nodep, int *sockindex)
857 {
858   int in_out = sock->in_out;
859   bNode *node;
860   bNodeSocket *tsock;
861   int index = 0;
862
863   for (node = ntree->nodes.first; node; node = node->next) {
864     tsock = (in_out == SOCK_IN ? node->inputs.first : node->outputs.first);
865     for (index = 0; tsock; tsock = tsock->next, index++) {
866       if (tsock == sock) {
867         break;
868       }
869     }
870     if (tsock) {
871       break;
872     }
873   }
874
875   if (node) {
876     *nodep = node;
877     if (sockindex) {
878       *sockindex = index;
879     }
880     return 1;
881   }
882
883   *nodep = NULL;
884   return 0;
885 }
886
887 /**
888  * \note Recursive
889  */
890 bNode *nodeFindRootParent(bNode *node)
891 {
892   if (node->parent) {
893     return nodeFindRootParent(node->parent);
894   }
895   else {
896     return node->type == NODE_FRAME ? node : NULL;
897   }
898 }
899
900 /**
901  * \returns true if \a child has \a parent as a parent/grandparent/...
902  * \note Recursive
903  */
904 bool nodeIsChildOf(const bNode *parent, const bNode *child)
905 {
906   if (parent == child) {
907     return true;
908   }
909   else if (child->parent) {
910     return nodeIsChildOf(parent, child->parent);
911   }
912   return false;
913 }
914
915 /**
916  * Iterate over a chain of nodes, starting with \a node_start, executing
917  * \a callback for each node (which can return false to end iterator).
918  *
919  * \param reversed: for backwards iteration
920  * \note Recursive
921  */
922 void nodeChainIter(const bNodeTree *ntree,
923                    const bNode *node_start,
924                    bool (*callback)(bNode *, bNode *, void *, const bool),
925                    void *userdata,
926                    const bool reversed)
927 {
928   bNodeLink *link;
929
930   for (link = ntree->links.first; link; link = link->next) {
931     if ((link->flag & NODE_LINK_VALID) == 0) {
932       /* Skip links marked as cyclic. */
933       continue;
934     }
935     if (link->tonode && link->fromnode) {
936       /* Is the link part of the chain meaning node_start == fromnode
937        * (or tonode for reversed case)? */
938       if ((reversed && (link->tonode == node_start)) ||
939           (!reversed && link->fromnode == node_start)) {
940         if (!callback(link->fromnode, link->tonode, userdata, reversed)) {
941           return;
942         }
943         nodeChainIter(
944             ntree, reversed ? link->fromnode : link->tonode, callback, userdata, reversed);
945       }
946     }
947   }
948 }
949
950 /**
951  * Iterate over all parents of \a node, executing \a callback for each parent
952  * (which can return false to end iterator)
953  *
954  * \note Recursive
955  */
956 void nodeParentsIter(bNode *node, bool (*callback)(bNode *, void *), void *userdata)
957 {
958   if (node->parent) {
959     if (!callback(node->parent, userdata)) {
960       return;
961     }
962     nodeParentsIter(node->parent, callback, userdata);
963   }
964 }
965
966 /* ************** Add stuff ********** */
967
968 /* Find the first available, non-duplicate name for a given node */
969 void nodeUniqueName(bNodeTree *ntree, bNode *node)
970 {
971   BLI_uniquename(
972       &ntree->nodes, node, DATA_("Node"), '.', offsetof(bNode, name), sizeof(node->name));
973 }
974
975 bNode *nodeAddNode(const struct bContext *C, bNodeTree *ntree, const char *idname)
976 {
977   bNode *node;
978
979   node = MEM_callocN(sizeof(bNode), "new node");
980   BLI_addtail(&ntree->nodes, node);
981
982   BLI_strncpy(node->idname, idname, sizeof(node->idname));
983   node_set_typeinfo(C, ntree, node, nodeTypeFind(idname));
984
985   ntree->update |= NTREE_UPDATE_NODES;
986
987   return node;
988 }
989
990 bNode *nodeAddStaticNode(const struct bContext *C, bNodeTree *ntree, int type)
991 {
992   const char *idname = NULL;
993
994   NODE_TYPES_BEGIN (ntype) {
995     /* do an extra poll here, because some int types are used
996      * for multiple node types, this helps find the desired type
997      */
998     if (ntype->type == type && (!ntype->poll || ntype->poll(ntype, ntree))) {
999       idname = ntype->idname;
1000       break;
1001     }
1002   }
1003   NODE_TYPES_END;
1004   if (!idname) {
1005     CLOG_ERROR(&LOG, "static node type %d undefined", type);
1006     return NULL;
1007   }
1008   return nodeAddNode(C, ntree, idname);
1009 }
1010
1011 static void node_socket_copy(bNodeSocket *sock_dst, bNodeSocket *sock_src, const int flag)
1012 {
1013   sock_src->new_sock = sock_dst;
1014
1015   if (sock_src->prop) {
1016     sock_dst->prop = IDP_CopyProperty_ex(sock_src->prop, flag);
1017   }
1018
1019   if (sock_src->default_value) {
1020     sock_dst->default_value = MEM_dupallocN(sock_src->default_value);
1021   }
1022
1023   sock_dst->stack_index = 0;
1024   /* XXX some compositor node (e.g. image, render layers) still store
1025    * some persistent buffer data here, need to clear this to avoid dangling pointers.
1026    */
1027   sock_dst->cache = NULL;
1028 }
1029
1030 /* keep socket listorder identical, for copying links */
1031 /* ntree is the target tree */
1032 bNode *BKE_node_copy_ex(bNodeTree *ntree, bNode *node_src, const int flag)
1033 {
1034   bNode *node_dst = MEM_callocN(sizeof(bNode), "dupli node");
1035   bNodeSocket *sock_dst, *sock_src;
1036   bNodeLink *link_dst, *link_src;
1037
1038   *node_dst = *node_src;
1039   /* can be called for nodes outside a node tree (e.g. clipboard) */
1040   if (ntree) {
1041     nodeUniqueName(ntree, node_dst);
1042
1043     BLI_addtail(&ntree->nodes, node_dst);
1044   }
1045
1046   BLI_duplicatelist(&node_dst->inputs, &node_src->inputs);
1047   for (sock_dst = node_dst->inputs.first, sock_src = node_src->inputs.first; sock_dst != NULL;
1048        sock_dst = sock_dst->next, sock_src = sock_src->next) {
1049     node_socket_copy(sock_dst, sock_src, flag);
1050   }
1051
1052   BLI_duplicatelist(&node_dst->outputs, &node_src->outputs);
1053   for (sock_dst = node_dst->outputs.first, sock_src = node_src->outputs.first; sock_dst != NULL;
1054        sock_dst = sock_dst->next, sock_src = sock_src->next) {
1055     node_socket_copy(sock_dst, sock_src, flag);
1056   }
1057
1058   if (node_src->prop) {
1059     node_dst->prop = IDP_CopyProperty_ex(node_src->prop, flag);
1060   }
1061
1062   BLI_duplicatelist(&node_dst->internal_links, &node_src->internal_links);
1063   for (link_dst = node_dst->internal_links.first, link_src = node_src->internal_links.first;
1064        link_dst != NULL;
1065        link_dst = link_dst->next, link_src = link_src->next) {
1066     link_dst->fromnode = node_dst;
1067     link_dst->tonode = node_dst;
1068     link_dst->fromsock = link_dst->fromsock->new_sock;
1069     link_dst->tosock = link_dst->tosock->new_sock;
1070   }
1071
1072   if ((flag & LIB_ID_CREATE_NO_USER_REFCOUNT) == 0) {
1073     id_us_plus(node_dst->id);
1074   }
1075
1076   if (node_src->typeinfo->copyfunc) {
1077     node_src->typeinfo->copyfunc(ntree, node_dst, node_src);
1078   }
1079
1080   node_src->new_node = node_dst;
1081   node_dst->new_node = NULL;
1082
1083   bool do_copy_api = !((flag & LIB_ID_CREATE_NO_MAIN) || (flag & LIB_ID_COPY_LOCALIZE));
1084   if (node_dst->typeinfo->copyfunc_api && do_copy_api) {
1085     PointerRNA ptr;
1086     RNA_pointer_create((ID *)ntree, &RNA_Node, node_dst, &ptr);
1087
1088     node_dst->typeinfo->copyfunc_api(&ptr, node_src);
1089   }
1090
1091   if (ntree) {
1092     ntree->update |= NTREE_UPDATE_NODES;
1093   }
1094
1095   return node_dst;
1096 }
1097
1098 /* also used via rna api, so we check for proper input output direction */
1099 bNodeLink *nodeAddLink(
1100     bNodeTree *ntree, bNode *fromnode, bNodeSocket *fromsock, bNode *tonode, bNodeSocket *tosock)
1101 {
1102   bNodeLink *link = NULL;
1103
1104   /* test valid input */
1105   BLI_assert(fromnode);
1106   BLI_assert(tonode);
1107
1108   if (fromsock->in_out == SOCK_OUT && tosock->in_out == SOCK_IN) {
1109     link = MEM_callocN(sizeof(bNodeLink), "link");
1110     if (ntree) {
1111       BLI_addtail(&ntree->links, link);
1112     }
1113     link->fromnode = fromnode;
1114     link->fromsock = fromsock;
1115     link->tonode = tonode;
1116     link->tosock = tosock;
1117   }
1118   else if (fromsock->in_out == SOCK_IN && tosock->in_out == SOCK_OUT) {
1119     /* OK but flip */
1120     link = MEM_callocN(sizeof(bNodeLink), "link");
1121     if (ntree) {
1122       BLI_addtail(&ntree->links, link);
1123     }
1124     link->fromnode = tonode;
1125     link->fromsock = tosock;
1126     link->tonode = fromnode;
1127     link->tosock = fromsock;
1128   }
1129
1130   if (ntree) {
1131     ntree->update |= NTREE_UPDATE_LINKS;
1132   }
1133
1134   return link;
1135 }
1136
1137 void nodeRemLink(bNodeTree *ntree, bNodeLink *link)
1138 {
1139   /* can be called for links outside a node tree (e.g. clipboard) */
1140   if (ntree) {
1141     BLI_remlink(&ntree->links, link);
1142   }
1143
1144   if (link->tosock) {
1145     link->tosock->link = NULL;
1146   }
1147   MEM_freeN(link);
1148
1149   if (ntree) {
1150     ntree->update |= NTREE_UPDATE_LINKS;
1151   }
1152 }
1153
1154 void nodeRemSocketLinks(bNodeTree *ntree, bNodeSocket *sock)
1155 {
1156   bNodeLink *link, *next;
1157
1158   for (link = ntree->links.first; link; link = next) {
1159     next = link->next;
1160     if (link->fromsock == sock || link->tosock == sock) {
1161       nodeRemLink(ntree, link);
1162     }
1163   }
1164
1165   ntree->update |= NTREE_UPDATE_LINKS;
1166 }
1167
1168 bool nodeLinkIsHidden(bNodeLink *link)
1169 {
1170   return nodeSocketIsHidden(link->fromsock) || nodeSocketIsHidden(link->tosock);
1171 }
1172
1173 void nodeInternalRelink(bNodeTree *ntree, bNode *node)
1174 {
1175   bNodeLink *link, *link_next;
1176
1177   /* store link pointers in output sockets, for efficient lookup */
1178   for (link = node->internal_links.first; link; link = link->next) {
1179     link->tosock->link = link;
1180   }
1181
1182   /* redirect downstream links */
1183   for (link = ntree->links.first; link; link = link_next) {
1184     link_next = link->next;
1185
1186     /* do we have internal link? */
1187     if (link->fromnode == node) {
1188       if (link->fromsock->link) {
1189         /* get the upstream input link */
1190         bNodeLink *fromlink = link->fromsock->link->fromsock->link;
1191         /* skip the node */
1192         if (fromlink) {
1193           link->fromnode = fromlink->fromnode;
1194           link->fromsock = fromlink->fromsock;
1195
1196           /* if the up- or downstream link is invalid,
1197            * the replacement link will be invalid too.
1198            */
1199           if (!(fromlink->flag & NODE_LINK_VALID)) {
1200             link->flag &= ~NODE_LINK_VALID;
1201           }
1202
1203           ntree->update |= NTREE_UPDATE_LINKS;
1204         }
1205         else {
1206           nodeRemLink(ntree, link);
1207         }
1208       }
1209       else {
1210         nodeRemLink(ntree, link);
1211       }
1212     }
1213   }
1214
1215   /* remove remaining upstream links */
1216   for (link = ntree->links.first; link; link = link_next) {
1217     link_next = link->next;
1218
1219     if (link->tonode == node) {
1220       nodeRemLink(ntree, link);
1221     }
1222   }
1223 }
1224
1225 void nodeToView(bNode *node, float x, float y, float *rx, float *ry)
1226 {
1227   if (node->parent) {
1228     nodeToView(node->parent, x + node->locx, y + node->locy, rx, ry);
1229   }
1230   else {
1231     *rx = x + node->locx;
1232     *ry = y + node->locy;
1233   }
1234 }
1235
1236 void nodeFromView(bNode *node, float x, float y, float *rx, float *ry)
1237 {
1238   if (node->parent) {
1239     nodeFromView(node->parent, x, y, rx, ry);
1240     *rx -= node->locx;
1241     *ry -= node->locy;
1242   }
1243   else {
1244     *rx = x - node->locx;
1245     *ry = y - node->locy;
1246   }
1247 }
1248
1249 bool nodeAttachNodeCheck(bNode *node, bNode *parent)
1250 {
1251   bNode *parent_recurse;
1252   for (parent_recurse = node; parent_recurse; parent_recurse = parent_recurse->parent) {
1253     if (parent_recurse == parent) {
1254       return true;
1255     }
1256   }
1257
1258   return false;
1259 }
1260
1261 void nodeAttachNode(bNode *node, bNode *parent)
1262 {
1263   float locx, locy;
1264
1265   BLI_assert(parent->type == NODE_FRAME);
1266   BLI_assert(nodeAttachNodeCheck(parent, node) == false);
1267
1268   nodeToView(node, 0.0f, 0.0f, &locx, &locy);
1269
1270   node->parent = parent;
1271   /* transform to parent space */
1272   nodeFromView(parent, locx, locy, &node->locx, &node->locy);
1273 }
1274
1275 void nodeDetachNode(struct bNode *node)
1276 {
1277   float locx, locy;
1278
1279   if (node->parent) {
1280
1281     BLI_assert(node->parent->type == NODE_FRAME);
1282
1283     /* transform to view space */
1284     nodeToView(node, 0.0f, 0.0f, &locx, &locy);
1285     node->locx = locx;
1286     node->locy = locy;
1287     node->parent = NULL;
1288   }
1289 }
1290
1291 void nodePositionRelative(bNode *from_node,
1292                           bNode *to_node,
1293                           bNodeSocket *from_sock,
1294                           bNodeSocket *to_sock)
1295 {
1296   float offset_x;
1297   int tot_sock_idx;
1298
1299   /* Socket to plug into. */
1300   if (SOCK_IN == to_sock->in_out) {
1301     offset_x = -(from_node->typeinfo->width + 50);
1302     tot_sock_idx = BLI_listbase_count(&to_node->outputs);
1303     tot_sock_idx += BLI_findindex(&to_node->inputs, to_sock);
1304   }
1305   else {
1306     offset_x = to_node->typeinfo->width + 50;
1307     tot_sock_idx = BLI_findindex(&to_node->outputs, to_sock);
1308   }
1309
1310   BLI_assert(tot_sock_idx != -1);
1311
1312   float offset_y = U.widget_unit * tot_sock_idx;
1313
1314   /* Output socket. */
1315   if (from_sock) {
1316     if (SOCK_IN == from_sock->in_out) {
1317       tot_sock_idx = BLI_listbase_count(&from_node->outputs);
1318       tot_sock_idx += BLI_findindex(&from_node->inputs, from_sock);
1319     }
1320     else {
1321       tot_sock_idx = BLI_findindex(&from_node->outputs, from_sock);
1322     }
1323   }
1324
1325   BLI_assert(tot_sock_idx != -1);
1326
1327   offset_y -= U.widget_unit * tot_sock_idx;
1328
1329   from_node->locx = to_node->locx + offset_x;
1330   from_node->locy = to_node->locy - offset_y;
1331 }
1332
1333 void nodePositionPropagate(bNode *node)
1334 {
1335   for (bNodeSocket *nsock = node->inputs.first; nsock; nsock = nsock->next) {
1336     if (nsock->link != NULL) {
1337       bNodeLink *link = nsock->link;
1338       nodePositionRelative(link->fromnode, link->tonode, link->fromsock, link->tosock);
1339       nodePositionPropagate(link->fromnode);
1340     }
1341   }
1342 }
1343
1344 void ntreeInitDefault(bNodeTree *ntree)
1345 {
1346   ntree_set_typeinfo(ntree, NULL);
1347 }
1348
1349 bNodeTree *ntreeAddTree(Main *bmain, const char *name, const char *idname)
1350 {
1351   bNodeTree *ntree;
1352
1353   /* trees are created as local trees for compositor, material or texture nodes,
1354    * node groups and other tree types are created as library data.
1355    */
1356   if (bmain) {
1357     ntree = BKE_libblock_alloc(bmain, ID_NT, name, 0);
1358   }
1359   else {
1360     ntree = MEM_callocN(sizeof(bNodeTree), "new node tree");
1361     *((short *)ntree->id.name) = ID_NT;
1362     BLI_strncpy(ntree->id.name + 2, name, sizeof(ntree->id.name));
1363   }
1364
1365   /* Types are fully initialized at this point,
1366    * if an undefined node is added later this will be reset.
1367    */
1368   ntree->init |= NTREE_TYPE_INIT;
1369
1370   BLI_strncpy(ntree->idname, idname, sizeof(ntree->idname));
1371   ntree_set_typeinfo(ntree, ntreeTypeFind(idname));
1372
1373   return ntree;
1374 }
1375
1376 /**
1377  * Only copy internal data of NodeTree ID from source
1378  * to already allocated/initialized destination.
1379  * You probably never want to use that directly,
1380  * use #BKE_id_copy or #BKE_id_copy_ex for typical needs.
1381  *
1382  * WARNING! This function will not handle ID user count!
1383  *
1384  * \param flag: Copying options (see BKE_library.h's LIB_ID_COPY_... flags for more).
1385  */
1386 void BKE_node_tree_copy_data(Main *UNUSED(bmain),
1387                              bNodeTree *ntree_dst,
1388                              const bNodeTree *ntree_src,
1389                              const int flag)
1390 {
1391   bNodeSocket *sock_dst, *sock_src;
1392   bNodeLink *link_dst;
1393
1394   /* We never handle usercount here for own data. */
1395   const int flag_subdata = flag | LIB_ID_CREATE_NO_USER_REFCOUNT;
1396
1397   /* in case a running nodetree is copied */
1398   ntree_dst->execdata = NULL;
1399
1400   ntree_dst->duplilock = NULL;
1401
1402   BLI_listbase_clear(&ntree_dst->nodes);
1403   BLI_listbase_clear(&ntree_dst->links);
1404
1405   for (bNode *node_src = ntree_src->nodes.first; node_src; node_src = node_src->next) {
1406     BKE_node_copy_ex(ntree_dst, node_src, flag_subdata);
1407   }
1408
1409   /* copy links */
1410   BLI_duplicatelist(&ntree_dst->links, &ntree_src->links);
1411   for (link_dst = ntree_dst->links.first; link_dst; link_dst = link_dst->next) {
1412     link_dst->fromnode = (link_dst->fromnode ? link_dst->fromnode->new_node : NULL);
1413     link_dst->fromsock = (link_dst->fromsock ? link_dst->fromsock->new_sock : NULL);
1414     link_dst->tonode = (link_dst->tonode ? link_dst->tonode->new_node : NULL);
1415     link_dst->tosock = (link_dst->tosock ? link_dst->tosock->new_sock : NULL);
1416     /* update the link socket's pointer */
1417     if (link_dst->tosock) {
1418       link_dst->tosock->link = link_dst;
1419     }
1420   }
1421
1422   /* copy interface sockets */
1423   BLI_duplicatelist(&ntree_dst->inputs, &ntree_src->inputs);
1424   for (sock_dst = ntree_dst->inputs.first, sock_src = ntree_src->inputs.first; sock_dst != NULL;
1425        sock_dst = sock_dst->next, sock_src = sock_src->next) {
1426     node_socket_copy(sock_dst, sock_src, flag_subdata);
1427   }
1428
1429   BLI_duplicatelist(&ntree_dst->outputs, &ntree_src->outputs);
1430   for (sock_dst = ntree_dst->outputs.first, sock_src = ntree_src->outputs.first; sock_dst != NULL;
1431        sock_dst = sock_dst->next, sock_src = sock_src->next) {
1432     node_socket_copy(sock_dst, sock_src, flag_subdata);
1433   }
1434
1435   /* copy preview hash */
1436   if (ntree_src->previews && (flag & LIB_ID_COPY_NO_PREVIEW) == 0) {
1437     bNodeInstanceHashIterator iter;
1438
1439     ntree_dst->previews = BKE_node_instance_hash_new("node previews");
1440
1441     NODE_INSTANCE_HASH_ITER (iter, ntree_src->previews) {
1442       bNodeInstanceKey key = BKE_node_instance_hash_iterator_get_key(&iter);
1443       bNodePreview *preview = BKE_node_instance_hash_iterator_get_value(&iter);
1444       BKE_node_instance_hash_insert(ntree_dst->previews, key, BKE_node_preview_copy(preview));
1445     }
1446   }
1447   else {
1448     ntree_dst->previews = NULL;
1449   }
1450
1451   /* update node->parent pointers */
1452   for (bNode *node_dst = ntree_dst->nodes.first, *node_src = ntree_src->nodes.first; node_dst;
1453        node_dst = node_dst->next, node_src = node_src->next) {
1454     if (node_dst->parent) {
1455       node_dst->parent = node_dst->parent->new_node;
1456     }
1457   }
1458
1459   /* node tree will generate its own interface type */
1460   ntree_dst->interface_type = NULL;
1461 }
1462
1463 bNodeTree *ntreeCopyTree_ex(const bNodeTree *ntree, Main *bmain, const bool do_id_user)
1464 {
1465   bNodeTree *ntree_copy;
1466   const int flag = do_id_user ? LIB_ID_CREATE_NO_USER_REFCOUNT | LIB_ID_CREATE_NO_MAIN : 0;
1467   BKE_id_copy_ex(bmain, (ID *)ntree, (ID **)&ntree_copy, flag);
1468   return ntree_copy;
1469 }
1470 bNodeTree *ntreeCopyTree(Main *bmain, const bNodeTree *ntree)
1471 {
1472   return ntreeCopyTree_ex(ntree, bmain, true);
1473 }
1474
1475 void ntreeUserIncrefID(bNodeTree *ntree)
1476 {
1477   bNode *node;
1478   for (node = ntree->nodes.first; node; node = node->next) {
1479     id_us_plus(node->id);
1480   }
1481 }
1482 void ntreeUserDecrefID(bNodeTree *ntree)
1483 {
1484   bNode *node;
1485   for (node = ntree->nodes.first; node; node = node->next) {
1486     id_us_min(node->id);
1487   }
1488 }
1489
1490 /* *************** Node Preview *********** */
1491
1492 /* XXX this should be removed eventually ...
1493  * Currently BKE functions are modeled closely on previous code,
1494  * using BKE_node_preview_init_tree to set up previews for a whole node tree in advance.
1495  * This should be left more to the individual node tree implementations.
1496  */
1497 int BKE_node_preview_used(bNode *node)
1498 {
1499   /* XXX check for closed nodes? */
1500   return (node->typeinfo->flag & NODE_PREVIEW) != 0;
1501 }
1502
1503 bNodePreview *BKE_node_preview_verify(
1504     bNodeInstanceHash *previews, bNodeInstanceKey key, int xsize, int ysize, bool create)
1505 {
1506   bNodePreview *preview;
1507
1508   preview = BKE_node_instance_hash_lookup(previews, key);
1509   if (!preview) {
1510     if (create) {
1511       preview = MEM_callocN(sizeof(bNodePreview), "node preview");
1512       BKE_node_instance_hash_insert(previews, key, preview);
1513     }
1514     else {
1515       return NULL;
1516     }
1517   }
1518
1519   /* node previews can get added with variable size this way */
1520   if (xsize == 0 || ysize == 0) {
1521     return preview;
1522   }
1523
1524   /* sanity checks & initialize */
1525   if (preview->rect) {
1526     if (preview->xsize != xsize || preview->ysize != ysize) {
1527       MEM_freeN(preview->rect);
1528       preview->rect = NULL;
1529     }
1530   }
1531
1532   if (preview->rect == NULL) {
1533     preview->rect = MEM_callocN(4 * xsize + xsize * ysize * sizeof(char) * 4, "node preview rect");
1534     preview->xsize = xsize;
1535     preview->ysize = ysize;
1536   }
1537   /* no clear, makes nicer previews */
1538
1539   return preview;
1540 }
1541
1542 bNodePreview *BKE_node_preview_copy(bNodePreview *preview)
1543 {
1544   bNodePreview *new_preview = MEM_dupallocN(preview);
1545   if (preview->rect) {
1546     new_preview->rect = MEM_dupallocN(preview->rect);
1547   }
1548   return new_preview;
1549 }
1550
1551 void BKE_node_preview_free(bNodePreview *preview)
1552 {
1553   if (preview->rect) {
1554     MEM_freeN(preview->rect);
1555   }
1556   MEM_freeN(preview);
1557 }
1558
1559 static void node_preview_init_tree_recursive(bNodeInstanceHash *previews,
1560                                              bNodeTree *ntree,
1561                                              bNodeInstanceKey parent_key,
1562                                              int xsize,
1563                                              int ysize,
1564                                              int create)
1565 {
1566   bNode *node;
1567   for (node = ntree->nodes.first; node; node = node->next) {
1568     bNodeInstanceKey key = BKE_node_instance_key(parent_key, ntree, node);
1569
1570     if (BKE_node_preview_used(node)) {
1571       node->preview_xsize = xsize;
1572       node->preview_ysize = ysize;
1573
1574       BKE_node_preview_verify(previews, key, xsize, ysize, create);
1575     }
1576
1577     if (node->type == NODE_GROUP && node->id) {
1578       node_preview_init_tree_recursive(previews, (bNodeTree *)node->id, key, xsize, ysize, create);
1579     }
1580   }
1581 }
1582
1583 void BKE_node_preview_init_tree(bNodeTree *ntree, int xsize, int ysize, int create_previews)
1584 {
1585   if (!ntree) {
1586     return;
1587   }
1588
1589   if (!ntree->previews) {
1590     ntree->previews = BKE_node_instance_hash_new("node previews");
1591   }
1592
1593   node_preview_init_tree_recursive(
1594       ntree->previews, ntree, NODE_INSTANCE_KEY_BASE, xsize, ysize, create_previews);
1595 }
1596
1597 static void node_preview_tag_used_recursive(bNodeInstanceHash *previews,
1598                                             bNodeTree *ntree,
1599                                             bNodeInstanceKey parent_key)
1600 {
1601   bNode *node;
1602   for (node = ntree->nodes.first; node; node = node->next) {
1603     bNodeInstanceKey key = BKE_node_instance_key(parent_key, ntree, node);
1604
1605     if (BKE_node_preview_used(node)) {
1606       BKE_node_instance_hash_tag_key(previews, key);
1607     }
1608
1609     if (node->type == NODE_GROUP && node->id) {
1610       node_preview_tag_used_recursive(previews, (bNodeTree *)node->id, key);
1611     }
1612   }
1613 }
1614
1615 void BKE_node_preview_remove_unused(bNodeTree *ntree)
1616 {
1617   if (!ntree || !ntree->previews) {
1618     return;
1619   }
1620
1621   /* use the instance hash functions for tagging and removing unused previews */
1622   BKE_node_instance_hash_clear_tags(ntree->previews);
1623   node_preview_tag_used_recursive(ntree->previews, ntree, NODE_INSTANCE_KEY_BASE);
1624
1625   BKE_node_instance_hash_remove_untagged(ntree->previews,
1626                                          (bNodeInstanceValueFP)BKE_node_preview_free);
1627 }
1628
1629 void BKE_node_preview_free_tree(bNodeTree *ntree)
1630 {
1631   if (!ntree) {
1632     return;
1633   }
1634
1635   if (ntree->previews) {
1636     BKE_node_instance_hash_free(ntree->previews, (bNodeInstanceValueFP)BKE_node_preview_free);
1637     ntree->previews = NULL;
1638   }
1639 }
1640
1641 void BKE_node_preview_clear(bNodePreview *preview)
1642 {
1643   if (preview && preview->rect) {
1644     memset(preview->rect, 0, MEM_allocN_len(preview->rect));
1645   }
1646 }
1647
1648 void BKE_node_preview_clear_tree(bNodeTree *ntree)
1649 {
1650   bNodeInstanceHashIterator iter;
1651
1652   if (!ntree || !ntree->previews) {
1653     return;
1654   }
1655
1656   NODE_INSTANCE_HASH_ITER (iter, ntree->previews) {
1657     bNodePreview *preview = BKE_node_instance_hash_iterator_get_value(&iter);
1658     BKE_node_preview_clear(preview);
1659   }
1660 }
1661
1662 static void node_preview_sync(bNodePreview *to, bNodePreview *from)
1663 {
1664   /* sizes should have been initialized by BKE_node_preview_init_tree */
1665   BLI_assert(to->xsize == from->xsize && to->ysize == from->ysize);
1666
1667   /* copy over contents of previews */
1668   if (to->rect && from->rect) {
1669     int xsize = to->xsize;
1670     int ysize = to->ysize;
1671     memcpy(to->rect, from->rect, xsize * ysize * sizeof(char) * 4);
1672   }
1673 }
1674
1675 void BKE_node_preview_sync_tree(bNodeTree *to_ntree, bNodeTree *from_ntree)
1676 {
1677   bNodeInstanceHash *from_previews = from_ntree->previews;
1678   bNodeInstanceHash *to_previews = to_ntree->previews;
1679   bNodeInstanceHashIterator iter;
1680
1681   if (!from_previews || !to_previews) {
1682     return;
1683   }
1684
1685   NODE_INSTANCE_HASH_ITER (iter, from_previews) {
1686     bNodeInstanceKey key = BKE_node_instance_hash_iterator_get_key(&iter);
1687     bNodePreview *from = BKE_node_instance_hash_iterator_get_value(&iter);
1688     bNodePreview *to = BKE_node_instance_hash_lookup(to_previews, key);
1689
1690     if (from && to) {
1691       node_preview_sync(to, from);
1692     }
1693   }
1694 }
1695
1696 void BKE_node_preview_merge_tree(bNodeTree *to_ntree, bNodeTree *from_ntree, bool remove_old)
1697 {
1698   if (remove_old || !to_ntree->previews) {
1699     /* free old previews */
1700     if (to_ntree->previews) {
1701       BKE_node_instance_hash_free(to_ntree->previews, (bNodeInstanceValueFP)BKE_node_preview_free);
1702     }
1703
1704     /* transfer previews */
1705     to_ntree->previews = from_ntree->previews;
1706     from_ntree->previews = NULL;
1707
1708     /* clean up, in case any to_ntree nodes have been removed */
1709     BKE_node_preview_remove_unused(to_ntree);
1710   }
1711   else {
1712     bNodeInstanceHashIterator iter;
1713
1714     if (from_ntree->previews) {
1715       NODE_INSTANCE_HASH_ITER (iter, from_ntree->previews) {
1716         bNodeInstanceKey key = BKE_node_instance_hash_iterator_get_key(&iter);
1717         bNodePreview *preview = BKE_node_instance_hash_iterator_get_value(&iter);
1718
1719         /* replace existing previews */
1720         BKE_node_instance_hash_remove(
1721             to_ntree->previews, key, (bNodeInstanceValueFP)BKE_node_preview_free);
1722         BKE_node_instance_hash_insert(to_ntree->previews, key, preview);
1723       }
1724
1725       /* Note: NULL free function here,
1726        * because pointers have already been moved over to to_ntree->previews! */
1727       BKE_node_instance_hash_free(from_ntree->previews, NULL);
1728       from_ntree->previews = NULL;
1729     }
1730   }
1731 }
1732
1733 /* hack warning! this function is only used for shader previews, and
1734  * since it gets called multiple times per pixel for Ztransp we only
1735  * add the color once. Preview gets cleared before it starts render though */
1736 void BKE_node_preview_set_pixel(
1737     bNodePreview *preview, const float col[4], int x, int y, bool do_manage)
1738 {
1739   if (preview) {
1740     if (x >= 0 && y >= 0) {
1741       if (x < preview->xsize && y < preview->ysize) {
1742         unsigned char *tar = preview->rect + 4 * ((preview->xsize * y) + x);
1743
1744         if (do_manage) {
1745           linearrgb_to_srgb_uchar4(tar, col);
1746         }
1747         else {
1748           rgba_float_to_uchar(tar, col);
1749         }
1750       }
1751       //else printf("prv out bound x y %d %d\n", x, y);
1752     }
1753     //else printf("prv out bound x y %d %d\n", x, y);
1754   }
1755 }
1756
1757 /* ************** Free stuff ********** */
1758
1759 /* goes over entire tree */
1760 void nodeUnlinkNode(bNodeTree *ntree, bNode *node)
1761 {
1762   bNodeLink *link, *next;
1763   bNodeSocket *sock;
1764   ListBase *lb;
1765
1766   for (link = ntree->links.first; link; link = next) {
1767     next = link->next;
1768
1769     if (link->fromnode == node) {
1770       lb = &node->outputs;
1771       if (link->tonode) {
1772         link->tonode->update |= NODE_UPDATE;
1773       }
1774     }
1775     else if (link->tonode == node) {
1776       lb = &node->inputs;
1777     }
1778     else {
1779       lb = NULL;
1780     }
1781
1782     if (lb) {
1783       for (sock = lb->first; sock; sock = sock->next) {
1784         if (link->fromsock == sock || link->tosock == sock) {
1785           break;
1786         }
1787       }
1788       if (sock) {
1789         nodeRemLink(ntree, link);
1790       }
1791     }
1792   }
1793 }
1794
1795 static void node_unlink_attached(bNodeTree *ntree, bNode *parent)
1796 {
1797   bNode *node;
1798   for (node = ntree->nodes.first; node; node = node->next) {
1799     if (node->parent == parent) {
1800       nodeDetachNode(node);
1801     }
1802   }
1803 }
1804
1805 /* Free the node itself. ID user refcounting is up the caller,
1806  * that does not happen here. */
1807 static void node_free_node(bNodeTree *ntree, bNode *node)
1808 {
1809   bNodeSocket *sock, *nextsock;
1810
1811   /* since it is called while free database, node->id is undefined */
1812
1813   /* can be called for nodes outside a node tree (e.g. clipboard) */
1814   if (ntree) {
1815     /* remove all references to this node */
1816     nodeUnlinkNode(ntree, node);
1817     node_unlink_attached(ntree, node);
1818
1819     BLI_remlink(&ntree->nodes, node);
1820
1821     if (ntree->typeinfo->free_node_cache) {
1822       ntree->typeinfo->free_node_cache(ntree, node);
1823     }
1824
1825     /* texture node has bad habit of keeping exec data around */
1826     if (ntree->type == NTREE_TEXTURE && ntree->execdata) {
1827       ntreeTexEndExecTree(ntree->execdata);
1828       ntree->execdata = NULL;
1829     }
1830   }
1831
1832   if (node->typeinfo->freefunc) {
1833     node->typeinfo->freefunc(node);
1834   }
1835
1836   for (sock = node->inputs.first; sock; sock = nextsock) {
1837     nextsock = sock->next;
1838     /* Remember, no ID user refcount management here! */
1839     node_socket_free(ntree, sock, node, false);
1840     MEM_freeN(sock);
1841   }
1842   for (sock = node->outputs.first; sock; sock = nextsock) {
1843     nextsock = sock->next;
1844     /* Remember, no ID user refcount management here! */
1845     node_socket_free(ntree, sock, node, false);
1846     MEM_freeN(sock);
1847   }
1848
1849   BLI_freelistN(&node->internal_links);
1850
1851   if (node->prop) {
1852     /* Remember, no ID user refcount management here! */
1853     IDP_FreeProperty_ex(node->prop, false);
1854     MEM_freeN(node->prop);
1855   }
1856
1857   MEM_freeN(node);
1858
1859   if (ntree) {
1860     ntree->update |= NTREE_UPDATE_NODES;
1861   }
1862 }
1863
1864 void ntreeFreeLocalNode(bNodeTree *ntree, bNode *node)
1865 {
1866   /* For removing nodes while editing localized node trees. */
1867   BLI_assert((ntree->id.tag & LIB_TAG_LOCALIZED) != 0);
1868   node_free_node(ntree, node);
1869 }
1870
1871 void nodeRemoveNode(Main *bmain, bNodeTree *ntree, bNode *node, bool do_id_user)
1872 {
1873   /* This function is not for localized node trees, we do not want
1874    * do to ID user refcounting and removal of animdation data then. */
1875   BLI_assert((ntree->id.tag & LIB_TAG_LOCALIZED) == 0);
1876
1877   if (do_id_user) {
1878     /* Free callback for NodeCustomGroup. */
1879     if (node->typeinfo->freefunc_api) {
1880       PointerRNA ptr;
1881       RNA_pointer_create((ID *)ntree, &RNA_Node, node, &ptr);
1882
1883       node->typeinfo->freefunc_api(&ptr);
1884     }
1885
1886     /* Do user counting. */
1887     if (node->id) {
1888       id_us_min(node->id);
1889     }
1890   }
1891
1892   /* Remove animation data. */
1893   char propname_esc[MAX_IDPROP_NAME * 2];
1894   char prefix[MAX_IDPROP_NAME * 2];
1895
1896   BLI_strescape(propname_esc, node->name, sizeof(propname_esc));
1897   BLI_snprintf(prefix, sizeof(prefix), "nodes[\"%s\"]", propname_esc);
1898
1899   if (BKE_animdata_fix_paths_remove((ID *)ntree, prefix)) {
1900     if (bmain != NULL) {
1901       DEG_relations_tag_update(bmain);
1902     }
1903   }
1904
1905   /* Free node itself. */
1906   node_free_node(ntree, node);
1907 }
1908
1909 static void node_socket_interface_free(bNodeTree *UNUSED(ntree), bNodeSocket *sock)
1910 {
1911   if (sock->prop) {
1912     IDP_FreeProperty(sock->prop);
1913     MEM_freeN(sock->prop);
1914   }
1915
1916   if (sock->default_value) {
1917     MEM_freeN(sock->default_value);
1918   }
1919 }
1920
1921 static void free_localized_node_groups(bNodeTree *ntree)
1922 {
1923   bNode *node;
1924
1925   /* Only localized node trees store a copy for each node group tree.
1926    * Each node group tree in a localized node tree can be freed,
1927    * since it is a localized copy itself (no risk of accessing free'd
1928    * data in main, see [#37939]).
1929    */
1930   if (!(ntree->id.tag & LIB_TAG_LOCALIZED)) {
1931     return;
1932   }
1933
1934   for (node = ntree->nodes.first; node; node = node->next) {
1935     if ((ELEM(node->type, NODE_GROUP, NODE_CUSTOM_GROUP)) && node->id) {
1936       bNodeTree *ngroup = (bNodeTree *)node->id;
1937       ntreeFreeTree(ngroup);
1938       MEM_freeN(ngroup);
1939     }
1940   }
1941 }
1942
1943 /* Free (or release) any data used by this nodetree. Does not free the
1944  * nodetree itself and does no ID user counting. */
1945 void ntreeFreeTree(bNodeTree *ntree)
1946 {
1947   bNode *node, *next;
1948   bNodeSocket *sock, *nextsock;
1949
1950   BKE_animdata_free((ID *)ntree, false);
1951
1952   /* XXX hack! node trees should not store execution graphs at all.
1953    * This should be removed when old tree types no longer require it.
1954    * Currently the execution data for texture nodes remains in the tree
1955    * after execution, until the node tree is updated or freed.
1956    */
1957   if (ntree->execdata) {
1958     switch (ntree->type) {
1959       case NTREE_SHADER:
1960         ntreeShaderEndExecTree(ntree->execdata);
1961         break;
1962       case NTREE_TEXTURE:
1963         ntreeTexEndExecTree(ntree->execdata);
1964         ntree->execdata = NULL;
1965         break;
1966     }
1967   }
1968
1969   /* XXX not nice, but needed to free localized node groups properly */
1970   free_localized_node_groups(ntree);
1971
1972   /* unregister associated RNA types */
1973   ntreeInterfaceTypeFree(ntree);
1974
1975   BLI_freelistN(&ntree->links); /* do first, then unlink_node goes fast */
1976
1977   for (node = ntree->nodes.first; node; node = next) {
1978     next = node->next;
1979     node_free_node(ntree, node);
1980   }
1981
1982   /* free interface sockets */
1983   for (sock = ntree->inputs.first; sock; sock = nextsock) {
1984     nextsock = sock->next;
1985     node_socket_interface_free(ntree, sock);
1986     MEM_freeN(sock);
1987   }
1988   for (sock = ntree->outputs.first; sock; sock = nextsock) {
1989     nextsock = sock->next;
1990     node_socket_interface_free(ntree, sock);
1991     MEM_freeN(sock);
1992   }
1993
1994   /* free preview hash */
1995   if (ntree->previews) {
1996     BKE_node_instance_hash_free(ntree->previews, (bNodeInstanceValueFP)BKE_node_preview_free);
1997   }
1998
1999   if (ntree->duplilock) {
2000     BLI_mutex_free(ntree->duplilock);
2001   }
2002
2003   if (ntree->id.tag & LIB_TAG_LOCALIZED) {
2004     BKE_libblock_free_data(&ntree->id, true);
2005   }
2006 }
2007
2008 void ntreeFreeNestedTree(bNodeTree *ntree)
2009 {
2010   ntreeFreeTree(ntree);
2011   BKE_libblock_free_data(&ntree->id, true);
2012 }
2013
2014 void ntreeFreeLocalTree(bNodeTree *ntree)
2015 {
2016   if (ntree->id.tag & LIB_TAG_LOCALIZED) {
2017     ntreeFreeTree(ntree);
2018   }
2019   else {
2020     ntreeFreeTree(ntree);
2021     BKE_libblock_free_data(&ntree->id, true);
2022   }
2023 }
2024
2025 void ntreeFreeCache(bNodeTree *ntree)
2026 {
2027   if (ntree == NULL) {
2028     return;
2029   }
2030
2031   if (ntree->typeinfo->free_cache) {
2032     ntree->typeinfo->free_cache(ntree);
2033   }
2034 }
2035
2036 void ntreeSetOutput(bNodeTree *ntree)
2037 {
2038   bNode *node;
2039
2040   /* find the active outputs, might become tree type dependent handler */
2041   for (node = ntree->nodes.first; node; node = node->next) {
2042     if (node->typeinfo->nclass == NODE_CLASS_OUTPUT) {
2043       bNode *tnode;
2044       int output = 0;
2045
2046       /* we need a check for which output node should be tagged like this, below an exception */
2047       if (node->type == CMP_NODE_OUTPUT_FILE) {
2048         continue;
2049       }
2050
2051       /* there is more types having output class, each one is checked */
2052       for (tnode = ntree->nodes.first; tnode; tnode = tnode->next) {
2053         if (tnode->typeinfo->nclass == NODE_CLASS_OUTPUT) {
2054
2055           if (ntree->type == NTREE_COMPOSIT) {
2056
2057             /* same type, exception for viewer */
2058             if (tnode->type == node->type ||
2059                 (ELEM(tnode->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER) &&
2060                  ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER))) {
2061               if (tnode->flag & NODE_DO_OUTPUT) {
2062                 output++;
2063                 if (output > 1) {
2064                   tnode->flag &= ~NODE_DO_OUTPUT;
2065                 }
2066               }
2067             }
2068           }
2069           else {
2070             /* same type */
2071             if (tnode->type == node->type) {
2072               if (tnode->flag & NODE_DO_OUTPUT) {
2073                 output++;
2074                 if (output > 1) {
2075                   tnode->flag &= ~NODE_DO_OUTPUT;
2076                 }
2077               }
2078             }
2079           }
2080         }
2081       }
2082       if (output == 0) {
2083         node->flag |= NODE_DO_OUTPUT;
2084       }
2085     }
2086
2087     /* group node outputs use this flag too */
2088     if (node->type == NODE_GROUP_OUTPUT) {
2089       bNode *tnode;
2090       int output = 0;
2091
2092       for (tnode = ntree->nodes.first; tnode; tnode = tnode->next) {
2093         if (tnode->type == NODE_GROUP_OUTPUT) {
2094           if (tnode->flag & NODE_DO_OUTPUT) {
2095             output++;
2096             if (output > 1) {
2097               tnode->flag &= ~NODE_DO_OUTPUT;
2098             }
2099           }
2100         }
2101       }
2102       if (output == 0) {
2103         node->flag |= NODE_DO_OUTPUT;
2104       }
2105     }
2106   }
2107
2108   /* here we could recursively set which nodes have to be done,
2109    * might be different for editor or for "real" use... */
2110 }
2111
2112 bNodeTree *ntreeFromID(const ID *id)
2113 {
2114   switch (GS(id->name)) {
2115     case ID_MA:
2116       return ((const Material *)id)->nodetree;
2117     case ID_LA:
2118       return ((const Light *)id)->nodetree;
2119     case ID_WO:
2120       return ((const World *)id)->nodetree;
2121     case ID_TE:
2122       return ((const Tex *)id)->nodetree;
2123     case ID_SCE:
2124       return ((const Scene *)id)->nodetree;
2125     case ID_LS:
2126       return ((const FreestyleLineStyle *)id)->nodetree;
2127     default:
2128       return NULL;
2129   }
2130 }
2131
2132 void ntreeMakeLocal(Main *bmain, bNodeTree *ntree, bool id_in_mainlist, const bool lib_local)
2133 {
2134   BKE_id_make_local_generic(bmain, &ntree->id, id_in_mainlist, lib_local);
2135 }
2136
2137 int ntreeNodeExists(bNodeTree *ntree, bNode *testnode)
2138 {
2139   bNode *node = ntree->nodes.first;
2140   for (; node; node = node->next) {
2141     if (node == testnode) {
2142       return 1;
2143     }
2144   }
2145   return 0;
2146 }
2147
2148 int ntreeOutputExists(bNode *node, bNodeSocket *testsock)
2149 {
2150   bNodeSocket *sock = node->outputs.first;
2151   for (; sock; sock = sock->next) {
2152     if (sock == testsock) {
2153       return 1;
2154     }
2155   }
2156   return 0;
2157 }
2158
2159 void ntreeNodeFlagSet(const bNodeTree *ntree, const int flag, const bool enable)
2160 {
2161   bNode *node = ntree->nodes.first;
2162
2163   for (; node; node = node->next) {
2164     if (enable) {
2165       node->flag |= flag;
2166     }
2167     else {
2168       node->flag &= ~flag;
2169     }
2170   }
2171 }
2172
2173 /* returns localized tree for execution in threads */
2174 bNodeTree *ntreeLocalize(bNodeTree *ntree)
2175 {
2176   if (ntree) {
2177     bNodeTree *ltree;
2178     bNode *node;
2179
2180     BLI_spin_lock(&spin);
2181     if (!ntree->duplilock) {
2182       ntree->duplilock = BLI_mutex_alloc();
2183     }
2184     BLI_spin_unlock(&spin);
2185
2186     BLI_mutex_lock(ntree->duplilock);
2187
2188     /* Make full copy outside of Main database.
2189      * Note: previews are not copied here.
2190      */
2191     BKE_id_copy_ex(
2192         NULL, &ntree->id, (ID **)&ltree, (LIB_ID_COPY_LOCALIZE | LIB_ID_COPY_NO_ANIMDATA));
2193
2194     ltree->id.tag |= LIB_TAG_LOCALIZED;
2195
2196     for (node = ltree->nodes.first; node; node = node->next) {
2197       if ((ELEM(node->type, NODE_GROUP, NODE_CUSTOM_GROUP)) && node->id) {
2198         node->id = (ID *)ntreeLocalize((bNodeTree *)node->id);
2199       }
2200     }
2201
2202     /* ensures only a single output node is enabled */
2203     ntreeSetOutput(ntree);
2204
2205     for (node = ntree->nodes.first; node; node = node->next) {
2206       /* store new_node pointer to original */
2207       node->new_node->original = node;
2208     }
2209
2210     if (ntree->typeinfo->localize) {
2211       ntree->typeinfo->localize(ltree, ntree);
2212     }
2213
2214     BLI_mutex_unlock(ntree->duplilock);
2215
2216     return ltree;
2217   }
2218   else {
2219     return NULL;
2220   }
2221 }
2222
2223 /* sync local composite with real tree */
2224 /* local tree is supposed to be running, be careful moving previews! */
2225 /* is called by jobs manager, outside threads, so it doesn't happen during draw */
2226 void ntreeLocalSync(bNodeTree *localtree, bNodeTree *ntree)
2227 {
2228   if (localtree && ntree) {
2229     if (ntree->typeinfo->local_sync) {
2230       ntree->typeinfo->local_sync(localtree, ntree);
2231     }
2232   }
2233 }
2234
2235 /* merge local tree results back, and free local tree */
2236 /* we have to assume the editor already changed completely */
2237 void ntreeLocalMerge(Main *bmain, bNodeTree *localtree, bNodeTree *ntree)
2238 {
2239   if (ntree && localtree) {
2240     if (ntree->typeinfo->local_merge) {
2241       ntree->typeinfo->local_merge(bmain, localtree, ntree);
2242     }
2243
2244     ntreeFreeTree(localtree);
2245     MEM_freeN(localtree);
2246   }
2247 }
2248
2249 /* ************ NODE TREE INTERFACE *************** */
2250
2251 static bNodeSocket *make_socket_interface(bNodeTree *ntree,
2252                                           int in_out,
2253                                           const char *idname,
2254                                           const char *name)
2255 {
2256   bNodeSocketType *stype = nodeSocketTypeFind(idname);
2257   bNodeSocket *sock;
2258   int own_index = ntree->cur_index++;
2259
2260   if (stype == NULL) {
2261     return NULL;
2262   }
2263
2264   sock = MEM_callocN(sizeof(bNodeSocket), "socket template");
2265   BLI_strncpy(sock->idname, stype->idname, sizeof(sock->idname));
2266   node_socket_set_typeinfo(ntree, sock, stype);
2267   sock->in_out = in_out;
2268   sock->type = SOCK_CUSTOM; /* int type undefined by default */
2269
2270   /* assign new unique index */
2271   own_index = ntree->cur_index++;
2272   /* use the own_index as socket identifier */
2273   if (in_out == SOCK_IN) {
2274     BLI_snprintf(sock->identifier, MAX_NAME, "Input_%d", own_index);
2275   }
2276   else {
2277     BLI_snprintf(sock->identifier, MAX_NAME, "Output_%d", own_index);
2278   }
2279
2280   sock->limit = (in_out == SOCK_IN ? 1 : 0xFFF);
2281
2282   BLI_strncpy(sock->name, name, NODE_MAXSTR);
2283   sock->storage = NULL;
2284   sock->flag |= SOCK_COLLAPSED;
2285
2286   return sock;
2287 }
2288
2289 bNodeSocket *ntreeFindSocketInterface(bNodeTree *ntree, int in_out, const char *identifier)
2290 {
2291   bNodeSocket *iosock = (in_out == SOCK_IN ? ntree->inputs.first : ntree->outputs.first);
2292   for (; iosock; iosock = iosock->next) {
2293     if (STREQ(iosock->identifier, identifier)) {
2294       return iosock;
2295     }
2296   }
2297   return NULL;
2298 }
2299
2300 bNodeSocket *ntreeAddSocketInterface(bNodeTree *ntree,
2301                                      int in_out,
2302                                      const char *idname,
2303                                      const char *name)
2304 {
2305   bNodeSocket *iosock;
2306
2307   iosock = make_socket_interface(ntree, in_out, idname, name);
2308   if (in_out == SOCK_IN) {
2309     BLI_addtail(&ntree->inputs, iosock);
2310     ntree->update |= NTREE_UPDATE_GROUP_IN;
2311   }
2312   else if (in_out == SOCK_OUT) {
2313     BLI_addtail(&ntree->outputs, iosock);
2314     ntree->update |= NTREE_UPDATE_GROUP_OUT;
2315   }
2316
2317   return iosock;
2318 }
2319
2320 bNodeSocket *ntreeInsertSocketInterface(
2321     bNodeTree *ntree, int in_out, const char *idname, bNodeSocket *next_sock, const char *name)
2322 {
2323   bNodeSocket *iosock;
2324
2325   iosock = make_socket_interface(ntree, in_out, idname, name);
2326   if (in_out == SOCK_IN) {
2327     BLI_insertlinkbefore(&ntree->inputs, next_sock, iosock);
2328     ntree->update |= NTREE_UPDATE_GROUP_IN;
2329   }
2330   else if (in_out == SOCK_OUT) {
2331     BLI_insertlinkbefore(&ntree->outputs, next_sock, iosock);
2332     ntree->update |= NTREE_UPDATE_GROUP_OUT;
2333   }
2334
2335   return iosock;
2336 }
2337
2338 struct bNodeSocket *ntreeAddSocketInterfaceFromSocket(bNodeTree *ntree,
2339                                                       bNode *from_node,
2340                                                       bNodeSocket *from_sock)
2341 {
2342   bNodeSocket *iosock = ntreeAddSocketInterface(
2343       ntree, from_sock->in_out, from_sock->idname, from_sock->name);
2344   if (iosock) {
2345     if (iosock->typeinfo->interface_from_socket) {
2346       iosock->typeinfo->interface_from_socket(ntree, iosock, from_node, from_sock);
2347     }
2348   }
2349   return iosock;
2350 }
2351
2352 struct bNodeSocket *ntreeInsertSocketInterfaceFromSocket(bNodeTree *ntree,
2353                                                          bNodeSocket *next_sock,
2354                                                          bNode *from_node,
2355                                                          bNodeSocket *from_sock)
2356 {
2357   bNodeSocket *iosock = ntreeInsertSocketInterface(
2358       ntree, from_sock->in_out, from_sock->idname, next_sock, from_sock->name);
2359   if (iosock) {
2360     if (iosock->typeinfo->interface_from_socket) {
2361       iosock->typeinfo->interface_from_socket(ntree, iosock, from_node, from_sock);
2362     }
2363   }
2364   return iosock;
2365 }
2366
2367 void ntreeRemoveSocketInterface(bNodeTree *ntree, bNodeSocket *sock)
2368 {
2369   /* this is fast, this way we don't need an in_out argument */
2370   BLI_remlink(&ntree->inputs, sock);
2371   BLI_remlink(&ntree->outputs, sock);
2372
2373   node_socket_interface_free(ntree, sock);
2374   MEM_freeN(sock);
2375
2376   ntree->update |= NTREE_UPDATE_GROUP;
2377 }
2378
2379 /* generates a valid RNA identifier from the node tree name */
2380 static void ntree_interface_identifier_base(bNodeTree *ntree, char *base)
2381 {
2382   /* generate a valid RNA identifier */
2383   sprintf(base, "NodeTreeInterface_%s", ntree->id.name + 2);
2384   RNA_identifier_sanitize(base, false);
2385 }
2386
2387 /* check if the identifier is already in use */
2388 static bool ntree_interface_unique_identifier_check(void *UNUSED(data), const char *identifier)
2389 {
2390   return (RNA_struct_find(identifier) != NULL);
2391 }
2392
2393 /* generates the actual unique identifier and ui name and description */
2394 static void ntree_interface_identifier(bNodeTree *ntree,
2395                                        const char *base,
2396                                        char *identifier,
2397                                        int maxlen,
2398                                        char *name,
2399                                        char *description)
2400 {
2401   /* There is a possibility that different node tree names get mapped to the same identifier
2402    * after sanitization (e.g. "SomeGroup_A", "SomeGroup.A" both get sanitized to "SomeGroup_A").
2403    * On top of the sanitized id string add a number suffix if necessary to avoid duplicates.
2404    */
2405   identifier[0] = '\0';
2406   BLI_uniquename_cb(ntree_interface_unique_identifier_check, NULL, base, '_', identifier, maxlen);
2407
2408   sprintf(name, "Node Tree %s Interface", ntree->id.name + 2);
2409   sprintf(description, "Interface properties of node group %s", ntree->id.name + 2);
2410 }
2411
2412 static void ntree_interface_type_create(bNodeTree *ntree)
2413 {
2414   StructRNA *srna;
2415   bNodeSocket *sock;
2416   /* strings are generated from base string + ID name, sizes are sufficient */
2417   char base[MAX_ID_NAME + 64], identifier[MAX_ID_NAME + 64], name[MAX_ID_NAME + 64],
2418       description[MAX_ID_NAME + 64];
2419
2420   /* generate a valid RNA identifier */
2421   ntree_interface_identifier_base(ntree, base);
2422   ntree_interface_identifier(ntree, base, identifier, sizeof(identifier), name, description);
2423
2424   /* register a subtype of PropertyGroup */
2425   srna = RNA_def_struct_ptr(&BLENDER_RNA, identifier, &RNA_PropertyGroup);
2426   RNA_def_struct_ui_text(srna, name, description);
2427   RNA_def_struct_duplicate_pointers(&BLENDER_RNA, srna);
2428
2429   /* associate the RNA type with the node tree */
2430   ntree->interface_type = srna;
2431   RNA_struct_blender_type_set(srna, ntree);
2432
2433   /* add socket properties */
2434   for (sock = ntree->inputs.first; sock; sock = sock->next) {
2435     bNodeSocketType *stype = sock->typeinfo;
2436     if (stype && stype->interface_register_properties) {
2437       stype->interface_register_properties(ntree, sock, srna);
2438     }
2439   }
2440   for (sock = ntree->outputs.first; sock; sock = sock->next) {
2441     bNodeSocketType *stype = sock->typeinfo;
2442     if (stype && stype->interface_register_properties) {
2443       stype->interface_register_properties(ntree, sock, srna);
2444     }
2445   }
2446 }
2447
2448 StructRNA *ntreeInterfaceTypeGet(bNodeTree *ntree, int create)
2449 {
2450   if (ntree->interface_type) {
2451     /* strings are generated from base string + ID name, sizes are sufficient */
2452     char base[MAX_ID_NAME + 64], identifier[MAX_ID_NAME + 64], name[MAX_ID_NAME + 64],
2453         description[MAX_ID_NAME + 64];
2454
2455     /* A bit of a hack: when changing the ID name, update the RNA type identifier too,
2456      * so that the names match. This is not strictly necessary to keep it working,
2457      * but better for identifying associated NodeTree blocks and RNA types.
2458      */
2459     StructRNA *srna = ntree->interface_type;
2460
2461     ntree_interface_identifier_base(ntree, base);
2462
2463     /* RNA identifier may have a number suffix, but should start with the idbase string */
2464     if (!STREQLEN(RNA_struct_identifier(srna), base, sizeof(base))) {
2465       /* generate new unique RNA identifier from the ID name */
2466       ntree_interface_identifier(ntree, base, identifier, sizeof(identifier), name, description);
2467
2468       /* rename the RNA type */
2469       RNA_def_struct_free_pointers(&BLENDER_RNA, srna);
2470       RNA_def_struct_identifier(&BLENDER_RNA, srna, identifier);
2471       RNA_def_struct_ui_text(srna, name, description);
2472       RNA_def_struct_duplicate_pointers(&BLENDER_RNA, srna);
2473     }
2474   }
2475   else if (create) {
2476     ntree_interface_type_create(ntree);
2477   }
2478
2479   return ntree->interface_type;
2480 }
2481
2482 void ntreeInterfaceTypeFree(bNodeTree *ntree)
2483 {
2484   if (ntree->interface_type) {
2485     RNA_struct_free(&BLENDER_RNA, ntree->interface_type);
2486     ntree->interface_type = NULL;
2487   }
2488 }
2489
2490 void ntreeInterfaceTypeUpdate(bNodeTree *ntree)
2491 {
2492   /* XXX it would be sufficient to just recreate all properties
2493    * instead of re-registering the whole struct type,
2494    * but there is currently no good way to do this in the RNA functions.
2495    * Overhead should be negligible.
2496    */
2497   ntreeInterfaceTypeFree(ntree);
2498   ntree_interface_type_create(ntree);
2499 }
2500
2501 /* ************ find stuff *************** */
2502
2503 bNode *ntreeFindType(const bNodeTree *ntree, int type)
2504 {
2505   if (ntree) {
2506     for (bNode *node = ntree->nodes.first; node; node = node->next) {
2507       if (node->type == type) {
2508         return node;
2509       }
2510     }
2511   }
2512   return NULL;
2513 }
2514
2515 bool ntreeHasType(const bNodeTree *ntree, int type)
2516 {
2517   return ntreeFindType(ntree, type) != NULL;
2518 }
2519
2520 bool ntreeHasTree(const bNodeTree *ntree, const bNodeTree *lookup)
2521 {
2522   bNode *node;
2523
2524   if (ntree == lookup) {
2525     return true;
2526   }
2527
2528   for (node = ntree->nodes.first; node; node = node->next) {
2529     if (ELEM(node->type, NODE_GROUP, NODE_CUSTOM_GROUP) && node->id) {
2530       if (ntreeHasTree((bNodeTree *)node->id, lookup)) {
2531         return true;
2532       }
2533     }
2534   }
2535
2536   return false;
2537 }
2538
2539 bNodeLink *nodeFindLink(bNodeTree *ntree, bNodeSocket *from, bNodeSocket *to)
2540 {
2541   bNodeLink *link;
2542
2543   for (link = ntree->links.first; link; link = link->next) {
2544     if (link->fromsock == from && link->tosock == to) {
2545       return link;
2546     }
2547     if (link->fromsock == to && link->tosock == from) { /* hrms? */
2548       return link;
2549     }
2550   }
2551   return NULL;
2552 }
2553
2554 int nodeCountSocketLinks(bNodeTree *ntree, bNodeSocket *sock)
2555 {
2556   bNodeLink *link;
2557   int tot = 0;
2558
2559   for (link = ntree->links.first; link; link = link->next) {
2560     if (link->fromsock == sock || link->tosock == sock) {
2561       tot++;
2562     }
2563   }
2564   return tot;
2565 }
2566
2567 bNode *nodeGetActive(bNodeTree *ntree)
2568 {
2569   bNode *node;
2570
2571   if (ntree == NULL) {
2572     return NULL;
2573   }
2574
2575   for (node = ntree->nodes.first; node; node = node->next) {
2576     if (node->flag & NODE_ACTIVE) {
2577       break;
2578     }
2579   }
2580   return node;
2581 }
2582
2583 static bNode *node_get_active_id_recursive(bNodeInstanceKey active_key,
2584                                            bNodeInstanceKey parent_key,
2585                                            bNodeTree *ntree,
2586                                            short idtype)
2587 {
2588   if (parent_key.value == active_key.value || active_key.value == 0) {
2589     bNode *node;
2590     for (node = ntree->nodes.first; node; node = node->next) {
2591       if (node->id && GS(node->id->name) == idtype) {
2592         if (node->flag & NODE_ACTIVE_ID) {
2593           return node;
2594         }
2595       }
2596     }
2597   }
2598   else {
2599     bNode *node, *tnode;
2600     /* no node with active ID in this tree, look inside groups */
2601     for (node = ntree->nodes.first; node; node = node->next) {
2602       if (node->type == NODE_GROUP) {
2603         bNodeTree *group = (bNodeTree *)node->id;
2604         if (group) {
2605           bNodeInstanceKey group_key = BKE_node_instance_key(parent_key, ntree, node);
2606           tnode = node_get_active_id_recursive(active_key, group_key, group, idtype);
2607           if (tnode) {
2608             return tnode;
2609           }
2610         }
2611       }
2612     }
2613   }
2614
2615   return NULL;
2616 }
2617
2618 /* two active flags, ID nodes have special flag for buttons display */
2619 bNode *nodeGetActiveID(bNodeTree *ntree, short idtype)
2620 {
2621   if (ntree) {
2622     return node_get_active_id_recursive(
2623         ntree->active_viewer_key, NODE_INSTANCE_KEY_BASE, ntree, idtype);
2624   }
2625   else {
2626     return NULL;
2627   }
2628 }
2629
2630 bool nodeSetActiveID(bNodeTree *ntree, short idtype, ID *id)
2631 {
2632   bNode *node;
2633   bool ok = false;
2634
2635   if (ntree == NULL) {
2636     return ok;
2637   }
2638
2639   for (node = ntree->nodes.first; node; node = node->next) {
2640     if (node->id && GS(node->id->name) == idtype) {
2641       if (id && ok == false && node->id == id) {
2642         node->flag |= NODE_ACTIVE_ID;
2643         ok = true;
2644       }
2645       else {
2646         node->flag &= ~NODE_ACTIVE_ID;
2647       }
2648     }
2649   }
2650
2651   /* update all groups linked from here
2652    * if active ID node has been found already,
2653    * just pass NULL so other matching nodes are deactivated.
2654    */
2655   for (node = ntree->nodes.first; node; node = node->next) {
2656     if (node->type == NODE_GROUP) {
2657       ok |= nodeSetActiveID((bNodeTree *)node->id, idtype, (ok == false ? id : NULL));
2658     }
2659   }
2660
2661   return ok;
2662 }
2663
2664 /* two active flags, ID nodes have special flag for buttons display */
2665 void nodeClearActiveID(bNodeTree *ntree, short idtype)
2666 {
2667   bNode *node;
2668
2669   if (ntree == NULL) {
2670     return;
2671   }
2672
2673   for (node = ntree->nodes.first; node; node = node->next) {
2674     if (node->id && GS(node->id->name) == idtype) {
2675       node->flag &= ~NODE_ACTIVE_ID;
2676     }
2677   }
2678 }
2679
2680 void nodeSetSelected(bNode *node, bool select)
2681 {
2682   if (select) {
2683     node->flag |= NODE_SELECT;
2684   }
2685   else {
2686     bNodeSocket *sock;
2687
2688     node->flag &= ~NODE_SELECT;
2689
2690     /* deselect sockets too */
2691     for (sock = node->inputs.first; sock; sock = sock->next) {
2692       sock->flag &= ~NODE_SELECT;
2693     }
2694     for (sock = node->outputs.first; sock; sock = sock->next) {
2695       sock->flag &= ~NODE_SELECT;
2696     }
2697   }
2698 }
2699
2700 void nodeClearActive(bNodeTree *ntree)
2701 {
2702   bNode *node;
2703
2704   if (ntree == NULL) {
2705     return;
2706   }
2707
2708   for (node = ntree->nodes.first; node; node = node->next) {
2709     node->flag &= ~(NODE_ACTIVE | NODE_ACTIVE_ID);
2710   }
2711 }
2712
2713 /* two active flags, ID nodes have special flag for buttons display */
2714 void nodeSetActive(bNodeTree *ntree, bNode *node)
2715 {
2716   bNode *tnode;
2717
2718   /* make sure only one node is active, and only one per ID type */
2719   for (tnode = ntree->nodes.first; tnode; tnode = tnode->next) {
2720     tnode->flag &= ~NODE_ACTIVE;
2721
2722     if (node->id && tnode->id) {
2723       if (GS(node->id->name) == GS(tnode->id->name)) {
2724         tnode->flag &= ~NODE_ACTIVE_ID;
2725       }
2726     }
2727     if (node->typeinfo->nclass == NODE_CLASS_TEXTURE) {
2728       tnode->flag &= ~NODE_ACTIVE_TEXTURE;
2729     }
2730   }
2731
2732   node->flag |= NODE_ACTIVE;
2733   if (node->id) {
2734     node->flag |= NODE_ACTIVE_ID;
2735   }
2736   if (node->typeinfo->nclass == NODE_CLASS_TEXTURE) {
2737     node->flag |= NODE_ACTIVE_TEXTURE;
2738   }
2739 }
2740
2741 int nodeSocketIsHidden(bNodeSocket *sock)
2742 {
2743   return ((sock->flag & (SOCK_HIDDEN | SOCK_UNAVAIL)) != 0);
2744 }
2745
2746 /* ************** Node Clipboard *********** */
2747
2748 #define USE_NODE_CB_VALIDATE
2749
2750 #ifdef USE_NODE_CB_VALIDATE
2751 /**
2752  * This data structure is to validate the node on creation,
2753  * otherwise we may reference missing data.
2754  *
2755  * Currently its only used for ID's, but nodes may one day
2756  * reference other pointers which need validation.
2757  */
2758 typedef struct bNodeClipboardExtraInfo {
2759   struct bNodeClipboardExtraInfo *next, *prev;
2760   ID *id;
2761   char id_name[MAX_ID_NAME];
2762   char library_name[FILE_MAX];
2763 } bNodeClipboardExtraInfo;
2764 #endif /* USE_NODE_CB_VALIDATE */
2765
2766 typedef struct bNodeClipboard {
2767   ListBase nodes;
2768
2769 #ifdef USE_NODE_CB_VALIDATE
2770   ListBase nodes_extra_info;
2771 #endif
2772
2773   ListBase links;
2774   int type;
2775 } bNodeClipboard;
2776
2777 static bNodeClipboard node_clipboard = {{NULL}};
2778
2779 void BKE_node_clipboard_init(struct bNodeTree *ntree)
2780 {
2781   node_clipboard.type = ntree->type;
2782 }
2783
2784 void BKE_node_clipboard_clear(void)
2785 {
2786   bNode *node, *node_next;
2787   bNodeLink *link, *link_next;
2788
2789   for (link = node_clipboard.links.first; link; link = link_next) {
2790     link_next = link->next;
2791     nodeRemLink(NULL, link);
2792   }
2793   BLI_listbase_clear(&node_clipboard.links);
2794
2795   for (node = node_clipboard.nodes.first; node; node = node_next) {
2796     node_next = node->next;
2797     node_free_node(NULL, node);
2798   }
2799   BLI_listbase_clear(&node_clipboard.nodes);
2800
2801 #ifdef USE_NODE_CB_VALIDATE
2802   BLI_freelistN(&node_clipboard.nodes_extra_info);
2803 #endif
2804 }
2805
2806 /* return false when one or more ID's are lost */
2807 bool BKE_node_clipboard_validate(void)
2808 {
2809   bool ok = true;
2810
2811 #ifdef USE_NODE_CB_VALIDATE
2812   bNodeClipboardExtraInfo *node_info;
2813   bNode *node;
2814
2815   /* lists must be aligned */
2816   BLI_assert(BLI_listbase_count(&node_clipboard.nodes) ==
2817              BLI_listbase_count(&node_clipboard.nodes_extra_info));
2818
2819   for (node = node_clipboard.nodes.first, node_info = node_clipboard.nodes_extra_info.first; node;
2820        node = node->next, node_info = node_info->next) {
2821     /* validate the node against the stored node info */
2822
2823     /* re-assign each loop since we may clear,
2824      * open a new file where the ID is valid, and paste again */
2825     node->id = node_info->id;
2826
2827     /* currently only validate the ID */
2828     if (node->id) {
2829       /* We want to search into current blend file, so using G_MAIN is valid here too. */
2830       ListBase *lb = which_libbase(G_MAIN, GS(node_info->id_name));
2831       BLI_assert(lb != NULL);
2832
2833       if (BLI_findindex(lb, node_info->id) == -1) {
2834         /* may assign NULL */
2835         node->id = BLI_findstring(lb, node_info->id_name + 2, offsetof(ID, name) + 2);
2836
2837         if (node->id == NULL) {
2838           ok = false;
2839         }
2840       }
2841     }
2842   }
2843 #endif /* USE_NODE_CB_VALIDATE */
2844
2845   return ok;
2846 }
2847
2848 void BKE_node_clipboard_add_node(bNode *node)
2849 {
2850 #ifdef USE_NODE_CB_VALIDATE
2851   /* add extra info */
2852   bNodeClipboardExtraInfo *node_info = MEM_mallocN(sizeof(bNodeClipboardExtraInfo),
2853                                                    "bNodeClipboardExtraInfo");
2854
2855   node_info->id = node->id;
2856   if (node->id) {
2857     BLI_strncpy(node_info->id_name, node->id->name, sizeof(node_info->id_name));
2858     if (ID_IS_LINKED(node->id)) {
2859       BLI_strncpy(
2860           node_info->library_name, node->id->lib->filepath, sizeof(node_info->library_name));
2861     }
2862     else {
2863       node_info->library_name[0] = '\0';
2864     }
2865   }
2866   else {
2867     node_info->id_name[0] = '\0';
2868     node_info->library_name[0] = '\0';
2869   }
2870   BLI_addtail(&node_clipboard.nodes_extra_info, node_info);
2871   /* end extra info */
2872 #endif /* USE_NODE_CB_VALIDATE */
2873
2874   /* add node */
2875   BLI_addtail(&node_clipboard.nodes, node);
2876 }
2877
2878 void BKE_node_clipboard_add_link(bNodeLink *link)
2879 {
2880   BLI_addtail(&node_clipboard.links, link);
2881 }
2882
2883 const ListBase *BKE_node_clipboard_get_nodes(void)
2884 {
2885   return &node_clipboard.nodes;
2886 }
2887
2888 const ListBase *BKE_node_clipboard_get_links(void)
2889 {
2890   return &node_clipboard.links;
2891 }
2892
2893 int BKE_node_clipboard_get_type(void)
2894 {
2895   return node_clipboard.type;
2896 }
2897
2898 void BKE_node_clipboard_free(void)
2899 {
2900   BKE_node_clipboard_validate();
2901   BKE_node_clipboard_clear();
2902 }
2903
2904 /* Node Instance Hash */
2905
2906 /* magic number for initial hash key */
2907 const bNodeInstanceKey NODE_INSTANCE_KEY_BASE = {5381};
2908 const bNodeInstanceKey NODE_INSTANCE_KEY_NONE = {0};
2909
2910 /* Generate a hash key from ntree and node names
2911  * Uses the djb2 algorithm with xor by Bernstein:
2912  * http://www.cse.yorku.ca/~oz/hash.html
2913  */
2914 static bNodeInstanceKey node_hash_int_str(bNodeInstanceKey hash, const char *str)
2915 {
2916   char c;
2917
2918   while ((c = *str++)) {
2919     hash.value = ((hash.value << 5) + hash.value) ^ c; /* (hash * 33) ^ c */
2920   }
2921
2922   /* separator '\0' character, to avoid ambiguity from concatenated strings */
2923   hash.value = (hash.value << 5) + hash.value; /* hash * 33 */
2924
2925   return hash;
2926 }
2927
2928 bNodeInstanceKey BKE_node_instance_key(bNodeInstanceKey parent_key, bNodeTree *ntree, bNode *node)
2929 {
2930   bNodeInstanceKey key;
2931
2932   key = node_hash_int_str(parent_key, ntree->id.name + 2);
2933
2934   if (node) {
2935     key = node_hash_int_str(key, node->name);
2936   }
2937
2938   return key;
2939 }
2940
2941 static unsigned int node_instance_hash_key(const void *key)
2942 {
2943   return ((const bNodeInstanceKey *)key)->value;
2944 }
2945
2946 static bool node_instance_hash_key_cmp(const void *a, const void *b)
2947 {
2948   unsigned int value_a = ((const bNodeInstanceKey *)a)->value;
2949   unsigned int value_b = ((const bNodeInstanceKey *)b)->value;
2950
2951   return (value_a != value_b);
2952 }
2953
2954 bNodeInstanceHash *BKE_node_instance_hash_new(const char *info)
2955 {
2956   bNodeInstanceHash *hash = MEM_mallocN(sizeof(bNodeInstanceHash), info);
2957   hash->ghash = BLI_ghash_new(
2958       node_instance_hash_key, node_instance_hash_key_cmp, "node instance hash ghash");
2959   return hash;
2960 }
2961
2962 void BKE_node_instance_hash_free(bNodeInstanceHash *hash, bNodeInstanceValueFP valfreefp)
2963 {
2964   BLI_ghash_free(hash->ghash, NULL, (GHashValFreeFP)valfreefp);
2965   MEM_freeN(hash);
2966 }
2967
2968 void BKE_node_instance_hash_insert(bNodeInstanceHash *hash, bNodeInstanceKey key, void *value)
2969 {
2970   bNodeInstanceHashEntry *entry = value;
2971   entry->key = key;
2972   entry->tag = 0;
2973   BLI_ghash_insert(hash->ghash, &entry->key, value);
2974 }
2975
2976 void *BKE_node_instance_hash_lookup(bNodeInstanceHash *hash, bNodeInstanceKey key)
2977 {
2978   return BLI_ghash_lookup(hash->ghash, &key);
2979 }
2980
2981 int BKE_node_instance_hash_remove(bNodeInstanceHash *hash,
2982                                   bNodeInstanceKey key,
2983                                   bNodeInstanceValueFP valfreefp)
2984 {
2985   return BLI_ghash_remove(hash->ghash, &key, NULL, (GHashValFreeFP)valfreefp);
2986 }
2987
2988 void BKE_node_instance_hash_clear(bNodeInstanceHash *hash, bNodeInstanceValueFP valfreefp)
2989 {
2990   BLI_ghash_clear(hash->ghash, NULL, (GHashValFreeFP)valfreefp);
2991 }
2992
2993 void *BKE_node_instance_hash_pop(bNodeInstanceHash *hash, bNodeInstanceKey key)
2994 {
2995   return BLI_ghash_popkey(hash->ghash, &key, NULL);
2996 }
2997
2998 int BKE_node_instance_hash_haskey(bNodeInstanceHash *hash, bNodeInstanceKey key)
2999 {
3000   return BLI_ghash_haskey(hash->ghash, &key);
3001 }
3002
3003 int BKE_node_instance_hash_size(bNodeInstanceHash *hash)
3004 {
3005   return BLI_ghash_len(hash->ghash);
3006 }
3007
3008 void BKE_node_instance_hash_clear_tags(bNodeInstanceHash *hash)
3009 {
3010   bNodeInstanceHashIterator iter;
3011
3012   NODE_INSTANCE_HASH_ITER (iter, hash) {
3013     bNodeInstanceHashEntry *value = BKE_node_instance_hash_iterator_get_value(&iter);
3014
3015     value->tag = 0;
3016   }
3017 }
3018
3019 void BKE_node_instance_hash_tag(bNodeInstanceHash *UNUSED(hash), void *value)
3020 {
3021   bNodeInstanceHashEntry *entry = value;
3022   entry->tag = 1;
3023 }
3024
3025 bool BKE_node_instance_hash_tag_key(bNodeInstanceHash *hash, bNodeInstanceKey key)
3026 {
3027   bNodeInstanceHashEntry *entry = BKE_node_instance_hash_lookup(hash, key);
3028
3029   if (entry) {
3030     entry->tag = 1;
3031     return true;
3032   }
3033   else {
3034     return false;
3035   }
3036 }
3037
3038 void BKE_node_instance_hash_remove_untagged(bNodeInstanceHash *hash,
3039                                             bNodeInstanceValueFP valfreefp)
3040 {
3041   /* NOTE: Hash must not be mutated during iterating!
3042    * Store tagged entries in a separate list and remove items afterward.
3043    */
3044   bNodeInstanceKey *untagged = MEM_mallocN(sizeof(bNodeInstanceKey) *
3045                                                BKE_node_instance_hash_size(hash),
3046                                            "temporary node instance key list");
3047   bNodeInstanceHashIterator iter;
3048   int num_untagged, i;
3049
3050   num_untagged = 0;
3051   NODE_INSTANCE_HASH_ITER (iter, hash) {
3052     bNodeInstanceHashEntry *value = BKE_node_instance_hash_iterator_get_value(&iter);
3053
3054     if (!value->tag) {
3055       untagged[num_untagged++] = BKE_node_instance_hash_iterator_get_key(&iter);
3056     }
3057   }
3058
3059   for (i = 0; i < num_untagged; ++i) {
3060     BKE_node_instance_hash_remove(hash, untagged[i], valfreefp);
3061   }
3062
3063   MEM_freeN(untagged);
3064 }
3065
3066 /* ************** dependency stuff *********** */
3067
3068 /* node is guaranteed to be not checked before */
3069 static int node_get_deplist_recurs(bNodeTree *ntree, bNode *node, bNode ***nsort)
3070 {
3071   bNode *fromnode;
3072   bNodeLink *link;
3073   int level = 0xFFF;
3074
3075   node->done = true;
3076
3077   /* check linked nodes */
3078   for (link = ntree->links.first; link; link = link->next) {
3079     if (link->tonode == node) {
3080       fromnode = link->fromnode;
3081       if (fromnode->done == 0) {
3082         fromnode->level = node_get_deplist_recurs(ntree, fromnode, nsort);
3083       }
3084       if (fromnode->level <= level) {
3085         level = fromnode->level - 1;
3086       }
3087     }
3088   }
3089
3090   /* check parent node */
3091   if (node->parent) {
3092     if (node->parent->done == 0) {
3093       node->parent->level = node_get_deplist_recurs(ntree, node->parent, nsort);
3094     }
3095     if (node->parent->level <= level) {
3096       level = node->parent->level - 1;
3097     }
3098   }
3099
3100   if (nsort) {
3101     **nsort = node;
3102     (*nsort)++;
3103   }
3104
3105   return level;
3106 }
3107
3108 void ntreeGetDependencyList(struct bNodeTree *ntree, struct bNode ***deplist, int *totnodes)
3109 {
3110   bNode *node, **nsort;
3111
3112   *totnodes = 0;
3113
3114   /* first clear data */
3115   for (node = ntree->nodes.first; node; node = node->next) {
3116     node->done = false;
3117     (*totnodes)++;
3118   }
3119   if (*totnodes == 0) {
3120     *deplist = NULL;
3121     return;
3122   }
3123
3124   nsort = *deplist = MEM_callocN((*totnodes) * sizeof(bNode *), "sorted node array");
3125
3126   /* recursive check */
3127   for (node = ntree->nodes.first; node; node = node->next) {
3128     if (node->done == 0) {
3129       node->level = node_get_deplist_recurs(ntree, node, &nsort);
3130     }
3131   }
3132 }
3133
3134 /* only updates node->level for detecting cycles links */
3135 static void ntree_update_node_level(bNodeTree *ntree)
3136 {
3137   bNode *node;
3138
3139   /* first clear tag */
3140   for (node = ntree->nodes.first; node; node = node->next) {
3141     node->done = false;
3142   }
3143
3144   /* recursive check */
3145   for (node = ntree->nodes.first; node; node = node->next) {
3146     if (node->done == 0) {
3147       node->level = node_get_deplist_recurs(ntree, node, NULL);
3148     }
3149   }
3150 }
3151
3152 void ntreeTagUsedSockets(bNodeTree *ntree)
3153 {
3154   bNode *node;
3155   bNodeSocket *sock;
3156   bNodeLink *link;
3157
3158   /* first clear data */
3159   for (node = ntree->nodes.first; node; node = node->next) {
3160     for (sock = node->inputs.first; sock; sock = sock->next) {
3161       sock->flag &= ~SOCK_IN_USE;
3162     }
3163     for (sock = node->outputs.first; sock; sock = sock->next) {
3164       sock->flag &= ~SOCK_IN_USE;
3165     }
3166   }
3167
3168   for (link = ntree->links.first; link; link = link->next) {
3169     /* link is unused if either side is disabled */
3170     if ((link->fromsock->flag & SOCK_UNAVAIL) || (link->tosock->flag & SOCK_UNAVAIL)) {
3171       continue;
3172     }
3173
3174     link->fromsock->flag |= SOCK_IN_USE;
3175     link->tosock->flag |= SOCK_IN_USE;
3176   }
3177 }
3178
3179 static void ntree_update_link_pointers(bNodeTree *ntree)
3180 {
3181   bNode *node;
3182   bNodeSocket *sock;
3183   bNodeLink *link;
3184
3185   /* first clear data */
3186   for (node = ntree->nodes.first; node; node = node->next) {
3187     for (sock = node->inputs.first; sock; sock = sock->next) {
3188       sock->link = NULL;
3189     }
3190   }
3191
3192   for (link = ntree->links.first; link; link = link->next) {
3193     link->tosock->link = link;
3194   }
3195
3196   ntreeTagUsedSockets(ntree);
3197 }
3198
3199 static void ntree_validate_links(bNodeTree *ntree)
3200 {
3201   bNodeLink *link;
3202
3203   for (link = ntree->links.first; link; link = link->next) {
3204     link->flag |= NODE_LINK_VALID;
3205     if (link->fromnode && link->tonode && link->fromnode->level <= link->tonode->level) {
3206       link->flag &= ~NODE_LINK_VALID;
3207     }
3208     else if (ntree->typeinfo->validate_link) {
3209       if (!ntree->typeinfo->validate_link(ntree, link)) {
3210         link->flag &= ~NODE_LINK_VALID;
3211       }
3212     }
3213   }
3214 }
3215
3216 void ntreeUpdateAllNew(Main *main)
3217 {
3218   /* Update all new node trees on file read or append, to add/remove sockets
3219    * in groups nodes if the group changed, and handle any update flags that
3220    * might have been set in file reading or versioning. */
3221   FOREACH_NODETREE_BEGIN (main, ntree, owner_id) {
3222     if (owner_id->tag & LIB_TAG_NEW) {
3223       for (bNode *node = ntree->nodes.first; node; node = node->next) {
3224         if (node->typeinfo->group_update_func) {
3225           node->typeinfo->group_update_func(ntree, node);
3226         }
3227       }
3228
3229       ntreeUpdateTree(NULL, ntree);
3230     }
3231   }
3232   FOREACH_NODETREE_END;
3233 }
3234
3235 void ntreeUpdateAllUsers(Main *main, ID *ngroup)
3236 {
3237   /* Update all users of ngroup, to add/remove sockets as needed. */
3238   FOREACH_NODETREE_BEGIN (main, ntree, owner_id) {
3239     bool need_update = false;
3240
3241     for (bNode *node = ntree->nodes.first; node; node = node->next) {
3242       if (node->id == ngroup) {
3243         if (node->typeinfo->group_update_func) {
3244           node->typeinfo->group_update_func(ntree, node);
3245         }
3246
3247         need_update = true;
3248       }
3249     }
3250
3251     if (need_update) {
3252       ntreeUpdateTree(NULL, ntree);
3253     }
3254   }
3255   FOREACH_NODETREE_END;
3256 }
3257
3258 void ntreeUpdateTree(Main *bmain, bNodeTree *ntree)
3259 {
3260   bNode *node;
3261
3262   if (!ntree) {
3263     return;
3264   }
3265
3266   /* avoid reentrant updates, can be caused by RNA update callbacks */
3267   if (ntree->is_updating) {
3268     return;
3269   }
3270   ntree->is_updating = true;
3271
3272   if (ntree->update & (NTREE_UPDATE_LINKS | NTREE_UPDATE_NODES)) {
3273     /* set the bNodeSocket->link pointers */
3274     ntree_update_link_pointers(ntree);
3275   }
3276
3277   /* update individual nodes */
3278   for (node = ntree->nodes.first; node; node = node->next) {
3279     /* node tree update tags override individual node update flags */
3280     if ((node->update & NODE_UPDATE) || (ntree->update & NTREE_UPDATE)) {
3281       if (node->typeinfo->updatefunc) {
3282         node->typeinfo->updatefunc(ntree, node);
3283       }
3284
3285       nodeUpdateInternalLinks(ntree, node);
3286     }
3287   }
3288
3289   /* generic tree update callback */
3290   if (ntree->typeinfo->update) {
3291     ntree->typeinfo->update(ntree);
3292   }
3293   /* XXX this should be moved into the tree type update callback for tree supporting node groups.
3294    * Currently the node tree interface is still a generic feature of the base NodeTree type.
3295    */
3296   if (ntree->update & NTREE_UPDATE_GROUP) {
3297     ntreeInterfaceTypeUpdate(ntree);
3298   }
3299
3300   /* XXX hack, should be done by depsgraph!! */
3301   if (bmain) {
3302     ntreeUpdateAllUsers(bmain, &ntree->id);
3303   }
3304
3305   if (ntree->update & (NTREE_UPDATE_LINKS | NTREE_UPDATE_NODES)) {
3306     /* node updates can change sockets or links, repeat link pointer update afterward */
3307     ntree_update_link_pointers(ntree);
3308
3309     /* update the node level from link dependencies */
3310     ntree_update_node_level(ntree);
3311
3312     /* check link validity */
3313     ntree_validate_links(ntree);
3314   }
3315
3316   /* clear update flags */
3317   for (node = ntree->nodes.first; node; node = node->next) {
3318     node->update = 0;
3319   }
3320   ntree->update = 0;
3321
3322   ntree->is_updating = false;
3323 }
3324
3325 void nodeUpdate(bNodeTree *ntree, bNode *node)
3326 {
3327   /* avoid reentrant updates, can be caused by RNA update callbacks */
3328   if (ntree->is_updating) {
3329     return;
3330   }
3331   ntree->is_updating = true;
3332
3333   if (node->typeinfo->updatefunc) {
3334     node->typeinfo->updatefunc(ntree, node);
3335   }
3336
3337   nodeUpdateInternalLinks(ntree, node);
3338
3339   /* clear update flag */
3340   node->update = 0;
3341
3342   ntree->is_updating = false;
3343 }
3344
3345 bool nodeUpdateID(bNodeTree *ntree, ID *id)
3346 {
3347   bNode *node;
3348   bool changed = false;
3349
3350   if (ELEM(NULL, id, ntree)) {
3351     return changed;
3352   }
3353
3354   /* avoid reentrant updates, can be caused by RNA update callbacks */
3355   if (ntree->is_updating) {
3356     return changed;
3357   }
3358   ntree->is_updating = true;
3359
3360   for (node = ntree->nodes.first; node; node = node->next) {
3361     if (node->id == id) {
3362       changed = true;
3363       node->update |= NODE_UPDATE_ID;
3364       if (node->typeinfo->updatefunc) {
3365         node->typeinfo->updatefunc(ntree, node);
3366       }
3367       /* clear update flag */
3368       node->update = 0;
3369     }
3370   }
3371
3372   for (node = ntree->nodes.first; node; node = node->next) {
3373     nodeUpdateInternalLinks(ntree, node);
3374   }
3375
3376   ntree->is_updating = false;
3377   return changed;
3378 }
3379
3380 void nodeUpdateInternalLinks(bNodeTree *ntree, bNode *node)
3381 {
3382   BLI_freelistN(&node->internal_links);
3383
3384   if (node->typeinfo && node->typeinfo->update_internal_links) {
3385     node->typeinfo->update_internal_links(ntree, node);
3386   }
3387 }
3388
3389 /* ************* node type access ********** */
3390
3391 void nodeLabel(bNodeTree *ntree, bNode *node, char *label, int maxlen)
3392 {
3393   label[0] = '\0';
3394
3395   if (node->label[0] != '\0') {
3396     BLI_strncpy(label, node->label, maxlen);
3397   }
3398   else if (node->typeinfo->labelfunc) {
3399     node->typeinfo->labelfunc(ntree, node, label, maxlen);
3400   }
3401
3402   /* The previous methods (labelfunc) could not provide an adequate label for the node. */
3403   if (label[0] == '\0') {
3404     /* Kind of hacky and weak... Ideally would be better to use RNA here. :| */
3405     const char *tmp = CTX_IFACE_(BLT_I18NCONTEXT_ID_NODETREE, node->typeinfo->ui_name);
3406     if (tmp == node->typeinfo->ui_name) {
3407       tmp = IFACE_(node->typeinfo->ui_name);
3408     }
3409     BLI_strncpy(label, tmp, maxlen);
3410   }
3411 }
3412
3413 static void node_type_base_defaults(bNodeType *ntype)
3414 {
3415   /* default size values */
3416   node_type_size_preset(ntype, NODE_SIZE_DEFAULT);
3417   ntype->height = 100;
3418   ntype->minheight = 30;
3419   ntype->maxheight = FLT_MAX;
3420 }
3421
3422 /* allow this node for any tree type */
3423 static bool node_poll_default(bNodeType *UNUSED(ntype), bNodeTree *UNUSED(ntree))
3424 {
3425   return true;
3426 }
3427
3428 /* use the basic poll function */
3429 static bool node_poll_instance_default(bNode *node, bNodeTree *ntree)
3430 {
3431   return node->typeinfo->poll(node->typeinfo, ntree);
3432 }
3433
3434 void node_type_base(bNodeType *ntype, int type, const char *name, short nclass, short flag)
3435 {
3436   /* Use static type info header to map static int type to identifier string and RNA struct type.
3437    * Associate the RNA struct type with the bNodeType.
3438    * Dynamically registered nodes will create an RNA type at runtime
3439    * and call RNA_struct_blender_type_set, so this only needs to be done for old RNA types
3440    * created in makesrna, which can not be associated to a bNodeType immediately,
3441    * since bNodeTypes are registered afterward ...
3442    */
3443 #define DefNode(Category, ID, DefFunc, EnumName, StructName, UIName, UIDesc) \
3444   case ID: \
3445     BLI_strncpy(ntype->idname, #Category #StructName, sizeof(ntype->idname)); \
3446     ntype->ext.srna = RNA_struct_find(#Category #StructName); \
3447     BLI_assert(ntype->ext.srna != NULL); \
3448     RNA_struct_blender_type_set(ntype->ext.srna, ntype); \
3449     break;
3450
3451   switch (type) {
3452 #include "NOD_static_types.h"
3453   }
3454
3455   /* make sure we have a valid type (everything registered) */
3456   BLI_assert(ntype->idname[0] != '\0');
3457
3458   ntype->type = type;
3459   BLI_strncpy(ntype->ui_name, name, sizeof(ntype->ui_name));
3460   ntype->nclass = nclass;
3461   ntype->flag = flag;
3462
3463   node_type_base_defaults(ntype);
3464
3465   ntype->poll = node_poll_default;
3466   ntype->poll_instance = node_poll_instance_default;
3467 }
3468
3469 void node_type_base_custom(
3470     bNodeType *ntype, const char *idname, const char *name, short nclass, short flag)
3471 {
3472   BLI_strncpy(ntype->idname, idname, sizeof(ntype->idname));
3473   ntype->type = NODE_CUSTOM;
3474   BLI_strncpy(ntype->ui_name, name, sizeof(ntype->ui_name));
3475   ntype->nclass = nclass;
3476   ntype->flag = flag;
3477
3478   node_type_base_defaults(ntype);
3479 }
3480
3481 static bool unique_socket_template_identifier_check(void *arg, const char *name)
3482 {
3483   bNodeSocketTemplate *ntemp;
3484   struct {
3485     bNodeSocketTemplate *list;
3486     bNodeSocketTemplate *ntemp;
3487   } *data = arg;
3488
3489   for (ntemp = data->list; ntemp->type >= 0; ++ntemp) {
3490     if (ntemp != data->ntemp) {
3491       if (STREQ(ntemp->identifier, name)) {
3492         return true;
3493       }
3494     }
3495   }
3496
3497   return false;
3498 }
3499
3500 static void unique_socket_template_identifier(bNodeSocketTemplate *list,
3501                                               bNodeSocketTemplate *ntemp,
3502                                               const char defname[],
3503                                               char delim)
3504 {
3505   struct {
3506     bNodeSocketTemplate *list;
3507     bNodeSocketTemplate *ntemp;
3508   } data;
3509   data.list = list;
3510   data.ntemp = ntemp;
3511
3512   BLI_uniquename_cb(unique_socket_template_identifier_check,
3513                     &data,
3514                     defname,
3515                     delim,
3516                     ntemp->identifier,
3517                     sizeof(ntemp->identifier));
3518 }
3519
3520 void node_type_socket_templates(struct bNodeType *ntype,
3521                                 struct bNodeSocketTemplate *inputs,
3522                                 struct bNodeSocketTemplate *outputs)
3523 {
3524   bNodeSocketTemplate *ntemp;
3525
3526   ntype->inputs = inputs;
3527   ntype->outputs = outputs;
3528
3529   /* automatically generate unique identifiers */
3530   if (inputs) {
3531     /* clear identifier strings (uninitialized memory) */
3532     for (ntemp = inputs; ntemp->type >= 0; ++ntemp) {
3533       ntemp->identifier[0] = '\0';
3534     }
3535
3536     for (ntemp = inputs; ntemp->type >= 0; ++ntemp) {
3537       BLI_strncpy(ntemp->identifier, ntemp->name, sizeof(ntemp->identifier));
3538       unique_socket_template_identifier(inputs, ntemp, ntemp->identifier, '_');
3539     }
3540   }
3541   if (outputs) {
3542     /* clear identifier strings (uninitialized memory) */
3543     for (ntemp = outputs; ntemp->type >= 0; ++ntemp) {
3544       ntemp->identifier[0] = '\0';
3545     }
3546
3547     for (ntemp = outputs; ntemp->type >= 0; ++ntemp) {
3548       BLI_strncpy(ntemp->identifier, ntemp->name, sizeof(ntemp->identifier));
3549       unique_socket_template_identifier(outputs, ntemp, ntemp->identifier, '_');
3550     }
3551   }
3552 }
3553
3554 void node_type_init(struct bNodeType *ntype,
3555                     void (*initfunc)(struct bNodeTree *ntree, struct bNode *node))
3556 {
3557   ntype->initfunc = initfunc;
3558 }
3559
3560 void node_type_size(struct bNodeType *ntype, int width, int minwidth, int maxwidth)
3561 {
3562   ntype->width = width;
3563   ntype->minwidth = minwidth;
3564   if (maxwidth <= minwidth) {
3565     ntype->maxwidth = FLT_MAX;
3566   }
3567   else {
3568     ntype->maxwidth = maxwidth;
3569   }
3570 }
3571
3572 void node_type_size_preset(struct bNodeType *ntype, eNodeSizePreset size)
3573 {
3574   switch (size) {
3575     case NODE_SIZE_DEFAULT:
3576       node_type_size(ntype, 140, 100, NODE_DEFAULT_MAX_WIDTH);
3577       break;
3578     case NODE_SIZE_SMALL:
3579       node_type_size(ntype, 100, 80, NODE_DEFAULT_MAX_WIDTH);
3580       break;
3581     case NODE_SIZE_MIDDLE:
3582       node_type_size(ntype, 150, 120, NODE_DEFAULT_MAX_WIDTH);
3583       break;
3584     case NODE_SIZE_LARGE:
3585       node_type_size(ntype, 240, 140, NODE_DEFAULT_MAX_WIDTH);
3586       break;
3587   }
3588 }
3589
3590 /**
3591  * \warning Nodes defining a storage type _must_ allocate this for new nodes.
3592  * Otherwise nodes will reload as undefined (T46619).
3593  */
3594 void node_type_storage(bNodeType *ntype,
3595                        const char *storagename,
3596                        void (*freefunc)(struct bNode *node),
3597                        void (*copyfunc)(struct bNodeTree *dest_ntree,
3598                                         struct bNode *dest_node,
3599                                         struct bNode *src_node))
3600 {
3601   if (storagename) {
3602     BLI_strncpy(ntype->storagename, storagename, sizeof(ntype->storagename));
3603   }
3604   else {
3605     ntype->storagename[0] = '\0';
3606   }
3607   ntype->copyfunc = copyfunc;
3608   ntype->freefunc = freefunc;
3609 }
3610
3611 void node_type_label(
3612     struct bNodeType *ntype,
3613     void (*labelfunc)(struct bNodeTree *ntree, struct bNode *node, char *label, int maxlen))
3614 {
3615   ntype->labelfunc = labelfunc;
3616 }
3617
3618 void node_type_update(struct bNodeType *ntype,
3619                       void (*updatefunc)(struct bNodeTree *ntree, struct bNode *node))
3620 {
3621   ntype->updatefunc = updatefunc;
3622 }
3623
3624 void node_type_group_update(struct bNodeType *ntype,
3625                             void (*group_update_func)(struct bNodeTree *ntree, struct bNode *node))
3626 {
3627   ntype->group_update_func = group_update_func;
3628 }
3629
3630 void node_type_exec(struct bNodeType *ntype,
3631                     NodeInitExecFunction initexecfunc,
3632                     NodeFreeExecFunction freeexecfunc,
3633                     NodeExecFunction execfunc)
3634 {
3635   ntype->initexecfunc = initexecfunc;
3636   ntype->freeexecfunc = freeexecfunc;
3637   ntype->execfunc = execfunc;
3638 }
3639
3640 void node_type_gpu(struct bNodeType *ntype, NodeGPUExecFunction gpufunc)
3641 {
3642   ntype->gpufunc = gpufunc;
3643 }
3644
3645 void node_type_internal_links(bNodeType *ntype,
3646                               void (*update_internal_links)(bNodeTree *, bNode *))
3647 {
3648   ntype->update_internal_links = update_internal_links;
3649 }
3650
3651 /* callbacks for undefined types */
3652
3653 static bool node_undefined_poll(bNodeType *UNUSED(ntype), bNodeTree *UNUSED(nodetree))
3654 {
3655   /* this type can not be added deliberately, it's just a placeholder */
3656   return false;
3657 }
3658
3659 /* register fallback types used for undefined tree, nodes, sockets */
3660 static void register_undefined_types(void)
3661 {
3662   /* Note: these types are not registered in the type hashes,
3663    * they are just used as placeholders in case the actual types are not registered.
3664    */
3665
3666   strcpy(NodeTreeTypeUndefined.idname, "NodeTreeUndefined");
3667   strcpy(NodeTreeTypeUndefined.ui_name, N_("Undefined"));
3668   strcpy(NodeTreeTypeUndefined.ui_description, N_("Undefined Node Tree Type"));
3669
3670   node_type_base_custom(&NodeTypeUndefined, "NodeUndefined", "Undefined", 0, 0);
3671   NodeTypeUndefined.poll = node_undefined_poll;
3672
3673   BLI_strncpy(NodeSocketTypeUndefined.idname,
3674               "NodeSocketUndefined",
3675               sizeof(NodeSocketTypeUndefined.idname));
3676   /* extra type info for standard socket types */
3677   NodeSocketTypeUndefined.type = SOCK_CUSTOM;
3678   NodeSocketTypeUndefined.subtype = PROP_NONE;
3679 }
3680
3681 static void registerCompositNodes(void)
3682 {
3683   register_node_type_cmp_group();
3684
3685   register_node_type_cmp_rlayers();
3686   register_node_type_cmp_image();
3687   register_node_type_cmp_texture();
3688   register_node_type_cmp_value();
3689   register_node_type_cmp_rgb();
3690   register_node_type_cmp_curve_time();
3691   register_node_type_cmp_movieclip();
3692
3693   register_node_type_cmp_composite();
3694   register_node_type_cmp_viewer();
3695   register_node_type_cmp_splitviewer();
3696   register_node_type_cmp_output_file();
3697   register_node_type_cmp_view_levels();
3698
3699   register_node_type_cmp_curve_rgb();
3700   register_node_type_cmp_mix_rgb();
3701   register_node_type_cmp_hue_sat();
3702   register_node_type_cmp_brightcontrast();
3703   register_node_type_cmp_gamma();
3704   register_node_type_cmp_invert();
3705   register_node_type_cmp_alphaover();
3706   register_node_type_cmp_zcombine();
3707   register_node_type_cmp_colorbalance();
3708   register_node_type_cmp_huecorrect();
3709
3710   register_node_type_cmp_normal();
3711   register_node_type_cmp_curve_vec();
3712   register_node_type_cmp_map_value();
3713   register_node_type_cmp_map_range();
3714   register_node_type_cmp_normalize();
3715
3716   register_node_type_cmp_filter();
3717   register_node_type_cmp_blur();
3718   register_node_type_cmp_dblur();
3719   register_node_type_cmp_bilateralblur();
3720   register_node_type_cmp_vecblur();
3721   register_node_type_cmp_dilateerode();
3722   register_node_type_cmp_inpaint();
3723   register_node_type_cmp_despeckle();
3724   register_node_type_cmp_defocus();
3725   register_node_type_cmp_sunbeams();
3726
3727   register_node_type_cmp_valtorgb();
3728   register_node_type_cmp_rgbtobw();
3729   register_node_type_cmp_setalpha();
3730   register_node_type_cmp_idmask();
3731   register_node_type_cmp_math();
3732   register_node_type_cmp_seprgba();
3733   register_node_type_cmp_combrgba();
3734   register_node_type_cmp_sephsva();
3735   register_node_type_cmp_combhsva();
3736   register_node_type_cmp_sepyuva();
3737   register_node_type_cmp_combyuva();
3738   register_node_type_cmp_sepycca();
3739   register_node_type_cmp_combycca();
3740   register_node_type_cmp_premulkey();
3741
3742   register_node_type_cmp_diff_matte();
3743   register_node_type_cmp_distance_matte();
3744   register_node_type_cmp_chroma_matte();
3745   register_node_type_cmp_color_matte();
3746   register_node_type_cmp_channel_matte();
3747   register_node_type_cmp_color_spill();
3748   register_node_type_cmp_luma_matte();
3749   register_node_type_cmp_doubleedgemask();
3750   register_node_type_cmp_keyingscreen();
3751   register_node_type_cmp_keying();
3752   register_node_type_cmp_cryptomatte();
3753
3754   register_node_type_cmp_translate();
3755   register_node_type_cmp_rotate();
3756   register_node_type_cmp_scale();
3757   register_node_type_cmp_flip();
3758   register_node_type_cmp_crop();
3759   register_node_type_cmp_displace();
3760   register_node_type_cmp_mapuv();
3761   register_node_type_cmp_glare();
3762   register_node_type_cmp_tonemap();
3763   register_node_type_cmp_lensdist();
3764   register_node_type_cmp_transform();
3765   register_node_type_cmp_stabilize2d();
3766   register_node_type_cmp_moviedistortion();
3767
3768   register_node_type_cmp_colorcorrection();
3769   register_node_type_cmp_boxmask();
3770   register_node_type_cmp_ellipsemask();
3771   register_node_type_cmp_bokehimage();
3772   register_node_type_cmp_bokehblur();
3773   register_node_type_cmp_switch();
3774   register_node_type_cmp_switch_view();
3775   register_node_type_cmp_pixelate();
3776
3777   register_node_type_cmp_mask();
3778   register_node_type_cmp_trackpos();
3779   register_node_type_cmp_planetrackdeform();
3780   register_node_type_cmp_cornerpin();
3781 }
3782
3783 static void registerShaderNodes(void)
3784 {
3785   register_node_type_sh_group();
3786
3787   register_node_type_sh_camera();
3788   register_node_type_sh_gamma();
3789   register_node_type_sh_brightcontrast();
3790   register_node_type_sh_value();
3791   register_node_type_sh_rgb();
3792   register_node_type_sh_wireframe();
3793   register_node_type_sh_wavelength();
3794   register_node_type_sh_blackbody();
3795   register_node_type_sh_mix_rgb();
3796   register_node_type_sh_valtorgb();
3797   register_node_type_sh_rgbtobw();
3798   register_node_type_sh_shadertorgb();
3799   register_node_type_sh_normal();
3800   register_node_type_sh_mapping();
3801   register_node_type_sh_curve_vec();
3802   register_node_type_sh_curve_rgb();
3803   register_node_type_sh_math();
3804   register_node_type_sh_vect_math();
3805   register_node_type_sh_vect_transform();
3806   register_node_type_sh_squeeze();
3807   register_node_type_sh_invert();
3808   register_node_type_sh_seprgb();
3809   register_node_type_sh_combrgb();
3810   register_node_type_sh_sephsv();
3811   register_node_type_sh_combhsv();
3812   register_node_type_sh_sepxyz();
3813   register_node_type_sh_combxyz();
3814   register_node_type_sh_hue_sat();
3815
3816   register_node_type_sh_attribute();
3817   register_node_type_sh_bevel();
3818   register_node_type_sh_displacement();
3819   register_node_type_sh_vector_displacement();
3820   register_node_type_sh_geometry();
3821   register_node_type_sh_light_path();
3822   register_node_type_sh_light_falloff();
3823   register_node_type_sh_object_info();
3824   register_node_type_sh_fresnel();
3825   register_node_type_sh_layer_weight();
3826   register_node_type_sh_tex_coord();
3827   register_node_type_sh_particle_info();
3828   register_node_type_sh_bump();
3829
3830   register_node_type_sh_background();
3831   register_node_type_sh_bsdf_anisotropic();
3832   register_node_type_sh_bsdf_diffuse();
3833   register_node_type_sh_bsdf_principled();
3834   register_node_type_sh_bsdf_glossy();
3835   register_node_type_sh_bsdf_glass();
3836   register_node_type_sh_bsdf_translucent();
3837   register_node_type_sh_bsdf_transparent();
3838   register_node_type_sh_bsdf_velvet();
3839   register_node_type_sh_bsdf_toon();
3840   register_node_type_sh_bsdf_hair();
3841   register_node_type_sh_bsdf_hair_principled();
3842   register_node_type_sh_emission();
3843   register_node_type_sh_holdout();
3844   register_node_type_sh_volume_absorption();
3845   register_node_type_sh_volume_scatter();
3846   register_node_type_sh_volume_principled();
3847   register_node_type_sh_subsurface_scattering();
3848   register_node_type_sh_mix_shader();
3849   register_node_type_sh_add_shader();
3850   register_node_type_sh_uvmap();
3851   register_node_type_sh_uvalongstroke();
3852   register_node_type_sh_eevee_specular();
3853
3854   register_node_type_sh_output_light();
3855   register_node_type_sh_output_material();
3856   register_node_type_sh_output_world();
3857   register_node_type_sh_output_linestyle();
3858