Merge branch 'blender2.7'
[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       bNodeInstanceKey key = BKE_node_instance_hash_iterator_get_key(&iter);
1394       bNodePreview *preview = BKE_node_instance_hash_iterator_get_value(&iter);
1395       BKE_node_instance_hash_insert(ntree_dst->previews, key, BKE_node_preview_copy(preview));
1396     }
1397   }
1398   else {
1399     ntree_dst->previews = NULL;
1400   }
1401
1402   /* update node->parent pointers */
1403   for (bNode *node_dst = ntree_dst->nodes.first, *node_src = ntree_src->nodes.first; node_dst;
1404        node_dst = node_dst->next, node_src = node_src->next) {
1405     if (node_dst->parent) {
1406       node_dst->parent = node_dst->parent->new_node;
1407     }
1408   }
1409
1410   /* node tree will generate its own interface type */
1411   ntree_dst->interface_type = NULL;
1412 }
1413
1414 bNodeTree *ntreeCopyTree_ex(const bNodeTree *ntree, Main *bmain, const bool do_id_user)
1415 {
1416   bNodeTree *ntree_copy;
1417   const int flag = do_id_user ? LIB_ID_CREATE_NO_USER_REFCOUNT | LIB_ID_CREATE_NO_MAIN : 0;
1418   BKE_id_copy_ex(bmain, (ID *)ntree, (ID **)&ntree_copy, flag);
1419   return ntree_copy;
1420 }
1421 bNodeTree *ntreeCopyTree(Main *bmain, const bNodeTree *ntree)
1422 {
1423   return ntreeCopyTree_ex(ntree, bmain, true);
1424 }
1425
1426 void ntreeUserIncrefID(bNodeTree *ntree)
1427 {
1428   bNode *node;
1429   for (node = ntree->nodes.first; node; node = node->next) {
1430     id_us_plus(node->id);
1431   }
1432 }
1433 void ntreeUserDecrefID(bNodeTree *ntree)
1434 {
1435   bNode *node;
1436   for (node = ntree->nodes.first; node; node = node->next) {
1437     id_us_min(node->id);
1438   }
1439 }
1440
1441 /* *************** Node Preview *********** */
1442
1443 /* XXX this should be removed eventually ...
1444  * Currently BKE functions are modeled closely on previous code,
1445  * using BKE_node_preview_init_tree to set up previews for a whole node tree in advance.
1446  * This should be left more to the individual node tree implementations.
1447  */
1448 int BKE_node_preview_used(bNode *node)
1449 {
1450   /* XXX check for closed nodes? */
1451   return (node->typeinfo->flag & NODE_PREVIEW) != 0;
1452 }
1453
1454 bNodePreview *BKE_node_preview_verify(
1455     bNodeInstanceHash *previews, bNodeInstanceKey key, int xsize, int ysize, bool create)
1456 {
1457   bNodePreview *preview;
1458
1459   preview = BKE_node_instance_hash_lookup(previews, key);
1460   if (!preview) {
1461     if (create) {
1462       preview = MEM_callocN(sizeof(bNodePreview), "node preview");
1463       BKE_node_instance_hash_insert(previews, key, preview);
1464     }
1465     else
1466       return NULL;
1467   }
1468
1469   /* node previews can get added with variable size this way */
1470   if (xsize == 0 || ysize == 0)
1471     return preview;
1472
1473   /* sanity checks & initialize */
1474   if (preview->rect) {
1475     if (preview->xsize != xsize || preview->ysize != ysize) {
1476       MEM_freeN(preview->rect);
1477       preview->rect = NULL;
1478     }
1479   }
1480
1481   if (preview->rect == NULL) {
1482     preview->rect = MEM_callocN(4 * xsize + xsize * ysize * sizeof(char) * 4, "node preview rect");
1483     preview->xsize = xsize;
1484     preview->ysize = ysize;
1485   }
1486   /* no clear, makes nicer previews */
1487
1488   return preview;
1489 }
1490
1491 bNodePreview *BKE_node_preview_copy(bNodePreview *preview)
1492 {
1493   bNodePreview *new_preview = MEM_dupallocN(preview);
1494   if (preview->rect)
1495     new_preview->rect = MEM_dupallocN(preview->rect);
1496   return new_preview;
1497 }
1498
1499 void BKE_node_preview_free(bNodePreview *preview)
1500 {
1501   if (preview->rect)
1502     MEM_freeN(preview->rect);
1503   MEM_freeN(preview);
1504 }
1505
1506 static void node_preview_init_tree_recursive(bNodeInstanceHash *previews,
1507                                              bNodeTree *ntree,
1508                                              bNodeInstanceKey parent_key,
1509                                              int xsize,
1510                                              int ysize,
1511                                              int create)
1512 {
1513   bNode *node;
1514   for (node = ntree->nodes.first; node; node = node->next) {
1515     bNodeInstanceKey key = BKE_node_instance_key(parent_key, ntree, node);
1516
1517     if (BKE_node_preview_used(node)) {
1518       node->preview_xsize = xsize;
1519       node->preview_ysize = ysize;
1520
1521       BKE_node_preview_verify(previews, key, xsize, ysize, create);
1522     }
1523
1524     if (node->type == NODE_GROUP && node->id)
1525       node_preview_init_tree_recursive(previews, (bNodeTree *)node->id, key, xsize, ysize, create);
1526   }
1527 }
1528
1529 void BKE_node_preview_init_tree(bNodeTree *ntree, int xsize, int ysize, int create_previews)
1530 {
1531   if (!ntree)
1532     return;
1533
1534   if (!ntree->previews)
1535     ntree->previews = BKE_node_instance_hash_new("node previews");
1536
1537   node_preview_init_tree_recursive(
1538       ntree->previews, ntree, NODE_INSTANCE_KEY_BASE, xsize, ysize, create_previews);
1539 }
1540
1541 static void node_preview_tag_used_recursive(bNodeInstanceHash *previews,
1542                                             bNodeTree *ntree,
1543                                             bNodeInstanceKey parent_key)
1544 {
1545   bNode *node;
1546   for (node = ntree->nodes.first; node; node = node->next) {
1547     bNodeInstanceKey key = BKE_node_instance_key(parent_key, ntree, node);
1548
1549     if (BKE_node_preview_used(node))
1550       BKE_node_instance_hash_tag_key(previews, key);
1551
1552     if (node->type == NODE_GROUP && node->id)
1553       node_preview_tag_used_recursive(previews, (bNodeTree *)node->id, key);
1554   }
1555 }
1556
1557 void BKE_node_preview_remove_unused(bNodeTree *ntree)
1558 {
1559   if (!ntree || !ntree->previews)
1560     return;
1561
1562   /* use the instance hash functions for tagging and removing unused previews */
1563   BKE_node_instance_hash_clear_tags(ntree->previews);
1564   node_preview_tag_used_recursive(ntree->previews, ntree, NODE_INSTANCE_KEY_BASE);
1565
1566   BKE_node_instance_hash_remove_untagged(ntree->previews,
1567                                          (bNodeInstanceValueFP)BKE_node_preview_free);
1568 }
1569
1570 void BKE_node_preview_free_tree(bNodeTree *ntree)
1571 {
1572   if (!ntree)
1573     return;
1574
1575   if (ntree->previews) {
1576     BKE_node_instance_hash_free(ntree->previews, (bNodeInstanceValueFP)BKE_node_preview_free);
1577     ntree->previews = NULL;
1578   }
1579 }
1580
1581 void BKE_node_preview_clear(bNodePreview *preview)
1582 {
1583   if (preview && preview->rect)
1584     memset(preview->rect, 0, MEM_allocN_len(preview->rect));
1585 }
1586
1587 void BKE_node_preview_clear_tree(bNodeTree *ntree)
1588 {
1589   bNodeInstanceHashIterator iter;
1590
1591   if (!ntree || !ntree->previews)
1592     return;
1593
1594   NODE_INSTANCE_HASH_ITER (iter, ntree->previews) {
1595     bNodePreview *preview = BKE_node_instance_hash_iterator_get_value(&iter);
1596     BKE_node_preview_clear(preview);
1597   }
1598 }
1599
1600 static void node_preview_sync(bNodePreview *to, bNodePreview *from)
1601 {
1602   /* sizes should have been initialized by BKE_node_preview_init_tree */
1603   BLI_assert(to->xsize == from->xsize && to->ysize == from->ysize);
1604
1605   /* copy over contents of previews */
1606   if (to->rect && from->rect) {
1607     int xsize = to->xsize;
1608     int ysize = to->ysize;
1609     memcpy(to->rect, from->rect, xsize * ysize * sizeof(char) * 4);
1610   }
1611 }
1612
1613 void BKE_node_preview_sync_tree(bNodeTree *to_ntree, bNodeTree *from_ntree)
1614 {
1615   bNodeInstanceHash *from_previews = from_ntree->previews;
1616   bNodeInstanceHash *to_previews = to_ntree->previews;
1617   bNodeInstanceHashIterator iter;
1618
1619   if (!from_previews || !to_previews)
1620     return;
1621
1622   NODE_INSTANCE_HASH_ITER (iter, from_previews) {
1623     bNodeInstanceKey key = BKE_node_instance_hash_iterator_get_key(&iter);
1624     bNodePreview *from = BKE_node_instance_hash_iterator_get_value(&iter);
1625     bNodePreview *to = BKE_node_instance_hash_lookup(to_previews, key);
1626
1627     if (from && to)
1628       node_preview_sync(to, from);
1629   }
1630 }
1631
1632 void BKE_node_preview_merge_tree(bNodeTree *to_ntree, bNodeTree *from_ntree, bool remove_old)
1633 {
1634   if (remove_old || !to_ntree->previews) {
1635     /* free old previews */
1636     if (to_ntree->previews)
1637       BKE_node_instance_hash_free(to_ntree->previews, (bNodeInstanceValueFP)BKE_node_preview_free);
1638
1639     /* transfer previews */
1640     to_ntree->previews = from_ntree->previews;
1641     from_ntree->previews = NULL;
1642
1643     /* clean up, in case any to_ntree nodes have been removed */
1644     BKE_node_preview_remove_unused(to_ntree);
1645   }
1646   else {
1647     bNodeInstanceHashIterator iter;
1648
1649     if (from_ntree->previews) {
1650       NODE_INSTANCE_HASH_ITER (iter, from_ntree->previews) {
1651         bNodeInstanceKey key = BKE_node_instance_hash_iterator_get_key(&iter);
1652         bNodePreview *preview = BKE_node_instance_hash_iterator_get_value(&iter);
1653
1654         /* replace existing previews */
1655         BKE_node_instance_hash_remove(
1656             to_ntree->previews, key, (bNodeInstanceValueFP)BKE_node_preview_free);
1657         BKE_node_instance_hash_insert(to_ntree->previews, key, preview);
1658       }
1659
1660       /* Note: NULL free function here, because pointers have already been moved over to to_ntree->previews! */
1661       BKE_node_instance_hash_free(from_ntree->previews, NULL);
1662       from_ntree->previews = NULL;
1663     }
1664   }
1665 }
1666
1667 /* hack warning! this function is only used for shader previews, and
1668  * since it gets called multiple times per pixel for Ztransp we only
1669  * add the color once. Preview gets cleared before it starts render though */
1670 void BKE_node_preview_set_pixel(
1671     bNodePreview *preview, const float col[4], int x, int y, bool do_manage)
1672 {
1673   if (preview) {
1674     if (x >= 0 && y >= 0) {
1675       if (x < preview->xsize && y < preview->ysize) {
1676         unsigned char *tar = preview->rect + 4 * ((preview->xsize * y) + x);
1677
1678         if (do_manage) {
1679           linearrgb_to_srgb_uchar4(tar, col);
1680         }
1681         else {
1682           rgba_float_to_uchar(tar, col);
1683         }
1684       }
1685       //else printf("prv out bound x y %d %d\n", x, y);
1686     }
1687     //else printf("prv out bound x y %d %d\n", x, y);
1688   }
1689 }
1690
1691 /* ************** Free stuff ********** */
1692
1693 /* goes over entire tree */
1694 void nodeUnlinkNode(bNodeTree *ntree, bNode *node)
1695 {
1696   bNodeLink *link, *next;
1697   bNodeSocket *sock;
1698   ListBase *lb;
1699
1700   for (link = ntree->links.first; link; link = next) {
1701     next = link->next;
1702
1703     if (link->fromnode == node) {
1704       lb = &node->outputs;
1705       if (link->tonode)
1706         link->tonode->update |= NODE_UPDATE;
1707     }
1708     else if (link->tonode == node)
1709       lb = &node->inputs;
1710     else
1711       lb = NULL;
1712
1713     if (lb) {
1714       for (sock = lb->first; sock; sock = sock->next) {
1715         if (link->fromsock == sock || link->tosock == sock)
1716           break;
1717       }
1718       if (sock) {
1719         nodeRemLink(ntree, link);
1720       }
1721     }
1722   }
1723 }
1724
1725 static void node_unlink_attached(bNodeTree *ntree, bNode *parent)
1726 {
1727   bNode *node;
1728   for (node = ntree->nodes.first; node; node = node->next) {
1729     if (node->parent == parent)
1730       nodeDetachNode(node);
1731   }
1732 }
1733
1734 /* Free the node itself. ID user refcounting is up the caller,
1735  * that does not happen here. */
1736 static void node_free_node(bNodeTree *ntree, bNode *node)
1737 {
1738   bNodeSocket *sock, *nextsock;
1739
1740   /* since it is called while free database, node->id is undefined */
1741
1742   /* can be called for nodes outside a node tree (e.g. clipboard) */
1743   if (ntree) {
1744     /* remove all references to this node */
1745     nodeUnlinkNode(ntree, node);
1746     node_unlink_attached(ntree, node);
1747
1748     BLI_remlink(&ntree->nodes, node);
1749
1750     if (ntree->typeinfo->free_node_cache)
1751       ntree->typeinfo->free_node_cache(ntree, node);
1752
1753     /* texture node has bad habit of keeping exec data around */
1754     if (ntree->type == NTREE_TEXTURE && ntree->execdata) {
1755       ntreeTexEndExecTree(ntree->execdata);
1756       ntree->execdata = NULL;
1757     }
1758   }
1759
1760   if (node->typeinfo->freefunc) {
1761     node->typeinfo->freefunc(node);
1762   }
1763
1764   for (sock = node->inputs.first; sock; sock = nextsock) {
1765     nextsock = sock->next;
1766     /* Remember, no ID user refcount management here! */
1767     node_socket_free(ntree, sock, node, false);
1768     MEM_freeN(sock);
1769   }
1770   for (sock = node->outputs.first; sock; sock = nextsock) {
1771     nextsock = sock->next;
1772     /* Remember, no ID user refcount management here! */
1773     node_socket_free(ntree, sock, node, false);
1774     MEM_freeN(sock);
1775   }
1776
1777   BLI_freelistN(&node->internal_links);
1778
1779   if (node->prop) {
1780     /* Remember, no ID user refcount management here! */
1781     IDP_FreeProperty_ex(node->prop, false);
1782     MEM_freeN(node->prop);
1783   }
1784
1785   MEM_freeN(node);
1786
1787   if (ntree)
1788     ntree->update |= NTREE_UPDATE_NODES;
1789 }
1790
1791 void ntreeFreeLocalNode(bNodeTree *ntree, bNode *node)
1792 {
1793   /* For removing nodes while editing localized node trees. */
1794   BLI_assert((ntree->id.tag & LIB_TAG_LOCALIZED) != 0);
1795   node_free_node(ntree, node);
1796 }
1797
1798 void nodeRemoveNode(Main *bmain, bNodeTree *ntree, bNode *node, bool do_id_user)
1799 {
1800   /* This function is not for localized node trees, we do not want
1801    * do to ID user refcounting and removal of animdation data then. */
1802   BLI_assert((ntree->id.tag & LIB_TAG_LOCALIZED) == 0);
1803
1804   if (do_id_user) {
1805     /* Free callback for NodeCustomGroup. */
1806     if (node->typeinfo->freefunc_api) {
1807       PointerRNA ptr;
1808       RNA_pointer_create((ID *)ntree, &RNA_Node, node, &ptr);
1809
1810       node->typeinfo->freefunc_api(&ptr);
1811     }
1812
1813     /* Do user counting. */
1814     if (node->id) {
1815       id_us_min(node->id);
1816     }
1817   }
1818
1819   /* Remove animation data. */
1820   char propname_esc[MAX_IDPROP_NAME * 2];
1821   char prefix[MAX_IDPROP_NAME * 2];
1822
1823   BLI_strescape(propname_esc, node->name, sizeof(propname_esc));
1824   BLI_snprintf(prefix, sizeof(prefix), "nodes[\"%s\"]", propname_esc);
1825
1826   if (BKE_animdata_fix_paths_remove((ID *)ntree, prefix)) {
1827     if (bmain != NULL) {
1828       DEG_relations_tag_update(bmain);
1829     }
1830   }
1831
1832   /* Free node itself. */
1833   node_free_node(ntree, node);
1834 }
1835
1836 static void node_socket_interface_free(bNodeTree *UNUSED(ntree), bNodeSocket *sock)
1837 {
1838   if (sock->prop) {
1839     IDP_FreeProperty(sock->prop);
1840     MEM_freeN(sock->prop);
1841   }
1842
1843   if (sock->default_value)
1844     MEM_freeN(sock->default_value);
1845 }
1846
1847 static void free_localized_node_groups(bNodeTree *ntree)
1848 {
1849   bNode *node;
1850
1851   /* Only localized node trees store a copy for each node group tree.
1852    * Each node group tree in a localized node tree can be freed,
1853    * since it is a localized copy itself (no risk of accessing free'd
1854    * data in main, see [#37939]).
1855    */
1856   if (!(ntree->id.tag & LIB_TAG_LOCALIZED))
1857     return;
1858
1859   for (node = ntree->nodes.first; node; node = node->next) {
1860     if ((ELEM(node->type, NODE_GROUP, NODE_CUSTOM_GROUP)) && node->id) {
1861       bNodeTree *ngroup = (bNodeTree *)node->id;
1862       ntreeFreeTree(ngroup);
1863       MEM_freeN(ngroup);
1864     }
1865   }
1866 }
1867
1868 /* Free (or release) any data used by this nodetree. Does not free the
1869  * nodetree itself and does no ID user counting. */
1870 void ntreeFreeTree(bNodeTree *ntree)
1871 {
1872   bNode *node, *next;
1873   bNodeSocket *sock, *nextsock;
1874
1875   BKE_animdata_free((ID *)ntree, false);
1876
1877   /* XXX hack! node trees should not store execution graphs at all.
1878    * This should be removed when old tree types no longer require it.
1879    * Currently the execution data for texture nodes remains in the tree
1880    * after execution, until the node tree is updated or freed.
1881    */
1882   if (ntree->execdata) {
1883     switch (ntree->type) {
1884       case NTREE_SHADER:
1885         ntreeShaderEndExecTree(ntree->execdata);
1886         break;
1887       case NTREE_TEXTURE:
1888         ntreeTexEndExecTree(ntree->execdata);
1889         ntree->execdata = NULL;
1890         break;
1891     }
1892   }
1893
1894   /* XXX not nice, but needed to free localized node groups properly */
1895   free_localized_node_groups(ntree);
1896
1897   /* unregister associated RNA types */
1898   ntreeInterfaceTypeFree(ntree);
1899
1900   BLI_freelistN(&ntree->links); /* do first, then unlink_node goes fast */
1901
1902   for (node = ntree->nodes.first; node; node = next) {
1903     next = node->next;
1904     node_free_node(ntree, node);
1905   }
1906
1907   /* free interface sockets */
1908   for (sock = ntree->inputs.first; sock; sock = nextsock) {
1909     nextsock = sock->next;
1910     node_socket_interface_free(ntree, sock);
1911     MEM_freeN(sock);
1912   }
1913   for (sock = ntree->outputs.first; sock; sock = nextsock) {
1914     nextsock = sock->next;
1915     node_socket_interface_free(ntree, sock);
1916     MEM_freeN(sock);
1917   }
1918
1919   /* free preview hash */
1920   if (ntree->previews) {
1921     BKE_node_instance_hash_free(ntree->previews, (bNodeInstanceValueFP)BKE_node_preview_free);
1922   }
1923
1924   if (ntree->duplilock)
1925     BLI_mutex_free(ntree->duplilock);
1926
1927   if (ntree->id.tag & LIB_TAG_LOCALIZED) {
1928     BKE_libblock_free_data(&ntree->id, true);
1929   }
1930 }
1931
1932 void ntreeFreeNestedTree(bNodeTree *ntree)
1933 {
1934   ntreeFreeTree(ntree);
1935   BKE_libblock_free_data(&ntree->id, true);
1936 }
1937
1938 void ntreeFreeLocalTree(bNodeTree *ntree)
1939 {
1940   if (ntree->id.tag & LIB_TAG_LOCALIZED) {
1941     ntreeFreeTree(ntree);
1942   }
1943   else {
1944     ntreeFreeTree(ntree);
1945     BKE_libblock_free_data(&ntree->id, true);
1946   }
1947 }
1948
1949 void ntreeFreeCache(bNodeTree *ntree)
1950 {
1951   if (ntree == NULL)
1952     return;
1953
1954   if (ntree->typeinfo->free_cache)
1955     ntree->typeinfo->free_cache(ntree);
1956 }
1957
1958 void ntreeSetOutput(bNodeTree *ntree)
1959 {
1960   bNode *node;
1961
1962   /* find the active outputs, might become tree type dependent handler */
1963   for (node = ntree->nodes.first; node; node = node->next) {
1964     if (node->typeinfo->nclass == NODE_CLASS_OUTPUT) {
1965       bNode *tnode;
1966       int output = 0;
1967
1968       /* we need a check for which output node should be tagged like this, below an exception */
1969       if (node->type == CMP_NODE_OUTPUT_FILE)
1970         continue;
1971
1972       /* there is more types having output class, each one is checked */
1973       for (tnode = ntree->nodes.first; tnode; tnode = tnode->next) {
1974         if (tnode->typeinfo->nclass == NODE_CLASS_OUTPUT) {
1975
1976           if (ntree->type == NTREE_COMPOSIT) {
1977
1978             /* same type, exception for viewer */
1979             if (tnode->type == node->type ||
1980                 (ELEM(tnode->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER) &&
1981                  ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER))) {
1982               if (tnode->flag & NODE_DO_OUTPUT) {
1983                 output++;
1984                 if (output > 1)
1985                   tnode->flag &= ~NODE_DO_OUTPUT;
1986               }
1987             }
1988           }
1989           else {
1990             /* same type */
1991             if (tnode->type == node->type) {
1992               if (tnode->flag & NODE_DO_OUTPUT) {
1993                 output++;
1994                 if (output > 1)
1995                   tnode->flag &= ~NODE_DO_OUTPUT;
1996               }
1997             }
1998           }
1999         }
2000       }
2001       if (output == 0)
2002         node->flag |= NODE_DO_OUTPUT;
2003     }
2004
2005     /* group node outputs use this flag too */
2006     if (node->type == NODE_GROUP_OUTPUT) {
2007       bNode *tnode;
2008       int output = 0;
2009
2010       for (tnode = ntree->nodes.first; tnode; tnode = tnode->next) {
2011         if (tnode->type == NODE_GROUP_OUTPUT) {
2012           if (tnode->flag & NODE_DO_OUTPUT) {
2013             output++;
2014             if (output > 1)
2015               tnode->flag &= ~NODE_DO_OUTPUT;
2016           }
2017         }
2018       }
2019       if (output == 0)
2020         node->flag |= NODE_DO_OUTPUT;
2021     }
2022   }
2023
2024   /* here we could recursively set which nodes have to be done,
2025    * might be different for editor or for "real" use... */
2026 }
2027
2028 bNodeTree *ntreeFromID(const ID *id)
2029 {
2030   switch (GS(id->name)) {
2031     case ID_MA:
2032       return ((const Material *)id)->nodetree;
2033     case ID_LA:
2034       return ((const Light *)id)->nodetree;
2035     case ID_WO:
2036       return ((const World *)id)->nodetree;
2037     case ID_TE:
2038       return ((const Tex *)id)->nodetree;
2039     case ID_SCE:
2040       return ((const Scene *)id)->nodetree;
2041     case ID_LS:
2042       return ((const FreestyleLineStyle *)id)->nodetree;
2043     default:
2044       return NULL;
2045   }
2046 }
2047
2048 void ntreeMakeLocal(Main *bmain, bNodeTree *ntree, bool id_in_mainlist, const bool lib_local)
2049 {
2050   BKE_id_make_local_generic(bmain, &ntree->id, id_in_mainlist, lib_local);
2051 }
2052
2053 int ntreeNodeExists(bNodeTree *ntree, bNode *testnode)
2054 {
2055   bNode *node = ntree->nodes.first;
2056   for (; node; node = node->next)
2057     if (node == testnode)
2058       return 1;
2059   return 0;
2060 }
2061
2062 int ntreeOutputExists(bNode *node, bNodeSocket *testsock)
2063 {
2064   bNodeSocket *sock = node->outputs.first;
2065   for (; sock; sock = sock->next)
2066     if (sock == testsock)
2067       return 1;
2068   return 0;
2069 }
2070
2071 void ntreeNodeFlagSet(const bNodeTree *ntree, const int flag, const bool enable)
2072 {
2073   bNode *node = ntree->nodes.first;
2074
2075   for (; node; node = node->next) {
2076     if (enable) {
2077       node->flag |= flag;
2078     }
2079     else {
2080       node->flag &= ~flag;
2081     }
2082   }
2083 }
2084
2085 /* returns localized tree for execution in threads */
2086 bNodeTree *ntreeLocalize(bNodeTree *ntree)
2087 {
2088   if (ntree) {
2089     bNodeTree *ltree;
2090     bNode *node;
2091
2092     BLI_spin_lock(&spin);
2093     if (!ntree->duplilock) {
2094       ntree->duplilock = BLI_mutex_alloc();
2095     }
2096     BLI_spin_unlock(&spin);
2097
2098     BLI_mutex_lock(ntree->duplilock);
2099
2100     /* Make full copy outside of Main database.
2101      * Note: previews are not copied here.
2102      */
2103     BKE_id_copy_ex(
2104         NULL, &ntree->id, (ID **)&ltree, (LIB_ID_COPY_LOCALIZE | LIB_ID_COPY_NO_ANIMDATA));
2105
2106     ltree->id.tag |= LIB_TAG_LOCALIZED;
2107
2108     for (node = ltree->nodes.first; node; node = node->next) {
2109       if ((ELEM(node->type, NODE_GROUP, NODE_CUSTOM_GROUP)) && node->id) {
2110         node->id = (ID *)ntreeLocalize((bNodeTree *)node->id);
2111       }
2112     }
2113
2114     /* ensures only a single output node is enabled */
2115     ntreeSetOutput(ntree);
2116
2117     for (node = ntree->nodes.first; node; node = node->next) {
2118       /* store new_node pointer to original */
2119       node->new_node->original = node;
2120     }
2121
2122     if (ntree->typeinfo->localize)
2123       ntree->typeinfo->localize(ltree, ntree);
2124
2125     BLI_mutex_unlock(ntree->duplilock);
2126
2127     return ltree;
2128   }
2129   else
2130     return NULL;
2131 }
2132
2133 /* sync local composite with real tree */
2134 /* local tree is supposed to be running, be careful moving previews! */
2135 /* is called by jobs manager, outside threads, so it doesn't happen during draw */
2136 void ntreeLocalSync(bNodeTree *localtree, bNodeTree *ntree)
2137 {
2138   if (localtree && ntree) {
2139     if (ntree->typeinfo->local_sync)
2140       ntree->typeinfo->local_sync(localtree, ntree);
2141   }
2142 }
2143
2144 /* merge local tree results back, and free local tree */
2145 /* we have to assume the editor already changed completely */
2146 void ntreeLocalMerge(Main *bmain, bNodeTree *localtree, bNodeTree *ntree)
2147 {
2148   if (ntree && localtree) {
2149     if (ntree->typeinfo->local_merge)
2150       ntree->typeinfo->local_merge(bmain, localtree, ntree);
2151
2152     ntreeFreeTree(localtree);
2153     MEM_freeN(localtree);
2154   }
2155 }
2156
2157 /* ************ NODE TREE INTERFACE *************** */
2158
2159 static bNodeSocket *make_socket_interface(bNodeTree *ntree,
2160                                           int in_out,
2161                                           const char *idname,
2162                                           const char *name)
2163 {
2164   bNodeSocketType *stype = nodeSocketTypeFind(idname);
2165   bNodeSocket *sock;
2166   int own_index = ntree->cur_index++;
2167
2168   if (stype == NULL) {
2169     return NULL;
2170   }
2171
2172   sock = MEM_callocN(sizeof(bNodeSocket), "socket template");
2173   BLI_strncpy(sock->idname, stype->idname, sizeof(sock->idname));
2174   node_socket_set_typeinfo(ntree, sock, stype);
2175   sock->in_out = in_out;
2176   sock->type = SOCK_CUSTOM; /* int type undefined by default */
2177
2178   /* assign new unique index */
2179   own_index = ntree->cur_index++;
2180   /* use the own_index as socket identifier */
2181   if (in_out == SOCK_IN)
2182     BLI_snprintf(sock->identifier, MAX_NAME, "Input_%d", own_index);
2183   else
2184     BLI_snprintf(sock->identifier, MAX_NAME, "Output_%d", own_index);
2185 #ifdef USE_NODE_COMPAT_CUSTOMNODES
2186     /* XXX forward compatibility:
2187      * own_index is deprecated, but needs to be set here.
2188      * Node sockets generally use the identifier string instead now,
2189      * but reconstructing own_index in writefile.c would require parsing the identifier string.
2190      */
2191
2192 #  if (defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 406)) || defined(__clang__)
2193 #    pragma GCC diagnostic push
2194 #    pragma GCC diagnostic ignored "-Wdeprecated-declarations"
2195 #  endif
2196
2197   sock->own_index = own_index;
2198
2199 #  if (defined(__GNUC__) && ((__GNUC__ * 100 + __GNUC_MINOR__) >= 406)) || defined(__clang__)
2200 #    pragma GCC diagnostic pop
2201 #  endif
2202
2203 #endif /* USE_NODE_COMPAT_CUSTOMNODES */
2204
2205   sock->limit = (in_out == SOCK_IN ? 1 : 0xFFF);
2206
2207   BLI_strncpy(sock->name, name, NODE_MAXSTR);
2208   sock->storage = NULL;
2209   sock->flag |= SOCK_COLLAPSED;
2210
2211   return sock;
2212 }
2213
2214 bNodeSocket *ntreeFindSocketInterface(bNodeTree *ntree, int in_out, const char *identifier)
2215 {
2216   bNodeSocket *iosock = (in_out == SOCK_IN ? ntree->inputs.first : ntree->outputs.first);
2217   for (; iosock; iosock = iosock->next)
2218     if (STREQ(iosock->identifier, identifier))
2219       return iosock;
2220   return NULL;
2221 }
2222
2223 bNodeSocket *ntreeAddSocketInterface(bNodeTree *ntree,
2224                                      int in_out,
2225                                      const char *idname,
2226                                      const char *name)
2227 {
2228   bNodeSocket *iosock;
2229
2230   iosock = make_socket_interface(ntree, in_out, idname, name);
2231   if (in_out == SOCK_IN) {
2232     BLI_addtail(&ntree->inputs, iosock);
2233     ntree->update |= NTREE_UPDATE_GROUP_IN;
2234   }
2235   else if (in_out == SOCK_OUT) {
2236     BLI_addtail(&ntree->outputs, iosock);
2237     ntree->update |= NTREE_UPDATE_GROUP_OUT;
2238   }
2239
2240   return iosock;
2241 }
2242
2243 bNodeSocket *ntreeInsertSocketInterface(
2244     bNodeTree *ntree, int in_out, const char *idname, bNodeSocket *next_sock, const char *name)
2245 {
2246   bNodeSocket *iosock;
2247
2248   iosock = make_socket_interface(ntree, in_out, idname, name);
2249   if (in_out == SOCK_IN) {
2250     BLI_insertlinkbefore(&ntree->inputs, next_sock, iosock);
2251     ntree->update |= NTREE_UPDATE_GROUP_IN;
2252   }
2253   else if (in_out == SOCK_OUT) {
2254     BLI_insertlinkbefore(&ntree->outputs, next_sock, iosock);
2255     ntree->update |= NTREE_UPDATE_GROUP_OUT;
2256   }
2257
2258   return iosock;
2259 }
2260
2261 struct bNodeSocket *ntreeAddSocketInterfaceFromSocket(bNodeTree *ntree,
2262                                                       bNode *from_node,
2263                                                       bNodeSocket *from_sock)
2264 {
2265   bNodeSocket *iosock = ntreeAddSocketInterface(
2266       ntree, from_sock->in_out, from_sock->idname, from_sock->name);
2267   if (iosock) {
2268     if (iosock->typeinfo->interface_from_socket)
2269       iosock->typeinfo->interface_from_socket(ntree, iosock, from_node, from_sock);
2270   }
2271   return iosock;
2272 }
2273
2274 struct bNodeSocket *ntreeInsertSocketInterfaceFromSocket(bNodeTree *ntree,
2275                                                          bNodeSocket *next_sock,
2276                                                          bNode *from_node,
2277                                                          bNodeSocket *from_sock)
2278 {
2279   bNodeSocket *iosock = ntreeInsertSocketInterface(
2280       ntree, from_sock->in_out, from_sock->idname, next_sock, from_sock->name);
2281   if (iosock) {
2282     if (iosock->typeinfo->interface_from_socket)
2283       iosock->typeinfo->interface_from_socket(ntree, iosock, from_node, from_sock);
2284   }
2285   return iosock;
2286 }
2287
2288 void ntreeRemoveSocketInterface(bNodeTree *ntree, bNodeSocket *sock)
2289 {
2290   /* this is fast, this way we don't need an in_out argument */
2291   BLI_remlink(&ntree->inputs, sock);
2292   BLI_remlink(&ntree->outputs, sock);
2293
2294   node_socket_interface_free(ntree, sock);
2295   MEM_freeN(sock);
2296
2297   ntree->update |= NTREE_UPDATE_GROUP;
2298 }
2299
2300 /* generates a valid RNA identifier from the node tree name */
2301 static void ntree_interface_identifier_base(bNodeTree *ntree, char *base)
2302 {
2303   /* generate a valid RNA identifier */
2304   sprintf(base, "NodeTreeInterface_%s", ntree->id.name + 2);
2305   RNA_identifier_sanitize(base, false);
2306 }
2307
2308 /* check if the identifier is already in use */
2309 static bool ntree_interface_unique_identifier_check(void *UNUSED(data), const char *identifier)
2310 {
2311   return (RNA_struct_find(identifier) != NULL);
2312 }
2313
2314 /* generates the actual unique identifier and ui name and description */
2315 static void ntree_interface_identifier(bNodeTree *ntree,
2316                                        const char *base,
2317                                        char *identifier,
2318                                        int maxlen,
2319                                        char *name,
2320                                        char *description)
2321 {
2322   /* There is a possibility that different node tree names get mapped to the same identifier
2323    * after sanitization (e.g. "SomeGroup_A", "SomeGroup.A" both get sanitized to "SomeGroup_A").
2324    * On top of the sanitized id string add a number suffix if necessary to avoid duplicates.
2325    */
2326   identifier[0] = '\0';
2327   BLI_uniquename_cb(ntree_interface_unique_identifier_check, NULL, base, '_', identifier, maxlen);
2328
2329   sprintf(name, "Node Tree %s Interface", ntree->id.name + 2);
2330   sprintf(description, "Interface properties of node group %s", ntree->id.name + 2);
2331 }
2332
2333 static void ntree_interface_type_create(bNodeTree *ntree)
2334 {
2335   StructRNA *srna;
2336   bNodeSocket *sock;
2337   /* strings are generated from base string + ID name, sizes are sufficient */
2338   char base[MAX_ID_NAME + 64], identifier[MAX_ID_NAME + 64], name[MAX_ID_NAME + 64],
2339       description[MAX_ID_NAME + 64];
2340
2341   /* generate a valid RNA identifier */
2342   ntree_interface_identifier_base(ntree, base);
2343   ntree_interface_identifier(ntree, base, identifier, sizeof(identifier), name, description);
2344
2345   /* register a subtype of PropertyGroup */
2346   srna = RNA_def_struct_ptr(&BLENDER_RNA, identifier, &RNA_PropertyGroup);
2347   RNA_def_struct_ui_text(srna, name, description);
2348   RNA_def_struct_duplicate_pointers(&BLENDER_RNA, srna);
2349
2350   /* associate the RNA type with the node tree */
2351   ntree->interface_type = srna;
2352   RNA_struct_blender_type_set(srna, ntree);
2353
2354   /* add socket properties */
2355   for (sock = ntree->inputs.first; sock; sock = sock->next) {
2356     bNodeSocketType *stype = sock->typeinfo;
2357     if (stype && stype->interface_register_properties)
2358       stype->interface_register_properties(ntree, sock, srna);
2359   }
2360   for (sock = ntree->outputs.first; sock; sock = sock->next) {
2361     bNodeSocketType *stype = sock->typeinfo;
2362     if (stype && stype->interface_register_properties)
2363       stype->interface_register_properties(ntree, sock, srna);
2364   }
2365 }
2366
2367 StructRNA *ntreeInterfaceTypeGet(bNodeTree *ntree, int create)
2368 {
2369   if (ntree->interface_type) {
2370     /* strings are generated from base string + ID name, sizes are sufficient */
2371     char base[MAX_ID_NAME + 64], identifier[MAX_ID_NAME + 64], name[MAX_ID_NAME + 64],
2372         description[MAX_ID_NAME + 64];
2373
2374     /* A bit of a hack: when changing the ID name, update the RNA type identifier too,
2375      * so that the names match. This is not strictly necessary to keep it working,
2376      * but better for identifying associated NodeTree blocks and RNA types.
2377      */
2378     StructRNA *srna = ntree->interface_type;
2379
2380     ntree_interface_identifier_base(ntree, base);
2381
2382     /* RNA identifier may have a number suffix, but should start with the idbase string */
2383     if (!STREQLEN(RNA_struct_identifier(srna), base, sizeof(base))) {
2384       /* generate new unique RNA identifier from the ID name */
2385       ntree_interface_identifier(ntree, base, identifier, sizeof(identifier), name, description);
2386
2387       /* rename the RNA type */
2388       RNA_def_struct_free_pointers(&BLENDER_RNA, srna);
2389       RNA_def_struct_identifier(&BLENDER_RNA, srna, identifier);
2390       RNA_def_struct_ui_text(srna, name, description);
2391       RNA_def_struct_duplicate_pointers(&BLENDER_RNA, srna);
2392     }
2393   }
2394   else if (create) {
2395     ntree_interface_type_create(ntree);
2396   }
2397
2398   return ntree->interface_type;
2399 }
2400
2401 void ntreeInterfaceTypeFree(bNodeTree *ntree)
2402 {
2403   if (ntree->interface_type) {
2404     RNA_struct_free(&BLENDER_RNA, ntree->interface_type);
2405     ntree->interface_type = NULL;
2406   }
2407 }
2408
2409 void ntreeInterfaceTypeUpdate(bNodeTree *ntree)
2410 {
2411   /* XXX it would be sufficient to just recreate all properties
2412    * instead of re-registering the whole struct type,
2413    * but there is currently no good way to do this in the RNA functions.
2414    * Overhead should be negligible.
2415    */
2416   ntreeInterfaceTypeFree(ntree);
2417   ntree_interface_type_create(ntree);
2418 }
2419
2420 /* ************ find stuff *************** */
2421
2422 bNode *ntreeFindType(const bNodeTree *ntree, int type)
2423 {
2424   if (ntree) {
2425     for (bNode *node = ntree->nodes.first; node; node = node->next) {
2426       if (node->type == type) {
2427         return node;
2428       }
2429     }
2430   }
2431   return NULL;
2432 }
2433
2434 bool ntreeHasType(const bNodeTree *ntree, int type)
2435 {
2436   return ntreeFindType(ntree, type) != NULL;
2437 }
2438
2439 bool ntreeHasTree(const bNodeTree *ntree, const bNodeTree *lookup)
2440 {
2441   bNode *node;
2442
2443   if (ntree == lookup)
2444     return true;
2445
2446   for (node = ntree->nodes.first; node; node = node->next)
2447     if (ELEM(node->type, NODE_GROUP, NODE_CUSTOM_GROUP) && node->id)
2448       if (ntreeHasTree((bNodeTree *)node->id, lookup))
2449         return true;
2450
2451   return false;
2452 }
2453
2454 bNodeLink *nodeFindLink(bNodeTree *ntree, bNodeSocket *from, bNodeSocket *to)
2455 {
2456   bNodeLink *link;
2457
2458   for (link = ntree->links.first; link; link = link->next) {
2459     if (link->fromsock == from && link->tosock == to)
2460       return link;
2461     if (link->fromsock == to && link->tosock == from) /* hrms? */
2462       return link;
2463   }
2464   return NULL;
2465 }
2466
2467 int nodeCountSocketLinks(bNodeTree *ntree, bNodeSocket *sock)
2468 {
2469   bNodeLink *link;
2470   int tot = 0;
2471
2472   for (link = ntree->links.first; link; link = link->next) {
2473     if (link->fromsock == sock || link->tosock == sock)
2474       tot++;
2475   }
2476   return tot;
2477 }
2478
2479 bNode *nodeGetActive(bNodeTree *ntree)
2480 {
2481   bNode *node;
2482
2483   if (ntree == NULL)
2484     return NULL;
2485
2486   for (node = ntree->nodes.first; node; node = node->next)
2487     if (node->flag & NODE_ACTIVE)
2488       break;
2489   return node;
2490 }
2491
2492 static bNode *node_get_active_id_recursive(bNodeInstanceKey active_key,
2493                                            bNodeInstanceKey parent_key,
2494                                            bNodeTree *ntree,
2495                                            short idtype)
2496 {
2497   if (parent_key.value == active_key.value || active_key.value == 0) {
2498     bNode *node;
2499     for (node = ntree->nodes.first; node; node = node->next)
2500       if (node->id && GS(node->id->name) == idtype)
2501         if (node->flag & NODE_ACTIVE_ID)
2502           return node;
2503   }
2504   else {
2505     bNode *node, *tnode;
2506     /* no node with active ID in this tree, look inside groups */
2507     for (node = ntree->nodes.first; node; node = node->next) {
2508       if (node->type == NODE_GROUP) {
2509         bNodeTree *group = (bNodeTree *)node->id;
2510         if (group) {
2511           bNodeInstanceKey group_key = BKE_node_instance_key(parent_key, ntree, node);
2512           tnode = node_get_active_id_recursive(active_key, group_key, group, idtype);
2513           if (tnode)
2514             return tnode;
2515         }
2516       }
2517     }
2518   }
2519
2520   return NULL;
2521 }
2522
2523 /* two active flags, ID nodes have special flag for buttons display */
2524 bNode *nodeGetActiveID(bNodeTree *ntree, short idtype)
2525 {
2526   if (ntree)
2527     return node_get_active_id_recursive(
2528         ntree->active_viewer_key, NODE_INSTANCE_KEY_BASE, ntree, idtype);
2529   else
2530     return NULL;
2531 }
2532
2533 bool nodeSetActiveID(bNodeTree *ntree, short idtype, ID *id)
2534 {
2535   bNode *node;
2536   bool ok = false;
2537
2538   if (ntree == NULL)
2539     return ok;
2540
2541   for (node = ntree->nodes.first; node; node = node->next) {
2542     if (node->id && GS(node->id->name) == idtype) {
2543       if (id && ok == false && node->id == id) {
2544         node->flag |= NODE_ACTIVE_ID;
2545         ok = true;
2546       }
2547       else {
2548         node->flag &= ~NODE_ACTIVE_ID;
2549       }
2550     }
2551   }
2552
2553   /* update all groups linked from here
2554    * if active ID node has been found already,
2555    * just pass NULL so other matching nodes are deactivated.
2556    */
2557   for (node = ntree->nodes.first; node; node = node->next) {
2558     if (node->type == NODE_GROUP)
2559       ok |= nodeSetActiveID((bNodeTree *)node->id, idtype, (ok == false ? id : NULL));
2560   }
2561
2562   return ok;
2563 }
2564
2565 /* two active flags, ID nodes have special flag for buttons display */
2566 void nodeClearActiveID(bNodeTree *ntree, short idtype)
2567 {
2568   bNode *node;
2569
2570   if (ntree == NULL)
2571     return;
2572
2573   for (node = ntree->nodes.first; node; node = node->next)
2574     if (node->id && GS(node->id->name) == idtype)
2575       node->flag &= ~NODE_ACTIVE_ID;
2576 }
2577
2578 void nodeSetSelected(bNode *node, bool select)
2579 {
2580   if (select) {
2581     node->flag |= NODE_SELECT;
2582   }
2583   else {
2584     bNodeSocket *sock;
2585
2586     node->flag &= ~NODE_SELECT;
2587
2588     /* deselect sockets too */
2589     for (sock = node->inputs.first; sock; sock = sock->next)
2590       sock->flag &= ~NODE_SELECT;
2591     for (sock = node->outputs.first; sock; sock = sock->next)
2592       sock->flag &= ~NODE_SELECT;
2593   }
2594 }
2595
2596 void nodeClearActive(bNodeTree *ntree)
2597 {
2598   bNode *node;
2599
2600   if (ntree == NULL)
2601     return;
2602
2603   for (node = ntree->nodes.first; node; node = node->next)
2604     node->flag &= ~(NODE_ACTIVE | NODE_ACTIVE_ID);
2605 }
2606
2607 /* two active flags, ID nodes have special flag for buttons display */
2608 void nodeSetActive(bNodeTree *ntree, bNode *node)
2609 {
2610   bNode *tnode;
2611
2612   /* make sure only one node is active, and only one per ID type */
2613   for (tnode = ntree->nodes.first; tnode; tnode = tnode->next) {
2614     tnode->flag &= ~NODE_ACTIVE;
2615
2616     if (node->id && tnode->id) {
2617       if (GS(node->id->name) == GS(tnode->id->name))
2618         tnode->flag &= ~NODE_ACTIVE_ID;
2619     }
2620     if (node->typeinfo->nclass == NODE_CLASS_TEXTURE)
2621       tnode->flag &= ~NODE_ACTIVE_TEXTURE;
2622   }
2623
2624   node->flag |= NODE_ACTIVE;
2625   if (node->id)
2626     node->flag |= NODE_ACTIVE_ID;
2627   if (node->typeinfo->nclass == NODE_CLASS_TEXTURE)
2628     node->flag |= NODE_ACTIVE_TEXTURE;
2629 }
2630
2631 int nodeSocketIsHidden(bNodeSocket *sock)
2632 {
2633   return ((sock->flag & (SOCK_HIDDEN | SOCK_UNAVAIL)) != 0);
2634 }
2635
2636 /* ************** Node Clipboard *********** */
2637
2638 #define USE_NODE_CB_VALIDATE
2639
2640 #ifdef USE_NODE_CB_VALIDATE
2641 /**
2642  * This data structure is to validate the node on creation,
2643  * otherwise we may reference missing data.
2644  *
2645  * Currently its only used for ID's, but nodes may one day
2646  * reference other pointers which need validation.
2647  */
2648 typedef struct bNodeClipboardExtraInfo {
2649   struct bNodeClipboardExtraInfo *next, *prev;
2650   ID *id;
2651   char id_name[MAX_ID_NAME];
2652   char library_name[FILE_MAX];
2653 } bNodeClipboardExtraInfo;
2654 #endif /* USE_NODE_CB_VALIDATE */
2655
2656 typedef struct bNodeClipboard {
2657   ListBase nodes;
2658
2659 #ifdef USE_NODE_CB_VALIDATE
2660   ListBase nodes_extra_info;
2661 #endif
2662
2663   ListBase links;
2664   int type;
2665 } bNodeClipboard;
2666
2667 static bNodeClipboard node_clipboard = {{NULL}};
2668
2669 void BKE_node_clipboard_init(struct bNodeTree *ntree)
2670 {
2671   node_clipboard.type = ntree->type;
2672 }
2673
2674 void BKE_node_clipboard_clear(void)
2675 {
2676   bNode *node, *node_next;
2677   bNodeLink *link, *link_next;
2678
2679   for (link = node_clipboard.links.first; link; link = link_next) {
2680     link_next = link->next;
2681     nodeRemLink(NULL, link);
2682   }
2683   BLI_listbase_clear(&node_clipboard.links);
2684
2685   for (node = node_clipboard.nodes.first; node; node = node_next) {
2686     node_next = node->next;
2687     node_free_node(NULL, node);
2688   }
2689   BLI_listbase_clear(&node_clipboard.nodes);
2690
2691 #ifdef USE_NODE_CB_VALIDATE
2692   BLI_freelistN(&node_clipboard.nodes_extra_info);
2693 #endif
2694 }
2695
2696 /* return false when one or more ID's are lost */
2697 bool BKE_node_clipboard_validate(void)
2698 {
2699   bool ok = true;
2700
2701 #ifdef USE_NODE_CB_VALIDATE
2702   bNodeClipboardExtraInfo *node_info;
2703   bNode *node;
2704
2705   /* lists must be aligned */
2706   BLI_assert(BLI_listbase_count(&node_clipboard.nodes) ==
2707              BLI_listbase_count(&node_clipboard.nodes_extra_info));
2708
2709   for (node = node_clipboard.nodes.first, node_info = node_clipboard.nodes_extra_info.first; node;
2710        node = node->next, node_info = node_info->next) {
2711     /* validate the node against the stored node info */
2712
2713     /* re-assign each loop since we may clear,
2714      * open a new file where the ID is valid, and paste again */
2715     node->id = node_info->id;
2716
2717     /* currently only validate the ID */
2718     if (node->id) {
2719       /* We want to search into current blend file, so using G_MAIN is valid here too. */
2720       ListBase *lb = which_libbase(G_MAIN, GS(node_info->id_name));
2721       BLI_assert(lb != NULL);
2722
2723       if (BLI_findindex(lb, node_info->id) == -1) {
2724         /* may assign NULL */
2725         node->id = BLI_findstring(lb, node_info->id_name + 2, offsetof(ID, name) + 2);
2726
2727         if (node->id == NULL) {
2728           ok = false;
2729         }
2730       }
2731     }
2732   }
2733 #endif /* USE_NODE_CB_VALIDATE */
2734
2735   return ok;
2736 }
2737
2738 void BKE_node_clipboard_add_node(bNode *node)
2739 {
2740 #ifdef USE_NODE_CB_VALIDATE
2741   /* add extra info */
2742   bNodeClipboardExtraInfo *node_info = MEM_mallocN(sizeof(bNodeClipboardExtraInfo),
2743                                                    "bNodeClipboardExtraInfo");
2744
2745   node_info->id = node->id;
2746   if (node->id) {
2747     BLI_strncpy(node_info->id_name, node->id->name, sizeof(node_info->id_name));
2748     if (ID_IS_LINKED(node->id)) {
2749       BLI_strncpy(
2750           node_info->library_name, node->id->lib->filepath, sizeof(node_info->library_name));
2751     }
2752     else {
2753       node_info->library_name[0] = '\0';
2754     }
2755   }
2756   else {
2757     node_info->id_name[0] = '\0';
2758     node_info->library_name[0] = '\0';
2759   }
2760   BLI_addtail(&node_clipboard.nodes_extra_info, node_info);
2761   /* end extra info */
2762 #endif /* USE_NODE_CB_VALIDATE */
2763
2764   /* add node */
2765   BLI_addtail(&node_clipboard.nodes, node);
2766 }
2767
2768 void BKE_node_clipboard_add_link(bNodeLink *link)
2769 {
2770   BLI_addtail(&node_clipboard.links, link);
2771 }
2772
2773 const ListBase *BKE_node_clipboard_get_nodes(void)
2774 {
2775   return &node_clipboard.nodes;
2776 }
2777
2778 const ListBase *BKE_node_clipboard_get_links(void)
2779 {
2780   return &node_clipboard.links;
2781 }
2782
2783 int BKE_node_clipboard_get_type(void)
2784 {
2785   return node_clipboard.type;
2786 }
2787
2788 void BKE_node_clipboard_free(void)
2789 {
2790   BKE_node_clipboard_validate();
2791   BKE_node_clipboard_clear();
2792 }
2793
2794 /* Node Instance Hash */
2795
2796 /* magic number for initial hash key */
2797 const bNodeInstanceKey NODE_INSTANCE_KEY_BASE = {5381};
2798 const bNodeInstanceKey NODE_INSTANCE_KEY_NONE = {0};
2799
2800 /* Generate a hash key from ntree and node names
2801  * Uses the djb2 algorithm with xor by Bernstein:
2802  * http://www.cse.yorku.ca/~oz/hash.html
2803  */
2804 static bNodeInstanceKey node_hash_int_str(bNodeInstanceKey hash, const char *str)
2805 {
2806   char c;
2807
2808   while ((c = *str++))
2809     hash.value = ((hash.value << 5) + hash.value) ^ c; /* (hash * 33) ^ c */
2810
2811   /* separator '\0' character, to avoid ambiguity from concatenated strings */
2812   hash.value = (hash.value << 5) + hash.value; /* hash * 33 */
2813
2814   return hash;
2815 }
2816
2817 bNodeInstanceKey BKE_node_instance_key(bNodeInstanceKey parent_key, bNodeTree *ntree, bNode *node)
2818 {
2819   bNodeInstanceKey key;
2820
2821   key = node_hash_int_str(parent_key, ntree->id.name + 2);
2822
2823   if (node)
2824     key = node_hash_int_str(key, node->name);
2825
2826   return key;
2827 }
2828
2829 static unsigned int node_instance_hash_key(const void *key)
2830 {
2831   return ((const bNodeInstanceKey *)key)->value;
2832 }
2833
2834 static bool node_instance_hash_key_cmp(const void *a, const void *b)
2835 {
2836   unsigned int value_a = ((const bNodeInstanceKey *)a)->value;
2837   unsigned int value_b = ((const bNodeInstanceKey *)b)->value;
2838
2839   return (value_a != value_b);
2840 }
2841
2842 bNodeInstanceHash *BKE_node_instance_hash_new(const char *info)
2843 {
2844   bNodeInstanceHash *hash = MEM_mallocN(sizeof(bNodeInstanceHash), info);
2845   hash->ghash = BLI_ghash_new(
2846       node_instance_hash_key, node_instance_hash_key_cmp, "node instance hash ghash");
2847   return hash;
2848 }
2849
2850 void BKE_node_instance_hash_free(bNodeInstanceHash *hash, bNodeInstanceValueFP valfreefp)
2851 {
2852   BLI_ghash_free(hash->ghash, NULL, (GHashValFreeFP)valfreefp);
2853   MEM_freeN(hash);
2854 }
2855
2856 void BKE_node_instance_hash_insert(bNodeInstanceHash *hash, bNodeInstanceKey key, void *value)
2857 {
2858   bNodeInstanceHashEntry *entry = value;
2859   entry->key = key;
2860   entry->tag = 0;
2861   BLI_ghash_insert(hash->ghash, &entry->key, value);
2862 }
2863
2864 void *BKE_node_instance_hash_lookup(bNodeInstanceHash *hash, bNodeInstanceKey key)
2865 {
2866   return BLI_ghash_lookup(hash->ghash, &key);
2867 }
2868
2869 int BKE_node_instance_hash_remove(bNodeInstanceHash *hash,
2870                                   bNodeInstanceKey key,
2871                                   bNodeInstanceValueFP valfreefp)
2872 {
2873   return BLI_ghash_remove(hash->ghash, &key, NULL, (GHashValFreeFP)valfreefp);
2874 }
2875
2876 void BKE_node_instance_hash_clear(bNodeInstanceHash *hash, bNodeInstanceValueFP valfreefp)
2877 {
2878   BLI_ghash_clear(hash->ghash, NULL, (GHashValFreeFP)valfreefp);
2879 }
2880
2881 void *BKE_node_instance_hash_pop(bNodeInstanceHash *hash, bNodeInstanceKey key)
2882 {
2883   return BLI_ghash_popkey(hash->ghash, &key, NULL);
2884 }
2885
2886 int BKE_node_instance_hash_haskey(bNodeInstanceHash *hash, bNodeInstanceKey key)
2887 {
2888   return BLI_ghash_haskey(hash->ghash, &key);
2889 }
2890
2891 int BKE_node_instance_hash_size(bNodeInstanceHash *hash)
2892 {
2893   return BLI_ghash_len(hash->ghash);
2894 }
2895
2896 void BKE_node_instance_hash_clear_tags(bNodeInstanceHash *hash)
2897 {
2898   bNodeInstanceHashIterator iter;
2899
2900   NODE_INSTANCE_HASH_ITER (iter, hash) {
2901     bNodeInstanceHashEntry *value = BKE_node_instance_hash_iterator_get_value(&iter);
2902
2903     value->tag = 0;
2904   }
2905 }
2906
2907 void BKE_node_instance_hash_tag(bNodeInstanceHash *UNUSED(hash), void *value)
2908 {
2909   bNodeInstanceHashEntry *entry = value;
2910   entry->tag = 1;
2911 }
2912
2913 bool BKE_node_instance_hash_tag_key(bNodeInstanceHash *hash, bNodeInstanceKey key)
2914 {
2915   bNodeInstanceHashEntry *entry = BKE_node_instance_hash_lookup(hash, key);
2916
2917   if (entry) {
2918     entry->tag = 1;
2919     return true;
2920   }
2921   else
2922     return false;
2923 }
2924
2925 void BKE_node_instance_hash_remove_untagged(bNodeInstanceHash *hash,
2926                                             bNodeInstanceValueFP valfreefp)
2927 {
2928   /* NOTE: Hash must not be mutated during iterating!
2929    * Store tagged entries in a separate list and remove items afterward.
2930    */
2931   bNodeInstanceKey *untagged = MEM_mallocN(sizeof(bNodeInstanceKey) *
2932                                                BKE_node_instance_hash_size(hash),
2933                                            "temporary node instance key list");
2934   bNodeInstanceHashIterator iter;
2935   int num_untagged, i;
2936
2937   num_untagged = 0;
2938   NODE_INSTANCE_HASH_ITER (iter, hash) {
2939     bNodeInstanceHashEntry *value = BKE_node_instance_hash_iterator_get_value(&iter);
2940
2941     if (!value->tag)
2942       untagged[num_untagged++] = BKE_node_instance_hash_iterator_get_key(&iter);
2943   }
2944
2945   for (i = 0; i < num_untagged; ++i) {
2946     BKE_node_instance_hash_remove(hash, untagged[i], valfreefp);
2947   }
2948
2949   MEM_freeN(untagged);
2950 }
2951
2952 /* ************** dependency stuff *********** */
2953
2954 /* node is guaranteed to be not checked before */
2955 static int node_get_deplist_recurs(bNodeTree *ntree, bNode *node, bNode ***nsort)
2956 {
2957   bNode *fromnode;
2958   bNodeLink *link;
2959   int level = 0xFFF;
2960
2961   node->done = true;
2962
2963   /* check linked nodes */
2964   for (link = ntree->links.first; link; link = link->next) {
2965     if (link->tonode == node) {
2966       fromnode = link->fromnode;
2967       if (fromnode->done == 0)
2968         fromnode->level = node_get_deplist_recurs(ntree, fromnode, nsort);
2969       if (fromnode->level <= level)
2970         level = fromnode->level - 1;
2971     }
2972   }
2973
2974   /* check parent node */
2975   if (node->parent) {
2976     if (node->parent->done == 0)
2977       node->parent->level = node_get_deplist_recurs(ntree, node->parent, nsort);
2978     if (node->parent->level <= level)
2979       level = node->parent->level - 1;
2980   }
2981
2982   if (nsort) {
2983     **nsort = node;
2984     (*nsort)++;
2985   }
2986
2987   return level;
2988 }
2989
2990 void ntreeGetDependencyList(struct bNodeTree *ntree, struct bNode ***deplist, int *totnodes)
2991 {
2992   bNode *node, **nsort;
2993
2994   *totnodes = 0;
2995
2996   /* first clear data */
2997   for (node = ntree->nodes.first; node; node = node->next) {
2998     node->done = false;
2999     (*totnodes)++;
3000   }
3001   if (*totnodes == 0) {
3002     *deplist = NULL;
3003     return;
3004   }
3005
3006   nsort = *deplist = MEM_callocN((*totnodes) * sizeof(bNode *), "sorted node array");
3007
3008   /* recursive check */
3009   for (node = ntree->nodes.first; node; node = node->next) {
3010     if (node->done == 0) {
3011       node->level = node_get_deplist_recurs(ntree, node, &nsort);
3012     }
3013   }
3014 }
3015
3016 /* only updates node->level for detecting cycles links */
3017 static void ntree_update_node_level(bNodeTree *ntree)
3018 {
3019   bNode *node;
3020
3021   /* first clear tag */
3022   for (node = ntree->nodes.first; node; node = node->next) {
3023     node->done = false;
3024   }
3025
3026   /* recursive check */
3027   for (node = ntree->nodes.first; node; node = node->next) {
3028     if (node->done == 0) {
3029       node->level = node_get_deplist_recurs(ntree, node, NULL);
3030     }
3031   }
3032 }
3033
3034 void ntreeTagUsedSockets(bNodeTree *ntree)
3035 {
3036   bNode *node;
3037   bNodeSocket *sock;
3038   bNodeLink *link;
3039
3040   /* first clear data */
3041   for (node = ntree->nodes.first; node; node = node->next) {
3042     for (sock = node->inputs.first; sock; sock = sock->next) {
3043       sock->flag &= ~SOCK_IN_USE;
3044     }
3045     for (sock = node->outputs.first; sock; sock = sock->next) {
3046       sock->flag &= ~SOCK_IN_USE;
3047     }
3048   }
3049
3050   for (link = ntree->links.first; link; link = link->next) {
3051     /* link is unused if either side is disabled */
3052     if ((link->fromsock->flag & SOCK_UNAVAIL) || (link->tosock->flag & SOCK_UNAVAIL))
3053       continue;
3054
3055     link->fromsock->flag |= SOCK_IN_USE;
3056     link->tosock->flag |= SOCK_IN_USE;
3057   }
3058 }
3059
3060 static void ntree_update_link_pointers(bNodeTree *ntree)
3061 {
3062   bNode *node;
3063   bNodeSocket *sock;
3064   bNodeLink *link;
3065
3066   /* first clear data */
3067   for (node = ntree->nodes.first; node; node = node->next) {
3068     for (sock = node->inputs.first; sock; sock = sock->next) {
3069       sock->link = NULL;
3070     }
3071   }
3072
3073   for (link = ntree->links.first; link; link = link->next) {
3074     link->tosock->link = link;
3075   }
3076
3077   ntreeTagUsedSockets(ntree);
3078 }
3079
3080 static void ntree_validate_links(bNodeTree *ntree)
3081 {
3082   bNodeLink *link;
3083
3084   for (link = ntree->links.first; link; link = link->next) {
3085     link->flag |= NODE_LINK_VALID;
3086     if (link->fromnode && link->tonode && link->fromnode->level <= link->tonode->level)
3087       link->flag &= ~NODE_LINK_VALID;
3088     else if (ntree->typeinfo->validate_link) {
3089       if (!ntree->typeinfo->validate_link(ntree, link))
3090         link->flag &= ~NODE_LINK_VALID;
3091     }
3092   }
3093 }
3094
3095 void ntreeVerifyNodes(struct Main *main, struct ID *id)
3096 {
3097   FOREACH_NODETREE_BEGIN (main, ntree, owner_id) {
3098     bNode *node;
3099
3100     for (node = ntree->nodes.first; node; node = node->next)
3101       if (node->typeinfo->verifyfunc)
3102         node->typeinfo->verifyfunc(ntree, node, id);
3103   }
3104   FOREACH_NODETREE_END;
3105 }
3106
3107 void ntreeUpdateTree(Main *bmain, bNodeTree *ntree)
3108 {
3109   bNode *node;
3110
3111   if (!ntree)
3112     return;
3113
3114   /* avoid reentrant updates, can be caused by RNA update callbacks */
3115   if (ntree->is_updating)
3116     return;
3117   ntree->is_updating = true;
3118
3119   if (ntree->update & (NTREE_UPDATE_LINKS | NTREE_UPDATE_NODES)) {
3120     /* set the bNodeSocket->link pointers */
3121     ntree_update_link_pointers(ntree);
3122   }
3123
3124   /* update individual nodes */
3125   for (node = ntree->nodes.first; node; node = node->next) {
3126     /* node tree update tags override individual node update flags */
3127     if ((node->update & NODE_UPDATE) || (ntree->update & NTREE_UPDATE)) {
3128       if (node->typeinfo->updatefunc)
3129         node->typeinfo->updatefunc(ntree, node);
3130
3131       nodeUpdateInternalLinks(ntree, node);
3132     }
3133   }
3134
3135   /* generic tree update callback */
3136   if (ntree->typeinfo->update)
3137     ntree->typeinfo->update(ntree);
3138   /* XXX this should be moved into the tree type update callback for tree supporting node groups.
3139    * Currently the node tree interface is still a generic feature of the base NodeTree type.
3140    */
3141   if (ntree->update & NTREE_UPDATE_GROUP)
3142     ntreeInterfaceTypeUpdate(ntree);
3143
3144   /* XXX hack, should be done by depsgraph!! */
3145   if (bmain)
3146     ntreeVerifyNodes(bmain, &ntree->id);
3147
3148   if (ntree->update & (NTREE_UPDATE_LINKS | NTREE_UPDATE_NODES)) {
3149     /* node updates can change sockets or links, repeat link pointer update afterward */
3150     ntree_update_link_pointers(ntree);
3151
3152     /* update the node level from link dependencies */
3153     ntree_update_node_level(ntree);
3154
3155     /* check link validity */
3156     ntree_validate_links(ntree);
3157   }
3158
3159   /* clear update flags */
3160   for (node = ntree->nodes.first; node; node = node->next) {
3161     node->update = 0;
3162   }
3163   ntree->update = 0;
3164
3165   ntree->is_updating = false;
3166 }
3167
3168 void nodeUpdate(bNodeTree *ntree, bNode *node)
3169 {
3170   /* avoid reentrant updates, can be caused by RNA update callbacks */
3171   if (ntree->is_updating)
3172     return;
3173   ntree->is_updating = true;
3174
3175   if (node->typeinfo->updatefunc)
3176     node->typeinfo->updatefunc(ntree, node);
3177
3178   nodeUpdateInternalLinks(ntree, node);
3179
3180   /* clear update flag */
3181   node->update = 0;
3182
3183   ntree->is_updating = false;
3184 }
3185
3186 bool nodeUpdateID(bNodeTree *ntree, ID *id)
3187 {
3188   bNode *node;
3189   bool changed = false;
3190
3191   if (ELEM(NULL, id, ntree))
3192     return changed;
3193
3194   /* avoid reentrant updates, can be caused by RNA update callbacks */
3195   if (ntree->is_updating)
3196     return changed;
3197   ntree->is_updating = true;
3198
3199   for (node = ntree->nodes.first; node; node = node->next) {
3200     if (node->id == id) {
3201       changed = true;
3202       node->update |= NODE_UPDATE_ID;
3203       if (node->typeinfo->updatefunc)
3204         node->typeinfo->updatefunc(ntree, node);
3205       /* clear update flag */
3206       node->update = 0;
3207     }
3208   }
3209
3210   for (node = ntree->nodes.first; node; node = node->next) {
3211     nodeUpdateInternalLinks(ntree, node);
3212   }
3213
3214   ntree->is_updating = false;
3215   return changed;
3216 }
3217
3218 void nodeUpdateInternalLinks(bNodeTree *ntree, bNode *node)
3219 {
3220   BLI_freelistN(&node->internal_links);
3221
3222   if (node->typeinfo && node->typeinfo->update_internal_links)
3223     node->typeinfo->update_internal_links(ntree, node);
3224 }
3225
3226 /* ************* node type access ********** */
3227
3228 void nodeLabel(bNodeTree *ntree, bNode *node, char *label, int maxlen)
3229 {
3230   label[0] = '\0';
3231
3232   if (node->label[0] != '\0') {
3233     BLI_strncpy(label, node->label, maxlen);
3234   }
3235   else if (node->typeinfo->labelfunc) {
3236     node->typeinfo->labelfunc(ntree, node, label, maxlen);
3237   }
3238
3239   /* The previous methods (labelfunc) could not provide an adequate label for the node. */
3240   if (label[0] == '\0') {
3241     /* Kind of hacky and weak... Ideally would be better to use RNA here. :| */
3242     const char *tmp = CTX_IFACE_(BLT_I18NCONTEXT_ID_NODETREE, node->typeinfo->ui_name);
3243     if (tmp == node->typeinfo->ui_name) {
3244       tmp = IFACE_(node->typeinfo->ui_name);
3245     }
3246     BLI_strncpy(label, tmp, maxlen);
3247   }
3248 }
3249
3250 static void node_type_base_defaults(bNodeType *ntype)
3251 {
3252   /* default size values */
3253   node_type_size_preset(ntype, NODE_SIZE_DEFAULT);
3254   ntype->height = 100;
3255   ntype->minheight = 30;
3256   ntype->maxheight = FLT_MAX;
3257 }
3258
3259 /* allow this node for any tree type */
3260 static bool node_poll_default(bNodeType *UNUSED(ntype), bNodeTree *UNUSED(ntree))
3261 {
3262   return true;
3263 }
3264
3265 /* use the basic poll function */
3266 static bool node_poll_instance_default(bNode *node, bNodeTree *ntree)
3267 {
3268   return node->typeinfo->poll(node->typeinfo, ntree);
3269 }
3270
3271 void node_type_base(bNodeType *ntype, int type, const char *name, short nclass, short flag)
3272 {
3273   /* Use static type info header to map static int type to identifier string and RNA struct type.
3274    * Associate the RNA struct type with the bNodeType.
3275    * Dynamically registered nodes will create an RNA type at runtime
3276    * and call RNA_struct_blender_type_set, so this only needs to be done for old RNA types
3277    * created in makesrna, which can not be associated to a bNodeType immediately,
3278    * since bNodeTypes are registered afterward ...
3279    */
3280 #define DefNode(Category, ID, DefFunc, EnumName, StructName, UIName, UIDesc) \
3281   case ID: \
3282     BLI_strncpy(ntype->idname, #Category #StructName, sizeof(ntype->idname)); \
3283     ntype->ext.srna = RNA_struct_find(#Category #StructName); \
3284     BLI_assert(ntype->ext.srna != NULL); \
3285     RNA_struct_blender_type_set(ntype->ext.srna, ntype); \
3286     break;
3287
3288   switch (type) {
3289 #include "NOD_static_types.h"
3290   }
3291
3292   /* make sure we have a valid type (everything registered) */
3293   BLI_assert(ntype->idname[0] != '\0');
3294
3295   ntype->type = type;
3296   BLI_strncpy(ntype->ui_name, name, sizeof(ntype->ui_name));
3297   ntype->nclass = nclass;
3298   ntype->flag = flag;
3299
3300   node_type_base_defaults(ntype);
3301
3302   ntype->poll = node_poll_default;
3303   ntype->poll_instance = node_poll_instance_default;
3304 }
3305
3306 void node_type_base_custom(
3307     bNodeType *ntype, const char *idname, const char *name, short nclass, short flag)
3308 {
3309   BLI_strncpy(ntype->idname, idname, sizeof(ntype->idname));
3310   ntype->type = NODE_CUSTOM;
3311   BLI_strncpy(ntype->ui_name, name, sizeof(ntype->ui_name));
3312   ntype->nclass = nclass;
3313   ntype->flag = flag;
3314
3315   node_type_base_defaults(ntype);
3316 }
3317
3318 static bool unique_socket_template_identifier_check(void *arg, const char *name)
3319 {
3320   bNodeSocketTemplate *ntemp;
3321   struct {
3322     bNodeSocketTemplate *list;
3323     bNodeSocketTemplate *ntemp;
3324   } *data = arg;
3325
3326   for (ntemp = data->list; ntemp->type >= 0; ++ntemp) {
3327     if (ntemp != data->ntemp) {
3328       if (STREQ(ntemp->identifier, name)) {
3329         return true;
3330       }
3331     }
3332   }
3333
3334   return false;
3335 }
3336
3337 static void unique_socket_template_identifier(bNodeSocketTemplate *list,
3338                                               bNodeSocketTemplate *ntemp,
3339                                               const char defname[],
3340                                               char delim)
3341 {
3342   struct {
3343     bNodeSocketTemplate *list;
3344     bNodeSocketTemplate *ntemp;
3345   } data;
3346   data.list = list;
3347   data.ntemp = ntemp;
3348
3349   BLI_uniquename_cb(unique_socket_template_identifier_check,
3350                     &data,
3351                     defname,
3352                     delim,
3353                     ntemp->identifier,
3354                     sizeof(ntemp->identifier));
3355 }
3356
3357 void node_type_socket_templates(struct bNodeType *ntype,
3358                                 struct bNodeSocketTemplate *inputs,
3359                                 struct bNodeSocketTemplate *outputs)
3360 {
3361   bNodeSocketTemplate *ntemp;
3362
3363   ntype->inputs = inputs;
3364   ntype->outputs = outputs;
3365
3366   /* automatically generate unique identifiers */
3367   if (inputs) {
3368     /* clear identifier strings (uninitialized memory) */
3369     for (ntemp = inputs; ntemp->type >= 0; ++ntemp)
3370       ntemp->identifier[0] = '\0';
3371
3372     for (ntemp = inputs; ntemp->type >= 0; ++ntemp) {
3373       BLI_strncpy(ntemp->identifier, ntemp->name, sizeof(ntemp->identifier));
3374       unique_socket_template_identifier(inputs, ntemp, ntemp->identifier, '_');
3375     }
3376   }
3377   if (outputs) {
3378     /* clear identifier strings (uninitialized memory) */
3379     for (ntemp = outputs; ntemp->type >= 0; ++ntemp)
3380       ntemp->identifier[0] = '\0';
3381
3382     for (ntemp = outputs; ntemp->type >= 0; ++ntemp) {
3383       BLI_strncpy(ntemp->identifier, ntemp->name, sizeof(ntemp->identifier));
3384       unique_socket_template_identifier(outputs, ntemp, ntemp->identifier, '_');
3385     }
3386   }
3387 }
3388
3389 void node_type_init(struct bNodeType *ntype,
3390                     void (*initfunc)(struct bNodeTree *ntree, struct bNode *node))
3391 {
3392   ntype->initfunc = initfunc;
3393 }
3394
3395 void node_type_size(struct bNodeType *ntype, int width, int minwidth, int maxwidth)
3396 {
3397   ntype->width = width;
3398   ntype->minwidth = minwidth;
3399   if (maxwidth <= minwidth)
3400     ntype->maxwidth = FLT_MAX;
3401   else
3402     ntype->maxwidth = maxwidth;
3403 }
3404
3405 void node_type_size_preset(struct bNodeType *ntype, eNodeSizePreset size)
3406 {
3407   switch (size) {
3408     case NODE_SIZE_DEFAULT:
3409       node_type_size(ntype, 140, 100, NODE_DEFAULT_MAX_WIDTH);
3410       break;
3411     case NODE_SIZE_SMALL:
3412       node_type_size(ntype, 100, 80, NODE_DEFAULT_MAX_WIDTH);
3413       break;
3414     case NODE_SIZE_MIDDLE:
3415       node_type_size(ntype, 150, 120, NODE_DEFAULT_MAX_WIDTH);
3416       break;
3417     case NODE_SIZE_LARGE:
3418       node_type_size(ntype, 240, 140, NODE_DEFAULT_MAX_WIDTH);
3419       break;
3420   }
3421 }
3422
3423 /**
3424  * \warning Nodes defining a storage type _must_ allocate this for new nodes.
3425  * Otherwise nodes will reload as undefined (T46619).
3426  */
3427 void node_type_storage(bNodeType *ntype,
3428                        const char *storagename,
3429                        void (*freefunc)(struct bNode *node),
3430                        void (*copyfunc)(struct bNodeTree *dest_ntree,
3431                                         struct bNode *dest_node,
3432                                         struct bNode *src_node))
3433 {
3434   if (storagename)
3435     BLI_strncpy(ntype->storagename, storagename, sizeof(ntype->storagename));
3436   else
3437     ntype->storagename[0] = '\0';
3438   ntype->copyfunc = copyfunc;
3439   ntype->freefunc = freefunc;
3440 }
3441
3442 void node_type_label(
3443     struct bNodeType *ntype,
3444     void (*labelfunc)(struct bNodeTree *ntree, struct bNode *node, char *label, int maxlen))
3445 {
3446   ntype->labelfunc = labelfunc;
3447 }
3448
3449 void node_type_update(struct bNodeType *ntype,
3450                       void (*updatefunc)(struct bNodeTree *ntree, struct bNode *node),
3451                       void (*verifyfunc)(struct bNodeTree *ntree,
3452                                          struct bNode *node,
3453                                          struct ID *id))
3454 {
3455   ntype->updatefunc = updatefunc;
3456   ntype->verifyfunc = verifyfunc;
3457 }
3458
3459 void node_type_exec(struct bNodeType *ntype,
3460                     NodeInitExecFunction initexecfunc,
3461                     NodeFreeExecFunction freeexecfunc,
3462                     NodeExecFunction execfunc)
3463 {
3464   ntype->initexecfunc = initexecfunc;
3465   ntype->freeexecfunc = freeexecfunc;
3466   ntype->execfunc = execfunc;
3467 }
3468
3469 void node_type_gpu(struct bNodeType *ntype, NodeGPUExecFunction gpufunc)
3470 {
3471   ntype->gpufunc = gpufunc;
3472 }
3473
3474 void node_type_internal_links(bNodeType *ntype,
3475                               void (*update_internal_links)(bNodeTree *, bNode *))
3476 {
3477   ntype->update_internal_links = update_internal_links;
3478 }
3479
3480 /* callbacks for undefined types */
3481
3482 static bool node_undefined_poll(bNodeType *UNUSED(ntype), bNodeTree *UNUSED(nodetree))
3483 {
3484   /* this type can not be added deliberately, it's just a placeholder */
3485   return false;
3486 }
3487
3488 /* register fallback types used for undefined tree, nodes, sockets */
3489 static void register_undefined_types(void)
3490 {
3491   /* Note: these types are not registered in the type hashes,
3492    * they are just used as placeholders in case the actual types are not registered.
3493    */
3494
3495   strcpy(NodeTreeTypeUndefined.idname, "NodeTreeUndefined");
3496   strcpy(NodeTreeTypeUndefined.ui_name, N_("Undefined"));
3497   strcpy(NodeTreeTypeUndefined.ui_description, N_("Undefined Node Tree Type"));
3498
3499   node_type_base_custom(&NodeTypeUndefined, "NodeUndefined", "Undefined", 0, 0);
3500   NodeTypeUndefined.poll = node_undefined_poll;
3501
3502   BLI_strncpy(NodeSocketTypeUndefined.idname,
3503               "NodeSocketUndefined",
3504               sizeof(NodeSocketTypeUndefined.idname));
3505   /* extra type info for standard socket types */
3506   NodeSocketTypeUndefined.type = SOCK_CUSTOM;
3507   NodeSocketTypeUndefined.subtype = PROP_NONE;
3508 }
3509
3510 static void registerCompositNodes(void)
3511 {
3512   register_node_type_cmp_group();
3513
3514   register_node_type_cmp_rlayers();
3515   register_node_type_cmp_image();
3516   register_node_type_cmp_texture();
3517   register_node_type_cmp_value();
3518   register_node_type_cmp_rgb();
3519   register_node_type_cmp_curve_time();
3520   register_node_type_cmp_movieclip();
3521
3522   register_node_type_cmp_composite();
3523   register_node_type_cmp_viewer();
3524   register_node_type_cmp_splitviewer();
3525   register_node_type_cmp_output_file();
3526   register_node_type_cmp_view_levels();
3527
3528   register_node_type_cmp_curve_rgb();
3529   register_node_type_cmp_mix_rgb();
3530   register_node_type_cmp_hue_sat();
3531   register_node_type_cmp_brightcontrast();
3532   register_node_type_cmp_gamma();
3533   register_node_type_cmp_invert();
3534   register_node_type_cmp_alphaover();
3535   register_node_type_cmp_zcombine();
3536   register_node_type_cmp_colorbalance();
3537   register_node_type_cmp_huecorrect();
3538
3539   register_node_type_cmp_normal();
3540   register_node_type_cmp_curve_vec();
3541   register_node_type_cmp_map_value();
3542   register_node_type_cmp_map_range();
3543   register_node_type_cmp_normalize();
3544
3545   register_node_type_cmp_filter();
3546   register_node_type_cmp_blur();
3547   register_node_type_cmp_dblur();
3548   register_node_type_cmp_bilateralblur();
3549   register_node_type_cmp_vecblur();
3550   register_node_type_cmp_dilateerode();
3551   register_node_type_cmp_inpaint();
3552   register_node_type_cmp_despeckle();
3553   register_node_type_cmp_defocus();
3554   register_node_type_cmp_sunbeams();
3555
3556   register_node_type_cmp_valtorgb();
3557   register_node_type_cmp_rgbtobw();
3558   register_node_type_cmp_setalpha();
3559   register_node_type_cmp_idmask();
3560   register_node_type_cmp_math();
3561   register_node_type_cmp_seprgba();
3562   register_node_type_cmp_combrgba();
3563   register_node_type_cmp_sephsva();
3564   register_node_type_cmp_combhsva();
3565   register_node_type_cmp_sepyuva();
3566   register_node_type_cmp_combyuva();
3567   register_node_type_cmp_sepycca();
3568   register_node_type_cmp_combycca();
3569   register_node_type_cmp_premulkey();
3570
3571   register_node_type_cmp_diff_matte();
3572   register_node_type_cmp_distance_matte();
3573   register_node_type_cmp_chroma_matte();
3574   register_node_type_cmp_color_matte();
3575   register_node_type_cmp_channel_matte();
3576   register_node_type_cmp_color_spill();
3577   register_node_type_cmp_luma_matte();
3578   register_node_type_cmp_doubleedgemask();
3579   register_node_type_cmp_keyingscreen();
3580   register_node_type_cmp_keying();
3581   register_node_type_cmp_cryptomatte();
3582
3583   register_node_type_cmp_translate();
3584   register_node_type_cmp_rotate();
3585   register_node_type_cmp_scale();
3586   register_node_type_cmp_flip();
3587   register_node_type_cmp_crop();
3588   register_node_type_cmp_displace();
3589   register_node_type_cmp_mapuv();
3590   register_node_type_cmp_glare();
3591   register_node_type_cmp_tonemap();
3592   register_node_type_cmp_lensdist();
3593   register_node_type_cmp_transform();
3594   register_node_type_cmp_stabilize2d();
3595   register_node_type_cmp_moviedistortion();
3596
3597   register_node_type_cmp_colorcorrection();
3598   register_node_type_cmp_boxmask();
3599   register_node_type_cmp_ellipsemask();
3600   register_node_type_cmp_bokehimage();
3601   register_node_type_cmp_bokehblur();
3602   register_node_type_cmp_switch();
3603   register_node_type_cmp_switch_view();
3604   register_node_type_cmp_pixelate();
3605
3606   register_node_type_cmp_mask();
3607   register_node_type_cmp_trackpos();
3608   register_node_type_cmp_planetrackdeform();
3609   register_node_type_cmp_cornerpin();
3610 }
3611
3612 static void registerShaderNodes(void)
3613 {
3614   register_node_type_sh_group();
3615
3616   register_node_type_sh_camera();
3617   register_node_type_sh_gamma();
3618   register_node_type_sh_brightcontrast();
3619   register_node_type_sh_value();
3620   register_node_type_sh_rgb();
3621   register_node_type_sh_wireframe();
3622   register_node_type_sh_wavelength();
3623   register_node_type_sh_blackbody();
3624   register_node_type_sh_mix_rgb();
3625   register_node_type_sh_valtorgb();
3626   register_node_type_sh_rgbtobw();
3627   register_node_type_sh_shadertorgb();
3628   register_node_type_sh_normal();
3629   register_node_type_sh_mapping();
3630   register_node_type_sh_curve_vec();
3631   register_node_type_sh_curve_rgb();
3632   register_node_type_sh_math();
3633   register_node_type_sh_vect_math();
3634   register_node_type_sh_vect_transform();
3635   register_node_type_sh_squeeze();
3636   register_node_type_sh_invert();
3637   register_node_type_sh_seprgb();
3638   register_node_type_sh_combrgb();
3639   register_node_type_sh_sephsv();
3640   register_node_type_sh_combhsv();
3641   register_node_type_sh_sepxyz();
3642   register_node_type_sh_combxyz();
3643   register_node_type_sh_hue_sat();
3644
3645   register_node_type_sh_attribute();
3646   register_node_type_sh_bevel();
3647   register_node_type_sh_displacement();
3648   register_node_type_sh_vector_displacement();
3649   register_node_type_sh_geometry();
3650   register_node_type_sh_light_path();
3651   register_node_type_sh_light_falloff();
3652   register_node_type_sh_object_info();
3653   register_node_type_sh_fresnel();
3654   register_node_type_sh_layer_weight();
3655   register_node_type_sh_tex_coord();
3656   register_node_type_sh_particle_info();
3657   register_node_type_sh_bump();
3658
3659   register_node_type_sh_background();
3660   register_node_type_sh_bsdf_anisotropic();
3661   register_node_type_sh_bsdf_diffuse();
3662   register_node_type_sh_bsdf_principled();
3663   register_node_type_sh_bsdf_glossy();
3664   register_node_type_sh_bsdf_glass();
3665   register_node_type_sh_bsdf_translucent();
3666   register_node_type_sh_bsdf_transparent();
3667   register_node_type_sh_bsdf_velvet();
3668   register_node_type_sh_bsdf_toon();
3669   register_node_type_sh_bsdf_hair();
3670   register_node_type_sh_bsdf_hair_principled();
3671   register_node_type_sh_emission();
3672   register_node_type_sh_holdout();
3673   register_node_type_sh_volume_absorption();
3674   register_node_type_sh_volume_scatter();
3675   register_node_type_sh_volume_principled();
3676   register_node_type_sh_subsurface_scattering();
3677   register_node_type_sh_mix_shader();
3678   register_node_type_sh_add_shader();
3679   register_node_type_sh_uvmap();
3680   register_node_type_sh_uvalongstroke();
3681   register_node_type_sh_eevee_specular();
3682
3683   register_node_type_sh_output_light();
3684   register_node_type_sh_output_material();
3685   register_node_type_sh_output_world();
3686   register_node_type_sh_output_linestyle();
3687
3688   register_node_type_sh_tex_image();
3689   register_node_type_sh_tex_environment();
3690   register_node_type_sh_tex_sky();
3691   register_node_type_sh_tex_noise();
3692   register_node_type_sh_tex_wave();
3693   register_node_type_sh_tex_voronoi();
3694   register_node_type_sh_tex_musgrave();
3695   register_node_type_sh_tex_gradient();
3696   register_node_type_sh_tex_magic();
3697   register_node_type_sh_tex_checker();
3698   register_node_type_sh_tex_brick();
3699   register_node_type_sh_tex_pointdensity();
3700   register_node_type_sh_tex_ies();
3701 }
3702
3703 static void registerTextureNodes(void)
3704 {
3705   register_node_type_tex_group();
3706
3707   register_node_type_tex_math();
3708   register_node_type_tex_mix_rgb();
3709   register_node_type_tex_valtorgb();
3710   register_node_type_tex_rgbtobw();
3711   register_node_type_tex_valtonor();
3712   register_node_type_tex_curve_rgb();
3713   register_node_type_tex_curve_time();
3714   register_node_type_tex_invert();
3715   register_node_type_tex_hue_sat();
3716   register_node_type_tex_coord();
3717   register_node_type_tex_distance();
3718   register_node_type_tex_compose();
3719   register_node_type_tex_decompose();
3720
3721   register_node_type_tex_output();
3722   register_node_type_tex_viewer();
3723   register_node_type_sh_script();
3724   register_node_type_sh_tangent();
3725   register_node_type_sh_normal_map();
3726   register_node_type_sh_hair_info();
3727
3728   register_node_type_tex_checker();
3729   register_node_type_tex_texture();
3730   register_node_type_tex_bricks();
3731   register_node_type_tex_image();
3732   register_node_type_sh_bsdf_refraction();
3733   register_node_type_sh_ambient_occlusion();
3734
3735   register_node_type_tex_rotate();
3736   register_node_type_tex_translate();
3737   register_node_type_tex_scale();
3738   register_node_type_tex_at();
3739
3740   register_node_type_tex_proc_voronoi();
3741   register_node_type_tex_proc_blend();
3742   register_node_type_tex_proc_magic();
3743   register_node_type_tex_proc_marble();
3744   register_node_type_tex_proc_clouds();
3745   register_node_type_tex_proc_wood();
3746   register_node_type_tex_proc_musgrave();
3747   register_node_type_tex_proc_noise();
3748   register_node_type_tex_proc_stucci();
3749   register_node_type_tex_proc_distnoise();
3750 }
3751
3752 void init_nodesystem(void)
3753 {
3754   nodetreetypes_hash = BLI_ghash_str_new("nodetreetypes_hash gh");
3755   nodetypes_hash = BLI_ghash_str_new("nodetypes_hash gh");
3756   nodesockettypes_hash = BLI_ghash_str_new("nodesockettypes_hash gh");
3757   BLI_spin_init(&spin);
3758
3759   register_undefined_types();
3760
3761   register_standard_node_socket_types();
3762
3763   register_node_tree_type_cmp();
3764   register_node_tree_type_sh();
3765   register_node_tree_type_tex();
3766
3767   register_node_type_frame();
3768   register_node_type_reroute();
3769   register_node_type_group_input();
3770   register_node_type_group_output();
3771
3772   registerCompositNodes();
3773   registerShaderNodes();
3774   registerTextureNodes();
3775 }
3776
3777 void free_nodesystem(void)
3778 {
3779   if (nodetypes_hash) {
3780     NODE_TYPES_BEGIN (nt) {
3781       if (nt->ext.free) {
3782         nt->ext.free(nt->ext.data);
3783       }
3784     }
3785     NODE_TYPES_END;
3786
3787     BLI_ghash_free(nodetypes_hash, NULL, node_free_type);
3788     nodetypes_hash = NULL;
3789   }
3790
3791   if (nodesockettypes_hash) {
3792     NODE_SOCKET_TYPES_BEGIN (st) {
3793       if (st->ext_socket.free)
3794         st->ext_socket.free(st->ext_socket.data);
3795       if (st->ext_interface.free)
3796         st->ext_interface.free(st->ext_interface.data);
3797     }
3798     NODE_SOCKET_TYPES_END;
3799
3800     BLI_ghash_free(nodesockettypes_hash, NULL, node_free_socket_type);
3801     nodesockettypes_hash = NULL;
3802   }
3803
3804   if (nodetreetypes_hash) {
3805     NODE_TREE_TYPES_BEGIN (nt) {
3806       if (nt->ext.free) {
3807         nt->ext.free(nt->ext.data);
3808       }
3809     }
3810     NODE_TREE_TYPES_END;
3811
3812     BLI_ghash_free(nodetreetypes_hash, NULL, ntree_free_type);
3813     nodetreetypes_hash = NULL;
3814   }
3815 }
3816
3817 /* -------------------------------------------------------------------- */
3818 /* NodeTree Iterator Helpers (FOREACH_NODETREE_BEGIN) */
3819
3820 void BKE_node_tree_iter_init(struct NodeTreeIterStore *ntreeiter, struct Main *bmain)
3821 {
3822   ntreeiter->ngroup = bmain->nodetrees.first;
3823   ntreeiter->scene = bmain->scenes.first;
3824   ntreeiter->mat = bmain->materials.first;
3825   ntreeiter->tex = bmain->textures.first;
3826   ntreeiter->light = bmain->lights.first;
3827   ntreeiter->world = bmain->worlds.first;
3828   ntreeiter->linestyle = bmain->linestyles.first;
3829 }
3830 bool BKE_node_tree_iter_step(struct NodeTreeIterStore *ntreeiter,
3831                              bNodeTree **r_nodetree,
3832                              struct ID **r_id)
3833 {
3834   if (ntreeiter->ngroup) {
3835     *r_nodetree = ntreeiter->ngroup;
3836     *r_id = (ID *)ntreeiter->ngroup;
3837     ntreeiter->ngroup = ntreeiter->ngroup->id.next;
3838   }
3839   else if (ntreeiter->scene) {
3840     *r_nodetree = ntreeiter->scene->nodetree;
3841     *r_id = (ID *)ntreeiter->scene;
3842     ntreeiter->scene = ntreeiter->scene->id.next;
3843   }
3844   else if (ntreeiter->mat) {
3845     *r_nodetree = ntreeiter->mat->nodetree;
3846     *r_id = (ID *)ntreeiter->mat;
3847     ntreeiter->mat = ntreeiter->mat->id.next;
3848   }