Merging r49463 through r49478 from trunk into soc-2011-tomato
[blender.git] / source / blender / editors / space_node / node_relationships.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2005 Blender Foundation.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): David Millan Escriva, Juho Vepsäläinen, Nathan Letwory
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/editors/space_node/node_relationships.c
29  *  \ingroup spnode
30  */
31
32 #include <stdio.h>
33 #include <stdlib.h>
34 #include <math.h>
35 #include <string.h>
36 #include <errno.h>
37
38 #include "MEM_guardedalloc.h"
39
40 #include "DNA_ID.h"
41 #include "DNA_lamp_types.h"
42 #include "DNA_material_types.h"
43 #include "DNA_node_types.h"
44 #include "DNA_object_types.h"
45 #include "DNA_particle_types.h"
46 #include "DNA_scene_types.h"
47 #include "DNA_world_types.h"
48 #include "DNA_action_types.h"
49 #include "DNA_anim_types.h"
50
51 #include "BLI_math.h"
52 #include "BLI_blenlib.h"
53 #include "BLI_utildefines.h"
54
55 #include "BKE_action.h"
56 #include "BKE_animsys.h"
57 #include "BKE_context.h"
58 #include "BKE_depsgraph.h"
59 #include "BKE_global.h"
60 #include "BKE_image.h"
61 #include "BKE_library.h"
62 #include "BKE_main.h"
63 #include "BKE_node.h"
64 #include "BKE_material.h"
65 #include "BKE_modifier.h"
66 #include "BKE_paint.h"
67 #include "BKE_scene.h"
68 #include "BKE_screen.h"
69 #include "BKE_texture.h"
70 #include "BKE_report.h"
71
72 #include "RE_pipeline.h"
73
74 #include "IMB_imbuf_types.h"
75
76 #include "ED_node.h"
77 #include "ED_image.h"
78 #include "ED_screen.h"
79 #include "ED_space_api.h"
80 #include "ED_render.h"
81
82 #include "RNA_access.h"
83 #include "RNA_define.h"
84 #include "RNA_enum_types.h"
85
86 #include "WM_api.h"
87 #include "WM_types.h"
88
89 #include "UI_interface.h"
90 #include "UI_resources.h"
91 #include "UI_view2d.h"
92
93 #include "IMB_imbuf.h"
94
95 #include "RNA_enum_types.h"
96
97 #include "GPU_material.h"
98
99 #include "node_intern.h"
100 #include "NOD_socket.h"
101
102
103 /* ****************** Add *********************** */
104
105
106 typedef struct bNodeListItem {
107         struct bNodeListItem *next, *prev;
108         struct bNode *node;
109 } bNodeListItem;
110
111 static int sort_nodes_locx(void *a, void *b)
112 {
113         bNodeListItem *nli1 = (bNodeListItem *)a;
114         bNodeListItem *nli2 = (bNodeListItem *)b;
115         bNode *node1 = nli1->node;
116         bNode *node2 = nli2->node;
117
118         if (node1->locx > node2->locx)
119                 return 1;
120         else
121                 return 0;
122 }
123
124 static int socket_is_available(bNodeTree *UNUSED(ntree), bNodeSocket *sock, int allow_used)
125 {
126         if (nodeSocketIsHidden(sock))
127                 return 0;
128
129         if (!allow_used && (sock->flag & SOCK_IN_USE))
130                 return 0;
131
132         return 1;
133 }
134
135 static bNodeSocket *best_socket_output(bNodeTree *ntree, bNode *node, bNodeSocket *sock_target, int allow_multiple)
136 {
137         bNodeSocket *sock;
138
139         /* first look for selected output */
140         for (sock = node->outputs.first; sock; sock = sock->next) {
141                 if (!socket_is_available(ntree, sock, allow_multiple))
142                         continue;
143
144                 if (sock->flag & SELECT)
145                         return sock;
146         }
147
148         /* try to find a socket with a matching name */
149         for (sock = node->outputs.first; sock; sock = sock->next) {
150                 if (!socket_is_available(ntree, sock, allow_multiple))
151                         continue;
152
153                 /* check for same types */
154                 if (sock->type == sock_target->type) {
155                         if (strcmp(sock->name, sock_target->name) == 0)
156                                 return sock;
157                 }
158         }
159
160         /* otherwise settle for the first available socket of the right type */
161         for (sock = node->outputs.first; sock; sock = sock->next) {
162
163                 if (!socket_is_available(ntree, sock, allow_multiple))
164                         continue;
165
166                 /* check for same types */
167                 if (sock->type == sock_target->type) {
168                         return sock;
169                 }
170         }
171
172         return NULL;
173 }
174
175 /* this is a bit complicated, but designed to prioritize finding
176  * sockets of higher types, such as image, first */
177 static bNodeSocket *best_socket_input(bNodeTree *ntree, bNode *node, int num, int replace)
178 {
179         bNodeSocket *sock;
180         int socktype, maxtype = 0;
181         int a = 0;
182
183         for (sock = node->inputs.first; sock; sock = sock->next) {
184                 maxtype = MAX2(sock->type, maxtype);
185         }
186
187         /* find sockets of higher 'types' first (i.e. image) */
188         for (socktype = maxtype; socktype >= 0; socktype--) {
189                 for (sock = node->inputs.first; sock; sock = sock->next) {
190
191                         if (!socket_is_available(ntree, sock, replace)) {
192                                 a++;
193                                 continue;
194                         }
195
196                         if (sock->type == socktype) {
197                                 /* increment to make sure we don't keep finding
198                                  * the same socket on every attempt running this function */
199                                 a++;
200                                 if (a > num)
201                                         return sock;
202                         }
203                 }
204         }
205
206         return NULL;
207 }
208
209 static int snode_autoconnect_input(SpaceNode *snode, bNode *node_fr, bNodeSocket *sock_fr, bNode *node_to, bNodeSocket *sock_to, int replace)
210 {
211         bNodeTree *ntree = snode->edittree;
212         bNodeLink *link;
213
214         /* then we can connect */
215         if (replace)
216                 nodeRemSocketLinks(ntree, sock_to);
217
218         link = nodeAddLink(ntree, node_fr, sock_fr, node_to, sock_to);
219         /* validate the new link */
220         ntreeUpdateTree(ntree);
221         if (!(link->flag & NODE_LINK_VALID)) {
222                 nodeRemLink(ntree, link);
223                 return 0;
224         }
225
226         snode_update(snode, node_to);
227         return 1;
228 }
229
230 static void snode_autoconnect(SpaceNode *snode, int allow_multiple, int replace)
231 {
232         bNodeTree *ntree = snode->edittree;
233         ListBase *nodelist = MEM_callocN(sizeof(ListBase), "items_list");
234         bNodeListItem *nli;
235         bNode *node;
236         int i, numlinks = 0;
237
238         for (node = ntree->nodes.first; node; node = node->next) {
239                 if (node->flag & NODE_SELECT) {
240                         nli = MEM_mallocN(sizeof(bNodeListItem), "temporary node list item");
241                         nli->node = node;
242                         BLI_addtail(nodelist, nli);
243                 }
244         }
245
246         /* sort nodes left to right */
247         BLI_sortlist(nodelist, sort_nodes_locx);
248
249         for (nli = nodelist->first; nli; nli = nli->next) {
250                 bNode *node_fr, *node_to;
251                 bNodeSocket *sock_fr, *sock_to;
252                 int has_selected_inputs = 0;
253
254                 if (nli->next == NULL) break;
255
256                 node_fr = nli->node;
257                 node_to = nli->next->node;
258
259                 /* if there are selected sockets, connect those */
260                 for (sock_to = node_to->inputs.first; sock_to; sock_to = sock_to->next) {
261                         if (sock_to->flag & SELECT) {
262                                 has_selected_inputs = 1;
263
264                                 if (!socket_is_available(ntree, sock_to, replace))
265                                         continue;
266
267                                 /* check for an appropriate output socket to connect from */
268                                 sock_fr = best_socket_output(ntree, node_fr, sock_to, allow_multiple);
269                                 if (!sock_fr)
270                                         continue;
271
272                                 if (snode_autoconnect_input(snode, node_fr, sock_fr, node_to, sock_to, replace))
273                                         ++numlinks;
274                         }
275                 }
276
277                 if (!has_selected_inputs) {
278                         /* no selected inputs, connect by finding suitable match */
279                         int num_inputs = BLI_countlist(&node_to->inputs);
280
281                         for (i = 0; i < num_inputs; i++) {
282
283                                 /* find the best guess input socket */
284                                 sock_to = best_socket_input(ntree, node_to, i, replace);
285                                 if (!sock_to)
286                                         continue;
287
288                                 /* check for an appropriate output socket to connect from */
289                                 sock_fr = best_socket_output(ntree, node_fr, sock_to, allow_multiple);
290                                 if (!sock_fr)
291                                         continue;
292
293                                 if (snode_autoconnect_input(snode, node_fr, sock_fr, node_to, sock_to, replace)) {
294                                         ++numlinks;
295                                         break;
296                                 }
297                         }
298                 }
299         }
300
301         if (numlinks > 0) {
302                 ntreeUpdateTree(ntree);
303         }
304
305         BLI_freelistN(nodelist);
306         MEM_freeN(nodelist);
307 }
308
309 /* *************************** link viewer op ******************** */
310
311 static int node_link_viewer(const bContext *C, bNode *tonode)
312 {
313         SpaceNode *snode = CTX_wm_space_node(C);
314         bNode *node;
315         bNodeLink *link;
316         bNodeSocket *sock;
317
318         /* context check */
319         if (tonode == NULL || tonode->outputs.first == NULL)
320                 return OPERATOR_CANCELLED;
321         if (ELEM(tonode->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER))
322                 return OPERATOR_CANCELLED;
323
324         /* get viewer */
325         for (node = snode->edittree->nodes.first; node; node = node->next)
326                 if (ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER))
327                         if (node->flag & NODE_DO_OUTPUT)
328                                 break;
329         /* no viewer, we make one active */
330         if (node == NULL) {
331                 for (node = snode->edittree->nodes.first; node; node = node->next) {
332                         if (ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER)) {
333                                 node->flag |= NODE_DO_OUTPUT;
334                                 break;
335                         }
336                 }
337         }
338
339         sock = NULL;
340
341         /* try to find an already connected socket to cycle to the next */
342         if (node) {
343                 link = NULL;
344                 for (link = snode->edittree->links.first; link; link = link->next)
345                         if (link->tonode == node && link->fromnode == tonode)
346                                 if (link->tosock == node->inputs.first)
347                                         break;
348                 if (link) {
349                         /* unlink existing connection */
350                         sock = link->fromsock;
351                         nodeRemLink(snode->edittree, link);
352
353                         /* find a socket after the previously connected socket */
354                         for (sock = sock->next; sock; sock = sock->next)
355                                 if (!nodeSocketIsHidden(sock))
356                                         break;
357                 }
358         }
359
360         /* find a socket starting from the first socket */
361         if (!sock) {
362                 for (sock = tonode->outputs.first; sock; sock = sock->next)
363                         if (!nodeSocketIsHidden(sock))
364                                 break;
365         }
366
367         if (sock) {
368                 /* add a new viewer if none exists yet */
369                 if (!node) {
370                         Main *bmain = CTX_data_main(C);
371                         Scene *scene = CTX_data_scene(C);
372                         bNodeTemplate ntemp;
373
374                         ntemp.type = CMP_NODE_VIEWER;
375                         /* XXX location is a quick hack, just place it next to the linked socket */
376                         node = node_add_node(snode, bmain, scene, &ntemp, sock->locx + 100, sock->locy);
377                         if (!node)
378                                 return OPERATOR_CANCELLED;
379
380                         link = NULL;
381                 }
382                 else {
383                         /* get link to viewer */
384                         for (link = snode->edittree->links.first; link; link = link->next)
385                                 if (link->tonode == node && link->tosock == node->inputs.first)
386                                         break;
387                 }
388
389                 if (link == NULL) {
390                         nodeAddLink(snode->edittree, tonode, sock, node, node->inputs.first);
391                 }
392                 else {
393                         link->fromnode = tonode;
394                         link->fromsock = sock;
395                         /* make sure the dependency sorting is updated */
396                         snode->edittree->update |= NTREE_UPDATE_LINKS;
397                 }
398                 ntreeUpdateTree(snode->edittree);
399                 snode_update(snode, node);
400         }
401
402         return OPERATOR_FINISHED;
403 }
404
405
406 static int node_active_link_viewer(bContext *C, wmOperator *UNUSED(op))
407 {
408         SpaceNode *snode = CTX_wm_space_node(C);
409         bNode *node;
410
411         node = editnode_get_active(snode->edittree);
412
413         if (!node)
414                 return OPERATOR_CANCELLED;
415
416         ED_preview_kill_jobs(C);
417
418         if (node_link_viewer(C, node) == OPERATOR_CANCELLED)
419                 return OPERATOR_CANCELLED;
420
421         snode_notify(C, snode);
422
423         return OPERATOR_FINISHED;
424 }
425
426
427 void NODE_OT_link_viewer(wmOperatorType *ot)
428 {
429         /* identifiers */
430         ot->name = "Link to Viewer Node";
431         ot->description = "Link to viewer node";
432         ot->idname = "NODE_OT_link_viewer";
433
434         /* api callbacks */
435         ot->exec = node_active_link_viewer;
436         ot->poll = composite_node_active;
437
438         /* flags */
439         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
440 }
441
442
443 /* *************************** add link op ******************** */
444
445 static void node_remove_extra_links(SpaceNode *snode, bNodeSocket *tsock, bNodeLink *link)
446 {
447         bNodeLink *tlink;
448         bNodeSocket *sock;
449
450         if (tsock && nodeCountSocketLinks(snode->edittree, link->tosock) > tsock->limit) {
451
452                 for (tlink = snode->edittree->links.first; tlink; tlink = tlink->next) {
453                         if (link != tlink && tlink->tosock == link->tosock)
454                                 break;
455                 }
456                 if (tlink) {
457                         /* try to move the existing link to the next available socket */
458                         if (tlink->tonode) {
459                                 /* is there a free input socket with the target type? */
460                                 for (sock = tlink->tonode->inputs.first; sock; sock = sock->next) {
461                                         if (sock->type == tlink->tosock->type)
462                                                 if (nodeCountSocketLinks(snode->edittree, sock) < sock->limit)
463                                                         break;
464                                 }
465                                 if (sock) {
466                                         tlink->tosock = sock;
467                                         sock->flag &= ~SOCK_HIDDEN;
468                                 }
469                                 else {
470                                         nodeRemLink(snode->edittree, tlink);
471                                 }
472                         }
473                         else
474                                 nodeRemLink(snode->edittree, tlink);
475
476                         snode->edittree->update |= NTREE_UPDATE_LINKS;
477                 }
478         }
479 }
480
481 static int outside_group_rect(SpaceNode *snode)
482 {
483         bNode *gnode = node_tree_get_editgroup(snode->nodetree);
484         if (gnode) {
485                 return (snode->mx <  gnode->totr.xmin ||
486                         snode->mx >= gnode->totr.xmax ||
487                         snode->my <  gnode->totr.ymin ||
488                         snode->my >= gnode->totr.ymax);
489         }
490         return 0;
491 }
492
493 /* loop that adds a nodelink, called by function below  */
494 /* in_out = starting socket */
495 static int node_link_modal(bContext *C, wmOperator *op, wmEvent *event)
496 {
497         SpaceNode *snode = CTX_wm_space_node(C);
498         ARegion *ar = CTX_wm_region(C);
499         bNodeLinkDrag *nldrag = op->customdata;
500         bNodeTree *ntree = snode->edittree;
501         bNode *tnode;
502         bNodeSocket *tsock = NULL;
503         bNodeLink *link;
504         LinkData *linkdata;
505         int in_out;
506
507         in_out = nldrag->in_out;
508
509         UI_view2d_region_to_view(&ar->v2d, event->mval[0], event->mval[1],
510                                  &snode->mx, &snode->my);
511
512         switch (event->type) {
513                 case MOUSEMOVE:
514
515                         if (in_out == SOCK_OUT) {
516                                 if (node_find_indicated_socket(snode, &tnode, &tsock, SOCK_IN)) {
517                                         for (linkdata = nldrag->links.first; linkdata; linkdata = linkdata->next) {
518                                                 link = linkdata->data;
519
520                                                 /* skip if this is already the target socket */
521                                                 if (link->tosock == tsock)
522                                                         continue;
523                                                 /* skip if socket is on the same node as the fromsock */
524                                                 if (tnode && link->fromnode == tnode)
525                                                         continue;
526
527                                                 /* attach links to the socket */
528                                                 link->tonode = tnode;
529                                                 link->tosock = tsock;
530                                                 /* add it to the node tree temporarily */
531                                                 if (BLI_findindex(&ntree->links, link) < 0)
532                                                         BLI_addtail(&ntree->links, link);
533
534                                                 ntree->update |= NTREE_UPDATE_LINKS;
535                                         }
536                                         ntreeUpdateTree(ntree);
537                                 }
538                                 else {
539                                         int do_update = FALSE;
540                                         for (linkdata = nldrag->links.first; linkdata; linkdata = linkdata->next) {
541                                                 link = linkdata->data;
542
543                                                 if (link->tonode || link->tosock) {
544                                                         BLI_remlink(&ntree->links, link);
545                                                         link->prev = link->next = NULL;
546                                                         link->tonode = NULL;
547                                                         link->tosock = NULL;
548
549                                                         ntree->update |= NTREE_UPDATE_LINKS;
550                                                         do_update = TRUE;
551                                                 }
552                                         }
553                                         if (do_update) {
554                                                 ntreeUpdateTree(ntree);
555                                         }
556                                 }
557                         }
558                         else {
559                                 if (node_find_indicated_socket(snode, &tnode, &tsock, SOCK_OUT)) {
560                                         for (linkdata = nldrag->links.first; linkdata; linkdata = linkdata->next) {
561                                                 link = linkdata->data;
562
563                                                 /* skip if this is already the target socket */
564                                                 if (link->fromsock == tsock)
565                                                         continue;
566                                                 /* skip if socket is on the same node as the fromsock */
567                                                 if (tnode && link->tonode == tnode)
568                                                         continue;
569
570                                                 /* attach links to the socket */
571                                                 link->fromnode = tnode;
572                                                 link->fromsock = tsock;
573                                                 /* add it to the node tree temporarily */
574                                                 if (BLI_findindex(&ntree->links, link) < 0)
575                                                         BLI_addtail(&ntree->links, link);
576
577                                                 ntree->update |= NTREE_UPDATE_LINKS;
578                                         }
579                                         ntreeUpdateTree(ntree);
580                                 }
581                                 else {
582                                         int do_update = FALSE;
583                                         for (linkdata = nldrag->links.first; linkdata; linkdata = linkdata->next) {
584                                                 link = linkdata->data;
585
586                                                 if (link->fromnode || link->fromsock) {
587                                                         BLI_remlink(&ntree->links, link);
588                                                         link->prev = link->next = NULL;
589                                                         link->fromnode = NULL;
590                                                         link->fromsock = NULL;
591
592                                                         ntree->update |= NTREE_UPDATE_LINKS;
593                                                         do_update = TRUE;
594                                                 }
595                                         }
596                                         if (do_update) {
597                                                 ntreeUpdateTree(ntree);
598                                         }
599                                 }
600                         }
601
602                         ED_region_tag_redraw(ar);
603                         break;
604
605                 case LEFTMOUSE:
606                 case RIGHTMOUSE:
607                 case MIDDLEMOUSE: {
608                         for (linkdata = nldrag->links.first; linkdata; linkdata = linkdata->next) {
609                                 link = linkdata->data;
610
611                                 if (link->tosock && link->fromsock) {
612                                         /* send changed events for original tonode and new */
613                                         if (link->tonode)
614                                                 snode_update(snode, link->tonode);
615
616                                         /* we might need to remove a link */
617                                         if (in_out == SOCK_OUT)
618                                                 node_remove_extra_links(snode, link->tosock, link);
619
620                                         /* when linking to group outputs, update the socket type */
621                                         /* XXX this should all be part of a generic update system */
622                                         if (!link->tonode) {
623                                                 if (link->tosock->type != link->fromsock->type)
624                                                         nodeSocketSetType(link->tosock, link->fromsock->type);
625                                         }
626                                 }
627                                 else if (outside_group_rect(snode) && (link->tonode || link->fromnode)) {
628                                         /* automatically add new group socket */
629                                         if (link->tonode && link->tosock) {
630                                                 link->fromsock = node_group_expose_socket(ntree, link->tosock, SOCK_IN);
631                                                 link->fromnode = NULL;
632                                                 if (BLI_findindex(&ntree->links, link) < 0)
633                                                         BLI_addtail(&ntree->links, link);
634
635                                                 ntree->update |= NTREE_UPDATE_GROUP_IN | NTREE_UPDATE_LINKS;
636                                         }
637                                         else if (link->fromnode && link->fromsock) {
638                                                 link->tosock = node_group_expose_socket(ntree, link->fromsock, SOCK_OUT);
639                                                 link->tonode = NULL;
640                                                 if (BLI_findindex(&ntree->links, link) < 0)
641                                                         BLI_addtail(&ntree->links, link);
642
643                                                 ntree->update |= NTREE_UPDATE_GROUP_OUT | NTREE_UPDATE_LINKS;
644                                         }
645                                 }
646                                 else
647                                         nodeRemLink(ntree, link);
648                         }
649
650                         ntreeUpdateTree(ntree);
651                         snode_notify(C, snode);
652                         snode_dag_update(C, snode);
653
654                         BLI_remlink(&snode->linkdrag, nldrag);
655                         /* links->data pointers are either held by the tree or freed already */
656                         BLI_freelistN(&nldrag->links);
657                         MEM_freeN(nldrag);
658
659                         return OPERATOR_FINISHED;
660                 }
661         }
662
663         return OPERATOR_RUNNING_MODAL;
664 }
665
666 /* return 1 when socket clicked */
667 static bNodeLinkDrag *node_link_init(SpaceNode *snode, int detach)
668 {
669         bNode *node;
670         bNodeSocket *sock;
671         bNodeLink *link, *link_next, *oplink;
672         bNodeLinkDrag *nldrag = NULL;
673         LinkData *linkdata;
674         int num_links;
675
676         /* output indicated? */
677         if (node_find_indicated_socket(snode, &node, &sock, SOCK_OUT)) {
678                 nldrag = MEM_callocN(sizeof(bNodeLinkDrag), "drag link op customdata");
679
680                 num_links = nodeCountSocketLinks(snode->edittree, sock);
681                 if (num_links > 0 && (num_links >= sock->limit || detach)) {
682                         /* dragged links are fixed on input side */
683                         nldrag->in_out = SOCK_IN;
684                         /* detach current links and store them in the operator data */
685                         for (link = snode->edittree->links.first; link; link = link_next) {
686                                 link_next = link->next;
687                                 if (link->fromsock == sock) {
688                                         linkdata = MEM_callocN(sizeof(LinkData), "drag link op link data");
689                                         linkdata->data = oplink = MEM_callocN(sizeof(bNodeLink), "drag link op link");
690                                         *oplink = *link;
691                                         oplink->next = oplink->prev = NULL;
692                                         BLI_addtail(&nldrag->links, linkdata);
693                                         nodeRemLink(snode->edittree, link);
694                                 }
695                         }
696                 }
697                 else {
698                         /* dragged links are fixed on output side */
699                         nldrag->in_out = SOCK_OUT;
700                         /* create a new link */
701                         linkdata = MEM_callocN(sizeof(LinkData), "drag link op link data");
702                         linkdata->data = oplink = MEM_callocN(sizeof(bNodeLink), "drag link op link");
703                         oplink->fromnode = node;
704                         oplink->fromsock = sock;
705                         BLI_addtail(&nldrag->links, linkdata);
706                 }
707         }
708         /* or an input? */
709         else if (node_find_indicated_socket(snode, &node, &sock, SOCK_IN)) {
710                 nldrag = MEM_callocN(sizeof(bNodeLinkDrag), "drag link op customdata");
711
712                 num_links = nodeCountSocketLinks(snode->edittree, sock);
713                 if (num_links > 0 && (num_links >= sock->limit || detach)) {
714                         /* dragged links are fixed on output side */
715                         nldrag->in_out = SOCK_OUT;
716                         /* detach current links and store them in the operator data */
717                         for (link = snode->edittree->links.first; link; link = link_next) {
718                                 link_next = link->next;
719                                 if (link->tosock == sock) {
720                                         linkdata = MEM_callocN(sizeof(LinkData), "drag link op link data");
721                                         linkdata->data = oplink = MEM_callocN(sizeof(bNodeLink), "drag link op link");
722                                         *oplink = *link;
723                                         oplink->next = oplink->prev = NULL;
724                                         BLI_addtail(&nldrag->links, linkdata);
725                                         nodeRemLink(snode->edittree, link);
726
727                                         /* send changed event to original link->tonode */
728                                         if (node)
729                                                 snode_update(snode, node);
730                                 }
731                         }
732                 }
733                 else {
734                         /* dragged links are fixed on input side */
735                         nldrag->in_out = SOCK_IN;
736                         /* create a new link */
737                         linkdata = MEM_callocN(sizeof(LinkData), "drag link op link data");
738                         linkdata->data = oplink = MEM_callocN(sizeof(bNodeLink), "drag link op link");
739                         oplink->tonode = node;
740                         oplink->tosock = sock;
741                         BLI_addtail(&nldrag->links, linkdata);
742                 }
743         }
744
745         return nldrag;
746 }
747
748 static int node_link_invoke(bContext *C, wmOperator *op, wmEvent *event)
749 {
750         SpaceNode *snode = CTX_wm_space_node(C);
751         ARegion *ar = CTX_wm_region(C);
752         bNodeLinkDrag *nldrag;
753         int detach = RNA_boolean_get(op->ptr, "detach");
754
755         UI_view2d_region_to_view(&ar->v2d, event->mval[0], event->mval[1],
756                                  &snode->mx, &snode->my);
757
758         ED_preview_kill_jobs(C);
759
760         nldrag = node_link_init(snode, detach);
761
762         if (nldrag) {
763                 op->customdata = nldrag;
764                 BLI_addtail(&snode->linkdrag, nldrag);
765
766                 /* add modal handler */
767                 WM_event_add_modal_handler(C, op);
768
769                 return OPERATOR_RUNNING_MODAL;
770         }
771         else
772                 return OPERATOR_CANCELLED | OPERATOR_PASS_THROUGH;
773 }
774
775 static int node_link_cancel(bContext *C, wmOperator *op)
776 {
777         SpaceNode *snode = CTX_wm_space_node(C);
778         bNodeLinkDrag *nldrag = op->customdata;
779
780         BLI_remlink(&snode->linkdrag, nldrag);
781
782         BLI_freelistN(&nldrag->links);
783         MEM_freeN(nldrag);
784
785         return OPERATOR_CANCELLED;
786 }
787
788 void NODE_OT_link(wmOperatorType *ot)
789 {
790         /* identifiers */
791         ot->name = "Link Nodes";
792         ot->idname = "NODE_OT_link";
793         ot->description = "Use the mouse to create a link between two nodes";
794
795         /* api callbacks */
796         ot->invoke = node_link_invoke;
797         ot->modal = node_link_modal;
798 //      ot->exec = node_link_exec;
799         ot->poll = ED_operator_node_active;
800         ot->cancel = node_link_cancel;
801
802         /* flags */
803         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO | OPTYPE_BLOCKING;
804
805         RNA_def_boolean(ot->srna, "detach", FALSE, "Detach", "Detach and redirect existing links");
806 }
807
808 /* ********************** Make Link operator ***************** */
809
810 /* makes a link between selected output and input sockets */
811 static int node_make_link_exec(bContext *C, wmOperator *op)
812 {
813         SpaceNode *snode = CTX_wm_space_node(C);
814         int replace = RNA_boolean_get(op->ptr, "replace");
815
816         ED_preview_kill_jobs(C);
817
818         snode_autoconnect(snode, 1, replace);
819
820         /* deselect sockets after linking */
821         node_deselect_all_input_sockets(snode, 0);
822         node_deselect_all_output_sockets(snode, 0);
823
824         ntreeUpdateTree(snode->edittree);
825         snode_notify(C, snode);
826         snode_dag_update(C, snode);
827
828         return OPERATOR_FINISHED;
829 }
830
831 void NODE_OT_link_make(wmOperatorType *ot)
832 {
833         /* identifiers */
834         ot->name = "Make Links";
835         ot->description = "Makes a link between selected output in input sockets";
836         ot->idname = "NODE_OT_link_make";
837
838         /* callbacks */
839         ot->exec = node_make_link_exec;
840         ot->poll = ED_operator_node_active; // XXX we need a special poll which checks that there are selected input/output sockets
841
842         /* flags */
843         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
844
845         RNA_def_boolean(ot->srna, "replace", 0, "Replace", "Replace socket connections with the new links");
846 }
847
848 /* ********************** Cut Link operator ***************** */
849 static int cut_links_intersect(bNodeLink *link, float mcoords[][2], int tot)
850 {
851         float coord_array[NODE_LINK_RESOL + 1][2];
852         int i, b;
853
854         if (node_link_bezier_points(NULL, NULL, link, coord_array, NODE_LINK_RESOL)) {
855
856                 for (i = 0; i < tot - 1; i++)
857                         for (b = 0; b < NODE_LINK_RESOL; b++)
858                                 if (isect_line_line_v2(mcoords[i], mcoords[i + 1], coord_array[b], coord_array[b + 1]) > 0)
859                                         return 1;
860         }
861         return 0;
862 }
863
864 static int cut_links_exec(bContext *C, wmOperator *op)
865 {
866         SpaceNode *snode = CTX_wm_space_node(C);
867         ARegion *ar = CTX_wm_region(C);
868         float mcoords[256][2];
869         int i = 0;
870
871         RNA_BEGIN(op->ptr, itemptr, "path")
872         {
873                 float loc[2];
874
875                 RNA_float_get_array(&itemptr, "loc", loc);
876                 UI_view2d_region_to_view(&ar->v2d, (int)loc[0], (int)loc[1],
877                                          &mcoords[i][0], &mcoords[i][1]);
878                 i++;
879                 if (i >= 256) break;
880         }
881         RNA_END;
882
883         if (i > 1) {
884                 bNodeLink *link, *next;
885
886                 ED_preview_kill_jobs(C);
887
888                 for (link = snode->edittree->links.first; link; link = next) {
889                         next = link->next;
890
891                         if (cut_links_intersect(link, mcoords, i)) {
892                                 snode_update(snode, link->tonode);
893                                 nodeRemLink(snode->edittree, link);
894                         }
895                 }
896
897                 ntreeUpdateTree(snode->edittree);
898                 snode_notify(C, snode);
899                 snode_dag_update(C, snode);
900
901                 return OPERATOR_FINISHED;
902         }
903
904         return OPERATOR_CANCELLED | OPERATOR_PASS_THROUGH;
905 }
906
907 void NODE_OT_links_cut(wmOperatorType *ot)
908 {
909         PropertyRNA *prop;
910
911         ot->name = "Cut links";
912         ot->idname = "NODE_OT_links_cut";
913         ot->description = "Use the mouse to cut (remove) some links";
914
915         ot->invoke = WM_gesture_lines_invoke;
916         ot->modal = WM_gesture_lines_modal;
917         ot->exec = cut_links_exec;
918         ot->cancel = WM_gesture_lines_cancel;
919
920         ot->poll = ED_operator_node_active;
921
922         /* flags */
923         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
924
925         prop = RNA_def_property(ot->srna, "path", PROP_COLLECTION, PROP_NONE);
926         RNA_def_property_struct_runtime(prop, &RNA_OperatorMousePath);
927         /* internal */
928         RNA_def_int(ot->srna, "cursor", BC_KNIFECURSOR, 0, INT_MAX, "Cursor", "", 0, INT_MAX);
929 }
930
931 /* ********************** Detach links operator ***************** */
932
933 static int detach_links_exec(bContext *C, wmOperator *UNUSED(op))
934 {
935         SpaceNode *snode = CTX_wm_space_node(C);
936         bNodeTree *ntree = snode->edittree;
937         bNode *node;
938
939         ED_preview_kill_jobs(C);
940
941         for (node = ntree->nodes.first; node; node = node->next) {
942                 if (node->flag & SELECT) {
943                         nodeInternalRelink(ntree, node);
944                 }
945         }
946
947         ntreeUpdateTree(ntree);
948
949         snode_notify(C, snode);
950         snode_dag_update(C, snode);
951
952         return OPERATOR_FINISHED;
953 }
954
955 void NODE_OT_links_detach(wmOperatorType *ot)
956 {
957         ot->name = "Detach Links";
958         ot->idname = "NODE_OT_links_detach";
959         ot->description = "Remove all links to selected nodes, and try to connect neighbor nodes together";
960
961         ot->exec = detach_links_exec;
962         ot->poll = ED_operator_node_active;
963
964         /* flags */
965         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
966 }
967
968
969 /* ****************** Show Cyclic Dependencies Operator  ******************* */
970
971 static int node_show_cycles_exec(bContext *C, wmOperator *UNUSED(op))
972 {
973         SpaceNode *snode = CTX_wm_space_node(C);
974
975         /* this is just a wrapper around this call... */
976         ntreeUpdateTree(snode->nodetree);
977         snode_notify(C, snode);
978
979         return OPERATOR_FINISHED;
980 }
981
982 void NODE_OT_show_cyclic_dependencies(wmOperatorType *ot)
983 {
984         /* identifiers */
985         ot->name = "Show Cyclic Dependencies";
986         ot->description = "Sort the nodes and show the cyclic dependencies between the nodes";
987         ot->idname = "NODE_OT_show_cyclic_dependencies";
988
989         /* callbacks */
990         ot->exec = node_show_cycles_exec;
991         ot->poll = ED_operator_node_active;
992
993         /* flags */
994         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
995 }
996
997 /* ****************** Set Parent ******************* */
998
999 static int node_parent_set_exec(bContext *C, wmOperator *UNUSED(op))
1000 {
1001         SpaceNode *snode = CTX_wm_space_node(C);
1002         bNodeTree *ntree = snode->edittree;
1003         bNode *frame = nodeGetActive(ntree), *node;
1004         if (!frame || frame->type != NODE_FRAME)
1005                 return OPERATOR_CANCELLED;
1006
1007         for (node = ntree->nodes.first; node; node = node->next) {
1008                 if (node == frame)
1009                         continue;
1010                 if (node->flag & NODE_SELECT) {
1011                         nodeDetachNode(node);
1012                         nodeAttachNode(node, frame);
1013                 }
1014         }
1015
1016         ED_node_sort(ntree);
1017         WM_event_add_notifier(C, NC_NODE | ND_DISPLAY, NULL);
1018
1019         return OPERATOR_FINISHED;
1020 }
1021
1022 void NODE_OT_parent_set(wmOperatorType *ot)
1023 {
1024         /* identifiers */
1025         ot->name = "Make Parent";
1026         ot->description = "Attach selected nodes";
1027         ot->idname = "NODE_OT_parent_set";
1028
1029         /* api callbacks */
1030         ot->exec = node_parent_set_exec;
1031         ot->poll = ED_operator_node_active;
1032
1033         /* flags */
1034         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
1035 }
1036
1037 /* ****************** Clear Parent ******************* */
1038
1039 static int node_parent_clear_exec(bContext *C, wmOperator *UNUSED(op))
1040 {
1041         SpaceNode *snode = CTX_wm_space_node(C);
1042         bNodeTree *ntree = snode->edittree;
1043         bNode *node;
1044
1045         for (node = ntree->nodes.first; node; node = node->next) {
1046                 if (node->flag & NODE_SELECT) {
1047                         nodeDetachNode(node);
1048                 }
1049         }
1050
1051         WM_event_add_notifier(C, NC_NODE | ND_DISPLAY, NULL);
1052
1053         return OPERATOR_FINISHED;
1054 }
1055
1056 void NODE_OT_parent_clear(wmOperatorType *ot)
1057 {
1058         /* identifiers */
1059         ot->name = "Clear Parent";
1060         ot->description = "Detach selected nodes";
1061         ot->idname = "NODE_OT_parent_clear";
1062
1063         /* api callbacks */
1064         ot->exec = node_parent_clear_exec;
1065         ot->poll = ED_operator_node_active;
1066
1067         /* flags */
1068         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
1069 }
1070
1071 /* ****************** Join Nodes ******************* */
1072
1073 /* tags for depth-first search */
1074 #define NODE_JOIN_DONE          1
1075 #define NODE_JOIN_IS_DESCENDANT 2
1076
1077 static void node_join_attach_recursive(bNode *node, bNode *frame)
1078 {
1079         node->done |= NODE_JOIN_DONE;
1080
1081         if (node == frame) {
1082                 node->done |= NODE_JOIN_IS_DESCENDANT;
1083         }
1084         else if (node->parent) {
1085                 /* call recursively */
1086                 if (!(node->parent->done & NODE_JOIN_DONE))
1087                         node_join_attach_recursive(node->parent, frame);
1088
1089                 /* in any case: if the parent is a descendant, so is the child */
1090                 if (node->parent->done & NODE_JOIN_IS_DESCENDANT)
1091                         node->done |= NODE_JOIN_IS_DESCENDANT;
1092                 else if (node->flag & NODE_TEST) {
1093                         /* if parent is not an decendant of the frame, reattach the node */
1094                         nodeDetachNode(node);
1095                         nodeAttachNode(node, frame);
1096                         node->done |= NODE_JOIN_IS_DESCENDANT;
1097                 }
1098         }
1099         else if (node->flag & NODE_TEST) {
1100                 nodeAttachNode(node, frame);
1101                 node->done |= NODE_JOIN_IS_DESCENDANT;
1102         }
1103 }
1104
1105 static int node_join_exec(bContext *C, wmOperator *UNUSED(op))
1106 {
1107         SpaceNode *snode = CTX_wm_space_node(C);
1108         Main *bmain = CTX_data_main(C);
1109         Scene *scene = CTX_data_scene(C);
1110         bNodeTree *ntree = snode->edittree;
1111         bNode *node, *frame;
1112         bNodeTemplate ntemp;
1113
1114         /* XXX save selection: node_add_node call below sets the new frame as single active+selected node */
1115         for (node = ntree->nodes.first; node; node = node->next) {
1116                 if (node->flag & NODE_SELECT)
1117                         node->flag |= NODE_TEST;
1118                 else
1119                         node->flag &= ~NODE_TEST;
1120         }
1121
1122         ntemp.main = bmain;
1123         ntemp.scene = scene;
1124         ntemp.type = NODE_FRAME;
1125         frame = node_add_node(snode, bmain, scene, &ntemp, 0.0f, 0.0f);
1126
1127         /* reset tags */
1128         for (node = ntree->nodes.first; node; node = node->next)
1129                 node->done = 0;
1130
1131         for (node = ntree->nodes.first; node; node = node->next) {
1132                 if (!(node->done & NODE_JOIN_DONE))
1133                         node_join_attach_recursive(node, frame);
1134         }
1135
1136         /* restore selection */
1137         for (node = ntree->nodes.first; node; node = node->next) {
1138                 if (node->flag & NODE_TEST)
1139                         node->flag |= NODE_SELECT;
1140         }
1141
1142         ED_node_sort(ntree);
1143         WM_event_add_notifier(C, NC_NODE | ND_DISPLAY, NULL);
1144
1145         return OPERATOR_FINISHED;
1146 }
1147
1148 void NODE_OT_join(wmOperatorType *ot)
1149 {
1150         /* identifiers */
1151         ot->name = "Join Nodes";
1152         ot->description = "Attach selected nodes to a new common frame";
1153         ot->idname = "NODE_OT_join";
1154
1155         /* api callbacks */
1156         ot->exec = node_join_exec;
1157         ot->poll = ED_operator_node_active;
1158
1159         /* flags */
1160         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
1161 }
1162
1163 /* ****************** Attach ******************* */
1164
1165 static int node_attach_exec(bContext *C, wmOperator *UNUSED(op))
1166 {
1167         SpaceNode *snode = CTX_wm_space_node(C);
1168         bNodeTree *ntree = snode->edittree;
1169         bNode *frame;
1170
1171         /* check nodes front to back */
1172         for (frame = ntree->nodes.last; frame; frame = frame->prev) {
1173                 /* skip selected, those are the nodes we want to attach */
1174                 if ((frame->type != NODE_FRAME) || (frame->flag & NODE_SELECT))
1175                         continue;
1176                 if (BLI_in_rctf(&frame->totr, snode->mx, snode->my))
1177                         break;
1178         }
1179         if (frame) {
1180                 bNode *node, *parent;
1181                 for (node = ntree->nodes.last; node; node = node->prev) {
1182                         if (node->flag & NODE_SELECT) {
1183                                 if (node->parent == NULL) {
1184                                         /* attach all unparented nodes */
1185                                         nodeAttachNode(node, frame);
1186                                 }
1187                                 else {
1188                                         /* attach nodes which share parent with the frame */
1189                                         for (parent = frame->parent; parent; parent = parent->parent)
1190                                                 if (parent == node->parent)
1191                                                         break;
1192                                         if (parent) {
1193                                                 nodeDetachNode(node);
1194                                                 nodeAttachNode(node, frame);
1195                                         }
1196                                 }
1197                         }
1198                 }
1199         }
1200
1201         ED_node_sort(ntree);
1202         WM_event_add_notifier(C, NC_NODE | ND_DISPLAY, NULL);
1203
1204         return OPERATOR_FINISHED;
1205 }
1206
1207 static int node_attach_invoke(bContext *C, wmOperator *op, wmEvent *event)
1208 {
1209         ARegion *ar = CTX_wm_region(C);
1210         SpaceNode *snode = CTX_wm_space_node(C);
1211
1212         /* convert mouse coordinates to v2d space */
1213         UI_view2d_region_to_view(&ar->v2d, event->mval[0], event->mval[1], &snode->mx, &snode->my);
1214
1215         return node_attach_exec(C, op);
1216 }
1217
1218 void NODE_OT_attach(wmOperatorType *ot)
1219 {
1220         /* identifiers */
1221         ot->name = "Attach Nodes";
1222         ot->description = "Attach active node to a frame";
1223         ot->idname = "NODE_OT_attach";
1224
1225         /* api callbacks */
1226         ot->exec = node_attach_exec;
1227         ot->invoke = node_attach_invoke;
1228         ot->poll = ED_operator_node_active;
1229
1230         /* flags */
1231         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
1232 }
1233
1234 /* ****************** Detach ******************* */
1235
1236 /* tags for depth-first search */
1237 #define NODE_DETACH_DONE            1
1238 #define NODE_DETACH_IS_DESCENDANT   2
1239
1240 static void node_detach_recursive(bNode *node)
1241 {
1242         node->done |= NODE_DETACH_DONE;
1243
1244         if (node->parent) {
1245                 /* call recursively */
1246                 if (!(node->parent->done & NODE_DETACH_DONE))
1247                         node_detach_recursive(node->parent);
1248
1249                 /* in any case: if the parent is a descendant, so is the child */
1250                 if (node->parent->done & NODE_DETACH_IS_DESCENDANT)
1251                         node->done |= NODE_DETACH_IS_DESCENDANT;
1252                 else if (node->flag & NODE_SELECT) {
1253                         /* if parent is not a decendant of a selected node, detach */
1254                         nodeDetachNode(node);
1255                         node->done |= NODE_DETACH_IS_DESCENDANT;
1256                 }
1257         }
1258         else if (node->flag & NODE_SELECT) {
1259                 node->done |= NODE_DETACH_IS_DESCENDANT;
1260         }
1261 }
1262
1263
1264 /* detach the root nodes in the current selection */
1265 static int node_detach_exec(bContext *C, wmOperator *UNUSED(op))
1266 {
1267         SpaceNode *snode = CTX_wm_space_node(C);
1268         bNodeTree *ntree = snode->edittree;
1269         bNode *node;
1270
1271         /* reset tags */
1272         for (node = ntree->nodes.first; node; node = node->next)
1273                 node->done = 0;
1274         /* detach nodes recursively
1275          * relative order is preserved here!
1276          */
1277         for (node = ntree->nodes.first; node; node = node->next) {
1278                 if (!(node->done & NODE_DETACH_DONE))
1279                         node_detach_recursive(node);
1280         }
1281
1282         ED_node_sort(ntree);
1283         WM_event_add_notifier(C, NC_NODE | ND_DISPLAY, NULL);
1284
1285         return OPERATOR_FINISHED;
1286 }
1287
1288 void NODE_OT_detach(wmOperatorType *ot)
1289 {
1290         /* identifiers */
1291         ot->name = "Detach Nodes";
1292         ot->description = "Detach selected nodes from parents";
1293         ot->idname = "NODE_OT_detach";
1294
1295         /* api callbacks */
1296         ot->exec = node_detach_exec;
1297         ot->poll = ED_operator_node_active;
1298
1299         /* flags */
1300         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
1301 }
1302
1303 /* *********************  automatic node insert on dragging ******************* */
1304
1305
1306 /* prevent duplicate testing code below */
1307 static SpaceNode *ed_node_link_conditions(ScrArea *sa, bNode **select)
1308 {
1309         SpaceNode *snode = sa ? sa->spacedata.first : NULL;
1310         bNode *node;
1311         bNodeLink *link;
1312
1313         /* no unlucky accidents */
1314         if (sa == NULL || sa->spacetype != SPACE_NODE) return NULL;
1315
1316         *select = NULL;
1317
1318         for (node = snode->edittree->nodes.first; node; node = node->next) {
1319                 if (node->flag & SELECT) {
1320                         if (*select)
1321                                 break;
1322                         else
1323                                 *select = node;
1324                 }
1325         }
1326         /* only one selected */
1327         if (node || *select == NULL) return NULL;
1328
1329         /* correct node */
1330         if ((*select)->inputs.first == NULL || (*select)->outputs.first == NULL) return NULL;
1331
1332         /* test node for links */
1333         for (link = snode->edittree->links.first; link; link = link->next) {
1334                 if (link->tonode == *select || link->fromnode == *select)
1335                         return NULL;
1336         }
1337
1338         return snode;
1339 }
1340
1341 /* test == 0, clear all intersect flags */
1342 void ED_node_link_intersect_test(ScrArea *sa, int test)
1343 {
1344         bNode *select;
1345         SpaceNode *snode = ed_node_link_conditions(sa, &select);
1346         bNodeLink *link, *selink = NULL;
1347         float mcoords[6][2];
1348
1349         if (snode == NULL) return;
1350
1351         /* clear flags */
1352         for (link = snode->edittree->links.first; link; link = link->next)
1353                 link->flag &= ~NODE_LINKFLAG_HILITE;
1354
1355         if (test == 0) return;
1356
1357         /* okay, there's 1 node, without links, now intersect */
1358         mcoords[0][0] = select->totr.xmin;
1359         mcoords[0][1] = select->totr.ymin;
1360         mcoords[1][0] = select->totr.xmax;
1361         mcoords[1][1] = select->totr.ymin;
1362         mcoords[2][0] = select->totr.xmax;
1363         mcoords[2][1] = select->totr.ymax;
1364         mcoords[3][0] = select->totr.xmin;
1365         mcoords[3][1] = select->totr.ymax;
1366         mcoords[4][0] = select->totr.xmin;
1367         mcoords[4][1] = select->totr.ymin;
1368         mcoords[5][0] = select->totr.xmax;
1369         mcoords[5][1] = select->totr.ymax;
1370
1371         /* we only tag a single link for intersect now */
1372         /* idea; use header dist when more? */
1373         for (link = snode->edittree->links.first; link; link = link->next) {
1374
1375                 if (cut_links_intersect(link, mcoords, 5)) { /* intersect code wants edges */
1376                         if (selink)
1377                                 break;
1378                         selink = link;
1379                 }
1380         }
1381
1382         if (link == NULL && selink)
1383                 selink->flag |= NODE_LINKFLAG_HILITE;
1384 }
1385
1386 /* assumes sockets in list */
1387 static bNodeSocket *socket_best_match(ListBase *sockets)
1388 {
1389         bNodeSocket *sock;
1390         int type, maxtype = 0;
1391
1392         /* find type range */
1393         for (sock = sockets->first; sock; sock = sock->next)
1394                 maxtype = MAX2(sock->type, maxtype);
1395
1396         /* try all types, starting from 'highest' (i.e. colors, vectors, values) */
1397         for (type = maxtype; type >= 0; --type) {
1398                 for (sock = sockets->first; sock; sock = sock->next) {
1399                         if (!nodeSocketIsHidden(sock) && type == sock->type) {
1400                                 return sock;
1401                         }
1402                 }
1403         }
1404
1405         /* no visible sockets, unhide first of highest type */
1406         for (type = maxtype; type >= 0; --type) {
1407                 for (sock = sockets->first; sock; sock = sock->next) {
1408                         if (type == sock->type) {
1409                                 sock->flag &= ~SOCK_HIDDEN;
1410                                 return sock;
1411                         }
1412                 }
1413         }
1414
1415         return NULL;
1416 }
1417
1418 /* assumes link with NODE_LINKFLAG_HILITE set */
1419 void ED_node_link_insert(ScrArea *sa)
1420 {
1421         bNode *node, *select;
1422         SpaceNode *snode = ed_node_link_conditions(sa, &select);
1423         bNodeLink *link;
1424         bNodeSocket *sockto;
1425
1426         if (snode == NULL) return;
1427
1428         /* get the link */
1429         for (link = snode->edittree->links.first; link; link = link->next)
1430                 if (link->flag & NODE_LINKFLAG_HILITE)
1431                         break;
1432
1433         if (link) {
1434                 node = link->tonode;
1435                 sockto = link->tosock;
1436
1437                 link->tonode = select;
1438                 link->tosock = socket_best_match(&select->inputs);
1439                 link->flag &= ~NODE_LINKFLAG_HILITE;
1440
1441                 nodeAddLink(snode->edittree, select, socket_best_match(&select->outputs), node, sockto);
1442                 ntreeUpdateTree(snode->edittree);   /* needed for pointers */
1443                 snode_update(snode, select);
1444                 ED_node_changed_update(snode->id, select);
1445         }
1446 }