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