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