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