Three-in-one commit:
[blender-staging.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., 59 Temple Place - Suite 330, Boston, MA  02111-1307, 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): none yet.
26  *
27  * ***** END GPL LICENSE BLOCK *****
28  */
29
30 #include <stdlib.h>
31 #include <string.h>
32
33 #include "DNA_ID.h"
34 #include "DNA_node_types.h"
35 #include "DNA_material_types.h"
36 #include "DNA_scene_types.h"
37
38 #include "BKE_blender.h"
39 #include "BKE_colortools.h"
40 #include "BKE_global.h"
41 #include "BKE_image.h"
42 #include "BKE_library.h"
43 #include "BKE_main.h"
44 #include "BKE_node.h"
45 #include "BKE_texture.h"
46 #include "BKE_utildefines.h"
47
48 #include "BLI_arithb.h"
49 #include "BLI_blenlib.h"
50 #include "BLI_threads.h"
51
52 #include "PIL_time.h"
53
54 #include "MEM_guardedalloc.h"
55 #include "IMB_imbuf.h"
56
57 /* not very important, but the stack solver likes to know a maximum */
58 #define MAX_SOCKET      64
59
60 #pragma mark /* ************** Type stuff **********  */
61
62 static bNodeType *node_get_type(bNodeTree *ntree, int type, bNodeTree *ngroup)
63 {
64         if(type==NODE_GROUP) {
65                 if(ngroup && GS(ngroup->id.name)==ID_NT) {
66                         return ngroup->owntype;
67                 }
68                 return NULL;
69         }
70         else {
71                 bNodeType **typedefs= ntree->alltypes;
72                 
73                 while( *typedefs && (*typedefs)->type!=type)
74                         typedefs++;
75                 
76                 return *typedefs;
77         }
78 }
79
80 void ntreeInitTypes(bNodeTree *ntree)
81 {
82         bNode *node, *next;
83         
84         if(ntree->type==NTREE_SHADER)
85                 ntree->alltypes= node_all_shaders;
86         else if(ntree->type==NTREE_COMPOSIT)
87                 ntree->alltypes= node_all_composit;
88         else {
89                 ntree->alltypes= NULL;
90                 printf("Error: no type definitions for nodes\n");
91         }
92         
93         for(node= ntree->nodes.first; node; node= next) {
94                 next= node->next;
95                 node->typeinfo= node_get_type(ntree, node->type, (bNodeTree *)node->id);
96                 if(node->typeinfo==NULL) {
97                         printf("Error: Node type %s doesn't exist anymore, removed\n", node->name);
98                         nodeFreeNode(ntree, node);
99                 }
100         }
101                         
102         ntree->init |= NTREE_TYPE_INIT;
103 }
104
105 /* only used internal... we depend on type definitions! */
106 static bNodeSocket *node_add_socket_type(ListBase *lb, bNodeSocketType *stype)
107 {
108         bNodeSocket *sock= MEM_callocN(sizeof(bNodeSocket), "sock");
109         
110         BLI_strncpy(sock->name, stype->name, NODE_MAXSTR);
111         if(stype->limit==0) sock->limit= 0xFFF;
112         else sock->limit= stype->limit;
113         sock->type= stype->type;
114         
115         sock->to_index= stype->own_index;
116         sock->tosock= stype->internsock;
117         
118         sock->ns.vec[0]= stype->val1;
119         sock->ns.vec[1]= stype->val2;
120         sock->ns.vec[2]= stype->val3;
121         sock->ns.vec[3]= stype->val4;
122                                 
123         if(lb)
124                 BLI_addtail(lb, sock);
125         
126         return sock;
127 }
128
129 static void node_rem_socket(bNodeTree *ntree, ListBase *lb, bNodeSocket *sock)
130 {
131         bNodeLink *link, *next;
132         
133         for(link= ntree->links.first; link; link= next) {
134                 next= link->next;
135                 if(link->fromsock==sock || link->tosock==sock) {
136                         nodeRemLink(ntree, link);
137                 }
138         }
139         
140         BLI_remlink(lb, sock);
141         MEM_freeN(sock);
142 }
143
144 static bNodeSocket *verify_socket(ListBase *lb, bNodeSocketType *stype)
145 {
146         bNodeSocket *sock;
147         
148         for(sock= lb->first; sock; sock= sock->next) {
149                 /* both indices are zero for non-groups, otherwise it's a unique index */
150                 if(sock->to_index==stype->own_index)
151                         if(strncmp(sock->name, stype->name, NODE_MAXSTR)==0)
152                                 break;
153         }
154         if(sock) {
155                 sock->type= stype->type;                /* in future, read this from tydefs! */
156                 if(stype->limit==0) sock->limit= 0xFFF;
157                 else sock->limit= stype->limit;
158                 sock->tosock= stype->internsock;
159                 
160                 BLI_remlink(lb, sock);
161                 
162                 return sock;
163         }
164         else {
165                 return node_add_socket_type(NULL, stype);
166         }
167 }
168
169 static void verify_socket_list(bNodeTree *ntree, ListBase *lb, bNodeSocketType *stype_first)
170 {
171         bNodeSocketType *stype;
172         
173         /* no inputs anymore? */
174         if(stype_first==NULL) {
175                 while(lb->first)
176                         node_rem_socket(ntree, lb, lb->first);
177         }
178         else {
179                 /* step by step compare */
180                 stype= stype_first;
181                 while(stype->type != -1) {
182                         stype->sock= verify_socket(lb, stype);
183                         stype++;
184                 }
185                 /* leftovers are removed */
186                 while(lb->first)
187                         node_rem_socket(ntree, lb, lb->first);
188                 /* and we put back the verified sockets */
189                 stype= stype_first;
190                 while(stype->type != -1) {
191                         BLI_addtail(lb, stype->sock);
192                         stype++;
193                 }
194         }
195 }
196
197 void nodeVerifyType(bNodeTree *ntree, bNode *node)
198 {
199         bNodeType *ntype= node->typeinfo;
200         
201         if(ntype) {
202                 /* might add some other verify stuff here */
203                 
204                 verify_socket_list(ntree, &node->inputs, ntype->inputs);
205                 verify_socket_list(ntree, &node->outputs, ntype->outputs);
206         }
207 }
208
209 void ntreeVerifyTypes(bNodeTree *ntree)
210 {
211         bNode *node;
212         
213         if((ntree->init & NTREE_TYPE_INIT)==0)
214                 ntreeInitTypes(ntree);
215         
216         /* check inputs and outputs, and remove or insert them */
217         for(node= ntree->nodes.first; node; node= node->next)
218                 nodeVerifyType(ntree, node);
219         
220 }
221
222 #pragma mark /* ************** Group stuff ********** */
223
224 bNodeType node_group_typeinfo= {
225         /* type code   */       NODE_GROUP,
226         /* name        */       "Group",
227         /* width+range */       120, 60, 200,
228         /* class+opts  */       NODE_CLASS_GROUP, NODE_OPTIONS,
229         /* input sock  */       NULL,
230         /* output sock */       NULL,
231         /* storage     */       "",
232         /* execfunc    */       NULL,
233         
234 };
235
236 /* tag internal sockets */
237 static void group_tag_internal_sockets(bNodeTree *ngroup)
238 {
239         bNode *node;
240         bNodeSocket *sock;
241         bNodeLink *link;
242         
243         /* clear intern tag, but check already for hidden sockets */
244         for(node= ngroup->nodes.first; node; node= node->next) {
245                 for(sock= node->inputs.first; sock; sock= sock->next)
246                         sock->intern= sock->flag & SOCK_HIDDEN;
247                 for(sock= node->outputs.first; sock; sock= sock->next)
248                         sock->intern= sock->flag & SOCK_HIDDEN;
249         }
250         /* set tag */
251         for(link= ngroup->links.first; link; link= link->next) {
252                 link->fromsock->intern= 1;
253                 link->tosock->intern= 1;
254         }
255         
256         /* remove link pointer to external links (only happens on create group) */
257         for(node= ngroup->nodes.first; node; node= node->next) {
258                 for(sock= node->inputs.first; sock; sock= sock->next)
259                         if(sock->intern==0)
260                                 sock->link= NULL;
261         }
262
263         /* set all intern sockets to own_index zero, makes sure that later use won't mixup */
264         for(node= ngroup->nodes.first; node; node= node->next) {
265                 for(sock= node->inputs.first; sock; sock= sock->next)
266                         if(sock->intern)
267                                 sock->own_index= 0;
268                 for(sock= node->outputs.first; sock; sock= sock->next)
269                         if(sock->intern)
270                                 sock->own_index= 0;
271         }
272 }
273
274 /* after editing group, new sockets are zero */
275 /* this routine ensures unique identifiers for zero sockets that are exposed */
276 static void group_verify_own_indices(bNodeTree *ngroup)
277 {
278         bNode *node;
279         bNodeSocket *sock;
280         
281         for(node= ngroup->nodes.first; node; node= node->next) {
282                 for(sock= node->inputs.first; sock; sock= sock->next)
283                         if(sock->own_index==0 && sock->intern==0)
284                                 sock->own_index= ++(ngroup->cur_index);
285                 for(sock= node->outputs.first; sock; sock= sock->next)
286                         if(sock->own_index==0 && sock->intern==0)
287                                 sock->own_index= ++(ngroup->cur_index);
288         }
289         //printf("internal index %d\n", ngroup->cur_index);
290 }
291
292
293 /* nodetrees can be used as groups, so we need typeinfo structs generated */
294 void ntreeMakeOwnType(bNodeTree *ngroup)
295 {
296         bNode *node;
297         bNodeSocket *sock;
298         int totin= 0, totout=0, a;
299
300         /* tags socket when internal linked */
301         group_tag_internal_sockets(ngroup);
302         
303         /* ensure all sockets have own unique id */
304         group_verify_own_indices(ngroup);
305         
306         /* counting stats */
307         for(node= ngroup->nodes.first; node; node= node->next) {
308                 if(node->type==NODE_GROUP)
309                         break;
310                 for(sock= node->inputs.first; sock; sock= sock->next)
311                         if(sock->intern==0) 
312                                 totin++;
313                 for(sock= node->outputs.first; sock; sock= sock->next)
314                         if(sock->intern==0) 
315                                 totout++;
316         }
317         /* debug: nodetrees in nodetrees not handled yet */
318         if(node) {
319                 printf("group in group, not supported yet\n");
320                 return;
321         }
322         
323         /* free own type struct */
324         if(ngroup->owntype) {
325                 if(ngroup->owntype->inputs)
326                         MEM_freeN(ngroup->owntype->inputs);
327                 if(ngroup->owntype->outputs)
328                         MEM_freeN(ngroup->owntype->outputs);
329                 MEM_freeN(ngroup->owntype);
330         }
331         
332         /* make own type struct */
333         ngroup->owntype= MEM_mallocN(sizeof(bNodeType), "group type");
334         *ngroup->owntype= node_group_typeinfo;
335         
336         /* input type arrays */
337         if(totin) {
338                 bNodeSocketType *stype;
339                 bNodeSocketType *inputs= MEM_mallocN(sizeof(bNodeSocketType)*(totin+1), "bNodeSocketType");
340                 a= 0;
341                 
342                 for(node= ngroup->nodes.first; node; node= node->next) {
343                         /* nodes are presumed fully verified, stype and socket list are in sync */
344                         stype= node->typeinfo->inputs;
345                         for(sock= node->inputs.first; sock; sock= sock->next, stype++) {
346                                 if(sock->intern==0) {
347                                         /* debug only print */
348                                         if(stype==NULL || stype->type==-1) printf("group verification error %s\n", ngroup->id.name);
349                                         
350                                         inputs[a]= *stype;
351                                         inputs[a].own_index= sock->own_index;
352                                         inputs[a].internsock= sock;     
353                                         a++;
354                                 }
355                         }
356                 }
357                 inputs[a].type= -1;     /* terminator code */
358                 ngroup->owntype->inputs= inputs;
359         }       
360         
361         /* output type arrays */
362         if(totout) {
363                 bNodeSocketType *stype;
364                 bNodeSocketType *outputs= MEM_mallocN(sizeof(bNodeSocketType)*(totout+1), "bNodeSocketType");
365                 a= 0;
366                 
367                 for(node= ngroup->nodes.first; node; node= node->next) {
368                         /* nodes are presumed fully verified, stype and socket list are in sync */
369                         stype= node->typeinfo->outputs;
370                         for(sock= node->outputs.first; sock; sock= sock->next, stype++) {
371                                 if(sock->intern==0) {
372                                         /* debug only print */
373                                         if(stype==NULL || stype->type==-1) printf("group verification error %s\n", ngroup->id.name);
374                                         
375                                         outputs[a]= *stype;
376                                         outputs[a].own_index= sock->own_index;
377                                         outputs[a].internsock= sock;    
378                                         a++;
379                                 }
380                         }
381                 }
382                 outputs[a].type= -1;    /* terminator code */
383                 ngroup->owntype->outputs= outputs;
384         }
385         
386         /* voila, the nodetree has the full definition for generating group-node instances! */
387 }
388
389
390 static bNodeSocket *groupnode_find_tosock(bNode *gnode, int index)
391 {
392         bNodeSocket *sock;
393         
394         for(sock= gnode->inputs.first; sock; sock= sock->next)
395                 if(sock->to_index==index)
396                         return sock;
397         return NULL;
398 }
399
400 static bNodeSocket *groupnode_find_fromsock(bNode *gnode, int index)
401 {
402         bNodeSocket *sock;
403         
404         for(sock= gnode->outputs.first; sock; sock= sock->next)
405                 if(sock->to_index==index)
406                         return sock;
407         return NULL;
408 }
409
410 bNode *nodeMakeGroupFromSelected(bNodeTree *ntree)
411 {
412         bNodeLink *link, *linkn;
413         bNode *node, *gnode, *nextn;
414         bNodeSocket *sock;
415         bNodeTree *ngroup;
416         float min[2], max[2];
417         int totnode=0;
418         
419         INIT_MINMAX2(min, max);
420         
421         /* is there something to group? also do some clearing */
422         for(node= ntree->nodes.first; node; node= node->next) {
423                 if(node->flag & NODE_SELECT) {
424                         /* no groups in groups */
425                         if(node->type==NODE_GROUP)
426                                 return NULL;
427                         DO_MINMAX2( (&node->locx), min, max);
428                         totnode++;
429                 }
430                 node->done= 0;
431         }
432         if(totnode==0) return NULL;
433         
434         /* check if all connections are OK, no unselected node has both
435                 inputs and outputs to a selection */
436         for(link= ntree->links.first; link; link= link->next) {
437                 if(link->fromnode->flag & NODE_SELECT)
438                         link->tonode->done |= 1;
439                 if(link->tonode->flag & NODE_SELECT)
440                         link->fromnode->done |= 2;
441         }       
442         
443         for(node= ntree->nodes.first; node; node= node->next) {
444                 if((node->flag & NODE_SELECT)==0)
445                         if(node->done==3)
446                                 break;
447         }
448         if(node) 
449                 return NULL;
450         
451         /* OK! new nodetree */
452         ngroup= alloc_libblock(&G.main->nodetree, ID_NT, "NodeGroup");
453         ngroup->type= ntree->type;
454         ngroup->alltypes= ntree->alltypes;
455         
456         /* move nodes over */
457         for(node= ntree->nodes.first; node; node= nextn) {
458                 nextn= node->next;
459                 if(node->flag & NODE_SELECT) {
460                         BLI_remlink(&ntree->nodes, node);
461                         BLI_addtail(&ngroup->nodes, node);
462                         node->locx-= 0.5f*(min[0]+max[0]);
463                         node->locy-= 0.5f*(min[1]+max[1]);
464                 }
465         }
466
467         /* move links over */
468         for(link= ntree->links.first; link; link= linkn) {
469                 linkn= link->next;
470                 if(link->fromnode->flag & link->tonode->flag & NODE_SELECT) {
471                         BLI_remlink(&ntree->links, link);
472                         BLI_addtail(&ngroup->links, link);
473                 }
474         }
475         
476         /* now we can make own group typeinfo */
477         ntreeMakeOwnType(ngroup);
478         
479         /* make group node */
480         gnode= nodeAddNodeType(ntree, NODE_GROUP, ngroup);
481         gnode->locx= 0.5f*(min[0]+max[0]);
482         gnode->locy= 0.5f*(min[1]+max[1]);
483         
484         /* relink external sockets */
485         for(link= ntree->links.first; link; link= linkn) {
486                 linkn= link->next;
487                 
488                 if(link->tonode->flag & NODE_SELECT) {
489                         link->tonode= gnode;
490                         sock= groupnode_find_tosock(gnode, link->tosock->own_index);
491                         if(sock==NULL) {
492                                 nodeRemLink(ntree, link);       
493                                 printf("Removed link, cannot mix internal and external sockets in group\n");
494                         }
495                         else link->tosock= sock;
496                 }
497                 else if(link->fromnode->flag & NODE_SELECT) {
498                         link->fromnode= gnode;
499                         sock= groupnode_find_fromsock(gnode, link->fromsock->own_index);
500                         if(sock==NULL) {
501                                 nodeRemLink(ntree, link);       
502                                 printf("Removed link, cannot mix internal and external sockets in group\n");
503                         }
504                         else link->fromsock= sock;
505                 }
506         }
507         
508         return gnode;
509 }
510
511 /* note: ungroup: group_indices zero! */
512
513 /* here's a nasty little one, need to check users... */
514 /* should become callbackable... */
515 void nodeVerifyGroup(bNodeTree *ngroup)
516 {
517         
518         /* group changed, so we rebuild the type definition */
519         ntreeMakeOwnType(ngroup);
520         
521         if(ngroup->type==NTREE_SHADER) {
522                 Material *ma;
523                 for(ma= G.main->mat.first; ma; ma= ma->id.next) {
524                         if(ma->nodetree) {
525                                 bNode *node;
526                                 
527                                 /* find if group is in tree */
528                                 for(node= ma->nodetree->nodes.first; node; node= node->next)
529                                         if(node->id == (ID *)ngroup)
530                                                 break;
531                                 
532                                 if(node) {
533                                         /* set all type pointers OK */
534                                         ntreeInitTypes(ma->nodetree);
535                                         
536                                         for(node= ma->nodetree->nodes.first; node; node= node->next)
537                                                 if(node->id == (ID *)ngroup)
538                                                         nodeVerifyType(ma->nodetree, node);
539                                 }
540                         }
541                 }
542         }
543         else if(ngroup->type==NTREE_COMPOSIT) {
544                 Scene *sce;
545                 for(sce= G.main->scene.first; sce; sce= sce->id.next) {
546                         if(sce->nodetree) {
547                                 bNode *node;
548                                 
549                                 /* find if group is in tree */
550                                 for(node= sce->nodetree->nodes.first; node; node= node->next)
551                                         if(node->id == (ID *)ngroup)
552                                                 break;
553                                 
554                                 if(node) {
555                                         /* set all type pointers OK */
556                                         ntreeInitTypes(sce->nodetree);
557                                         
558                                         for(node= sce->nodetree->nodes.first; node; node= node->next)
559                                                 if(node->id == (ID *)ngroup)
560                                                         nodeVerifyType(sce->nodetree, node);
561                                 }
562                         }
563                 }
564         }
565 }
566
567 /* also to check all users of groups. Now only used in editor for hide/unhide */
568 /* should become callbackable? */
569 void nodeGroupSocketUseFlags(bNodeTree *ngroup)
570 {
571         bNode *node;
572         bNodeSocket *sock;
573
574         /* clear flags */
575         for(node= ngroup->nodes.first; node; node= node->next) {
576                 for(sock= node->inputs.first; sock; sock= sock->next)
577                         sock->flag &= ~SOCK_IN_USE;
578                 for(sock= node->outputs.first; sock; sock= sock->next)
579                         sock->flag &= ~SOCK_IN_USE;
580         }
581         
582         /* tag all thats in use */
583         if(ngroup->type==NTREE_SHADER) {
584                 Material *ma;
585                 for(ma= G.main->mat.first; ma; ma= ma->id.next) {
586                         if(ma->nodetree) {
587                                 for(node= ma->nodetree->nodes.first; node; node= node->next) {
588                                         if(node->id==(ID *)ngroup) {
589                                                 for(sock= node->inputs.first; sock; sock= sock->next)
590                                                         if(sock->link)
591                                                                 if(sock->tosock) 
592                                                                         sock->tosock->flag |= SOCK_IN_USE;
593                                                 for(sock= node->outputs.first; sock; sock= sock->next)
594                                                         if(nodeCountSocketLinks(ma->nodetree, sock))
595                                                                 if(sock->tosock) 
596                                                                         sock->tosock->flag |= SOCK_IN_USE;
597                                         }
598                                 }
599                         }
600                 }
601         }
602         else if(ngroup->type==NTREE_COMPOSIT) {
603                 Scene *sce;
604                 for(sce= G.main->scene.first; sce; sce= sce->id.next) {
605                         if(sce->nodetree) {
606                                 for(node= sce->nodetree->nodes.first; node; node= node->next) {
607                                         if(node->id==(ID *)ngroup) {
608                                                 for(sock= node->inputs.first; sock; sock= sock->next)
609                                                         if(sock->link)
610                                                                 if(sock->tosock) 
611                                                                         sock->tosock->flag |= SOCK_IN_USE;
612                                                 for(sock= node->outputs.first; sock; sock= sock->next)
613                                                         if(nodeCountSocketLinks(sce->nodetree, sock))
614                                                                 if(sock->tosock) 
615                                                                         sock->tosock->flag |= SOCK_IN_USE;
616                                         }
617                                 }
618                         }
619                 }
620         }
621 }
622
623 static void find_node_with_socket(bNodeTree *ntree, bNodeSocket *sock, bNode **nodep, int *sockindex)
624 {
625         bNode *node;
626         bNodeSocket *tsock;
627         int index;
628         
629         for(node= ntree->nodes.first; node; node= node->next) {
630                 for(index=0, tsock= node->inputs.first; tsock; tsock= tsock->next, index++)
631                         if(tsock==sock)
632                                 break;
633                 if(tsock)
634                         break;
635                 for(index=0, tsock= node->outputs.first; tsock; tsock= tsock->next, index++)
636                         if(tsock==sock)
637                                 break;
638                 if(tsock)
639                         break;
640         }
641         if(node) {
642                 *nodep= node;
643                 *sockindex= index;
644         }
645         else {
646                 *nodep= NULL;
647         }
648 }
649
650 /* returns 1 if its OK */
651 int nodeGroupUnGroup(bNodeTree *ntree, bNode *gnode)
652 {
653         bNodeLink *link, *linkn;
654         bNode *node, *nextn;
655         bNodeTree *ngroup, *wgroup;
656         int index;
657         
658         ngroup= (bNodeTree *)gnode->id;
659         if(ngroup==NULL) return 0;
660         
661         /* clear new pointers, set in copytree */
662         for(node= ntree->nodes.first; node; node= node->next)
663                 node->new= NULL;
664
665         wgroup= ntreeCopyTree(ngroup, 0);
666         
667         /* add the nodes into the ntree */
668         for(node= wgroup->nodes.first; node; node= nextn) {
669                 nextn= node->next;
670                 BLI_remlink(&wgroup->nodes, node);
671                 BLI_addtail(&ntree->nodes, node);
672                 node->locx+= gnode->locx;
673                 node->locy+= gnode->locy;
674                 node->flag |= NODE_SELECT;
675         }
676         /* and the internal links */
677         for(link= wgroup->links.first; link; link= linkn) {
678                 linkn= link->next;
679                 BLI_remlink(&wgroup->links, link);
680                 BLI_addtail(&ntree->links, link);
681         }
682
683         /* restore links to and from the gnode */
684         for(link= ntree->links.first; link; link= link->next) {
685                 if(link->tonode==gnode) {
686                         /* link->tosock->tosock is on the node we look for */
687                         find_node_with_socket(ngroup, link->tosock->tosock, &nextn, &index);
688                         if(nextn==NULL) printf("wrong stuff!\n");
689                         else if(nextn->new==NULL) printf("wrong stuff too!\n");
690                         else {
691                                 link->tonode= nextn->new;
692                                 link->tosock= BLI_findlink(&link->tonode->inputs, index);
693                         }
694                 }
695                 else if(link->fromnode==gnode) {
696                         /* link->fromsock->tosock is on the node we look for */
697                         find_node_with_socket(ngroup, link->fromsock->tosock, &nextn, &index);
698                         if(nextn==NULL) printf("1 wrong stuff!\n");
699                         else if(nextn->new==NULL) printf("1 wrong stuff too!\n");
700                         else {
701                                 link->fromnode= nextn->new;
702                                 link->fromsock= BLI_findlink(&link->fromnode->outputs, index);
703                         }
704                 }
705         }
706         
707         /* remove the gnode & work tree */
708         ntreeFreeTree(wgroup);
709         MEM_freeN(wgroup);
710         
711         nodeFreeNode(ntree, gnode);
712         
713         return 1;
714 }
715
716 #pragma mark /* ************** Add stuff ********** */
717
718 bNode *nodeAddNodeType(bNodeTree *ntree, int type, bNodeTree *ngroup)
719 {
720         bNode *node;
721         bNodeType *ntype= node_get_type(ntree, type, ngroup);
722         bNodeSocketType *stype;
723         
724         node= MEM_callocN(sizeof(bNode), "new node");
725         BLI_addtail(&ntree->nodes, node);
726         node->typeinfo= ntype;
727         
728         BLI_strncpy(node->name, ntype->name, NODE_MAXSTR);
729         node->type= ntype->type;
730         node->flag= NODE_SELECT|ntype->flag;
731         node->width= ntype->width;
732         node->miniwidth= 15.0f;         /* small value only, allows print of first chars */
733         
734         if(type==NODE_GROUP)
735                 node->id= (ID *)ngroup;
736         
737         if(ntype->inputs) {
738                 stype= ntype->inputs;
739                 while(stype->type != -1) {
740                         node_add_socket_type(&node->inputs, stype);
741                         stype++;
742                 }
743         }
744         if(ntype->outputs) {
745                 stype= ntype->outputs;
746                 while(stype->type != -1) {
747                         node_add_socket_type(&node->outputs, stype);
748                         stype++;
749                 }
750         }
751         
752         /* need init handler later? */
753         if(ntree->type==NTREE_SHADER) {
754                 if(type==SH_NODE_MATERIAL)
755                         node->custom1= SH_NODE_MAT_DIFF|SH_NODE_MAT_SPEC;
756                 else if(type==SH_NODE_VALTORGB)
757                         node->storage= add_colorband(1);
758                 else if(type==SH_NODE_MAPPING)
759                         node->storage= add_mapping();
760                 else if(type==SH_NODE_CURVE_VEC)
761                         node->storage= curvemapping_add(3, -1.0f, -1.0f, 1.0f, 1.0f);
762                 else if(type==SH_NODE_CURVE_RGB)
763                         node->storage= curvemapping_add(4, 0.0f, 0.0f, 1.0f, 1.0f);
764         }
765         else if(ntree->type==NTREE_COMPOSIT) {
766                 if(type==CMP_NODE_VALTORGB)
767                         node->storage= add_colorband(1);
768                 else if(type==CMP_NODE_CURVE_VEC)
769                         node->storage= curvemapping_add(3, -1.0f, -1.0f, 1.0f, 1.0f);
770                 else if(type==CMP_NODE_CURVE_RGB)
771                         node->storage= curvemapping_add(4, 0.0f, 0.0f, 1.0f, 1.0f);
772                 else if(type==CMP_NODE_MAP_VALUE)
773                         node->storage= add_mapping();
774         }
775         
776         return node;
777 }
778
779 /* keep socket listorder identical, for copying links */
780 /* ntree is the target tree */
781 bNode *nodeCopyNode(struct bNodeTree *ntree, struct bNode *node)
782 {
783         bNode *nnode= MEM_callocN(sizeof(bNode), "dupli node");
784         bNodeSocket *sock;
785
786         *nnode= *node;
787         BLI_addtail(&ntree->nodes, nnode);
788         
789         duplicatelist(&nnode->inputs, &node->inputs);
790         for(sock= nnode->inputs.first; sock; sock= sock->next)
791                 sock->own_index= 0;
792         
793         duplicatelist(&nnode->outputs, &node->outputs);
794         for(sock= nnode->outputs.first; sock; sock= sock->next) {
795                 sock->own_index= 0;
796                 sock->ns.data= NULL;
797         }
798         
799         if(nnode->id)
800                 nnode->id->us++;
801         
802         if(nnode->storage) {
803                 /* another candidate for handlerizing! */
804                 if(ntree->type==NTREE_SHADER) {
805                         if(node->type==SH_NODE_CURVE_VEC || node->type==SH_NODE_CURVE_RGB)
806                                 nnode->storage= curvemapping_copy(node->storage);
807                         else 
808                                 nnode->storage= MEM_dupallocN(nnode->storage);
809                 }
810                 else if(ntree->type==NTREE_COMPOSIT) {
811                         if(node->type==CMP_NODE_CURVE_VEC || node->type==CMP_NODE_CURVE_RGB)
812                                 nnode->storage= curvemapping_copy(node->storage);
813                         else 
814                                 nnode->storage= MEM_dupallocN(nnode->storage);
815                 }
816                 else 
817                         nnode->storage= MEM_dupallocN(nnode->storage);
818         }
819         
820         node->new= nnode;
821         nnode->new= NULL;
822         nnode->preview= NULL;
823         
824         return nnode;
825 }
826
827 bNodeLink *nodeAddLink(bNodeTree *ntree, bNode *fromnode, bNodeSocket *fromsock, bNode *tonode, bNodeSocket *tosock)
828 {
829         bNodeLink *link= MEM_callocN(sizeof(bNodeLink), "link");
830         
831         BLI_addtail(&ntree->links, link);
832         link->fromnode= fromnode;
833         link->fromsock= fromsock;
834         link->tonode= tonode;
835         link->tosock= tosock;
836         
837         return link;
838 }
839
840 void nodeRemLink(bNodeTree *ntree, bNodeLink *link)
841 {
842         BLI_remlink(&ntree->links, link);
843         if(link->tosock)
844                 link->tosock->link= NULL;
845         MEM_freeN(link);
846 }
847
848
849 bNodeTree *ntreeAddTree(int type)
850 {
851         bNodeTree *ntree= MEM_callocN(sizeof(bNodeTree), "new node tree");
852         ntree->type= type;
853         
854         ntreeInitTypes(ntree);
855         return ntree;
856 }
857
858 #pragma mark /* ************** Free stuff ********** */
859
860 /* goes over entire tree */
861 static void node_unlink_node(bNodeTree *ntree, bNode *node)
862 {
863         bNodeLink *link, *next;
864         bNodeSocket *sock;
865         ListBase *lb;
866         
867         for(link= ntree->links.first; link; link= next) {
868                 next= link->next;
869                 
870                 if(link->fromnode==node) {
871                         lb= &node->outputs;
872                         NodeTagChanged(ntree, link->tonode);
873                 }
874                 else if(link->tonode==node)
875                         lb= &node->inputs;
876                 else
877                         lb= NULL;
878
879                 if(lb) {
880                         for(sock= lb->first; sock; sock= sock->next) {
881                                 if(link->fromsock==sock || link->tosock==sock)
882                                         break;
883                         }
884                         if(sock) {
885                                 nodeRemLink(ntree, link);
886                         }
887                 }
888         }
889 }
890
891 static void composit_free_sockets(bNode *node)
892 {
893         bNodeSocket *sock;
894         
895         for(sock= node->outputs.first; sock; sock= sock->next) {
896                 if(sock->ns.data)
897                         free_compbuf(sock->ns.data);
898         }
899 }
900
901 void nodeFreeNode(bNodeTree *ntree, bNode *node)
902 {
903         node_unlink_node(ntree, node);
904         BLI_remlink(&ntree->nodes, node);
905
906         if(node->id)
907                 node->id->us--;
908         
909         if(ntree->type==NTREE_COMPOSIT)
910                 composit_free_sockets(node);
911         BLI_freelistN(&node->inputs);
912         BLI_freelistN(&node->outputs);
913         
914         if(node->preview) {
915                 if(node->preview->rect)
916                         MEM_freeN(node->preview->rect);
917                 MEM_freeN(node->preview);
918         }
919         if(node->storage) {
920                 /* could be handlerized at some point, now only 1 exception still */
921                 if(ntree->type==NTREE_SHADER) {
922                         if(node->type==SH_NODE_CURVE_VEC || node->type==SH_NODE_CURVE_RGB)
923                                 curvemapping_free(node->storage);
924                         else 
925                                 MEM_freeN(node->storage);
926                 }
927                 else if(ntree->type==NTREE_COMPOSIT) {
928                         if(node->type==CMP_NODE_CURVE_VEC || node->type==CMP_NODE_CURVE_RGB)
929                                 curvemapping_free(node->storage);
930                         else 
931                                 MEM_freeN(node->storage);
932                 }
933                 else 
934                         MEM_freeN(node->storage);
935         }
936         MEM_freeN(node);
937 }
938
939 /* do not free ntree itself here, free_libblock calls this function too */
940 void ntreeFreeTree(bNodeTree *ntree)
941 {
942         bNode *node, *next;
943         
944         if(ntree==NULL) return;
945         
946         BLI_freelistN(&ntree->links);   /* do first, then unlink_node goes fast */
947         
948         for(node= ntree->nodes.first; node; node= next) {
949                 next= node->next;
950                 nodeFreeNode(ntree, node);
951         }
952         
953         if(ntree->owntype) {
954                 if(ntree->owntype->inputs)
955                         MEM_freeN(ntree->owntype->inputs);
956                 if(ntree->owntype->outputs)
957                         MEM_freeN(ntree->owntype->outputs);
958                 MEM_freeN(ntree->owntype);
959         }
960 }
961
962 bNodeTree *ntreeCopyTree(bNodeTree *ntree, int internal_select)
963 {
964         bNodeTree *newtree;
965         bNode *node, *nnode, *last;
966         bNodeLink *link, *nlink;
967         bNodeSocket *sock;
968         int a;
969         
970         if(ntree==NULL) return NULL;
971         
972         if(internal_select==0) {
973                 newtree= MEM_dupallocN(ntree);
974                 newtree->nodes.first= newtree->nodes.last= NULL;
975                 newtree->links.first= newtree->links.last= NULL;
976         }
977         else
978                 newtree= ntree;
979         
980         last= ntree->nodes.last;
981         for(node= ntree->nodes.first; node; node= node->next) {
982                 
983                 node->new= NULL;
984                 if(internal_select==0 || (node->flag & NODE_SELECT)) {
985                         nnode= nodeCopyNode(newtree, node);     /* sets node->new */
986                         if(internal_select) {
987                                 node->flag &= ~NODE_SELECT;
988                                 nnode->flag |= NODE_SELECT;
989                         }
990                         node->flag &= ~NODE_ACTIVE;
991                 }
992                 if(node==last) break;
993         }
994         
995         /* check for copying links */
996         for(link= ntree->links.first; link; link= link->next) {
997                 if(link->fromnode->new && link->tonode->new) {
998                         nlink= nodeAddLink(newtree, link->fromnode->new, NULL, link->tonode->new, NULL);
999                         /* sockets were copied in order */
1000                         for(a=0, sock= link->fromnode->outputs.first; sock; sock= sock->next, a++) {
1001                                 if(sock==link->fromsock)
1002                                         break;
1003                         }
1004                         nlink->fromsock= BLI_findlink(&link->fromnode->new->outputs, a);
1005                         
1006                         for(a=0, sock= link->tonode->inputs.first; sock; sock= sock->next, a++) {
1007                                 if(sock==link->tosock)
1008                                         break;
1009                         }
1010                         nlink->tosock= BLI_findlink(&link->tonode->new->inputs, a);
1011                 }
1012         }
1013         
1014         /* own type definition for group usage */
1015         if(internal_select==0) {
1016                 if(ntree->owntype) {
1017                         newtree->owntype= MEM_dupallocN(ntree->owntype);
1018                         if(ntree->owntype->inputs)
1019                                 newtree->owntype->inputs= MEM_dupallocN(ntree->owntype->inputs);
1020                         if(ntree->owntype->outputs)
1021                                 newtree->owntype->outputs= MEM_dupallocN(ntree->owntype->outputs);
1022                 }
1023         }       
1024         return newtree;
1025 }
1026
1027 #pragma mark /* ************ find stuff *************** */
1028
1029 bNodeLink *nodeFindLink(bNodeTree *ntree, bNodeSocket *from, bNodeSocket *to)
1030 {
1031         bNodeLink *link;
1032         
1033         for(link= ntree->links.first; link; link= link->next) {
1034                 if(link->fromsock==from && link->tosock==to)
1035                         return link;
1036                 if(link->fromsock==to && link->tosock==from)    /* hrms? */
1037                         return link;
1038         }
1039         return NULL;
1040 }
1041
1042 int nodeCountSocketLinks(bNodeTree *ntree, bNodeSocket *sock)
1043 {
1044         bNodeLink *link;
1045         int tot= 0;
1046         
1047         for(link= ntree->links.first; link; link= link->next) {
1048                 if(link->fromsock==sock || link->tosock==sock)
1049                         tot++;
1050         }
1051         return tot;
1052 }
1053
1054 bNode *nodeGetActive(bNodeTree *ntree)
1055 {
1056         bNode *node;
1057         
1058         if(ntree==NULL) return NULL;
1059         
1060         for(node= ntree->nodes.first; node; node= node->next)
1061                 if(node->flag & NODE_ACTIVE)
1062                         break;
1063         return node;
1064 }
1065
1066 /* two active flags, ID nodes have special flag for buttons display */
1067 bNode *nodeGetActiveID(bNodeTree *ntree, short idtype)
1068 {
1069         bNode *node;
1070         
1071         if(ntree==NULL) return NULL;
1072         
1073         for(node= ntree->nodes.first; node; node= node->next)
1074                 if(node->id && GS(node->id->name)==idtype)
1075                         if(node->flag & NODE_ACTIVE_ID)
1076                                 break;
1077         return node;
1078 }
1079
1080 /* two active flags, ID nodes have special flag for buttons display */
1081 void nodeClearActiveID(bNodeTree *ntree, short idtype)
1082 {
1083         bNode *node;
1084         
1085         if(ntree==NULL) return;
1086         
1087         for(node= ntree->nodes.first; node; node= node->next)
1088                 if(node->id && GS(node->id->name)==idtype)
1089                         node->flag &= ~NODE_ACTIVE_ID;
1090 }
1091
1092 /* two active flags, ID nodes have special flag for buttons display */
1093 void nodeSetActive(bNodeTree *ntree, bNode *node)
1094 {
1095         bNode *tnode;
1096         
1097         /* make sure only one node is active, and only one per ID type */
1098         for(tnode= ntree->nodes.first; tnode; tnode= tnode->next) {
1099                 tnode->flag &= ~NODE_ACTIVE;
1100                 
1101                 if(node->id && tnode->id) {
1102                         if(GS(node->id->name) == GS(tnode->id->name))
1103                                 tnode->flag &= ~NODE_ACTIVE_ID;
1104                 }
1105         }
1106         
1107         node->flag |= NODE_ACTIVE;
1108         if(node->id)
1109                 node->flag |= NODE_ACTIVE_ID;
1110 }
1111
1112 /* use flags are not persistant yet, groups might need different tagging, so we do it each time
1113    when we need to get this info */
1114 void ntreeSocketUseFlags(bNodeTree *ntree)
1115 {
1116         bNode *node;
1117         bNodeSocket *sock;
1118         bNodeLink *link;
1119         
1120         /* clear flags */
1121         for(node= ntree->nodes.first; node; node= node->next) {
1122                 for(sock= node->inputs.first; sock; sock= sock->next)
1123                         sock->flag &= ~SOCK_IN_USE;
1124                 for(sock= node->outputs.first; sock; sock= sock->next)
1125                         sock->flag &= ~SOCK_IN_USE;
1126         }
1127         
1128         /* tag all thats in use */
1129         for(link= ntree->links.first; link; link= link->next) {
1130                 link->fromsock->flag |= SOCK_IN_USE;
1131                 link->tosock->flag |= SOCK_IN_USE;
1132         }
1133 }
1134
1135 #pragma mark /* ************** dependency stuff *********** */
1136
1137 /* node is guaranteed to be not checked before */
1138 static int node_recurs_check(bNode *node, bNode ***nsort, int level)
1139 {
1140         bNode *fromnode;
1141         bNodeSocket *sock;
1142         int has_inputlinks= 0;
1143         
1144         node->done= 1;
1145         level++;
1146         
1147         for(sock= node->inputs.first; sock; sock= sock->next) {
1148                 if(sock->link) {
1149                         has_inputlinks= 1;
1150                         fromnode= sock->link->fromnode;
1151                         if(fromnode->done==0) {
1152                                 fromnode->level= node_recurs_check(fromnode, nsort, level);
1153                         }
1154                 }
1155         }
1156 //      printf("node sort %s level %d\n", node->name, level);
1157         **nsort= node;
1158         (*nsort)++;
1159         
1160         if(has_inputlinks)
1161                 return level;
1162         else 
1163                 return 0xFFF;
1164 }
1165
1166 void ntreeSolveOrder(bNodeTree *ntree)
1167 {
1168         bNode *node, **nodesort, **nsort;
1169         bNodeSocket *sock;
1170         bNodeLink *link;
1171         int a, totnode=0;
1172         
1173         /* the solve-order is called on each tree change, so we should be sure no exec can be running */
1174         ntreeEndExecTree(ntree);
1175
1176         /* set links pointers the input sockets, to find dependencies */
1177         /* first clear data */
1178         for(node= ntree->nodes.first; node; node= node->next) {
1179                 node->done= 0;
1180                 totnode++;
1181                 for(sock= node->inputs.first; sock; sock= sock->next)
1182                         sock->link= NULL;
1183         }
1184         if(totnode==0)
1185                 return;
1186         
1187         for(link= ntree->links.first; link; link= link->next) {
1188                 link->tosock->link= link;
1189         }
1190         
1191         nsort= nodesort= MEM_callocN(totnode*sizeof(void *), "sorted node array");
1192         
1193         /* recursive check */
1194         for(node= ntree->nodes.first; node; node= node->next) {
1195                 if(node->done==0) {
1196                         node->level= node_recurs_check(node, &nsort, 0);
1197                 }
1198         }
1199         
1200         /* re-insert nodes in order, first a paranoia check */
1201         for(a=0; a<totnode; a++) {
1202                 if(nodesort[a]==NULL)
1203                         break;
1204         }
1205         if(a<totnode)
1206                 printf("sort error in node tree");
1207         else {
1208                 ntree->nodes.first= ntree->nodes.last= NULL;
1209                 for(a=0; a<totnode; a++)
1210                         BLI_addtail(&ntree->nodes, nodesort[a]);
1211         }
1212         
1213         MEM_freeN(nodesort);
1214         
1215         /* find the active outputs, might become tree type dependant handler */
1216         for(node= ntree->nodes.first; node; node= node->next) {
1217                 if(node->typeinfo->nclass==NODE_CLASS_OUTPUT) {
1218                         bNode *tnode;
1219                         int output= 0;
1220                         /* there is more types having output class, each one is checked */
1221                         for(tnode= ntree->nodes.first; tnode; tnode= tnode->next) {
1222                                 if(tnode->typeinfo->nclass==NODE_CLASS_OUTPUT) {
1223                                         if(tnode->type==node->type) {
1224                                                 if(tnode->flag & NODE_DO_OUTPUT) {
1225                                                         if(output>1)
1226                                                                 tnode->flag &= ~NODE_DO_OUTPUT;
1227                                                         output++;
1228                                                 }
1229                                         }
1230                                 }
1231                         }
1232                         if(output==0)
1233                                 node->flag |= NODE_DO_OUTPUT;
1234                 }
1235         }
1236         
1237         /* here we could recursively set which nodes have to be done,
1238                 might be different for editor or for "real" use... */
1239 }
1240
1241 /* should be callback! */
1242 void NodeTagChanged(bNodeTree *ntree, bNode *node)
1243 {
1244         if(ntree->type==NTREE_COMPOSIT) {
1245                 bNodeSocket *sock;
1246                 
1247                 for(sock= node->outputs.first; sock; sock= sock->next) {
1248                         if(sock->ns.data) {
1249                                 free_compbuf(sock->ns.data);
1250                                 sock->ns.data= NULL;
1251                         }
1252                 }
1253                 node->need_exec= 1;
1254         }
1255 }
1256
1257 #pragma mark /* *************** preview *********** */
1258
1259 /* if node->preview, then we assume the rect to exist */
1260
1261 static void nodeInitPreview(bNode *node, int xsize, int ysize)
1262 {
1263         
1264         if(node->preview==NULL) {
1265                 node->preview= MEM_callocN(sizeof(bNodePreview), "node preview");
1266                 printf("added preview %s\n", node->name);
1267         }
1268         
1269         /* node previews can get added with variable size this way */
1270         if(xsize==0 || ysize==0)
1271                 return;
1272         
1273         /* sanity checks & initialize */
1274         if(node->preview && node->preview->rect) {
1275                 if(node->preview->xsize!=xsize && node->preview->ysize!=ysize) {
1276                         MEM_freeN(node->preview->rect);
1277                         node->preview->rect= NULL;
1278                 }
1279         }
1280         
1281         if(node->preview->rect==NULL) {
1282                 node->preview->rect= MEM_callocN(4*xsize + xsize*ysize*sizeof(float)*4, "node preview rect");
1283                 node->preview->xsize= xsize;
1284                 node->preview->ysize= ysize;
1285         }
1286 }
1287
1288 void ntreeInitPreview(bNodeTree *ntree, int xsize, int ysize)
1289 {
1290         bNode *node;
1291         
1292         if(ntree==NULL)
1293                 return;
1294         
1295         for(node= ntree->nodes.first; node; node= node->next) {
1296                 if(node->typeinfo->flag & NODE_PREVIEW) /* hrms, check for closed nodes? */
1297                         nodeInitPreview(node, xsize, ysize);
1298                 if(node->type==NODE_GROUP && (node->flag & NODE_GROUP_EDIT))
1299                         ntreeInitPreview((bNodeTree *)node->id, xsize, ysize);
1300         }               
1301 }
1302
1303 void nodeAddToPreview(bNode *node, float *col, int x, int y)
1304 {
1305         bNodePreview *preview= node->preview;
1306         if(preview) {
1307                 if(x>=0 && y>=0) {
1308                         if(x<preview->xsize && y<preview->ysize) {
1309                                 float *tar= preview->rect+ 4*((preview->xsize*y) + x);
1310                                 QUATCOPY(tar, col);
1311                         }
1312                         else printf("prv out bound x y %d %d\n", x, y);
1313                 }
1314                 else printf("prv out bound x y %d %d\n", x, y);
1315         }
1316 }
1317
1318
1319
1320 #pragma mark /* ******************* executing ************* */
1321
1322 /* see notes at ntreeBeginExecTree */
1323 static void group_node_get_stack(bNode *node, bNodeStack *stack, bNodeStack **in, bNodeStack **out, bNodeStack **gin, bNodeStack **gout)
1324 {
1325         bNodeSocket *sock;
1326         
1327         /* build pointer stack */
1328         for(sock= node->inputs.first; sock; sock= sock->next) {
1329                 if(sock->intern) {
1330                         /* yep, intern can have link or is hidden socket */
1331                         if(sock->link)
1332                                 *(in++)= stack + sock->link->fromsock->stack_index;
1333                         else
1334                                 *(in++)= &sock->ns;
1335                 }
1336                 else
1337                         *(in++)= gin[sock->stack_index_ext];
1338         }
1339         
1340         for(sock= node->outputs.first; sock; sock= sock->next) {
1341                 if(sock->intern)
1342                         *(out++)= stack + sock->stack_index;
1343                 else
1344                         *(out++)= gout[sock->stack_index_ext];
1345         }
1346 }
1347
1348 static void node_group_execute(bNodeStack *stack, void *data, bNode *gnode, bNodeStack **in, bNodeStack **out)
1349 {
1350         bNode *node;
1351         bNodeTree *ntree= (bNodeTree *)gnode->id;
1352         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
1353         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
1354         
1355         if(ntree==NULL) return;
1356         
1357         stack+= gnode->stack_index;
1358                 
1359         for(node= ntree->nodes.first; node; node= node->next) {
1360                 if(node->typeinfo->execfunc) {
1361                         group_node_get_stack(node, stack, nsin, nsout, in, out);
1362                         node->typeinfo->execfunc(data, node, nsin, nsout);
1363                 }
1364         }
1365 }
1366
1367 /* recursively called for groups */
1368 /* we set all trees on own local indices, but put a total counter
1369    in the groups, so each instance of a group has own stack */
1370 static int ntree_begin_exec_tree(bNodeTree *ntree)
1371 {
1372         bNode *node;
1373         bNodeSocket *sock;
1374         int index= 0, index_in= 0, index_out= 0;
1375         
1376         if((ntree->init & NTREE_TYPE_INIT)==0)
1377                 ntreeInitTypes(ntree);
1378         
1379         /* create indices for stack, check preview */
1380         for(node= ntree->nodes.first; node; node= node->next) {
1381                 
1382                 for(sock= node->inputs.first; sock; sock= sock->next) {
1383                         if(sock->intern==0)
1384                                 sock->stack_index_ext= index_in++;
1385                 }
1386                 
1387                 for(sock= node->outputs.first; sock; sock= sock->next) {
1388                         sock->stack_index= index++;
1389                         if(sock->intern==0)
1390                                 sock->stack_index_ext= index_out++;
1391                 }
1392                 
1393                 if(node->type==NODE_GROUP) {
1394                         if(node->id) {
1395                                 
1396                                 node->stack_index= index;
1397                                 index+= ntree_begin_exec_tree((bNodeTree *)node->id);
1398
1399                                 /* copy internal data from internal nodes to own input sockets */
1400                                 for(sock= node->inputs.first; sock; sock= sock->next) {
1401                                         if(sock->tosock) {
1402                                                 sock->ns= sock->tosock->ns;
1403                                         }
1404                                 }
1405                         }
1406                 }
1407         }
1408         
1409         return index;
1410 }
1411
1412 /* copy socket compbufs to stack */
1413 static void composit_begin_exec(bNodeTree *ntree)
1414 {
1415         bNode *node;
1416         
1417         for(node= ntree->nodes.first; node; node= node->next) {
1418                 bNodeSocket *sock;
1419                 for(sock= node->outputs.first; sock; sock= sock->next) {
1420                         if(sock->ns.data) {
1421                                 bNodeStack *ns= ntree->stack + sock->stack_index;
1422
1423                                 ns->data= sock->ns.data;
1424                                 sock->ns.data= NULL;
1425                         }
1426                 }
1427         }
1428 }
1429
1430 /* copy stack compbufs to sockets */
1431 static void composit_end_exec(bNodeTree *ntree)
1432 {
1433         extern void print_compbuf(char *str, struct CompBuf *cbuf);
1434         bNode *node;
1435         bNodeStack *ns;
1436         int a;
1437         
1438         for(node= ntree->nodes.first; node; node= node->next) {
1439                 bNodeSocket *sock;
1440                 
1441                 for(sock= node->outputs.first; sock; sock= sock->next) {
1442                         ns= ntree->stack + sock->stack_index;
1443                         if(ns->data) {
1444                                 sock->ns.data= ns->data;
1445                                 ns->data= NULL;
1446                         }
1447                 }
1448                 node->need_exec= 0;
1449         }
1450                                 
1451         for(ns= ntree->stack, a=0; a<ntree->stacksize; a++, ns++) {
1452                 if(ns->data) {
1453                         print_compbuf("error: buf hanging in stack", ns->data);
1454                         free_compbuf(ns->data);
1455                 }
1456         }
1457                                 
1458 }
1459
1460 /* stack indices make sure all nodes only write in allocated data, for making it thread safe */
1461 /* only root tree gets the stack, to enable instances to have own stack entries */
1462 /* only two threads now! */
1463 /* per tree (and per group) unique indices are created */
1464 /* the index_ext we need to be able to map from groups to the group-node own stack */
1465
1466 void ntreeBeginExecTree(bNodeTree *ntree)
1467 {
1468         
1469         /* goes recursive over all groups */
1470         ntree->stacksize= ntree_begin_exec_tree(ntree);
1471         
1472         if(ntree->stacksize) {
1473                 bNode *node;
1474                 bNodeStack *ns;
1475                 int a;
1476                 
1477                 /* allocate stack */
1478                 ns=ntree->stack= MEM_callocN(ntree->stacksize*sizeof(bNodeStack), "node stack");
1479                 
1480                 /* tag inputs, the get_stack() gives own socket stackdata if not in use */
1481                 for(a=0; a<ntree->stacksize; a++, ns++) ns->hasinput= 1;
1482                 
1483                 /* tag used outputs, so we know when we can skip operations */
1484                 /* hrms... groups... */
1485                 for(node= ntree->nodes.first; node; node= node->next) {
1486                         bNodeSocket *sock;
1487                         for(sock= node->inputs.first; sock; sock= sock->next) {
1488                                 if(sock->link) {
1489                                         ns= ntree->stack + sock->link->fromsock->stack_index;
1490                                         ns->hasoutput= 1;
1491                                 }
1492                         }
1493                 }
1494                 if(ntree->type==NTREE_COMPOSIT)
1495                         composit_begin_exec(ntree);
1496                 else
1497                         ntree->stack1= MEM_dupallocN(ntree->stack);
1498         }
1499         
1500         ntree->init |= NTREE_EXEC_INIT;
1501 }
1502
1503 void ntreeEndExecTree(bNodeTree *ntree)
1504 {
1505         
1506         if(ntree->init & NTREE_EXEC_INIT) {
1507                 
1508                 /* another callback candidate! */
1509                 if(ntree->type==NTREE_COMPOSIT)
1510                         composit_end_exec(ntree);
1511                 
1512                 if(ntree->stack)
1513                         MEM_freeN(ntree->stack);
1514                 ntree->stack= NULL;
1515                 
1516                 if(ntree->stack1)
1517                         MEM_freeN(ntree->stack1);
1518                 ntree->stack1= NULL;
1519
1520                 ntree->init &= ~NTREE_EXEC_INIT;
1521         }
1522 }
1523
1524 static void node_get_stack(bNode *node, bNodeStack *stack, bNodeStack **in, bNodeStack **out)
1525 {
1526         bNodeSocket *sock;
1527         
1528         /* build pointer stack */
1529         for(sock= node->inputs.first; sock; sock= sock->next) {
1530                 if(sock->link)
1531                         *(in++)= stack + sock->link->fromsock->stack_index;
1532                 else
1533                         *(in++)= &sock->ns;
1534         }
1535         
1536         for(sock= node->outputs.first; sock; sock= sock->next) {
1537                 *(out++)= stack + sock->stack_index;
1538         }
1539 }
1540
1541 /* nodes are presorted, so exec is in order of list */
1542 void ntreeExecTree(bNodeTree *ntree, void *callerdata, int thread)
1543 {
1544         bNode *node;
1545         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
1546         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
1547         bNodeStack *stack;
1548         
1549         /* only when initialized */
1550         if((ntree->init & NTREE_EXEC_INIT)==0)
1551                 ntreeBeginExecTree(ntree);
1552                 
1553         if(thread)
1554                 stack= ntree->stack1;
1555         else
1556                 stack= ntree->stack;
1557         
1558         for(node= ntree->nodes.first; node; node= node->next) {
1559                 if(node->typeinfo->execfunc) {
1560                         node_get_stack(node, stack, nsin, nsout);
1561                         node->typeinfo->execfunc(callerdata, node, nsin, nsout);
1562                 }
1563                 else if(node->type==NODE_GROUP && node->id) {
1564                         node_get_stack(node, stack, nsin, nsout);
1565                         node_group_execute(stack, callerdata, node, nsin, nsout); 
1566                 }
1567         }
1568 }
1569
1570
1571 /* ***************************** threaded version for execute composite nodes ************* */
1572
1573 #define NODE_PROCESSING 1
1574 #define NODE_READY              2
1575 #define NODE_FINISHED   4
1576
1577 /* not changing info, for thread callback */
1578 typedef struct ThreadData {
1579         bNodeStack *stack;
1580         RenderData *rd;
1581 } ThreadData;
1582
1583 static int exec_composite_node(void *node_v)
1584 {
1585         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
1586         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
1587         bNode *node= node_v;
1588         ThreadData *thd= (ThreadData *)node->new;
1589         
1590         node_get_stack(node, thd->stack, nsin, nsout);
1591         
1592         if(node->typeinfo->execfunc) {
1593                 node->typeinfo->execfunc(thd->rd, node, nsin, nsout);
1594         }
1595         else if(node->type==NODE_GROUP && node->id) {
1596                 node_group_execute(thd->stack, thd->rd, node, nsin, nsout); 
1597         }
1598         
1599         node->exec |= NODE_READY;
1600         return 0;
1601 }
1602
1603 /* return total of executable nodes, for timecursor */
1604 static int setExecutableNodes(bNodeTree *ntree, ThreadData *thd)
1605 {
1606         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
1607         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
1608         bNode *node;
1609         bNodeSocket *sock;
1610         int totnode= 0;
1611         
1612         for(node= ntree->nodes.first; node; node= node->next) {
1613                 if(node->typeinfo->execfunc) {
1614                         int a;
1615                         
1616                         node_get_stack(node, thd->stack, nsin, nsout);
1617                         
1618                         /* test the inputs */
1619                         for(a=0, sock= node->inputs.first; sock; sock= sock->next, a++) {
1620                                 /* is sock in use? */
1621                                 if(sock->link) {
1622                                         if(nsin[a]->data==NULL || sock->link->fromnode->need_exec) {
1623                                                 node->need_exec= 1;
1624                                                 break;
1625                                         }
1626                                 }
1627                         }
1628                         
1629                         /* test the outputs */
1630                         for(a=0, sock= node->outputs.first; sock; sock= sock->next, a++) {
1631                                 if(nsout[a]->data==NULL && nsout[a]->hasoutput) {
1632                                         node->need_exec= 1;
1633                                         break;
1634                                 }
1635                         }
1636                         if(node->need_exec) {
1637                                 
1638                                 /* free output buffers */
1639                                 for(a=0, sock= node->outputs.first; sock; sock= sock->next, a++) {
1640                                         if(nsout[a]->data) {
1641                                                 free_compbuf(nsout[a]->data);
1642                                                 nsout[a]->data= NULL;
1643                                         }
1644                                 }
1645                                 totnode++;
1646                                 //printf("node needs exec %s\n", node->name);
1647                                 
1648                                 /* tag for getExecutableNode() */
1649                                 node->exec= 0;
1650                         }
1651                         else
1652                                 /* tag for getExecutableNode() */
1653                                 node->exec= NODE_READY|NODE_FINISHED;
1654                 }
1655         }
1656         return totnode;
1657 }
1658
1659 static bNode *getExecutableNode(bNodeTree *ntree)
1660 {
1661         bNode *node;
1662         bNodeSocket *sock;
1663         
1664         for(node= ntree->nodes.first; node; node= node->next) {
1665                 if(node->exec==0) {
1666                         
1667                         /* input sockets should be ready */
1668                         for(sock= node->inputs.first; sock; sock= sock->next) {
1669                                 if(sock->link)
1670                                         if((sock->link->fromnode->exec & NODE_READY)==0)
1671                                                 break;
1672                         }
1673                         if(sock==NULL) {
1674                                 printf("exec %s\n", node->name);
1675                                 return node;
1676                         }
1677                 }
1678         }
1679         return NULL;
1680 }
1681
1682
1683 /* optimized tree execute test for compositing */
1684 void ntreeCompositExecTree(bNodeTree *ntree, RenderData *rd, int do_preview)
1685 {
1686         bNode *node;
1687         ListBase threads;
1688         ThreadData thdata;
1689         int totnode, maxthreads, rendering= 1;
1690         
1691         if(ntree==NULL) return;
1692         
1693         if(rd->mode & R_THREADS)
1694                 maxthreads= 2;
1695         else
1696                 maxthreads= 1;
1697         
1698         if(do_preview)
1699                 ntreeInitPreview(ntree, 0, 0);
1700         
1701         ntreeBeginExecTree(ntree);
1702         
1703         /* setup callerdata for thread callback */
1704         thdata.rd= rd;
1705         thdata.stack= ntree->stack;
1706         
1707         /* sets need_exec tags in nodes */
1708         totnode= setExecutableNodes(ntree, &thdata);
1709         
1710         BLI_init_threads(&threads, exec_composite_node, maxthreads);
1711         
1712         while(rendering) {
1713                 
1714                 if(BLI_available_threads(&threads)) {
1715                         node= getExecutableNode(ntree);
1716                         if(node) {
1717                                 
1718                                 if(ntree->timecursor)
1719                                         ntree->timecursor(totnode--);
1720                                 
1721                                 node->new = (bNode *)&thdata;
1722                                 node->exec= NODE_PROCESSING;
1723                                 BLI_insert_thread(&threads, node);
1724                         }
1725                 }
1726                 else
1727                         PIL_sleep_ms(50);
1728                 
1729                 /* check for ready ones, and if we need to continue */
1730                 rendering= 0;
1731                 for(node= ntree->nodes.first; node; node= node->next) {
1732                         if(node->exec & NODE_READY) {
1733                                 if((node->exec & NODE_FINISHED)==0) {
1734                                         BLI_remove_thread(&threads, node);
1735                                         node->exec |= NODE_FINISHED;
1736                                 }
1737                         }
1738                         else rendering= 1;
1739                 }
1740         }
1741         
1742         
1743         BLI_end_threads(&threads);
1744         
1745         ntreeEndExecTree(ntree);
1746         
1747         free_unused_animimages();
1748         
1749 }
1750
1751