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