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