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