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