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