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