Cycles Volume Render: support for rendering of homogeneous volume with absorption.
[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_node_types.h"
45 #include "DNA_scene_types.h"
46 #include "DNA_texture_types.h"
47 #include "DNA_world_types.h"
48
49 #include "BLI_string.h"
50 #include "BLI_math.h"
51 #include "BLI_listbase.h"
52 #include "BLI_path_util.h"
53 #include "BLI_utildefines.h"
54
55 #include "BLF_translation.h"
56
57 #include "BKE_animsys.h"
58 #include "BKE_action.h"
59 #include "BKE_fcurve.h"
60 #include "BKE_global.h"
61 #include "BKE_idprop.h"
62 #include "BKE_image.h"
63 #include "BKE_library.h"
64 #include "BKE_main.h"
65 #include "BKE_node.h"
66
67 #include "BLI_ghash.h"
68 #include "RNA_access.h"
69 #include "RNA_define.h"
70
71 #include "NOD_socket.h"
72 #include "NOD_common.h"
73 #include "NOD_composite.h"
74 #include "NOD_shader.h"
75 #include "NOD_texture.h"
76
77 /* Fallback types for undefined tree, nodes, sockets */
78 bNodeTreeType NodeTreeTypeUndefined;
79 bNodeType NodeTypeUndefined;
80 bNodeSocketType NodeSocketTypeUndefined;
81
82
83 static void node_add_sockets_from_type(bNodeTree *ntree, bNode *node, bNodeType *ntype)
84 {
85         bNodeSocketTemplate *sockdef;
86         /* bNodeSocket *sock; */ /* UNUSED */
87
88         if (ntype->inputs) {
89                 sockdef = ntype->inputs;
90                 while (sockdef->type != -1) {
91                         /* sock = */ node_add_socket_from_template(ntree, node, sockdef, SOCK_IN);
92                         
93                         sockdef++;
94                 }
95         }
96         if (ntype->outputs) {
97                 sockdef = ntype->outputs;
98                 while (sockdef->type != -1) {
99                         /* sock = */ node_add_socket_from_template(ntree, node, sockdef, SOCK_OUT);
100                         
101                         sockdef++;
102                 }
103         }
104 }
105
106 /* Note: This function is called to initialize node data based on the type.
107  * The bNodeType may not be registered at creation time of the node,
108  * so this can be delayed until the node type gets registered.
109  */
110 static void node_init(const struct bContext *C, bNodeTree *ntree, bNode *node)
111 {
112         bNodeType *ntype = node->typeinfo;
113         if (ntype == &NodeTypeUndefined)
114                 return;
115         
116         /* only do this once */
117         if (node->flag & NODE_INIT)
118                 return;
119         
120         node->flag = NODE_SELECT | NODE_OPTIONS | ntype->flag;
121         node->width = ntype->width;
122         node->miniwidth = 42.0f;
123         node->height = ntype->height;
124         node->color[0] = node->color[1] = node->color[2] = 0.608;   /* default theme color */
125         /* initialize the node name with the node label.
126          * note: do this after the initfunc so nodes get their data set which may be used in naming
127          * (node groups for example) */
128         /* XXX Do not use nodeLabel() here, it returns translated content for UI, which should *only* be used
129          *     in UI, *never* in data... Data have their own translation option!
130          *     This solution may be a bit rougher than nodeLabel()'s returned string, but it's simpler
131          *     than adding "do_translate" flags to this func (and labelfunc() as well). */
132         BLI_strncpy(node->name, DATA_(ntype->ui_name), NODE_MAXSTR);
133         nodeUniqueName(ntree, node);
134         
135         node_add_sockets_from_type(ntree, node, ntype);
136
137         if (ntype->initfunc != NULL)
138                 ntype->initfunc(ntree, node);
139
140         if (ntree->typeinfo->node_add_init != NULL)
141                 ntree->typeinfo->node_add_init(ntree, node);
142
143         /* extra init callback */
144         if (ntype->initfunc_api) {
145                 PointerRNA ptr;
146                 RNA_pointer_create((ID *)ntree, &RNA_Node, node, &ptr);
147                 
148                 /* XXX Warning: context can be NULL in case nodes are added in do_versions.
149                  * Delayed init is not supported for nodes with context-based initfunc_api atm.
150                  */
151                 BLI_assert(C != NULL);
152                 ntype->initfunc_api(C, &ptr);
153         }
154         
155         if (node->id)
156                 id_us_plus(node->id);
157         
158         node->flag |= NODE_INIT;
159 }
160
161 static void ntree_set_typeinfo(bNodeTree *ntree, bNodeTreeType *typeinfo)
162 {
163         if (typeinfo) {
164                 ntree->typeinfo = typeinfo;
165                 
166                 /* deprecated integer type */
167                 ntree->type = typeinfo->type;
168         }
169         else {
170                 ntree->typeinfo = &NodeTreeTypeUndefined;
171                 
172                 ntree->init &= ~NTREE_TYPE_INIT;
173         }
174 }
175
176 static void node_set_typeinfo(const struct bContext *C, bNodeTree *ntree, bNode *node, bNodeType *typeinfo)
177 {
178         if (typeinfo) {
179                 node->typeinfo = typeinfo;
180                 
181                 /* deprecated integer type */
182                 node->type = typeinfo->type;
183                 
184                 /* initialize the node if necessary */
185                 node_init(C, ntree, node);
186         }
187         else {
188                 node->typeinfo = &NodeTypeUndefined;
189                 
190                 ntree->init &= ~NTREE_TYPE_INIT;
191         }
192 }
193
194 static void node_socket_set_typeinfo(bNodeTree *ntree, bNodeSocket *sock, bNodeSocketType *typeinfo)
195 {
196         if (typeinfo) {
197                 sock->typeinfo = typeinfo;
198                 
199                 /* deprecated integer type */
200                 sock->type = typeinfo->type;
201                 
202                 if (sock->default_value == NULL) {
203                         /* initialize the default_value pointer used by standard socket types */
204                         node_socket_init_default_value(sock);
205                 }
206         }
207         else {
208                 sock->typeinfo = &NodeSocketTypeUndefined;
209                 
210                 ntree->init &= ~NTREE_TYPE_INIT;
211         }
212 }
213
214 /* Set specific typeinfo pointers in all node trees on register/unregister */
215 static void update_typeinfo(Main *bmain, const struct bContext *C, bNodeTreeType *treetype, bNodeType *nodetype, bNodeSocketType *socktype, bool unregister)
216 {
217         if (!bmain)
218                 return;
219         
220         FOREACH_NODETREE(bmain, ntree, id) {
221                 bNode *node;
222                 bNodeSocket *sock;
223                 
224                 ntree->init |= NTREE_TYPE_INIT;
225                 
226                 if (treetype && STREQ(ntree->idname, treetype->idname))
227                         ntree_set_typeinfo(ntree, unregister ? NULL : treetype);
228                 
229                 /* initialize nodes */
230                 for (node = ntree->nodes.first; node; node = node->next) {
231                         if (nodetype && STREQ(node->idname, nodetype->idname))
232                                 node_set_typeinfo(C, ntree, node, unregister ? NULL : nodetype);
233                         
234                         /* initialize node sockets */
235                         for (sock = node->inputs.first; sock; sock = sock->next)
236                                 if (socktype && STREQ(sock->idname, socktype->idname))
237                                         node_socket_set_typeinfo(ntree, sock, unregister ? NULL : socktype);
238                         for (sock = node->outputs.first; sock; sock = sock->next)
239                                 if (socktype && STREQ(sock->idname, socktype->idname))
240                                         node_socket_set_typeinfo(ntree, sock, unregister ? NULL : socktype);
241                 }
242                 
243                 /* initialize tree sockets */
244                 for (sock = ntree->inputs.first; sock; sock = sock->next)
245                         if (socktype && STREQ(sock->idname, socktype->idname))
246                                 node_socket_set_typeinfo(ntree, sock, unregister ? NULL : socktype);
247                 for (sock = ntree->outputs.first; sock; sock = sock->next)
248                         if (socktype && STREQ(sock->idname, socktype->idname))
249                                 node_socket_set_typeinfo(ntree, sock, unregister ? NULL : socktype);
250         }
251         FOREACH_NODETREE_END
252 }
253
254 /* Try to initialize all typeinfo in a node tree.
255  * NB: In general undefined typeinfo is a perfectly valid case, the type may just be registered later.
256  * In that case the update_typeinfo function will set typeinfo on registration
257  * and do necessary updates.
258  */
259 void ntreeSetTypes(const struct bContext *C, bNodeTree *ntree)
260 {
261         bNode *node;
262         bNodeSocket *sock;
263         
264         ntree->init |= NTREE_TYPE_INIT;
265         
266         ntree_set_typeinfo(ntree, ntreeTypeFind(ntree->idname));
267         
268         for (node = ntree->nodes.first; node; node = node->next) {
269                 node_set_typeinfo(C, ntree, node, nodeTypeFind(node->idname));
270                 
271                 for (sock = node->inputs.first; sock; sock = sock->next)
272                         node_socket_set_typeinfo(ntree, sock, nodeSocketTypeFind(sock->idname));
273                 for (sock = node->outputs.first; sock; sock = sock->next)
274                         node_socket_set_typeinfo(ntree, sock, nodeSocketTypeFind(sock->idname));
275         }
276         
277         for (sock = ntree->inputs.first; sock; sock = sock->next)
278                 node_socket_set_typeinfo(ntree, sock, nodeSocketTypeFind(sock->idname));
279         for (sock = ntree->outputs.first; sock; sock = sock->next)
280                 node_socket_set_typeinfo(ntree, sock, nodeSocketTypeFind(sock->idname));
281 }
282
283
284 static GHash *nodetreetypes_hash = NULL;
285 static GHash *nodetypes_hash = NULL;
286 static GHash *nodesockettypes_hash = NULL;
287
288 bNodeTreeType *ntreeTypeFind(const char *idname)
289 {
290         bNodeTreeType *nt;
291
292         if (idname[0]) {
293                 nt = BLI_ghash_lookup(nodetreetypes_hash, idname);
294                 if (nt)
295                         return nt;
296         }
297
298         return NULL;
299 }
300
301 void ntreeTypeAdd(bNodeTreeType *nt)
302 {
303         BLI_ghash_insert(nodetreetypes_hash, (void *)nt->idname, nt);
304         /* XXX pass Main to register function? */
305         update_typeinfo(G.main, NULL, nt, NULL, NULL, false);
306 }
307
308 /* callback for hash value free function */
309 static void ntree_free_type(void *treetype_v)
310 {
311         bNodeTreeType *treetype = treetype_v;
312         /* XXX pass Main to unregister function? */
313         update_typeinfo(G.main, NULL, treetype, NULL, NULL, true);
314         MEM_freeN(treetype);
315 }
316
317 void ntreeTypeFreeLink(bNodeTreeType *nt)
318 {
319         BLI_ghash_remove(nodetreetypes_hash, nt->idname, NULL, ntree_free_type);
320 }
321
322 bool ntreeIsRegistered(bNodeTree *ntree)
323 {
324         return (ntree->typeinfo != &NodeTreeTypeUndefined);
325 }
326
327 GHashIterator *ntreeTypeGetIterator(void)
328 {
329         return BLI_ghashIterator_new(nodetreetypes_hash);
330 }
331
332 bNodeType *nodeTypeFind(const char *idname)
333 {
334         bNodeType *nt;
335
336         if (idname[0]) {
337                 nt = BLI_ghash_lookup(nodetypes_hash, idname);
338                 if (nt)
339                         return nt;
340         }
341
342         return NULL;
343 }
344
345 static void free_dynamic_typeinfo(bNodeType *ntype)
346 {
347         if (ntype->type == NODE_DYNAMIC) {
348                 if (ntype->inputs) {
349                         MEM_freeN(ntype->inputs);
350                 }
351                 if (ntype->outputs) {
352                         MEM_freeN(ntype->outputs);
353                 }
354         }
355 }
356
357 /* callback for hash value free function */
358 static void node_free_type(void *nodetype_v)
359 {
360         bNodeType *nodetype = nodetype_v;
361         /* XXX pass Main to unregister function? */
362         update_typeinfo(G.main, NULL, NULL, nodetype, NULL, true);
363         
364         /* XXX deprecated */
365         if (nodetype->type == NODE_DYNAMIC)
366                 free_dynamic_typeinfo(nodetype);
367         
368         if (nodetype->needs_free)
369                 MEM_freeN(nodetype);
370 }
371
372 void nodeRegisterType(bNodeType *nt)
373 {
374         /* debug only: basic verification of registered types */
375         BLI_assert(nt->idname[0] != '\0');
376         BLI_assert(nt->poll != NULL);
377         
378         BLI_ghash_insert(nodetypes_hash, (void *)nt->idname, nt);
379         /* XXX pass Main to register function? */
380         update_typeinfo(G.main, NULL, NULL, nt, NULL, false);
381 }
382
383 void nodeUnregisterType(bNodeType *nt)
384 {
385         BLI_ghash_remove(nodetypes_hash, nt->idname, NULL, node_free_type);
386 }
387
388 bool nodeIsRegistered(bNode *node)
389 {
390         return (node->typeinfo != &NodeTypeUndefined);
391 }
392
393 GHashIterator *nodeTypeGetIterator(void)
394 {
395         return BLI_ghashIterator_new(nodetypes_hash);
396 }
397
398 bNodeSocketType *nodeSocketTypeFind(const char *idname)
399 {
400         bNodeSocketType *st;
401
402         if (idname[0]) {
403                 st = BLI_ghash_lookup(nodesockettypes_hash, idname);
404                 if (st)
405                         return st;
406         }
407
408         return NULL;
409 }
410
411 /* callback for hash value free function */
412 static void node_free_socket_type(void *socktype_v)
413 {
414         bNodeSocketType *socktype = socktype_v;
415         /* XXX pass Main to unregister function? */
416         update_typeinfo(G.main, NULL, NULL, NULL, socktype, true);
417         
418         MEM_freeN(socktype);
419 }
420
421 void nodeRegisterSocketType(bNodeSocketType *st)
422 {
423         BLI_ghash_insert(nodesockettypes_hash, (void *)st->idname, st);
424         /* XXX pass Main to register function? */
425         update_typeinfo(G.main, NULL, NULL, NULL, st, false);
426 }
427
428 void nodeUnregisterSocketType(bNodeSocketType *st)
429 {
430         BLI_ghash_remove(nodesockettypes_hash, st->idname, NULL, node_free_socket_type);
431 }
432
433 bool nodeSocketIsRegistered(bNodeSocket *sock)
434 {
435         return (sock->typeinfo != &NodeSocketTypeUndefined);
436 }
437
438 GHashIterator *nodeSocketTypeGetIterator(void)
439 {
440         return BLI_ghashIterator_new(nodesockettypes_hash);
441 }
442
443 struct bNodeSocket *nodeFindSocket(bNode *node, int in_out, const char *identifier)
444 {
445         bNodeSocket *sock = (in_out == SOCK_IN ? node->inputs.first : node->outputs.first);
446         for (; sock; sock = sock->next) {
447                 if (STREQ(sock->identifier, identifier))
448                         return sock;
449         }
450         return NULL;
451 }
452
453 /* find unique socket identifier */
454 static bool unique_identifier_check(void *arg, const char *identifier)
455 {
456         struct ListBase *lb = arg;
457         bNodeSocket *sock;
458         for (sock = lb->first; sock; sock = sock->next) {
459                 if (STREQ(sock->identifier, identifier))
460                         return true;
461         }
462         return false;
463 }
464
465 static bNodeSocket *make_socket(bNodeTree *ntree, bNode *UNUSED(node), int in_out, ListBase *lb,
466                                 const char *idname, const char *identifier, const char *name)
467 {
468         bNodeSocket *sock;
469         char auto_identifier[MAX_NAME];
470         
471         if (identifier && identifier[0] != '\0') {
472                 /* use explicit identifier */
473                 BLI_strncpy(auto_identifier, identifier, sizeof(auto_identifier));
474         }
475         else {
476                 /* if no explicit identifier is given, assign a unique identifier based on the name */
477                 BLI_strncpy(auto_identifier, name, sizeof(auto_identifier));
478         }
479         /* make the identifier unique */
480         BLI_uniquename_cb(unique_identifier_check, lb, "socket", '.', auto_identifier, sizeof(auto_identifier));
481         
482         sock = MEM_callocN(sizeof(bNodeSocket), "sock");
483         sock->in_out = in_out;
484         
485         BLI_strncpy(sock->identifier, auto_identifier, NODE_MAXSTR);
486         sock->limit = (in_out == SOCK_IN ? 1 : 0xFFF);
487         
488         BLI_strncpy(sock->name, name, NODE_MAXSTR);
489         sock->storage = NULL;
490         sock->flag |= SOCK_COLLAPSED;
491         sock->type = SOCK_CUSTOM;       /* int type undefined by default */
492         
493         BLI_strncpy(sock->idname, idname, sizeof(sock->idname));
494         node_socket_set_typeinfo(ntree, sock, nodeSocketTypeFind(idname));
495         
496         return sock;
497 }
498
499 bNodeSocket *nodeAddSocket(bNodeTree *ntree, bNode *node, int in_out, const char *idname,
500                            const char *identifier, const char *name)
501 {
502         ListBase *lb = (in_out == SOCK_IN ? &node->inputs : &node->outputs);
503         bNodeSocket *sock = make_socket(ntree, node, in_out, lb, idname, identifier, name);
504         
505         BLI_remlink(lb, sock);  /* does nothing for new socket */
506         BLI_addtail(lb, sock);
507         
508         node->update |= NODE_UPDATE;
509         
510         return sock;
511 }
512
513 bNodeSocket *nodeInsertSocket(bNodeTree *ntree, bNode *node, int in_out, const char *idname,
514                               bNodeSocket *next_sock, const char *identifier, const char *name)
515 {
516         ListBase *lb = (in_out == SOCK_IN ? &node->inputs : &node->outputs);
517         bNodeSocket *sock = make_socket(ntree, node, in_out, lb, idname, identifier, name);
518         
519         BLI_remlink(lb, sock);  /* does nothing for new socket */
520         BLI_insertlinkbefore(lb, next_sock, sock);
521         
522         node->update |= NODE_UPDATE;
523         
524         return sock;
525 }
526
527 const char *nodeStaticSocketType(int type, int subtype)
528 {
529         switch (type) {
530                 case SOCK_FLOAT:
531                         switch (subtype) {
532                                 case PROP_UNSIGNED:
533                                         return "NodeSocketFloatUnsigned";
534                                 case PROP_PERCENTAGE:
535                                         return "NodeSocketFloatPercentage";
536                                 case PROP_FACTOR:
537                                         return "NodeSocketFloatFactor";
538                                 case PROP_ANGLE:
539                                         return "NodeSocketFloatAngle";
540                                 case PROP_TIME:
541                                         return "NodeSocketFloatTime";
542                                 case PROP_NONE:
543                                 default:
544                                         return "NodeSocketFloat";
545                         }
546                 case SOCK_INT:
547                         switch (subtype) {
548                                 case PROP_UNSIGNED:
549                                         return "NodeSocketIntUnsigned";
550                                 case PROP_PERCENTAGE:
551                                         return "NodeSocketIntPercentage";
552                                 case PROP_FACTOR:
553                                         return "NodeSocketIntFactor";
554                                 case PROP_NONE:
555                                 default:
556                                         return "NodeSocketInt";
557                         }
558                 case SOCK_BOOLEAN:
559                         return "NodeSocketBool";
560                 case SOCK_VECTOR:
561                         switch (subtype) {
562                                 case PROP_TRANSLATION:
563                                         return "NodeSocketVectorTranslation";
564                                 case PROP_DIRECTION:
565                                         return "NodeSocketVectorDirection";
566                                 case PROP_VELOCITY:
567                                         return "NodeSocketVectorVelocity";
568                                 case PROP_ACCELERATION:
569                                         return "NodeSocketVectorAcceleration";
570                                 case PROP_EULER:
571                                         return "NodeSocketVectorEuler";
572                                 case PROP_XYZ:
573                                         return "NodeSocketVectorXYZ";
574                                 case PROP_NONE:
575                                 default:
576                                         return "NodeSocketVector";
577                         }
578                 case SOCK_RGBA:
579                         return "NodeSocketColor";
580                 case SOCK_STRING:
581                         return "NodeSocketString";
582                 case SOCK_SHADER:
583                         return "NodeSocketShader";
584         }
585         return NULL;
586 }
587
588 const char *nodeStaticSocketInterfaceType(int type, int subtype)
589 {
590         switch (type) {
591                 case SOCK_FLOAT:
592                         switch (subtype) {
593                                 case PROP_UNSIGNED:
594                                         return "NodeSocketInterfaceFloatUnsigned";
595                                 case PROP_PERCENTAGE:
596                                         return "NodeSocketInterfaceFloatPercentage";
597                                 case PROP_FACTOR:
598                                         return "NodeSocketInterfaceFloatFactor";
599                                 case PROP_ANGLE:
600                                         return "NodeSocketInterfaceFloatAngle";
601                                 case PROP_TIME:
602                                         return "NodeSocketInterfaceFloatTime";
603                                 case PROP_NONE:
604                                 default:
605                                         return "NodeSocketInterfaceFloat";
606                         }
607                 case SOCK_INT:
608                         switch (subtype) {
609                                 case PROP_UNSIGNED:
610                                         return "NodeSocketInterfaceIntUnsigned";
611                                 case PROP_PERCENTAGE:
612                                         return "NodeSocketInterfaceIntPercentage";
613                                 case PROP_FACTOR:
614                                         return "NodeSocketInterfaceIntFactor";
615                                 case PROP_NONE:
616                                 default:
617                                         return "NodeSocketInterfaceInt";
618                         }
619                 case SOCK_BOOLEAN:
620                         return "NodeSocketInterfaceBool";
621                 case SOCK_VECTOR:
622                         switch (subtype) {
623                                 case PROP_TRANSLATION:
624                                         return "NodeSocketInterfaceVectorTranslation";
625                                 case PROP_DIRECTION:
626                                         return "NodeSocketInterfaceVectorDirection";
627                                 case PROP_VELOCITY:
628                                         return "NodeSocketInterfaceVectorVelocity";
629                                 case PROP_ACCELERATION:
630                                         return "NodeSocketInterfaceVectorAcceleration";
631                                 case PROP_EULER:
632                                         return "NodeSocketInterfaceVectorEuler";
633                                 case PROP_XYZ:
634                                         return "NodeSocketInterfaceVectorXYZ";
635                                 case PROP_NONE:
636                                 default:
637                                         return "NodeSocketInterfaceVector";
638                         }
639                 case SOCK_RGBA:
640                         return "NodeSocketInterfaceColor";
641                 case SOCK_STRING:
642                         return "NodeSocketInterfaceString";
643                 case SOCK_SHADER:
644                         return "NodeSocketInterfaceShader";
645         }
646         return NULL;
647 }
648
649 bNodeSocket *nodeAddStaticSocket(bNodeTree *ntree, bNode *node, int in_out, int type, int subtype,
650                                  const char *identifier, const char *name)
651 {
652         const char *idname = nodeStaticSocketType(type, subtype);
653         bNodeSocket *sock;
654         
655         if (!idname) {
656                 printf("Error: static node socket type %d undefined\n", type);
657                 return NULL;
658         }
659         
660         sock = nodeAddSocket(ntree, node, in_out, idname, identifier, name);
661         sock->type = type;
662         return sock;
663 }
664
665 bNodeSocket *nodeInsertStaticSocket(bNodeTree *ntree, bNode *node, int in_out, int type, int subtype,
666                                     bNodeSocket *next_sock, const char *identifier, const char *name)
667 {
668         const char *idname = nodeStaticSocketType(type, subtype);
669         bNodeSocket *sock;
670         
671         if (!idname) {
672                 printf("Error: static node socket type %d undefined\n", type);
673                 return NULL;
674         }
675         
676         sock = nodeInsertSocket(ntree, node, in_out, idname, next_sock, identifier, name);
677         sock->type = type;
678         return sock;
679 }
680
681 static void node_socket_free(bNodeTree *UNUSED(ntree), bNodeSocket *sock, bNode *UNUSED(node))
682 {
683         if (sock->prop) {
684                 IDP_FreeProperty(sock->prop);
685                 MEM_freeN(sock->prop);
686         }
687         
688         if (sock->default_value)
689                 MEM_freeN(sock->default_value);
690 }
691
692 void nodeRemoveSocket(bNodeTree *ntree, bNode *node, bNodeSocket *sock)
693 {
694         bNodeLink *link, *next;
695         
696         for (link = ntree->links.first; link; link = next) {
697                 next = link->next;
698                 if (link->fromsock == sock || link->tosock == sock) {
699                         nodeRemLink(ntree, link);
700                 }
701         }
702         
703         /* this is fast, this way we don't need an in_out argument */
704         BLI_remlink(&node->inputs, sock);
705         BLI_remlink(&node->outputs, sock);
706         
707         node_socket_free(ntree, sock, node);
708         MEM_freeN(sock);
709         
710         node->update |= NODE_UPDATE;
711 }
712
713 void nodeRemoveAllSockets(bNodeTree *ntree, bNode *node)
714 {
715         bNodeSocket *sock, *sock_next;
716         bNodeLink *link, *next;
717         
718         for (link = ntree->links.first; link; link = next) {
719                 next = link->next;
720                 if (link->fromnode == node || link->tonode == node) {
721                         nodeRemLink(ntree, link);
722                 }
723         }
724         
725         for (sock = node->inputs.first; sock; sock = sock_next) {
726                 sock_next = sock->next;
727                 node_socket_free(ntree, sock, node);
728                 MEM_freeN(sock);
729         }
730         for (sock = node->outputs.first; sock; sock = sock_next) {
731                 sock_next = sock->next;
732                 node_socket_free(ntree, sock, node);
733                 MEM_freeN(sock);
734         }
735         
736         node->update |= NODE_UPDATE;
737 }
738
739 /* finds a node based on its name */
740 bNode *nodeFindNodebyName(bNodeTree *ntree, const char *name)
741 {
742         return BLI_findstring(&ntree->nodes, name, offsetof(bNode, name));
743 }
744
745 /* finds a node based on given socket */
746 int nodeFindNode(bNodeTree *ntree, bNodeSocket *sock, bNode **nodep, int *sockindex)
747 {
748         int in_out = sock->in_out;
749         bNode *node;
750         bNodeSocket *tsock;
751         int index = 0;
752         
753         for (node = ntree->nodes.first; node; node = node->next) {
754                 tsock = (in_out == SOCK_IN ? node->inputs.first : node->outputs.first);
755                 for (index = 0; tsock; tsock = tsock->next, index++) {
756                         if (tsock == sock)
757                                 break;
758                 }
759                 if (tsock)
760                         break;
761         }
762
763         if (node) {
764                 *nodep = node;
765                 if (sockindex) *sockindex = index;
766                 return 1;
767         }
768         
769         *nodep = NULL;
770         return 0;
771 }
772
773 /* ************** Add stuff ********** */
774
775 /* Find the first available, non-duplicate name for a given node */
776 void nodeUniqueName(bNodeTree *ntree, bNode *node)
777 {
778         BLI_uniquename(&ntree->nodes, node, DATA_("Node"), '.', offsetof(bNode, name), sizeof(node->name));
779 }
780
781 bNode *nodeAddNode(const struct bContext *C, bNodeTree *ntree, const char *idname)
782 {
783         bNode *node;
784         
785         node = MEM_callocN(sizeof(bNode), "new node");
786         BLI_addtail(&ntree->nodes, node);
787         
788         BLI_strncpy(node->idname, idname, sizeof(node->idname));
789         node_set_typeinfo(C, ntree, node, nodeTypeFind(idname));
790         
791         ntree->update |= NTREE_UPDATE_NODES;
792         
793         return node;
794 }
795
796 bNode *nodeAddStaticNode(const struct bContext *C, bNodeTree *ntree, int type)
797 {
798         const char *idname = NULL;
799         
800         NODE_TYPES_BEGIN(ntype)
801                 /* do an extra poll here, because some int types are used
802                  * for multiple node types, this helps find the desired type
803                  */
804                 if (ntype->type == type && (!ntype->poll || ntype->poll(ntype, ntree))) {
805                         idname = ntype->idname;
806                         break;
807                 }
808         NODE_TYPES_END
809         if (!idname) {
810                 printf("Error: static node type %d undefined\n", type);
811                 return NULL;
812         }
813         return nodeAddNode(C, ntree, idname);
814 }
815
816 static void node_socket_copy(bNodeSocket *dst, bNodeSocket *src)
817 {
818         src->new_sock = dst;
819         
820         if (src->prop)
821                 dst->prop = IDP_CopyProperty(src->prop);
822         
823         if (src->default_value)
824                 dst->default_value = MEM_dupallocN(src->default_value);
825         
826         dst->stack_index = 0;
827         /* XXX some compositor node (e.g. image, render layers) still store
828          * some persistent buffer data here, need to clear this to avoid dangling pointers.
829          */
830         dst->cache = NULL;
831 }
832
833 /* keep socket listorder identical, for copying links */
834 /* ntree is the target tree */
835 bNode *nodeCopyNode(struct bNodeTree *ntree, struct bNode *node)
836 {
837         bNode *nnode = MEM_callocN(sizeof(bNode), "dupli node");
838         bNodeSocket *sock, *oldsock;
839         bNodeLink *link, *oldlink;
840
841         *nnode = *node;
842         /* can be called for nodes outside a node tree (e.g. clipboard) */
843         if (ntree) {
844                 nodeUniqueName(ntree, nnode);
845
846                 BLI_addtail(&ntree->nodes, nnode);
847         }
848
849         BLI_duplicatelist(&nnode->inputs, &node->inputs);
850         oldsock = node->inputs.first;
851         for (sock = nnode->inputs.first; sock; sock = sock->next, oldsock = oldsock->next)
852                 node_socket_copy(sock, oldsock);
853         
854         BLI_duplicatelist(&nnode->outputs, &node->outputs);
855         oldsock = node->outputs.first;
856         for (sock = nnode->outputs.first; sock; sock = sock->next, oldsock = oldsock->next)
857                 node_socket_copy(sock, oldsock);
858         
859         if (node->prop)
860                 nnode->prop = IDP_CopyProperty(node->prop);
861         
862         BLI_duplicatelist(&nnode->internal_links, &node->internal_links);
863         oldlink = node->internal_links.first;
864         for (link = nnode->internal_links.first; link; link = link->next, oldlink = oldlink->next) {
865                 link->fromnode = nnode;
866                 link->tonode = nnode;
867                 link->fromsock = link->fromsock->new_sock;
868                 link->tosock = link->tosock->new_sock;
869         }
870         
871         /* don't increase node->id users, freenode doesn't decrement either */
872         
873         if (node->typeinfo->copyfunc)
874                 node->typeinfo->copyfunc(ntree, nnode, node);
875         
876         node->new_node = nnode;
877         nnode->new_node = NULL;
878         
879         if (nnode->typeinfo->copyfunc_api) {
880                 PointerRNA ptr;
881                 RNA_pointer_create((ID *)ntree, &RNA_Node, nnode, &ptr);
882                 
883                 nnode->typeinfo->copyfunc_api(&ptr, node);
884         }
885         
886         if (ntree)
887                 ntree->update |= NTREE_UPDATE_NODES;
888         
889         return nnode;
890 }
891
892 /* also used via rna api, so we check for proper input output direction */
893 bNodeLink *nodeAddLink(bNodeTree *ntree, bNode *fromnode, bNodeSocket *fromsock, bNode *tonode, bNodeSocket *tosock)
894 {
895         bNodeLink *link = NULL;
896         
897         /* test valid input */
898         BLI_assert(fromnode);
899         BLI_assert(tonode);
900         
901         if (fromsock->in_out == SOCK_OUT && tosock->in_out == SOCK_IN) {
902                 link = MEM_callocN(sizeof(bNodeLink), "link");
903                 if (ntree)
904                         BLI_addtail(&ntree->links, link);
905                 link->fromnode = fromnode;
906                 link->fromsock = fromsock;
907                 link->tonode = tonode;
908                 link->tosock = tosock;
909         }
910         else if (fromsock->in_out == SOCK_IN && tosock->in_out == SOCK_OUT) {
911                 /* OK but flip */
912                 link = MEM_callocN(sizeof(bNodeLink), "link");
913                 if (ntree)
914                         BLI_addtail(&ntree->links, link);
915                 link->fromnode = tonode;
916                 link->fromsock = tosock;
917                 link->tonode = fromnode;
918                 link->tosock = fromsock;
919         }
920         
921         if (ntree)
922                 ntree->update |= NTREE_UPDATE_LINKS;
923         
924         return link;
925 }
926
927 void nodeRemLink(bNodeTree *ntree, bNodeLink *link)
928 {
929         /* can be called for links outside a node tree (e.g. clipboard) */
930         if (ntree)
931                 BLI_remlink(&ntree->links, link);
932
933         if (link->tosock)
934                 link->tosock->link = NULL;
935         MEM_freeN(link);
936         
937         if (ntree)
938                 ntree->update |= NTREE_UPDATE_LINKS;
939 }
940
941 void nodeRemSocketLinks(bNodeTree *ntree, bNodeSocket *sock)
942 {
943         bNodeLink *link, *next;
944         
945         for (link = ntree->links.first; link; link = next) {
946                 next = link->next;
947                 if (link->fromsock == sock || link->tosock == sock) {
948                         nodeRemLink(ntree, link);
949                 }
950         }
951         
952         ntree->update |= NTREE_UPDATE_LINKS;
953 }
954
955 int nodeLinkIsHidden(bNodeLink *link)
956 {
957         return nodeSocketIsHidden(link->fromsock) || nodeSocketIsHidden(link->tosock);
958 }
959
960 void nodeInternalRelink(bNodeTree *ntree, bNode *node)
961 {
962         bNodeLink *link, *link_next;
963         
964         /* store link pointers in output sockets, for efficient lookup */
965         for (link = node->internal_links.first; link; link = link->next)
966                 link->tosock->link = link;
967         
968         /* redirect downstream links */
969         for (link = ntree->links.first; link; link = link_next) {
970                 link_next = link->next;
971                 
972                 /* do we have internal link? */
973                 if (link->fromnode == node) {
974                         if (link->fromsock->link) {
975                                 /* get the upstream input link */
976                                 bNodeLink *fromlink = link->fromsock->link->fromsock->link;
977                                 /* skip the node */
978                                 if (fromlink) {
979                                         link->fromnode = fromlink->fromnode;
980                                         link->fromsock = fromlink->fromsock;
981                                         
982                                         /* if the up- or downstream link is invalid,
983                                          * the replacement link will be invalid too.
984                                          */
985                                         if (!(fromlink->flag & NODE_LINK_VALID))
986                                                 link->flag &= ~NODE_LINK_VALID;
987                                         
988                                         ntree->update |= NTREE_UPDATE_LINKS;
989                                 }
990                                 else
991                                         nodeRemLink(ntree, link);
992                         }
993                         else
994                                 nodeRemLink(ntree, link);
995                 }
996         }
997         
998         /* remove remaining upstream links */
999         for (link = ntree->links.first; link; link = link_next) {
1000                 link_next = link->next;
1001                 
1002                 if (link->tonode == node)
1003                         nodeRemLink(ntree, link);
1004         }
1005 }
1006
1007 void nodeToView(bNode *node, float x, float y, float *rx, float *ry)
1008 {
1009         if (node->parent) {
1010                 nodeToView(node->parent, x + node->locx, y + node->locy, rx, ry);
1011         }
1012         else {
1013                 *rx = x + node->locx;
1014                 *ry = y + node->locy;
1015         }
1016 }
1017
1018 void nodeFromView(bNode *node, float x, float y, float *rx, float *ry)
1019 {
1020         if (node->parent) {
1021                 nodeFromView(node->parent, x, y, rx, ry);
1022                 *rx -= node->locx;
1023                 *ry -= node->locy;
1024         }
1025         else {
1026                 *rx = x - node->locx;
1027                 *ry = y - node->locy;
1028         }
1029 }
1030
1031 int nodeAttachNodeCheck(bNode *node, bNode *parent)
1032 {
1033         bNode *parent_recurse;
1034         for (parent_recurse = node; parent_recurse; parent_recurse = parent_recurse->parent) {
1035                 if (parent_recurse == parent) {
1036                         return TRUE;
1037                 }
1038         }
1039
1040         return FALSE;
1041 }
1042
1043 void nodeAttachNode(bNode *node, bNode *parent)
1044 {
1045         float locx, locy;
1046
1047         BLI_assert(parent->type == NODE_FRAME);
1048         BLI_assert(nodeAttachNodeCheck(parent, node) == FALSE);
1049
1050         nodeToView(node, 0.0f, 0.0f, &locx, &locy);
1051         
1052         node->parent = parent;
1053         /* transform to parent space */
1054         nodeFromView(parent, locx, locy, &node->locx, &node->locy);
1055 }
1056
1057 void nodeDetachNode(struct bNode *node)
1058 {
1059         float locx, locy;
1060         
1061         if (node->parent) {
1062
1063                 BLI_assert(node->parent->type == NODE_FRAME);
1064
1065                 /* transform to view space */
1066                 nodeToView(node, 0.0f, 0.0f, &locx, &locy);
1067                 node->locx = locx;
1068                 node->locy = locy;
1069                 node->parent = NULL;
1070         }
1071 }
1072
1073 bNodeTree *ntreeAddTree(Main *bmain, const char *name, const char *idname)
1074 {
1075         bNodeTree *ntree;
1076         
1077         /* trees are created as local trees for compositor, material or texture nodes,
1078          * node groups and other tree types are created as library data.
1079          */
1080         if (bmain) {
1081                 ntree = BKE_libblock_alloc(&bmain->nodetree, ID_NT, name);
1082         }
1083         else {
1084                 ntree = MEM_callocN(sizeof(bNodeTree), "new node tree");
1085                 *( (short *)ntree->id.name ) = ID_NT;
1086                 BLI_strncpy(ntree->id.name + 2, name, sizeof(ntree->id.name));
1087         }
1088         
1089         /* Types are fully initialized at this point,
1090          * if an undefined node is added later this will be reset.
1091          */
1092         ntree->init |= NTREE_TYPE_INIT;
1093         
1094         BLI_strncpy(ntree->idname, idname, sizeof(ntree->idname));
1095         ntree_set_typeinfo(ntree, ntreeTypeFind(idname));
1096         
1097         return ntree;
1098 }
1099
1100 /* Warning: this function gets called during some rather unexpected times
1101  *      - this gets called when executing compositing updates (for threaded previews)
1102  *      - when the nodetree datablock needs to be copied (i.e. when users get copied)
1103  *      - for scene duplication use ntreeSwapID() after so we don't have stale pointers.
1104  *
1105  * do_make_extern: keep enabled for general use, only reason _not_ to enable is when
1106  * copying for internal use (threads for eg), where you wont want it to modify the
1107  * scene data.
1108  */
1109 static bNodeTree *ntreeCopyTree_internal(bNodeTree *ntree, Main *bmain, bool do_id_user, bool do_make_extern, bool copy_previews)
1110 {
1111         bNodeTree *newtree;
1112         bNode *node /*, *nnode */ /* UNUSED */, *last;
1113         bNodeSocket *sock, *oldsock;
1114         bNodeLink *link;
1115         
1116         if (ntree == NULL) return NULL;
1117         
1118         if (bmain) {
1119                 /* is ntree part of library? */
1120                 if (BLI_findindex(&bmain->nodetree, ntree) != -1)
1121                         newtree = BKE_libblock_copy(&ntree->id);
1122                 else
1123                         newtree = NULL;
1124         }
1125         else
1126                 newtree = NULL;
1127         
1128         if (newtree == NULL) {
1129                 newtree = MEM_dupallocN(ntree);
1130                 newtree->id.lib = NULL; /* same as owning datablock id.lib */
1131                 BKE_libblock_copy_data(&newtree->id, &ntree->id, true); /* copy animdata and ID props */
1132         }
1133
1134         id_us_plus((ID *)newtree->gpd);
1135
1136         /* in case a running nodetree is copied */
1137         newtree->execdata = NULL;
1138         
1139         newtree->nodes.first = newtree->nodes.last = NULL;
1140         newtree->links.first = newtree->links.last = NULL;
1141         
1142         last = ntree->nodes.last;
1143         for (node = ntree->nodes.first; node; node = node->next) {
1144
1145                 /* ntreeUserDecrefID inline */
1146                 if (do_id_user) {
1147                         id_us_plus(node->id);
1148                 }
1149
1150                 if (do_make_extern) {
1151                         id_lib_extern(node->id);
1152                 }
1153
1154                 node->new_node = NULL;
1155                 /* nnode = */ nodeCopyNode(newtree, node);   /* sets node->new */
1156                 
1157                 /* make sure we don't copy new nodes again! */
1158                 if (node == last)
1159                         break;
1160         }
1161         
1162         /* copy links */
1163         BLI_duplicatelist(&newtree->links, &ntree->links);
1164         for (link = newtree->links.first; link; link = link->next) {
1165                 link->fromnode = (link->fromnode ? link->fromnode->new_node : NULL);
1166                 link->fromsock = (link->fromsock ? link->fromsock->new_sock : NULL);
1167                 link->tonode = (link->tonode ? link->tonode->new_node : NULL);
1168                 link->tosock = (link->tosock ? link->tosock->new_sock : NULL);
1169                 /* update the link socket's pointer */
1170                 if (link->tosock)
1171                         link->tosock->link = link;
1172         }
1173         
1174         /* copy interface sockets */
1175         BLI_duplicatelist(&newtree->inputs, &ntree->inputs);
1176         oldsock = ntree->inputs.first;
1177         for (sock = newtree->inputs.first; sock; sock = sock->next, oldsock = oldsock->next)
1178                 node_socket_copy(sock, oldsock);
1179         
1180         BLI_duplicatelist(&newtree->outputs, &ntree->outputs);
1181         oldsock = ntree->outputs.first;
1182         for (sock = newtree->outputs.first; sock; sock = sock->next, oldsock = oldsock->next)
1183                 node_socket_copy(sock, oldsock);
1184         
1185         /* copy preview hash */
1186         if (ntree->previews && copy_previews) {
1187                 bNodeInstanceHashIterator iter;
1188                 
1189                 newtree->previews = BKE_node_instance_hash_new("node previews");
1190                 
1191                 NODE_INSTANCE_HASH_ITER(iter, ntree->previews) {
1192                         bNodeInstanceKey key = BKE_node_instance_hash_iterator_get_key(&iter);
1193                         bNodePreview *preview = BKE_node_instance_hash_iterator_get_value(&iter);
1194                         BKE_node_instance_hash_insert(newtree->previews, key, BKE_node_preview_copy(preview));
1195                 }
1196         }
1197         else
1198                 newtree->previews = NULL;
1199         
1200         /* update node->parent pointers */
1201         for (node = newtree->nodes.first; node; node = node->next) {
1202                 if (node->parent)
1203                         node->parent = node->parent->new_node;
1204         }
1205         
1206         /* node tree will generate its own interface type */
1207         ntree->interface_type = NULL;
1208         
1209         return newtree;
1210 }
1211
1212 bNodeTree *ntreeCopyTree_ex(bNodeTree *ntree, const short do_id_user)
1213 {
1214         return ntreeCopyTree_internal(ntree, G.main, do_id_user, TRUE, TRUE);
1215 }
1216 bNodeTree *ntreeCopyTree(bNodeTree *ntree)
1217 {
1218         return ntreeCopyTree_ex(ntree, TRUE);
1219 }
1220
1221 /* use when duplicating scenes */
1222 void ntreeSwitchID_ex(bNodeTree *ntree, ID *id_from, ID *id_to, const short do_id_user)
1223 {
1224         bNode *node;
1225
1226         if (id_from == id_to) {
1227                 /* should never happen but may as well skip if it does */
1228                 return;
1229         }
1230
1231         /* for scene duplication only */
1232         for (node = ntree->nodes.first; node; node = node->next) {
1233                 if (node->id == id_from) {
1234                         if (do_id_user) {
1235                                 id_us_min(id_from);
1236                                 id_us_plus(id_to);
1237                         }
1238
1239                         node->id = id_to;
1240                 }
1241         }
1242 }
1243 void ntreeSwitchID(bNodeTree *ntree, ID *id_from, ID *id_to)
1244 {
1245         ntreeSwitchID_ex(ntree, id_from, id_to, TRUE);
1246 }
1247
1248 void ntreeUserIncrefID(bNodeTree *ntree)
1249 {
1250         bNode *node;
1251         for (node = ntree->nodes.first; node; node = node->next) {
1252                 id_us_plus(node->id);
1253         }
1254 }
1255 void ntreeUserDecrefID(bNodeTree *ntree)
1256 {
1257         bNode *node;
1258         for (node = ntree->nodes.first; node; node = node->next) {
1259                 id_us_min(node->id);
1260         }
1261 }
1262
1263 /* *************** Node Preview *********** */
1264
1265 /* XXX this should be removed eventually ...
1266  * Currently BKE functions are modelled closely on previous code,
1267  * using BKE_node_preview_init_tree to set up previews for a whole node tree in advance.
1268  * This should be left more to the individual node tree implementations.
1269  */
1270 int BKE_node_preview_used(bNode *node)
1271 {
1272         /* XXX check for closed nodes? */
1273         return (node->typeinfo->flag & NODE_PREVIEW) != 0;
1274 }
1275
1276 bNodePreview *BKE_node_preview_verify(bNodeInstanceHash *previews, bNodeInstanceKey key, int xsize, int ysize, int create)
1277 {
1278         bNodePreview *preview;
1279         
1280         preview = BKE_node_instance_hash_lookup(previews, key);
1281         if (!preview) {
1282                 if (create) {
1283                         preview = MEM_callocN(sizeof(bNodePreview), "node preview");
1284                         BKE_node_instance_hash_insert(previews, key, preview);
1285                 }
1286                 else
1287                         return NULL;
1288         }
1289         
1290         /* node previews can get added with variable size this way */
1291         if (xsize == 0 || ysize == 0)
1292                 return preview;
1293         
1294         /* sanity checks & initialize */
1295         if (preview->rect) {
1296                 if (preview->xsize != xsize || preview->ysize != ysize) {
1297                         MEM_freeN(preview->rect);
1298                         preview->rect = NULL;
1299                 }
1300         }
1301         
1302         if (preview->rect == NULL) {
1303                 preview->rect = MEM_callocN(4 * xsize + xsize * ysize * sizeof(char) * 4, "node preview rect");
1304                 preview->xsize = xsize;
1305                 preview->ysize = ysize;
1306         }
1307         /* no clear, makes nicer previews */
1308         
1309         return preview;
1310 }
1311
1312 bNodePreview *BKE_node_preview_copy(bNodePreview *preview)
1313 {
1314         bNodePreview *new_preview = MEM_dupallocN(preview);
1315         if (preview->rect)
1316                 new_preview->rect = MEM_dupallocN(preview->rect);
1317         return new_preview;
1318 }
1319
1320 void BKE_node_preview_free(bNodePreview *preview)
1321 {
1322         if (preview->rect)
1323                 MEM_freeN(preview->rect);
1324         MEM_freeN(preview);
1325 }
1326
1327 static void node_preview_init_tree_recursive(bNodeInstanceHash *previews, bNodeTree *ntree, bNodeInstanceKey parent_key, int xsize, int ysize, int create)
1328 {
1329         bNode *node;
1330         for (node = ntree->nodes.first; node; node = node->next) {
1331                 bNodeInstanceKey key = BKE_node_instance_key(parent_key, ntree, node);
1332                 
1333                 if (BKE_node_preview_used(node)) {
1334                         node->preview_xsize = xsize;
1335                         node->preview_ysize = ysize;
1336                         
1337                         BKE_node_preview_verify(previews, key, xsize, ysize, create);
1338                 }
1339                 
1340                 if (node->type == NODE_GROUP && node->id)
1341                         node_preview_init_tree_recursive(previews, (bNodeTree *)node->id, key, xsize, ysize, create);
1342         }
1343 }
1344
1345 void BKE_node_preview_init_tree(bNodeTree *ntree, int xsize, int ysize, int create_previews)
1346 {
1347         if (!ntree)
1348                 return;
1349         
1350         if (!ntree->previews)
1351                 ntree->previews = BKE_node_instance_hash_new("node previews");
1352         
1353         node_preview_init_tree_recursive(ntree->previews, ntree, NODE_INSTANCE_KEY_BASE, xsize, ysize, create_previews);
1354 }
1355
1356 static void node_preview_tag_used_recursive(bNodeInstanceHash *previews, bNodeTree *ntree, bNodeInstanceKey parent_key)
1357 {
1358         bNode *node;
1359         for (node = ntree->nodes.first; node; node = node->next) {
1360                 bNodeInstanceKey key = BKE_node_instance_key(parent_key, ntree, node);
1361                 
1362                 if (BKE_node_preview_used(node))
1363                         BKE_node_instance_hash_tag_key(previews, key);
1364                 
1365                 if (node->type == NODE_GROUP && node->id)
1366                         node_preview_tag_used_recursive(previews, (bNodeTree *)node->id, key);
1367         }
1368 }
1369
1370 void BKE_node_preview_remove_unused(bNodeTree *ntree)
1371 {
1372         if (!ntree || !ntree->previews)
1373                 return;
1374         
1375         /* use the instance hash functions for tagging and removing unused previews */
1376         BKE_node_instance_hash_clear_tags(ntree->previews);
1377         node_preview_tag_used_recursive(ntree->previews, ntree, NODE_INSTANCE_KEY_BASE);
1378         
1379         BKE_node_instance_hash_remove_untagged(ntree->previews, (bNodeInstanceValueFP)BKE_node_preview_free);
1380 }
1381
1382 void BKE_node_preview_free_tree(bNodeTree *ntree)
1383 {
1384         if (!ntree)
1385                 return;
1386         
1387         if (ntree->previews) {
1388                 BKE_node_instance_hash_free(ntree->previews, (bNodeInstanceValueFP)BKE_node_preview_free);
1389                 ntree->previews = NULL;
1390         }
1391 }
1392
1393 void BKE_node_preview_clear(bNodePreview *preview)
1394 {
1395         if (preview && preview->rect)
1396                 memset(preview->rect, 0, MEM_allocN_len(preview->rect));
1397 }
1398
1399 void BKE_node_preview_clear_tree(bNodeTree *ntree)
1400 {
1401         bNodeInstanceHashIterator iter;
1402         
1403         if (!ntree || !ntree->previews)
1404                 return;
1405         
1406         NODE_INSTANCE_HASH_ITER(iter, ntree->previews) {
1407                 bNodePreview *preview = BKE_node_instance_hash_iterator_get_value(&iter);
1408                 BKE_node_preview_clear(preview);
1409         }
1410 }
1411
1412 static void node_preview_sync(bNodePreview *to, bNodePreview *from)
1413 {
1414         /* sizes should have been initialized by BKE_node_preview_init_tree */
1415         BLI_assert(to->xsize == from->xsize && to->ysize == from->ysize);
1416         
1417         /* copy over contents of previews */
1418         if (to->rect && from->rect) {
1419                 int xsize = to->xsize;
1420                 int ysize = to->ysize;
1421                 memcpy(to->rect, from->rect, 4 * xsize + xsize * ysize * sizeof(char) * 4);
1422         }
1423 }
1424
1425 void BKE_node_preview_sync_tree(bNodeTree *to_ntree, bNodeTree *from_ntree)
1426 {
1427         bNodeInstanceHash *from_previews = from_ntree->previews;
1428         bNodeInstanceHash *to_previews = to_ntree->previews;
1429         bNodeInstanceHashIterator iter;
1430         
1431         if (!from_previews || !to_previews)
1432                 return;
1433         
1434         NODE_INSTANCE_HASH_ITER(iter, from_previews) {
1435                 bNodeInstanceKey key = BKE_node_instance_hash_iterator_get_key(&iter);
1436                 bNodePreview *from = BKE_node_instance_hash_iterator_get_value(&iter);
1437                 bNodePreview *to = BKE_node_instance_hash_lookup(to_previews, key);
1438                 
1439                 if (from && to)
1440                         node_preview_sync(to, from);
1441         }
1442 }
1443
1444 void BKE_node_preview_merge_tree(bNodeTree *to_ntree, bNodeTree *from_ntree, bool remove_old)
1445 {
1446         if (remove_old || !to_ntree->previews) {
1447                 /* free old previews */
1448                 if (to_ntree->previews)
1449                         BKE_node_instance_hash_free(to_ntree->previews, (bNodeInstanceValueFP)BKE_node_preview_free);
1450                 
1451                 /* transfer previews */
1452                 to_ntree->previews = from_ntree->previews;
1453                 from_ntree->previews = NULL;
1454                 
1455                 /* clean up, in case any to_ntree nodes have been removed */
1456                 BKE_node_preview_remove_unused(to_ntree);
1457         }
1458         else {
1459                 bNodeInstanceHashIterator iter;
1460                 
1461                 if (from_ntree->previews) {
1462                         NODE_INSTANCE_HASH_ITER(iter, from_ntree->previews) {
1463                                 bNodeInstanceKey key = BKE_node_instance_hash_iterator_get_key(&iter);
1464                                 bNodePreview *preview = BKE_node_instance_hash_iterator_get_value(&iter);
1465                                 
1466                                 /* replace existing previews */
1467                                 BKE_node_instance_hash_remove(to_ntree->previews, key, (bNodeInstanceValueFP)BKE_node_preview_free);
1468                                 BKE_node_instance_hash_insert(to_ntree->previews, key, preview);
1469                         }
1470                         
1471                         /* Note: NULL free function here, because pointers have already been moved over to to_ntree->previews! */
1472                         BKE_node_instance_hash_free(from_ntree->previews, NULL);
1473                         from_ntree->previews = NULL;
1474                 }
1475         }
1476 }
1477
1478 /* hack warning! this function is only used for shader previews, and 
1479  * since it gets called multiple times per pixel for Ztransp we only
1480  * add the color once. Preview gets cleared before it starts render though */
1481 void BKE_node_preview_set_pixel(bNodePreview *preview, const float col[4], int x, int y, int do_manage)
1482 {
1483         if (preview) {
1484                 if (x >= 0 && y >= 0) {
1485                         if (x < preview->xsize && y < preview->ysize) {
1486                                 unsigned char *tar = preview->rect + 4 * ((preview->xsize * y) + x);
1487                                 
1488                                 if (do_manage) {
1489                                         linearrgb_to_srgb_uchar4(tar, col);
1490                                 }
1491                                 else {
1492                                         rgba_float_to_uchar(tar, col);
1493                                 }
1494                         }
1495                         //else printf("prv out bound x y %d %d\n", x, y);
1496                 }
1497                 //else printf("prv out bound x y %d %d\n", x, y);
1498         }
1499 }
1500
1501 #if 0
1502 static void nodeClearPreview(bNode *node)
1503 {
1504         if (node->preview && node->preview->rect)
1505                 memset(node->preview->rect, 0, MEM_allocN_len(node->preview->rect));
1506 }
1507
1508 /* use it to enforce clear */
1509 void ntreeClearPreview(bNodeTree *ntree)
1510 {
1511         bNode *node;
1512         
1513         if (ntree == NULL)
1514                 return;
1515         
1516         for (node = ntree->nodes.first; node; node = node->next) {
1517                 if (node->typeinfo->flag & NODE_PREVIEW)
1518                         nodeClearPreview(node);
1519                 if (node->type == NODE_GROUP)
1520                         ntreeClearPreview((bNodeTree *)node->id);
1521         }
1522 }
1523
1524 /* hack warning! this function is only used for shader previews, and 
1525  * since it gets called multiple times per pixel for Ztransp we only
1526  * add the color once. Preview gets cleared before it starts render though */
1527 void nodeAddToPreview(bNode *node, const float col[4], int x, int y, int do_manage)
1528 {
1529         bNodePreview *preview = node->preview;
1530         if (preview) {
1531                 if (x >= 0 && y >= 0) {
1532                         if (x < preview->xsize && y < preview->ysize) {
1533                                 unsigned char *tar = preview->rect + 4 * ((preview->xsize * y) + x);
1534                                 
1535                                 if (do_manage) {
1536                                         linearrgb_to_srgb_uchar4(tar, col);
1537                                 }
1538                                 else {
1539                                         rgba_float_to_uchar(tar, col);
1540                                 }
1541                         }
1542                         //else printf("prv out bound x y %d %d\n", x, y);
1543                 }
1544                 //else printf("prv out bound x y %d %d\n", x, y);
1545         }
1546 }
1547 #endif
1548
1549 /* ************** Free stuff ********** */
1550
1551 /* goes over entire tree */
1552 void nodeUnlinkNode(bNodeTree *ntree, bNode *node)
1553 {
1554         bNodeLink *link, *next;
1555         bNodeSocket *sock;
1556         ListBase *lb;
1557         
1558         for (link = ntree->links.first; link; link = next) {
1559                 next = link->next;
1560                 
1561                 if (link->fromnode == node) {
1562                         lb = &node->outputs;
1563                         if (link->tonode)
1564                                 link->tonode->update |= NODE_UPDATE;
1565                 }
1566                 else if (link->tonode == node)
1567                         lb = &node->inputs;
1568                 else
1569                         lb = NULL;
1570
1571                 if (lb) {
1572                         for (sock = lb->first; sock; sock = sock->next) {
1573                                 if (link->fromsock == sock || link->tosock == sock)
1574                                         break;
1575                         }
1576                         if (sock) {
1577                                 nodeRemLink(ntree, link);
1578                         }
1579                 }
1580         }
1581 }
1582
1583 static void node_unlink_attached(bNodeTree *ntree, bNode *parent)
1584 {
1585         bNode *node;
1586         for (node = ntree->nodes.first; node; node = node->next) {
1587                 if (node->parent == parent)
1588                         nodeDetachNode(node);
1589         }
1590 }
1591
1592 /** \note caller needs to manage node->id user */
1593 static void node_free_node_ex(bNodeTree *ntree, bNode *node, bool use_api_free_cb)
1594 {
1595         bNodeSocket *sock, *nextsock;
1596         char propname_esc[MAX_IDPROP_NAME * 2];
1597         char prefix[MAX_IDPROP_NAME * 2];
1598         
1599         /* extra free callback */
1600         if (use_api_free_cb && node->typeinfo->freefunc_api) {
1601                 PointerRNA ptr;
1602                 RNA_pointer_create((ID *)ntree, &RNA_Node, node, &ptr);
1603                 
1604                 node->typeinfo->freefunc_api(&ptr);
1605         }
1606         
1607         /* since it is called while free database, node->id is undefined */
1608         
1609         /* can be called for nodes outside a node tree (e.g. clipboard) */
1610         if (ntree) {
1611                 /* remove all references to this node */
1612                 nodeUnlinkNode(ntree, node);
1613                 node_unlink_attached(ntree, node);
1614                 
1615                 BLI_remlink(&ntree->nodes, node);
1616                 
1617                 BLI_strescape(propname_esc, node->name, sizeof(propname_esc));
1618                 BLI_snprintf(prefix, sizeof(prefix), "nodes[\"%s\"]", propname_esc);
1619
1620                 BKE_animdata_fix_paths_remove((ID *)ntree, prefix);
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);
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 short 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);
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 int ntreeHasType(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 bNodeLink *nodeFindLink(bNodeTree *ntree, bNodeSocket *from, bNodeSocket *to)
2296 {
2297         bNodeLink *link;
2298         
2299         for (link = ntree->links.first; link; link = link->next) {
2300                 if (link->fromsock == from && link->tosock == to)
2301                         return link;
2302                 if (link->fromsock == to && link->tosock == from) /* hrms? */
2303                         return link;
2304         }
2305         return NULL;
2306 }
2307
2308 int nodeCountSocketLinks(bNodeTree *ntree, bNodeSocket *sock)
2309 {
2310         bNodeLink *link;
2311         int tot = 0;
2312         
2313         for (link = ntree->links.first; link; link = link->next) {
2314                 if (link->fromsock == sock || link->tosock == sock)
2315                         tot++;
2316         }
2317         return tot;
2318 }
2319
2320 bNode *nodeGetActive(bNodeTree *ntree)
2321 {
2322         bNode *node;
2323         
2324         if (ntree == NULL) return NULL;
2325         
2326         for (node = ntree->nodes.first; node; node = node->next)
2327                 if (node->flag & NODE_ACTIVE)
2328                         break;
2329         return node;
2330 }
2331
2332 static bNode *node_get_active_id_recursive(bNodeInstanceKey active_key, bNodeInstanceKey parent_key, bNodeTree *ntree, short idtype)
2333 {
2334         if (parent_key.value == active_key.value || active_key.value == 0) {
2335                 bNode *node;
2336                 for (node = ntree->nodes.first; node; node = node->next)
2337                         if (node->id && GS(node->id->name) == idtype)
2338                                 if (node->flag & NODE_ACTIVE_ID)
2339                                         return node;
2340         }
2341         else {
2342                 bNode *node, *tnode;
2343                 /* no node with active ID in this tree, look inside groups */
2344                 for (node = ntree->nodes.first; node; node = node->next) {
2345                         if (node->type == NODE_GROUP) {
2346                                 bNodeTree *group = (bNodeTree *)node->id;
2347                                 if (group) {
2348                                         bNodeInstanceKey group_key = BKE_node_instance_key(parent_key, ntree, node);
2349                                         tnode = node_get_active_id_recursive(active_key, group_key, group, idtype);
2350                                         if (tnode)
2351                                                 return tnode;
2352                                 }
2353                         }
2354                 }
2355         }
2356         
2357         return NULL;
2358 }
2359
2360 /* two active flags, ID nodes have special flag for buttons display */
2361 bNode *nodeGetActiveID(bNodeTree *ntree, short idtype)
2362 {
2363         if (ntree)
2364                 return node_get_active_id_recursive(ntree->active_viewer_key, NODE_INSTANCE_KEY_BASE, ntree, idtype);
2365         else
2366                 return NULL;
2367 }
2368
2369 bool nodeSetActiveID(bNodeTree *ntree, short idtype, ID *id)
2370 {
2371         bNode *node;
2372         bool ok = false;
2373
2374         if (ntree == NULL) return ok;
2375
2376         for (node = ntree->nodes.first; node; node = node->next) {
2377                 if (node->id && GS(node->id->name) == idtype) {
2378                         if (id && ok == FALSE && node->id == id) {
2379                                 node->flag |= NODE_ACTIVE_ID;
2380                                 ok = TRUE;
2381                         }
2382                         else {
2383                                 node->flag &= ~NODE_ACTIVE_ID;
2384                         }
2385                 }
2386         }
2387
2388         /* update all groups linked from here
2389          * if active ID node has been found already,
2390          * just pass NULL so other matching nodes are deactivated.
2391          */
2392         for (node = ntree->nodes.first; node; node = node->next) {
2393                 if (node->type == NODE_GROUP)
2394                         ok |= nodeSetActiveID((bNodeTree *)node->id, idtype, (ok == false ? id : NULL));
2395         }
2396
2397         return ok;
2398 }
2399
2400
2401 /* two active flags, ID nodes have special flag for buttons display */
2402 void nodeClearActiveID(bNodeTree *ntree, short idtype)
2403 {
2404         bNode *node;
2405         
2406         if (ntree == NULL) return;
2407         
2408         for (node = ntree->nodes.first; node; node = node->next)
2409                 if (node->id && GS(node->id->name) == idtype)
2410                         node->flag &= ~NODE_ACTIVE_ID;
2411 }
2412
2413 void nodeSetSelected(bNode *node, int select)
2414 {
2415         if (select) {
2416                 node->flag |= NODE_SELECT;
2417         }
2418         else {
2419                 bNodeSocket *sock;
2420                 
2421                 node->flag &= ~NODE_SELECT;
2422                 
2423                 /* deselect sockets too */
2424                 for (sock = node->inputs.first; sock; sock = sock->next)
2425                         sock->flag &= ~NODE_SELECT;
2426                 for (sock = node->outputs.first; sock; sock = sock->next)
2427                         sock->flag &= ~NODE_SELECT;
2428         }
2429 }
2430
2431 void nodeClearActive(bNodeTree *ntree)
2432 {
2433         bNode *node;
2434
2435         if (ntree == NULL) return;
2436
2437         for (node = ntree->nodes.first; node; node = node->next)
2438                 node->flag &= ~(NODE_ACTIVE | NODE_ACTIVE_ID);
2439 }
2440
2441 /* two active flags, ID nodes have special flag for buttons display */
2442 void nodeSetActive(bNodeTree *ntree, bNode *node)
2443 {
2444         bNode *tnode;
2445         
2446         /* make sure only one node is active, and only one per ID type */
2447         for (tnode = ntree->nodes.first; tnode; tnode = tnode->next) {
2448                 tnode->flag &= ~NODE_ACTIVE;
2449                 
2450                 if (node->id && tnode->id) {
2451                         if (GS(node->id->name) == GS(tnode->id->name))
2452                                 tnode->flag &= ~NODE_ACTIVE_ID;
2453                 }
2454                 if (node->typeinfo->nclass == NODE_CLASS_TEXTURE)
2455                         tnode->flag &= ~NODE_ACTIVE_TEXTURE;
2456         }
2457         
2458         node->flag |= NODE_ACTIVE;
2459         if (node->id)
2460                 node->flag |= NODE_ACTIVE_ID;
2461         if (node->typeinfo->nclass == NODE_CLASS_TEXTURE)
2462                 node->flag |= NODE_ACTIVE_TEXTURE;
2463 }
2464
2465 int nodeSocketIsHidden(bNodeSocket *sock)
2466 {
2467         return ((sock->flag & (SOCK_HIDDEN | SOCK_UNAVAIL)) != 0);
2468 }
2469
2470 /* ************** Node Clipboard *********** */
2471
2472 #define USE_NODE_CB_VALIDATE
2473
2474 #ifdef USE_NODE_CB_VALIDATE
2475 /**
2476  * This data structure is to validate the node on creation,
2477  * otherwise we may reference missing data.
2478  *
2479  * Currently its only used for ID's, but nodes may one day
2480  * reference other pointers which need validation.
2481  */
2482 typedef struct bNodeClipboardExtraInfo {
2483         struct bNodeClipboardExtraInfo *next, *prev;
2484         ID  *id;
2485         char id_name[MAX_ID_NAME];
2486         char library_name[FILE_MAX];
2487 } bNodeClipboardExtraInfo;
2488 #endif  /* USE_NODE_CB_VALIDATE */
2489
2490
2491 typedef struct bNodeClipboard {
2492         ListBase nodes;
2493
2494 #ifdef USE_NODE_CB_VALIDATE
2495         ListBase nodes_extra_info;
2496 #endif
2497
2498         ListBase links;
2499         int type;
2500 } bNodeClipboard;
2501
2502 static bNodeClipboard node_clipboard = {{NULL}};
2503
2504 void BKE_node_clipboard_init(struct bNodeTree *ntree)
2505 {
2506         node_clipboard.type = ntree->type;
2507 }
2508
2509 void BKE_node_clipboard_clear(void)
2510 {
2511         bNode *node, *node_next;
2512         bNodeLink *link, *link_next;
2513         
2514         for (link = node_clipboard.links.first; link; link = link_next) {
2515                 link_next = link->next;
2516                 nodeRemLink(NULL, link);
2517         }
2518         node_clipboard.links.first = node_clipboard.links.last = NULL;
2519         
2520         for (node = node_clipboard.nodes.first; node; node = node_next) {
2521                 node_next = node->next;
2522                 node_free_node_ex(NULL, node, false);
2523         }
2524         node_clipboard.nodes.first = node_clipboard.nodes.last = NULL;
2525
2526 #ifdef USE_NODE_CB_VALIDATE
2527         BLI_freelistN(&node_clipboard.nodes_extra_info);
2528 #endif
2529 }
2530
2531 /* return FALSE when one or more ID's are lost */
2532 int BKE_node_clipboard_validate(void)
2533 {
2534         int ok = TRUE;
2535
2536 #ifdef USE_NODE_CB_VALIDATE
2537         bNodeClipboardExtraInfo *node_info;
2538         bNode *node;
2539
2540
2541         /* lists must be aligned */
2542         BLI_assert(BLI_countlist(&node_clipboard.nodes) ==
2543                    BLI_countlist(&node_clipboard.nodes_extra_info));
2544
2545         for (node = node_clipboard.nodes.first, node_info = node_clipboard.nodes_extra_info.first;
2546              node;
2547              node = node->next, node_info = node_info->next)
2548         {
2549                 /* validate the node against the stored node info */
2550
2551                 /* re-assign each loop since we may clear,
2552                  * open a new file where the ID is valid, and paste again */
2553                 node->id = node_info->id;
2554
2555                 /* currently only validate the ID */
2556                 if (node->id) {
2557                         ListBase *lb = which_libbase(G.main, GS(node_info->id_name));
2558                         BLI_assert(lb != NULL);
2559
2560                         if (BLI_findindex(lb, node_info->id) == -1) {
2561                                 /* may assign NULL */
2562                                 node->id = BLI_findstring(lb, node_info->id_name + 2, offsetof(ID, name) + 2);
2563
2564                                 if (node->id == NULL) {
2565                                         ok = FALSE;
2566                                 }
2567                         }
2568                 }
2569         }
2570 #endif  /* USE_NODE_CB_VALIDATE */
2571
2572         return ok;
2573 }
2574
2575 void BKE_node_clipboard_add_node(bNode *node)
2576 {
2577 #ifdef USE_NODE_CB_VALIDATE
2578         /* add extra info */
2579         bNodeClipboardExtraInfo *node_info = MEM_mallocN(sizeof(bNodeClipboardExtraInfo), "bNodeClipboardExtraInfo");
2580
2581         node_info->id = node->id;
2582         if (node->id) {
2583                 BLI_strncpy(node_info->id_name, node->id->name, sizeof(node_info->id_name));
2584                 if (node->id->lib) {
2585                         BLI_strncpy(node_info->library_name, node->id->lib->filepath, sizeof(node_info->library_name));
2586                 }
2587                 else {
2588                         node_info->library_name[0] = '\0';
2589                 }
2590         }
2591         else {
2592                 node_info->id_name[0] = '\0';
2593                 node_info->library_name[0] = '\0';
2594         }
2595         BLI_addtail(&node_clipboard.nodes_extra_info, node_info);
2596         /* end extra info */
2597 #endif  /* USE_NODE_CB_VALIDATE */
2598
2599         /* add node */
2600         BLI_addtail(&node_clipboard.nodes, node);
2601
2602 }
2603
2604 void BKE_node_clipboard_add_link(bNodeLink *link)
2605 {
2606         BLI_addtail(&node_clipboard.links, link);
2607 }
2608
2609 const ListBase *BKE_node_clipboard_get_nodes(void)
2610 {
2611         return &node_clipboard.nodes;
2612 }
2613
2614 const ListBase *BKE_node_clipboard_get_links(void)
2615 {
2616         return &node_clipboard.links;
2617 }
2618
2619 int BKE_node_clipboard_get_type(void)
2620 {
2621         return node_clipboard.type;
2622 }
2623
2624
2625 /* Node Instance Hash */
2626
2627 /* magic number for initial hash key */
2628 const bNodeInstanceKey NODE_INSTANCE_KEY_BASE = {5381};
2629 const bNodeInstanceKey NODE_INSTANCE_KEY_NONE = {0};
2630
2631 /* Generate a hash key from ntree and node names
2632  * Uses the djb2 algorithm with xor by Bernstein:
2633  * http://www.cse.yorku.ca/~oz/hash.html
2634  */
2635 static bNodeInstanceKey node_hash_int_str(bNodeInstanceKey hash, const char *str)
2636 {
2637         char c;
2638         
2639         while ((c = *str++))
2640                 hash.value = ((hash.value << 5) + hash.value) ^ c; /* (hash * 33) ^ c */
2641         
2642         /* separator '\0' character, to avoid ambiguity from concatenated strings */
2643         hash.value = (hash.value << 5) + hash.value; /* hash * 33 */
2644         
2645         return hash;
2646 }
2647
2648 bNodeInstanceKey BKE_node_instance_key(bNodeInstanceKey parent_key, bNodeTree *ntree, bNode *node)
2649 {
2650         bNodeInstanceKey key;
2651         
2652         key = node_hash_int_str(parent_key, ntree->id.name + 2);
2653         
2654         if (node)
2655                 key = node_hash_int_str(key, node->name);
2656         
2657         return key;
2658 }
2659
2660 static unsigned int node_instance_hash_key(const void *key)
2661 {
2662         return ((const bNodeInstanceKey *)key)->value;
2663 }
2664
2665 static int node_instance_hash_key_cmp(const void *a, const void *b)
2666 {
2667         unsigned int value_a = ((const bNodeInstanceKey *)a)->value;
2668         unsigned int value_b = ((const bNodeInstanceKey *)b)->value;
2669         if (value_a == value_b)
2670                 return 0;
2671         else if (value_a < value_b)
2672                 return -1;
2673         else
2674                 return 1;
2675 }
2676
2677 bNodeInstanceHash *BKE_node_instance_hash_new(const char *info)
2678 {
2679         bNodeInstanceHash *hash = MEM_mallocN(sizeof(bNodeInstanceHash), info);
2680         hash->ghash = BLI_ghash_new(node_instance_hash_key, node_instance_hash_key_cmp, "node instance hash ghash");
2681         return hash;
2682 }
2683
2684 void BKE_node_instance_hash_free(bNodeInstanceHash *hash, bNodeInstanceValueFP valfreefp)
2685 {
2686         BLI_ghash_free(hash->ghash, NULL, (GHashValFreeFP)valfreefp);
2687         MEM_freeN(hash);
2688 }
2689
2690 void BKE_node_instance_hash_insert(bNodeInstanceHash *hash, bNodeInstanceKey key, void *value)
2691 {
2692         bNodeInstanceHashEntry *entry = value;
2693         entry->key = key;
2694         entry->tag = 0;
2695         BLI_ghash_insert(hash->ghash, &entry->key, value);
2696 }
2697
2698 void *BKE_node_instance_hash_lookup(bNodeInstanceHash *hash, bNodeInstanceKey key)
2699 {
2700         return BLI_ghash_lookup(hash->ghash, &key);
2701 }
2702
2703 int BKE_node_instance_hash_remove(bNodeInstanceHash *hash, bNodeInstanceKey key, bNodeInstanceValueFP valfreefp)
2704 {
2705         return BLI_ghash_remove(hash->ghash, &key, NULL, (GHashValFreeFP)valfreefp);
2706 }
2707
2708 void BKE_node_instance_hash_clear(bNodeInstanceHash *hash, bNodeInstanceValueFP valfreefp)
2709 {
2710         BLI_ghash_clear(hash->ghash, NULL, (GHashValFreeFP)valfreefp);
2711 }
2712
2713 void *BKE_node_instance_hash_pop(bNodeInstanceHash *hash, bNodeInstanceKey key)
2714 {
2715         return BLI_ghash_popkey(hash->ghash, &key, NULL);
2716 }
2717
2718 int BKE_node_instance_hash_haskey(bNodeInstanceHash *hash, bNodeInstanceKey key)
2719 {
2720         return BLI_ghash_haskey(hash->ghash, &key);
2721 }
2722
2723 int BKE_node_instance_hash_size(bNodeInstanceHash *hash)
2724 {
2725         return BLI_ghash_size(hash->ghash);
2726 }
2727
2728 void BKE_node_instance_hash_clear_tags(bNodeInstanceHash *hash)
2729 {
2730         bNodeInstanceHashIterator iter;
2731         
2732         NODE_INSTANCE_HASH_ITER(iter, hash) {
2733                 bNodeInstanceHashEntry *value = BKE_node_instance_hash_iterator_get_value(&iter);
2734                 
2735                 value->tag = 0;
2736         }
2737 }
2738
2739 void BKE_node_instance_hash_tag(bNodeInstanceHash *UNUSED(hash), void *value)
2740 {
2741         bNodeInstanceHashEntry *entry = value;
2742         entry->tag = 1;
2743 }
2744
2745 int BKE_node_instance_hash_tag_key(bNodeInstanceHash *hash, bNodeInstanceKey key)
2746 {
2747         bNodeInstanceHashEntry *entry = BKE_node_instance_hash_lookup(hash, key);
2748         
2749         if (entry) {
2750                 entry->tag = 1;
2751                 return TRUE;
2752         }
2753         else
2754                 return FALSE;
2755 }
2756
2757 void BKE_node_instance_hash_remove_untagged(bNodeInstanceHash *hash, bNodeInstanceValueFP valfreefp)
2758 {
2759         /* NOTE: Hash must not be mutated during iterating!
2760          * Store tagged entries in a separate list and remove items afterward.
2761          */
2762         bNodeInstanceKey *untagged = MEM_mallocN(sizeof(bNodeInstanceKey) * BKE_node_instance_hash_size(hash), "temporary node instance key list");
2763         bNodeInstanceHashIterator iter;
2764         int num_untagged, i;
2765         
2766         num_untagged = 0;
2767         NODE_INSTANCE_HASH_ITER(iter, hash) {
2768                 bNodeInstanceHashEntry *value = BKE_node_instance_hash_iterator_get_value(&iter);
2769                 
2770                 if (!value->tag)
2771                         untagged[num_untagged++] = BKE_node_instance_hash_iterator_get_key(&iter);
2772         }
2773         
2774         for (i = 0; i < num_untagged; ++i) {
2775                 BKE_node_instance_hash_remove(hash, untagged[i], valfreefp);
2776         }
2777         
2778         MEM_freeN(untagged);
2779 }
2780
2781
2782 /* ************** dependency stuff *********** */
2783
2784 /* node is guaranteed to be not checked before */
2785 static int node_get_deplist_recurs(bNodeTree *ntree, bNode *node, bNode ***nsort)
2786 {
2787         bNode *fromnode;
2788         bNodeLink *link;
2789         int level = 0xFFF;
2790         
2791         node->done = TRUE;
2792         
2793         /* check linked nodes */
2794         for (link = ntree->links.first; link; link = link->next) {
2795                 if (link->tonode == node) {
2796                         fromnode = link->fromnode;
2797                         if (fromnode->done == 0)
2798                                 fromnode->level = node_get_deplist_recurs(ntree, fromnode, nsort);
2799                         if (fromnode->level <= level)
2800                                 level = fromnode->level - 1;
2801                 }
2802         }
2803         
2804         /* check parent node */
2805         if (node->parent) {
2806                 if (node->parent->done == 0)
2807                         node->parent->level = node_get_deplist_recurs(ntree, node->parent, nsort);
2808                 if (node->parent->level <= level)
2809                         level = node->parent->level - 1;
2810         }
2811         
2812         if (nsort) {
2813                 **nsort = node;
2814                 (*nsort)++;
2815         }
2816         
2817         return level;
2818 }
2819
2820 void ntreeGetDependencyList(struct bNodeTree *ntree, struct bNode ***deplist, int *totnodes)
2821 {
2822         bNode *node, **nsort;
2823         
2824         *totnodes = 0;
2825         
2826         /* first clear data */
2827         for (node = ntree->nodes.first; node; node = node->next) {
2828                 node->done = FALSE;
2829                 (*totnodes)++;
2830         }
2831         if (*totnodes == 0) {
2832                 *deplist = NULL;
2833                 return;
2834         }
2835         
2836         nsort = *deplist = MEM_callocN((*totnodes) * sizeof(bNode *), "sorted node array");
2837         
2838         /* recursive check */
2839         for (node = ntree->nodes.first; node; node = node->next) {
2840                 if (node->done == 0) {
2841                         node->level = node_get_deplist_recurs(ntree, node, &nsort);
2842                 }
2843         }
2844 }
2845
2846 /* only updates node->level for detecting cycles links */
2847 static void ntree_update_node_level(bNodeTree *ntree)
2848 {
2849         bNode *node;
2850         
2851         /* first clear tag */
2852         for (node = ntree->nodes.first; node; node = node->next) {
2853                 node->done = FALSE;
2854         }
2855         
2856         /* recursive check */
2857         for (node = ntree->nodes.first; node; node = node->next) {
2858                 if (node->done == 0) {
2859                         node->level = node_get_deplist_recurs(ntree, node, NULL);
2860                 }
2861         }
2862 }
2863
2864 static void ntree_update_link_pointers(bNodeTree *ntree)
2865 {
2866         bNode *node;
2867         bNodeSocket *sock;
2868         bNodeLink *link;
2869         
2870         /* first clear data */
2871         for (node = ntree->nodes.first; node; node = node->next) {
2872                 for (sock = node->inputs.first; sock; sock = sock->next) {
2873                         sock->link = NULL;
2874                         sock->flag &= ~SOCK_IN_USE;
2875                 }
2876                 for (sock = node->outputs.first; sock; sock = sock->next) {
2877                         sock->flag &= ~SOCK_IN_USE;
2878                 }
2879         }
2880
2881         for (link = ntree->links.first; link; link = link->next) {
2882                 link->tosock->link = link;
2883                 
2884                 link->fromsock->flag |= SOCK_IN_USE;
2885                 link->tosock->flag |= SOCK_IN_USE;
2886         }
2887 }
2888
2889 static void ntree_validate_links(bNodeTree *ntree)
2890 {
2891         bNodeLink *link;
2892         
2893         for (link = ntree->links.first; link; link = link->next) {
2894                 link->flag |= NODE_LINK_VALID;
2895                 if (link->fromnode && link->tonode && link->fromnode->level <= link->tonode->level)
2896                         link->flag &= ~NODE_LINK_VALID;
2897                 else if (ntree->typeinfo->validate_link) {
2898                         if (!ntree->typeinfo->validate_link(ntree, link))
2899                                 link->flag &= ~NODE_LINK_VALID;
2900                 }
2901         }
2902 }
2903
2904 void ntreeVerifyNodes(struct Main *main, struct ID *id)
2905 {
2906         FOREACH_NODETREE(main, ntree, owner_id) {
2907                 bNode *node;
2908                 
2909                 for (node = ntree->nodes.first; node; node = node->next)
2910                         if (node->typeinfo->verifyfunc)
2911                                 node->typeinfo->verifyfunc(ntree, node, id);
2912         } FOREACH_NODETREE_END
2913 }
2914
2915 void ntreeUpdateTree(Main *bmain, bNodeTree *ntree)
2916 {
2917         bNode *node;
2918         
2919         if (!ntree)
2920                 return;
2921         
2922         /* avoid reentrant updates, can be caused by RNA update callbacks */
2923         if (ntree->is_updating)
2924                 return;
2925         ntree->is_updating = TRUE;
2926         
2927         if (ntree->update & (NTREE_UPDATE_LINKS | NTREE_UPDATE_NODES)) {
2928                 /* set the bNodeSocket->link pointers */
2929                 ntree_update_link_pointers(ntree);
2930         }
2931         
2932         /* update individual nodes */
2933         for (node = ntree->nodes.first; node; node = node->next) {
2934                 /* node tree update tags override individual node update flags */
2935                 if ((node->update & NODE_UPDATE) || (ntree->update & NTREE_UPDATE)) {
2936                         if (node->typeinfo->updatefunc)
2937                                 node->typeinfo->updatefunc(ntree, node);
2938                         
2939                         nodeUpdateInternalLinks(ntree, node);
2940                 }
2941         }
2942         
2943         /* generic tree update callback */
2944         if (ntree->typeinfo->update)
2945                 ntree->typeinfo->update(ntree);
2946         /* XXX this should be moved into the tree type update callback for tree supporting node groups.
2947          * Currently the node tree interface is still a generic feature of the base NodeTree type.
2948          */
2949         if (ntree->update & NTREE_UPDATE_GROUP)
2950                 ntreeInterfaceTypeUpdate(ntree);
2951         
2952         /* XXX hack, should be done by depsgraph!! */
2953         if (bmain)
2954                 ntreeVerifyNodes(bmain, &ntree->id);
2955         
2956         if (ntree->update & (NTREE_UPDATE_LINKS | NTREE_UPDATE_NODES)) {
2957                 /* node updates can change sockets or links, repeat link pointer update afterward */
2958                 ntree_update_link_pointers(ntree);
2959                 
2960                 /* update the node level from link dependencies */
2961                 ntree_update_node_level(ntree);
2962                 
2963                 /* check link validity */
2964                 ntree_validate_links(ntree);
2965         }
2966         
2967         /* clear update flags */
2968         for (node = ntree->nodes.first; node; node = node->next) {
2969                 node->update = 0;
2970         }
2971         ntree->update = 0;
2972         
2973         ntree->is_updating = FALSE;
2974 }
2975
2976 void nodeUpdate(bNodeTree *ntree, bNode *node)
2977 {
2978         /* avoid reentrant updates, can be caused by RNA update callbacks */
2979         if (ntree->is_updating)
2980                 return;
2981         ntree->is_updating = TRUE;
2982         
2983         if (node->typeinfo->updatefunc)
2984                 node->typeinfo->updatefunc(ntree, node);
2985         
2986         nodeUpdateInternalLinks(ntree, node);
2987         
2988         /* clear update flag */
2989         node->update = 0;
2990         
2991         ntree->is_updating = FALSE;
2992 }
2993
2994 bool nodeUpdateID(bNodeTree *ntree, ID *id)
2995 {
2996         bNode *node;
2997         bool changed = false;
2998         
2999         if (ELEM(NULL, id, ntree))
3000                 return changed;
3001         
3002         /* avoid reentrant updates, can be caused by RNA update callbacks */
3003         if (ntree->is_updating)
3004                 return changed;
3005         ntree->is_updating = true;
3006         
3007         for (node = ntree->nodes.first; node; node = node->next) {
3008                 if (node->id == id) {
3009                         changed = true;
3010                         node->update |= NODE_UPDATE_ID;
3011                         if (node->typeinfo->updatefunc)
3012                                 node->typeinfo->updatefunc(ntree, node);
3013                         /* clear update flag */
3014                         node->update = 0;
3015                 }
3016         }
3017         
3018         for (node = ntree->nodes.first; node; node = node->next) {
3019                 nodeUpdateInternalLinks(ntree, node);
3020         }
3021         
3022         ntree->is_updating = FALSE;
3023         return changed;
3024 }
3025
3026 void nodeUpdateInternalLinks(bNodeTree *ntree, bNode *node)
3027 {
3028         BLI_freelistN(&node->internal_links);
3029         
3030         if (node->typeinfo && node->typeinfo->update_internal_links)
3031                 node->typeinfo->update_internal_links(ntree, node);
3032 }
3033
3034
3035 /* nodes that use ID data get synced with local data */
3036 void nodeSynchronizeID(bNode *node, bool copy_to_id)
3037 {
3038         if (node->id == NULL) return;
3039         
3040         if (ELEM(node->type, SH_NODE_MATERIAL, SH_NODE_MATERIAL_EXT)) {
3041                 bNodeSocket *sock;
3042                 Material *ma = (Material *)node->id;
3043                 int a;
3044                 
3045                 /* hrmf, case in loop isn't super fast, but we don't edit 100s of material at same time either! */
3046                 for (a = 0, sock = node->inputs.first; sock; sock = sock->next, a++) {
3047                         if (!nodeSocketIsHidden(sock)) {
3048                                 if (copy_to_id) {
3049                                         switch (a) {
3050                                                 case MAT_IN_COLOR:
3051                                                         copy_v3_v3(&ma->r, ((bNodeSocketValueRGBA *)sock->default_value)->value); break;
3052                                                 case MAT_IN_SPEC:
3053                                                         copy_v3_v3(&ma->specr, ((bNodeSocketValueRGBA *)sock->default_value)->value); break;
3054                                                 case MAT_IN_REFL:
3055                                                         ma->ref = ((bNodeSocketValueFloat *)sock->default_value)->value; break;
3056                                                 case MAT_IN_MIR:
3057                                                         copy_v3_v3(&ma->mirr, ((bNodeSocketValueRGBA *)sock->default_value)->value); break;
3058                                                 case MAT_IN_AMB:
3059                                                         ma->amb = ((bNodeSocketValueFloat *)sock->default_value)->value; break;
3060                                                 case MAT_IN_EMIT:
3061                                                         ma->emit = ((bNodeSocketValueFloat *)sock->default_value)->value; break;
3062                                                 case MAT_IN_SPECTRA:
3063                                                         ma->spectra = ((bNodeSocketValueFloat *)sock->default_value)->value; break;
3064                                                 case MAT_IN_RAY_MIRROR:
3065                                                         ma->ray_mirror = ((bNodeSocketValueFloat *)sock->default_value)->value; break;
3066                                                 case MAT_IN_ALPHA:
3067                                                         ma->alpha = ((bNodeSocketValueFloat *)sock->default_value)->value; break;
3068                                                 case MAT_IN_TRANSLUCENCY:
3069                                                         ma->translucency = ((bNodeSocketValueFloat *)sock->default_value)->value; break;
3070                                         }
3071                                 }
3072                                 else {
3073                                         switch (a) {
3074                                                 case MAT_IN_COLOR:
3075                                                         copy_v3_v3(((bNodeSocketValueRGBA *)sock->default_value)->value, &ma->r); break;
3076                                                 case MAT_IN_SPEC:
3077                                                         copy_v3_v3(((bNodeSocketValueRGBA *)sock->default_value)->value, &ma->specr); break;
3078                                                 case MAT_IN_REFL:
3079                                                         ((bNodeSocketValueFloat *)sock->default_value)->value = ma->ref; break;
3080                                                 case MAT_IN_MIR:
3081                                                         copy_v3_v3(((bNodeSocketValueRGBA *)sock->default_value)->value, &ma->mirr); break;
3082                                                 case MAT_IN_AMB:
3083                                                         ((bNodeSocketValueFloat *)sock->default_value)->value = ma->amb; break;
3084                                                 case MAT_IN_EMIT:
3085                                                         ((bNodeSocketValueFloat *)sock->default_value)->value = ma->emit; break;
3086                                                 case MAT_IN_SPECTRA:
3087                                                         ((bNodeSocketValueFloat *)sock->default_value)->value = ma->spectra; break;
3088                                                 case MAT_IN_RAY_MIRROR:
3089                                                         ((bNodeSocketValueFloat *)sock->default_value)->value = ma->ray_mirror; break;
3090                                                 case MAT_IN_ALPHA:
3091                                                         ((bNodeSocketValueFloat *)sock->default_value)->value = ma->alpha; break;
3092                                                 case MAT_IN_TRANSLUCENCY:
3093                                                         ((bNodeSocketValueFloat *)sock->default_value)->value = ma->translucency; break;
3094                                         }
3095                                 }
3096                         }
3097                 }
3098         }
3099 }
3100
3101
3102 /* ************* node type access ********** */
3103
3104 void nodeLabel(bNodeTree *ntree, bNode *node, char *label, int maxlen)
3105 {
3106         if (node->label[0] != '\0')
3107                 BLI_strncpy(label, node->label, maxlen);
3108         else if (node->typeinfo->labelfunc)
3109                 node->typeinfo->labelfunc(ntree, node, label, maxlen);
3110         else
3111                 BLI_strncpy(label, IFACE_(node->typeinfo->ui_name), maxlen);
3112 }
3113
3114 static void node_type_base_defaults(bNodeType *ntype)
3115 {
3116         /* default size values */
3117         node_type_size_preset(ntype, NODE_SIZE_DEFAULT);
3118         ntype->height = 100;
3119         ntype->minheight = 30;
3120         ntype->maxheight = FLT_MAX;
3121 }
3122
3123 /* allow this node for any tree type */
3124 static int node_poll_default(bNodeType *UNUSED(ntype), bNodeTree *UNUSED(ntree))
3125 {
3126         return TRUE;
3127 }
3128
3129 /* use the basic poll function */
3130 static int node_poll_instance_default(bNode *node, bNodeTree *ntree)
3131 {
3132         return node->typeinfo->poll(node->typeinfo, ntree);
3133 }
3134
3135 void node_type_base(bNodeType *ntype, int type, const char *name, short nclass, short flag)
3136 {
3137         /* Use static type info header to map static int type to identifier string and RNA struct type.
3138          * Associate the RNA struct type with the bNodeType.
3139          * Dynamically registered nodes will create an RNA type at runtime
3140          * and call RNA_struct_blender_type_set, so this only needs to be done for old RNA types
3141          * created in makesrna, which can not be associated to a bNodeType immediately,
3142          * since bNodeTypes are registered afterward ...
3143          */
3144 #define DefNode(Category, ID, DefFunc, EnumName, StructName, UIName, UIDesc) \
3145                 case ID: \
3146                         BLI_strncpy(ntype->idname, #Category #StructName, sizeof(ntype->idname)); \
3147                         ntype->ext.srna = RNA_struct_find(#Category #StructName); \
3148                         BLI_assert(ntype->ext.srna != NULL); \
3149                         RNA_struct_blender_type_set(ntype->ext.srna, ntype); \
3150                         break;
3151         
3152         switch (type) {
3153 #include "NOD_static_types.h"
3154         }
3155         
3156         /* make sure we have a valid type (everything registered) */
3157         BLI_assert(ntype->idname[0] != '\0');
3158         
3159         ntype->type = type;
3160         BLI_strncpy(ntype->ui_name, name, sizeof(ntype->ui_name));
3161         ntype->nclass = nclass;
3162         ntype->flag = flag;
3163
3164         node_type_base_defaults(ntype);
3165
3166         ntype->poll = node_poll_default;
3167         ntype->poll_instance = node_poll_instance_default;
3168 }
3169
3170 void node_type_base_custom(bNodeType *ntype, const char *idname, const char *name, short nclass, short flag)
3171 {
3172         BLI_strncpy(ntype->idname, idname, sizeof(ntype->idname));
3173         ntype->type = NODE_CUSTOM;
3174         BLI_strncpy(ntype->ui_name, name, sizeof(ntype->ui_name));
3175         ntype->nclass = nclass;
3176         ntype->flag = flag;
3177
3178         node_type_base_defaults(ntype);
3179 }
3180
3181 static bool unique_socket_template_identifier_check(void *arg, const char *name)
3182 {
3183         bNodeSocketTemplate *ntemp;
3184         struct {bNodeSocketTemplate *list; bNodeSocketTemplate *ntemp;} *data = arg;
3185         
3186         for (ntemp = data->list; ntemp->type >= 0; ++ntemp) {
3187                 if (ntemp != data->ntemp) {
3188                         if (STREQ(ntemp->identifier, name)) {
3189                                 return true;
3190                         }
3191                 }
3192         }
3193         
3194         return false;
3195 }
3196
3197 static void unique_socket_template_identifier(bNodeSocketTemplate *list, bNodeSocketTemplate *ntemp, const char defname[], char delim)
3198 {
3199         struct {bNodeSocketTemplate *list; bNodeSocketTemplate *ntemp;} data;
3200         data.list = list;
3201         data.ntemp = ntemp;
3202
3203         BLI_uniquename_cb(unique_socket_template_identifier_check, &data, defname, delim, ntemp->identifier, sizeof(ntemp->identifier));
3204 }
3205
3206 void node_type_socket_templates(struct bNodeType *ntype, struct bNodeSocketTemplate *inputs, struct bNodeSocketTemplate *outputs)
3207 {
3208         bNodeSocketTemplate *ntemp;
3209         
3210         ntype->inputs = inputs;
3211         ntype->outputs = outputs;
3212         
3213         /* automatically generate unique identifiers */
3214         if (inputs) {
3215                 /* clear identifier strings (uninitialized memory) */
3216                 for (ntemp = inputs; ntemp->type >= 0; ++ntemp)
3217                         ntemp->identifier[0] = '\0';
3218                 
3219                 for (ntemp = inputs; ntemp->type >= 0; ++ntemp) {
3220                         BLI_strncpy(ntemp->identifier, ntemp->name, sizeof(ntemp->identifier));
3221                         unique_socket_template_identifier(inputs, ntemp, ntemp->identifier, '_');
3222                 }
3223         }
3224         if (outputs) {
3225                 /* clear identifier strings (uninitialized memory) */
3226                 for (ntemp = outputs; ntemp->type >= 0; ++ntemp)
3227                         ntemp->identifier[0] = '\0';
3228                 
3229                 for (ntemp = outputs; ntemp->type >= 0; ++ntemp) {
3230                         BLI_strncpy(ntemp->identifier, ntemp->name, sizeof(ntemp->identifier));
3231                         unique_socket_template_identifier(outputs, ntemp, ntemp->identifier, '_');
3232                 }
3233         }
3234 }
3235
3236 void node_type_init(struct bNodeType *ntype, void (*initfunc)(struct bNodeTree *ntree, struct bNode *node))
3237 {
3238         ntype->initfunc = initfunc;
3239 }
3240
3241 void node_type_size(struct bNodeType *ntype, int width, int minwidth, int maxwidth)
3242 {
3243         ntype->width = width;
3244         ntype->minwidth = minwidth;
3245         if (maxwidth <= minwidth)
3246                 ntype->maxwidth = FLT_MAX;
3247         else
3248                 ntype->maxwidth = maxwidth;
3249 }
3250
3251 void node_type_size_preset(struct bNodeType *ntype, eNodeSizePreset size)
3252 {
3253         switch (size) {
3254                 case NODE_SIZE_DEFAULT:
3255                         node_type_size(ntype, 140, 100, 320);
3256                         break;
3257                 case NODE_SIZE_SMALL:
3258                         node_type_size(ntype, 100, 80, 320);
3259                         break;
3260                 case NODE_SIZE_MIDDLE:
3261                         node_type_size(ntype, 150, 120, 320);
3262                         break;
3263                 case NODE_SIZE_LARGE:
3264                         node_type_size(ntype, 240, 140, 320);
3265                         break;
3266         }
3267 }
3268
3269 void node_type_storage(bNodeType *ntype,
3270         const char *storagename,
3271         void (*freefunc)(struct bNode *node),
3272         void (*copyfunc)(struct bNodeTree *dest_ntree, struct bNode *dest_node, struct bNode *src_node))
3273 {