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