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