fix for memory leak: node animation data wasnt being free'd
[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 #ifndef DISABLE_PYTHON
31 #include <Python.h>
32 #endif
33
34 #include <stdlib.h>
35 #include <stddef.h>
36 #include <string.h>
37
38 #include "DNA_anim_types.h"
39 #include "DNA_ID.h"
40 #include "DNA_image_types.h"
41 #include "DNA_node_types.h"
42 #include "DNA_material_types.h"
43 #include "DNA_texture_types.h"
44 #include "DNA_text_types.h"
45 #include "DNA_scene_types.h"
46
47 #include "RNA_access.h"
48
49 #include "BKE_blender.h"
50 #include "BKE_colortools.h"
51 #include "BKE_fcurve.h"
52 #include "BKE_global.h"
53 #include "BKE_image.h"
54 #include "BKE_library.h"
55 #include "BKE_main.h"
56 #include "BKE_node.h"
57 #include "BKE_texture.h"
58 #include "BKE_text.h"
59 #include "BKE_utildefines.h"
60 #include "BKE_animsys.h" /* BKE_free_animdata only */
61
62 #include "BLI_math.h"
63 #include "BLI_blenlib.h"
64 #include "BLI_rand.h"
65 #include "BLI_threads.h"
66
67 #include "PIL_time.h"
68
69 #include "MEM_guardedalloc.h"
70 #include "IMB_imbuf.h"
71
72 #include "RE_pipeline.h"
73 #include "RE_shader_ext.h"              /* <- TexResult */
74 #include "RE_render_ext.h"              /* <- ibuf_sample() */
75
76 #include "CMP_node.h"
77 #include "intern/CMP_util.h"    /* stupid include path... */
78
79 #include "SHD_node.h"
80 #include "TEX_node.h"
81 #include "intern/TEX_util.h"
82
83 #include "GPU_extensions.h"
84 #include "GPU_material.h"
85
86 static ListBase empty_list = {NULL, NULL};
87 ListBase node_all_composit = {NULL, NULL};
88 ListBase node_all_shaders = {NULL, NULL};
89 ListBase node_all_textures = {NULL, NULL};
90
91 /* ************** Type stuff **********  */
92
93 static bNodeType *node_get_type(bNodeTree *ntree, int type, bNodeTree *ngroup, ID *id)
94 {
95         if(type==NODE_GROUP) {
96                 if(ngroup && GS(ngroup->id.name)==ID_NT) {
97                         return ngroup->owntype;
98                 }
99                 return NULL;
100         }
101         else {
102                 bNodeType *ntype = ntree->alltypes.first;
103                 for(; ntype; ntype= ntype->next)
104                         if(ntype->type==type && id==ntype->id )
105                                 return ntype;
106                 
107                 return NULL;
108         }
109 }
110
111 void ntreeInitTypes(bNodeTree *ntree)
112 {
113         bNode *node, *next;
114         
115         if(ntree->type==NTREE_SHADER)
116                 ntree->alltypes= node_all_shaders;
117         else if(ntree->type==NTREE_COMPOSIT)
118                 ntree->alltypes= node_all_composit;
119         else if(ntree->type==NTREE_TEXTURE)
120                 ntree->alltypes= node_all_textures;
121         else {
122                 ntree->alltypes= empty_list;
123                 printf("Error: no type definitions for nodes\n");
124         }
125         
126         for(node= ntree->nodes.first; node; node= next) {
127                 next= node->next;
128                 if(node->type==NODE_DYNAMIC) {
129                         bNodeType *stype= NULL;
130                         if(node->id==NULL) { /* empty script node */
131                                 stype= node_get_type(ntree, node->type, NULL, NULL);
132                         } else { /* not an empty script node */
133                                 stype= node_get_type(ntree, node->type, NULL, node->id);
134                                 if(!stype) {
135                                         stype= node_get_type(ntree, node->type, NULL, NULL);
136                                         /* needed info if the pynode script fails now: */
137                                         if (node->id) node->storage= ntree;
138                                 } else {
139                                         node->custom1= 0;
140                                         node->custom1= BSET(node->custom1,NODE_DYNAMIC_ADDEXIST);
141                                 }
142                         }
143                         node->typeinfo= stype;
144                         node->typeinfo->initfunc(node);
145                 } else {
146                         node->typeinfo= node_get_type(ntree, node->type, (bNodeTree *)node->id, NULL);
147                 }
148
149                 if(node->typeinfo==NULL) {
150                         printf("Error: Node type %s doesn't exist anymore, removed\n", node->name);
151                         nodeFreeNode(ntree, node);
152                 }
153         }
154                         
155         ntree->init |= NTREE_TYPE_INIT;
156 }
157
158 /* updates node with (modified) bNodeType.. this should be done for all trees */
159 void ntreeUpdateType(bNodeTree *ntree, bNodeType *ntype)
160 {
161         bNode *node;
162
163         for(node= ntree->nodes.first; node; node= node->next) {
164                 if(node->typeinfo== ntype) {
165                         nodeUpdateType(ntree, node, ntype);
166                 }
167         }
168 }
169
170 /* only used internal... we depend on type definitions! */
171 static bNodeSocket *node_add_socket_type(ListBase *lb, bNodeSocketType *stype)
172 {
173         bNodeSocket *sock= MEM_callocN(sizeof(bNodeSocket), "sock");
174         
175         BLI_strncpy(sock->name, stype->name, NODE_MAXSTR);
176         if(stype->limit==0) sock->limit= 0xFFF;
177         else sock->limit= stype->limit;
178         sock->type= stype->type;
179         
180         sock->to_index= stype->own_index;
181         sock->tosock= stype->internsock;
182         
183         sock->ns.vec[0]= stype->val1;
184         sock->ns.vec[1]= stype->val2;
185         sock->ns.vec[2]= stype->val3;
186         sock->ns.vec[3]= stype->val4;
187         sock->ns.min= stype->min;
188         sock->ns.max= stype->max;
189         
190         if(lb)
191                 BLI_addtail(lb, sock);
192
193         return sock;
194 }
195
196 static void node_rem_socket(bNodeTree *ntree, ListBase *lb, bNodeSocket *sock)
197 {
198         bNodeLink *link, *next;
199         
200         for(link= ntree->links.first; link; link= next) {
201                 next= link->next;
202                 if(link->fromsock==sock || link->tosock==sock) {
203                         nodeRemLink(ntree, link);
204                 }
205         }
206         
207         BLI_remlink(lb, sock);
208         MEM_freeN(sock);
209 }
210
211 static bNodeSocket *verify_socket(ListBase *lb, bNodeSocketType *stype)
212 {
213         bNodeSocket *sock;
214         
215         for(sock= lb->first; sock; sock= sock->next) {
216                 /* both indices are zero for non-groups, otherwise it's a unique index */
217                 if(sock->to_index==stype->own_index)
218                         if(strncmp(sock->name, stype->name, NODE_MAXSTR)==0)
219                                 break;
220         }
221         if(sock) {
222                 sock->type= stype->type;                /* in future, read this from tydefs! */
223                 if(stype->limit==0) sock->limit= 0xFFF;
224                 else sock->limit= stype->limit;
225                 sock->ns.min= stype->min;
226                 sock->ns.max= stype->max;
227                 sock->tosock= stype->internsock;
228                 
229                 BLI_remlink(lb, sock);
230                 
231                 return sock;
232         }
233         else {
234                 return node_add_socket_type(NULL, stype);
235         }
236 }
237
238 static void verify_socket_list(bNodeTree *ntree, ListBase *lb, bNodeSocketType *stype_first)
239 {
240         bNodeSocketType *stype;
241         
242         /* no inputs anymore? */
243         if(stype_first==NULL) {
244                 while(lb->first)
245                         node_rem_socket(ntree, lb, lb->first);
246         }
247         else {
248                 /* step by step compare */
249                 stype= stype_first;
250                 while(stype->type != -1) {
251                         stype->sock= verify_socket(lb, stype);
252                         stype++;
253                 }
254                 /* leftovers are removed */
255                 while(lb->first)
256                         node_rem_socket(ntree, lb, lb->first);
257                 /* and we put back the verified sockets */
258                 stype= stype_first;
259                 while(stype->type != -1) {
260                         BLI_addtail(lb, stype->sock);
261                         stype++;
262                 }
263         }
264 }
265
266 void nodeVerifyType(bNodeTree *ntree, bNode *node)
267 {
268         bNodeType *ntype= node->typeinfo;
269         
270         if(ntype) {
271                 /* might add some other verify stuff here */
272                 
273                 verify_socket_list(ntree, &node->inputs, ntype->inputs);
274                 verify_socket_list(ntree, &node->outputs, ntype->outputs);
275         }
276 }
277
278 void ntreeVerifyTypes(bNodeTree *ntree)
279 {
280         bNode *node;
281         
282         /* if((ntree->init & NTREE_TYPE_INIT)==0) */
283         ntreeInitTypes(ntree);
284
285         /* check inputs and outputs, and remove or insert them */
286         for(node= ntree->nodes.first; node; node= node->next)
287                 nodeVerifyType(ntree, node);
288         
289 }
290
291 /* ************** Group stuff ********** */
292
293 bNodeType node_group_typeinfo= {
294         /* next,prev   */       NULL, NULL,
295         /* type code   */       NODE_GROUP,
296         /* name        */       "Group",
297         /* width+range */       120, 60, 200,
298         /* class+opts  */       NODE_CLASS_GROUP, NODE_OPTIONS,
299         /* input sock  */       NULL,
300         /* output sock */       NULL,
301         /* storage     */       "",
302         /* execfunc    */       NULL,
303         /* butfunc     */       NULL,
304         /* initfunc    */       NULL,
305         /* freestoragefunc    */        NULL,
306         /* copystoragefunc    */        NULL,
307         /* id          */       NULL
308 };
309
310 /* tag internal sockets */
311 static void group_tag_internal_sockets(bNodeTree *ngroup)
312 {
313         bNode *node;
314         bNodeSocket *sock;
315         bNodeLink *link;
316         
317         /* clear intern tag, but check already for hidden sockets */
318         for(node= ngroup->nodes.first; node; node= node->next) {
319                 for(sock= node->inputs.first; sock; sock= sock->next)
320                         sock->intern= sock->flag & SOCK_HIDDEN;
321                 for(sock= node->outputs.first; sock; sock= sock->next)
322                         sock->intern= sock->flag & (SOCK_HIDDEN|SOCK_UNAVAIL);
323         }
324         /* set tag */
325         for(link= ngroup->links.first; link; link= link->next) {
326                 link->fromsock->intern= 1;
327                 link->tosock->intern= 1;
328         }
329         
330         /* remove link pointer to external links (only happens on create group) */
331         for(node= ngroup->nodes.first; node; node= node->next) {
332                 for(sock= node->inputs.first; sock; sock= sock->next)
333                         if(sock->intern==0)
334                                 sock->link= NULL;
335         }
336
337         /* set all intern sockets to own_index zero, makes sure that later use won't mixup */
338         for(node= ngroup->nodes.first; node; node= node->next) {
339                 for(sock= node->inputs.first; sock; sock= sock->next)
340                         if(sock->intern)
341                                 sock->own_index= 0;
342                 for(sock= node->outputs.first; sock; sock= sock->next)
343                         if(sock->intern)
344                                 sock->own_index= 0;
345         }
346 }
347
348 /* after editing group, new sockets are zero */
349 /* this routine ensures unique identifiers for zero sockets that are exposed */
350 static void group_verify_own_indices(bNodeTree *ngroup)
351 {
352         bNode *node;
353         bNodeSocket *sock;
354         
355         for(node= ngroup->nodes.first; node; node= node->next) {
356                 for(sock= node->inputs.first; sock; sock= sock->next)
357                         if(sock->own_index==0 && sock->intern==0)
358                                 sock->own_index= ++(ngroup->cur_index);
359                 for(sock= node->outputs.first; sock; sock= sock->next)
360                         if(sock->own_index==0 && sock->intern==0)
361                                 sock->own_index= ++(ngroup->cur_index);
362         }
363         //printf("internal index %d\n", ngroup->cur_index);
364 }
365
366
367 /* nodetrees can be used as groups, so we need typeinfo structs generated */
368 void ntreeMakeOwnType(bNodeTree *ngroup)
369 {
370         bNode *node;
371         bNodeSocket *sock;
372         int totin= 0, totout=0, a;
373
374         /* tags socket when internal linked */
375         group_tag_internal_sockets(ngroup);
376         
377         /* ensure all sockets have own unique id */
378         group_verify_own_indices(ngroup);
379         
380         /* counting stats */
381         for(node= ngroup->nodes.first; node; node= node->next) {
382                 if(node->type==NODE_GROUP)
383                         break;
384                 for(sock= node->inputs.first; sock; sock= sock->next)
385                         if(sock->intern==0) 
386                                 totin++;
387                 for(sock= node->outputs.first; sock; sock= sock->next)
388                         if(sock->intern==0) 
389                                 totout++;
390         }
391         /* debug: nodetrees in nodetrees not handled yet */
392         if(node) {
393                 printf("group in group, not supported yet\n");
394                 return;
395         }
396         
397         /* free own type struct */
398         if(ngroup->owntype) {
399                 if(ngroup->owntype->inputs)
400                         MEM_freeN(ngroup->owntype->inputs);
401                 if(ngroup->owntype->outputs)
402                         MEM_freeN(ngroup->owntype->outputs);
403                 MEM_freeN(ngroup->owntype);
404         }
405         
406         /* make own type struct */
407         ngroup->owntype= MEM_callocN(sizeof(bNodeType), "group type");
408         *ngroup->owntype= node_group_typeinfo; /* copy data, for init */
409         
410         /* input type arrays */
411         if(totin) {
412                 bNodeSocketType *stype;
413                 bNodeSocketType *inputs= MEM_callocN(sizeof(bNodeSocketType)*(totin+1), "bNodeSocketType");
414                 a= 0;
415                 
416                 for(node= ngroup->nodes.first; node; node= node->next) {
417                         /* nodes are presumed fully verified, stype and socket list are in sync */
418                         stype= node->typeinfo->inputs;
419                         for(sock= node->inputs.first; sock; sock= sock->next, stype++) {
420                                 if(sock->intern==0) {
421                                         /* debug only print */
422                                         if(stype==NULL || stype->type==-1) printf("group verification error %s\n", ngroup->id.name);
423                                         
424                                         inputs[a]= *stype;
425                                         inputs[a].own_index= sock->own_index;
426                                         inputs[a].internsock= sock;     
427                                         a++;
428                                 }
429                         }
430                 }
431                 inputs[a].type= -1;     /* terminator code */
432                 ngroup->owntype->inputs= inputs;
433         }       
434         
435         /* output type arrays */
436         if(totout) {
437                 bNodeSocketType *stype;
438                 bNodeSocketType *outputs= MEM_callocN(sizeof(bNodeSocketType)*(totout+1), "bNodeSocketType");
439                 a= 0;
440                 
441                 for(node= ngroup->nodes.first; node; node= node->next) {
442                         /* nodes are presumed fully verified, stype and socket list are in sync */
443                         stype= node->typeinfo->outputs;
444                         for(sock= node->outputs.first; sock; sock= sock->next, stype++) {
445                                 if(sock->intern==0) {
446                                         /* debug only print */
447                                         if(stype==NULL || stype->type==-1) printf("group verification error %s\n", ngroup->id.name);
448                                         
449                                         outputs[a]= *stype;
450                                         outputs[a].own_index= sock->own_index;
451                                         outputs[a].internsock= sock;    
452                                         a++;
453                                 }
454                         }
455                 }
456                 outputs[a].type= -1;    /* terminator code */
457                 ngroup->owntype->outputs= outputs;
458         }
459         
460         /* voila, the nodetree has the full definition for generating group-node instances! */
461 }
462
463
464 static bNodeSocket *groupnode_find_tosock(bNode *gnode, int index)
465 {
466         bNodeSocket *sock;
467         
468         for(sock= gnode->inputs.first; sock; sock= sock->next)
469                 if(sock->to_index==index)
470                         return sock;
471         return NULL;
472 }
473
474 static bNodeSocket *groupnode_find_fromsock(bNode *gnode, int index)
475 {
476         bNodeSocket *sock;
477         
478         for(sock= gnode->outputs.first; sock; sock= sock->next)
479                 if(sock->to_index==index)
480                         return sock;
481         return NULL;
482 }
483
484 bNode *nodeMakeGroupFromSelected(bNodeTree *ntree)
485 {
486         bNodeLink *link, *linkn;
487         bNode *node, *gnode, *nextn;
488         bNodeSocket *sock;
489         bNodeTree *ngroup;
490         float min[2], max[2];
491         int totnode=0;
492         
493         INIT_MINMAX2(min, max);
494         
495         /* is there something to group? also do some clearing */
496         for(node= ntree->nodes.first; node; node= node->next) {
497                 if(node->flag & NODE_SELECT) {
498                         /* no groups in groups */
499                         if(node->type==NODE_GROUP)
500                                 return NULL;
501                         DO_MINMAX2( (&node->locx), min, max);
502                         totnode++;
503                 }
504                 node->done= 0;
505         }
506         if(totnode==0) return NULL;
507         
508         /* check if all connections are OK, no unselected node has both
509                 inputs and outputs to a selection */
510         for(link= ntree->links.first; link; link= link->next) {
511                 if(link->fromnode->flag & NODE_SELECT)
512                         link->tonode->done |= 1;
513                 if(link->tonode->flag & NODE_SELECT)
514                         link->fromnode->done |= 2;
515         }       
516         
517         for(node= ntree->nodes.first; node; node= node->next) {
518                 if((node->flag & NODE_SELECT)==0)
519                         if(node->done==3)
520                                 break;
521         }
522         if(node) 
523                 return NULL;
524         
525         /* OK! new nodetree */
526         ngroup= alloc_libblock(&G.main->nodetree, ID_NT, "NodeGroup");
527         ngroup->type= ntree->type;
528         ngroup->alltypes= ntree->alltypes;
529         
530         /* move nodes over */
531         for(node= ntree->nodes.first; node; node= nextn) {
532                 nextn= node->next;
533                 if(node->flag & NODE_SELECT) {
534                         BLI_remlink(&ntree->nodes, node);
535                         BLI_addtail(&ngroup->nodes, node);
536                         node->locx-= 0.5f*(min[0]+max[0]);
537                         node->locy-= 0.5f*(min[1]+max[1]);
538
539                         /* set socket own_index to zero since it can still have a value
540                          * from being in a group before, otherwise it doesn't get a unique
541                          * index in group_verify_own_indices */
542                         for(sock= node->inputs.first; sock; sock= sock->next)
543                                 sock->own_index= 0;
544                         for(sock= node->outputs.first; sock; sock= sock->next)
545                                 sock->own_index= 0;
546                 }
547         }
548
549         /* move links over */
550         for(link= ntree->links.first; link; link= linkn) {
551                 linkn= link->next;
552                 if(link->fromnode->flag & link->tonode->flag & NODE_SELECT) {
553                         BLI_remlink(&ntree->links, link);
554                         BLI_addtail(&ngroup->links, link);
555                 }
556         }
557         
558         /* now we can make own group typeinfo */
559         ntreeMakeOwnType(ngroup);
560         
561         /* make group node */
562         gnode= nodeAddNodeType(ntree, NODE_GROUP, ngroup, NULL);
563         gnode->locx= 0.5f*(min[0]+max[0]);
564         gnode->locy= 0.5f*(min[1]+max[1]);
565         
566         /* relink external sockets */
567         for(link= ntree->links.first; link; link= linkn) {
568                 linkn= link->next;
569                 
570                 if(link->tonode->flag & NODE_SELECT) {
571                         link->tonode= gnode;
572                         sock= groupnode_find_tosock(gnode, link->tosock->own_index);
573                         if(sock==NULL) {
574                                 nodeRemLink(ntree, link);       
575                                 printf("Removed link, cannot mix internal and external sockets in group\n");
576                         }
577                         else link->tosock= sock;
578                 }
579                 else if(link->fromnode->flag & NODE_SELECT) {
580                         link->fromnode= gnode;
581                         sock= groupnode_find_fromsock(gnode, link->fromsock->own_index);
582                         if(sock==NULL) {
583                                 nodeRemLink(ntree, link);       
584                                 printf("Removed link, cannot mix internal and external sockets in group\n");
585                         }
586                         else link->fromsock= sock;
587                 }
588         }
589         
590         /* initialize variables of unused input sockets */
591         for(node= ngroup->nodes.first; node; node= node->next) {
592                 for(sock= node->inputs.first; sock; sock= sock->next) {
593                         if(sock->intern==0) {
594                                 bNodeSocket *nsock= groupnode_find_tosock(gnode, sock->own_index);
595                                 if(nsock) {
596                                         QUATCOPY(nsock->ns.vec, sock->ns.vec);
597                                 }
598                         }
599                 }
600         }
601
602         /* update node levels */
603         ntreeSolveOrder(ntree);
604
605         return gnode;
606 }
607
608 /* note: ungroup: group_indices zero! */
609
610 /* here's a nasty little one, need to check users... */
611 /* should become callbackable... */
612 void nodeVerifyGroup(bNodeTree *ngroup)
613 {
614         
615         /* group changed, so we rebuild the type definition */
616         ntreeMakeOwnType(ngroup);
617         
618         if(ngroup->type==NTREE_SHADER) {
619                 Material *ma;
620                 for(ma= G.main->mat.first; ma; ma= ma->id.next) {
621                         if(ma->nodetree) {
622                                 bNode *node;
623                                 
624                                 /* find if group is in tree */
625                                 for(node= ma->nodetree->nodes.first; node; node= node->next)
626                                         if(node->id == (ID *)ngroup)
627                                                 break;
628                                 
629                                 if(node) {
630                                         /* set all type pointers OK */
631                                         ntreeInitTypes(ma->nodetree);
632                                         
633                                         for(node= ma->nodetree->nodes.first; node; node= node->next)
634                                                 if(node->id == (ID *)ngroup)
635                                                         nodeVerifyType(ma->nodetree, node);
636                                 }
637                         }
638                 }
639         }
640         else if(ngroup->type==NTREE_COMPOSIT) {
641                 Scene *sce;
642                 for(sce= G.main->scene.first; sce; sce= sce->id.next) {
643                         if(sce->nodetree) {
644                                 bNode *node;
645                                 
646                                 /* find if group is in tree */
647                                 for(node= sce->nodetree->nodes.first; node; node= node->next)
648                                         if(node->id == (ID *)ngroup)
649                                                 break;
650                                 
651                                 if(node) {
652                                         /* set all type pointers OK */
653                                         ntreeInitTypes(sce->nodetree);
654                                         
655                                         for(node= sce->nodetree->nodes.first; node; node= node->next)
656                                                 if(node->id == (ID *)ngroup)
657                                                         nodeVerifyType(sce->nodetree, node);
658                                 }
659                         }
660                 }
661         }
662         else if(ngroup->type==NTREE_TEXTURE) {
663                 Tex *tx;
664                 for(tx= G.main->tex.first; tx; tx= tx->id.next) {
665                         if(tx->nodetree) {
666                                 bNode *node;
667                                 
668                                 /* find if group is in tree */
669                                 for(node= tx->nodetree->nodes.first; node; node= node->next)
670                                         if(node->id == (ID *)ngroup)
671                                                 break;
672                                 
673                                 if(node) {
674                                         /* set all type pointers OK */
675                                         ntreeInitTypes(tx->nodetree);
676                                         
677                                         for(node= tx->nodetree->nodes.first; node; node= node->next)
678                                                 if(node->id == (ID *)ngroup)
679                                                         nodeVerifyType(tx->nodetree, node);
680                                 }
681                         }
682                 }
683         }
684 }
685
686 /* also to check all users of groups. Now only used in editor for hide/unhide */
687 /* should become callbackable? */
688 void nodeGroupSocketUseFlags(bNodeTree *ngroup)
689 {
690         bNode *node;
691         bNodeSocket *sock;
692
693         /* clear flags */
694         for(node= ngroup->nodes.first; node; node= node->next) {
695                 for(sock= node->inputs.first; sock; sock= sock->next)
696                         sock->flag &= ~SOCK_IN_USE;
697                 for(sock= node->outputs.first; sock; sock= sock->next)
698                         sock->flag &= ~SOCK_IN_USE;
699         }
700         
701         /* tag all thats in use */
702         if(ngroup->type==NTREE_SHADER) {
703                 Material *ma;
704                 for(ma= G.main->mat.first; ma; ma= ma->id.next) {
705                         if(ma->nodetree) {
706                                 for(node= ma->nodetree->nodes.first; node; node= node->next) {
707                                         if(node->id==(ID *)ngroup) {
708                                                 for(sock= node->inputs.first; sock; sock= sock->next)
709                                                         if(sock->link)
710                                                                 if(sock->tosock) 
711                                                                         sock->tosock->flag |= SOCK_IN_USE;
712                                                 for(sock= node->outputs.first; sock; sock= sock->next)
713                                                         if(nodeCountSocketLinks(ma->nodetree, sock))
714                                                                 if(sock->tosock) 
715                                                                         sock->tosock->flag |= SOCK_IN_USE;
716                                         }
717                                 }
718                         }
719                 }
720         }
721         else if(ngroup->type==NTREE_COMPOSIT) {
722                 Scene *sce;
723                 for(sce= G.main->scene.first; sce; sce= sce->id.next) {
724                         if(sce->nodetree) {
725                                 for(node= sce->nodetree->nodes.first; node; node= node->next) {
726                                         if(node->id==(ID *)ngroup) {
727                                                 for(sock= node->inputs.first; sock; sock= sock->next)
728                                                         if(sock->link)
729                                                                 if(sock->tosock) 
730                                                                         sock->tosock->flag |= SOCK_IN_USE;
731                                                 for(sock= node->outputs.first; sock; sock= sock->next)
732                                                         if(nodeCountSocketLinks(sce->nodetree, sock))
733                                                                 if(sock->tosock) 
734                                                                         sock->tosock->flag |= SOCK_IN_USE;
735                                         }
736                                 }
737                         }
738                 }
739         }
740         else if(ngroup->type==NTREE_TEXTURE) {
741                 Tex *tx;
742                 for(tx= G.main->tex.first; tx; tx= tx->id.next) {
743                         if(tx->nodetree) {
744                                 for(node= tx->nodetree->nodes.first; node; node= node->next) {
745                                         if(node->id==(ID *)ngroup) {
746                                                 for(sock= node->inputs.first; sock; sock= sock->next)
747                                                         if(sock->link)
748                                                                 if(sock->tosock) 
749                                                                         sock->tosock->flag |= SOCK_IN_USE;
750                                                 for(sock= node->outputs.first; sock; sock= sock->next)
751                                                         if(nodeCountSocketLinks(tx->nodetree, sock))
752                                                                 if(sock->tosock) 
753                                                                         sock->tosock->flag |= SOCK_IN_USE;
754                                         }
755                                 }
756                         }
757                 }
758         }
759         
760 }
761 /* finds a node based on its name */
762 bNode *nodeFindNodebyName(bNodeTree *ntree, const char *name)
763 {
764         bNode *node=NULL;
765         
766         for(node= ntree->nodes.first; node; node= node->next) {
767                 if (strcmp(name, node->name) == 0)
768                         break;
769         }
770         return node;
771 }
772
773 /* finds a node based on given socket */
774 int nodeFindNode(bNodeTree *ntree, bNodeSocket *sock, bNode **nodep, int *sockindex)
775 {
776         bNode *node;
777         bNodeSocket *tsock;
778         int index= 0;
779         
780         for(node= ntree->nodes.first; node; node= node->next) {
781                 for(index=0, tsock= node->inputs.first; tsock; tsock= tsock->next, index++)
782                         if(tsock==sock)
783                                 break;
784                 if(tsock)
785                         break;
786                 for(index=0, tsock= node->outputs.first; tsock; tsock= tsock->next, index++)
787                         if(tsock==sock)
788                                 break;
789                 if(tsock)
790                         break;
791         }
792
793         if(node) {
794                 *nodep= node;
795                 if(sockindex) *sockindex= index;
796                 return 1;
797         }
798         
799         *nodep= NULL;
800         return 0;
801 }
802
803 /* returns 1 if its OK */
804 int nodeGroupUnGroup(bNodeTree *ntree, bNode *gnode)
805 {
806         bNodeLink *link, *linkn;
807         bNode *node, *nextn;
808         bNodeTree *ngroup, *wgroup;
809         int index;
810         
811         ngroup= (bNodeTree *)gnode->id;
812         if(ngroup==NULL) return 0;
813         
814         /* clear new pointers, set in copytree */
815         for(node= ntree->nodes.first; node; node= node->next)
816                 node->new_node= NULL;
817
818         wgroup= ntreeCopyTree(ngroup, 0);
819         
820         /* add the nodes into the ntree */
821         for(node= wgroup->nodes.first; node; node= nextn) {
822                 nextn= node->next;
823                 BLI_remlink(&wgroup->nodes, node);
824                 BLI_addtail(&ntree->nodes, node);
825                 node->locx+= gnode->locx;
826                 node->locy+= gnode->locy;
827                 node->flag |= NODE_SELECT;
828         }
829         /* and the internal links */
830         for(link= wgroup->links.first; link; link= linkn) {
831                 linkn= link->next;
832                 BLI_remlink(&wgroup->links, link);
833                 BLI_addtail(&ntree->links, link);
834         }
835
836         /* restore links to and from the gnode */
837         for(link= ntree->links.first; link; link= link->next) {
838                 if(link->tonode==gnode) {
839                         /* link->tosock->tosock is on the node we look for */
840                         nodeFindNode(ngroup, link->tosock->tosock, &nextn, &index);
841                         if(nextn==NULL) printf("wrong stuff!\n");
842                         else if(nextn->new_node==NULL) printf("wrong stuff too!\n");
843                         else {
844                                 link->tonode= nextn->new_node;
845                                 link->tosock= BLI_findlink(&link->tonode->inputs, index);
846                         }
847                 }
848                 else if(link->fromnode==gnode) {
849                         /* link->fromsock->tosock is on the node we look for */
850                         nodeFindNode(ngroup, link->fromsock->tosock, &nextn, &index);
851                         if(nextn==NULL) printf("1 wrong stuff!\n");
852                         else if(nextn->new_node==NULL) printf("1 wrong stuff too!\n");
853                         else {
854                                 link->fromnode= nextn->new_node;
855                                 link->fromsock= BLI_findlink(&link->fromnode->outputs, index);
856                         }
857                 }
858         }
859         
860         /* remove the gnode & work tree */
861         free_libblock(&G.main->nodetree, wgroup);
862         
863         nodeFreeNode(ntree, gnode);
864         
865         /* solve order goes fine, but the level tags not... doing it twice works for now. solve this once */
866         ntreeSolveOrder(ntree);
867         ntreeSolveOrder(ntree);
868
869         return 1;
870 }
871
872 void nodeCopyGroup(bNode *gnode)
873 {
874         bNodeSocket *sock;
875
876         gnode->id->us--;
877         gnode->id= (ID *)ntreeCopyTree((bNodeTree *)gnode->id, 0);
878
879         /* new_sock was set in nodeCopyNode */
880         for(sock=gnode->inputs.first; sock; sock=sock->next)
881                 if(sock->tosock)
882                         sock->tosock= sock->tosock->new_sock;
883
884         for(sock=gnode->outputs.first; sock; sock=sock->next)
885                 if(sock->tosock)
886                         sock->tosock= sock->tosock->new_sock;
887 }
888
889 /* ************** Add stuff ********** */
890 void nodeAddSockets(bNode *node, bNodeType *ntype)
891 {
892         bNodeSocketType *stype;
893
894         if(ntype->inputs) {
895                 stype= ntype->inputs;
896                 while(stype->type != -1) {
897                         node_add_socket_type(&node->inputs, stype);
898                         stype++;
899                 }
900         }
901         if(ntype->outputs) {
902                 stype= ntype->outputs;
903                 while(stype->type != -1) {
904                         node_add_socket_type(&node->outputs, stype);
905                         stype++;
906                 }
907         }
908 }
909 /* Find the first available, non-duplicate name for a given node */
910 void nodeUniqueName(bNodeTree *ntree, bNode *node)
911 {
912         BLI_uniquename(&ntree->nodes, node, "Node", '.', offsetof(bNode, name), 32);
913 }
914
915 bNode *nodeAddNodeType(bNodeTree *ntree, int type, bNodeTree *ngroup, ID *id)
916 {
917         bNode *node= NULL;
918         bNodeType *ntype= NULL;
919
920         if(type>=NODE_DYNAMIC_MENU) {
921                 int a=0, idx= type-NODE_DYNAMIC_MENU;
922                 ntype= ntree->alltypes.first;
923                 while(ntype) {
924                         if(ntype->type==NODE_DYNAMIC) {
925                                 if(a==idx)
926                                         break;
927                                 a++;
928                         }
929                         ntype= ntype->next;
930                 }
931         } else
932                 ntype= node_get_type(ntree, type, ngroup, id);
933
934         node= MEM_callocN(sizeof(bNode), "new node");
935         BLI_addtail(&ntree->nodes, node);
936         node->typeinfo= ntype;
937         if(type>=NODE_DYNAMIC_MENU)
938                 node->custom2= type; /* for node_dynamic_init */
939
940         if(ngroup)
941                 BLI_strncpy(node->name, ngroup->id.name+2, NODE_MAXSTR);
942         else if(type>NODE_DYNAMIC_MENU) {
943                 BLI_strncpy(node->name, ntype->id->name+2, NODE_MAXSTR);
944         }
945         else
946                 BLI_strncpy(node->name, ntype->name, NODE_MAXSTR);
947
948         nodeUniqueName(ntree, node);
949         
950         node->type= ntype->type;
951         node->flag= NODE_SELECT|ntype->flag;
952         node->width= ntype->width;
953         node->miniwidth= 42.0f;         /* small value only, allows print of first chars */
954
955         if(type==NODE_GROUP)
956                 node->id= (ID *)ngroup;
957
958         /* need init handler later? */
959         /* got it-bob*/
960         if(ntype->initfunc!=NULL)
961                 ntype->initfunc(node);
962         
963         nodeAddSockets(node, ntype);
964         
965         return node;
966 }
967
968 void nodeMakeDynamicType(bNode *node)
969 {
970         /* find SH_DYNAMIC_NODE ntype */
971         bNodeType *ntype= node_all_shaders.first;
972         while(ntype) {
973                 if(ntype->type==NODE_DYNAMIC && ntype->id==NULL)
974                         break;
975                 ntype= ntype->next;
976         }
977
978         /* make own type struct to fill */
979         if(ntype) {
980                 /*node->typeinfo= MEM_dupallocN(ntype);*/
981                 bNodeType *newtype= MEM_callocN(sizeof(bNodeType), "dynamic bNodeType");
982                 *newtype= *ntype;
983                 newtype->name= BLI_strdup(ntype->name);
984                 node->typeinfo= newtype;
985         }
986 }
987
988 void nodeUpdateType(bNodeTree *ntree, bNode* node, bNodeType *ntype)
989 {
990         verify_socket_list(ntree, &node->inputs, ntype->inputs);
991         verify_socket_list(ntree, &node->outputs, ntype->outputs);
992 }
993
994 /* keep socket listorder identical, for copying links */
995 /* ntree is the target tree */
996 bNode *nodeCopyNode(struct bNodeTree *ntree, struct bNode *node, int internal)
997 {
998         bNode *nnode= MEM_callocN(sizeof(bNode), "dupli node");
999         bNodeSocket *sock, *oldsock;
1000
1001         *nnode= *node;
1002         nodeUniqueName(ntree, nnode);
1003         
1004         BLI_addtail(&ntree->nodes, nnode);
1005         
1006         BLI_duplicatelist(&nnode->inputs, &node->inputs);
1007         oldsock= node->inputs.first;
1008         for(sock= nnode->inputs.first; sock; sock= sock->next, oldsock= oldsock->next) {
1009                 oldsock->new_sock= sock;
1010                 if(internal)
1011                         sock->own_index= 0;
1012         }
1013         
1014         BLI_duplicatelist(&nnode->outputs, &node->outputs);
1015         oldsock= node->outputs.first;
1016         for(sock= nnode->outputs.first; sock; sock= sock->next, oldsock= oldsock->next) {
1017                 if(internal)
1018                         sock->own_index= 0;
1019                 sock->stack_index= 0;
1020                 sock->ns.data= NULL;
1021                 oldsock->new_sock= sock;
1022         }
1023         
1024         /* don't increase node->id users, freenode doesn't decrement either */
1025         
1026         if(node->typeinfo->copystoragefunc)
1027                 node->typeinfo->copystoragefunc(node, nnode);
1028         
1029         node->new_node= nnode;
1030         nnode->new_node= NULL;
1031         nnode->preview= NULL;
1032         
1033         return nnode;
1034 }
1035
1036 bNodeLink *nodeAddLink(bNodeTree *ntree, bNode *fromnode, bNodeSocket *fromsock, bNode *tonode, bNodeSocket *tosock)
1037 {
1038         bNodeLink *link= MEM_callocN(sizeof(bNodeLink), "link");
1039         
1040         BLI_addtail(&ntree->links, link);
1041         link->fromnode= fromnode;
1042         link->fromsock= fromsock;
1043         link->tonode= tonode;
1044         link->tosock= tosock;
1045         
1046         return link;
1047 }
1048
1049 void nodeRemLink(bNodeTree *ntree, bNodeLink *link)
1050 {
1051         BLI_remlink(&ntree->links, link);
1052         if(link->tosock)
1053                 link->tosock->link= NULL;
1054         MEM_freeN(link);
1055 }
1056
1057 void nodeRemSocketLinks(bNodeTree *ntree, bNodeSocket *sock)
1058 {
1059         bNodeLink *link, *next;
1060         
1061         for(link= ntree->links.first; link; link= next) {
1062                 next= link->next;
1063                 if(link->fromsock==sock || link->tosock==sock) {
1064                         nodeRemLink(ntree, link);
1065                 }
1066         }
1067 }
1068
1069
1070 bNodeTree *ntreeAddTree(int type)
1071 {
1072         bNodeTree *ntree= MEM_callocN(sizeof(bNodeTree), "new node tree");
1073         ntree->type= type;
1074         ntree->alltypes.first = NULL;
1075         ntree->alltypes.last = NULL;
1076
1077         /* this helps RNA identify ID pointers as nodetree */
1078     if(ntree->type==NTREE_SHADER)
1079                 BLI_strncpy(ntree->id.name, "NTShader Nodetree", sizeof(ntree->id.name));
1080     else if(ntree->type==NTREE_COMPOSIT)
1081                 BLI_strncpy(ntree->id.name, "NTCompositing Nodetree", sizeof(ntree->id.name));
1082     else if(ntree->type==NTREE_TEXTURE)
1083                 BLI_strncpy(ntree->id.name, "NTTexture Nodetree", sizeof(ntree->id.name));
1084         
1085         ntreeInitTypes(ntree);
1086         return ntree;
1087 }
1088
1089 /* Warning: this function gets called during some rather unexpected times
1090  *      - internal_select is only 1 when used for duplicating selected nodes (i.e. Shift-D duplicate operator)
1091  *      - this gets called when executing compositing updates (for threaded previews)
1092  *      - when the nodetree datablock needs to be copied (i.e. when users get copied)
1093  */
1094 bNodeTree *ntreeCopyTree(bNodeTree *ntree, int internal_select)
1095 {
1096         bNodeTree *newtree;
1097         bNode *node, *nnode, *last;
1098         bNodeLink *link, *nlink;
1099         bNodeSocket *sock;
1100         int a;
1101         
1102         if(ntree==NULL) return NULL;
1103         
1104         if(internal_select==0) {
1105                 /* is ntree part of library? */
1106                 for(newtree=G.main->nodetree.first; newtree; newtree= newtree->id.next)
1107                         if(newtree==ntree) break;
1108                 if(newtree)
1109                         newtree= copy_libblock(ntree);
1110                 else
1111                         newtree= MEM_dupallocN(ntree);
1112                 newtree->nodes.first= newtree->nodes.last= NULL;
1113                 newtree->links.first= newtree->links.last= NULL;
1114         }
1115         else
1116                 newtree= ntree;
1117         
1118         last= ntree->nodes.last;
1119         for(node= ntree->nodes.first; node; node= node->next) {
1120                 
1121                 node->new_node= NULL;
1122                 if(internal_select==0 || (node->flag & NODE_SELECT)) {
1123                         nnode= nodeCopyNode(newtree, node, internal_select);    /* sets node->new */
1124                         if(internal_select) {
1125                                 node->flag &= ~(NODE_SELECT|NODE_ACTIVE);
1126                                 nnode->flag |= NODE_SELECT;
1127                         }
1128                 }
1129                 if(node==last) break;
1130         }
1131         
1132         /* check for copying links */
1133         for(link= ntree->links.first; link; link= link->next) {
1134                 if(link->fromnode==NULL || link->tonode==NULL);
1135                 else if(link->fromnode->new_node && link->tonode->new_node) {
1136                         nlink= nodeAddLink(newtree, link->fromnode->new_node, NULL, link->tonode->new_node, NULL);
1137                         /* sockets were copied in order */
1138                         for(a=0, sock= link->fromnode->outputs.first; sock; sock= sock->next, a++) {
1139                                 if(sock==link->fromsock)
1140                                         break;
1141                         }
1142                         nlink->fromsock= BLI_findlink(&link->fromnode->new_node->outputs, a);
1143                         
1144                         for(a=0, sock= link->tonode->inputs.first; sock; sock= sock->next, a++) {
1145                                 if(sock==link->tosock)
1146                                         break;
1147                         }
1148                         nlink->tosock= BLI_findlink(&link->tonode->new_node->inputs, a);
1149                 }
1150         }
1151         
1152         /* own type definition for group usage */
1153         if(internal_select==0) {
1154                 if(ntree->owntype) {
1155                         newtree->owntype= MEM_dupallocN(ntree->owntype);
1156                         if(ntree->owntype->inputs)
1157                                 newtree->owntype->inputs= MEM_dupallocN(ntree->owntype->inputs);
1158                         if(ntree->owntype->outputs)
1159                                 newtree->owntype->outputs= MEM_dupallocN(ntree->owntype->outputs);
1160                 }
1161         }
1162         /* weird this is required... there seem to be link pointers wrong still? */
1163         /* anyhoo, doing this solves crashes on copying entire tree (copy scene) and delete nodes */
1164         ntreeSolveOrder(newtree);
1165
1166         return newtree;
1167 }
1168
1169 /* *************** preview *********** */
1170 /* if node->preview, then we assume the rect to exist */
1171
1172 static void node_free_preview(bNode *node)
1173 {
1174         if(node->preview) {
1175                 if(node->preview->rect)
1176                         MEM_freeN(node->preview->rect);
1177                 MEM_freeN(node->preview);
1178                 node->preview= NULL;
1179         }       
1180 }
1181
1182 static void node_init_preview(bNode *node, int xsize, int ysize)
1183 {
1184         
1185         if(node->preview==NULL) {
1186                 node->preview= MEM_callocN(sizeof(bNodePreview), "node preview");
1187                 //              printf("added preview %s\n", node->name);
1188         }
1189         
1190         /* node previews can get added with variable size this way */
1191         if(xsize==0 || ysize==0)
1192                 return;
1193         
1194         /* sanity checks & initialize */
1195         if(node->preview->rect) {
1196                 if(node->preview->xsize!=xsize && node->preview->ysize!=ysize) {
1197                         MEM_freeN(node->preview->rect);
1198                         node->preview->rect= NULL;
1199                 }
1200         }
1201         
1202         if(node->preview->rect==NULL) {
1203                 node->preview->rect= MEM_callocN(4*xsize + xsize*ysize*sizeof(float)*4, "node preview rect");
1204                 node->preview->xsize= xsize;
1205                 node->preview->ysize= ysize;
1206         }
1207         else
1208                 memset(node->preview->rect, 0, 4*xsize + xsize*ysize*sizeof(float)*4);
1209 }
1210
1211 void ntreeInitPreview(bNodeTree *ntree, int xsize, int ysize)
1212 {
1213         bNode *node;
1214         
1215         if(ntree==NULL)
1216                 return;
1217         
1218         for(node= ntree->nodes.first; node; node= node->next) {
1219                 if(node->typeinfo->flag & NODE_PREVIEW) /* hrms, check for closed nodes? */
1220                         node_init_preview(node, xsize, ysize);
1221                 if(node->type==NODE_GROUP && (node->flag & NODE_GROUP_EDIT))
1222                         ntreeInitPreview((bNodeTree *)node->id, xsize, ysize);
1223         }               
1224 }
1225
1226 static void nodeClearPreview(bNode *node)
1227 {
1228         if(node->preview && node->preview->rect)
1229                 memset(node->preview->rect, 0, MEM_allocN_len(node->preview->rect));
1230 }
1231
1232 /* use it to enforce clear */
1233 void ntreeClearPreview(bNodeTree *ntree)
1234 {
1235         bNode *node;
1236         
1237         if(ntree==NULL)
1238                 return;
1239         
1240         for(node= ntree->nodes.first; node; node= node->next) {
1241                 if(node->typeinfo->flag & NODE_PREVIEW)
1242                         nodeClearPreview(node);
1243                 if(node->type==NODE_GROUP && (node->flag & NODE_GROUP_EDIT))
1244                         ntreeClearPreview((bNodeTree *)node->id);
1245         }               
1246 }
1247
1248 /* hack warning! this function is only used for shader previews, and 
1249 since it gets called multiple times per pixel for Ztransp we only
1250 add the color once. Preview gets cleared before it starts render though */
1251 void nodeAddToPreview(bNode *node, float *col, int x, int y)
1252 {
1253         bNodePreview *preview= node->preview;
1254         if(preview) {
1255                 if(x>=0 && y>=0) {
1256                         if(x<preview->xsize && y<preview->ysize) {
1257                                 unsigned char *tar= preview->rect+ 4*((preview->xsize*y) + x);
1258                                 //if(tar[0]==0.0f) {
1259                                 tar[0]= FTOCHAR(col[0]);
1260                                 tar[1]= FTOCHAR(col[1]);
1261                                 tar[2]= FTOCHAR(col[2]);
1262                                 tar[3]= FTOCHAR(col[3]);
1263                                 //}
1264                         }
1265                         //else printf("prv out bound x y %d %d\n", x, y);
1266                 }
1267                 //else printf("prv out bound x y %d %d\n", x, y);
1268         }
1269 }
1270
1271
1272 /* ************** Free stuff ********** */
1273
1274 /* goes over entire tree */
1275 void nodeUnlinkNode(bNodeTree *ntree, bNode *node)
1276 {
1277         bNodeLink *link, *next;
1278         bNodeSocket *sock;
1279         ListBase *lb;
1280         
1281         for(link= ntree->links.first; link; link= next) {
1282                 next= link->next;
1283                 
1284                 if(link->fromnode==node) {
1285                         lb= &node->outputs;
1286                         NodeTagChanged(ntree, link->tonode);
1287                 }
1288                 else if(link->tonode==node)
1289                         lb= &node->inputs;
1290                 else
1291                         lb= NULL;
1292
1293                 if(lb) {
1294                         for(sock= lb->first; sock; sock= sock->next) {
1295                                 if(link->fromsock==sock || link->tosock==sock)
1296                                         break;
1297                         }
1298                         if(sock) {
1299                                 nodeRemLink(ntree, link);
1300                         }
1301                 }
1302         }
1303 }
1304
1305 static void composit_free_node_cache(bNode *node)
1306 {
1307         bNodeSocket *sock;
1308         
1309         for(sock= node->outputs.first; sock; sock= sock->next) {
1310                 if(sock->ns.data) {
1311                         free_compbuf(sock->ns.data);
1312                         sock->ns.data= NULL;
1313                 }
1314         }
1315 }
1316
1317 void nodeFreeNode(bNodeTree *ntree, bNode *node)
1318 {
1319         nodeUnlinkNode(ntree, node);
1320         BLI_remlink(&ntree->nodes, node);
1321
1322         /* since it is called while free database, node->id is undefined */
1323         
1324         if(ntree->type==NTREE_COMPOSIT)
1325                 composit_free_node_cache(node);
1326         BLI_freelistN(&node->inputs);
1327         BLI_freelistN(&node->outputs);
1328         
1329         node_free_preview(node);
1330
1331         if(node->typeinfo && node->typeinfo->freestoragefunc) {
1332                 node->typeinfo->freestoragefunc(node);
1333         }
1334
1335         MEM_freeN(node);
1336 }
1337
1338 /* do not free ntree itself here, free_libblock calls this function too */
1339 void ntreeFreeTree(bNodeTree *ntree)
1340 {
1341         bNode *node, *next;
1342         
1343         if(ntree==NULL) return;
1344         
1345         ntreeEndExecTree(ntree);        /* checks for if it is still initialized */
1346         
1347         BKE_free_animdata((ID *)ntree);
1348
1349         BLI_freelistN(&ntree->links);   /* do first, then unlink_node goes fast */
1350         
1351         for(node= ntree->nodes.first; node; node= next) {
1352                 next= node->next;
1353                 nodeFreeNode(ntree, node);
1354         }
1355         
1356         if(ntree->owntype) {
1357                 if(ntree->owntype->inputs)
1358                         MEM_freeN(ntree->owntype->inputs);
1359                 if(ntree->owntype->outputs)
1360                         MEM_freeN(ntree->owntype->outputs);
1361                 MEM_freeN(ntree->owntype);
1362         }
1363 }
1364
1365 void ntreeFreeCache(bNodeTree *ntree)
1366 {
1367         bNode *node;
1368         
1369         if(ntree==NULL) return;
1370
1371         if(ntree->type==NTREE_COMPOSIT)
1372                 for(node= ntree->nodes.first; node; node= node->next)
1373                         composit_free_node_cache(node);
1374
1375 }
1376
1377 void ntreeMakeLocal(bNodeTree *ntree)
1378 {
1379         int local=0, lib=0;
1380         
1381         /* - only lib users: do nothing
1382             * - only local users: set flag
1383             * - mixed: make copy
1384             */
1385         
1386         if(ntree->id.lib==NULL) return;
1387         if(ntree->id.us==1) {
1388                 ntree->id.lib= 0;
1389                 ntree->id.flag= LIB_LOCAL;
1390                 new_id(0, (ID *)ntree, 0);
1391                 return;
1392         }
1393         
1394         /* now check users of groups... again typedepending, callback... */
1395         if(ntree->type==NTREE_SHADER) {
1396                 Material *ma;
1397                 for(ma= G.main->mat.first; ma; ma= ma->id.next) {
1398                         if(ma->nodetree) {
1399                                 bNode *node;
1400                                 
1401                                 /* find if group is in tree */
1402                                 for(node= ma->nodetree->nodes.first; node; node= node->next) {
1403                                         if(node->id == (ID *)ntree) {
1404                                                 if(ma->id.lib) lib= 1;
1405                                                 else local= 1;
1406                                         }
1407                                 }
1408                         }
1409                 }
1410         }
1411         else if(ntree->type==NTREE_COMPOSIT) {
1412                 Scene *sce;
1413                 for(sce= G.main->scene.first; sce; sce= sce->id.next) {
1414                         if(sce->nodetree) {
1415                                 bNode *node;
1416                                 
1417                                 /* find if group is in tree */
1418                                 for(node= sce->nodetree->nodes.first; node; node= node->next) {
1419                                         if(node->id == (ID *)ntree) {
1420                                                 if(sce->id.lib) lib= 1;
1421                                                 else local= 1;
1422                                         }
1423                                 }
1424                         }
1425                 }
1426         }
1427         else if(ntree->type==NTREE_TEXTURE) {
1428                 Tex *tx;
1429                 for(tx= G.main->tex.first; tx; tx= tx->id.next) {
1430                         if(tx->nodetree) {
1431                                 bNode *node;
1432                                 
1433                                 /* find if group is in tree */
1434                                 for(node= tx->nodetree->nodes.first; node; node= node->next) {
1435                                         if(node->id == (ID *)ntree) {
1436                                                 if(tx->id.lib) lib= 1;
1437                                                 else local= 1;
1438                                         }
1439                                 }
1440                         }
1441                 }
1442         }
1443         
1444         /* if all users are local, we simply make tree local */
1445         if(local && lib==0) {
1446                 ntree->id.lib= NULL;
1447                 ntree->id.flag= LIB_LOCAL;
1448                 new_id(0, (ID *)ntree, 0);
1449         }
1450         else if(local && lib) {
1451                 /* this is the mixed case, we copy the tree and assign it to local users */
1452                 bNodeTree *newtree= ntreeCopyTree(ntree, 0);
1453                 
1454                 newtree->id.us= 0;
1455                 
1456                 if(ntree->type==NTREE_SHADER) {
1457                         Material *ma;
1458                         for(ma= G.main->mat.first; ma; ma= ma->id.next) {
1459                                 if(ma->nodetree) {
1460                                         bNode *node;
1461                                         
1462                                         /* find if group is in tree */
1463                                         for(node= ma->nodetree->nodes.first; node; node= node->next) {
1464                                                 if(node->id == (ID *)ntree) {
1465                                                         if(ma->id.lib==NULL) {
1466                                                                 node->id= &newtree->id;
1467                                                                 newtree->id.us++;
1468                                                                 ntree->id.us--;
1469                                                         }
1470                                                 }
1471                                         }
1472                                 }
1473                         }
1474                 }
1475                 else if(ntree->type==NTREE_COMPOSIT) {
1476                         Scene *sce;
1477                         for(sce= G.main->scene.first; sce; sce= sce->id.next) {
1478                                 if(sce->nodetree) {
1479                                         bNode *node;
1480                                         
1481                                         /* find if group is in tree */
1482                                         for(node= sce->nodetree->nodes.first; node; node= node->next) {
1483                                                 if(node->id == (ID *)ntree) {
1484                                                         if(sce->id.lib==NULL) {
1485                                                                 node->id= &newtree->id;
1486                                                                 newtree->id.us++;
1487                                                                 ntree->id.us--;
1488                                                         }
1489                                                 }
1490                                         }
1491                                 }
1492                         }
1493                 }
1494                 else if(ntree->type==NTREE_TEXTURE) {
1495                         Tex *tx;
1496                         for(tx= G.main->tex.first; tx; tx= tx->id.next) {
1497                                 if(tx->nodetree) {
1498                                         bNode *node;
1499                                         
1500                                         /* find if group is in tree */
1501                                         for(node= tx->nodetree->nodes.first; node; node= node->next) {
1502                                                 if(node->id == (ID *)ntree) {
1503                                                         if(tx->id.lib==NULL) {
1504                                                                 node->id= &newtree->id;
1505                                                                 newtree->id.us++;
1506                                                                 ntree->id.us--;
1507                                                         }
1508                                                 }
1509                                         }
1510                                 }
1511                         }
1512                 }
1513         }
1514 }
1515
1516
1517 /* ************ find stuff *************** */
1518
1519 static int ntreeHasType(bNodeTree *ntree, int type)
1520 {
1521         bNode *node;
1522         
1523         if(ntree)
1524                 for(node= ntree->nodes.first; node; node= node->next)
1525                         if(node->type == type)
1526                                 return 1;
1527         return 0;
1528 }
1529
1530 bNodeLink *nodeFindLink(bNodeTree *ntree, bNodeSocket *from, bNodeSocket *to)
1531 {
1532         bNodeLink *link;
1533         
1534         for(link= ntree->links.first; link; link= link->next) {
1535                 if(link->fromsock==from && link->tosock==to)
1536                         return link;
1537                 if(link->fromsock==to && link->tosock==from)    /* hrms? */
1538                         return link;
1539         }
1540         return NULL;
1541 }
1542
1543 int nodeCountSocketLinks(bNodeTree *ntree, bNodeSocket *sock)
1544 {
1545         bNodeLink *link;
1546         int tot= 0;
1547         
1548         for(link= ntree->links.first; link; link= link->next) {
1549                 if(link->fromsock==sock || link->tosock==sock)
1550                         tot++;
1551         }
1552         return tot;
1553 }
1554
1555 bNode *nodeGetActive(bNodeTree *ntree)
1556 {
1557         bNode *node;
1558         
1559         if(ntree==NULL) return NULL;
1560         
1561         for(node= ntree->nodes.first; node; node= node->next)
1562                 if(node->flag & NODE_ACTIVE)
1563                         break;
1564         return node;
1565 }
1566
1567 /* two active flags, ID nodes have special flag for buttons display */
1568 bNode *nodeGetActiveID(bNodeTree *ntree, short idtype)
1569 {
1570         bNode *node;
1571         
1572         if(ntree==NULL) return NULL;
1573
1574         /* check for group edit */
1575     for(node= ntree->nodes.first; node; node= node->next)
1576                 if(node->flag & NODE_GROUP_EDIT)
1577                         break;
1578
1579         if(node)
1580                 ntree= (bNodeTree*)node->id;
1581         
1582         /* now find active node with this id */
1583         for(node= ntree->nodes.first; node; node= node->next)
1584                 if(node->id && GS(node->id->name)==idtype)
1585                         if(node->flag & NODE_ACTIVE_ID)
1586                                 break;
1587
1588         return node;
1589 }
1590
1591 int nodeSetActiveID(bNodeTree *ntree, short idtype, ID *id)
1592 {
1593         bNode *node;
1594         int ok= FALSE;
1595
1596         if(ntree==NULL) return ok;
1597
1598         /* check for group edit */
1599     for(node= ntree->nodes.first; node; node= node->next)
1600                 if(node->flag & NODE_GROUP_EDIT)
1601                         break;
1602
1603         if(node)
1604                 ntree= (bNodeTree*)node->id;
1605
1606         /* now find active node with this id */
1607         for(node= ntree->nodes.first; node; node= node->next) {
1608                 if(node->id && GS(node->id->name)==idtype) {
1609                         if(id && ok==FALSE && node->id==id) {
1610                                 node->flag |= NODE_ACTIVE_ID;
1611                                 ok= TRUE;
1612                         } else {
1613                                 node->flag &= ~NODE_ACTIVE_ID;
1614                         }
1615                 }
1616         }
1617
1618         return ok;
1619 }
1620
1621
1622 /* two active flags, ID nodes have special flag for buttons display */
1623 void nodeClearActiveID(bNodeTree *ntree, short idtype)
1624 {
1625         bNode *node;
1626         
1627         if(ntree==NULL) return;
1628         
1629         for(node= ntree->nodes.first; node; node= node->next)
1630                 if(node->id && GS(node->id->name)==idtype)
1631                         node->flag &= ~NODE_ACTIVE_ID;
1632 }
1633
1634 /* two active flags, ID nodes have special flag for buttons display */
1635 void nodeSetActive(bNodeTree *ntree, bNode *node)
1636 {
1637         bNode *tnode;
1638         
1639         /* make sure only one node is active, and only one per ID type */
1640         for(tnode= ntree->nodes.first; tnode; tnode= tnode->next) {
1641                 tnode->flag &= ~NODE_ACTIVE;
1642                 
1643                 if(node->id && tnode->id) {
1644                         if(GS(node->id->name) == GS(tnode->id->name))
1645                                 tnode->flag &= ~NODE_ACTIVE_ID;
1646                 }
1647         }
1648         
1649         node->flag |= NODE_ACTIVE;
1650         if(node->id)
1651                 node->flag |= NODE_ACTIVE_ID;
1652 }
1653
1654 /* use flags are not persistant yet, groups might need different tagging, so we do it each time
1655    when we need to get this info */
1656 void ntreeSocketUseFlags(bNodeTree *ntree)
1657 {
1658         bNode *node;
1659         bNodeSocket *sock;
1660         bNodeLink *link;
1661         
1662         /* clear flags */
1663         for(node= ntree->nodes.first; node; node= node->next) {
1664                 for(sock= node->inputs.first; sock; sock= sock->next)
1665                         sock->flag &= ~SOCK_IN_USE;
1666                 for(sock= node->outputs.first; sock; sock= sock->next)
1667                         sock->flag &= ~SOCK_IN_USE;
1668         }
1669         
1670         /* tag all thats in use */
1671         for(link= ntree->links.first; link; link= link->next) {
1672         
1673                 if(link->fromsock) // FIXME, see below
1674                         link->fromsock->flag |= SOCK_IN_USE;
1675                 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
1676                         link->tosock->flag |= SOCK_IN_USE;
1677         }
1678 }
1679
1680 /* ************** dependency stuff *********** */
1681
1682 /* node is guaranteed to be not checked before */
1683 static int node_recurs_check(bNode *node, bNode ***nsort, int level)
1684 {
1685         bNode *fromnode;
1686         bNodeSocket *sock;
1687         int has_inputlinks= 0;
1688         
1689         node->done= 1;
1690         level++;
1691         
1692         for(sock= node->inputs.first; sock; sock= sock->next) {
1693                 if(sock->link) {
1694                         has_inputlinks= 1;
1695                         fromnode= sock->link->fromnode;
1696                         if(fromnode->done==0) {
1697                                 fromnode->level= node_recurs_check(fromnode, nsort, level);
1698                         }
1699                 }
1700         }
1701 //      printf("node sort %s level %d\n", node->name, level);
1702         **nsort= node;
1703         (*nsort)++;
1704         
1705         if(has_inputlinks)
1706                 return level;
1707         else 
1708                 return 0xFFF;
1709 }
1710
1711 void ntreeSolveOrder(bNodeTree *ntree)
1712 {
1713         bNode *node, **nodesort, **nsort;
1714         bNodeSocket *sock;
1715         bNodeLink *link;
1716         int a, totnode=0;
1717         
1718         /* the solve-order is called on each tree change, so we should be sure no exec can be running */
1719         ntreeEndExecTree(ntree);
1720
1721         /* set links pointers the input sockets, to find dependencies */
1722         /* first clear data */
1723         for(node= ntree->nodes.first; node; node= node->next) {
1724                 node->done= 0;
1725                 totnode++;
1726                 for(sock= node->inputs.first; sock; sock= sock->next)
1727                         sock->link= NULL;
1728         }
1729         if(totnode==0)
1730                 return;
1731         
1732         for(link= ntree->links.first; link; link= link->next) {
1733                 link->tosock->link= link;
1734         }
1735         
1736         nsort= nodesort= MEM_callocN(totnode*sizeof(void *), "sorted node array");
1737         
1738         /* recursive check */
1739         for(node= ntree->nodes.first; node; node= node->next) {
1740                 if(node->done==0) {
1741                         node->level= node_recurs_check(node, &nsort, 0);
1742                 }
1743         }
1744         
1745         /* re-insert nodes in order, first a paranoia check */
1746         for(a=0; a<totnode; a++) {
1747                 if(nodesort[a]==NULL)
1748                         break;
1749         }
1750         if(a<totnode)
1751                 printf("sort error in node tree");
1752         else {
1753                 ntree->nodes.first= ntree->nodes.last= NULL;
1754                 for(a=0; a<totnode; a++)
1755                         BLI_addtail(&ntree->nodes, nodesort[a]);
1756         }
1757         
1758         MEM_freeN(nodesort);
1759         
1760         /* find the active outputs, might become tree type dependant handler */
1761         for(node= ntree->nodes.first; node; node= node->next) {
1762                 if(node->typeinfo->nclass==NODE_CLASS_OUTPUT) {
1763                         bNode *tnode;
1764                         int output= 0;
1765                         
1766                         /* we need a check for which output node should be tagged like this, below an exception */
1767                         if(node->type==CMP_NODE_OUTPUT_FILE)
1768                            continue;
1769                            
1770                         /* there is more types having output class, each one is checked */
1771                         for(tnode= ntree->nodes.first; tnode; tnode= tnode->next) {
1772                                 if(tnode->typeinfo->nclass==NODE_CLASS_OUTPUT) {
1773                                         if(tnode->type==node->type) {
1774                                                 if(tnode->flag & NODE_DO_OUTPUT) {
1775                                                         output++;
1776                                                         if(output>1)
1777                                                                 tnode->flag &= ~NODE_DO_OUTPUT;
1778                                                 }
1779                                         }
1780                                 }
1781                         }
1782                         if(output==0)
1783                                 node->flag |= NODE_DO_OUTPUT;
1784                 }
1785         }
1786         
1787         /* here we could recursively set which nodes have to be done,
1788                 might be different for editor or for "real" use... */
1789 }
1790
1791 /* Should be callback! */
1792 /* Do not call execs here */
1793 void NodeTagChanged(bNodeTree *ntree, bNode *node)
1794 {
1795         if(ntree->type==NTREE_COMPOSIT) {
1796                 bNodeSocket *sock;
1797
1798                 for(sock= node->outputs.first; sock; sock= sock->next) {
1799                         if(sock->ns.data) {
1800                                 //free_compbuf(sock->ns.data);
1801                                 //sock->ns.data= NULL;
1802                         }
1803                 }
1804                 node->need_exec= 1;
1805         }
1806 }
1807
1808 void NodeTagIDChanged(bNodeTree *ntree, ID *id)
1809 {
1810         if(id==NULL)
1811                 return;
1812         
1813         if(ntree->type==NTREE_COMPOSIT) {
1814                 bNode *node;
1815                 
1816                 for(node= ntree->nodes.first; node; node= node->next)
1817                         if(node->id==id)
1818                                 NodeTagChanged(ntree, node);
1819         }
1820 }
1821
1822
1823
1824 /* ******************* executing ************* */
1825
1826 /* see notes at ntreeBeginExecTree */
1827 static void group_node_get_stack(bNode *node, bNodeStack *stack, bNodeStack **in, bNodeStack **out, bNodeStack **gin, bNodeStack **gout)
1828 {
1829         bNodeSocket *sock;
1830         
1831         /* build pointer stack */
1832         for(sock= node->inputs.first; sock; sock= sock->next) {
1833                 if(sock->intern) {
1834                         /* yep, intern can have link or is hidden socket */
1835                         if(sock->link)
1836                                 *(in++)= stack + sock->link->fromsock->stack_index;
1837                         else
1838                                 *(in++)= &sock->ns;
1839                 }
1840                 else
1841                         *(in++)= gin[sock->stack_index_ext];
1842         }
1843         
1844         for(sock= node->outputs.first; sock; sock= sock->next) {
1845                 if(sock->intern)
1846                         *(out++)= stack + sock->stack_index;
1847                 else
1848                         *(out++)= gout[sock->stack_index_ext];
1849         }
1850 }
1851
1852 static void node_group_execute(bNodeStack *stack, void *data, bNode *gnode, bNodeStack **in, bNodeStack **out)
1853 {
1854         bNode *node;
1855         bNodeTree *ntree= (bNodeTree *)gnode->id;
1856         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
1857         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
1858         
1859         if(ntree==NULL) return;
1860         
1861         stack+= gnode->stack_index;
1862                 
1863         for(node= ntree->nodes.first; node; node= node->next) {
1864                 if(node->typeinfo->execfunc) {
1865                         group_node_get_stack(node, stack, nsin, nsout, in, out);
1866                         
1867                         /* for groups, only execute outputs for edited group */
1868                         if(node->typeinfo->nclass==NODE_CLASS_OUTPUT) {
1869                                 if(gnode->flag & NODE_GROUP_EDIT)
1870                                         if(node->flag & NODE_DO_OUTPUT)
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, 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         /* sets need_exec tags in nodes */
2482         totnode= setExecutableNodes(ntree, &thdata);
2483
2484         BLI_init_threads(&threads, exec_composite_node, rd->threads);
2485         
2486         while(rendering) {
2487                 
2488                 if(BLI_available_threads(&threads)) {
2489                         node= getExecutableNode(ntree);
2490                         if(node) {
2491                                 
2492                                 if(ntree->timecursor)
2493                                         ntree->timecursor(ntree->tch, totnode);
2494                                 if(ntree->stats_draw) {
2495                                         char str[64];
2496                                         sprintf(str, "Compositing %d %s", totnode, node->name);
2497                                         ntree->stats_draw(ntree->sdh, str);
2498                                 }
2499                                 totnode--;
2500                                 
2501                                 node->threaddata = &thdata;
2502                                 node->exec= NODE_PROCESSING;
2503                                 BLI_insert_thread(&threads, node);
2504                         }
2505                         else
2506                                 PIL_sleep_ms(50);
2507                 }
2508                 else
2509                         PIL_sleep_ms(50);
2510                 
2511                 rendering= 0;
2512                 /* test for ESC */
2513                 if(ntree->test_break && ntree->test_break(ntree->tbh)) {
2514                         for(node= ntree->nodes.first; node; node= node->next)
2515                                 node->exec |= NODE_READY;
2516                 }
2517                 
2518                 /* check for ready ones, and if we need to continue */
2519                 for(node= ntree->nodes.first; node; node= node->next) {
2520                         if(node->exec & NODE_READY) {
2521                                 if((node->exec & NODE_FINISHED)==0) {
2522                                         BLI_remove_thread(&threads, node); /* this waits for running thread to finish btw */
2523                                         node->exec |= NODE_FINISHED;
2524                                         
2525                                         /* freeing unused buffers */
2526                                         if(rd->scemode & R_COMP_FREE)
2527                                                 freeExecutableNode(ntree);
2528                                 }
2529                         }
2530                         else rendering= 1;
2531                 }
2532         }
2533         
2534         BLI_end_threads(&threads);
2535         
2536         ntreeEndExecTree(ntree);
2537 }
2538
2539
2540 /* ********** copy composite tree entirely, to allow threaded exec ******************* */
2541 /* ***************** do NOT execute this in a thread!               ****************** */
2542
2543 /* returns localized composite tree for execution in threads */
2544 /* local tree then owns all compbufs */
2545 bNodeTree *ntreeLocalize(bNodeTree *ntree)
2546 {
2547         bNodeTree *ltree= ntreeCopyTree(ntree, 0);
2548         bNode *node;
2549         bNodeSocket *sock;
2550         
2551         /* move over the compbufs */
2552         /* right after ntreeCopyTree() oldsock pointers are valid */
2553         for(node= ntree->nodes.first; node; node= node->next) {
2554                 
2555                 /* store new_node pointer to original */
2556                 node->new_node->new_node= node;
2557                 /* ensure new user input gets handled ok */
2558                 node->need_exec= 0;
2559                 
2560                 if(ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER)) {
2561                         if(node->id) {
2562                                 if(node->flag & NODE_DO_OUTPUT)
2563                                         node->new_node->id= (ID *)BKE_image_copy((Image *)node->id);
2564                                 else
2565                                         node->new_node->id= NULL;
2566                         }
2567                 }
2568                 
2569                 for(sock= node->outputs.first; sock; sock= sock->next) {
2570                         
2571                         sock->new_sock->ns.data= sock->ns.data;
2572                         sock->ns.data= NULL;
2573                         sock->new_sock->new_sock= sock;
2574                 }
2575         }
2576         
2577         return ltree;
2578 }
2579
2580 static int node_exists(bNodeTree *ntree, bNode *testnode)
2581 {
2582         bNode *node= ntree->nodes.first;
2583         for(; node; node= node->next)
2584                 if(node==testnode)
2585                         return 1;
2586         return 0;
2587 }
2588
2589 static int outsocket_exists(bNode *node, bNodeSocket *testsock)
2590 {
2591         bNodeSocket *sock= node->outputs.first;
2592         for(; sock; sock= sock->next)
2593                 if(sock==testsock)
2594                         return 1;
2595         return 0;
2596 }
2597
2598
2599 /* sync local composite with real tree */
2600 /* local composite is supposed to be running, be careful moving previews! */
2601 void ntreeLocalSync(bNodeTree *localtree, bNodeTree *ntree)
2602 {
2603         bNode *lnode;
2604         
2605         /* move over the compbufs and previews */
2606         for(lnode= localtree->nodes.first; lnode; lnode= lnode->next) {
2607                 if( (lnode->exec & NODE_READY) && !(lnode->exec & NODE_SKIPPED) ) {
2608                         if(node_exists(ntree, lnode->new_node)) {
2609                                 
2610                                 if(lnode->preview && lnode->preview->rect) {
2611                                         node_free_preview(lnode->new_node);
2612                                         lnode->new_node->preview= lnode->preview;
2613                                         lnode->preview= NULL;
2614                                 }
2615                         }
2616                 }
2617         }
2618 }
2619
2620 /* merge local tree results back, and free local tree */
2621 /* we have to assume the editor already changed completely */
2622 void ntreeLocalMerge(bNodeTree *localtree, bNodeTree *ntree)
2623 {
2624         bNode *lnode;
2625         bNodeSocket *lsock;
2626         
2627         /* move over the compbufs and previews */
2628         for(lnode= localtree->nodes.first; lnode; lnode= lnode->next) {
2629                 if(node_exists(ntree, lnode->new_node)) {
2630                         
2631                         if(lnode->preview && lnode->preview->rect) {
2632                                 node_free_preview(lnode->new_node);
2633                                 lnode->new_node->preview= lnode->preview;
2634                                 lnode->preview= NULL;
2635                         }
2636                         
2637                         if(ELEM(lnode->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER)) {
2638                                 if(lnode->id && (lnode->flag & NODE_DO_OUTPUT)) {
2639                                         /* image_merge does sanity check for pointers */
2640                                         BKE_image_merge((Image *)lnode->new_node->id, (Image *)lnode->id);
2641                                 }
2642                         }
2643                         
2644                         for(lsock= lnode->outputs.first; lsock; lsock= lsock->next) {
2645                                 if(outsocket_exists(lnode->new_node, lsock->new_sock)) {
2646                                         lsock->new_sock->ns.data= lsock->ns.data;
2647                                         lsock->ns.data= NULL;
2648                                                 lsock->new_sock= NULL;
2649                                 }
2650                         }
2651                 }
2652         }
2653         ntreeFreeTree(localtree);
2654         MEM_freeN(localtree);
2655 }
2656
2657 /* *********************************************** */
2658
2659 /* GPU material from shader nodes */
2660
2661 static void gpu_from_node_stack(ListBase *sockets, bNodeStack **ns, GPUNodeStack *gs)
2662 {
2663         bNodeSocket *sock;
2664         int i;
2665
2666         for (sock=sockets->first, i=0; sock; sock=sock->next, i++) {
2667                 memset(&gs[i], 0, sizeof(gs[i]));
2668
2669         QUATCOPY(gs[i].vec, ns[i]->vec);
2670                 gs[i].link= ns[i]->data;
2671
2672                 if (sock->type == SOCK_VALUE)
2673                         gs[i].type= GPU_FLOAT;
2674                 else if (sock->type == SOCK_VECTOR)
2675                         gs[i].type= GPU_VEC3;
2676                 else if (sock->type == SOCK_RGBA)
2677                         gs[i].type= GPU_VEC4;
2678                 else
2679                         gs[i].type= GPU_NONE;
2680
2681                 gs[i].name = "";
2682                 gs[i].hasinput= ns[i]->hasinput && ns[i]->data;
2683                 gs[i].hasoutput= ns[i]->hasinput && ns[i]->data;
2684                 gs[i].sockettype= ns[i]->sockettype;
2685         }
2686
2687         gs[i].type= GPU_NONE;
2688 }
2689
2690 static void data_from_gpu_stack(ListBase *sockets, bNodeStack **ns, GPUNodeStack *gs)
2691 {
2692         bNodeSocket *sock;
2693         int i;
2694
2695         for (sock=sockets->first, i=0; sock; sock=sock->next, i++) {
2696                 ns[i]->data= gs[i].link;
2697                 ns[i]->hasinput= gs[i].hasinput && gs[i].link;
2698                 ns[i]->hasoutput= gs[i].hasoutput;
2699                 ns[i]->sockettype= gs[i].sockettype;
2700         }
2701 }
2702
2703 static void gpu_node_group_execute(bNodeStack *stack, GPUMaterial *mat, bNode *gnode, bNodeStack **in, bNodeStack **out)
2704 {
2705         bNode *node;
2706         bNodeTree *ntree= (bNodeTree *)gnode->id;
2707         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2708         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
2709         GPUNodeStack gpuin[MAX_SOCKET+1], gpuout[MAX_SOCKET+1];
2710         int doit = 0;
2711         
2712         if(ntree==NULL) return;
2713         
2714         stack+= gnode->stack_index;
2715                 
2716         for(node= ntree->nodes.first; node; node= node->next) {
2717                 if(node->typeinfo->gpufunc) {
2718                         group_node_get_stack(node, stack, nsin, nsout, in, out);
2719
2720                         doit = 0;
2721                         
2722                         /* for groups, only execute outputs for edited group */
2723                         if(node->typeinfo->nclass==NODE_CLASS_OUTPUT) {
2724                                 if(gnode->flag & NODE_GROUP_EDIT)
2725                                         if(node->flag & NODE_DO_OUTPUT)
2726                                                 doit = 1;
2727                         }
2728                         else
2729                                 doit = 1;
2730
2731                         if(doit)  {
2732                                 gpu_from_node_stack(&node->inputs, nsin, gpuin);
2733                                 gpu_from_node_stack(&node->outputs, nsout, gpuout);
2734                                 if(node->typeinfo->gpufunc(mat, node, gpuin, gpuout))
2735                                         data_from_gpu_stack(&node->outputs, nsout, gpuout);
2736                         }
2737                 }
2738         }
2739 }
2740
2741 void ntreeGPUMaterialNodes(bNodeTree *ntree, GPUMaterial *mat)
2742 {
2743         bNode *node;
2744         bNodeStack *stack;
2745         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2746         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
2747         GPUNodeStack gpuin[MAX_SOCKET+1], gpuout[MAX_SOCKET+1];
2748
2749         if((ntree->init & NTREE_EXEC_INIT)==0)
2750                 ntreeBeginExecTree(ntree);
2751
2752         stack= ntree->stack;
2753
2754         for(node= ntree->nodes.first; node; node= node->next) {
2755                 if(node->typeinfo->gpufunc) {
2756                         node_get_stack(node, stack, nsin, nsout);
2757                         gpu_from_node_stack(&node->inputs, nsin, gpuin);
2758                         gpu_from_node_stack(&node->outputs, nsout, gpuout);
2759                         if(node->typeinfo->gpufunc(mat, node, gpuin, gpuout))
2760                                 data_from_gpu_stack(&node->outputs, nsout, gpuout);
2761                 }
2762         else if(node->type==NODE_GROUP && node->id) {
2763                         node_get_stack(node, stack, nsin, nsout);
2764                         gpu_node_group_execute(stack, mat, node, nsin, nsout);
2765                 }
2766         }
2767
2768         ntreeEndExecTree(ntree);
2769 }
2770
2771 /* **************** call to switch lamploop for material node ************ */
2772
2773 void (*node_shader_lamp_loop)(struct ShadeInput *, struct ShadeResult *);
2774
2775 void set_node_shader_lamp_loop(void (*lamp_loop_func)(ShadeInput *, ShadeResult *))
2776 {
2777         node_shader_lamp_loop= lamp_loop_func;
2778 }
2779
2780 /* clumsy checking... should do dynamic outputs once */
2781 static void force_hidden_passes(bNode *node, int passflag)
2782 {
2783         bNodeSocket *sock;
2784         
2785         for(sock= node->outputs.first; sock; sock= sock->next)
2786                 sock->flag &= ~SOCK_UNAVAIL;
2787         
2788         sock= BLI_findlink(&node->outputs, RRES_OUT_Z);
2789         if(!(passflag & SCE_PASS_Z)) sock->flag |= SOCK_UNAVAIL;
2790         sock= BLI_findlink(&node->outputs, RRES_OUT_NORMAL);
2791         if(!(passflag & SCE_PASS_NORMAL)) sock->flag |= SOCK_UNAVAIL;
2792         sock= BLI_findlink(&node->outputs, RRES_OUT_VEC);
2793         if(!(passflag & SCE_PASS_VECTOR)) sock->flag |= SOCK_UNAVAIL;
2794         sock= BLI_findlink(&node->outputs, RRES_OUT_UV);
2795         if(!(passflag & SCE_PASS_UV)) sock->flag |= SOCK_UNAVAIL;
2796         sock= BLI_findlink(&node->outputs, RRES_OUT_RGBA);
2797         if(!(passflag & SCE_PASS_RGBA)) sock->flag |= SOCK_UNAVAIL;
2798         sock= BLI_findlink(&node->outputs, RRES_OUT_DIFF);
2799         if(!(passflag & SCE_PASS_DIFFUSE)) sock->flag |= SOCK_UNAVAIL;
2800         sock= BLI_findlink(&node->outputs, RRES_OUT_SPEC);
2801         if(!(passflag & SCE_PASS_SPEC)) sock->flag |= SOCK_UNAVAIL;
2802         sock= BLI_findlink(&node->outputs, RRES_OUT_SHADOW);
2803         if(!(passflag & SCE_PASS_SHADOW)) sock->flag |= SOCK_UNAVAIL;
2804         sock= BLI_findlink(&node->outputs, RRES_OUT_AO);
2805         if(!(passflag & SCE_PASS_AO)) sock->flag |= SOCK_UNAVAIL;
2806         sock= BLI_findlink(&node->outputs, RRES_OUT_REFLECT);
2807         if(!(passflag & SCE_PASS_REFLECT)) sock->flag |= SOCK_UNAVAIL;
2808         sock= BLI_findlink(&node->outputs, RRES_OUT_REFRACT);
2809         if(!(passflag & SCE_PASS_REFRACT)) sock->flag |= SOCK_UNAVAIL;
2810         sock= BLI_findlink(&node->outputs, RRES_OUT_RADIO);
2811         if(!(passflag & SCE_PASS_RADIO)) sock->flag |= SOCK_UNAVAIL;
2812         sock= BLI_findlink(&node->outputs, RRES_OUT_INDEXOB);
2813         if(!(passflag & SCE_PASS_INDEXOB)) sock->flag |= SOCK_UNAVAIL;
2814         sock= BLI_findlink(&node->outputs, RRES_OUT_MIST);
2815         if(!(passflag & SCE_PASS_MIST)) sock->flag |= SOCK_UNAVAIL;
2816         
2817 }
2818
2819 /* based on rules, force sockets hidden always */
2820 void ntreeCompositForceHidden(bNodeTree *ntree, Scene *curscene)
2821 {
2822         bNode *node;
2823         
2824         if(ntree==NULL) return;
2825         
2826         for(node= ntree->nodes.first; node; node= node->next) {
2827                 if( node->type==CMP_NODE_R_LAYERS) {
2828                         Scene *sce= node->id?(Scene *)node->id:curscene;
2829                         SceneRenderLayer *srl= BLI_findlink(&sce->r.layers, node->custom1);
2830                         if(srl)
2831                                 force_hidden_passes(node, srl->passflag);
2832                 }
2833                 else if( node->type==CMP_NODE_IMAGE) {
2834                         Image *ima= (Image *)node->id;
2835                         if(ima) {
2836                                 if(ima->rr) {
2837                                         ImageUser *iuser= node->storage;
2838                                         RenderLayer *rl= BLI_findlink(&ima->rr->layers, iuser->layer);
2839                                         if(rl)
2840                                                 force_hidden_passes(node, rl->passflag);
2841                                         else
2842                                                 force_hidden_passes(node, 0);
2843                                 }
2844                                 else if(ima->type!=IMA_TYPE_MULTILAYER) {       /* if ->rr not yet read we keep inputs */
2845                                         force_hidden_passes(node, RRES_OUT_Z);
2846                                 }
2847                                 else
2848                                         force_hidden_passes(node, 0);
2849                         }
2850                         else
2851                                 force_hidden_passes(node, 0);
2852                 }
2853         }
2854
2855 }
2856
2857 /* called from render pipeline, to tag render input and output */
2858 /* need to do all scenes, to prevent errors when you re-render 1 scene */
2859 void ntreeCompositTagRender(Scene *curscene)
2860 {
2861         Scene *sce;
2862         
2863         for(sce= G.main->scene.first; sce; sce= sce->id.next) {
2864                 if(sce->nodetree) {
2865                         bNode *node;
2866                         
2867                         for(node= sce->nodetree->nodes.first; node; node= node->next) {
2868                                 if(node->id==(ID *)curscene || node->type==CMP_NODE_COMPOSITE)
2869                                         NodeTagChanged(sce->nodetree, node);
2870                         }
2871                 }
2872         }
2873 }
2874
2875 static int node_animation_properties(bNodeTree *ntree, bNode *node)
2876 {
2877         bNodeSocket *sock;
2878         const ListBase *lb;
2879         Link *link;
2880         PointerRNA ptr;
2881         PropertyRNA *prop;
2882         
2883         /* check to see if any of the node's properties have fcurves */
2884         RNA_pointer_create((ID *)ntree, &RNA_Node, node, &ptr);
2885         lb = RNA_struct_defined_properties(ptr.type);
2886         
2887         for (link=lb->first; link; link=link->next) {
2888                 int driven, len=1, index;
2889                 prop = (PropertyRNA *)link;
2890                 
2891                 if (RNA_property_array_check(&ptr, prop))
2892                         len = RNA_property_array_length(&ptr, prop);
2893                 
2894                 for (index=0; index<len; index++) {
2895                         if (rna_get_fcurve(&ptr, prop, index, NULL, &driven)) {
2896                                 NodeTagChanged(ntree, node);
2897                                 return 1;
2898                         }
2899                 }
2900         }
2901         
2902         /* now check node sockets */
2903         for (sock = node->inputs.first; sock; sock=sock->next) {
2904                 int driven, len=1, index;
2905                 
2906                 RNA_pointer_create((ID *)ntree, &RNA_NodeSocket, sock, &ptr);
2907                 prop = RNA_struct_find_property(&ptr, "default_value");
2908                 
2909                 if (RNA_property_array_check(&ptr, prop))
2910                         len = RNA_property_array_length(&ptr, prop);
2911                 
2912                 for (index=0; index<len; index++) {
2913                         if (rna_get_fcurve(&ptr, prop, index, NULL, &driven)) {
2914                                 NodeTagChanged(ntree, node);
2915                                 return 1;
2916                         }
2917                 }
2918         }
2919
2920         return 0;
2921 }
2922
2923 /* tags nodes that have animation capabilities */
2924 int ntreeCompositTagAnimated(bNodeTree *ntree)
2925 {
2926         bNode *node;
2927         int tagged= 0;
2928         
2929         if(ntree==NULL) return 0;
2930         
2931         for(node= ntree->nodes.first; node; node= node->next) {
2932                 
2933                 tagged = node_animation_properties(ntree, node);
2934                 
2935                 /* otherwise always tag these node types */
2936                 if(node->type==CMP_NODE_IMAGE) {
2937                         Image *ima= (Image *)node->id;
2938                         if(ima && ELEM(ima->source, IMA_SRC_MOVIE, IMA_SRC_SEQUENCE)) {
2939                                 NodeTagChanged(ntree, node);
2940                                 tagged= 1;
2941                         }
2942                 }
2943                 else if(node->type==CMP_NODE_TIME) {
2944                         NodeTagChanged(ntree, node);
2945                         tagged= 1;
2946                 }
2947                 else if(node->type==CMP_NODE_R_LAYERS) {
2948                         NodeTagChanged(ntree, node);
2949                         tagged= 1;
2950                 }
2951                 else if(node->type==NODE_GROUP) {
2952                         if( ntreeCompositTagAnimated((bNodeTree *)node->id) ) {
2953                                 NodeTagChanged(ntree, node);
2954                         }
2955                 }
2956         }
2957         
2958         return tagged;
2959 }
2960
2961
2962 /* called from image window preview */
2963 void ntreeCompositTagGenerators(bNodeTree *ntree)
2964 {
2965         bNode *node;
2966         
2967         if(ntree==NULL) return;
2968         
2969         for(node= ntree->nodes.first; node; node= node->next) {
2970                 if( ELEM(node->type, CMP_NODE_R_LAYERS, CMP_NODE_IMAGE))
2971                         NodeTagChanged(ntree, node);
2972         }
2973 }
2974
2975 int ntreeTexTagAnimated(bNodeTree *ntree)
2976 {
2977         bNode *node;
2978         
2979         if(ntree==NULL) return 0;
2980         
2981         for(node= ntree->nodes.first; node; node= node->next) {
2982                 if(node->type==TEX_NODE_CURVE_TIME) {
2983                         NodeTagChanged(ntree, node);
2984                         return 1;
2985                 }
2986                 else if(node->type==NODE_GROUP) {
2987                         if( ntreeTexTagAnimated((bNodeTree *)node->id) ) {
2988                                 return 1;
2989                         }
2990                 }
2991         }
2992         
2993         return 0;
2994 }
2995
2996 /* ************* node definition init ********** */
2997
2998 static bNodeType *is_nodetype_registered(ListBase *typelist, int type, ID *id) 
2999 {
3000         bNodeType *ntype= typelist->first;
3001         
3002         for(;ntype; ntype= ntype->next )
3003                 if(ntype->type==type && ntype->id==id)
3004                         return ntype;
3005         
3006         return NULL;
3007 }
3008
3009 /* type can be from a static array, we make copy for duplicate types (like group) */
3010 void nodeRegisterType(ListBase *typelist, const bNodeType *ntype) 
3011 {
3012         bNodeType *found= is_nodetype_registered(typelist, ntype->type, ntype->id);
3013         
3014         if(found==NULL) {
3015                 bNodeType *ntypen= MEM_callocN(sizeof(bNodeType), "node type");
3016                 *ntypen= *ntype;
3017                 BLI_addtail(typelist, ntypen);
3018         }
3019 }
3020
3021 static void registerCompositNodes(ListBase *ntypelist)
3022 {
3023         nodeRegisterType(ntypelist, &node_group_typeinfo);
3024         nodeRegisterType(ntypelist, &cmp_node_rlayers);
3025         nodeRegisterType(ntypelist, &cmp_node_image);
3026         nodeRegisterType(ntypelist, &cmp_node_texture);
3027         nodeRegisterType(ntypelist, &cmp_node_value);
3028         nodeRegisterType(ntypelist, &cmp_node_rgb);
3029         nodeRegisterType(ntypelist, &cmp_node_curve_time);
3030         
3031         nodeRegisterType(ntypelist, &cmp_node_composite);
3032         nodeRegisterType(ntypelist, &cmp_node_viewer);
3033         nodeRegisterType(ntypelist, &cmp_node_splitviewer);
3034         nodeRegisterType(ntypelist, &cmp_node_output_file);
3035         nodeRegisterType(ntypelist, &cmp_node_view_levels);
3036         
3037         nodeRegisterType(ntypelist, &cmp_node_curve_rgb);
3038         nodeRegisterType(ntypelist, &cmp_node_mix_rgb);
3039         nodeRegisterType(ntypelist, &cmp_node_hue_sat);
3040         nodeRegisterType(ntypelist, &cmp_node_brightcontrast);
3041         nodeRegisterType(ntypelist, &cmp_node_gamma);
3042         nodeRegisterType(ntypelist, &cmp_node_invert);
3043         nodeRegisterType(ntypelist, &cmp_node_alphaover);
3044         nodeRegisterType(ntypelist, &cmp_node_zcombine);
3045         nodeRegisterType(ntypelist, &cmp_node_colorbalance);
3046         nodeRegisterType(ntypelist, &cmp_node_huecorrect);
3047         
3048         nodeRegisterType(ntypelist, &cmp_node_normal);
3049         nodeRegisterType(ntypelist, &cmp_node_curve_vec);
3050         nodeRegisterType(ntypelist, &cmp_node_map_value);
3051         nodeRegisterType(ntypelist, &cmp_node_normalize);
3052         
3053         nodeRegisterType(ntypelist, &cmp_node_filter);
3054         nodeRegisterType(ntypelist, &cmp_node_blur);
3055         nodeRegisterType(ntypelist, &cmp_node_dblur);
3056         nodeRegisterType(ntypelist, &cmp_node_bilateralblur);
3057         nodeRegisterType(ntypelist, &cmp_node_vecblur);
3058         nodeRegisterType(ntypelist, &cmp_node_dilateerode);
3059         nodeRegisterType(ntypelist, &cmp_node_defocus);
3060         
3061         nodeRegisterType(ntypelist, &cmp_node_valtorgb);
3062         nodeRegisterType(ntypelist, &cmp_node_rgbtobw);
3063         nodeRegisterType(ntypelist, &cmp_node_setalpha);
3064         nodeRegisterType(ntypelist, &cmp_node_idmask);
3065         nodeRegisterType(ntypelist, &cmp_node_math);
3066         nodeRegisterType(ntypelist, &cmp_node_seprgba);
3067         nodeRegisterType(ntypelist, &cmp_node_combrgba);
3068         nodeRegisterType(ntypelist, &cmp_node_sephsva);
3069         nodeRegisterType(ntypelist, &cmp_node_combhsva);
3070         nodeRegisterType(ntypelist, &cmp_node_sepyuva);
3071         nodeRegisterType(ntypelist, &cmp_node_combyuva);
3072         nodeRegisterType(ntypelist, &cmp_node_sepycca);
3073         nodeRegisterType(ntypelist, &cmp_node_combycca);
3074         nodeRegisterType(ntypelist, &cmp_node_premulkey);
3075         
3076         nodeRegisterType(ntypelist, &cmp_node_diff_matte);
3077         nodeRegisterType(ntypelist, &cmp_node_distance_matte);
3078         nodeRegisterType(ntypelist, &cmp_node_chroma_matte);
3079         nodeRegisterType(ntypelist, &cmp_node_color_matte);
3080         nodeRegisterType(ntypelist, &cmp_node_channel_matte);
3081         nodeRegisterType(ntypelist, &cmp_node_color_spill);
3082         nodeRegisterType(ntypelist, &cmp_node_luma_matte);
3083         
3084         nodeRegisterType(ntypelist, &cmp_node_translate);
3085         nodeRegisterType(ntypelist, &cmp_node_rotate);
3086         nodeRegisterType(ntypelist, &cmp_node_scale);
3087         nodeRegisterType(ntypelist, &cmp_node_flip);
3088         nodeRegisterType(ntypelist, &cmp_node_crop);
3089         nodeRegisterType(ntypelist, &cmp_node_displace);
3090         nodeRegisterType(ntypelist, &cmp_node_mapuv);
3091         nodeRegisterType(ntypelist, &cmp_node_glare);
3092         nodeRegisterType(ntypelist, &cmp_node_tonemap);
3093         nodeRegisterType(ntypelist, &cmp_node_lensdist);
3094 }
3095
3096 static void registerShaderNodes(ListBase *ntypelist) 
3097 {
3098         nodeRegisterType(ntypelist, &node_group_typeinfo);
3099         nodeRegisterType(ntypelist, &sh_node_output);
3100         nodeRegisterType(ntypelist, &sh_node_mix_rgb);
3101         nodeRegisterType(ntypelist, &sh_node_valtorgb);
3102         nodeRegisterType(ntypelist, &sh_node_rgbtobw);
3103         nodeRegisterType(ntypelist, &sh_node_normal);
3104         nodeRegisterType(ntypelist, &sh_node_geom);
3105         nodeRegisterType(ntypelist, &sh_node_mapping);
3106         nodeRegisterType(ntypelist, &sh_node_curve_vec);
3107         nodeRegisterType(ntypelist, &sh_node_curve_rgb);
3108         nodeRegisterType(ntypelist, &sh_node_math);
3109         nodeRegisterType(ntypelist, &sh_node_vect_math);
3110         nodeRegisterType(ntypelist, &sh_node_squeeze);