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