doxygen: blender/blenkernel tagged.
[blender.git] / source / blender / blenkernel / intern / node.c
1 /*
2  * $Id$
3  *
4  * ***** BEGIN GPL LICENSE BLOCK *****
5  *
6  * This program is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU General Public License
8  * as published by the Free Software Foundation; either version 2
9  * of the License, or (at your option) any later version. 
10  *
11  * This program is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software Foundation,
18  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
19  *
20  * The Original Code is Copyright (C) 2005 Blender Foundation.
21  * All rights reserved.
22  *
23  * The Original Code is: all of this file.
24  *
25  * Contributor(s): Bob Holcomb.
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  */
29
30 /** \file blender/blenkernel/intern/node.c
31  *  \ingroup bke
32  */
33
34
35 #ifdef WITH_PYTHON
36 #include <Python.h>
37 #endif
38
39 #include "MEM_guardedalloc.h"
40
41 #include <stdlib.h>
42 #include <stddef.h>
43 #include <string.h>
44 #include <limits.h>
45
46 #include "DNA_anim_types.h"
47 #include "DNA_action_types.h"
48 #include "DNA_node_types.h"
49
50 #include "BLI_listbase.h"
51
52 #include "RNA_access.h"
53
54 #include "BKE_animsys.h"
55 #include "BKE_action.h"
56 #include "BKE_fcurve.h"
57 #include "BKE_node.h"
58 #include "BKE_utildefines.h"
59 #include "BKE_node.h"
60
61 #include "PIL_time.h"
62
63 #include "CMP_node.h"
64 #include "intern/CMP_util.h"    /* stupid include path... */
65
66 #include "SHD_node.h"
67 #include "TEX_node.h"
68 #include "intern/TEX_util.h"
69
70 #include "GPU_material.h"
71
72 static ListBase empty_list = {NULL, NULL};
73 ListBase node_all_composit = {NULL, NULL};
74 ListBase node_all_shaders = {NULL, NULL};
75 ListBase node_all_textures = {NULL, NULL};
76
77 /* ************** Type stuff **********  */
78
79 static bNodeType *node_get_type(bNodeTree *ntree, int type, ID *id)
80 {
81         bNodeType *ntype = ntree->alltypes.first;
82         for(; ntype; ntype= ntype->next)
83                 if(ntype->type==type && id==ntype->id )
84                         return ntype;
85         
86         return NULL;
87 }
88
89 void ntreeInitTypes(bNodeTree *ntree)
90 {
91         bNode *node, *next;
92         
93         if(ntree->type==NTREE_SHADER)
94                 ntree->alltypes= node_all_shaders;
95         else if(ntree->type==NTREE_COMPOSIT)
96                 ntree->alltypes= node_all_composit;
97         else if(ntree->type==NTREE_TEXTURE)
98                 ntree->alltypes= node_all_textures;
99         else {
100                 ntree->alltypes= empty_list;
101                 printf("Error: no type definitions for nodes\n");
102         }
103         
104         for(node= ntree->nodes.first; node; node= next) {
105                 next= node->next;
106                 if(node->type==NODE_DYNAMIC) {
107                         bNodeType *stype= NULL;
108                         if(node->id==NULL) { /* empty script node */
109                                 stype= node_get_type(ntree, node->type, NULL);
110                         } else { /* not an empty script node */
111                                 stype= node_get_type(ntree, node->type, node->id);
112                                 if(!stype) {
113                                         stype= node_get_type(ntree, node->type, NULL);
114                                         /* needed info if the pynode script fails now: */
115                                         if (node->id) node->storage= ntree;
116                                 } else {
117                                         node->custom1= 0;
118                                         node->custom1= BSET(node->custom1,NODE_DYNAMIC_ADDEXIST);
119                                 }
120                         }
121                         node->typeinfo= stype;
122                         if(node->typeinfo)
123                                 node->typeinfo->initfunc(node);
124                 } else {
125                         node->typeinfo= node_get_type(ntree, node->type, NULL);
126                 }
127
128                 if(node->typeinfo==NULL) {
129                         printf("Error: Node type %s doesn't exist anymore, removed\n", node->name);
130                         nodeFreeNode(ntree, node);
131                 }
132         }
133                         
134         ntree->init |= NTREE_TYPE_INIT;
135 }
136
137 /* updates node with (modified) bNodeType.. this should be done for all trees */
138 void ntreeUpdateType(bNodeTree *ntree, bNodeType *ntype)
139 {
140         bNode *node;
141
142         for(node= ntree->nodes.first; node; node= node->next) {
143                 if(node->typeinfo== ntype) {
144                         nodeUpdateType(ntree, node, ntype);
145                 }
146         }
147 }
148
149 /* only used internal... we depend on type definitions! */
150 static bNodeSocket *node_add_socket_type(ListBase *lb, bNodeSocketType *stype)
151 {
152         bNodeSocket *sock= MEM_callocN(sizeof(bNodeSocket), "sock");
153         
154         BLI_strncpy(sock->name, stype->name, NODE_MAXSTR);
155         if(stype->limit==0) sock->limit= 0xFFF;
156         else sock->limit= stype->limit;
157         sock->type= stype->type;
158         
159         sock->ns.vec[0]= stype->val1;
160         sock->ns.vec[1]= stype->val2;
161         sock->ns.vec[2]= stype->val3;
162         sock->ns.vec[3]= stype->val4;
163         sock->ns.min= stype->min;
164         sock->ns.max= stype->max;
165         
166         if(lb)
167                 BLI_addtail(lb, sock);
168
169         return sock;
170 }
171
172 static bNodeSocket *node_add_group_socket(ListBase *lb, bNodeSocket *gsock)
173 {
174         bNodeSocket *sock= MEM_callocN(sizeof(bNodeSocket), "sock");
175         
176         /* make a copy of the group socket */
177         *sock = *gsock;
178         sock->link = NULL;
179         sock->next = sock->prev = NULL;
180         sock->new_sock = NULL;
181         sock->ns.data = NULL;
182         
183         sock->own_index = gsock->own_index;
184         sock->groupsock = gsock;
185         /* XXX hack: group socket input/output roles are inverted internally,
186          * need to change the limit value when making actual node sockets from them.
187          */
188         sock->limit = (gsock->limit==1 ? 0xFFF : 1);
189         
190         if(lb)
191                 BLI_addtail(lb, sock);
192
193         return sock;
194 }
195
196 static void node_rem_socket(bNodeTree *ntree, ListBase *lb, bNodeSocket *sock)
197 {
198         bNodeLink *link, *next;
199         
200         for(link= ntree->links.first; link; link= next) {
201                 next= link->next;
202                 if(link->fromsock==sock || link->tosock==sock) {
203                         nodeRemLink(ntree, link);
204                 }
205         }
206         
207         BLI_remlink(lb, sock);
208         MEM_freeN(sock);
209 }
210
211 static bNodeSocket *verify_socket(ListBase *lb, bNodeSocketType *stype)
212 {
213         bNodeSocket *sock;
214         
215         for(sock= lb->first; sock; sock= sock->next) {
216                 if(strncmp(sock->name, stype->name, NODE_MAXSTR)==0)
217                         break;
218         }
219         if(sock) {
220                 sock->type= stype->type;                /* in future, read this from tydefs! */
221                 if(stype->limit==0) sock->limit= 0xFFF;
222                 else sock->limit= stype->limit;
223                 
224                 sock->ns.min= stype->min;
225                 sock->ns.max= stype->max;
226                 
227                 BLI_remlink(lb, sock);
228                 
229                 return sock;
230         }
231         else {
232                 return node_add_socket_type(NULL, stype);
233         }
234 }
235
236 static bNodeSocket *verify_group_socket(ListBase *lb, bNodeSocket *gsock)
237 {
238         bNodeSocket *sock;
239         
240         for(sock= lb->first; sock; sock= sock->next) {
241                 if(sock->own_index==gsock->own_index)
242                                 break;
243         }
244         if(sock) {
245                 sock->groupsock = gsock;
246                 
247                 strcpy(sock->name, gsock->name);
248                 sock->type= gsock->type;
249                 
250                 /* XXX hack: group socket input/output roles are inverted internally,
251                  * need to change the limit value when making actual node sockets from them.
252                  */
253                 sock->limit = (gsock->limit==1 ? 0xFFF : 1);
254                 
255                 sock->ns.min= gsock->ns.min;
256                 sock->ns.max= gsock->ns.max;
257                 
258                 BLI_remlink(lb, sock);
259                 
260                 return sock;
261         }
262         else {
263                 return node_add_group_socket(NULL, gsock);
264         }
265 }
266
267 static void verify_socket_list(bNodeTree *ntree, ListBase *lb, bNodeSocketType *stype_first)
268 {
269         bNodeSocketType *stype;
270         
271         /* no inputs anymore? */
272         if(stype_first==NULL) {
273                 while(lb->first)
274                         node_rem_socket(ntree, lb, lb->first);
275         }
276         else {
277                 /* step by step compare */
278                 stype= stype_first;
279                 while(stype->type != -1) {
280                         stype->sock= verify_socket(lb, stype);
281                         stype++;
282                 }
283                 /* leftovers are removed */
284                 while(lb->first)
285                         node_rem_socket(ntree, lb, lb->first);
286                 /* and we put back the verified sockets */
287                 stype= stype_first;
288                 while(stype->type != -1) {
289                         BLI_addtail(lb, stype->sock);
290                         stype++;
291                 }
292         }
293 }
294
295 static void verify_group_socket_list(bNodeTree *ntree, ListBase *lb, ListBase *glb)
296 {
297         bNodeSocket *gsock;
298         
299         /* step by step compare */
300         for (gsock= glb->first; gsock; gsock=gsock->next) {
301                 /* abusing new_sock pointer for verification here! only used inside this function */
302                 gsock->new_sock= verify_group_socket(lb, gsock);
303         }
304         /* leftovers are removed */
305         while(lb->first)
306                 node_rem_socket(ntree, lb, lb->first);
307         /* and we put back the verified sockets */
308         for (gsock= glb->first; gsock; gsock=gsock->next) {
309                 BLI_addtail(lb, gsock->new_sock);
310                 gsock->new_sock = NULL;
311         }
312 }
313
314 void nodeVerifyType(bNodeTree *ntree, bNode *node)
315 {
316         /* node groups don't have static sock lists, but use external sockets from the tree instead */
317         if (node->type==NODE_GROUP) {
318                 bNodeTree *ngroup= (bNodeTree*)node->id;
319                 if (ngroup) {
320                         verify_group_socket_list(ntree, &node->inputs, &ngroup->inputs);
321                         verify_group_socket_list(ntree, &node->outputs, &ngroup->outputs);
322                 }
323         }
324         else {
325                 bNodeType *ntype= node->typeinfo;
326                 if(ntype) {
327                         verify_socket_list(ntree, &node->inputs, ntype->inputs);
328                         verify_socket_list(ntree, &node->outputs, ntype->outputs);
329                 }
330         }
331 }
332
333 void ntreeVerifyTypes(bNodeTree *ntree)
334 {
335         bNode *node;
336         
337         /* if((ntree->init & NTREE_TYPE_INIT)==0) */
338         ntreeInitTypes(ntree);
339
340         /* check inputs and outputs, and remove or insert them */
341         for(node= ntree->nodes.first; node; node= node->next)
342                 nodeVerifyType(ntree, node);
343         
344 }
345
346 /* ************** Group stuff ********** */
347
348 /* XXX group typeinfo struct is used directly in ntreeMakeOwnType, needs cleanup */
349 static bNodeType ntype_group;
350
351 /* groups display their internal tree name as label */
352 static const char *group_label(bNode *node)
353 {
354         return node->id->name+2;
355 }
356
357 void register_node_type_group(ListBase *lb)
358 {
359         node_type_base(&ntype_group, NODE_GROUP, "Group", NODE_CLASS_GROUP, NODE_OPTIONS, NULL, NULL);
360         node_type_size(&ntype_group, 120, 60, 200);
361         node_type_label(&ntype_group, group_label);
362         
363         nodeRegisterType(lb, &ntype_group);
364 }
365
366 static bNodeSocket *find_group_node_input(bNode *gnode, bNodeSocket *gsock)
367 {
368         bNodeSocket *sock;
369         for (sock=gnode->inputs.first; sock; sock=sock->next)
370                 if (sock->groupsock == gsock)
371                         return sock;
372         return NULL;
373 }
374
375 static bNodeSocket *find_group_node_output(bNode *gnode, bNodeSocket *gsock)
376 {
377         bNodeSocket *sock;
378         for (sock=gnode->outputs.first; sock; sock=sock->next)
379                 if (sock->groupsock == gsock)
380                         return sock;
381         return NULL;
382 }
383
384 bNode *nodeMakeGroupFromSelected(bNodeTree *ntree)
385 {
386         bNodeLink *link, *linkn;
387         bNode *node, *gnode, *nextn;
388         bNodeTree *ngroup;
389         bNodeSocket *gsock;
390         ListBase anim_basepaths = {NULL, NULL};
391         float min[2], max[2];
392         int totnode=0;
393         
394         INIT_MINMAX2(min, max);
395         
396         /* is there something to group? also do some clearing */
397         for(node= ntree->nodes.first; node; node= node->next) {
398                 if(node->flag & NODE_SELECT) {
399                         /* no groups in groups */
400                         if(node->type==NODE_GROUP)
401                                 return NULL;
402                         DO_MINMAX2( (&node->locx), min, max);
403                         totnode++;
404                 }
405                 node->done= 0;
406         }
407         if(totnode==0) return NULL;
408         
409         /* check if all connections are OK, no unselected node has both
410                 inputs and outputs to a selection */
411         for(link= ntree->links.first; link; link= link->next) {
412                 if(link->fromnode && link->tonode && link->fromnode->flag & NODE_SELECT)
413                         link->tonode->done |= 1;
414                 if(link->fromnode && link->tonode && link->tonode->flag & NODE_SELECT)
415                         link->fromnode->done |= 2;
416         }       
417         
418         for(node= ntree->nodes.first; node; node= node->next) {
419                 if((node->flag & NODE_SELECT)==0)
420                         if(node->done==3)
421                                 break;
422         }
423         if(node) 
424                 return NULL;
425         
426         /* OK! new nodetree */
427         ngroup= ntreeAddTree("NodeGroup", ntree->type, TRUE);
428         
429         /* move nodes over */
430         for(node= ntree->nodes.first; node; node= nextn) {
431                 nextn= node->next;
432                 if(node->flag & NODE_SELECT) {
433                         /* keep track of this node's RNA "base" path (the part of the pat identifying the node) 
434                          * if the old nodetree has animation data which potentially covers this node
435                          */
436                         if (ntree->adt) {
437                                 PointerRNA ptr;
438                                 char *path;
439                                 
440                                 RNA_pointer_create(&ntree->id, &RNA_Node, node, &ptr);
441                                 path = RNA_path_from_ID_to_struct(&ptr);
442                                 
443                                 if (path)
444                                         BLI_addtail(&anim_basepaths, BLI_genericNodeN(path));
445                         }
446                         
447                         /* change node-collection membership */
448                         BLI_remlink(&ntree->nodes, node);
449                         BLI_addtail(&ngroup->nodes, node);
450                         
451                         node->locx-= 0.5f*(min[0]+max[0]);
452                         node->locy-= 0.5f*(min[1]+max[1]);
453                 }
454         }
455
456         /* move animation data over */
457         if (ntree->adt) {
458                 LinkData *ld, *ldn=NULL;
459                 
460                 BKE_animdata_separate_by_basepath(&ntree->id, &ngroup->id, &anim_basepaths);
461                 
462                 /* paths + their wrappers need to be freed */
463                 for (ld = anim_basepaths.first; ld; ld = ldn) {
464                         ldn = ld->next;
465                         
466                         MEM_freeN(ld->data);
467                         BLI_freelinkN(&anim_basepaths, ld);
468                 }
469         }
470         
471         /* make group node */
472         gnode= nodeAddNodeType(ntree, NODE_GROUP, ngroup, NULL);
473         gnode->locx= 0.5f*(min[0]+max[0]);
474         gnode->locy= 0.5f*(min[1]+max[1]);
475         
476         /* relink external sockets */
477         for(link= ntree->links.first; link; link= linkn) {
478                 linkn= link->next;
479                 
480                 if(link->fromnode && link->tonode && (link->fromnode->flag & link->tonode->flag & NODE_SELECT)) {
481                         BLI_remlink(&ntree->links, link);
482                         BLI_addtail(&ngroup->links, link);
483                 }
484                 else if(link->tonode && (link->tonode->flag & NODE_SELECT)) {
485                         gsock = nodeGroupExposeSocket(ngroup, link->tosock, SOCK_IN);
486                         link->tosock->link = nodeAddLink(ngroup, NULL, gsock, link->tonode, link->tosock);
487                         link->tosock = node_add_group_socket(&gnode->inputs, gsock);
488                         link->tonode = gnode;
489                 }
490                 else if(link->fromnode && (link->fromnode->flag & NODE_SELECT)) {
491                         /* search for existing group node socket */
492                         for (gsock=ngroup->outputs.first; gsock; gsock=gsock->next)
493                                 if (gsock->link && gsock->link->fromsock==link->fromsock)
494                                         break;
495                         if (!gsock) {
496                                 gsock = nodeGroupExposeSocket(ngroup, link->fromsock, SOCK_OUT);
497                                 gsock->link = nodeAddLink(ngroup, link->fromnode, link->fromsock, NULL, gsock);
498                                 link->fromsock = node_add_group_socket(&gnode->outputs, gsock);
499                         }
500                         else
501                                 link->fromsock = find_group_node_output(gnode, gsock);
502                         link->fromnode = gnode;
503                 }
504         }
505
506         /* update node levels */
507         ntreeSolveOrder(ntree);
508
509         return gnode;
510 }
511
512 /* here's a nasty little one, need to check users... */
513 /* should become callbackable... */
514 void nodeGroupVerify(bNodeTree *ngroup)
515 {
516         /* group changed, so we rebuild the type definition */
517 //      ntreeMakeGroupSockets(ngroup);
518         
519         if(ngroup->type==NTREE_SHADER) {
520                 Material *ma;
521                 for(ma= G.main->mat.first; ma; ma= ma->id.next) {
522                         if(ma->nodetree) {
523                                 bNode *node;
524                                 for(node= ma->nodetree->nodes.first; node; node= node->next)
525                                         if(node->id == (ID *)ngroup)
526                                                 nodeVerifyType(ma->nodetree, node);
527                         }
528                 }
529         }
530         else if(ngroup->type==NTREE_COMPOSIT) {
531                 Scene *sce;
532                 for(sce= G.main->scene.first; sce; sce= sce->id.next) {
533                         if(sce->nodetree) {
534                                 bNode *node;
535                                 for(node= sce->nodetree->nodes.first; node; node= node->next)
536                                         if(node->id == (ID *)ngroup)
537                                                 nodeVerifyType(sce->nodetree, node);
538                         }
539                 }
540         }
541         else if(ngroup->type==NTREE_TEXTURE) {
542                 Tex *tx;
543                 for(tx= G.main->tex.first; tx; tx= tx->id.next) {
544                         if(tx->nodetree) {
545                                 bNode *node;
546                                 for(node= tx->nodetree->nodes.first; node; node= node->next)
547                                         if(node->id == (ID *)ngroup)
548                                                 nodeVerifyType(tx->nodetree, node);
549                         }
550                 }
551         }
552 }
553
554 /* also to check all users of groups. Now only used in editor for hide/unhide */
555 /* should become callbackable? */
556 void nodeGroupSocketUseFlags(bNodeTree *ngroup)
557 {
558         bNode *node;
559         bNodeSocket *sock;
560
561         /* clear flags */
562         for(node= ngroup->nodes.first; node; node= node->next) {
563                 for(sock= node->inputs.first; sock; sock= sock->next)
564                         sock->flag &= ~SOCK_IN_USE;
565                 for(sock= node->outputs.first; sock; sock= sock->next)
566                         sock->flag &= ~SOCK_IN_USE;
567         }
568         
569         /* tag all thats in use */
570         if(ngroup->type==NTREE_SHADER) {
571                 Material *ma;
572                 for(ma= G.main->mat.first; ma; ma= ma->id.next) {
573                         if(ma->nodetree) {
574                                 for(node= ma->nodetree->nodes.first; node; node= node->next) {
575                                         if(node->id==&ngroup->id) {
576                                                 for(sock= node->inputs.first; sock; sock= sock->next)
577                                                         if(sock->link)
578                                                                 if(sock->groupsock) 
579                                                                         sock->groupsock->flag |= SOCK_IN_USE;
580                                                 for(sock= node->outputs.first; sock; sock= sock->next)
581                                                         if(nodeCountSocketLinks(ma->nodetree, sock))
582                                                                 if(sock->groupsock) 
583                                                                         sock->groupsock->flag |= SOCK_IN_USE;
584                                         }
585                                 }
586                         }
587                 }
588         }
589         else if(ngroup->type==NTREE_COMPOSIT) {
590                 Scene *sce;
591                 for(sce= G.main->scene.first; sce; sce= sce->id.next) {
592                         if(sce->nodetree) {
593                                 for(node= sce->nodetree->nodes.first; node; node= node->next) {
594                                         if(node->id==(ID *)ngroup) {
595                                                 for(sock= node->inputs.first; sock; sock= sock->next)
596                                                         if(sock->link)
597                                                                 if(sock->groupsock) 
598                                                                         sock->groupsock->flag |= SOCK_IN_USE;
599                                                 for(sock= node->outputs.first; sock; sock= sock->next)
600                                                         if(nodeCountSocketLinks(sce->nodetree, sock))
601                                                                 if(sock->groupsock) 
602                                                                         sock->groupsock->flag |= SOCK_IN_USE;
603                                         }
604                                 }
605                         }
606                 }
607         }
608         else if(ngroup->type==NTREE_TEXTURE) {
609                 Tex *tx;
610                 for(tx= G.main->tex.first; tx; tx= tx->id.next) {
611                         if(tx->nodetree) {
612                                 for(node= tx->nodetree->nodes.first; node; node= node->next) {
613                                         if(node->id==(ID *)ngroup) {
614                                                 for(sock= node->inputs.first; sock; sock= sock->next)
615                                                         if(sock->link)
616                                                                 if(sock->groupsock) 
617                                                                         sock->groupsock->flag |= SOCK_IN_USE;
618                                                 for(sock= node->outputs.first; sock; sock= sock->next)
619                                                         if(nodeCountSocketLinks(tx->nodetree, sock))
620                                                                 if(sock->groupsock) 
621                                                                         sock->groupsock->flag |= SOCK_IN_USE;
622                                         }
623                                 }
624                         }
625                 }
626         }
627         
628 }
629 /* finds a node based on its name */
630 bNode *nodeFindNodebyName(bNodeTree *ntree, const char *name)
631 {
632         return BLI_findstring(&ntree->nodes, name, offsetof(bNode, name));
633 }
634
635 /* finds a node based on given socket */
636 int nodeFindNode(bNodeTree *ntree, bNodeSocket *sock, bNode **nodep, int *sockindex, int *in_out)
637 {
638         bNode *node;
639         bNodeSocket *tsock;
640         int index= 0;
641         
642         for(node= ntree->nodes.first; node; node= node->next) {
643                 for(index=0, tsock= node->inputs.first; tsock; tsock= tsock->next, index++) {
644                         if(tsock==sock) {
645                                 if (in_out) *in_out= SOCK_IN;
646                                 break;
647                         }
648                 }
649                 if(tsock)
650                         break;
651                 for(index=0, tsock= node->outputs.first; tsock; tsock= tsock->next, index++) {
652                         if(tsock==sock) {
653                                 if (in_out) *in_out= SOCK_OUT;
654                                 break;
655                         }
656                 }
657                 if(tsock)
658                         break;
659         }
660
661         if(node) {
662                 *nodep= node;
663                 if(sockindex) *sockindex= index;
664                 return 1;
665         }
666         
667         *nodep= NULL;
668         return 0;
669 }
670
671 /* returns 1 if its OK */
672 int nodeGroupUnGroup(bNodeTree *ntree, bNode *gnode)
673 {
674         bNodeLink *link, *linkn;
675         bNode *node, *nextn;
676         bNodeTree *ngroup, *wgroup;
677         ListBase anim_basepaths = {NULL, NULL};
678         
679         ngroup= (bNodeTree *)gnode->id;
680         if(ngroup==NULL) return 0;
681         
682         /* clear new pointers, set in copytree */
683         for(node= ntree->nodes.first; node; node= node->next)
684                 node->new_node= NULL;
685         
686         /* wgroup is a temporary copy of the NodeTree we're merging in
687          *      - all of wgroup's nodes are transferred across to their new home
688          *      - ngroup (i.e. the source NodeTree) is left unscathed
689          */
690         wgroup= ntreeCopyTree(ngroup);
691         
692         /* add the nodes into the ntree */
693         for(node= wgroup->nodes.first; node; node= nextn) {
694                 nextn= node->next;
695                 
696                 /* keep track of this node's RNA "base" path (the part of the pat identifying the node) 
697                  * if the old nodetree has animation data which potentially covers this node
698                  */
699                 if (wgroup->adt) {
700                         PointerRNA ptr;
701                         char *path;
702                         
703                         RNA_pointer_create(&wgroup->id, &RNA_Node, node, &ptr);
704                         path = RNA_path_from_ID_to_struct(&ptr);
705                         
706                         if (path)
707                                 BLI_addtail(&anim_basepaths, BLI_genericNodeN(path));
708                 }
709                 
710                 /* migrate node */
711                 BLI_remlink(&wgroup->nodes, node);
712                 BLI_addtail(&ntree->nodes, node);
713                 
714                 node->locx+= gnode->locx;
715                 node->locy+= gnode->locy;
716                 
717                 node->flag |= NODE_SELECT;
718         }
719         
720         /* restore external links to and from the gnode */
721         for(link= ntree->links.first; link; link= link->next) {
722                 if (link->fromnode==gnode) {
723                         if (link->fromsock->groupsock) {
724                                 bNodeSocket *gsock= link->fromsock->groupsock;
725                                 if (gsock->link) {
726                                         if (gsock->link->fromnode) {
727                                                 /* NB: using the new internal copies here! the groupsock pointer still maps to the old tree */
728                                                 link->fromnode = (gsock->link->fromnode ? gsock->link->fromnode->new_node : NULL);
729                                                 link->fromsock = gsock->link->fromsock->new_sock;
730                                         }
731                                         else {
732                                                 /* group output directly maps to group input */
733                                                 bNodeSocket *insock= find_group_node_input(gnode, gsock->link->fromsock);
734                                                 if (insock->link) {
735                                                         link->fromnode = insock->link->fromnode;
736                                                         link->fromsock = insock->link->fromsock;
737                                                 }
738                                         }
739                                 }
740                                 else {
741                                         /* constant group output: copy the stack value to the external socket.
742                                          * the link is kept here until all possible external users have been fixed.
743                                          */
744                                         QUATCOPY(link->tosock->ns.vec, gsock->ns.vec);
745                                 }
746                         }
747                 }
748         }
749         /* remove internal output links, these are not used anymore */
750         for(link=wgroup->links.first; link; link= linkn) {
751                 linkn = link->next;
752                 if (!link->tonode)
753                         nodeRemLink(wgroup, link);
754         }
755         /* restore links from internal nodes */
756         for(link= wgroup->links.first; link; link= link->next) {
757                 /* indicates link to group input */
758                 if (!link->fromnode) {
759                         /* NB: can't use find_group_node_input here,
760                          * because gnode sockets still point to the old tree!
761                          */
762                         bNodeSocket *insock;
763                         for (insock= gnode->inputs.first; insock; insock= insock->next)
764                                 if (insock->groupsock->new_sock == link->fromsock)
765                                         break;
766                         if (insock->link) {
767                                 link->fromnode = insock->link->fromnode;
768                                 link->fromsock = insock->link->fromsock;
769                         }
770                         else {
771                                 /* uses group constant input. copy the input value and remove the dead link. */
772                                 QUATCOPY(link->tosock->ns.vec, insock->ns.vec);
773                                 nodeRemLink(wgroup, link);
774                         }
775                 }
776         }
777         
778         /* add internal links to the ntree */
779         for(link= wgroup->links.first; link; link= linkn) {
780                 linkn= link->next;
781                 BLI_remlink(&wgroup->links, link);
782                 BLI_addtail(&ntree->links, link);
783         }
784         
785         /* and copy across the animation */
786         if (wgroup->adt) {
787                 LinkData *ld, *ldn=NULL;
788                 bAction *waction;
789                 
790                 /* firstly, wgroup needs to temporary dummy action that can be destroyed, as it shares copies */
791                 waction = wgroup->adt->action = copy_action(wgroup->adt->action);
792                 
793                 /* now perform the moving */
794                 BKE_animdata_separate_by_basepath(&wgroup->id, &ntree->id, &anim_basepaths);
795                 
796                 /* paths + their wrappers need to be freed */
797                 for (ld = anim_basepaths.first; ld; ld = ldn) {
798                         ldn = ld->next;
799                         
800                         MEM_freeN(ld->data);
801                         BLI_freelinkN(&anim_basepaths, ld);
802                 }
803                 
804                 /* free temp action too */
805                 free_libblock(&G.main->action, waction);
806         }
807         
808         /* delete the group instance. this also removes old input links! */
809         nodeFreeNode(ntree, gnode);
810         
811         /* free the group tree (takes care of user count) */
812         free_libblock(&G.main->nodetree, wgroup);
813         
814         /* solve order goes fine, but the level tags not... doing it twice works for now. solve this once */
815         /* XXX is this still necessary with new groups? it may have been caused by non-updated sock->link pointers. lukas */
816         ntreeSolveOrder(ntree);
817         ntreeSolveOrder(ntree);
818
819         return 1;
820 }
821
822 void nodeGroupCopy(bNode *gnode)
823 {
824         bNodeSocket *sock;
825
826         gnode->id->us--;
827         gnode->id= (ID *)ntreeCopyTree((bNodeTree *)gnode->id);
828
829         /* new_sock was set in nodeCopyNode */
830         for(sock=gnode->inputs.first; sock; sock=sock->next)
831                 if(sock->groupsock)
832                         sock->groupsock= sock->groupsock->new_sock;
833
834         for(sock=gnode->outputs.first; sock; sock=sock->next)
835                 if(sock->groupsock)
836                         sock->groupsock= sock->groupsock->new_sock;
837 }
838
839 bNodeSocket *nodeGroupAddSocket(bNodeTree *ngroup, const char *name, int type, int in_out)
840 {
841         bNodeSocket *gsock = MEM_callocN(sizeof(bNodeSocket), "bNodeSocket");
842         
843         strncpy(gsock->name, name, sizeof(gsock->name));
844         gsock->type = type;
845         gsock->ns.sockettype = type;
846         gsock->ns.min = INT_MIN;
847         gsock->ns.max = INT_MAX;
848         zero_v4(gsock->ns.vec);
849         gsock->ns.data = NULL;
850         gsock->flag = 0;
851
852         gsock->next = gsock->prev = NULL;
853         gsock->new_sock = NULL;
854         gsock->link = NULL;
855         gsock->ns.data = NULL;
856         /* assign new unique index */
857         gsock->own_index = ngroup->cur_index++;
858         gsock->limit = (in_out==SOCK_IN ? 0xFFF : 1);
859         
860         BLI_addtail(in_out==SOCK_IN ? &ngroup->inputs : &ngroup->outputs, gsock);
861         
862         return gsock;
863 }
864
865 bNodeSocket *nodeGroupExposeSocket(bNodeTree *ngroup, bNodeSocket *sock, int in_out)
866 {
867         bNodeSocket *gsock= nodeGroupAddSocket(ngroup, sock->name, sock->type, in_out);
868         /* initialize the default socket value */
869         QUATCOPY(gsock->ns.vec, sock->ns.vec);
870         return gsock;
871 }
872
873 void nodeGroupExposeAllSockets(bNodeTree *ngroup)
874 {
875         bNode *node;
876         bNodeSocket *sock, *gsock;
877         
878         for (node=ngroup->nodes.first; node; node=node->next) {
879                 for (sock=node->inputs.first; sock; sock=sock->next) {
880                         if (!sock->link && !(sock->flag & SOCK_HIDDEN)) {
881                                 gsock = nodeGroupAddSocket(ngroup, sock->name, sock->type, SOCK_IN);
882                                 /* initialize the default socket value */
883                                 QUATCOPY(gsock->ns.vec, sock->ns.vec);
884                                 sock->link = nodeAddLink(ngroup, NULL, gsock, node, sock);
885                         }
886                 }
887                 for (sock=node->outputs.first; sock; sock=sock->next) {
888                         if (nodeCountSocketLinks(ngroup, sock)==0 && !(sock->flag & SOCK_HIDDEN)) {
889                                 gsock = nodeGroupAddSocket(ngroup, sock->name, sock->type, SOCK_OUT);
890                                 /* initialize the default socket value */
891                                 QUATCOPY(gsock->ns.vec, sock->ns.vec);
892                                 gsock->link = nodeAddLink(ngroup, node, sock, NULL, gsock);
893                         }
894                 }
895         }
896 }
897
898 void nodeGroupRemoveSocket(bNodeTree *ngroup, bNodeSocket *gsock, int in_out)
899 {
900         nodeRemSocketLinks(ngroup, gsock);
901         switch (in_out) {
902         case SOCK_IN:   BLI_remlink(&ngroup->inputs, gsock);    break;
903         case SOCK_OUT:  BLI_remlink(&ngroup->outputs, gsock);   break;
904         }
905 }
906
907 /* ************** Add stuff ********** */
908 void nodeAddSockets(bNode *node, bNodeType *ntype)
909 {
910         if (node->type==NODE_GROUP) {
911                 bNodeTree *ntree= (bNodeTree*)node->id;
912                 if (ntree) {
913                         bNodeSocket *gsock;
914                         for (gsock=ntree->inputs.first; gsock; gsock=gsock->next)
915                                 node_add_group_socket(&node->inputs, gsock);
916                         for (gsock=ntree->outputs.first; gsock; gsock=gsock->next)
917                                 node_add_group_socket(&node->outputs, gsock);
918                 }
919         }
920         else {
921                 bNodeSocketType *stype;
922                 
923                 if(ntype->inputs) {
924                         stype= ntype->inputs;
925                         while(stype->type != -1) {
926                                 node_add_socket_type(&node->inputs, stype);
927                                 stype++;
928                         }
929                 }
930                 if(ntype->outputs) {
931                         stype= ntype->outputs;
932                         while(stype->type != -1) {
933                                 node_add_socket_type(&node->outputs, stype);
934                                 stype++;
935                         }
936                 }
937         }
938 }
939
940 /* Find the first available, non-duplicate name for a given node */
941 void nodeUniqueName(bNodeTree *ntree, bNode *node)
942 {
943         BLI_uniquename(&ntree->nodes, node, "Node", '.', offsetof(bNode, name), sizeof(node->name));
944 }
945
946 bNode *nodeAddNodeType(bNodeTree *ntree, int type, bNodeTree *ngroup, ID *id)
947 {
948         bNode *node= NULL;
949         bNodeType *ntype= NULL;
950
951         if (ngroup && BLI_findindex(&G.main->nodetree, ngroup)==-1) {
952                 printf("nodeAddNodeType() error: '%s' not in main->nodetree\n", ngroup->id.name);
953                 return NULL;
954         }
955
956         if(type>=NODE_DYNAMIC_MENU) {
957                 int a=0, idx= type-NODE_DYNAMIC_MENU;
958                 ntype= ntree->alltypes.first;
959                 while(ntype) {
960                         if(ntype->type==NODE_DYNAMIC) {
961                                 if(a==idx)
962                                         break;
963                                 a++;
964                         }
965                         ntype= ntype->next;
966                 }
967         } else
968                 ntype= node_get_type(ntree, type, id);
969
970         node= MEM_callocN(sizeof(bNode), "new node");
971         BLI_addtail(&ntree->nodes, node);
972         node->typeinfo= ntype;
973         if(type>=NODE_DYNAMIC_MENU)
974                 node->custom2= type; /* for node_dynamic_init */
975
976         if(ngroup)
977                 BLI_strncpy(node->name, ngroup->id.name+2, NODE_MAXSTR);
978         else if(type>NODE_DYNAMIC_MENU) {
979                 BLI_strncpy(node->name, ntype->id->name+2, NODE_MAXSTR);
980         }
981         else
982                 BLI_strncpy(node->name, ntype->name, NODE_MAXSTR);
983
984         nodeUniqueName(ntree, node);
985         
986         node->type= ntype->type;
987         node->flag= NODE_SELECT|ntype->flag;
988         node->width= ntype->width;
989         node->miniwidth= 42.0f;         /* small value only, allows print of first chars */
990
991         if(type==NODE_GROUP)
992                 node->id= (ID *)ngroup;
993
994         /* need init handler later? */
995         /* got it-bob*/
996         if(ntype->initfunc!=NULL)
997                 ntype->initfunc(node);
998         
999         nodeAddSockets(node, ntype);
1000         
1001         return node;
1002 }
1003
1004 void nodeMakeDynamicType(bNode *node)
1005 {
1006         /* find SH_DYNAMIC_NODE ntype */
1007         bNodeType *ntype= node_all_shaders.first;
1008         while(ntype) {
1009                 if(ntype->type==NODE_DYNAMIC && ntype->id==NULL)
1010                         break;
1011                 ntype= ntype->next;
1012         }
1013
1014         /* make own type struct to fill */
1015         if(ntype) {
1016                 /*node->typeinfo= MEM_dupallocN(ntype);*/
1017                 bNodeType *newtype= MEM_callocN(sizeof(bNodeType), "dynamic bNodeType");
1018                 *newtype= *ntype;
1019                 newtype->name= BLI_strdup(ntype->name);
1020                 node->typeinfo= newtype;
1021         }
1022 }
1023
1024 void nodeUpdateType(bNodeTree *ntree, bNode* node, bNodeType *ntype)
1025 {
1026         verify_socket_list(ntree, &node->inputs, ntype->inputs);
1027         verify_socket_list(ntree, &node->outputs, ntype->outputs);
1028 }
1029
1030 /* keep socket listorder identical, for copying links */
1031 /* ntree is the target tree */
1032 bNode *nodeCopyNode(struct bNodeTree *ntree, struct bNode *node)
1033 {
1034         bNode *nnode= MEM_callocN(sizeof(bNode), "dupli node");
1035         bNodeSocket *sock, *oldsock;
1036
1037         *nnode= *node;
1038         nodeUniqueName(ntree, nnode);
1039         
1040         BLI_addtail(&ntree->nodes, nnode);
1041         
1042         BLI_duplicatelist(&nnode->inputs, &node->inputs);
1043         oldsock= node->inputs.first;
1044         for(sock= nnode->inputs.first; sock; sock= sock->next, oldsock= oldsock->next) {
1045                 oldsock->new_sock= sock;
1046         }
1047         
1048         BLI_duplicatelist(&nnode->outputs, &node->outputs);
1049         oldsock= node->outputs.first;
1050         for(sock= nnode->outputs.first; sock; sock= sock->next, oldsock= oldsock->next) {
1051                 sock->stack_index= 0;
1052                 sock->ns.data= NULL;
1053                 oldsock->new_sock= sock;
1054         }
1055         
1056         /* don't increase node->id users, freenode doesn't decrement either */
1057         
1058         if(node->typeinfo->copystoragefunc)
1059                 node->typeinfo->copystoragefunc(node, nnode);
1060         
1061         node->new_node= nnode;
1062         nnode->new_node= NULL;
1063         nnode->preview= NULL;
1064         
1065         return nnode;
1066 }
1067
1068 /* fromsock and tosock can be NULL */
1069 /* also used via rna api, so we check for proper input output direction */
1070 bNodeLink *nodeAddLink(bNodeTree *ntree, bNode *fromnode, bNodeSocket *fromsock, bNode *tonode, bNodeSocket *tosock)
1071 {
1072         bNodeSocket *sock;
1073         bNodeLink *link= NULL; 
1074         int from= 0, to= 0;
1075         
1076         if(fromnode) {
1077                 /* test valid input */
1078                 for(sock= fromnode->outputs.first; sock; sock= sock->next)
1079                         if(sock==fromsock)
1080                                 break;
1081                 if(sock)
1082                         from= 1; /* OK */
1083                 else {
1084                         for(sock= fromnode->inputs.first; sock; sock= sock->next)
1085                                 if(sock==fromsock)
1086                                         break;
1087                         if(sock)
1088                                 from= -1; /* OK but flip */
1089                 }
1090         }
1091         if(tonode) {
1092                 for(sock= tonode->inputs.first; sock; sock= sock->next)
1093                         if(sock==tosock)
1094                                 break;
1095                 if(sock)
1096                         to= 1; /* OK */
1097                 else {
1098                         for(sock= tonode->outputs.first; sock; sock= sock->next)
1099                                 if(sock==tosock)
1100                                         break;
1101                         if(sock)
1102                                 to= -1; /* OK but flip */
1103                 }
1104         }
1105         
1106         /* this allows NULL sockets to work */
1107         if(from >= 0 && to >= 0) {
1108                 link= MEM_callocN(sizeof(bNodeLink), "link");
1109                 BLI_addtail(&ntree->links, link);
1110                 link->fromnode= fromnode;
1111                 link->fromsock= fromsock;
1112                 link->tonode= tonode;
1113                 link->tosock= tosock;
1114         }
1115         else if(from <= 0 && to <= 0) {
1116                 link= MEM_callocN(sizeof(bNodeLink), "link");
1117                 BLI_addtail(&ntree->links, link);
1118                 link->fromnode= tonode;
1119                 link->fromsock= tosock;
1120                 link->tonode= fromnode;
1121                 link->tosock= fromsock;
1122         }
1123         
1124         return link;
1125 }
1126
1127 void nodeRemLink(bNodeTree *ntree, bNodeLink *link)
1128 {
1129         BLI_remlink(&ntree->links, link);
1130         if(link->tosock)
1131                 link->tosock->link= NULL;
1132         MEM_freeN(link);
1133 }
1134
1135 void nodeRemSocketLinks(bNodeTree *ntree, bNodeSocket *sock)
1136 {
1137         bNodeLink *link, *next;
1138         
1139         for(link= ntree->links.first; link; link= next) {
1140                 next= link->next;
1141                 if(link->fromsock==sock || link->tosock==sock) {
1142                         nodeRemLink(ntree, link);
1143                 }
1144         }
1145 }
1146
1147
1148 bNodeTree *ntreeAddTree(const char *name, int type, const short is_group)
1149 {
1150         bNodeTree *ntree;
1151
1152         if (is_group)
1153                 ntree= alloc_libblock(&G.main->nodetree, ID_NT, name);
1154         else {
1155                 ntree= MEM_callocN(sizeof(bNodeTree), "new node tree");
1156                 *( (short *)ntree->id.name )= ID_NT; /* not "type", as that is ntree->type */
1157                 BLI_strncpy(ntree->id.name+2, name, sizeof(ntree->id.name));
1158         }
1159
1160         ntree->type= type;
1161         ntree->alltypes.first = NULL;
1162         ntree->alltypes.last = NULL;
1163
1164         ntreeInitTypes(ntree);
1165         return ntree;
1166 }
1167
1168 /* Warning: this function gets called during some rather unexpected times
1169  *      - this gets called when executing compositing updates (for threaded previews)
1170  *      - when the nodetree datablock needs to be copied (i.e. when users get copied)
1171  *      - for scene duplication use ntreeSwapID() after so we dont have stale pointers.
1172  */
1173 bNodeTree *ntreeCopyTree(bNodeTree *ntree)
1174 {
1175         bNodeTree *newtree;
1176         bNode *node, *nnode, *last;
1177         bNodeLink *link;
1178         bNodeSocket *gsock, *oldgsock;
1179         
1180         if(ntree==NULL) return NULL;
1181         
1182         /* is ntree part of library? */
1183         for(newtree=G.main->nodetree.first; newtree; newtree= newtree->id.next)
1184                 if(newtree==ntree) break;
1185         if(newtree) {
1186                 newtree= copy_libblock(ntree);
1187         } else {
1188                 newtree= MEM_dupallocN(ntree);
1189                 copy_libblock_data(&newtree->id, &ntree->id, TRUE); /* copy animdata and ID props */
1190         }
1191         newtree->nodes.first= newtree->nodes.last= NULL;
1192         newtree->links.first= newtree->links.last= NULL;
1193         
1194         last = ntree->nodes.last;
1195         for(node= ntree->nodes.first; node; node= node->next) {
1196                 node->new_node= NULL;
1197                 nnode= nodeCopyNode(newtree, node);     /* sets node->new */
1198                 if(node==last) break;
1199         }
1200         
1201         /* socket definition for group usage */
1202         BLI_duplicatelist(&newtree->inputs, &ntree->inputs);
1203         for(gsock= newtree->inputs.first, oldgsock= ntree->inputs.first; gsock; gsock=gsock->next, oldgsock=oldgsock->next) {
1204                 oldgsock->new_sock= gsock;
1205                 gsock->groupsock = (oldgsock->groupsock ? oldgsock->groupsock->new_sock : NULL);
1206         }
1207         
1208         BLI_duplicatelist(&newtree->outputs, &ntree->outputs);
1209         for(gsock= newtree->outputs.first, oldgsock= ntree->outputs.first; gsock; gsock=gsock->next, oldgsock=oldgsock->next) {
1210                 oldgsock->new_sock= gsock;
1211                 gsock->groupsock = (oldgsock->groupsock ? oldgsock->groupsock->new_sock : NULL);
1212         }
1213
1214         /* copy links */
1215         BLI_duplicatelist(&newtree->links, &ntree->links);
1216         for(link= newtree->links.first; link; link= link->next) {
1217                 link->fromnode = (link->fromnode ? link->fromnode->new_node : NULL);
1218                 link->fromsock = (link->fromsock ? link->fromsock->new_sock : NULL);
1219                 link->tonode = (link->tonode ? link->tonode->new_node : NULL);
1220                 link->tosock = (link->tosock ? link->tosock->new_sock : NULL);
1221                 /* update the link socket's pointer */
1222                 if (link->tosock)
1223                         link->tosock->link = link;
1224         }
1225
1226         return newtree;
1227 }
1228
1229 /* use when duplicating scenes */
1230 void ntreeSwitchID(bNodeTree *ntree, ID *id_from, ID *id_to)
1231 {
1232         bNode *node;
1233         /* for scene duplication only */
1234         for(node= ntree->nodes.first; node; node= node->next) {
1235                 if(node->id==id_from) {
1236                         node->id= id_to;
1237                 }
1238         }
1239 }
1240
1241 /* *************** preview *********** */
1242 /* if node->preview, then we assume the rect to exist */
1243
1244 static void node_free_preview(bNode *node)
1245 {
1246         if(node->preview) {
1247                 if(node->preview->rect)
1248                         MEM_freeN(node->preview->rect);
1249                 MEM_freeN(node->preview);
1250                 node->preview= NULL;
1251         }       
1252 }
1253
1254 static void node_init_preview(bNode *node, int xsize, int ysize)
1255 {
1256         
1257         if(node->preview==NULL) {
1258                 node->preview= MEM_callocN(sizeof(bNodePreview), "node preview");
1259                 //              printf("added preview %s\n", node->name);
1260         }
1261         
1262         /* node previews can get added with variable size this way */
1263         if(xsize==0 || ysize==0)
1264                 return;
1265         
1266         /* sanity checks & initialize */
1267         if(node->preview->rect) {
1268                 if(node->preview->xsize!=xsize && node->preview->ysize!=ysize) {
1269                         MEM_freeN(node->preview->rect);
1270                         node->preview->rect= NULL;
1271                 }
1272         }
1273         
1274         if(node->preview->rect==NULL) {
1275                 node->preview->rect= MEM_callocN(4*xsize + xsize*ysize*sizeof(char)*4, "node preview rect");
1276                 node->preview->xsize= xsize;
1277                 node->preview->ysize= ysize;
1278         }
1279         /* no clear, makes nicer previews */
1280 }
1281
1282 void ntreeInitPreview(bNodeTree *ntree, int xsize, int ysize)
1283 {
1284         bNode *node;
1285         
1286         if(ntree==NULL)
1287                 return;
1288         
1289         for(node= ntree->nodes.first; node; node= node->next) {
1290                 if(node->typeinfo->flag & NODE_PREVIEW) /* hrms, check for closed nodes? */
1291                         node_init_preview(node, xsize, ysize);
1292                 if(node->type==NODE_GROUP && (node->flag & NODE_GROUP_EDIT))
1293                         ntreeInitPreview((bNodeTree *)node->id, xsize, ysize);
1294         }               
1295 }
1296
1297 static void nodeClearPreview(bNode *node)
1298 {
1299         if(node->preview && node->preview->rect)
1300                 memset(node->preview->rect, 0, MEM_allocN_len(node->preview->rect));
1301 }
1302
1303 /* use it to enforce clear */
1304 void ntreeClearPreview(bNodeTree *ntree)
1305 {
1306         bNode *node;
1307         
1308         if(ntree==NULL)
1309                 return;
1310         
1311         for(node= ntree->nodes.first; node; node= node->next) {
1312                 if(node->typeinfo->flag & NODE_PREVIEW)
1313                         nodeClearPreview(node);
1314                 if(node->type==NODE_GROUP && (node->flag & NODE_GROUP_EDIT))
1315                         ntreeClearPreview((bNodeTree *)node->id);
1316         }               
1317 }
1318
1319 /* hack warning! this function is only used for shader previews, and 
1320 since it gets called multiple times per pixel for Ztransp we only
1321 add the color once. Preview gets cleared before it starts render though */
1322 void nodeAddToPreview(bNode *node, float *col, int x, int y)
1323 {
1324         bNodePreview *preview= node->preview;
1325         if(preview) {
1326                 if(x>=0 && y>=0) {
1327                         if(x<preview->xsize && y<preview->ysize) {
1328                                 unsigned char *tar= preview->rect+ 4*((preview->xsize*y) + x);
1329                                 
1330                                 if(TRUE) {
1331                                         tar[0]= FTOCHAR(linearrgb_to_srgb(col[0]));
1332                                         tar[1]= FTOCHAR(linearrgb_to_srgb(col[1]));
1333                                         tar[2]= FTOCHAR(linearrgb_to_srgb(col[2]));
1334                                 }
1335                                 else {
1336                                         tar[0]= FTOCHAR(col[0]);
1337                                         tar[1]= FTOCHAR(col[1]);
1338                                         tar[2]= FTOCHAR(col[2]);
1339                                 }
1340                                 tar[3]= FTOCHAR(col[3]);
1341                         }
1342                         //else printf("prv out bound x y %d %d\n", x, y);
1343                 }
1344                 //else printf("prv out bound x y %d %d\n", x, y);
1345         }
1346 }
1347
1348
1349 /* ************** Free stuff ********** */
1350
1351 /* goes over entire tree */
1352 void nodeUnlinkNode(bNodeTree *ntree, bNode *node)
1353 {
1354         bNodeLink *link, *next;
1355         bNodeSocket *sock;
1356         ListBase *lb;
1357         
1358         for(link= ntree->links.first; link; link= next) {
1359                 next= link->next;
1360                 
1361                 if(link->fromnode==node) {
1362                         lb= &node->outputs;
1363                         if (link->tonode)
1364                                 NodeTagChanged(ntree, link->tonode);
1365                 }
1366                 else if(link->tonode==node)
1367                         lb= &node->inputs;
1368                 else
1369                         lb= NULL;
1370
1371                 if(lb) {
1372                         for(sock= lb->first; sock; sock= sock->next) {
1373                                 if(link->fromsock==sock || link->tosock==sock)
1374                                         break;
1375                         }
1376                         if(sock) {
1377                                 nodeRemLink(ntree, link);
1378                         }
1379                 }
1380         }
1381 }
1382
1383 static void composit_free_node_cache(bNode *node)
1384 {
1385         bNodeSocket *sock;
1386         
1387         for(sock= node->outputs.first; sock; sock= sock->next) {
1388                 if(sock->ns.data) {
1389                         free_compbuf(sock->ns.data);
1390                         sock->ns.data= NULL;
1391                 }
1392         }
1393 }
1394
1395 void nodeFreeNode(bNodeTree *ntree, bNode *node)
1396 {
1397         nodeUnlinkNode(ntree, node);
1398         BLI_remlink(&ntree->nodes, node);
1399
1400         /* since it is called while free database, node->id is undefined */
1401         
1402         if(ntree->type==NTREE_COMPOSIT)
1403                 composit_free_node_cache(node);
1404         BLI_freelistN(&node->inputs);
1405         BLI_freelistN(&node->outputs);
1406         
1407         node_free_preview(node);
1408
1409         if(node->typeinfo && node->typeinfo->freestoragefunc) {
1410                 node->typeinfo->freestoragefunc(node);
1411         }
1412
1413         MEM_freeN(node);
1414 }
1415
1416 /* do not free ntree itself here, free_libblock calls this function too */
1417 void ntreeFreeTree(bNodeTree *ntree)
1418 {
1419         bNode *node, *next;
1420         
1421         if(ntree==NULL) return;
1422         
1423         ntreeEndExecTree(ntree);        /* checks for if it is still initialized */
1424         
1425         BKE_free_animdata((ID *)ntree);
1426
1427         BLI_freelistN(&ntree->links);   /* do first, then unlink_node goes fast */
1428         
1429         for(node= ntree->nodes.first; node; node= next) {
1430                 next= node->next;
1431                 nodeFreeNode(ntree, node);
1432         }
1433         
1434         BLI_freelistN(&ntree->inputs);
1435         BLI_freelistN(&ntree->outputs);
1436 }
1437
1438 void ntreeFreeCache(bNodeTree *ntree)
1439 {
1440         bNode *node;
1441         
1442         if(ntree==NULL) return;
1443
1444         if(ntree->type==NTREE_COMPOSIT)
1445                 for(node= ntree->nodes.first; node; node= node->next)
1446                         composit_free_node_cache(node);
1447
1448 }
1449
1450 void ntreeMakeLocal(bNodeTree *ntree)
1451 {
1452         int local=0, lib=0;
1453         
1454         /* - only lib users: do nothing
1455                 * - only local users: set flag
1456                 * - mixed: make copy
1457                 */
1458         
1459         if(ntree->id.lib==NULL) return;
1460         if(ntree->id.us==1) {
1461                 ntree->id.lib= NULL;
1462                 ntree->id.flag= LIB_LOCAL;
1463                 new_id(NULL, (ID *)ntree, NULL);
1464                 return;
1465         }
1466         
1467         /* now check users of groups... again typedepending, callback... */
1468         if(ntree->type==NTREE_SHADER) {
1469                 Material *ma;
1470                 for(ma= G.main->mat.first; ma; ma= ma->id.next) {
1471                         if(ma->nodetree) {
1472                                 bNode *node;
1473                                 
1474                                 /* find if group is in tree */
1475                                 for(node= ma->nodetree->nodes.first; node; node= node->next) {
1476                                         if(node->id == (ID *)ntree) {
1477                                                 if(ma->id.lib) lib= 1;
1478                                                 else local= 1;
1479                                         }
1480                                 }
1481                         }
1482                 }
1483         }
1484         else if(ntree->type==NTREE_COMPOSIT) {
1485                 Scene *sce;
1486                 for(sce= G.main->scene.first; sce; sce= sce->id.next) {
1487                         if(sce->nodetree) {
1488                                 bNode *node;
1489                                 
1490                                 /* find if group is in tree */
1491                                 for(node= sce->nodetree->nodes.first; node; node= node->next) {
1492                                         if(node->id == (ID *)ntree) {
1493                                                 if(sce->id.lib) lib= 1;
1494                                                 else local= 1;
1495                                         }
1496                                 }
1497                         }
1498                 }
1499         }
1500         else if(ntree->type==NTREE_TEXTURE) {
1501                 Tex *tx;
1502                 for(tx= G.main->tex.first; tx; tx= tx->id.next) {
1503                         if(tx->nodetree) {
1504                                 bNode *node;
1505                                 
1506                                 /* find if group is in tree */
1507                                 for(node= tx->nodetree->nodes.first; node; node= node->next) {
1508                                         if(node->id == (ID *)ntree) {
1509                                                 if(tx->id.lib) lib= 1;
1510                                                 else local= 1;
1511                                         }
1512                                 }
1513                         }
1514                 }
1515         }
1516         
1517         /* if all users are local, we simply make tree local */
1518         if(local && lib==0) {
1519                 ntree->id.lib= NULL;
1520                 ntree->id.flag= LIB_LOCAL;
1521                 new_id(NULL, (ID *)ntree, NULL);
1522         }
1523         else if(local && lib) {
1524                 /* this is the mixed case, we copy the tree and assign it to local users */
1525                 bNodeTree *newtree= ntreeCopyTree(ntree);
1526                 
1527                 newtree->id.us= 0;
1528                 
1529                 if(ntree->type==NTREE_SHADER) {
1530                         Material *ma;
1531                         for(ma= G.main->mat.first; ma; ma= ma->id.next) {
1532                                 if(ma->nodetree) {
1533                                         bNode *node;
1534                                         
1535                                         /* find if group is in tree */
1536                                         for(node= ma->nodetree->nodes.first; node; node= node->next) {
1537                                                 if(node->id == (ID *)ntree) {
1538                                                         if(ma->id.lib==NULL) {
1539                                                                 node->id= &newtree->id;
1540                                                                 newtree->id.us++;
1541                                                                 ntree->id.us--;
1542                                                         }
1543                                                 }
1544                                         }
1545                                 }
1546                         }
1547                 }
1548                 else if(ntree->type==NTREE_COMPOSIT) {
1549                         Scene *sce;
1550                         for(sce= G.main->scene.first; sce; sce= sce->id.next) {
1551                                 if(sce->nodetree) {
1552                                         bNode *node;
1553                                         
1554                                         /* find if group is in tree */
1555                                         for(node= sce->nodetree->nodes.first; node; node= node->next) {
1556                                                 if(node->id == (ID *)ntree) {
1557                                                         if(sce->id.lib==NULL) {
1558                                                                 node->id= &newtree->id;
1559                                                                 newtree->id.us++;
1560                                                                 ntree->id.us--;
1561                                                         }
1562                                                 }
1563                                         }
1564                                 }
1565                         }
1566                 }
1567                 else if(ntree->type==NTREE_TEXTURE) {
1568                         Tex *tx;
1569                         for(tx= G.main->tex.first; tx; tx= tx->id.next) {
1570                                 if(tx->nodetree) {
1571                                         bNode *node;
1572                                         
1573                                         /* find if group is in tree */
1574                                         for(node= tx->nodetree->nodes.first; node; node= node->next) {
1575                                                 if(node->id == (ID *)ntree) {
1576                                                         if(tx->id.lib==NULL) {
1577                                                                 node->id= &newtree->id;
1578                                                                 newtree->id.us++;
1579                                                                 ntree->id.us--;
1580                                                         }
1581                                                 }
1582                                         }
1583                                 }
1584                         }
1585                 }
1586         }
1587 }
1588
1589
1590 /* ************ find stuff *************** */
1591
1592 static int ntreeHasType(bNodeTree *ntree, int type)
1593 {
1594         bNode *node;
1595         
1596         if(ntree)
1597                 for(node= ntree->nodes.first; node; node= node->next)
1598                         if(node->type == type)
1599                                 return 1;
1600         return 0;
1601 }
1602
1603 bNodeLink *nodeFindLink(bNodeTree *ntree, bNodeSocket *from, bNodeSocket *to)
1604 {
1605         bNodeLink *link;
1606         
1607         for(link= ntree->links.first; link; link= link->next) {
1608                 if(link->fromsock==from && link->tosock==to)
1609                         return link;
1610                 if(link->fromsock==to && link->tosock==from)    /* hrms? */
1611                         return link;
1612         }
1613         return NULL;
1614 }
1615
1616 int nodeCountSocketLinks(bNodeTree *ntree, bNodeSocket *sock)
1617 {
1618         bNodeLink *link;
1619         int tot= 0;
1620         
1621         for(link= ntree->links.first; link; link= link->next) {
1622                 if(link->fromsock==sock || link->tosock==sock)
1623                         tot++;
1624         }
1625         return tot;
1626 }
1627
1628 bNode *nodeGetActive(bNodeTree *ntree)
1629 {
1630         bNode *node;
1631         
1632         if(ntree==NULL) return NULL;
1633         
1634         for(node= ntree->nodes.first; node; node= node->next)
1635                 if(node->flag & NODE_ACTIVE)
1636                         break;
1637         return node;
1638 }
1639
1640 /* two active flags, ID nodes have special flag for buttons display */
1641 bNode *nodeGetActiveID(bNodeTree *ntree, short idtype)
1642 {
1643         bNode *node;
1644         
1645         if(ntree==NULL) return NULL;
1646
1647         /* check for group edit */
1648         for(node= ntree->nodes.first; node; node= node->next)
1649                 if(node->flag & NODE_GROUP_EDIT)
1650                         break;
1651
1652         if(node)
1653                 ntree= (bNodeTree*)node->id;
1654         
1655         /* now find active node with this id */
1656         for(node= ntree->nodes.first; node; node= node->next)
1657                 if(node->id && GS(node->id->name)==idtype)
1658                         if(node->flag & NODE_ACTIVE_ID)
1659                                 break;
1660
1661         return node;
1662 }
1663
1664 int nodeSetActiveID(bNodeTree *ntree, short idtype, ID *id)
1665 {
1666         bNode *node;
1667         int ok= FALSE;
1668
1669         if(ntree==NULL) return ok;
1670
1671         /* check for group edit */
1672         for(node= ntree->nodes.first; node; node= node->next)
1673                 if(node->flag & NODE_GROUP_EDIT)
1674                         break;
1675
1676         if(node)
1677                 ntree= (bNodeTree*)node->id;
1678
1679         /* now find active node with this id */
1680         for(node= ntree->nodes.first; node; node= node->next) {
1681                 if(node->id && GS(node->id->name)==idtype) {
1682                         if(id && ok==FALSE && node->id==id) {
1683                                 node->flag |= NODE_ACTIVE_ID;
1684                                 ok= TRUE;
1685                         } else {
1686                                 node->flag &= ~NODE_ACTIVE_ID;
1687                         }
1688                 }
1689         }
1690
1691         return ok;
1692 }
1693
1694
1695 /* two active flags, ID nodes have special flag for buttons display */
1696 void nodeClearActiveID(bNodeTree *ntree, short idtype)
1697 {
1698         bNode *node;
1699         
1700         if(ntree==NULL) return;
1701         
1702         for(node= ntree->nodes.first; node; node= node->next)
1703                 if(node->id && GS(node->id->name)==idtype)
1704                         node->flag &= ~NODE_ACTIVE_ID;
1705 }
1706
1707 /* two active flags, ID nodes have special flag for buttons display */
1708 void nodeSetActive(bNodeTree *ntree, bNode *node)
1709 {
1710         bNode *tnode;
1711         
1712         /* make sure only one node is active, and only one per ID type */
1713         for(tnode= ntree->nodes.first; tnode; tnode= tnode->next) {
1714                 tnode->flag &= ~NODE_ACTIVE;
1715                 
1716                 if(node->id && tnode->id) {
1717                         if(GS(node->id->name) == GS(tnode->id->name))
1718                                 tnode->flag &= ~NODE_ACTIVE_ID;
1719                 }
1720         }
1721         
1722         node->flag |= NODE_ACTIVE;
1723         if(node->id)
1724                 node->flag |= NODE_ACTIVE_ID;
1725 }
1726
1727 /* use flags are not persistant yet, groups might need different tagging, so we do it each time
1728    when we need to get this info */
1729 void ntreeSocketUseFlags(bNodeTree *ntree)
1730 {
1731         bNode *node;
1732         bNodeSocket *sock;
1733         bNodeLink *link;
1734         
1735         /* clear flags */
1736         for(node= ntree->nodes.first; node; node= node->next) {
1737                 for(sock= node->inputs.first; sock; sock= sock->next)
1738                         sock->flag &= ~SOCK_IN_USE;
1739                 for(sock= node->outputs.first; sock; sock= sock->next)
1740                         sock->flag &= ~SOCK_IN_USE;
1741         }
1742         
1743         /* tag all thats in use */
1744         for(link= ntree->links.first; link; link= link->next) {
1745         
1746                 if(link->fromsock) // FIXME, see below
1747                         link->fromsock->flag |= SOCK_IN_USE;
1748                 if(link->tosock) // FIXME This can be NULL, when dragging a new link in the UI, should probably copy the node tree for preview render - campbell
1749                         link->tosock->flag |= SOCK_IN_USE;
1750         }
1751 }
1752
1753 /* ************** dependency stuff *********** */
1754
1755 /* node is guaranteed to be not checked before */
1756 static int node_recurs_check(bNode *node, bNode ***nsort, int level)
1757 {
1758         bNode *fromnode;
1759         bNodeSocket *sock;
1760         int has_inputlinks= 0;
1761         
1762         node->done= 1;
1763         level++;
1764         
1765         for(sock= node->inputs.first; sock; sock= sock->next) {
1766                 if(sock->link) {
1767                         has_inputlinks= 1;
1768                         fromnode= sock->link->fromnode;
1769                         if(fromnode && fromnode->done==0) {
1770                                 fromnode->level= node_recurs_check(fromnode, nsort, level);
1771                         }
1772                 }
1773         }
1774 //      printf("node sort %s level %d\n", node->name, level);
1775         **nsort= node;
1776         (*nsort)++;
1777         
1778         if(has_inputlinks)
1779                 return level;
1780         else 
1781                 return 0xFFF;
1782 }
1783
1784
1785 static void ntreeSetOutput(bNodeTree *ntree)
1786 {
1787         bNode *node;
1788
1789         /* find the active outputs, might become tree type dependant handler */
1790         for(node= ntree->nodes.first; node; node= node->next) {
1791                 if(node->typeinfo->nclass==NODE_CLASS_OUTPUT) {
1792                         bNode *tnode;
1793                         int output= 0;
1794                         
1795                         /* we need a check for which output node should be tagged like this, below an exception */
1796                         if(node->type==CMP_NODE_OUTPUT_FILE)
1797                            continue;
1798                            
1799                         /* there is more types having output class, each one is checked */
1800                         for(tnode= ntree->nodes.first; tnode; tnode= tnode->next) {
1801                                 if(tnode->typeinfo->nclass==NODE_CLASS_OUTPUT) {
1802                                         
1803                                         if(ntree->type==NTREE_COMPOSIT) {
1804                                                         
1805                                                 /* same type, exception for viewer */
1806                                                 if(tnode->type==node->type ||
1807                                                    (ELEM(tnode->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER) &&
1808                                                         ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER))) {
1809                                                         if(tnode->flag & NODE_DO_OUTPUT) {
1810                                                                 output++;
1811                                                                 if(output>1)
1812                                                                         tnode->flag &= ~NODE_DO_OUTPUT;
1813                                                         }
1814                                                 }
1815                                         }
1816                                         else {
1817                                                 /* same type */
1818                                                 if(tnode->type==node->type) {
1819                                                         if(tnode->flag & NODE_DO_OUTPUT) {
1820                                                                 output++;
1821                                                                 if(output>1)
1822                                                                         tnode->flag &= ~NODE_DO_OUTPUT;
1823                                                         }
1824                                                 }
1825                                         }
1826                                 }
1827                         }
1828                         if(output==0)
1829                                 node->flag |= NODE_DO_OUTPUT;
1830                 }
1831         }
1832         
1833         /* here we could recursively set which nodes have to be done,
1834                 might be different for editor or for "real" use... */
1835 }
1836
1837 void ntreeSolveOrder(bNodeTree *ntree)
1838 {
1839         bNode *node, **nodesort, **nsort;
1840         bNodeSocket *sock;
1841         bNodeLink *link;
1842         int a, totnode=0;
1843         
1844         /* the solve-order is called on each tree change, so we should be sure no exec can be running */
1845         ntreeEndExecTree(ntree);
1846
1847         /* set links pointers the input sockets, to find dependencies */
1848         /* first clear data */
1849         for(node= ntree->nodes.first; node; node= node->next) {
1850                 node->done= 0;
1851                 totnode++;
1852                 for(sock= node->inputs.first; sock; sock= sock->next)
1853                         sock->link= NULL;
1854         }
1855         /* clear group socket links */
1856         for(sock= ntree->outputs.first; sock; sock= sock->next)
1857                 sock->link= NULL;
1858         if(totnode==0)
1859                 return;
1860         
1861         for(link= ntree->links.first; link; link= link->next) {
1862                 link->tosock->link= link;
1863         }
1864         
1865         nsort= nodesort= MEM_callocN(totnode*sizeof(void *), "sorted node array");
1866         
1867         /* recursive check */
1868         for(node= ntree->nodes.first; node; node= node->next) {
1869                 if(node->done==0) {
1870                         node->level= node_recurs_check(node, &nsort, 0);
1871                 }
1872         }
1873         
1874         /* re-insert nodes in order, first a paranoia check */
1875         for(a=0; a<totnode; a++) {
1876                 if(nodesort[a]==NULL)
1877                         break;
1878         }
1879         if(a<totnode)
1880                 printf("sort error in node tree");
1881         else {
1882                 ntree->nodes.first= ntree->nodes.last= NULL;
1883                 for(a=0; a<totnode; a++)
1884                         BLI_addtail(&ntree->nodes, nodesort[a]);
1885         }
1886         
1887         MEM_freeN(nodesort);
1888
1889         ntreeSetOutput(ntree);
1890 }
1891
1892
1893 /* Should be callback! */
1894 /* Do not call execs here */
1895 void NodeTagChanged(bNodeTree *ntree, bNode *node)
1896 {
1897         if(ntree->type==NTREE_COMPOSIT) {
1898                 bNodeSocket *sock;
1899
1900                 for(sock= node->outputs.first; sock; sock= sock->next) {
1901                         if(sock->ns.data) {
1902                                 //free_compbuf(sock->ns.data);
1903                                 //sock->ns.data= NULL;
1904                         }
1905                 }
1906                 node->need_exec= 1;
1907         }
1908 }
1909
1910 int NodeTagIDChanged(bNodeTree *ntree, ID *id)
1911 {
1912         int change = FALSE;
1913
1914         if(ELEM(NULL, id, ntree))
1915                 return change;
1916         
1917         if(ntree->type==NTREE_COMPOSIT) {
1918                 bNode *node;
1919                 
1920                 for(node= ntree->nodes.first; node; node= node->next) {
1921                         if(node->id==id) {
1922                                 change= TRUE;
1923                                 NodeTagChanged(ntree, node);
1924                         }
1925                 }
1926         }
1927         
1928         return change;
1929 }
1930
1931
1932
1933 /* ******************* executing ************* */
1934
1935 /* for a given socket, find the actual stack entry */
1936 static bNodeStack *get_socket_stack(bNodeStack *stack, bNodeSocket *sock, bNodeStack **gin)
1937 {
1938         switch (sock->stack_type) {
1939         case SOCK_STACK_LOCAL:
1940                 return stack + sock->stack_index;
1941         case SOCK_STACK_EXTERN:
1942                 return (gin ? gin[sock->stack_index] : NULL);
1943         case SOCK_STACK_CONST:
1944                 return sock->stack_ptr;
1945         }
1946         return NULL;
1947 }
1948
1949 /* see notes at ntreeBeginExecTree */
1950 static void node_get_stack(bNode *node, bNodeStack *stack, bNodeStack **in, bNodeStack **out, bNodeStack **gin)
1951 {
1952         bNodeSocket *sock;
1953         
1954         /* build pointer stack */
1955         if (in) {
1956                 for(sock= node->inputs.first; sock; sock= sock->next) {
1957                         *(in++) = get_socket_stack(stack, sock, gin);
1958                 }
1959         }
1960         
1961         if (out) {
1962                 for(sock= node->outputs.first; sock; sock= sock->next) {
1963                         *(out++) = get_socket_stack(stack, sock, gin);
1964                 }
1965         }
1966 }
1967
1968 static void node_group_execute(bNodeStack *stack, void *data, bNode *gnode, bNodeStack **in)
1969 {
1970         bNode *node;
1971         bNodeTree *ntree= (bNodeTree *)gnode->id;
1972         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
1973         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
1974         
1975         if(ntree==NULL) return;
1976         
1977         stack+= gnode->stack_index;
1978                 
1979         for(node= ntree->nodes.first; node; node= node->next) {
1980                 if(node->typeinfo->execfunc) {
1981                         node_get_stack(node, stack, nsin, nsout, in);
1982                         
1983                         /* for groups, only execute outputs for edited group */
1984                         if(node->typeinfo->nclass==NODE_CLASS_OUTPUT) {
1985                                 if(node->type==CMP_NODE_OUTPUT_FILE || (gnode->flag & NODE_GROUP_EDIT))
1986                                         node->typeinfo->execfunc(data, node, nsin, nsout);
1987                         }
1988                         else
1989                                 node->typeinfo->execfunc(data, node, nsin, nsout);
1990                 }
1991         }
1992         
1993         /* free internal buffers */
1994         if (ntree->type==NTREE_COMPOSIT) {
1995                 bNodeSocket *sock;
1996                 bNodeStack *ns;
1997                 for (sock=ntree->outputs.first; sock; sock=sock->next) {
1998                         /* use the hasoutput flag to tag external sockets */
1999                         if (sock->stack_type==SOCK_STACK_LOCAL) {
2000                                 ns= get_socket_stack(stack, sock, in);
2001                                 ns->hasoutput = 0;
2002                         }
2003                 }
2004                 /* now free all stacks that are not used from outside */
2005                 for (node=ntree->nodes.first; node; node=node->next) {
2006                         for (sock=node->outputs.first; sock; sock=sock->next) {
2007                                 if (sock->stack_type==SOCK_STACK_LOCAL ) {
2008                                         ns= get_socket_stack(stack, sock, in);
2009                                         if (ns->hasoutput!=0 && ns->data) {
2010                                                 free_compbuf(ns->data);
2011                                                 ns->data = NULL;
2012                                                 /* reset the flag */
2013                                                 ns->hasoutput = 1;
2014                                         }
2015                                 }
2016                         }
2017                 }
2018         }
2019 }
2020
2021 static int set_stack_indexes_default(bNode *node, int index)
2022 {
2023         bNodeSocket *sock;
2024         
2025         for (sock=node->inputs.first; sock; sock=sock->next) {
2026                 if (sock->link && sock->link->fromsock) {
2027                         sock->stack_type = sock->link->fromsock->stack_type;
2028                         sock->stack_index = sock->link->fromsock->stack_index;
2029                         sock->stack_ptr = sock->link->fromsock->stack_ptr;
2030                 }
2031                 else {
2032                         sock->stack_type = SOCK_STACK_CONST;
2033                         sock->stack_index = -1;
2034                         sock->stack_ptr = &sock->ns;
2035                 }
2036         }
2037         
2038         for (sock=node->outputs.first; sock; sock=sock->next) {
2039                 sock->stack_type = SOCK_STACK_LOCAL;
2040                 sock->stack_index = index++;
2041                 sock->stack_ptr = NULL;
2042         }
2043         
2044         return index;
2045 }
2046
2047 static int ntree_begin_exec_tree(bNodeTree *ntree);
2048 static int set_stack_indexes_group(bNode *node, int index)
2049 {
2050         bNodeTree *ngroup= (bNodeTree*)node->id;
2051         bNodeSocket *sock;
2052         
2053         if((ngroup->init & NTREE_TYPE_INIT)==0)
2054                 ntreeInitTypes(ngroup);
2055         
2056         node->stack_index = index;
2057         index += ntree_begin_exec_tree(ngroup);
2058         
2059         for (sock=node->inputs.first; sock; sock=sock->next) {
2060                 if (sock->link && sock->link->fromsock) {
2061                         sock->stack_type = sock->link->fromsock->stack_type;
2062                         sock->stack_index = sock->link->fromsock->stack_index;
2063                         sock->stack_ptr = sock->link->fromsock->stack_ptr;
2064                 }
2065                 else {
2066                         sock->stack_type = SOCK_STACK_CONST;
2067                         sock->stack_index = -1;
2068                         sock->stack_ptr = &sock->ns;
2069                 }
2070         }
2071         
2072         /* identify group node outputs from internal group sockets */
2073         for(sock= node->outputs.first; sock; sock= sock->next) {
2074                 if (sock->groupsock) {
2075                         bNodeSocket *insock, *gsock = sock->groupsock;
2076                         switch (gsock->stack_type) {
2077                         case SOCK_STACK_EXTERN:
2078                                 /* extern stack is resolved for this group node instance */
2079                                 insock= find_group_node_input(node, gsock->link->fromsock);
2080                                 sock->stack_type = insock->stack_type;
2081                                 sock->stack_index = insock->stack_index;
2082                                 sock->stack_ptr = insock->stack_ptr;
2083                                 break;
2084                         case SOCK_STACK_LOCAL:
2085                                 sock->stack_type = SOCK_STACK_LOCAL;
2086                                 /* local stack index must be offset by group node instance */
2087                                 sock->stack_index = gsock->stack_index + node->stack_index;
2088                                 sock->stack_ptr = NULL;
2089                                 break;
2090                         case SOCK_STACK_CONST:
2091                                 sock->stack_type = SOCK_STACK_CONST;
2092                                 sock->stack_index = -1;
2093                                 sock->stack_ptr = gsock->stack_ptr;
2094                                 break;
2095                         }
2096                 }
2097                 else {
2098                         sock->stack_type = SOCK_STACK_LOCAL;
2099                         sock->stack_index = index++;
2100                         sock->stack_ptr = NULL;
2101                 }
2102         }
2103         
2104         return index;
2105 }
2106
2107 /* recursively called for groups */
2108 /* we set all trees on own local indices, but put a total counter
2109    in the groups, so each instance of a group has own stack */
2110 static int ntree_begin_exec_tree(bNodeTree *ntree)
2111 {
2112         bNode *node;
2113         bNodeSocket *gsock;
2114         int index= 0, i;
2115         
2116         if((ntree->init & NTREE_TYPE_INIT)==0)
2117                 ntreeInitTypes(ntree);
2118         
2119         /* group inputs are numbered 0..totinputs, so external stack can easily be addressed */
2120         i = 0;
2121         for(gsock=ntree->inputs.first; gsock; gsock = gsock->next) {
2122                 gsock->stack_type = SOCK_STACK_EXTERN;
2123                 gsock->stack_index = i++;
2124                 gsock->stack_ptr = NULL;
2125         }
2126         
2127         /* create indices for stack, check preview */
2128         for(node= ntree->nodes.first; node; node= node->next) {
2129                 /* XXX can this be done by a generic one-for-all function?
2130                  * otherwise should use node-type callback.
2131                  */
2132                 if(node->type==NODE_GROUP)
2133                         index = set_stack_indexes_group(node, index);
2134                 else
2135                         index = set_stack_indexes_default(node, index);
2136         }
2137         
2138         /* group outputs */
2139         for(gsock=ntree->outputs.first; gsock; gsock = gsock->next) {
2140                 if (gsock->link && gsock->link->fromsock) {
2141                         gsock->stack_type = gsock->link->fromsock->stack_type;
2142                         gsock->stack_index = gsock->link->fromsock->stack_index;
2143                         gsock->stack_ptr = gsock->link->fromsock->stack_ptr;
2144                 }
2145                 else {
2146                         gsock->stack_type = SOCK_STACK_CONST;
2147                         gsock->stack_index = -1;
2148                         gsock->stack_ptr = &gsock->ns;
2149                 }
2150         }
2151         
2152         return index;
2153 }
2154
2155 /* copy socket compbufs to stack, initialize usage of curve nodes */
2156 static void composit_begin_exec(bNodeTree *ntree, bNodeStack *stack)
2157 {
2158         bNode *node;
2159         bNodeSocket *sock;
2160         
2161         for(node= ntree->nodes.first; node; node= node->next) {
2162                 
2163                 /* initialize needed for groups */
2164                 node->exec= 0;  
2165                 
2166                 for(sock= node->outputs.first; sock; sock= sock->next) {
2167                         bNodeStack *ns= get_socket_stack(stack, sock, NULL);
2168                         if(ns && sock->ns.data) {
2169                                 ns->data= sock->ns.data;
2170                                 sock->ns.data= NULL;
2171                         }
2172                 }
2173                 
2174                 /* cannot initialize them while using in threads */
2175                 if(ELEM4(node->type, CMP_NODE_TIME, CMP_NODE_CURVE_VEC, CMP_NODE_CURVE_RGB, CMP_NODE_HUECORRECT)) {
2176                         curvemapping_initialize(node->storage);
2177                         if(node->type==CMP_NODE_CURVE_RGB)
2178                                 curvemapping_premultiply(node->storage, 0);
2179                 }
2180                 if(node->type==NODE_GROUP)
2181                         composit_begin_exec((bNodeTree *)node->id, stack + node->stack_index);
2182
2183         }
2184 }
2185
2186 /* copy stack compbufs to sockets */
2187 static void composit_end_exec(bNodeTree *ntree, bNodeStack *stack)
2188 {
2189         bNode *node;
2190         bNodeStack *ns;
2191
2192         for(node= ntree->nodes.first; node; node= node->next) {
2193                 bNodeSocket *sock;
2194                 
2195                 for(sock= node->outputs.first; sock; sock= sock->next) {
2196                         ns = get_socket_stack(stack, sock, NULL);
2197                         if(ns && ns->data) {
2198                                 sock->ns.data= ns->data;
2199                                 ns->data= NULL;
2200                         }
2201                 }
2202                 
2203                 if(node->type==CMP_NODE_CURVE_RGB)
2204                         curvemapping_premultiply(node->storage, 1);
2205                 
2206                 if(node->type==NODE_GROUP)
2207                         composit_end_exec((bNodeTree *)node->id, stack + node->stack_index);
2208
2209                 node->need_exec= 0;
2210         }
2211 }
2212
2213 static void group_tag_used_outputs(bNode *gnode, bNodeStack *stack, bNodeStack **gin)
2214 {
2215         bNodeTree *ntree= (bNodeTree *)gnode->id;
2216         bNode *node;
2217         bNodeSocket *sock;
2218         
2219         stack+= gnode->stack_index;
2220         
2221         for(node= ntree->nodes.first; node; node= node->next) {
2222                 if(node->typeinfo->execfunc) {
2223                         for(sock= node->inputs.first; sock; sock= sock->next) {
2224                                 bNodeStack *ns = get_socket_stack(stack, sock, gin);
2225                                 ns->hasoutput= 1;
2226                         }
2227                 }
2228                 
2229                 /* set stack types (for local stack entries) */
2230                 for(sock= node->outputs.first; sock; sock= sock->next) {
2231                         bNodeStack *ns = get_socket_stack(stack, sock, NULL);
2232                         if (ns)
2233                                 ns->sockettype = sock->type;
2234                 }
2235         }
2236 }
2237
2238 /* notes below are ancient! (ton) */
2239 /* stack indices make sure all nodes only write in allocated data, for making it thread safe */
2240 /* only root tree gets the stack, to enable instances to have own stack entries */
2241 /* per tree (and per group) unique indices are created */
2242 /* the index_ext we need to be able to map from groups to the group-node own stack */
2243
2244 typedef struct bNodeThreadStack {
2245         struct bNodeThreadStack *next, *prev;
2246         bNodeStack *stack;
2247         int used;
2248 } bNodeThreadStack;
2249
2250 static bNodeThreadStack *ntreeGetThreadStack(bNodeTree *ntree, int thread)
2251 {
2252         ListBase *lb= &ntree->threadstack[thread];
2253         bNodeThreadStack *nts;
2254         
2255         for(nts=lb->first; nts; nts=nts->next) {
2256                 if(!nts->used) {
2257                         nts->used= 1;
2258                         return nts;
2259                 }
2260         }
2261         nts= MEM_callocN(sizeof(bNodeThreadStack), "bNodeThreadStack");
2262         nts->stack= MEM_dupallocN(ntree->stack);
2263         nts->used= 1;
2264         BLI_addtail(lb, nts);
2265
2266         return nts;
2267 }
2268
2269 static void ntreeReleaseThreadStack(bNodeThreadStack *nts)
2270 {
2271         nts->used= 0;
2272 }
2273
2274 /* free texture delegates */
2275 static void tex_end_exec(bNodeTree *ntree)
2276 {
2277         bNodeThreadStack *nts;
2278         bNodeStack *ns;
2279         int th, a;
2280         
2281         if(ntree->threadstack)
2282                 for(th=0; th<BLENDER_MAX_THREADS; th++)
2283                         for(nts=ntree->threadstack[th].first; nts; nts=nts->next)
2284                                 for(ns= nts->stack, a=0; a<ntree->stacksize; a++, ns++)
2285                                         if(ns->data)
2286                                                 MEM_freeN(ns->data);
2287                                                 
2288 }
2289
2290 void ntreeBeginExecTree(bNodeTree *ntree)
2291 {
2292         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2293         
2294         /* let's make it sure */
2295         if(ntree->init & NTREE_EXEC_INIT)
2296                 return;
2297         
2298         /* allocate the thread stack listbase array */
2299         if(ntree->type!=NTREE_COMPOSIT)
2300                 ntree->threadstack= MEM_callocN(BLENDER_MAX_THREADS*sizeof(ListBase), "thread stack array");
2301
2302         /* goes recursive over all groups */
2303         ntree->stacksize= ntree_begin_exec_tree(ntree);
2304
2305         if(ntree->stacksize) {
2306                 bNode *node;
2307                 bNodeStack *ns;
2308                 int a;
2309                 
2310                 /* allocate the base stack */
2311                 ns=ntree->stack= MEM_callocN(ntree->stacksize*sizeof(bNodeStack), "node stack");
2312                 
2313                 /* tag inputs, the get_stack() gives own socket stackdata if not in use */
2314                 for(a=0; a<ntree->stacksize; a++, ns++) ns->hasinput= 1;
2315                 
2316                 /* tag used outputs, so we know when we can skip operations */
2317                 for(node= ntree->nodes.first; node; node= node->next) {
2318                         bNodeSocket *sock;
2319                         
2320                         /* composite has own need_exec tag handling */
2321                         if(ntree->type!=NTREE_COMPOSIT)
2322                                 node->need_exec= 1;
2323
2324                         for(sock= node->inputs.first; sock; sock= sock->next) {
2325                                 ns = get_socket_stack(ntree->stack, sock, NULL);
2326                                 if (ns) {
2327                                         ns->hasoutput = 1;
2328                                         
2329                                         /* sock type is needed to detect rgba or value or vector types */
2330                                         if(sock->link)
2331                                                 ns->sockettype= sock->link->fromsock->type;
2332                                         else
2333                                                 sock->ns.sockettype= sock->type;
2334                                 }
2335                                 
2336                                 if(sock->link) {
2337                                         bNodeLink *link= sock->link;
2338                                         /* this is the test for a cyclic case */
2339                                         if(link->fromnode && link->tonode) {
2340                                                 if(link->fromnode->level >= link->tonode->level && link->tonode->level!=0xFFF);
2341                                                 else {
2342                                                         node->need_exec= 0;
2343                                                 }
2344                                         }
2345                                 }
2346                         }
2347                         
2348                         /* set stack types (for local stack entries) */
2349                         for(sock= node->outputs.first; sock; sock= sock->next) {
2350                                 ns = get_socket_stack(ntree->stack, sock, NULL);
2351                                 if (ns)
2352                                         ns->sockettype = sock->type;
2353                         }
2354                         
2355                         if(node->type==NODE_GROUP && node->id) {
2356                                 node_get_stack(node, ntree->stack, nsin, NULL, NULL);
2357                                 group_tag_used_outputs(node, ntree->stack, nsin);
2358                         }
2359                 }
2360                 
2361                 if(ntree->type==NTREE_COMPOSIT)
2362                         composit_begin_exec(ntree, ntree->stack);
2363         }
2364         
2365         ntree->init |= NTREE_EXEC_INIT;
2366 }
2367
2368 void ntreeEndExecTree(bNodeTree *ntree)
2369 {
2370         bNodeStack *ns;
2371         
2372         if(ntree->init & NTREE_EXEC_INIT) {
2373                 bNodeThreadStack *nts;
2374                 int a;
2375                 
2376                 /* another callback candidate! */
2377                 if(ntree->type==NTREE_COMPOSIT) {
2378                         composit_end_exec(ntree, ntree->stack);
2379                         
2380                         for(ns= ntree->stack, a=0; a<ntree->stacksize; a++, ns++) {
2381                                 if(ns->data) {
2382                                         printf("freed leftover buffer from stack\n");
2383                                         free_compbuf(ns->data);
2384                                         ns->data= NULL;
2385                                 }
2386                         }
2387                 }
2388                 else if(ntree->type==NTREE_TEXTURE)
2389                         tex_end_exec(ntree);
2390                 
2391                 if(ntree->stack) {
2392                         MEM_freeN(ntree->stack);
2393                         ntree->stack= NULL;
2394                 }
2395
2396                 if(ntree->threadstack) {
2397                         for(a=0; a<BLENDER_MAX_THREADS; a++) {
2398                                 for(nts=ntree->threadstack[a].first; nts; nts=nts->next)
2399                                         if (nts->stack) MEM_freeN(nts->stack);
2400                                 BLI_freelistN(&ntree->threadstack[a]);
2401                         }
2402
2403                         MEM_freeN(ntree->threadstack);
2404                         ntree->threadstack= NULL;
2405                 }
2406
2407                 ntree->init &= ~NTREE_EXEC_INIT;
2408         }
2409 }
2410
2411 /* nodes are presorted, so exec is in order of list */
2412 void ntreeExecTree(bNodeTree *ntree, void *callerdata, int thread)
2413 {
2414         bNode *node;
2415         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2416         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
2417         bNodeStack *stack;
2418         bNodeThreadStack *nts = NULL;
2419         
2420         /* only when initialized */
2421         if((ntree->init & NTREE_EXEC_INIT)==0)
2422                 ntreeBeginExecTree(ntree);
2423         
2424         /* composite does 1 node per thread, so no multiple stacks needed */
2425         if(ntree->type==NTREE_COMPOSIT) {
2426                 stack= ntree->stack;
2427         }
2428         else {
2429                 nts= ntreeGetThreadStack(ntree, thread);
2430                 stack= nts->stack;
2431         }
2432         
2433         for(node= ntree->nodes.first; node; node= node->next) {
2434                 if(node->need_exec) {
2435                         if(node->typeinfo->execfunc) {
2436                                 node_get_stack(node, stack, nsin, nsout, NULL);
2437                                 node->typeinfo->execfunc(callerdata, node, nsin, nsout);
2438                         }
2439                         else if(node->type==NODE_GROUP && node->id) {
2440                                 node_get_stack(node, stack, nsin, NULL, NULL);
2441                                 node_group_execute(stack, callerdata, node, nsin);
2442                         }
2443                 }
2444         }
2445
2446         if(nts)
2447                 ntreeReleaseThreadStack(nts);
2448 }
2449
2450
2451 /* ***************************** threaded version for execute composite nodes ************* */
2452 /* these are nodes without input, only giving values */
2453 /* or nodes with only value inputs */
2454 static int node_only_value(bNode *node)
2455 {
2456         bNodeSocket *sock;
2457         
2458         if(ELEM3(node->type, CMP_NODE_TIME, CMP_NODE_VALUE, CMP_NODE_RGB))
2459                 return 1;
2460         
2461         /* doing this for all node types goes wrong. memory free errors */
2462         if(node->inputs.first && node->type==CMP_NODE_MAP_VALUE) {
2463                 int retval= 1;
2464                 for(sock= node->inputs.first; sock; sock= sock->next) {
2465                         if(sock->link)
2466                                 retval &= node_only_value(sock->link->fromnode);
2467                 }
2468                 return retval;
2469         }
2470         return 0;
2471 }
2472
2473
2474 /* not changing info, for thread callback */
2475 typedef struct ThreadData {
2476         bNodeStack *stack;
2477         RenderData *rd;
2478 } ThreadData;
2479
2480 static void *exec_composite_node(void *node_v)
2481 {
2482         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2483         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
2484         bNode *node= node_v;
2485         ThreadData *thd= (ThreadData *)node->threaddata;
2486         
2487         node_get_stack(node, thd->stack, nsin, nsout, NULL);
2488         
2489         if((node->flag & NODE_MUTED) && (!node_only_value(node))) {
2490                 /* viewers we execute, for feedback to user */
2491                 if(ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER)) 
2492                         node->typeinfo->execfunc(thd->rd, node, nsin, nsout);
2493                 else
2494                         node_compo_pass_on(node, nsin, nsout);
2495         }
2496         else if(node->typeinfo->execfunc) {
2497                 node->typeinfo->execfunc(thd->rd, node, nsin, nsout);
2498         }
2499         else if(node->type==NODE_GROUP && node->id) {
2500                 node_group_execute(thd->stack, thd->rd, node, nsin); 
2501         }
2502         
2503         node->exec |= NODE_READY;
2504         return NULL;
2505 }
2506
2507 /* return total of executable nodes, for timecursor */
2508 /* only compositor uses it */
2509 static int setExecutableNodes(bNodeTree *ntree, ThreadData *thd)
2510 {
2511         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2512         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
2513         bNode *node;
2514         bNodeSocket *sock;
2515         int totnode= 0, group_edit= 0;
2516         
2517         /* note; do not add a dependency sort here, the stack was created already */
2518         
2519         /* if we are in group edit, viewer nodes get skipped when group has viewer */
2520         for(node= ntree->nodes.first; node; node= node->next)
2521                 if(node->type==NODE_GROUP && (node->flag & NODE_GROUP_EDIT))
2522                         if(ntreeHasType((bNodeTree *)node->id, CMP_NODE_VIEWER))
2523                                 group_edit= 1;
2524         
2525         for(node= ntree->nodes.first; node; node= node->next) {
2526                 int a;
2527                 
2528                 node_get_stack(node, thd->stack, nsin, nsout, NULL);
2529                 
2530                 /* test the outputs */
2531                 /* skip value-only nodes (should be in type!) */
2532                 if(!node_only_value(node)) {
2533                         for(a=0, sock= node->outputs.first; sock; sock= sock->next, a++) {
2534                                 if(nsout[a]->data==NULL && nsout[a]->hasoutput) {
2535                                         node->need_exec= 1;
2536                                         break;
2537                                 }
2538                         }
2539                 }
2540                 
2541                 /* test the inputs */
2542                 for(a=0, sock= node->inputs.first; sock; sock= sock->next, a++) {
2543                         /* skip viewer nodes in bg render or group edit */
2544                         if( ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER) && (G.background || group_edit))
2545                                 node->need_exec= 0;
2546                         /* is sock in use? */
2547                         else if(sock->link) {
2548                                 bNodeLink *link= sock->link;
2549                                 
2550                                 /* this is the test for a cyclic case */
2551                                 if(link->fromnode==NULL || link->tonode==NULL);
2552                                 else if(link->fromnode->level >= link->tonode->level && link->tonode->level!=0xFFF) {
2553                                         if(link->fromnode->need_exec) {
2554                                                 node->need_exec= 1;
2555                                                 break;
2556                                         }
2557                                 }
2558                                 else {
2559                                         node->need_exec= 0;
2560                                         printf("Node %s skipped, cyclic dependency\n", node->name);
2561                                 }
2562                         }
2563                 }
2564                 
2565                 if(node->need_exec) {
2566                         
2567                         /* free output buffers */
2568                         for(a=0, sock= node->outputs.first; sock; sock= sock->next, a++) {
2569                                 if(nsout[a]->data) {
2570                                         free_compbuf(nsout[a]->data);
2571                                         nsout[a]->data= NULL;
2572                                 }
2573                         }
2574                         totnode++;
2575                         /* printf("node needs exec %s\n", node->name); */
2576                         
2577                         /* tag for getExecutableNode() */
2578                         node->exec= 0;
2579                 }
2580                 else {
2581                         /* tag for getExecutableNode() */
2582                         node->exec= NODE_READY|NODE_FINISHED|NODE_SKIPPED;
2583                         
2584                 }
2585         }
2586         
2587         /* last step: set the stack values for only-value nodes */
2588         /* just does all now, compared to a full buffer exec this is nothing */
2589         if(totnode) {
2590                 for(node= ntree->nodes.first; node; node= node->next) {
2591                         if(node->need_exec==0 && node_only_value(node)) {
2592                                 if(node->typeinfo->execfunc) {
2593                                         node_get_stack(node, thd->stack, nsin, nsout, NULL);
2594                                         node->typeinfo->execfunc(thd->rd, node, nsin, nsout);
2595                                 }
2596                         }
2597                 }
2598         }
2599         
2600         return totnode;
2601 }
2602
2603 /* while executing tree, free buffers from nodes that are not needed anymore */
2604 static void freeExecutableNode(bNodeTree *ntree)
2605 {
2606         /* node outputs can be freed when:
2607         - not a render result or image node
2608         - when node outputs go to nodes all being set NODE_FINISHED
2609         */
2610         bNode *node;
2611         bNodeSocket *sock;
2612         
2613         /* set exec flag for finished nodes that might need freed */
2614         for(node= ntree->nodes.first; node; node= node->next) {
2615                 if(node->type!=CMP_NODE_R_LAYERS)
2616                         if(node->exec & NODE_FINISHED)
2617                                 node->exec |= NODE_FREEBUFS;
2618         }
2619         /* clear this flag for input links that are not done yet */
2620         for(node= ntree->nodes.first; node; node= node->next) {
2621                 if((node->exec & NODE_FINISHED)==0) {
2622                         for(sock= node->inputs.first; sock; sock= sock->next)
2623                                 if(sock->link)
2624                                         sock->link->fromnode->exec &= ~NODE_FREEBUFS;
2625                 }
2626         }
2627         /* now we can free buffers */
2628         for(node= ntree->nodes.first; node; node= node->next) {
2629                 if(node->exec & NODE_FREEBUFS) {
2630                         for(sock= node->outputs.first; sock; sock= sock->next) {
2631                                 bNodeStack *ns= get_socket_stack(ntree->stack, sock, NULL);
2632                                 if(ns && ns->data) {
2633                                         free_compbuf(ns->data);
2634                                         ns->data= NULL;
2635                                         // printf("freed buf node %s \n", node->name);
2636                                 }
2637                         }
2638                 }
2639         }
2640 }
2641
2642 static bNode *getExecutableNode(bNodeTree *ntree)
2643 {
2644         bNode *node;
2645         bNodeSocket *sock;
2646         
2647         for(node= ntree->nodes.first; node; node= node->next) {
2648                 if(node->exec==0) {
2649                         
2650                         /* input sockets should be ready */
2651                         for(sock= node->inputs.first; sock; sock= sock->next) {
2652                                 if(sock->link && sock->link->fromnode)
2653                                         if((sock->link->fromnode->exec & NODE_READY)==0)
2654                                                 break;
2655                         }
2656                         if(sock==NULL)
2657                                 return node;
2658                 }
2659         }
2660         return NULL;
2661 }
2662
2663 /* check if texture nodes need exec or end */
2664 static  void ntree_composite_texnode(bNodeTree *ntree, int init)
2665 {
2666         bNode *node;
2667         
2668         for(node= ntree->nodes.first; node; node= node->next) {
2669                 if(node->type==CMP_NODE_TEXTURE && node->id) {
2670                         Tex *tex= (Tex *)node->id;
2671                         if(tex->nodetree && tex->use_nodes) {
2672                                 /* has internal flag to detect it only does it once */
2673                                 if(init)
2674                                         ntreeBeginExecTree(tex->nodetree); 
2675                                 else
2676                                         ntreeEndExecTree(tex->nodetree);
2677                         }
2678                 }
2679         }
2680
2681 }
2682
2683 /* optimized tree execute test for compositing */
2684 void ntreeCompositExecTree(bNodeTree *ntree, RenderData *rd, int do_preview)
2685 {
2686         bNode *node;
2687         ListBase threads;
2688         ThreadData thdata;
2689         int totnode, curnode, rendering= 1;
2690         
2691         if(ntree==NULL) return;
2692         
2693         if(do_preview)
2694                 ntreeInitPreview(ntree, 0, 0);
2695         
2696         ntreeBeginExecTree(ntree);
2697         ntree_composite_texnode(ntree, 1);
2698         
2699         /* prevent unlucky accidents */
2700         if(G.background)
2701                 rd->scemode &= ~R_COMP_CROP;
2702         
2703         /* setup callerdata for thread callback */
2704         thdata.rd= rd;
2705         thdata.stack= ntree->stack;
2706         
2707         /* fixed seed, for example noise texture */
2708         BLI_srandom(rd->cfra);
2709
2710         /* ensures only a single output node is enabled */
2711         ntreeSetOutput(ntree);
2712
2713         /* sets need_exec tags in nodes */
2714         curnode = totnode= setExecutableNodes(ntree, &thdata);
2715
2716         BLI_init_threads(&threads, exec_composite_node, rd->threads);
2717         
2718         while(rendering) {
2719                 
2720                 if(BLI_available_threads(&threads)) {
2721                         node= getExecutableNode(ntree);
2722                         if(node) {
2723                                 if(ntree->progress && totnode)
2724                                         ntree->progress(ntree->prh, (1.0 - curnode/(float)totnode));
2725                                 if(ntree->stats_draw) {
2726                                         char str[64];
2727                                         sprintf(str, "Compositing %d %s", curnode, node->name);
2728                                         ntree->stats_draw(ntree->sdh, str);
2729                                 }
2730                                 curnode--;
2731                                 
2732                                 node->threaddata = &thdata;
2733                                 node->exec= NODE_PROCESSING;
2734                                 BLI_insert_thread(&threads, node);
2735                         }
2736                         else
2737                                 PIL_sleep_ms(50);
2738                 }
2739                 else
2740                         PIL_sleep_ms(50);
2741                 
2742                 rendering= 0;
2743                 /* test for ESC */
2744                 if(ntree->test_break && ntree->test_break(ntree->tbh)) {
2745                         for(node= ntree->nodes.first; node; node= node->next)
2746                                 node->exec |= NODE_READY;
2747                 }
2748                 
2749                 /* check for ready ones, and if we need to continue */
2750                 for(node= ntree->nodes.first; node; node= node->next) {
2751                         if(node->exec & NODE_READY) {
2752                                 if((node->exec & NODE_FINISHED)==0) {
2753                                         BLI_remove_thread(&threads, node); /* this waits for running thread to finish btw */
2754                                         node->exec |= NODE_FINISHED;
2755                                         
2756                                         /* freeing unused buffers */
2757                                         if(rd->scemode & R_COMP_FREE)
2758                                                 freeExecutableNode(ntree);
2759                                 }
2760                         }
2761                         else rendering= 1;
2762                 }
2763         }
2764         
2765         BLI_end_threads(&threads);
2766         
2767         ntreeEndExecTree(ntree);
2768 }
2769
2770
2771 /* ********** copy composite tree entirely, to allow threaded exec ******************* */
2772 /* ***************** do NOT execute this in a thread!               ****************** */
2773
2774 /* returns localized composite tree for execution in threads */
2775 /* local tree then owns all compbufs */
2776 bNodeTree *ntreeLocalize(bNodeTree *ntree)
2777 {
2778         bNodeTree *ltree;
2779         bNode *node;
2780         bNodeSocket *sock;
2781         
2782         bAction *action_backup= NULL, *tmpact_backup= NULL;
2783         
2784         /* Workaround for copying an action on each render!
2785          * set action to NULL so animdata actions dont get copied */
2786         AnimData *adt= BKE_animdata_from_id(&ntree->id);
2787
2788         if(adt) {
2789                 action_backup= adt->action;
2790                 tmpact_backup= adt->tmpact;
2791
2792                 adt->action= NULL;
2793                 adt->tmpact= NULL;
2794         }
2795
2796         /* node copy func */
2797         ltree= ntreeCopyTree(ntree);
2798
2799         if(adt) {
2800                 AnimData *ladt= BKE_animdata_from_id(&ltree->id);
2801
2802                 adt->action= ladt->action= action_backup;
2803                 adt->tmpact= ladt->tmpact= tmpact_backup;
2804
2805                 if(action_backup) action_backup->id.us++;
2806                 if(tmpact_backup) tmpact_backup->id.us++;
2807                 
2808         }
2809         /* end animdata uglyness */
2810
2811         /* ensures only a single output node is enabled */
2812         ntreeSetOutput(ntree);
2813
2814         for(node= ntree->nodes.first; node; node= node->next) {
2815                 
2816                 /* store new_node pointer to original */
2817                 node->new_node->new_node= node;
2818                 /* ensure new user input gets handled ok */
2819                 node->need_exec= 0;
2820                 
2821                 if(ntree->type==NTREE_COMPOSIT) {
2822                         /* move over the compbufs */
2823                         /* right after ntreeCopyTree() oldsock pointers are valid */
2824                         
2825                         if(ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER)) {
2826                                 if(node->id) {
2827                                         if(node->flag & NODE_DO_OUTPUT)
2828                                                 node->new_node->id= (ID *)copy_image((Image *)node->id);
2829                                         else
2830                                                 node->new_node->id= NULL;
2831                                 }
2832                         }
2833                         
2834                         for(sock= node->outputs.first; sock; sock= sock->next) {
2835                                 
2836                                 sock->new_sock->ns.data= sock->ns.data;
2837                                 compbuf_set_node(sock->new_sock->ns.data, node->new_node);
2838                                 
2839                                 sock->ns.data= NULL;
2840                                 sock->new_sock->new_sock= sock;
2841                         }
2842                 }
2843         }
2844         
2845         return ltree;
2846 }
2847
2848 static int node_exists(bNodeTree *ntree, bNode *testnode)
2849 {
2850         bNode *node= ntree->nodes.first;
2851         for(; node; node= node->next)
2852                 if(node==testnode)
2853                         return 1;
2854         return 0;
2855 }
2856
2857 static int outsocket_exists(bNode *node, bNodeSocket *testsock)
2858 {
2859         bNodeSocket *sock= node->outputs.first;
2860         for(; sock; sock= sock->next)
2861                 if(sock==testsock)
2862                         return 1;
2863         return 0;
2864 }
2865
2866
2867 /* sync local composite with real tree */
2868 /* local composite is supposed to be running, be careful moving previews! */
2869 /* is called by jobs manager, outside threads, so it doesnt happen during draw */
2870 void ntreeLocalSync(bNodeTree *localtree, bNodeTree *ntree)
2871 {
2872         bNode *lnode;
2873         
2874         if(ntree->type==NTREE_COMPOSIT) {
2875                 /* move over the compbufs and previews */
2876                 for(lnode= localtree->nodes.first; lnode; lnode= lnode->next) {
2877                         if( (lnode->exec & NODE_READY) && !(lnode->exec & NODE_SKIPPED) ) {
2878                                 if(node_exists(ntree, lnode->new_node)) {
2879                                         
2880                                         if(lnode->preview && lnode->preview->rect) {
2881                                                 node_free_preview(lnode->new_node);
2882                                                 lnode->new_node->preview= lnode->preview;
2883                                                 lnode->preview= NULL;
2884                                         }
2885                                 }
2886                         }
2887                 }
2888         }
2889         else if(ntree->type==NTREE_SHADER) {
2890                 /* copy over contents of previews */
2891                 for(lnode= localtree->nodes.first; lnode; lnode= lnode->next) {
2892                         if(node_exists(ntree, lnode->new_node)) {
2893                                 bNode *node= lnode->new_node;
2894                                 
2895                                 if(node->preview && node->preview->rect) {
2896                                         if(lnode->preview && lnode->preview->rect) {
2897                                                 int xsize= node->preview->xsize;
2898                                                 int ysize= node->preview->ysize;
2899                                                 memcpy(node->preview->rect, lnode->preview->rect, 4*xsize + xsize*ysize*sizeof(char)*4);
2900                                         }
2901                                 }
2902                         }
2903                 }
2904         }
2905 }
2906
2907 /* merge local tree results back, and free local tree */
2908 /* we have to assume the editor already changed completely */
2909 void ntreeLocalMerge(bNodeTree *localtree, bNodeTree *ntree)
2910 {
2911         bNode *lnode;
2912         bNodeSocket *lsock;
2913         
2914         /* move over the compbufs and previews */
2915         for(lnode= localtree->nodes.first; lnode; lnode= lnode->next) {
2916                 if(node_exists(ntree, lnode->new_node)) {
2917                         
2918                         if(lnode->preview && lnode->preview->rect) {
2919                                 node_free_preview(lnode->new_node);
2920                                 lnode->new_node->preview= lnode->preview;
2921                                 lnode->preview= NULL;
2922                         }
2923                         
2924                         if(ELEM(lnode->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER)) {
2925                                 if(lnode->id && (lnode->flag & NODE_DO_OUTPUT)) {
2926                                         /* image_merge does sanity check for pointers */
2927                                         BKE_image_merge((Image *)lnode->new_node->id, (Image *)lnode->id);
2928                                 }
2929                         }
2930                         
2931                         for(lsock= lnode->outputs.first; lsock; lsock= lsock->next) {
2932                                 if(outsocket_exists(lnode->new_node, lsock->new_sock)) {
2933                                         lsock->new_sock->ns.data= lsock->ns.data;
2934                                         compbuf_set_node(lsock->new_sock->ns.data, lnode->new_node);
2935                                         lsock->ns.data= NULL;
2936                                         lsock->new_sock= NULL;
2937                                 }
2938                         }
2939                 }
2940         }
2941         ntreeFreeTree(localtree);
2942         MEM_freeN(localtree);
2943 }
2944
2945 /* *********************************************** */
2946
2947 /* GPU material from shader nodes */
2948
2949 static void gpu_from_node_stack(ListBase *sockets, bNodeStack **ns, GPUNodeStack *gs)
2950 {
2951         bNodeSocket *sock;
2952         int i;
2953
2954         for (sock=sockets->first, i=0; sock; sock=sock->next, i++) {
2955                 memset(&gs[i], 0, sizeof(gs[i]));
2956
2957                 QUATCOPY(gs[i].vec, ns[i]->vec);
2958                 gs[i].link= ns[i]->data;
2959
2960                 if (sock->type == SOCK_VALUE)
2961                         gs[i].type= GPU_FLOAT;
2962                 else if (sock->type == SOCK_VECTOR)
2963                         gs[i].type= GPU_VEC3;
2964                 else if (sock->type == SOCK_RGBA)
2965                         gs[i].type= GPU_VEC4;
2966                 else
2967                         gs[i].type= GPU_NONE;
2968
2969                 gs[i].name = "";
2970                 gs[i].hasinput= ns[i]->hasinput && ns[i]->data;
2971                 gs[i].hasoutput= ns[i]->hasoutput && ns[i]->data;
2972                 gs[i].sockettype= ns[i]->sockettype;
2973         }
2974
2975         gs[i].type= GPU_NONE;
2976 }
2977
2978 static void data_from_gpu_stack(ListBase *sockets, bNodeStack **ns, GPUNodeStack *gs)
2979 {
2980         bNodeSocket *sock;
2981         int i;
2982
2983         for (sock=sockets->first, i=0; sock; sock=sock->next, i++) {
2984                 ns[i]->data= gs[i].link;
2985                 ns[i]->sockettype= gs[i].sockettype;
2986         }
2987 }
2988
2989 static void gpu_node_group_execute(bNodeStack *stack, GPUMaterial *mat, bNode *gnode, bNodeStack **in)
2990 {
2991         bNode *node;
2992         bNodeTree *ntree= (bNodeTree *)gnode->id;
2993         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2994         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
2995         GPUNodeStack gpuin[MAX_SOCKET+1], gpuout[MAX_SOCKET+1];
2996         int doit = 0;
2997         
2998         if(ntree==NULL) return;
2999         
3000         stack+= gnode->stack_index;
3001                 
3002         for(node= ntree->nodes.first; node; node= node->next) {
3003                 if(node->typeinfo->gpufunc) {
3004                         node_get_stack(node, stack, nsin, nsout, in);
3005
3006                         doit = 0;
3007                         
3008                         /* for groups, only execute outputs for edited group */
3009                         if(node->typeinfo->nclass==NODE_CLASS_OUTPUT) {
3010                                 if(gnode->flag & NODE_GROUP_EDIT)
3011                                         if(node->flag & NODE_DO_OUTPUT)
3012                                                 doit = 1;
3013                         }
3014                         else
3015                                 doit = 1;
3016
3017                         if(doit)  {
3018                                 gpu_from_node_stack(&node->inputs, nsin, gpuin);
3019                                 gpu_from_node_stack(&node->outputs, nsout, gpuout);
3020                                 if(node->typeinfo->gpufunc(mat, node, gpuin, gpuout))
3021                                         data_from_gpu_stack(&node->outputs, nsout, gpuout);
3022                         }
3023                 }
3024         }
3025 }
3026
3027 void ntreeGPUMaterialNodes(bNodeTree *ntree, GPUMaterial *mat)
3028 {
3029         bNode *node;
3030         bNodeStack *stack;
3031         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
3032         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
3033         GPUNodeStack gpuin[MAX_SOCKET+1], gpuout[MAX_SOCKET+1];
3034
3035         if((ntree->init & NTREE_EXEC_INIT)==0)
3036                 ntreeBeginExecTree(ntree);
3037
3038         stack= ntree->stack;
3039
3040         for(node= ntree->nodes.first; node; node= node->next) {
3041                 if(node->typeinfo->gpufunc) {
3042                         node_get_stack(node, stack, nsin, nsout, NULL);
3043                         gpu_from_node_stack(&node->inputs, nsin, gpuin);
3044                         gpu_from_node_stack(&node->outputs, nsout, gpuout);
3045                         if(node->typeinfo->gpufunc(mat, node, gpuin, gpuout))
3046                                 data_from_gpu_stack(&node->outputs, nsout, gpuout);
3047                 }
3048                 else if(node->type==NODE_GROUP && node->id) {
3049                         node_get_stack(node, stack, nsin, nsout, NULL);
3050                         gpu_node_group_execute(stack, mat, node, nsin);
3051                 }
3052         }
3053
3054         ntreeEndExecTree(ntree);
3055 }
3056
3057 /* **************** call to switch lamploop for material node ************ */
3058
3059 void (*node_shader_lamp_loop)(struct ShadeInput *, struct ShadeResult *);
3060
3061 void set_node_shader_lamp_loop(void (*lamp_loop_func)(ShadeInput *, ShadeResult *))
3062 {
3063         node_shader_lamp_loop= lamp_loop_func;
3064 }
3065
3066 /* clumsy checking... should do dynamic outputs once */
3067 static void force_hidden_passes(bNode *node, int passflag)
3068 {
3069         bNodeSocket *sock;
3070         
3071         for(sock= node->outputs.first; sock; sock= sock->next)
3072                 sock->flag &= ~SOCK_UNAVAIL;
3073         
3074         sock= BLI_findlink(&node->outputs, RRES_OUT_Z);
3075         if(!(passflag & SCE_PASS_Z)) sock->flag |= SOCK_UNAVAIL;
3076         sock= BLI_findlink(&node->outputs, RRES_OUT_NORMAL);
3077         if(!(passflag & SCE_PASS_NORMAL)) sock->flag |= SOCK_UNAVAIL;
3078         sock= BLI_findlink(&node->outputs, RRES_OUT_VEC);
3079         if(!(passflag & SCE_PASS_VECTOR)) sock->flag |= SOCK_UNAVAIL;
3080         sock= BLI_findlink(&node->outputs, RRES_OUT_UV);
3081         if(!(passflag & SCE_PASS_UV)) sock->flag |= SOCK_UNAVAIL;
3082         sock= BLI_findlink(&node->outputs, RRES_OUT_RGBA);
3083         if(!(passflag & SCE_PASS_RGBA)) sock->flag |= SOCK_UNAVAIL;
3084         sock= BLI_findlink(&node->outputs, RRES_OUT_DIFF);
3085         if(!(passflag & SCE_PASS_DIFFUSE)) sock->flag |= SOCK_UNAVAIL;
3086