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