Cleanup: rename IDP_FreeProperty_ex to IDP_FreePropertyContent_ex
[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_FreePropertyContent_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_FreePropertyContent_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   }
1914
1915   if (sock->default_value) {
1916     MEM_freeN(sock->default_value);
1917   }
1918 }
1919
1920 static void free_localized_node_groups(bNodeTree *ntree)
1921 {
1922   bNode *node;
1923
1924   /* Only localized node trees store a copy for each node group tree.
1925    * Each node group tree in a localized node tree can be freed,
1926    * since it is a localized copy itself (no risk of accessing free'd
1927    * data in main, see [#37939]).
1928    */
1929   if (!(ntree->id.tag & LIB_TAG_LOCALIZED)) {
1930     return;
1931   }
1932
1933   for (node = ntree->nodes.first; node; node = node->next) {
1934     if ((ELEM(node->type, NODE_GROUP, NODE_CUSTOM_GROUP)) && node->id) {
1935       bNodeTree *ngroup = (bNodeTree *)node->id;
1936       ntreeFreeTree(ngroup);
1937       MEM_freeN(ngroup);
1938     }
1939   }
1940 }
1941
1942 /* Free (or release) any data used by this nodetree. Does not free the
1943  * nodetree itself and does no ID user counting. */
1944 void ntreeFreeTree(bNodeTree *ntree)
1945 {
1946   bNode *node, *next;
1947   bNodeSocket *sock, *nextsock;
1948
1949   BKE_animdata_free((ID *)ntree, false);
1950
1951   /* XXX hack! node trees should not store execution graphs at all.
1952    * This should be removed when old tree types no longer require it.
1953    * Currently the execution data for texture nodes remains in the tree
1954    * after execution, until the node tree is updated or freed.
1955    */
1956   if (ntree->execdata) {
1957     switch (ntree->type) {
1958       case NTREE_SHADER:
1959         ntreeShaderEndExecTree(ntree->execdata);
1960         break;
1961       case NTREE_TEXTURE:
1962         ntreeTexEndExecTree(ntree->execdata);
1963         ntree->execdata = NULL;
1964         break;
1965     }
1966   }
1967
1968   /* XXX not nice, but needed to free localized node groups properly */
1969   free_localized_node_groups(ntree);
1970
1971   /* unregister associated RNA types */
1972   ntreeInterfaceTypeFree(ntree);
1973
1974   BLI_freelistN(&ntree->links); /* do first, then unlink_node goes fast */
1975
1976   for (node = ntree->nodes.first; node; node = next) {
1977     next = node->next;
1978     node_free_node(ntree, node);
1979   }
1980
1981   /* free interface sockets */
1982   for (sock = ntree->inputs.first; sock; sock = nextsock) {
1983     nextsock = sock->next;
1984     node_socket_interface_free(ntree, sock);
1985     MEM_freeN(sock);
1986   }
1987   for (sock = ntree->outputs.first; sock; sock = nextsock) {
1988     nextsock = sock->next;
1989     node_socket_interface_free(ntree, sock);
1990     MEM_freeN(sock);
1991   }
1992
1993   /* free preview hash */
1994   if (ntree->previews) {
1995     BKE_node_instance_hash_free(ntree->previews, (bNodeInstanceValueFP)BKE_node_preview_free);
1996   }
1997
1998   if (ntree->duplilock) {
1999     BLI_mutex_free(ntree->duplilock);
2000   }
2001
2002   if (ntree->id.tag & LIB_TAG_LOCALIZED) {
2003     BKE_libblock_free_data(&ntree->id, true);
2004   }
2005 }
2006
2007 void ntreeFreeNestedTree(bNodeTree *ntree)
2008 {
2009   ntreeFreeTree(ntree);
2010   BKE_libblock_free_data(&ntree->id, true);
2011 }
2012
2013 void ntreeFreeLocalTree(bNodeTree *ntree)
2014 {
2015   if (ntree->id.tag & LIB_TAG_LOCALIZED) {
2016     ntreeFreeTree(ntree);
2017   }
2018   else {
2019     ntreeFreeTree(ntree);
2020     BKE_libblock_free_data(&ntree->id, true);
2021   }
2022 }
2023
2024 void ntreeFreeCache(bNodeTree *ntree)
2025 {
2026   if (ntree == NULL) {
2027     return;
2028   }
2029
2030   if (ntree->typeinfo->free_cache) {
2031     ntree->typeinfo->free_cache(ntree);
2032   }
2033 }
2034
2035 void ntreeSetOutput(bNodeTree *ntree)
2036 {
2037   bNode *node;
2038
2039   /* find the active outputs, might become tree type dependent handler */
2040   for (node = ntree->nodes.first; node; node = node->next) {
2041     if (node->typeinfo->nclass == NODE_CLASS_OUTPUT) {
2042       bNode *tnode;
2043       int output = 0;
2044
2045       /* we need a check for which output node should be tagged like this, below an exception */
2046       if (node->type == CMP_NODE_OUTPUT_FILE) {
2047         continue;
2048       }
2049
2050       /* there is more types having output class, each one is checked */
2051       for (tnode = ntree->nodes.first; tnode; tnode = tnode->next) {
2052         if (tnode->typeinfo->nclass == NODE_CLASS_OUTPUT) {
2053
2054           if (ntree->type == NTREE_COMPOSIT) {
2055
2056             /* same type, exception for viewer */
2057             if (tnode->type == node->type ||
2058                 (ELEM(tnode->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER) &&
2059                  ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER))) {
2060               if (tnode->flag & NODE_DO_OUTPUT) {
2061                 output++;
2062                 if (output > 1) {
2063                   tnode->flag &= ~NODE_DO_OUTPUT;
2064                 }
2065               }
2066             }
2067           }
2068           else {
2069             /* same type */
2070             if (tnode->type == node->type) {
2071               if (tnode->flag & NODE_DO_OUTPUT) {
2072                 output++;
2073                 if (output > 1) {
2074                   tnode->flag &= ~NODE_DO_OUTPUT;
2075                 }
2076               }
2077             }
2078           }
2079         }
2080       }
2081       if (output == 0) {
2082         node->flag |= NODE_DO_OUTPUT;
2083       }
2084     }
2085
2086     /* group node outputs use this flag too */
2087     if (node->type == NODE_GROUP_OUTPUT) {
2088       bNode *tnode;
2089       int output = 0;
2090
2091       for (tnode = ntree->nodes.first; tnode; tnode = tnode->next) {
2092         if (tnode->type == NODE_GROUP_OUTPUT) {
2093           if (tnode->flag & NODE_DO_OUTPUT) {
2094             output++;
2095             if (output > 1) {
2096               tnode->flag &= ~NODE_DO_OUTPUT;
2097             }
2098           }
2099         }
2100       }
2101       if (output == 0) {
2102         node->flag |= NODE_DO_OUTPUT;
2103       }
2104     }
2105   }
2106
2107   /* here we could recursively set which nodes have to be done,
2108    * might be different for editor or for "real" use... */
2109 }
2110
2111 bNodeTree *ntreeFromID(const ID *id)
2112 {
2113   switch (GS(id->name)) {
2114     case ID_MA:
2115       return ((const Material *)id)->nodetree;
2116     case ID_LA:
2117       return ((const Light *)id)->nodetree;
2118     case ID_WO:
2119       return ((const World *)id)->nodetree;
2120     case ID_TE:
2121       return ((const Tex *)id)->nodetree;
2122     case ID_SCE:
2123       return ((const Scene *)id)->nodetree;
2124     case ID_LS:
2125       return ((const FreestyleLineStyle *)id)->nodetree;
2126     default:
2127       return NULL;
2128   }
2129 }
2130
2131 void ntreeMakeLocal(Main *bmain, bNodeTree *ntree, bool id_in_mainlist, const bool lib_local)
2132 {
2133   BKE_id_make_local_generic(bmain, &ntree->id, id_in_mainlist, lib_local);
2134 }
2135
2136 int ntreeNodeExists(bNodeTree *ntree, bNode *testnode)
2137 {
2138   bNode *node = ntree->nodes.first;
2139   for (; node; node = node->next) {
2140     if (node == testnode) {
2141       return 1;
2142     }
2143   }
2144   return 0;
2145 }
2146
2147 int ntreeOutputExists(bNode *node, bNodeSocket *testsock)
2148 {
2149   bNodeSocket *sock = node->outputs.first;
2150   for (; sock; sock = sock->next) {
2151     if (sock == testsock) {
2152       return 1;
2153     }
2154   }
2155   return 0;
2156 }
2157
2158 void ntreeNodeFlagSet(const bNodeTree *ntree, const int flag, const bool enable)
2159 {
2160   bNode *node = ntree->nodes.first;
2161
2162   for (; node; node = node->next) {
2163     if (enable) {
2164       node->flag |= flag;
2165     }
2166     else {
2167       node->flag &= ~flag;
2168     }
2169   }
2170 }
2171
2172 /* returns localized tree for execution in threads */
2173 bNodeTree *ntreeLocalize(bNodeTree *ntree)
2174 {
2175   if (ntree) {
2176     bNodeTree *ltree;
2177     bNode *node;
2178
2179     BLI_spin_lock(&spin);
2180     if (!ntree->duplilock) {
2181       ntree->duplilock = BLI_mutex_alloc();
2182     }
2183     BLI_spin_unlock(&spin);
2184
2185     BLI_mutex_lock(ntree->duplilock);
2186
2187     /* Make full copy outside of Main database.
2188      * Note: previews are not copied here.
2189      */
2190     BKE_id_copy_ex(
2191         NULL, &ntree->id, (ID **)&ltree, (LIB_ID_COPY_LOCALIZE | LIB_ID_COPY_NO_ANIMDATA));
2192
2193     ltree->id.tag |= LIB_TAG_LOCALIZED;
2194
2195     for (node = ltree->nodes.first; node; node = node->next) {
2196       if ((ELEM(node->type, NODE_GROUP, NODE_CUSTOM_GROUP)) && node->id) {
2197         node->id = (ID *)ntreeLocalize((bNodeTree *)node->id);
2198       }
2199     }
2200
2201     /* ensures only a single output node is enabled */
2202     ntreeSetOutput(ntree);
2203
2204     for (node = ntree->nodes.first; node; node = node->next) {
2205       /* store new_node pointer to original */
2206       node->new_node->original = node;
2207     }
2208
2209     if (ntree->typeinfo->localize) {
2210       ntree->typeinfo->localize(ltree, ntree);
2211     }
2212
2213     BLI_mutex_unlock(ntree->duplilock);
2214
2215     return ltree;
2216   }
2217   else {
2218     return NULL;
2219   }
2220 }
2221
2222 /* sync local composite with real tree */
2223 /* local tree is supposed to be running, be careful moving previews! */
2224 /* is called by jobs manager, outside threads, so it doesn't happen during draw */
2225 void ntreeLocalSync(bNodeTree *localtree, bNodeTree *ntree)
2226 {
2227   if (localtree && ntree) {
2228     if (ntree->typeinfo->local_sync) {
2229       ntree->typeinfo->local_sync(localtree, ntree);
2230     }
2231   }
2232 }
2233
2234 /* merge local tree results back, and free local tree */
2235 /* we have to assume the editor already changed completely */
2236 void ntreeLocalMerge(Main *bmain, bNodeTree *localtree, bNodeTree *ntree)
2237 {
2238   if (ntree && localtree) {
2239     if (ntree->typeinfo->local_merge) {
2240       ntree->typeinfo->local_merge(bmain, localtree, ntree);
2241     }
2242
2243     ntreeFreeTree(localtree);
2244     MEM_freeN(localtree);
2245   }
2246 }
2247
2248 /* ************ NODE TREE INTERFACE *************** */
2249
2250 static bNodeSocket *make_socket_interface(bNodeTree *ntree,
2251                                           int in_out,
2252                                           const char *idname,
2253                                           const char *name)
2254 {
2255   bNodeSocketType *stype = nodeSocketTypeFind(idname);
2256   bNodeSocket *sock;
2257   int own_index = ntree->cur_index++;
2258
2259   if (stype == NULL) {
2260     return NULL;
2261   }
2262
2263   sock = MEM_callocN(sizeof(bNodeSocket), "socket template");
2264   BLI_strncpy(sock->idname, stype->idname, sizeof(sock->idname));
2265   node_socket_set_typeinfo(ntree, sock, stype);
2266   sock->in_out = in_out;
2267   sock->type = SOCK_CUSTOM; /* int type undefined by default */
2268
2269   /* assign new unique index */
2270   own_index = ntree->cur_index++;
2271   /* use the own_index as socket identifier */
2272   if (in_out == SOCK_IN) {
2273     BLI_snprintf(sock->identifier, MAX_NAME, "Input_%d", own_index);
2274   }
2275   else {
2276     BLI_snprintf(sock->identifier, MAX_NAME, "Output_%d", own_index);
2277   }
2278
2279   sock->limit = (in_out == SOCK_IN ? 1 : 0xFFF);
2280
2281   BLI_strncpy(sock->name, name, NODE_MAXSTR);
2282   sock->storage = NULL;
2283   sock->flag |= SOCK_COLLAPSED;
2284
2285   return sock;
2286 }
2287
2288 bNodeSocket *ntreeFindSocketInterface(bNodeTree *ntree, int in_out, const char *identifier)
2289 {
2290   bNodeSocket *iosock = (in_out == SOCK_IN ? ntree->inputs.first : ntree->outputs.first);
2291   for (; iosock; iosock = iosock->next) {
2292     if (STREQ(iosock->identifier, identifier)) {
2293       return iosock;
2294     }
2295   }
2296   return NULL;
2297 }
2298
2299 bNodeSocket *ntreeAddSocketInterface(bNodeTree *ntree,
2300                                      int in_out,
2301                                      const char *idname,
2302                                      const char *name)
2303 {
2304   bNodeSocket *iosock;
2305
2306   iosock = make_socket_interface(ntree, in_out, idname, name);
2307   if (in_out == SOCK_IN) {
2308     BLI_addtail(&ntree->inputs, iosock);
2309     ntree->update |= NTREE_UPDATE_GROUP_IN;
2310   }
2311   else if (in_out == SOCK_OUT) {
2312     BLI_addtail(&ntree->outputs, iosock);
2313     ntree->update |= NTREE_UPDATE_GROUP_OUT;
2314   }
2315
2316   return iosock;
2317 }
2318
2319 bNodeSocket *ntreeInsertSocketInterface(
2320     bNodeTree *ntree, int in_out, const char *idname, bNodeSocket *next_sock, const char *name)
2321 {
2322   bNodeSocket *iosock;
2323
2324   iosock = make_socket_interface(ntree, in_out, idname, name);
2325   if (in_out == SOCK_IN) {
2326     BLI_insertlinkbefore(&ntree->inputs, next_sock, iosock);
2327     ntree->update |= NTREE_UPDATE_GROUP_IN;
2328   }
2329   else if (in_out == SOCK_OUT) {
2330     BLI_insertlinkbefore(&ntree->outputs, next_sock, iosock);
2331     ntree->update |= NTREE_UPDATE_GROUP_OUT;
2332   }
2333
2334   return iosock;
2335 }
2336
2337 struct bNodeSocket *ntreeAddSocketInterfaceFromSocket(bNodeTree *ntree,
2338                                                       bNode *from_node,
2339                                                       bNodeSocket *from_sock)
2340 {
2341   bNodeSocket *iosock = ntreeAddSocketInterface(
2342       ntree, from_sock->in_out, from_sock->idname, from_sock->name);
2343   if (iosock) {
2344     if (iosock->typeinfo->interface_from_socket) {
2345       iosock->typeinfo->interface_from_socket(ntree, iosock, from_node, from_sock);
2346     }
2347   }
2348   return iosock;
2349 }
2350
2351 struct bNodeSocket *ntreeInsertSocketInterfaceFromSocket(bNodeTree *ntree,
2352                                                          bNodeSocket *next_sock,
2353                                                          bNode *from_node,
2354                                                          bNodeSocket *from_sock)
2355 {
2356   bNodeSocket *iosock = ntreeInsertSocketInterface(
2357       ntree, from_sock->in_out, from_sock->idname, next_sock, from_sock->name);
2358   if (iosock) {
2359     if (iosock->typeinfo->interface_from_socket) {
2360       iosock->typeinfo->interface_from_socket(ntree, iosock, from_node, from_sock);
2361     }
2362   }
2363   return iosock;
2364 }
2365
2366 void ntreeRemoveSocketInterface(bNodeTree *ntree, bNodeSocket *sock)
2367 {
2368   /* this is fast, this way we don't need an in_out argument */
2369   BLI_remlink(&ntree->inputs, sock);
2370   BLI_remlink(&ntree->outputs, sock);
2371
2372   node_socket_interface_free(ntree, sock);
2373   MEM_freeN(sock);
2374
2375   ntree->update |= NTREE_UPDATE_GROUP;
2376 }
2377
2378 /* generates a valid RNA identifier from the node tree name */
2379 static void ntree_interface_identifier_base(bNodeTree *ntree, char *base)
2380 {
2381   /* generate a valid RNA identifier */
2382   sprintf(base, "NodeTreeInterface_%s", ntree->id.name + 2);
2383   RNA_identifier_sanitize(base, false);
2384 }
2385
2386 /* check if the identifier is already in use */
2387 static bool ntree_interface_unique_identifier_check(void *UNUSED(data), const char *identifier)
2388 {
2389   return (RNA_struct_find(identifier) != NULL);
2390 }
2391
2392 /* generates the actual unique identifier and ui name and description */
2393 static void ntree_interface_identifier(bNodeTree *ntree,
2394                                        const char *base,
2395                                        char *identifier,
2396                                        int maxlen,
2397                                        char *name,
2398                                        char *description)
2399 {
2400   /* There is a possibility that different node tree names get mapped to the same identifier
2401    * after sanitization (e.g. "SomeGroup_A", "SomeGroup.A" both get sanitized to "SomeGroup_A").
2402    * On top of the sanitized id string add a number suffix if necessary to avoid duplicates.
2403    */
2404   identifier[0] = '\0';
2405   BLI_uniquename_cb(ntree_interface_unique_identifier_check, NULL, base, '_', identifier, maxlen);
2406
2407   sprintf(name, "Node Tree %s Interface", ntree->id.name + 2);
2408   sprintf(description, "Interface properties of node group %s", ntree->id.name + 2);
2409 }
2410
2411 static void ntree_interface_type_create(bNodeTree *ntree)
2412 {
2413   StructRNA *srna;
2414   bNodeSocket *sock;
2415   /* strings are generated from base string + ID name, sizes are sufficient */
2416   char base[MAX_ID_NAME + 64], identifier[MAX_ID_NAME + 64], name[MAX_ID_NAME + 64],
2417       description[MAX_ID_NAME + 64];
2418
2419   /* generate a valid RNA identifier */
2420   ntree_interface_identifier_base(ntree, base);
2421   ntree_interface_identifier(ntree, base, identifier, sizeof(identifier), name, description);
2422
2423   /* register a subtype of PropertyGroup */
2424   srna = RNA_def_struct_ptr(&BLENDER_RNA, identifier, &RNA_PropertyGroup);
2425   RNA_def_struct_ui_text(srna, name, description);
2426   RNA_def_struct_duplicate_pointers(&BLENDER_RNA, srna);
2427
2428   /* associate the RNA type with the node tree */
2429   ntree->interface_type = srna;
2430   RNA_struct_blender_type_set(srna, ntree);
2431
2432   /* add socket properties */
2433   for (sock = ntree->inputs.first; sock; sock = sock->next) {
2434     bNodeSocketType *stype = sock->typeinfo;
2435     if (stype && stype->interface_register_properties) {
2436       stype->interface_register_properties(ntree, sock, srna);
2437     }
2438   }
2439   for (sock = ntree->outputs.first; sock; sock = sock->next) {
2440     bNodeSocketType *stype = sock->typeinfo;
2441     if (stype && stype->interface_register_properties) {
2442       stype->interface_register_properties(ntree, sock, srna);
2443     }
2444   }
2445 }
2446
2447 StructRNA *ntreeInterfaceTypeGet(bNodeTree *ntree, int create)
2448 {
2449   if (ntree->interface_type) {
2450     /* strings are generated from base string + ID name, sizes are sufficient */
2451     char base[MAX_ID_NAME + 64], identifier[MAX_ID_NAME + 64], name[MAX_ID_NAME + 64],
2452         description[MAX_ID_NAME + 64];
2453
2454     /* A bit of a hack: when changing the ID name, update the RNA type identifier too,
2455      * so that the names match. This is not strictly necessary to keep it working,
2456      * but better for identifying associated NodeTree blocks and RNA types.
2457      */
2458     StructRNA *srna = ntree->interface_type;
2459
2460     ntree_interface_identifier_base(ntree, base);
2461
2462     /* RNA identifier may have a number suffix, but should start with the idbase string */
2463     if (!STREQLEN(RNA_struct_identifier(srna), base, sizeof(base))) {
2464       /* generate new unique RNA identifier from the ID name */
2465       ntree_interface_identifier(ntree, base, identifier, sizeof(identifier), name, description);
2466
2467       /* rename the RNA type */
2468       RNA_def_struct_free_pointers(&BLENDER_RNA, srna);
2469       RNA_def_struct_identifier(&BLENDER_RNA, srna, identifier);
2470       RNA_def_struct_ui_text(srna, name, description);
2471       RNA_def_struct_duplicate_pointers(&BLENDER_RNA, srna);
2472     }
2473   }
2474   else if (create) {
2475     ntree_interface_type_create(ntree);
2476   }
2477
2478   return ntree->interface_type;
2479 }
2480
2481 void ntreeInterfaceTypeFree(bNodeTree *ntree)
2482 {
2483   if (ntree->interface_type) {
2484     RNA_struct_free(&BLENDER_RNA, ntree->interface_type);
2485     ntree->interface_type = NULL;
2486   }
2487 }
2488
2489 void ntreeInterfaceTypeUpdate(bNodeTree *ntree)
2490 {
2491   /* XXX it would be sufficient to just recreate all properties
2492    * instead of re-registering the whole struct type,
2493    * but there is currently no good way to do this in the RNA functions.
2494    * Overhead should be negligible.
2495    */
2496   ntreeInterfaceTypeFree(ntree);
2497   ntree_interface_type_create(ntree);
2498 }
2499
2500 /* ************ find stuff *************** */
2501
2502 bNode *ntreeFindType(const bNodeTree *ntree, int type)
2503 {
2504   if (ntree) {
2505     for (bNode *node = ntree->nodes.first; node; node = node->next) {
2506       if (node->type == type) {
2507         return node;
2508       }
2509     }
2510   }
2511   return NULL;
2512 }
2513
2514 bool ntreeHasType(const bNodeTree *ntree, int type)
2515 {
2516   return ntreeFindType(ntree, type) != NULL;
2517 }
2518
2519 bool ntreeHasTree(const bNodeTree *ntree, const bNodeTree *lookup)
2520 {
2521   bNode *node;
2522
2523   if (ntree == lookup) {
2524     return true;
2525   }
2526
2527   for (node = ntree->nodes.first; node; node = node->next) {
2528     if (ELEM(node->type, NODE_GROUP, NODE_CUSTOM_GROUP) && node->id) {
2529       if (ntreeHasTree((bNodeTree *)node->id, lookup)) {
2530         return true;
2531       }
2532     }
2533   }
2534
2535   return false;
2536 }
2537
2538 bNodeLink *nodeFindLink(bNodeTree *ntree, bNodeSocket *from, bNodeSocket *to)
2539 {
2540   bNodeLink *link;
2541
2542   for (link = ntree->links.first; link; link = link->next) {
2543     if (link->fromsock == from && link->tosock == to) {
2544       return link;
2545     }
2546     if (link->fromsock == to && link->tosock == from) { /* hrms? */
2547       return link;
2548     }
2549   }
2550   return NULL;
2551 }
2552
2553 int nodeCountSocketLinks(bNodeTree *ntree, bNodeSocket *sock)
2554 {
2555   bNodeLink *link;
2556   int tot = 0;
2557
2558   for (link = ntree->links.first; link; link = link->next) {
2559     if (link->fromsock == sock || link->tosock == sock) {
2560       tot++;
2561     }
2562   }
2563   return tot;
2564 }
2565
2566 bNode *nodeGetActive(bNodeTree *ntree)
2567 {
2568   bNode *node;
2569
2570   if (ntree == NULL) {
2571     return NULL;
2572   }
2573
2574   for (node = ntree->nodes.first; node; node = node->next) {
2575     if (node->flag & NODE_ACTIVE) {
2576       break;
2577     }
2578   }
2579   return node;
2580 }
2581
2582 static bNode *node_get_active_id_recursive(bNodeInstanceKey active_key,
2583                                            bNodeInstanceKey parent_key,
2584                                            bNodeTree *ntree,
2585                                            short idtype)
2586 {
2587   if (parent_key.value == active_key.value || active_key.value == 0) {
2588     bNode *node;
2589     for (node = ntree->nodes.first; node; node = node->next) {
2590       if (node->id && GS(node->id->name) == idtype) {
2591         if (node->flag & NODE_ACTIVE_ID) {
2592           return node;
2593         }
2594       }
2595     }
2596   }
2597   else {
2598     bNode *node, *tnode;
2599     /* no node with active ID in this tree, look inside groups */
2600     for (node = ntree->nodes.first; node; node = node->next) {
2601       if (node->type == NODE_GROUP) {
2602         bNodeTree *group = (bNodeTree *)node->id;
2603         if (group) {
2604           bNodeInstanceKey group_key = BKE_node_instance_key(parent_key, ntree, node);
2605           tnode = node_get_active_id_recursive(active_key, group_key, group, idtype);
2606           if (tnode) {
2607             return tnode;
2608           }
2609         }
2610       }
2611     }
2612   }
2613
2614   return NULL;
2615 }
2616
2617 /* two active flags, ID nodes have special flag for buttons display */
2618 bNode *nodeGetActiveID(bNodeTree *ntree, short idtype)
2619 {
2620   if (ntree) {
2621     return node_get_active_id_recursive(
2622         ntree->active_viewer_key, NODE_INSTANCE_KEY_BASE, ntree, idtype);
2623   }
2624   else {
2625     return NULL;
2626   }
2627 }
2628
2629 bool nodeSetActiveID(bNodeTree *ntree, short idtype, ID *id)
2630 {
2631   bNode *node;
2632   bool ok = false;
2633
2634   if (ntree == NULL) {
2635     return ok;
2636   }
2637
2638   for (node = ntree->nodes.first; node; node = node->next) {
2639     if (node->id && GS(node->id->name) == idtype) {
2640       if (id && ok == false && node->id == id) {
2641         node->flag |= NODE_ACTIVE_ID;
2642         ok = true;
2643       }
2644       else {
2645         node->flag &= ~NODE_ACTIVE_ID;
2646       }
2647     }
2648   }
2649
2650   /* update all groups linked from here
2651    * if active ID node has been found already,
2652    * just pass NULL so other matching nodes are deactivated.
2653    */
2654   for (node = ntree->nodes.first; node; node = node->next) {
2655     if (node->type == NODE_GROUP) {
2656       ok |= nodeSetActiveID((bNodeTree *)node->id, idtype, (ok == false ? id : NULL));
2657     }
2658   }
2659
2660   return ok;
2661 }
2662
2663 /* two active flags, ID nodes have special flag for buttons display */
2664 void nodeClearActiveID(bNodeTree *ntree, short idtype)
2665 {
2666   bNode *node;
2667
2668   if (ntree == NULL) {
2669     return;
2670   }
2671
2672   for (node = ntree->nodes.first; node; node = node->next) {
2673     if (node->id && GS(node->id->name) == idtype) {
2674       node->flag &= ~NODE_ACTIVE_ID;
2675     }
2676   }
2677 }
2678
2679 void nodeSetSelected(bNode *node, bool select)
2680 {
2681   if (select) {
2682     node->flag |= NODE_SELECT;
2683   }
2684   else {
2685     bNodeSocket *sock;
2686
2687     node->flag &= ~NODE_SELECT;
2688
2689     /* deselect sockets too */
2690     for (sock = node->inputs.first; sock; sock = sock->next) {
2691       sock->flag &= ~NODE_SELECT;
2692     }
2693     for (sock = node->outputs.first; sock; sock = sock->next) {
2694       sock->flag &= ~NODE_SELECT;
2695     }
2696   }
2697 }
2698
2699 void nodeClearActive(bNodeTree *ntree)
2700 {
2701   bNode *node;
2702
2703   if (ntree == NULL) {
2704     return;
2705   }
2706
2707   for (node = ntree->nodes.first; node; node = node->next) {
2708     node->flag &= ~(NODE_ACTIVE | NODE_ACTIVE_ID);
2709   }
2710 }
2711
2712 /* two active flags, ID nodes have special flag for buttons display */
2713 void nodeSetActive(bNodeTree *ntree, bNode *node)
2714 {
2715   bNode *tnode;
2716
2717   /* make sure only one node is active, and only one per ID type */
2718   for (tnode = ntree->nodes.first; tnode; tnode = tnode->next) {
2719     tnode->flag &= ~NODE_ACTIVE;
2720
2721     if (node->id && tnode->id) {
2722       if (GS(node->id->name) == GS(tnode->id->name)) {
2723         tnode->flag &= ~NODE_ACTIVE_ID;
2724       }
2725     }
2726     if (node->typeinfo->nclass == NODE_CLASS_TEXTURE) {
2727       tnode->flag &= ~NODE_ACTIVE_TEXTURE;
2728     }
2729   }
2730
2731   node->flag |= NODE_ACTIVE;
2732   if (node->id) {
2733     node->flag |= NODE_ACTIVE_ID;
2734   }
2735   if (node->typeinfo->nclass == NODE_CLASS_TEXTURE) {
2736     node->flag |= NODE_ACTIVE_TEXTURE;
2737   }
2738 }
2739
2740 int nodeSocketIsHidden(bNodeSocket *sock)
2741 {
2742   return ((sock->flag & (SOCK_HIDDEN | SOCK_UNAVAIL)) != 0);
2743 }
2744
2745 /* ************** Node Clipboard *********** */
2746
2747 #define USE_NODE_CB_VALIDATE
2748
2749 #ifdef USE_NODE_CB_VALIDATE
2750 /**
2751  * This data structure is to validate the node on creation,
2752  * otherwise we may reference missing data.
2753  *
2754  * Currently its only used for ID's, but nodes may one day
2755  * reference other pointers which need validation.
2756  */
2757 typedef struct bNodeClipboardExtraInfo {
2758   struct bNodeClipboardExtraInfo *next, *prev;
2759   ID *id;
2760   char id_name[MAX_ID_NAME];
2761   char library_name[FILE_MAX];
2762 } bNodeClipboardExtraInfo;
2763 #endif /* USE_NODE_CB_VALIDATE */
2764
2765 typedef struct bNodeClipboard {
2766   ListBase nodes;
2767
2768 #ifdef USE_NODE_CB_VALIDATE
2769   ListBase nodes_extra_info;
2770 #endif
2771
2772   ListBase links;
2773   int type;
2774 } bNodeClipboard;
2775
2776 static bNodeClipboard node_clipboard = {{NULL}};
2777
2778 void BKE_node_clipboard_init(struct bNodeTree *ntree)
2779 {
2780   node_clipboard.type = ntree->type;
2781 }
2782
2783 void BKE_node_clipboard_clear(void)
2784 {
2785   bNode *node, *node_next;
2786   bNodeLink *link, *link_next;
2787
2788   for (link = node_clipboard.links.first; link; link = link_next) {
2789     link_next = link->next;
2790     nodeRemLink(NULL, link);
2791   }
2792   BLI_listbase_clear(&node_clipboard.links);
2793
2794   for (node = node_clipboard.nodes.first; node; node = node_next) {
2795     node_next = node->next;
2796     node_free_node(NULL, node);
2797   }
2798   BLI_listbase_clear(&node_clipboard.nodes);
2799
2800 #ifdef USE_NODE_CB_VALIDATE
2801   BLI_freelistN(&node_clipboard.nodes_extra_info);
2802 #endif
2803 }
2804
2805 /* return false when one or more ID's are lost */
2806 bool BKE_node_clipboard_validate(void)
2807 {
2808   bool ok = true;
2809
2810 #ifdef USE_NODE_CB_VALIDATE
2811   bNodeClipboardExtraInfo *node_info;
2812   bNode *node;
2813
2814   /* lists must be aligned */
2815   BLI_assert(BLI_listbase_count(&node_clipboard.nodes) ==
2816              BLI_listbase_count(&node_clipboard.nodes_extra_info));
2817
2818   for (node = node_clipboard.nodes.first, node_info = node_clipboard.nodes_extra_info.first; node;
2819        node = node->next, node_info = node_info->next) {
2820     /* validate the node against the stored node info */
2821
2822     /* re-assign each loop since we may clear,
2823      * open a new file where the ID is valid, and paste again */
2824     node->id = node_info->id;
2825
2826     /* currently only validate the ID */
2827     if (node->id) {
2828       /* We want to search into current blend file, so using G_MAIN is valid here too. */
2829       ListBase *lb = which_libbase(G_MAIN, GS(node_info->id_name));
2830       BLI_assert(lb != NULL);
2831
2832       if (BLI_findindex(lb, node_info->id) == -1) {
2833         /* may assign NULL */
2834         node->id = BLI_findstring(lb, node_info->id_name + 2, offsetof(ID, name) + 2);
2835
2836         if (node->id == NULL) {
2837           ok = false;
2838         }
2839       }
2840     }
2841   }
2842 #endif /* USE_NODE_CB_VALIDATE */
2843
2844   return ok;
2845 }
2846
2847 void BKE_node_clipboard_add_node(bNode *node)
2848 {
2849 #ifdef USE_NODE_CB_VALIDATE
2850   /* add extra info */
2851   bNodeClipboardExtraInfo *node_info = MEM_mallocN(sizeof(bNodeClipboardExtraInfo),
2852                                                    "bNodeClipboardExtraInfo");
2853
2854   node_info->id = node->id;
2855   if (node->id) {
2856     BLI_strncpy(node_info->id_name, node->id->name, sizeof(node_info->id_name));
2857     if (ID_IS_LINKED(node->id)) {
2858       BLI_strncpy(
2859           node_info->library_name, node->id->lib->filepath, sizeof(node_info->library_name));
2860     }
2861     else {
2862       node_info->library_name[0] = '\0';
2863     }
2864   }
2865   else {
2866     node_info->id_name[0] = '\0';
2867     node_info->library_name[0] = '\0';
2868   }
2869   BLI_addtail(&node_clipboard.nodes_extra_info, node_info);
2870   /* end extra info */
2871 #endif /* USE_NODE_CB_VALIDATE */
2872
2873   /* add node */
2874   BLI_addtail(&node_clipboard.nodes, node);
2875 }
2876
2877 void BKE_node_clipboard_add_link(bNodeLink *link)
2878 {
2879   BLI_addtail(&node_clipboard.links, link);
2880 }
2881
2882 const ListBase *BKE_node_clipboard_get_nodes(void)
2883 {
2884   return &node_clipboard.nodes;
2885 }
2886
2887 const ListBase *BKE_node_clipboard_get_links(void)
2888 {
2889   return &node_clipboard.links;
2890 }
2891
2892 int BKE_node_clipboard_get_type(void)
2893 {
2894   return node_clipboard.type;
2895 }
2896
2897 void BKE_node_clipboard_free(void)
2898 {
2899   BKE_node_clipboard_validate();
2900   BKE_node_clipboard_clear();
2901 }
2902
2903 /* Node Instance Hash */
2904
2905 /* magic number for initial hash key */
2906 const bNodeInstanceKey NODE_INSTANCE_KEY_BASE = {5381};
2907 const bNodeInstanceKey NODE_INSTANCE_KEY_NONE = {0};
2908
2909 /* Generate a hash key from ntree and node names
2910  * Uses the djb2 algorithm with xor by Bernstein:
2911  * http://www.cse.yorku.ca/~oz/hash.html
2912  */
2913 static bNodeInstanceKey node_hash_int_str(bNodeInstanceKey hash, const char *str)
2914 {
2915   char c;
2916
2917   while ((c = *str++)) {
2918     hash.value = ((hash.value << 5) + hash.value) ^ c; /* (hash * 33) ^ c */
2919   }
2920
2921   /* separator '\0' character, to avoid ambiguity from concatenated strings */
2922   hash.value = (hash.value << 5) + hash.value; /* hash * 33 */
2923
2924   return hash;
2925 }
2926
2927 bNodeInstanceKey BKE_node_instance_key(bNodeInstanceKey parent_key, bNodeTree *ntree, bNode *node)
2928 {
2929   bNodeInstanceKey key;
2930
2931   key = node_hash_int_str(parent_key, ntree->id.name + 2);
2932
2933   if (node) {
2934     key = node_hash_int_str(key, node->name);
2935   }
2936
2937   return key;
2938 }
2939
2940 static unsigned int node_instance_hash_key(const void *key)
2941 {
2942   return ((const bNodeInstanceKey *)key)->value;
2943 }
2944
2945 static bool node_instance_hash_key_cmp(const void *a, const void *b)
2946 {
2947   unsigned int value_a = ((const bNodeInstanceKey *)a)->value;
2948   unsigned int value_b = ((const bNodeInstanceKey *)b)->value;
2949
2950   return (value_a != value_b);
2951 }
2952
2953 bNodeInstanceHash *BKE_node_instance_hash_new(const char *info)
2954 {
2955   bNodeInstanceHash *hash = MEM_mallocN(sizeof(bNodeInstanceHash), info);
2956   hash->ghash = BLI_ghash_new(
2957       node_instance_hash_key, node_instance_hash_key_cmp, "node instance hash ghash");
2958   return hash;
2959 }
2960
2961 void BKE_node_instance_hash_free(bNodeInstanceHash *hash, bNodeInstanceValueFP valfreefp)
2962 {
2963   BLI_ghash_free(hash->ghash, NULL, (GHashValFreeFP)valfreefp);
2964   MEM_freeN(hash);
2965 }
2966
2967 void BKE_node_instance_hash_insert(bNodeInstanceHash *hash, bNodeInstanceKey key, void *value)
2968 {
2969   bNodeInstanceHashEntry *entry = value;
2970   entry->key = key;
2971   entry->tag = 0;
2972   BLI_ghash_insert(hash->ghash, &entry->key, value);
2973 }
2974
2975 void *BKE_node_instance_hash_lookup(bNodeInstanceHash *hash, bNodeInstanceKey key)
2976 {
2977   return BLI_ghash_lookup(hash->ghash, &key);
2978 }
2979
2980 int BKE_node_instance_hash_remove(bNodeInstanceHash *hash,
2981                                   bNodeInstanceKey key,
2982                                   bNodeInstanceValueFP valfreefp)
2983 {
2984   return BLI_ghash_remove(hash->ghash, &key, NULL, (GHashValFreeFP)valfreefp);
2985 }
2986
2987 void BKE_node_instance_hash_clear(bNodeInstanceHash *hash, bNodeInstanceValueFP valfreefp)
2988 {
2989   BLI_ghash_clear(hash->ghash, NULL, (GHashValFreeFP)valfreefp);
2990 }
2991
2992 void *BKE_node_instance_hash_pop(bNodeInstanceHash *hash, bNodeInstanceKey key)
2993 {
2994   return BLI_ghash_popkey(hash->ghash, &key, NULL);
2995 }
2996
2997 int BKE_node_instance_hash_haskey(bNodeInstanceHash *hash, bNodeInstanceKey key)
2998 {
2999   return BLI_ghash_haskey(hash->ghash, &key);
3000 }
3001
3002 int BKE_node_instance_hash_size(bNodeInstanceHash *hash)
3003 {
3004   return BLI_ghash_len(hash->ghash);
3005 }
3006
3007 void BKE_node_instance_hash_clear_tags(bNodeInstanceHash *hash)
3008 {
3009   bNodeInstanceHashIterator iter;
3010
3011   NODE_INSTANCE_HASH_ITER (iter, hash) {
3012     bNodeInstanceHashEntry *value = BKE_node_instance_hash_iterator_get_value(&iter);
3013
3014     value->tag = 0;
3015   }
3016 }
3017
3018 void BKE_node_instance_hash_tag(bNodeInstanceHash *UNUSED(hash), void *value)
3019 {
3020   bNodeInstanceHashEntry *entry = value;
3021   entry->tag = 1;
3022 }
3023
3024 bool BKE_node_instance_hash_tag_key(bNodeInstanceHash *hash, bNodeInstanceKey key)
3025 {
3026   bNodeInstanceHashEntry *entry = BKE_node_instance_hash_lookup(hash, key);
3027
3028   if (entry) {
3029     entry->tag = 1;
3030     return true;
3031   }
3032   else {
3033     return false;
3034   }
3035 }
3036
3037 void BKE_node_instance_hash_remove_untagged(bNodeInstanceHash *hash,
3038                                             bNodeInstanceValueFP valfreefp)
3039 {
3040   /* NOTE: Hash must not be mutated during iterating!
3041    * Store tagged entries in a separate list and remove items afterward.
3042    */
3043   bNodeInstanceKey *untagged = MEM_mallocN(sizeof(bNodeInstanceKey) *
3044                                                BKE_node_instance_hash_size(hash),
3045                                            "temporary node instance key list");
3046   bNodeInstanceHashIterator iter;
3047   int num_untagged, i;
3048
3049   num_untagged = 0;
3050   NODE_INSTANCE_HASH_ITER (iter, hash) {
3051     bNodeInstanceHashEntry *value = BKE_node_instance_hash_iterator_get_value(&iter);
3052
3053     if (!value->tag) {
3054       untagged[num_untagged++] = BKE_node_instance_hash_iterator_get_key(&iter);
3055     }
3056   }
3057
3058   for (i = 0; i < num_untagged; ++i) {
3059     BKE_node_instance_hash_remove(hash, untagged[i], valfreefp);
3060   }
3061
3062   MEM_freeN(untagged);
3063 }
3064
3065 /* ************** dependency stuff *********** */
3066
3067 /* node is guaranteed to be not checked before */
3068 static int node_get_deplist_recurs(bNodeTree *ntree, bNode *node, bNode ***nsort)
3069 {
3070   bNode *fromnode;
3071   bNodeLink *link;
3072   int level = 0xFFF;
3073
3074   node->done = true;
3075
3076   /* check linked nodes */
3077   for (link = ntree->links.first; link; link = link->next) {
3078     if (link->tonode == node) {
3079       fromnode = link->fromnode;
3080       if (fromnode->done == 0) {
3081         fromnode->level = node_get_deplist_recurs(ntree, fromnode, nsort);
3082       }
3083       if (fromnode->level <= level) {
3084         level = fromnode->level - 1;
3085       }
3086     }
3087   }
3088
3089   /* check parent node */
3090   if (node->parent) {
3091     if (node->parent->done == 0) {
3092       node->parent->level = node_get_deplist_recurs(ntree, node->parent, nsort);
3093     }
3094     if (node->parent->level <= level) {
3095       level = node->parent->level - 1;
3096     }
3097   }
3098
3099   if (nsort) {
3100     **nsort = node;
3101     (*nsort)++;
3102   }
3103
3104   return level;
3105 }
3106
3107 void ntreeGetDependencyList(struct bNodeTree *ntree, struct bNode ***deplist, int *totnodes)
3108 {
3109   bNode *node, **nsort;
3110
3111   *totnodes = 0;
3112
3113   /* first clear data */
3114   for (node = ntree->nodes.first; node; node = node->next) {
3115     node->done = false;
3116     (*totnodes)++;
3117   }
3118   if (*totnodes == 0) {
3119     *deplist = NULL;
3120     return;
3121   }
3122
3123   nsort = *deplist = MEM_callocN((*totnodes) * sizeof(bNode *), "sorted node array");
3124
3125   /* recursive check */
3126   for (node = ntree->nodes.first; node; node = node->next) {
3127     if (node->done == 0) {
3128       node->level = node_get_deplist_recurs(ntree, node, &nsort);
3129     }
3130   }
3131 }
3132
3133 /* only updates node->level for detecting cycles links */
3134 static void ntree_update_node_level(bNodeTree *ntree)
3135 {
3136   bNode *node;
3137
3138   /* first clear tag */
3139   for (node = ntree->nodes.first; node; node = node->next) {
3140     node->done = false;
3141   }
3142
3143   /* recursive check */
3144   for (node = ntree->nodes.first; node; node = node->next) {
3145     if (node->done == 0) {
3146       node->level = node_get_deplist_recurs(ntree, node, NULL);
3147     }
3148   }
3149 }
3150
3151 void ntreeTagUsedSockets(bNodeTree *ntree)
3152 {
3153   bNode *node;
3154   bNodeSocket *sock;
3155   bNodeLink *link;
3156
3157   /* first clear data */
3158   for (node = ntree->nodes.first; node; node = node->next) {
3159     for (sock = node->inputs.first; sock; sock = sock->next) {
3160       sock->flag &= ~SOCK_IN_USE;
3161     }
3162     for (sock = node->outputs.first; sock; sock = sock->next) {
3163       sock->flag &= ~SOCK_IN_USE;
3164     }
3165   }
3166
3167   for (link = ntree->links.first; link; link = link->next) {
3168     /* link is unused if either side is disabled */
3169     if ((link->fromsock->flag & SOCK_UNAVAIL) || (link->tosock->flag & SOCK_UNAVAIL)) {
3170       continue;
3171     }
3172
3173     link->fromsock->flag |= SOCK_IN_USE;
3174     link->tosock->flag |= SOCK_IN_USE;
3175   }
3176 }
3177
3178 static void ntree_update_link_pointers(bNodeTree *ntree)
3179 {
3180   bNode *node;
3181   bNodeSocket *sock;
3182   bNodeLink *link;
3183
3184   /* first clear data */
3185   for (node = ntree->nodes.first; node; node = node->next) {
3186     for (sock = node->inputs.first; sock; sock = sock->next) {
3187       sock->link = NULL;
3188     }
3189   }
3190
3191   for (link = ntree->links.first; link; link = link->next) {
3192     link->tosock->link = link;
3193   }
3194
3195   ntreeTagUsedSockets(ntree);
3196 }
3197
3198 static void ntree_validate_links(bNodeTree *ntree)
3199 {
3200   bNodeLink *link;
3201
3202   for (link = ntree->links.first; link; link = link->next) {
3203     link->flag |= NODE_LINK_VALID;
3204     if (link->fromnode && link->tonode && link->fromnode->level <= link->tonode->level) {
3205       link->flag &= ~NODE_LINK_VALID;
3206     }
3207     else if (ntree->typeinfo->validate_link) {
3208       if (!ntree->typeinfo->validate_link(ntree, link)) {
3209         link->flag &= ~NODE_LINK_VALID;
3210       }
3211     }
3212   }
3213 }
3214
3215 void ntreeUpdateAllNew(Main *main)
3216 {
3217   /* Update all new node trees on file read or append, to add/remove sockets
3218    * in groups nodes if the group changed, and handle any update flags that
3219    * might have been set in file reading or versioning. */
3220   FOREACH_NODETREE_BEGIN (main, ntree, owner_id) {
3221     if (owner_id->tag & LIB_TAG_NEW) {
3222       for (bNode *node = ntree->nodes.first; node; node = node->next) {
3223         if (node->typeinfo->group_update_func) {
3224           node->typeinfo->group_update_func(ntree, node);
3225         }
3226       }
3227
3228       ntreeUpdateTree(NULL, ntree);
3229     }
3230   }
3231   FOREACH_NODETREE_END;
3232 }
3233
3234 void ntreeUpdateAllUsers(Main *main, ID *ngroup)
3235 {
3236   /* Update all users of ngroup, to add/remove sockets as needed. */
3237   FOREACH_NODETREE_BEGIN (main, ntree, owner_id) {
3238     bool need_update = false;
3239
3240     for (bNode *node = ntree->nodes.first; node; node = node->next) {
3241       if (node->id == ngroup) {
3242         if (node->typeinfo->group_update_func) {
3243           node->typeinfo->group_update_func(ntree, node);
3244         }
3245
3246         need_update = true;
3247       }
3248     }
3249
3250     if (need_update) {
3251       ntreeUpdateTree(NULL, ntree);
3252     }
3253   }
3254   FOREACH_NODETREE_END;
3255 }
3256
3257 void ntreeUpdateTree(Main *bmain, bNodeTree *ntree)
3258 {
3259   bNode *node;
3260
3261   if (!ntree) {
3262     return;
3263   }
3264
3265   /* avoid reentrant updates, can be caused by RNA update callbacks */
3266   if (ntree->is_updating) {
3267     return;
3268   }
3269   ntree->is_updating = true;
3270
3271   if (ntree->update & (NTREE_UPDATE_LINKS | NTREE_UPDATE_NODES)) {
3272     /* set the bNodeSocket->link pointers */
3273     ntree_update_link_pointers(ntree);
3274   }
3275
3276   /* update individual nodes */
3277   for (node = ntree->nodes.first; node; node = node->next) {
3278     /* node tree update tags override individual node update flags */
3279     if ((node->update & NODE_UPDATE) || (ntree->update & NTREE_UPDATE)) {
3280       if (node->typeinfo->updatefunc) {
3281         node->typeinfo->updatefunc(ntree, node);
3282       }
3283
3284       nodeUpdateInternalLinks(ntree, node);
3285     }
3286   }
3287
3288   /* generic tree update callback */
3289   if (ntree->typeinfo->update) {
3290     ntree->typeinfo->update(ntree);
3291   }
3292   /* XXX this should be moved into the tree type update callback for tree supporting node groups.
3293    * Currently the node tree interface is still a generic feature of the base NodeTree type.
3294    */
3295   if (ntree->update & NTREE_UPDATE_GROUP) {
3296     ntreeInterfaceTypeUpdate(ntree);
3297   }
3298
3299   /* XXX hack, should be done by depsgraph!! */
3300   if (bmain) {
3301     ntreeUpdateAllUsers(bmain, &ntree->id);
3302   }
3303
3304   if (ntree->update & (NTREE_UPDATE_LINKS | NTREE_UPDATE_NODES)) {
3305     /* node updates can change sockets or links, repeat link pointer update afterward */
3306     ntree_update_link_pointers(ntree);
3307
3308     /* update the node level from link dependencies */
3309     ntree_update_node_level(ntree);
3310
3311     /* check link validity */
3312     ntree_validate_links(ntree);
3313   }
3314
3315   /* clear update flags */
3316   for (node = ntree->nodes.first; node; node = node->next) {
3317     node->update = 0;
3318   }
3319   ntree->update = 0;
3320
3321   ntree->is_updating = false;
3322 }
3323
3324 void nodeUpdate(bNodeTree *ntree, bNode *node)
3325 {
3326   /* avoid reentrant updates, can be caused by RNA update callbacks */
3327   if (ntree->is_updating) {
3328     return;
3329   }
3330   ntree->is_updating = true;
3331
3332   if (node->typeinfo->updatefunc) {
3333     node->typeinfo->updatefunc(ntree, node);
3334   }
3335
3336   nodeUpdateInternalLinks(ntree, node);
3337
3338   /* clear update flag */
3339   node->update = 0;
3340
3341   ntree->is_updating = false;
3342 }
3343
3344 bool nodeUpdateID(bNodeTree *ntree, ID *id)
3345 {
3346   bNode *node;
3347   bool changed = false;
3348
3349   if (ELEM(NULL, id, ntree)) {
3350     return changed;
3351   }
3352
3353   /* avoid reentrant updates, can be caused by RNA update callbacks */
3354   if (ntree->is_updating) {
3355     return changed;
3356   }
3357   ntree->is_updating = true;
3358
3359   for (node = ntree->nodes.first; node; node = node->next) {
3360     if (node->id == id) {
3361       changed = true;
3362       node->update |= NODE_UPDATE_ID;
3363       if (node->typeinfo->updatefunc) {
3364         node->typeinfo->updatefunc(ntree, node);
3365       }
3366       /* clear update flag */
3367       node->update = 0;
3368     }
3369   }
3370
3371   for (node = ntree->nodes.first; node; node = node->next) {
3372     nodeUpdateInternalLinks(ntree, node);
3373   }
3374
3375   ntree->is_updating = false;
3376   return changed;
3377 }
3378
3379 void nodeUpdateInternalLinks(bNodeTree *ntree, bNode *node)
3380 {
3381   BLI_freelistN(&node->internal_links);
3382
3383   if (node->typeinfo && node->typeinfo->update_internal_links) {
3384     node->typeinfo->update_internal_links(ntree, node);
3385   }
3386 }
3387
3388 /* ************* node type access ********** */
3389
3390 void nodeLabel(bNodeTree *ntree, bNode *node, char *label, int maxlen)
3391 {
3392   label[0] = '\0';
3393
3394   if (node->label[0] != '\0') {
3395     BLI_strncpy(label, node->label, maxlen);
3396   }
3397   else if (node->typeinfo->labelfunc) {
3398     node->typeinfo->labelfunc(ntree, node, label, maxlen);
3399   }
3400
3401   /* The previous methods (labelfunc) could not provide an adequate label for the node. */
3402   if (label[0] == '\0') {
3403     /* Kind of hacky and weak... Ideally would be better to use RNA here. :| */
3404     const char *tmp = CTX_IFACE_(BLT_I18NCONTEXT_ID_NODETREE, node->typeinfo->ui_name);
3405     if (tmp == node->typeinfo->ui_name) {
3406       tmp = IFACE_(node->typeinfo->ui_name);
3407     }
3408     BLI_strncpy(label, tmp, maxlen);
3409   }
3410 }
3411
3412 static void node_type_base_defaults(bNodeType *ntype)
3413 {
3414   /* default size values */
3415   node_type_size_preset(ntype, NODE_SIZE_DEFAULT);
3416   ntype->height = 100;
3417   ntype->minheight = 30;
3418   ntype->maxheight = FLT_MAX;
3419 }
3420
3421 /* allow this node for any tree type */
3422 static bool node_poll_default(bNodeType *UNUSED(ntype), bNodeTree *UNUSED(ntree))
3423 {
3424   return true;
3425 }
3426
3427 /* use the basic poll function */
3428 static bool node_poll_instance_default(bNode *node, bNodeTree *ntree)
3429 {
3430   return node->typeinfo->poll(node->typeinfo, ntree);
3431 }
3432
3433 void node_type_base(bNodeType *ntype, int type, const char *name, short nclass, short flag)
3434 {
3435   /* Use static type info header to map static int type to identifier string and RNA struct type.
3436    * Associate the RNA struct type with the bNodeType.
3437    * Dynamically registered nodes will create an RNA type at runtime
3438    * and call RNA_struct_blender_type_set, so this only needs to be done for old RNA types
3439    * created in makesrna, which can not be associated to a bNodeType immediately,
3440    * since bNodeTypes are registered afterward ...
3441    */
3442 #define DefNode(Category, ID, DefFunc, EnumName, StructName, UIName, UIDesc) \
3443   case ID: \
3444     BLI_strncpy(ntype->idname, #Category #StructName, sizeof(ntype->idname)); \
3445     ntype->ext.srna = RNA_struct_find(#Category #StructName); \
3446     BLI_assert(ntype->ext.srna != NULL); \
3447     RNA_struct_blender_type_set(ntype->ext.srna, ntype); \
3448     break;
3449
3450   switch (type) {
3451 #include "NOD_static_types.h"
3452   }
3453
3454   /* make sure we have a valid type (everything registered) */
3455   BLI_assert(ntype->idname[0] != '\0');
3456
3457   ntype->type = type;
3458   BLI_strncpy(ntype->ui_name, name, sizeof(ntype->ui_name));
3459   ntype->nclass = nclass;
3460   ntype->flag = flag;
3461
3462   node_type_base_defaults(ntype);
3463
3464   ntype->poll = node_poll_default;
3465   ntype->poll_instance = node_poll_instance_default;
3466 }
3467
3468 void node_type_base_custom(
3469     bNodeType *ntype, const char *idname, const char *name, short nclass, short flag)
3470 {
3471   BLI_strncpy(ntype->idname, idname, sizeof(ntype->idname));
3472   ntype->type = NODE_CUSTOM;
3473   BLI_strncpy(ntype->ui_name, name, sizeof(ntype->ui_name));
3474   ntype->nclass = nclass;
3475   ntype->flag = flag;
3476
3477   node_type_base_defaults(ntype);
3478 }
3479
3480 static bool unique_socket_template_identifier_check(void *arg, const char *name)
3481 {
3482   bNodeSocketTemplate *ntemp;
3483   struct {
3484     bNodeSocketTemplate *list;
3485     bNodeSocketTemplate *ntemp;
3486   } *data = arg;
3487
3488   for (ntemp = data->list; ntemp->type >= 0; ++ntemp) {
3489     if (ntemp != data->ntemp) {
3490       if (STREQ(ntemp->identifier, name)) {
3491         return true;
3492       }
3493     }
3494   }
3495
3496   return false;
3497 }
3498
3499 static void unique_socket_template_identifier(bNodeSocketTemplate *list,
3500                                               bNodeSocketTemplate *ntemp,
3501                                               const char defname[],
3502                                               char delim)
3503 {
3504   struct {
3505     bNodeSocketTemplate *list;
3506     bNodeSocketTemplate *ntemp;
3507   } data;
3508   data.list = list;
3509   data.ntemp = ntemp;
3510
3511   BLI_uniquename_cb(unique_socket_template_identifier_check,
3512                     &data,
3513                     defname,
3514                     delim,
3515                     ntemp->identifier,
3516                     sizeof(ntemp->identifier));
3517 }
3518
3519 void node_type_socket_templates(struct bNodeType *ntype,
3520                                 struct bNodeSocketTemplate *inputs,
3521                                 struct bNodeSocketTemplate *outputs)
3522 {
3523   bNodeSocketTemplate *ntemp;
3524
3525   ntype->inputs = inputs;
3526   ntype->outputs = outputs;
3527
3528   /* automatically generate unique identifiers */
3529   if (inputs) {
3530     /* clear identifier strings (uninitialized memory) */
3531     for (ntemp = inputs; ntemp->type >= 0; ++ntemp) {
3532       ntemp->identifier[0] = '\0';
3533     }
3534
3535     for (ntemp = inputs; ntemp->type >= 0; ++ntemp) {
3536       BLI_strncpy(ntemp->identifier, ntemp->name, sizeof(ntemp->identifier));
3537       unique_socket_template_identifier(inputs, ntemp, ntemp->identifier, '_');
3538     }
3539   }
3540   if (outputs) {
3541     /* clear identifier strings (uninitialized memory) */
3542     for (ntemp = outputs; ntemp->type >= 0; ++ntemp) {
3543       ntemp->identifier[0] = '\0';
3544     }
3545
3546     for (ntemp = outputs; ntemp->type >= 0; ++ntemp) {
3547       BLI_strncpy(ntemp->identifier, ntemp->name, sizeof(ntemp->identifier));
3548       unique_socket_template_identifier(outputs, ntemp, ntemp->identifier, '_');
3549     }
3550   }
3551 }
3552
3553 void node_type_init(struct bNodeType *ntype,
3554                     void (*initfunc)(struct bNodeTree *ntree, struct bNode *node))
3555 {
3556   ntype->initfunc = initfunc;
3557 }
3558
3559 void node_type_size(struct bNodeType *ntype, int width, int minwidth, int maxwidth)
3560 {
3561   ntype->width = width;
3562   ntype->minwidth = minwidth;
3563   if (maxwidth <= minwidth) {
3564     ntype->maxwidth = FLT_MAX;
3565   }
3566   else {
3567     ntype->maxwidth = maxwidth;
3568   }
3569 }
3570
3571 void node_type_size_preset(struct bNodeType *ntype, eNodeSizePreset size)
3572 {
3573   switch (size) {
3574     case NODE_SIZE_DEFAULT:
3575       node_type_size(ntype, 140, 100, NODE_DEFAULT_MAX_WIDTH);
3576       break;
3577     case NODE_SIZE_SMALL:
3578       node_type_size(ntype, 100, 80, NODE_DEFAULT_MAX_WIDTH);
3579       break;
3580     case NODE_SIZE_MIDDLE:
3581       node_type_size(ntype, 150, 120, NODE_DEFAULT_MAX_WIDTH);
3582       break;
3583     case NODE_SIZE_LARGE:
3584       node_type_size(ntype, 240, 140, NODE_DEFAULT_MAX_WIDTH);
3585       break;
3586   }
3587 }
3588
3589 /**
3590  * \warning Nodes defining a storage type _must_ allocate this for new nodes.
3591  * Otherwise nodes will reload as undefined (T46619).
3592  */
3593 void node_type_storage(bNodeType *ntype,
3594                        const char *storagename,
3595                        void (*freefunc)(struct bNode *node),
3596                        void (*copyfunc)(struct bNodeTree *dest_ntree,
3597                                         struct bNode *dest_node,
3598                                         struct bNode *src_node))
3599 {
3600   if (storagename) {
3601     BLI_strncpy(ntype->storagename, storagename, sizeof(ntype->storagename));
3602   }
3603   else {
3604     ntype->storagename[0] = '\0';
3605   }
3606   ntype->copyfunc = copyfunc;
3607   ntype->freefunc = freefunc;
3608 }
3609
3610 void node_type_label(
3611     struct bNodeType *ntype,
3612     void (*labelfunc)(struct bNodeTree *ntree, struct bNode *node, char *label, int maxlen))
3613 {
3614   ntype->labelfunc = labelfunc;
3615 }
3616
3617 void node_type_update(struct bNodeType *ntype,
3618                       void (*updatefunc)(struct bNodeTree *ntree, struct bNode *node))
3619 {
3620   ntype->updatefunc = updatefunc;
3621 }
3622
3623 void node_type_group_update(struct bNodeType *ntype,
3624                             void (*group_update_func)(struct bNodeTree *ntree, struct bNode *node))
3625 {
3626   ntype->group_update_func = group_update_func;
3627 }
3628
3629 void node_type_exec(struct bNodeType *ntype,
3630                     NodeInitExecFunction initexecfunc,
3631                     NodeFreeExecFunction freeexecfunc,
3632                     NodeExecFunction execfunc)
3633 {
3634   ntype->initexecfunc = initexecfunc;
3635   ntype->freeexecfunc = freeexecfunc;
3636   ntype->execfunc = execfunc;
3637 }
3638
3639 void node_type_gpu(struct bNodeType *ntype, NodeGPUExecFunction gpufunc)
3640 {
3641   ntype->gpufunc = gpufunc;
3642 }
3643
3644 void node_type_internal_links(bNodeType *ntype,
3645                               void (*update_internal_links)(bNodeTree *, bNode *))
3646 {
3647   ntype->update_internal_links = update_internal_links;
3648 }
3649
3650 /* callbacks for undefined types */
3651
3652 static bool node_undefined_poll(bNodeType *UNUSED(ntype), bNodeTree *UNUSED(nodetree))
3653 {
3654   /* this type can not be added deliberately, it's just a placeholder */
3655   return false;
3656 }
3657
3658 /* register fallback types used for undefined tree, nodes, sockets */
3659 static void register_undefined_types(void)
3660 {
3661   /* Note: these types are not registered in the type hashes,
3662    * they are just used as placeholders in case the actual types are not registered.
3663    */
3664
3665   strcpy(NodeTreeTypeUndefined.idname, "NodeTreeUndefined");
3666   strcpy(NodeTreeTypeUndefined.ui_name, N_("Undefined"));
3667   strcpy(NodeTreeTypeUndefined.ui_description, N_("Undefined Node Tree Type"));
3668
3669   node_type_base_custom(&NodeTypeUndefined, "NodeUndefined", "Undefined", 0, 0);
3670   NodeTypeUndefined.poll = node_undefined_poll;
3671
3672   BLI_strncpy(NodeSocketTypeUndefined.idname,
3673               "NodeSocketUndefined",
3674               sizeof(NodeSocketTypeUndefined.idname));
3675   /* extra type info for standard socket types */
3676   NodeSocketTypeUndefined.type = SOCK_CUSTOM;
3677   NodeSocketTypeUndefined.subtype = PROP_NONE;
3678 }
3679
3680 static void registerCompositNodes(void)
3681 {
3682   register_node_type_cmp_group();
3683
3684   register_node_type_cmp_rlayers();
3685   register_node_type_cmp_image();
3686   register_node_type_cmp_texture();
3687   register_node_type_cmp_value();
3688   register_node_type_cmp_rgb();
3689   register_node_type_cmp_curve_time();
3690   register_node_type_cmp_movieclip();
3691
3692   register_node_type_cmp_composite();
3693   register_node_type_cmp_viewer();
3694   register_node_type_cmp_splitviewer();
3695   register_node_type_cmp_output_file();
3696   register_node_type_cmp_view_levels();
3697
3698   register_node_type_cmp_curve_rgb();
3699   register_node_type_cmp_mix_rgb();
3700   register_node_type_cmp_hue_sat();
3701   register_node_type_cmp_brightcontrast();
3702   register_node_type_cmp_gamma();
3703   register_node_type_cmp_invert();
3704   register_node_type_cmp_alphaover();
3705   register_node_type_cmp_zcombine();
3706   register_node_type_cmp_colorbalance();
3707   register_node_type_cmp_huecorrect();
3708
3709   register_node_type_cmp_normal();
3710   register_node_type_cmp_curve_vec();
3711   register_node_type_cmp_map_value();
3712   register_node_type_cmp_map_range();
3713   register_node_type_cmp_normalize();
3714
3715   register_node_type_cmp_filter();
3716   register_node_type_cmp_blur();
3717   register_node_type_cmp_dblur();
3718   register_node_type_cmp_bilateralblur();
3719   register_node_type_cmp_vecblur();
3720   register_node_type_cmp_dilateerode();
3721   register_node_type_cmp_inpaint();
3722   register_node_type_cmp_despeckle();
3723   register_node_type_cmp_defocus();
3724   register_node_type_cmp_sunbeams();
3725
3726   register_node_type_cmp_valtorgb();
3727   register_node_type_cmp_rgbtobw();
3728   register_node_type_cmp_setalpha();
3729   register_node_type_cmp_idmask();
3730   register_node_type_cmp_math();
3731   register_node_type_cmp_seprgba();
3732   register_node_type_cmp_combrgba();
3733   register_node_type_cmp_sephsva();
3734   register_node_type_cmp_combhsva();
3735   register_node_type_cmp_sepyuva();
3736   register_node_type_cmp_combyuva();
3737   register_node_type_cmp_sepycca();
3738   register_node_type_cmp_combycca();
3739   register_node_type_cmp_premulkey();
3740
3741   register_node_type_cmp_diff_matte();
3742   register_node_type_cmp_distance_matte();
3743   register_node_type_cmp_chroma_matte();
3744   register_node_type_cmp_color_matte();
3745   register_node_type_cmp_channel_matte();
3746   register_node_type_cmp_color_spill();
3747   register_node_type_cmp_luma_matte();
3748   register_node_type_cmp_doubleedgemask();
3749   register_node_type_cmp_keyingscreen();
3750   register_node_type_cmp_keying();
3751   register_node_type_cmp_cryptomatte();
3752
3753   register_node_type_cmp_translate();
3754   register_node_type_cmp_rotate();
3755   register_node_type_cmp_scale();
3756   register_node_type_cmp_flip();
3757   register_node_type_cmp_crop();
3758   register_node_type_cmp_displace();
3759   register_node_type_cmp_mapuv();
3760   register_node_type_cmp_glare();
3761   register_node_type_cmp_tonemap();
3762   register_node_type_cmp_lensdist();
3763   register_node_type_cmp_transform();
3764   register_node_type_cmp_stabilize2d();
3765   register_node_type_cmp_moviedistortion();
3766
3767   register_node_type_cmp_colorcorrection();
3768   register_node_type_cmp_boxmask();
3769   register_node_type_cmp_ellipsemask();
3770   register_node_type_cmp_bokehimage();
3771   register_node_type_cmp_bokehblur();
3772   register_node_type_cmp_switch();
3773   register_node_type_cmp_switch_view();
3774   register_node_type_cmp_pixelate();
3775
3776   register_node_type_cmp_mask();
3777   register_node_type_cmp_trackpos();
3778   register_node_type_cmp_planetrackdeform();
3779   register_node_type_cmp_cornerpin();
3780 }
3781
3782 static void registerShaderNodes(void)
3783 {
3784   register_node_type_sh_group();
3785
3786   register_node_type_sh_camera();
3787   register_node_type_sh_gamma();
3788   register_node_type_sh_brightcontrast();
3789   register_node_type_sh_value();
3790   register_node_type_sh_rgb();
3791   register_node_type_sh_wireframe();
3792   register_node_type_sh_wavelength();
3793   register_node_type_sh_blackbody();
3794   register_node_type_sh_mix_rgb();
3795   register_node_type_sh_valtorgb();
3796   register_node_type_sh_rgbtobw();
3797   register_node_type_sh_shadertorgb();
3798   register_node_type_sh_normal();
3799   register_node_type_sh_mapping();
3800   register_node_type_sh_curve_vec();
3801   register_node_type_sh_curve_rgb();
3802   register_node_type_sh_math();
3803   register_node_type_sh_vect_math();
3804   register_node_type_sh_vect_transform();
3805   register_node_type_sh_squeeze();
3806   register_node_type_sh_invert();
3807   register_node_type_sh_seprgb();
3808   register_node_type_sh_combrgb();
3809   register_node_type_sh_sephsv();
3810   register_node_type_sh_combhsv();
3811   register_node_type_sh_sepxyz();
3812   register_node_type_sh_combxyz();
3813   register_node_type_sh_hue_sat();
3814
3815   register_node_type_sh_attribute();
3816   register_node_type_sh_bevel();
3817   register_node_type_sh_displacement();
3818   register_node_type_sh_vector_displacement();
3819   register_node_type_sh_geometry();
3820   register_node_type_sh_light_path();
3821   register_node_type_sh_light_falloff();
3822   register_node_type_sh_object_info();
3823   register_node_type_sh_fresnel();
3824   register_node_type_sh_layer_weight();
3825   register_node_type_sh_tex_coord();
3826   register_node_type_sh_particle_info();
3827   register_node_type_sh_bump();
3828
3829   register_node_type_sh_background();
3830   register_node_type_sh_bsdf_anisotropic();
3831   register_node_type_sh_bsdf_diffuse();
3832   register_node_type_sh_bsdf_principled();
3833   register_node_type_sh_bsdf_glossy();
3834   register_node_type_sh_bsdf_glass();
3835   register_node_type_sh_bsdf_translucent();
3836   register_node_type_sh_bsdf_transparent();
3837   register_node_type_sh_bsdf_velvet();
3838   register_node_type_sh_bsdf_toon();
3839   register_node_type_sh_bsdf_hair();
3840   register_node_type_sh_bsdf_hair_principled();
3841   register_node_type_sh_emission();
3842   register_node_type_sh_holdout();
3843   register_node_type_sh_volume_absorption();
3844   register_node_type_sh_volume_scatter();
3845   register_node_type_sh_volume_principled();
3846   register_node_type_sh_subsurface_scattering();
3847   register_node_type_sh_mix_shader();
3848   register_node_type_sh_add_shader();
3849   register_node_type_sh_uvmap();
3850   register_node_type_sh_uvalongstroke();
3851   register_node_type_sh_eevee_specular();
3852
3853   register_node_type_sh_output_light();
3854   register_node_type_sh_output_material();
3855   register_node_type_sh_output_world();
3856   register_node_type_sh_output_linestyle();
3857
3858   register_node_type_sh_tex_image();