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