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