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