Cycles: svn merge -r36352:36495 https://svn.blender.org/svnroot/bf-blender/trunk...
[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         id_us_plus((ID *)newtree->gpd);
1210
1211         /* in case a running nodetree is copied */
1212         newtree->init &= ~(NTREE_EXEC_INIT);
1213         newtree->threadstack= NULL;
1214         newtree->stack= NULL;
1215         
1216         newtree->nodes.first= newtree->nodes.last= NULL;
1217         newtree->links.first= newtree->links.last= NULL;
1218         
1219         last = ntree->nodes.last;
1220         for(node= ntree->nodes.first; node; node= node->next) {
1221                 node->new_node= NULL;
1222                 nnode= nodeCopyNode(newtree, node);     /* sets node->new */
1223                 if(node==last) break;
1224         }
1225         
1226         /* socket definition for group usage */
1227         BLI_duplicatelist(&newtree->inputs, &ntree->inputs);
1228         for(gsock= newtree->inputs.first, oldgsock= ntree->inputs.first; gsock; gsock=gsock->next, oldgsock=oldgsock->next) {
1229                 oldgsock->new_sock= gsock;
1230                 gsock->groupsock = (oldgsock->groupsock ? oldgsock->groupsock->new_sock : NULL);
1231         }
1232         
1233         BLI_duplicatelist(&newtree->outputs, &ntree->outputs);
1234         for(gsock= newtree->outputs.first, oldgsock= ntree->outputs.first; gsock; gsock=gsock->next, oldgsock=oldgsock->next) {
1235                 oldgsock->new_sock= gsock;
1236                 gsock->groupsock = (oldgsock->groupsock ? oldgsock->groupsock->new_sock : NULL);
1237         }
1238
1239         /* copy links */
1240         BLI_duplicatelist(&newtree->links, &ntree->links);
1241         for(link= newtree->links.first; link; link= link->next) {
1242                 link->fromnode = (link->fromnode ? link->fromnode->new_node : NULL);
1243                 link->fromsock = (link->fromsock ? link->fromsock->new_sock : NULL);
1244                 link->tonode = (link->tonode ? link->tonode->new_node : NULL);
1245                 link->tosock = (link->tosock ? link->tosock->new_sock : NULL);
1246                 /* update the link socket's pointer */
1247                 if (link->tosock)
1248                         link->tosock->link = link;
1249         }
1250
1251         return newtree;
1252 }
1253
1254 /* use when duplicating scenes */
1255 void ntreeSwitchID(bNodeTree *ntree, ID *id_from, ID *id_to)
1256 {
1257         bNode *node;
1258         /* for scene duplication only */
1259         for(node= ntree->nodes.first; node; node= node->next) {
1260                 if(node->id==id_from) {
1261                         node->id= id_to;
1262                 }
1263         }
1264 }
1265
1266 /* *************** preview *********** */
1267 /* if node->preview, then we assume the rect to exist */
1268
1269 static void node_free_preview(bNode *node)
1270 {
1271         if(node->preview) {
1272                 if(node->preview->rect)
1273                         MEM_freeN(node->preview->rect);
1274                 MEM_freeN(node->preview);
1275                 node->preview= NULL;
1276         }       
1277 }
1278
1279 static void node_init_preview(bNode *node, int xsize, int ysize)
1280 {
1281         
1282         if(node->preview==NULL) {
1283                 node->preview= MEM_callocN(sizeof(bNodePreview), "node preview");
1284                 //              printf("added preview %s\n", node->name);
1285         }
1286         
1287         /* node previews can get added with variable size this way */
1288         if(xsize==0 || ysize==0)
1289                 return;
1290         
1291         /* sanity checks & initialize */
1292         if(node->preview->rect) {
1293                 if(node->preview->xsize!=xsize && node->preview->ysize!=ysize) {
1294                         MEM_freeN(node->preview->rect);
1295                         node->preview->rect= NULL;
1296                 }
1297         }
1298         
1299         if(node->preview->rect==NULL) {
1300                 node->preview->rect= MEM_callocN(4*xsize + xsize*ysize*sizeof(char)*4, "node preview rect");
1301                 node->preview->xsize= xsize;
1302                 node->preview->ysize= ysize;
1303         }
1304         /* no clear, makes nicer previews */
1305 }
1306
1307 void ntreeInitPreview(bNodeTree *ntree, int xsize, int ysize)
1308 {
1309         bNode *node;
1310         
1311         if(ntree==NULL)
1312                 return;
1313         
1314         for(node= ntree->nodes.first; node; node= node->next) {
1315                 if(node->typeinfo->flag & NODE_PREVIEW) /* hrms, check for closed nodes? */
1316                         node_init_preview(node, xsize, ysize);
1317                 if(node->type==NODE_GROUP && (node->flag & NODE_GROUP_EDIT))
1318                         ntreeInitPreview((bNodeTree *)node->id, xsize, ysize);
1319         }               
1320 }
1321
1322 static void nodeClearPreview(bNode *node)
1323 {
1324         if(node->preview && node->preview->rect)
1325                 memset(node->preview->rect, 0, MEM_allocN_len(node->preview->rect));
1326 }
1327
1328 /* use it to enforce clear */
1329 void ntreeClearPreview(bNodeTree *ntree)
1330 {
1331         bNode *node;
1332         
1333         if(ntree==NULL)
1334                 return;
1335         
1336         for(node= ntree->nodes.first; node; node= node->next) {
1337                 if(node->typeinfo->flag & NODE_PREVIEW)
1338                         nodeClearPreview(node);
1339                 if(node->type==NODE_GROUP && (node->flag & NODE_GROUP_EDIT))
1340                         ntreeClearPreview((bNodeTree *)node->id);
1341         }               
1342 }
1343
1344 /* hack warning! this function is only used for shader previews, and 
1345 since it gets called multiple times per pixel for Ztransp we only
1346 add the color once. Preview gets cleared before it starts render though */
1347 void nodeAddToPreview(bNode *node, float *col, int x, int y, int do_manage)
1348 {
1349         bNodePreview *preview= node->preview;
1350         if(preview) {
1351                 if(x>=0 && y>=0) {
1352                         if(x<preview->xsize && y<preview->ysize) {
1353                                 unsigned char *tar= preview->rect+ 4*((preview->xsize*y) + x);
1354                                 
1355                                 if(do_manage) {
1356                                         tar[0]= FTOCHAR(linearrgb_to_srgb(col[0]));
1357                                         tar[1]= FTOCHAR(linearrgb_to_srgb(col[1]));
1358                                         tar[2]= FTOCHAR(linearrgb_to_srgb(col[2]));
1359                                 }
1360                                 else {
1361                                         tar[0]= FTOCHAR(col[0]);
1362                                         tar[1]= FTOCHAR(col[1]);
1363                                         tar[2]= FTOCHAR(col[2]);
1364                                 }
1365                                 tar[3]= FTOCHAR(col[3]);
1366                         }
1367                         //else printf("prv out bound x y %d %d\n", x, y);
1368                 }
1369                 //else printf("prv out bound x y %d %d\n", x, y);
1370         }
1371 }
1372
1373
1374 /* ************** Free stuff ********** */
1375
1376 /* goes over entire tree */
1377 void nodeUnlinkNode(bNodeTree *ntree, bNode *node)
1378 {
1379         bNodeLink *link, *next;
1380         bNodeSocket *sock;
1381         ListBase *lb;
1382         
1383         for(link= ntree->links.first; link; link= next) {
1384                 next= link->next;
1385                 
1386                 if(link->fromnode==node) {
1387                         lb= &node->outputs;
1388                         if (link->tonode)
1389                                 NodeTagChanged(ntree, link->tonode);
1390                 }
1391                 else if(link->tonode==node)
1392                         lb= &node->inputs;
1393                 else
1394                         lb= NULL;
1395
1396                 if(lb) {
1397                         for(sock= lb->first; sock; sock= sock->next) {
1398                                 if(link->fromsock==sock || link->tosock==sock)
1399                                         break;
1400                         }
1401                         if(sock) {
1402                                 nodeRemLink(ntree, link);
1403                         }
1404                 }
1405         }
1406 }
1407
1408 static void composit_free_node_cache(bNode *node)
1409 {
1410         bNodeSocket *sock;
1411         
1412         for(sock= node->outputs.first; sock; sock= sock->next) {
1413                 if(sock->ns.data) {
1414                         free_compbuf(sock->ns.data);
1415                         sock->ns.data= NULL;
1416                 }
1417         }
1418 }
1419
1420 void nodeFreeNode(bNodeTree *ntree, bNode *node)
1421 {
1422         nodeUnlinkNode(ntree, node);
1423         BLI_remlink(&ntree->nodes, node);
1424
1425         /* since it is called while free database, node->id is undefined */
1426         
1427         if(ntree->type==NTREE_COMPOSIT)
1428                 composit_free_node_cache(node);
1429         BLI_freelistN(&node->inputs);
1430         BLI_freelistN(&node->outputs);
1431         
1432         node_free_preview(node);
1433
1434         if(node->typeinfo && node->typeinfo->freestoragefunc) {
1435                 node->typeinfo->freestoragefunc(node);
1436         }
1437
1438         MEM_freeN(node);
1439 }
1440
1441 /* do not free ntree itself here, free_libblock calls this function too */
1442 void ntreeFreeTree(bNodeTree *ntree)
1443 {
1444         bNode *node, *next;
1445         
1446         if(ntree==NULL) return;
1447         
1448         ntreeEndExecTree(ntree);        /* checks for if it is still initialized */
1449         
1450         BKE_free_animdata((ID *)ntree);
1451
1452         id_us_min((ID *)ntree->gpd);
1453
1454         BLI_freelistN(&ntree->links);   /* do first, then unlink_node goes fast */
1455         
1456         for(node= ntree->nodes.first; node; node= next) {
1457                 next= node->next;
1458                 nodeFreeNode(ntree, node);
1459         }
1460         
1461         BLI_freelistN(&ntree->inputs);
1462         BLI_freelistN(&ntree->outputs);
1463 }
1464
1465 void ntreeFreeCache(bNodeTree *ntree)
1466 {
1467         bNode *node;
1468         
1469         if(ntree==NULL) return;
1470
1471         if(ntree->type==NTREE_COMPOSIT)
1472                 for(node= ntree->nodes.first; node; node= node->next)
1473                         composit_free_node_cache(node);
1474
1475 }
1476
1477 void ntreeMakeLocal(bNodeTree *ntree)
1478 {
1479         int local=0, lib=0;
1480         
1481         /* - only lib users: do nothing
1482                 * - only local users: set flag
1483                 * - mixed: make copy
1484                 */
1485         
1486         if(ntree->id.lib==NULL) return;
1487         if(ntree->id.us==1) {
1488                 ntree->id.lib= NULL;
1489                 ntree->id.flag= LIB_LOCAL;
1490                 new_id(NULL, (ID *)ntree, NULL);
1491                 return;
1492         }
1493         
1494         /* now check users of groups... again typedepending, callback... */
1495         if(ntree->type==NTREE_SHADER) {
1496                 Material *ma;
1497                 Lamp *la;
1498                 World *wrld;
1499
1500                 for(ma= G.main->mat.first; ma; ma= ma->id.next) {
1501                         if(ma->nodetree) {
1502                                 bNode *node;
1503                                 
1504                                 /* find if group is in tree */
1505                                 for(node= ma->nodetree->nodes.first; node; node= node->next) {
1506                                         if(node->id == (ID *)ntree) {
1507                                                 if(ma->id.lib) lib= 1;
1508                                                 else local= 1;
1509                                         }
1510                                 }
1511                         }
1512                 }
1513
1514                 for(ma= G.main->mat.first; ma; ma= ma->id.next) {
1515                         if(ma->nodetree) {
1516                                 bNode *node;
1517                                 
1518                                 /* find if group is in tree */
1519                                 for(node= ma->nodetree->nodes.first; node; node= node->next) {
1520                                         if(node->id == (ID *)ntree) {
1521                                                 if(ma->id.lib) lib= 1;
1522                                                 else local= 1;
1523                                         }
1524                                 }
1525                         }
1526                 }
1527
1528                 for(la= G.main->lamp.first; la; la= la->id.next) {
1529                         if(la->nodetree) {
1530                                 bNode *node;
1531                                 
1532                                 /* find if group is in tree */
1533                                 for(node= la->nodetree->nodes.first; node; node= node->next) {
1534                                         if(node->id == (ID *)ntree) {
1535                                                 if(la->id.lib) lib= 1;
1536                                                 else local= 1;
1537                                         }
1538                                 }
1539                         }
1540                 }
1541
1542                 for(wrld= G.main->world.first; wrld; wrld= wrld->id.next) {
1543                         if(wrld->nodetree) {
1544                                 bNode *node;
1545                                 
1546                                 /* find if group is in tree */
1547                                 for(node= wrld->nodetree->nodes.first; node; node= node->next) {
1548                                         if(node->id == (ID *)ntree) {
1549                                                 if(wrld->id.lib) lib= 1;
1550                                                 else local= 1;
1551                                         }
1552                                 }
1553                         }
1554                 }
1555         }
1556         else if(ntree->type==NTREE_COMPOSIT) {
1557                 Scene *sce;
1558                 for(sce= G.main->scene.first; sce; sce= sce->id.next) {
1559                         if(sce->nodetree) {
1560                                 bNode *node;
1561                                 
1562                                 /* find if group is in tree */
1563                                 for(node= sce->nodetree->nodes.first; node; node= node->next) {
1564                                         if(node->id == (ID *)ntree) {
1565                                                 if(sce->id.lib) lib= 1;
1566                                                 else local= 1;
1567                                         }
1568                                 }
1569                         }
1570                 }
1571         }
1572         else if(ntree->type==NTREE_TEXTURE) {
1573                 Tex *tx;
1574                 for(tx= G.main->tex.first; tx; tx= tx->id.next) {
1575                         if(tx->nodetree) {
1576                                 bNode *node;
1577                                 
1578                                 /* find if group is in tree */
1579                                 for(node= tx->nodetree->nodes.first; node; node= node->next) {
1580                                         if(node->id == (ID *)ntree) {
1581                                                 if(tx->id.lib) lib= 1;
1582                                                 else local= 1;
1583                                         }
1584                                 }
1585                         }
1586                 }
1587         }
1588         
1589         /* if all users are local, we simply make tree local */
1590         if(local && lib==0) {
1591                 ntree->id.lib= NULL;
1592                 ntree->id.flag= LIB_LOCAL;
1593                 new_id(NULL, (ID *)ntree, NULL);
1594         }
1595         else if(local && lib) {
1596                 /* this is the mixed case, we copy the tree and assign it to local users */
1597                 bNodeTree *newtree= ntreeCopyTree(ntree);
1598                 
1599                 newtree->id.us= 0;
1600                 
1601                 if(ntree->type==NTREE_SHADER) {
1602                         Material *ma;
1603                         Lamp *la;
1604                         World *wrld;
1605
1606                         for(ma= G.main->mat.first; ma; ma= ma->id.next) {
1607                                 if(ma->nodetree) {
1608                                         bNode *node;
1609                                         
1610                                         /* find if group is in tree */
1611                                         for(node= ma->nodetree->nodes.first; node; node= node->next) {
1612                                                 if(node->id == (ID *)ntree) {
1613                                                         if(ma->id.lib==NULL) {
1614                                                                 node->id= &newtree->id;
1615                                                                 newtree->id.us++;
1616                                                                 ntree->id.us--;
1617                                                         }
1618                                                 }
1619                                         }
1620                                 }
1621                         }
1622
1623                         for(la= G.main->lamp.first; la; la= la->id.next) {
1624                                 if(la->nodetree) {
1625                                         bNode *node;
1626                                         
1627                                         /* find if group is in tree */
1628                                         for(node= la->nodetree->nodes.first; node; node= node->next) {
1629                                                 if(node->id == (ID *)ntree) {
1630                                                         if(la->id.lib==NULL) {
1631                                                                 node->id= &newtree->id;
1632                                                                 newtree->id.us++;
1633                                                                 ntree->id.us--;
1634                                                         }
1635                                                 }
1636                                         }
1637                                 }
1638                         }
1639
1640                         for(wrld= G.main->world.first; wrld; wrld= wrld->id.next) {
1641                                 if(wrld->nodetree) {
1642                                         bNode *node;
1643                                         
1644                                         /* find if group is in tree */
1645                                         for(node= wrld->nodetree->nodes.first; node; node= node->next) {
1646                                                 if(node->id == (ID *)ntree) {
1647                                                         if(wrld->id.lib==NULL) {
1648                                                                 node->id= &newtree->id;
1649                                                                 newtree->id.us++;
1650                                                                 ntree->id.us--;
1651                                                         }
1652                                                 }
1653                                         }
1654                                 }
1655                         }
1656                 }
1657                 else if(ntree->type==NTREE_COMPOSIT) {
1658                         Scene *sce;
1659                         for(sce= G.main->scene.first; sce; sce= sce->id.next) {
1660                                 if(sce->nodetree) {
1661                                         bNode *node;
1662                                         
1663                                         /* find if group is in tree */
1664                                         for(node= sce->nodetree->nodes.first; node; node= node->next) {
1665                                                 if(node->id == (ID *)ntree) {
1666                                                         if(sce->id.lib==NULL) {
1667                                                                 node->id= &newtree->id;
1668                                                                 newtree->id.us++;
1669                                                                 ntree->id.us--;
1670                                                         }
1671                                                 }
1672                                         }
1673                                 }
1674                         }
1675                 }
1676                 else if(ntree->type==NTREE_TEXTURE) {
1677                         Tex *tx;
1678                         for(tx= G.main->tex.first; tx; tx= tx->id.next) {
1679                                 if(tx->nodetree) {
1680                                         bNode *node;
1681                                         
1682                                         /* find if group is in tree */
1683                                         for(node= tx->nodetree->nodes.first; node; node= node->next) {
1684                                                 if(node->id == (ID *)ntree) {
1685                                                         if(tx->id.lib==NULL) {
1686                                                                 node->id= &newtree->id;
1687                                                                 newtree->id.us++;
1688                                                                 ntree->id.us--;
1689                                                         }
1690                                                 }
1691                                         }
1692                                 }
1693                         }
1694                 }
1695         }
1696 }
1697
1698
1699 /* ************ find stuff *************** */
1700
1701 static int ntreeHasType(bNodeTree *ntree, int type)
1702 {
1703         bNode *node;
1704         
1705         if(ntree)
1706                 for(node= ntree->nodes.first; node; node= node->next)
1707                         if(node->type == type)
1708                                 return 1;
1709         return 0;
1710 }
1711
1712 bNodeLink *nodeFindLink(bNodeTree *ntree, bNodeSocket *from, bNodeSocket *to)
1713 {
1714         bNodeLink *link;
1715         
1716         for(link= ntree->links.first; link; link= link->next) {
1717                 if(link->fromsock==from && link->tosock==to)
1718                         return link;
1719                 if(link->fromsock==to && link->tosock==from)    /* hrms? */
1720                         return link;
1721         }
1722         return NULL;
1723 }
1724
1725 int nodeCountSocketLinks(bNodeTree *ntree, bNodeSocket *sock)
1726 {
1727         bNodeLink *link;
1728         int tot= 0;
1729         
1730         for(link= ntree->links.first; link; link= link->next) {
1731                 if(link->fromsock==sock || link->tosock==sock)
1732                         tot++;
1733         }
1734         return tot;
1735 }
1736
1737 bNode *nodeGetActive(bNodeTree *ntree)
1738 {
1739         bNode *node;
1740         
1741         if(ntree==NULL) return NULL;
1742         
1743         for(node= ntree->nodes.first; node; node= node->next)
1744                 if(node->flag & NODE_ACTIVE)
1745                         break;
1746         return node;
1747 }
1748
1749 /* two active flags, ID nodes have special flag for buttons display */
1750 bNode *nodeGetActiveID(bNodeTree *ntree, short idtype)
1751 {
1752         bNode *node;
1753         
1754         if(ntree==NULL) return NULL;
1755
1756         /* check for group edit */
1757         for(node= ntree->nodes.first; node; node= node->next)
1758                 if(node->flag & NODE_GROUP_EDIT)
1759                         break;
1760
1761         if(node)
1762                 ntree= (bNodeTree*)node->id;
1763         
1764         /* now find active node with this id */
1765         for(node= ntree->nodes.first; node; node= node->next)
1766                 if(node->id && GS(node->id->name)==idtype)
1767                         if(node->flag & NODE_ACTIVE_ID)
1768                                 break;
1769
1770         return node;
1771 }
1772
1773 int nodeSetActiveID(bNodeTree *ntree, short idtype, ID *id)
1774 {
1775         bNode *node;
1776         int ok= FALSE;
1777
1778         if(ntree==NULL) return ok;
1779
1780         /* check for group edit */
1781         for(node= ntree->nodes.first; node; node= node->next)
1782                 if(node->flag & NODE_GROUP_EDIT)
1783                         break;
1784
1785         if(node)
1786                 ntree= (bNodeTree*)node->id;
1787
1788         /* now find active node with this id */
1789         for(node= ntree->nodes.first; node; node= node->next) {
1790                 if(node->id && GS(node->id->name)==idtype) {
1791                         if(id && ok==FALSE && node->id==id) {
1792                                 node->flag |= NODE_ACTIVE_ID;
1793                                 ok= TRUE;
1794                         } else {
1795                                 node->flag &= ~NODE_ACTIVE_ID;
1796                         }
1797                 }
1798         }
1799
1800         return ok;
1801 }
1802
1803
1804 /* two active flags, ID nodes have special flag for buttons display */
1805 void nodeClearActiveID(bNodeTree *ntree, short idtype)
1806 {
1807         bNode *node;
1808         
1809         if(ntree==NULL) return;
1810         
1811         for(node= ntree->nodes.first; node; node= node->next)
1812                 if(node->id && GS(node->id->name)==idtype)
1813                         node->flag &= ~NODE_ACTIVE_ID;
1814 }
1815
1816 /* two active flags, ID nodes have special flag for buttons display */
1817 void nodeSetActive(bNodeTree *ntree, bNode *node)
1818 {
1819         bNode *tnode;
1820         
1821         /* make sure only one node is active, and only one per ID type */
1822         for(tnode= ntree->nodes.first; tnode; tnode= tnode->next) {
1823                 tnode->flag &= ~NODE_ACTIVE;
1824                 
1825                 if(node->id && tnode->id) {
1826                         if(GS(node->id->name) == GS(tnode->id->name))
1827                                 tnode->flag &= ~NODE_ACTIVE_ID;
1828                 }
1829         }
1830         
1831         node->flag |= NODE_ACTIVE;
1832         if(node->id)
1833                 node->flag |= NODE_ACTIVE_ID;
1834 }
1835
1836 /* use flags are not persistant yet, groups might need different tagging, so we do it each time
1837    when we need to get this info */
1838 void ntreeSocketUseFlags(bNodeTree *ntree)
1839 {
1840         bNode *node;
1841         bNodeSocket *sock;
1842         bNodeLink *link;
1843         
1844         /* clear flags */
1845         for(node= ntree->nodes.first; node; node= node->next) {
1846                 for(sock= node->inputs.first; sock; sock= sock->next)
1847                         sock->flag &= ~SOCK_IN_USE;
1848                 for(sock= node->outputs.first; sock; sock= sock->next)
1849                         sock->flag &= ~SOCK_IN_USE;
1850         }
1851         
1852         /* tag all thats in use */
1853         for(link= ntree->links.first; link; link= link->next) {
1854         
1855                 if(link->fromsock) // FIXME, see below
1856                         link->fromsock->flag |= SOCK_IN_USE;
1857                 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
1858                         link->tosock->flag |= SOCK_IN_USE;
1859         }
1860 }
1861
1862 /* ************** dependency stuff *********** */
1863
1864 /* node is guaranteed to be not checked before */
1865 static int node_recurs_check(bNode *node, bNode ***nsort)
1866 {
1867         bNode *fromnode;
1868         bNodeSocket *sock;
1869         int level = 0xFFF;
1870         
1871         node->done= 1;
1872         
1873         for(sock= node->inputs.first; sock; sock= sock->next) {
1874                 if(sock->link) {
1875                         fromnode= sock->link->fromnode;
1876                         if(fromnode) {
1877                                 if (fromnode->done==0)
1878                                         fromnode->level= node_recurs_check(fromnode, nsort);
1879                                 if (fromnode->level <= level)
1880                                         level = fromnode->level - 1;
1881                         }
1882                 }
1883         }
1884         **nsort= node;
1885         (*nsort)++;
1886         
1887         return level;
1888 }
1889
1890
1891 static void ntreeSetOutput(bNodeTree *ntree)
1892 {
1893         bNode *node;
1894
1895         /* find the active outputs, might become tree type dependant handler */
1896         for(node= ntree->nodes.first; node; node= node->next) {
1897                 if(node->typeinfo->nclass==NODE_CLASS_OUTPUT) {
1898                         bNode *tnode;
1899                         int output= 0;
1900                         
1901                         /* we need a check for which output node should be tagged like this, below an exception */
1902                         if(node->type==CMP_NODE_OUTPUT_FILE)
1903                            continue;
1904                            
1905                         /* there is more types having output class, each one is checked */
1906                         for(tnode= ntree->nodes.first; tnode; tnode= tnode->next) {
1907                                 if(tnode->typeinfo->nclass==NODE_CLASS_OUTPUT) {
1908                                         
1909                                         if(ntree->type==NTREE_COMPOSIT) {
1910                                                         
1911                                                 /* same type, exception for viewer */
1912                                                 if(tnode->type==node->type ||
1913                                                    (ELEM(tnode->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER) &&
1914                                                         ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER))) {
1915                                                         if(tnode->flag & NODE_DO_OUTPUT) {
1916                                                                 output++;
1917                                                                 if(output>1)
1918                                                                         tnode->flag &= ~NODE_DO_OUTPUT;
1919                                                         }
1920                                                 }
1921                                         }
1922                                         else {
1923                                                 /* same type */
1924                                                 if(tnode->type==node->type) {
1925                                                         if(tnode->flag & NODE_DO_OUTPUT) {
1926                                                                 output++;
1927                                                                 if(output>1)
1928                                                                         tnode->flag &= ~NODE_DO_OUTPUT;
1929                                                         }
1930                                                 }
1931                                         }
1932                                 }
1933                         }
1934                         if(output==0)
1935                                 node->flag |= NODE_DO_OUTPUT;
1936                 }
1937         }
1938         
1939         /* here we could recursively set which nodes have to be done,
1940                 might be different for editor or for "real" use... */
1941 }
1942
1943 void ntreeSolveOrder(bNodeTree *ntree)
1944 {
1945         bNode *node, **nodesort, **nsort;
1946         bNodeSocket *sock;
1947         bNodeLink *link;
1948         int a, totnode=0;
1949         
1950         /* the solve-order is called on each tree change, so we should be sure no exec can be running */
1951         ntreeEndExecTree(ntree);
1952
1953         /* set links pointers the input sockets, to find dependencies */
1954         /* first clear data */
1955         for(node= ntree->nodes.first; node; node= node->next) {
1956                 node->done= 0;
1957                 totnode++;
1958                 for(sock= node->inputs.first; sock; sock= sock->next)
1959                         sock->link= NULL;
1960         }
1961         /* clear group socket links */
1962         for(sock= ntree->outputs.first; sock; sock= sock->next)
1963                 sock->link= NULL;
1964         if(totnode==0)
1965                 return;
1966         
1967         for(link= ntree->links.first; link; link= link->next) {
1968                 link->tosock->link= link;
1969         }
1970         
1971         nsort= nodesort= MEM_callocN(totnode*sizeof(void *), "sorted node array");
1972         
1973         /* recursive check */
1974         for(node= ntree->nodes.first; node; node= node->next) {
1975                 if(node->done==0) {
1976                         node->level= node_recurs_check(node, &nsort);
1977                 }
1978         }
1979         
1980         /* re-insert nodes in order, first a paranoia check */
1981         for(a=0; a<totnode; a++) {
1982                 if(nodesort[a]==NULL)
1983                         break;
1984         }
1985         if(a<totnode)
1986                 printf("sort error in node tree");
1987         else {
1988                 ntree->nodes.first= ntree->nodes.last= NULL;
1989                 for(a=0; a<totnode; a++)
1990                         BLI_addtail(&ntree->nodes, nodesort[a]);
1991         }
1992         
1993         MEM_freeN(nodesort);
1994
1995         ntreeSetOutput(ntree);
1996 }
1997
1998
1999 /* Should be callback! */
2000 /* Do not call execs here */
2001 void NodeTagChanged(bNodeTree *ntree, bNode *node)
2002 {
2003         if(ntree->type==NTREE_COMPOSIT) {
2004                 bNodeSocket *sock;
2005
2006                 for(sock= node->outputs.first; sock; sock= sock->next) {
2007                         if(sock->ns.data) {
2008                                 //free_compbuf(sock->ns.data);
2009                                 //sock->ns.data= NULL;
2010                         }
2011                 }
2012                 node->need_exec= 1;
2013         }
2014 }
2015
2016 int NodeTagIDChanged(bNodeTree *ntree, ID *id)
2017 {
2018         int change = FALSE;
2019
2020         if(ELEM(NULL, id, ntree))
2021                 return change;
2022         
2023         if(ntree->type==NTREE_COMPOSIT) {
2024                 bNode *node;
2025                 
2026                 for(node= ntree->nodes.first; node; node= node->next) {
2027                         if(node->id==id) {
2028                                 change= TRUE;
2029                                 NodeTagChanged(ntree, node);
2030                         }
2031                 }
2032         }
2033         
2034         return change;
2035 }
2036
2037
2038
2039 /* ******************* executing ************* */
2040
2041 /* for a given socket, find the actual stack entry */
2042 static bNodeStack *get_socket_stack(bNodeStack *stack, bNodeSocket *sock, bNodeStack **gin)
2043 {
2044         switch (sock->stack_type) {
2045         case SOCK_STACK_LOCAL:
2046                 return stack + sock->stack_index;
2047         case SOCK_STACK_EXTERN:
2048                 return (gin ? gin[sock->stack_index] : NULL);
2049         case SOCK_STACK_CONST:
2050                 return sock->stack_ptr;
2051         }
2052         return NULL;
2053 }
2054
2055 /* see notes at ntreeBeginExecTree */
2056 static void node_get_stack(bNode *node, bNodeStack *stack, bNodeStack **in, bNodeStack **out, bNodeStack **gin)
2057 {
2058         bNodeSocket *sock;
2059         
2060         /* build pointer stack */
2061         if (in) {
2062                 for(sock= node->inputs.first; sock; sock= sock->next) {
2063                         *(in++) = get_socket_stack(stack, sock, gin);
2064                 }
2065         }
2066         
2067         if (out) {
2068                 for(sock= node->outputs.first; sock; sock= sock->next) {
2069                         *(out++) = get_socket_stack(stack, sock, gin);
2070                 }
2071         }
2072 }
2073
2074 static void node_group_execute(bNodeStack *stack, void *data, bNode *gnode, bNodeStack **in)
2075 {
2076         bNode *node;
2077         bNodeTree *ntree= (bNodeTree *)gnode->id;
2078         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2079         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
2080         
2081         if(ntree==NULL) return;
2082         
2083         stack+= gnode->stack_index;
2084                 
2085         for(node= ntree->nodes.first; node; node= node->next) {
2086                 if(node->typeinfo->execfunc) {
2087                         node_get_stack(node, stack, nsin, nsout, in);
2088                         
2089                         /* for groups, only execute outputs for edited group */
2090                         if(node->typeinfo->nclass==NODE_CLASS_OUTPUT) {
2091                                 if(node->type==CMP_NODE_OUTPUT_FILE || (gnode->flag & NODE_GROUP_EDIT))
2092                                         node->typeinfo->execfunc(data, node, nsin, nsout);
2093                         }
2094                         else
2095                                 node->typeinfo->execfunc(data, node, nsin, nsout);
2096                 }
2097         }
2098         
2099         /* free internal buffers */
2100         if (ntree->type==NTREE_COMPOSIT) {
2101                 bNodeSocket *sock;
2102                 bNodeStack *ns;
2103                 
2104                 /* clear hasoutput on all local stack data,
2105                  * only the group output will be used from now on
2106                  */
2107                 for (node=ntree->nodes.first; node; node=node->next) {
2108                         for (sock=node->outputs.first; sock; sock=sock->next) {
2109                                 if (sock->stack_type==SOCK_STACK_LOCAL) {
2110                                         ns= get_socket_stack(stack, sock, in);
2111                                         ns->hasoutput = 0;
2112                                 }
2113                         }
2114                 }
2115                 /* use the hasoutput flag to tag external sockets */
2116                 for (sock=ntree->outputs.first; sock; sock=sock->next) {
2117                         if (sock->stack_type==SOCK_STACK_LOCAL) {
2118                                 ns= get_socket_stack(stack, sock, in);
2119                                 ns->hasoutput = 1;
2120                         }
2121                 }
2122                 /* now free all stacks that are not used from outside */
2123                 for (node=ntree->nodes.first; node; node=node->next) {
2124                         for (sock=node->outputs.first; sock; sock=sock->next) {
2125                                 if (sock->stack_type==SOCK_STACK_LOCAL ) {
2126                                         ns= get_socket_stack(stack, sock, in);
2127                                         if (ns->hasoutput==0 && ns->data) {
2128                                                 free_compbuf(ns->data);
2129                                                 ns->data = NULL;
2130                                         }
2131                                 }
2132                         }
2133                 }
2134         }
2135 }
2136
2137 static int set_stack_indexes_default(bNode *node, int index)
2138 {
2139         bNodeSocket *sock;
2140         
2141         for (sock=node->inputs.first; sock; sock=sock->next) {
2142                 if (sock->link && sock->link->fromsock) {
2143                         sock->stack_type = sock->link->fromsock->stack_type;
2144                         sock->stack_index = sock->link->fromsock->stack_index;
2145                         sock->stack_ptr = sock->link->fromsock->stack_ptr;
2146                 }
2147                 else {
2148                         sock->stack_type = SOCK_STACK_CONST;
2149                         sock->stack_index = -1;
2150                         sock->stack_ptr = &sock->ns;
2151                 }
2152         }
2153         
2154         for (sock=node->outputs.first; sock; sock=sock->next) {
2155                 sock->stack_type = SOCK_STACK_LOCAL;
2156                 sock->stack_index = index++;
2157                 sock->stack_ptr = NULL;
2158         }
2159         
2160         return index;
2161 }
2162
2163 static int ntree_begin_exec_tree(bNodeTree *ntree);
2164 static int set_stack_indexes_group(bNode *node, int index)
2165 {
2166         bNodeTree *ngroup= (bNodeTree*)node->id;
2167         bNodeSocket *sock;
2168         
2169         if((ngroup->init & NTREE_TYPE_INIT)==0)
2170                 ntreeInitTypes(ngroup);
2171         
2172         node->stack_index = index;
2173         index += ntree_begin_exec_tree(ngroup);
2174         
2175         for (sock=node->inputs.first; sock; sock=sock->next) {
2176                 if (sock->link && sock->link->fromsock) {
2177                         sock->stack_type = sock->link->fromsock->stack_type;
2178                         sock->stack_index = sock->link->fromsock->stack_index;
2179                         sock->stack_ptr = sock->link->fromsock->stack_ptr;
2180                 }
2181                 else {
2182                         sock->stack_type = SOCK_STACK_CONST;
2183                         sock->stack_index = -1;
2184                         sock->stack_ptr = &sock->ns;
2185                 }
2186         }
2187         
2188         /* identify group node outputs from internal group sockets */
2189         for(sock= node->outputs.first; sock; sock= sock->next) {
2190                 if (sock->groupsock) {
2191                         bNodeSocket *insock, *gsock = sock->groupsock;
2192                         switch (gsock->stack_type) {
2193                         case SOCK_STACK_EXTERN:
2194                                 /* extern stack is resolved for this group node instance */
2195                                 insock= find_group_node_input(node, gsock->link->fromsock);
2196                                 sock->stack_type = insock->stack_type;
2197                                 sock->stack_index = insock->stack_index;
2198                                 sock->stack_ptr = insock->stack_ptr;
2199                                 break;
2200                         case SOCK_STACK_LOCAL:
2201                                 sock->stack_type = SOCK_STACK_LOCAL;
2202                                 /* local stack index must be offset by group node instance */
2203                                 sock->stack_index = gsock->stack_index + node->stack_index;
2204                                 sock->stack_ptr = NULL;
2205                                 break;
2206                         case SOCK_STACK_CONST:
2207                                 sock->stack_type = SOCK_STACK_CONST;
2208                                 sock->stack_index = -1;
2209                                 sock->stack_ptr = gsock->stack_ptr;
2210                                 break;
2211                         }
2212                 }
2213                 else {
2214                         sock->stack_type = SOCK_STACK_LOCAL;
2215                         sock->stack_index = index++;
2216                         sock->stack_ptr = NULL;
2217                 }
2218         }
2219         
2220         return index;
2221 }
2222
2223 /* recursively called for groups */
2224 /* we set all trees on own local indices, but put a total counter
2225    in the groups, so each instance of a group has own stack */
2226 static int ntree_begin_exec_tree(bNodeTree *ntree)
2227 {
2228         bNode *node;
2229         bNodeSocket *gsock;
2230         int index= 0, i;
2231         
2232         if((ntree->init & NTREE_TYPE_INIT)==0)
2233                 ntreeInitTypes(ntree);
2234         
2235         /* group inputs are numbered 0..totinputs, so external stack can easily be addressed */
2236         i = 0;
2237         for(gsock=ntree->inputs.first; gsock; gsock = gsock->next) {
2238                 gsock->stack_type = SOCK_STACK_EXTERN;
2239                 gsock->stack_index = i++;
2240                 gsock->stack_ptr = NULL;
2241         }
2242         
2243         /* create indices for stack, check preview */
2244         for(node= ntree->nodes.first; node; node= node->next) {
2245                 /* XXX can this be done by a generic one-for-all function?
2246                  * otherwise should use node-type callback.
2247                  */
2248                 if(node->type==NODE_GROUP)
2249                         index = set_stack_indexes_group(node, index);
2250                 else
2251                         index = set_stack_indexes_default(node, index);
2252         }
2253         
2254         /* group outputs */
2255         for(gsock=ntree->outputs.first; gsock; gsock = gsock->next) {
2256                 if (gsock->link && gsock->link->fromsock) {
2257                         gsock->stack_type = gsock->link->fromsock->stack_type;
2258                         gsock->stack_index = gsock->link->fromsock->stack_index;
2259                         gsock->stack_ptr = gsock->link->fromsock->stack_ptr;
2260                 }
2261                 else {
2262                         gsock->stack_type = SOCK_STACK_CONST;
2263                         gsock->stack_index = -1;
2264                         gsock->stack_ptr = &gsock->ns;
2265                 }
2266         }
2267         
2268         return index;
2269 }
2270
2271 /* copy socket compbufs to stack, initialize usage of curve nodes */
2272 static void composit_begin_exec(bNodeTree *ntree, bNodeStack *stack)
2273 {
2274         bNode *node;
2275         bNodeSocket *sock;
2276         
2277         for(node= ntree->nodes.first; node; node= node->next) {
2278                 
2279                 /* initialize needed for groups */
2280                 node->exec= 0;  
2281                 
2282                 for(sock= node->outputs.first; sock; sock= sock->next) {
2283                         bNodeStack *ns= get_socket_stack(stack, sock, NULL);
2284                         if(ns && sock->ns.data) {
2285                                 ns->data= sock->ns.data;
2286                                 sock->ns.data= NULL;
2287                         }
2288                 }
2289                 
2290                 /* cannot initialize them while using in threads */
2291                 if(ELEM4(node->type, CMP_NODE_TIME, CMP_NODE_CURVE_VEC, CMP_NODE_CURVE_RGB, CMP_NODE_HUECORRECT)) {
2292                         curvemapping_initialize(node->storage);
2293                         if(node->type==CMP_NODE_CURVE_RGB)
2294                                 curvemapping_premultiply(node->storage, 0);
2295                 }
2296                 if(node->type==NODE_GROUP)
2297                         composit_begin_exec((bNodeTree *)node->id, stack + node->stack_index);
2298
2299         }
2300 }
2301
2302 /* copy stack compbufs to sockets */
2303 static void composit_end_exec(bNodeTree *ntree, bNodeStack *stack)
2304 {
2305         bNode *node;
2306         bNodeStack *ns;
2307
2308         for(node= ntree->nodes.first; node; node= node->next) {
2309                 bNodeSocket *sock;
2310                 
2311                 for(sock= node->outputs.first; sock; sock= sock->next) {
2312                         ns = get_socket_stack(stack, sock, NULL);
2313                         if(ns && ns->data) {
2314                                 sock->ns.data= ns->data;
2315                                 ns->data= NULL;
2316                         }
2317                 }
2318                 
2319                 if(node->type==CMP_NODE_CURVE_RGB)
2320                         curvemapping_premultiply(node->storage, 1);
2321                 
2322                 if(node->type==NODE_GROUP)
2323                         composit_end_exec((bNodeTree *)node->id, stack + node->stack_index);
2324
2325                 node->need_exec= 0;
2326         }
2327 }
2328
2329 static void group_tag_used_outputs(bNode *gnode, bNodeStack *stack, bNodeStack **gin)
2330 {
2331         bNodeTree *ntree= (bNodeTree *)gnode->id;
2332         bNode *node;
2333         bNodeSocket *sock;
2334         
2335         stack+= gnode->stack_index;
2336         
2337         for(node= ntree->nodes.first; node; node= node->next) {
2338                 if(node->typeinfo->execfunc) {
2339                         for(sock= node->inputs.first; sock; sock= sock->next) {
2340                                 bNodeStack *ns = get_socket_stack(stack, sock, gin);
2341                                 ns->hasoutput= 1;
2342                         }
2343                 }
2344                 
2345                 /* non-composite trees do all nodes by default */
2346                 if (ntree->type!=NTREE_COMPOSIT)
2347                         node->need_exec = 1;
2348                 
2349                 for(sock= node->inputs.first; sock; sock= sock->next) {
2350                         bNodeStack *ns = get_socket_stack(stack, sock, gin);
2351                         if (ns) {
2352                                 ns->hasoutput = 1;
2353                                 
2354                                 /* sock type is needed to detect rgba or value or vector types */
2355                                 if(sock->link && sock->link->fromsock)
2356                                         ns->sockettype= sock->link->fromsock->type;
2357                                 else
2358                                         sock->ns.sockettype= sock->type;
2359                         }
2360                         
2361                         if(sock->link) {
2362                                 bNodeLink *link= sock->link;
2363                                 /* this is the test for a cyclic case */
2364                                 if(link->fromnode && link->tonode) {
2365                                         if(link->fromnode->level >= link->tonode->level && link->tonode->level!=0xFFF);
2366                                         else {
2367                                                 node->need_exec= 0;
2368                                         }
2369                                 }
2370                         }
2371                 }
2372                 
2373                 /* set stack types (for local stack entries) */
2374                 for(sock= node->outputs.first; sock; sock= sock->next) {
2375                         bNodeStack *ns = get_socket_stack(stack, sock, gin);
2376                         if (ns)
2377                                 ns->sockettype = sock->type;
2378                 }
2379         }
2380 }
2381
2382 /* notes below are ancient! (ton) */
2383 /* stack indices make sure all nodes only write in allocated data, for making it thread safe */
2384 /* only root tree gets the stack, to enable instances to have own stack entries */
2385 /* per tree (and per group) unique indices are created */
2386 /* the index_ext we need to be able to map from groups to the group-node own stack */
2387
2388 typedef struct bNodeThreadStack {
2389         struct bNodeThreadStack *next, *prev;
2390         bNodeStack *stack;
2391         int used;
2392 } bNodeThreadStack;
2393
2394 static bNodeThreadStack *ntreeGetThreadStack(bNodeTree *ntree, int thread)
2395 {
2396         ListBase *lb= &ntree->threadstack[thread];
2397         bNodeThreadStack *nts;
2398         
2399         for(nts=lb->first; nts; nts=nts->next) {
2400                 if(!nts->used) {
2401                         nts->used= 1;
2402                         return nts;
2403                 }
2404         }
2405         nts= MEM_callocN(sizeof(bNodeThreadStack), "bNodeThreadStack");
2406         nts->stack= MEM_dupallocN(ntree->stack);
2407         nts->used= 1;
2408         BLI_addtail(lb, nts);
2409
2410         return nts;
2411 }
2412
2413 static void ntreeReleaseThreadStack(bNodeThreadStack *nts)
2414 {
2415         nts->used= 0;
2416 }
2417
2418 /* free texture delegates */
2419 static void tex_end_exec(bNodeTree *ntree)
2420 {
2421         bNodeThreadStack *nts;
2422         bNodeStack *ns;
2423         int th, a;
2424         
2425         if(ntree->threadstack) {
2426                 for(th=0; th<BLENDER_MAX_THREADS; th++) {
2427                         for(nts=ntree->threadstack[th].first; nts; nts=nts->next) {
2428                                 for(ns= nts->stack, a=0; a<ntree->stacksize; a++, ns++) {
2429                                         if(ns->data) {
2430                                                 MEM_freeN(ns->data);
2431                                                 ns->data= NULL;
2432                                         }
2433                                 }
2434                         }
2435                 }
2436         }
2437 }
2438
2439 void ntreeBeginExecTree(bNodeTree *ntree)
2440 {
2441         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2442         
2443         /* let's make it sure */
2444         if(ntree->init & NTREE_EXEC_INIT)
2445                 return;
2446         
2447         /* allocate the thread stack listbase array */
2448         if(ntree->type!=NTREE_COMPOSIT)
2449                 ntree->threadstack= MEM_callocN(BLENDER_MAX_THREADS*sizeof(ListBase), "thread stack array");
2450
2451         /* goes recursive over all groups */
2452         ntree->stacksize= ntree_begin_exec_tree(ntree);
2453
2454         if(ntree->stacksize) {
2455                 bNode *node;
2456                 bNodeStack *ns;
2457                 int a;
2458                 
2459                 /* allocate the base stack */
2460                 ns=ntree->stack= MEM_callocN(ntree->stacksize*sizeof(bNodeStack), "node stack");
2461                 
2462                 /* tag inputs, the get_stack() gives own socket stackdata if not in use */
2463                 for(a=0; a<ntree->stacksize; a++, ns++) ns->hasinput= 1;
2464                 
2465                 /* tag used outputs, so we know when we can skip operations */
2466                 for(node= ntree->nodes.first; node; node= node->next) {
2467                         bNodeSocket *sock;
2468                         
2469                         /* non-composite trees do all nodes by default */
2470                         if(ntree->type!=NTREE_COMPOSIT)
2471                                 node->need_exec= 1;
2472
2473                         for(sock= node->inputs.first; sock; sock= sock->next) {
2474                                 ns = get_socket_stack(ntree->stack, sock, NULL);
2475                                 if (ns) {
2476                                         ns->hasoutput = 1;
2477                                         
2478                                         /* sock type is needed to detect rgba or value or vector types */
2479                                         if(sock->link && sock->link->fromsock)
2480                                                 ns->sockettype= sock->link->fromsock->type;
2481                                         else
2482                                                 sock->ns.sockettype= sock->type;
2483                                 }
2484                                 
2485                                 if(sock->link) {
2486                                         bNodeLink *link= sock->link;
2487                                         /* this is the test for a cyclic case */
2488                                         if(link->fromnode && link->tonode) {
2489                                                 if(link->fromnode->level >= link->tonode->level && link->tonode->level!=0xFFF);
2490                                                 else {
2491                                                         node->need_exec= 0;
2492                                                 }
2493                                         }
2494                                 }
2495                         }
2496                         
2497                         /* set stack types (for local stack entries) */
2498                         for(sock= node->outputs.first; sock; sock= sock->next) {
2499                                 ns = get_socket_stack(ntree->stack, sock, NULL);
2500                                 if (ns)
2501                                         ns->sockettype = sock->type;
2502                         }
2503                         
2504                         if(node->type==NODE_GROUP && node->id) {
2505                                 node_get_stack(node, ntree->stack, nsin, NULL, NULL);
2506                                 group_tag_used_outputs(node, ntree->stack, nsin);
2507                         }
2508                 }
2509                 
2510                 if(ntree->type==NTREE_COMPOSIT)
2511                         composit_begin_exec(ntree, ntree->stack);
2512         }
2513         
2514         ntree->init |= NTREE_EXEC_INIT;
2515 }
2516
2517 void ntreeEndExecTree(bNodeTree *ntree)
2518 {
2519         bNodeStack *ns;
2520         
2521         if(ntree->init & NTREE_EXEC_INIT) {
2522                 bNodeThreadStack *nts;
2523                 int a;
2524                 
2525                 /* another callback candidate! */
2526                 if(ntree->type==NTREE_COMPOSIT) {
2527                         composit_end_exec(ntree, ntree->stack);
2528                         
2529                         for(ns= ntree->stack, a=0; a<ntree->stacksize; a++, ns++) {
2530                                 if(ns->data) {
2531                                         printf("freed leftover buffer from stack\n");
2532                                         free_compbuf(ns->data);
2533                                         ns->data= NULL;
2534                                 }
2535                         }
2536                 }
2537                 else if(ntree->type==NTREE_TEXTURE)
2538                         tex_end_exec(ntree);
2539                 
2540                 if(ntree->stack) {
2541                         MEM_freeN(ntree->stack);
2542                         ntree->stack= NULL;
2543                 }
2544
2545                 if(ntree->threadstack) {
2546                         for(a=0; a<BLENDER_MAX_THREADS; a++) {
2547                                 for(nts=ntree->threadstack[a].first; nts; nts=nts->next)
2548                                         if (nts->stack) MEM_freeN(nts->stack);
2549                                 BLI_freelistN(&ntree->threadstack[a]);
2550                         }
2551
2552                         MEM_freeN(ntree->threadstack);
2553                         ntree->threadstack= NULL;
2554                 }
2555
2556                 ntree->init &= ~NTREE_EXEC_INIT;
2557         }
2558 }
2559
2560 /* nodes are presorted, so exec is in order of list */
2561 void ntreeExecTree(bNodeTree *ntree, void *callerdata, int thread)
2562 {
2563         bNode *node;
2564         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2565         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
2566         bNodeStack *stack;
2567         bNodeThreadStack *nts = NULL;
2568         
2569         /* only when initialized */
2570         if((ntree->init & NTREE_EXEC_INIT)==0)
2571                 ntreeBeginExecTree(ntree);
2572         
2573         /* composite does 1 node per thread, so no multiple stacks needed */
2574         if(ntree->type==NTREE_COMPOSIT) {
2575                 stack= ntree->stack;
2576         }
2577         else {
2578                 nts= ntreeGetThreadStack(ntree, thread);
2579                 stack= nts->stack;
2580         }
2581         
2582         for(node= ntree->nodes.first; node; node= node->next) {
2583                 if(node->need_exec) {
2584                         if(node->typeinfo->execfunc) {
2585                                 node_get_stack(node, stack, nsin, nsout, NULL);
2586                                 node->typeinfo->execfunc(callerdata, node, nsin, nsout);
2587                         }
2588                         else if(node->type==NODE_GROUP && node->id) {
2589                                 node_get_stack(node, stack, nsin, NULL, NULL);
2590                                 node_group_execute(stack, callerdata, node, nsin);
2591                         }
2592                 }
2593         }
2594
2595         if(nts)
2596                 ntreeReleaseThreadStack(nts);
2597 }
2598
2599
2600 /* ***************************** threaded version for execute composite nodes ************* */
2601 /* these are nodes without input, only giving values */
2602 /* or nodes with only value inputs */
2603 static int node_only_value(bNode *node)
2604 {
2605         bNodeSocket *sock;
2606         
2607         if(ELEM3(node->type, CMP_NODE_TIME, CMP_NODE_VALUE, CMP_NODE_RGB))
2608                 return 1;
2609         
2610         /* doing this for all node types goes wrong. memory free errors */
2611         if(node->inputs.first && node->type==CMP_NODE_MAP_VALUE) {
2612                 int retval= 1;
2613                 for(sock= node->inputs.first; sock; sock= sock->next) {
2614                         if(sock->link && sock->link->fromnode)
2615                                 retval &= node_only_value(sock->link->fromnode);
2616                 }
2617                 return retval;
2618         }
2619         return 0;
2620 }
2621
2622
2623 /* not changing info, for thread callback */
2624 typedef struct ThreadData {
2625         bNodeStack *stack;
2626         RenderData *rd;
2627 } ThreadData;
2628
2629 static void *exec_composite_node(void *node_v)
2630 {
2631         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2632         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
2633         bNode *node= node_v;
2634         ThreadData *thd= (ThreadData *)node->threaddata;
2635         
2636         node_get_stack(node, thd->stack, nsin, nsout, NULL);
2637         
2638         if((node->flag & NODE_MUTED) && (!node_only_value(node))) {
2639                 /* viewers we execute, for feedback to user */
2640                 if(ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER)) 
2641                         node->typeinfo->execfunc(thd->rd, node, nsin, nsout);
2642                 else
2643                         node_compo_pass_on(node, nsin, nsout);
2644         }
2645         else if(node->typeinfo->execfunc) {
2646                 node->typeinfo->execfunc(thd->rd, node, nsin, nsout);
2647         }
2648         else if(node->type==NODE_GROUP && node->id) {
2649                 node_group_execute(thd->stack, thd->rd, node, nsin); 
2650         }
2651         
2652         node->exec |= NODE_READY;
2653         return NULL;
2654 }
2655
2656 /* return total of executable nodes, for timecursor */
2657 /* only compositor uses it */
2658 static int setExecutableNodes(bNodeTree *ntree, ThreadData *thd)
2659 {
2660         bNodeStack *nsin[MAX_SOCKET];   /* arbitrary... watch this */
2661         bNodeStack *nsout[MAX_SOCKET];  /* arbitrary... watch this */
2662         bNode *node;
2663         bNodeSocket *sock;
2664         int totnode= 0, group_edit= 0;
2665         
2666         /* note; do not add a dependency sort here, the stack was created already */
2667         
2668         /* if we are in group edit, viewer nodes get skipped when group has viewer */
2669         for(node= ntree->nodes.first; node; node= node->next)
2670                 if(node->type==NODE_GROUP && (node->flag & NODE_GROUP_EDIT))
2671                         if(ntreeHasType((bNodeTree *)node->id, CMP_NODE_VIEWER))
2672                                 group_edit= 1;
2673         
2674         for(node= ntree->nodes.first; node; node= node->next) {
2675                 int a;
2676                 
2677                 node_get_stack(node, thd->stack, nsin, nsout, NULL);
2678                 
2679                 /* test the outputs */
2680                 /* skip value-only nodes (should be in type!) */
2681                 if(!node_only_value(node)) {
2682                         for(a=0, sock= node->outputs.first; sock; sock= sock->next, a++) {
2683                                 if(nsout[a]->data==NULL && nsout[a]->hasoutput) {
2684                                         node->need_exec= 1;
2685                                         break;
2686                                 }
2687                         }
2688                 }
2689                 
2690                 /* test the inputs */
2691                 for(a=0, sock= node->inputs.first; sock; sock= sock->next, a++) {
2692                         /* skip viewer nodes in bg render or group edit */
2693                         if( ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER) && (G.background || group_edit))
2694                                 node->need_exec= 0;
2695                         /* is sock in use? */
2696                         else if(sock->link) {
2697                                 bNodeLink *link= sock->link;
2698                                 
2699                                 /* this is the test for a cyclic case */
2700                                 if(link->fromnode==NULL || link->tonode==NULL);
2701                                 else if(link->fromnode->level >= link->tonode->level && link->tonode->level!=0xFFF) {
2702                                         if(link->fromnode->need_exec) {
2703                                                 node->need_exec= 1;
2704                                                 break;
2705                                         }
2706                                 }
2707                                 else {
2708                                         node->need_exec= 0;
2709                                         printf("Node %s skipped, cyclic dependency\n", node->name);
2710                                 }
2711                         }
2712                 }
2713                 
2714                 if(node->need_exec) {
2715                         
2716                         /* free output buffers */
2717                         for(a=0, sock= node->outputs.first; sock; sock= sock->next, a++) {
2718                                 if(nsout[a]->data) {
2719                                         free_compbuf(nsout[a]->data);
2720                                         nsout[a]->data= NULL;
2721                                 }
2722                         }
2723                         totnode++;
2724                         /* printf("node needs exec %s\n", node->name); */
2725                         
2726                         /* tag for getExecutableNode() */
2727                         node->exec= 0;
2728                 }
2729                 else {
2730                         /* tag for getExecutableNode() */
2731                         node->exec= NODE_READY|NODE_FINISHED|NODE_SKIPPED;
2732                         
2733                 }
2734         }
2735         
2736         /* last step: set the stack values for only-value nodes */
2737         /* just does all now, compared to a full buffer exec this is nothing */
2738         if(totnode) {
2739                 for(node= ntree->nodes.first; node; node= node->next) {
2740                         if(node->need_exec==0 && node_only_value(node)) {
2741                                 if(node->typeinfo->execfunc) {
2742                                         node_get_stack(node, thd->stack, nsin, nsout, NULL);
2743                                         node->typeinfo->execfunc(thd->rd, node, nsin, nsout);
2744                                 }
2745                         }
2746                 }
2747         }
2748         
2749         return totnode;
2750 }
2751
2752 /* while executing tree, free buffers from nodes that are not needed anymore */
2753 static void freeExecutableNode(bNodeTree *ntree)
2754 {
2755         /* node outputs can be freed when:
2756         - not a render result or image node
2757         - when node outputs go to nodes all being set NODE_FINISHED
2758         */
2759         bNode *node;
2760         bNodeSocket *sock;
2761         
2762         /* set exec flag for finished nodes that might need freed */
2763         for(node= ntree->nodes.first; node; node= node->next) {
2764                 if(node->type!=CMP_NODE_R_LAYERS)
2765                         if(node->exec & NODE_FINISHED)
2766                                 node->exec |= NODE_FREEBUFS;
2767         }
2768         /* clear this flag for input links that are not done yet */
2769         for(node= ntree->nodes.first; node; node= node->next) {
2770                 if((node->exec & NODE_FINISHED)==0) {
2771                         for(sock= node->inputs.first; sock; sock= sock->next)
2772                                 if(sock->link && sock->link->fromnode)
2773                                         sock->link->fromnode->exec &= ~NODE_FREEBUFS;
2774                 }
2775         }
2776         /* now we can free buffers */
2777         for(node= ntree->nodes.first; node; node= node->next) {
2778                 if(node->exec & NODE_FREEBUFS) {
2779                         for(sock= node->outputs.first; sock; sock= sock->next) {
2780                                 bNodeStack *ns= get_socket_stack(ntree->stack, sock, NULL);
2781                                 if(ns && ns->data) {
2782                                         free_compbuf(ns->data);
2783                                         ns->data= NULL;
2784                                         // printf("freed buf node %s \n", node->name);
2785                                 }
2786                         }
2787                 }
2788         }
2789 }
2790
2791 static bNode *getExecutableNode(bNodeTree *ntree)
2792 {
2793         bNode *node;
2794         bNodeSocket *sock;
2795         
2796         for(node= ntree->nodes.first; node; node= node->next) {
2797                 if(node->exec==0) {
2798                         
2799                         /* input sockets should be ready */
2800                         for(sock= node->inputs.first; sock; sock= sock->next) {
2801                                 if(sock->link && sock->link->fromnode)
2802                                         if((sock->link->fromnode->exec & NODE_READY)==0)
2803                                                 break;
2804                         }
2805                         if(sock==NULL)
2806                                 return node;
2807                 }
2808         }
2809         return NULL;
2810 }
2811
2812 /* check if texture nodes need exec or end */
2813 static  void ntree_composite_texnode(bNodeTree *ntree, int init)
2814 {
2815         bNode *node;
2816         
2817         for(node= ntree->nodes.first; node; node= node->next) {
2818                 if(node->type==CMP_NODE_TEXTURE && node->id) {
2819                         Tex *tex= (Tex *)node->id;
2820                         if(tex->nodetree && tex->use_nodes) {
2821                                 /* has internal flag to detect it only does it once */
2822                                 if(init)
2823                                         ntreeBeginExecTree(tex->nodetree); 
2824                                 else
2825                                         ntreeEndExecTree(tex->nodetree);
2826                         }
2827                 }
2828         }
2829
2830 }
2831
2832 /* optimized tree execute test for compositing */
2833 void ntreeCompositExecTree(bNodeTree *ntree, RenderData *rd, int do_preview)
2834 {
2835         bNode *node;
2836         ListBase threads;
2837         ThreadData thdata;
2838         int totnode, curnode, rendering= 1;
2839         
2840         if(ntree==NULL) return;
2841         
2842         if(do_preview)
2843                 ntreeInitPreview(ntree, 0, 0);
2844         
2845         ntreeBeginExecTree(ntree);
2846         ntree_composite_texnode(ntree, 1);
2847         
2848         /* prevent unlucky accidents */
2849         if(G.background)
2850                 rd->scemode &= ~R_COMP_CROP;
2851         
2852         /* setup callerdata for thread callback */
2853         thdata.rd= rd;
2854         thdata.stack= ntree->stack;
2855         
2856         /* fixed seed, for example noise texture */
2857         BLI_srandom(rd->cfra);
2858
2859         /* ensures only a single output node is enabled */
2860         ntreeSetOutput(ntree);
2861
2862         /* sets need_exec tags in nodes */
2863         curnode = totnode= setExecutableNodes(ntree, &thdata);
2864
2865         BLI_init_threads(&threads, exec_composite_node, rd->threads);
2866         
2867         while(rendering) {
2868                 
2869                 if(BLI_available_threads(&threads)) {
2870                         node= getExecutableNode(ntree);
2871                         if(node) {
2872                                 if(ntree->progress && totnode)
2873                                         ntree->progress(ntree->prh, (1.0f - curnode/(float)totnode));
2874                                 if(ntree->stats_draw) {
2875                                         char str[64];
2876                                         sprintf(str, "Compositing %d %s", curnode, node->name);
2877                                         ntree->stats_draw(ntree->sdh, str);
2878                                 }
2879                                 curnode--;
2880                                 
2881                                 node->threaddata = &thdata;
2882                                 node->exec= NODE_PROCESSING;
2883                                 BLI_insert_thread(&threads, node);
2884                         }
2885                         else
2886                                 PIL_sleep_ms(50);
2887                 }
2888                 else
2889                         PIL_sleep_ms(50);
2890                 
2891                 rendering= 0;
2892                 /* test for ESC */
2893                 if(ntree->test_break && ntree->test_break(ntree->tbh)) {
2894                         for(node= ntree->nodes.first; node; node= node->next)
2895                                 node->exec |= NODE_READY;
2896                 }
2897                 
2898                 /* check for ready ones, and if we need to continue */
2899                 for(node= ntree->nodes.first; node; node= node->next) {
2900                         if(node->exec & NODE_READY) {
2901                                 if((node->exec & NODE_FINISHED)==0) {
2902                                         BLI_remove_thread(&threads, node); /* this waits for running thread to finish btw */
2903                                         node->exec |= NODE_FINISHED;
2904                                         
2905                                         /* freeing unused buffers */
2906                                         if(rd->scemode & R_COMP_FREE)
2907                                                 freeExecutableNode(ntree);
2908                                 }
2909                         }
2910                         else rendering= 1;
2911                 }
2912         }
2913         
2914         BLI_end_threads(&threads);
2915         
2916         ntreeEndExecTree(ntree);
2917 }
2918
2919
2920 /* ********** copy composite tree entirely, to allow threaded exec ******************* */
2921 /* ***************** do NOT execute this in a thread!               ****************** */
2922
2923 /* returns localized tree for execution in threads */
2924 /* local tree then owns all compbufs (for composite) */
2925 bNodeTree *ntreeLocalize(bNodeTree *ntree)
2926 {
2927         bNodeTree *ltree;
2928         bNode *node;
2929         bNodeSocket *sock;
2930         
2931         bAction *action_backup= NULL, *tmpact_backup= NULL;
2932         
2933         /* Workaround for copying an action on each render!
2934          * set action to NULL so animdata actions dont get copied */
2935         AnimData *adt= BKE_animdata_from_id(&ntree->id);
2936
2937         if(adt) {
2938                 action_backup= adt->action;
2939                 tmpact_backup= adt->tmpact;
2940
2941                 adt->action= NULL;
2942                 adt->tmpact= NULL;
2943         }
2944
2945         /* node copy func */
2946         ltree= ntreeCopyTree(ntree);
2947
2948         if(adt) {
2949                 AnimData *ladt= BKE_animdata_from_id(&ltree->id);
2950
2951                 adt->action= ladt->action= action_backup;
2952                 adt->tmpact= ladt->tmpact= tmpact_backup;
2953
2954                 if(action_backup) action_backup->id.us++;
2955                 if(tmpact_backup) tmpact_backup->id.us++;
2956                 
2957         }
2958         /* end animdata uglyness */
2959
2960         /* ensures only a single output node is enabled */
2961         ntreeSetOutput(ltree);
2962
2963         for(node= ntree->nodes.first; node; node= node->next) {
2964                 
2965                 /* store new_node pointer to original */
2966                 node->new_node->new_node= node;
2967                 
2968                 if(ntree->type==NTREE_COMPOSIT) {
2969                         /* ensure new user input gets handled ok, only composites (texture nodes will break, for painting since it uses no tags) */
2970                         node->need_exec= 0;
2971                         
2972                         /* move over the compbufs */
2973                         /* right after ntreeCopyTree() oldsock pointers are valid */
2974                         
2975                         if(ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER)) {
2976                                 if(node->id) {
2977                                         if(node->flag & NODE_DO_OUTPUT)
2978                                                 node->new_node->id= (ID *)copy_image((Image *)node->id);
2979                                         else
2980                                                 node->new_node->id= NULL;
2981                                 }
2982                         }
2983                         
2984                         for(sock= node->outputs.first; sock; sock= sock->next) {
2985                                 
2986                                 sock->new_sock->ns.data= sock->ns.data;
2987                                 compbuf_set_node(sock->new_sock->ns.data, node->new_node);
2988                                 
2989                                 sock->ns.data= NULL;
2990                                 sock->new_sock->new_sock= sock;
2991                         }
2992                 }
2993         }
2994         
2995         return ltree;
2996 }
2997
2998 static int node_exists(bNodeTree *ntree, bNode *testnode)
2999 {
3000         bNode *node= ntree->nodes.first;
3001         for(; node; node= node->next)
3002                 if(node==testnode)
3003                         return 1;
3004         return 0;
3005 }
3006
3007 static int outsocket_exists(bNode *node, bNodeSocket *testsock)
3008 {
3009         bNodeSocket *sock= node->outputs.first;
3010         for(; sock; sock= sock->next)
3011                 if(sock==testsock)
3012                         return 1;
3013         return 0;
3014 }
3015
3016
3017 /* sync local composite with real tree */
3018 /* local composite is supposed to be running, be careful moving previews! */
3019 /* is called by jobs manager, outside threads, so it doesnt happen during draw */
3020 void ntreeLocalSync(bNodeTree *localtree, bNodeTree *ntree)
3021 {
3022         bNode *lnode;
3023         
3024         if(ntree->type==NTREE_COMPOSIT) {
3025                 /* move over the compbufs and previews */
3026                 for(lnode= localtree->nodes.first; lnode; lnode= lnode->next) {
3027                         if( (lnode->exec & NODE_READY) && !(lnode->exec & NODE_SKIPPED) ) {
3028                                 if(node_exists(ntree, lnode->new_node)) {
3029                                         
3030                                         if(lnode->preview && lnode->preview->rect) {
3031                                                 node_free_preview(lnode->new_node);
3032                                                 lnode->new_node->preview= lnode->preview;
3033                                                 lnode->preview= NULL;
3034                                         }
3035                                 }
3036                         }
3037                 }
3038         }
3039         else if(ELEM(ntree->type, NTREE_SHADER, NTREE_TEXTURE)) {
3040                 /* copy over contents of previews */
3041                 for(lnode= localtree->nodes.first; lnode; lnode= lnode->next) {
3042                         if(node_exists(ntree, lnode->new_node)) {
3043                                 bNode *node= lnode->new_node;
3044                                 
3045                                 if(node->preview && node->preview->rect) {
3046                                         if(lnode->preview && lnode->preview->rect) {
3047                                                 int xsize= node->preview->xsize;
3048                                                 int ysize= node->preview->ysize;
3049                                                 memcpy(node->preview->rect, lnode->preview->rect, 4*xsize + xsize*ysize*sizeof(char)*4);
3050                                         }
3051                                 }
3052                         }
3053                 }
3054         }
3055 }
3056
3057 /* merge local tree results back, and free local tree */
3058 /* we have to assume the editor already changed completely */
3059 void ntreeLocalMerge(bNodeTree *localtree, bNodeTree *ntree)
3060 {
3061         bNode *lnode;
3062         bNodeSocket *lsock;
3063         
3064         /* move over the compbufs and previews */
3065         for(lnode= localtree->nodes.first; lnode; lnode= lnode->next) {
3066                 if(node_exists(ntree, lnode->new_node)) {
3067                         
3068                         if(lnode->preview && lnode->preview->rect) {
3069                                 node_free_preview(lnode->new_node);
3070