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