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