Cleanup: spelling
[blender-staging.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 <ctype.h>
33
34 #include "MEM_guardedalloc.h"
35
36 #include "DNA_node_types.h"
37
38 #include "BLI_math.h"
39 #include "BLI_blenlib.h"
40 #include "BLI_easing.h"
41
42 #include "BKE_context.h"
43 #include "BKE_global.h"
44 #include "BKE_node.h"
45
46 #include "ED_node.h"  /* own include */
47 #include "ED_screen.h"
48 #include "ED_render.h"
49 #include "ED_util.h"
50
51 #include "RNA_access.h"
52 #include "RNA_define.h"
53
54 #include "WM_api.h"
55 #include "WM_types.h"
56
57 #include "UI_view2d.h"
58 #include "UI_resources.h"
59
60 #include "BLT_translation.h"
61
62 #include "node_intern.h"  /* own include */
63
64 /* ****************** Add *********************** */
65
66
67 typedef struct bNodeListItem {
68         struct bNodeListItem *next, *prev;
69         struct bNode *node;
70 } bNodeListItem;
71
72 typedef struct NodeInsertOfsData {
73         bNodeTree *ntree;
74         bNode *insert;        /* inserted node */
75         bNode *prev, *next;   /* prev/next node in the chain */
76         bNode *insert_parent;
77
78         wmTimer *anim_timer;
79
80         float offset_x;       /* offset to apply to node chain */
81 } NodeInsertOfsData;
82
83 static int sort_nodes_locx(const void *a, const void *b)
84 {
85         const bNodeListItem *nli1 = a;
86         const bNodeListItem *nli2 = b;
87         const bNode *node1 = nli1->node;
88         const bNode *node2 = nli2->node;
89
90         if (node1->locx > node2->locx)
91                 return 1;
92         else
93                 return 0;
94 }
95
96 static bool socket_is_available(bNodeTree *UNUSED(ntree), bNodeSocket *sock, const bool allow_used)
97 {
98         if (nodeSocketIsHidden(sock))
99                 return 0;
100
101         if (!allow_used && (sock->flag & SOCK_IN_USE))
102                 return 0;
103
104         return 1;
105 }
106
107 static bNodeSocket *best_socket_output(bNodeTree *ntree, bNode *node, bNodeSocket *sock_target, const bool allow_multiple)
108 {
109         bNodeSocket *sock;
110
111         /* first look for selected output */
112         for (sock = node->outputs.first; sock; sock = sock->next) {
113                 if (!socket_is_available(ntree, sock, allow_multiple))
114                         continue;
115
116                 if (sock->flag & SELECT)
117                         return sock;
118         }
119
120         /* try to find a socket with a matching name */
121         for (sock = node->outputs.first; sock; sock = sock->next) {
122                 if (!socket_is_available(ntree, sock, allow_multiple))
123                         continue;
124
125                 /* check for same types */
126                 if (sock->type == sock_target->type) {
127                         if (STREQ(sock->name, sock_target->name))
128                                 return sock;
129                 }
130         }
131
132         /* otherwise settle for the first available socket of the right type */
133         for (sock = node->outputs.first; sock; sock = sock->next) {
134
135                 if (!socket_is_available(ntree, sock, allow_multiple))
136                         continue;
137
138                 /* check for same types */
139                 if (sock->type == sock_target->type) {
140                         return sock;
141                 }
142         }
143
144         return NULL;
145 }
146
147 /* this is a bit complicated, but designed to prioritize finding
148  * sockets of higher types, such as image, first */
149 static bNodeSocket *best_socket_input(bNodeTree *ntree, bNode *node, int num, int replace)
150 {
151         bNodeSocket *sock;
152         int socktype, maxtype = 0;
153         int a = 0;
154
155         for (sock = node->inputs.first; sock; sock = sock->next) {
156                 maxtype = max_ii(sock->type, maxtype);
157         }
158
159         /* find sockets of higher 'types' first (i.e. image) */
160         for (socktype = maxtype; socktype >= 0; socktype--) {
161                 for (sock = node->inputs.first; sock; sock = sock->next) {
162
163                         if (!socket_is_available(ntree, sock, replace)) {
164                                 a++;
165                                 continue;
166                         }
167
168                         if (sock->type == socktype) {
169                                 /* increment to make sure we don't keep finding
170                                  * the same socket on every attempt running this function */
171                                 a++;
172                                 if (a > num)
173                                         return sock;
174                         }
175                 }
176         }
177
178         return NULL;
179 }
180
181 static int snode_autoconnect_input(SpaceNode *snode, bNode *node_fr, bNodeSocket *sock_fr, bNode *node_to, bNodeSocket *sock_to, int replace)
182 {
183         bNodeTree *ntree = snode->edittree;
184         bNodeLink *link;
185
186         /* then we can connect */
187         if (replace)
188                 nodeRemSocketLinks(ntree, sock_to);
189
190         link = nodeAddLink(ntree, node_fr, sock_fr, node_to, sock_to);
191         /* validate the new link */
192         ntreeUpdateTree(G.main, ntree);
193         if (!(link->flag & NODE_LINK_VALID)) {
194                 nodeRemLink(ntree, link);
195                 return 0;
196         }
197
198         snode_update(snode, node_to);
199         return 1;
200 }
201
202 static void snode_autoconnect(SpaceNode *snode, const bool allow_multiple, const bool replace)
203 {
204         bNodeTree *ntree = snode->edittree;
205         ListBase *nodelist = MEM_callocN(sizeof(ListBase), "items_list");
206         bNodeListItem *nli;
207         bNode *node;
208         int i, numlinks = 0;
209
210         for (node = ntree->nodes.first; node; node = node->next) {
211                 if (node->flag & NODE_SELECT) {
212                         nli = MEM_mallocN(sizeof(bNodeListItem), "temporary node list item");
213                         nli->node = node;
214                         BLI_addtail(nodelist, nli);
215                 }
216         }
217
218         /* sort nodes left to right */
219         BLI_listbase_sort(nodelist, sort_nodes_locx);
220
221         for (nli = nodelist->first; nli; nli = nli->next) {
222                 bNode *node_fr, *node_to;
223                 bNodeSocket *sock_fr, *sock_to;
224                 bool has_selected_inputs = false;
225
226                 if (nli->next == NULL) break;
227
228                 node_fr = nli->node;
229                 node_to = nli->next->node;
230
231                 /* if there are selected sockets, connect those */
232                 for (sock_to = node_to->inputs.first; sock_to; sock_to = sock_to->next) {
233                         if (sock_to->flag & SELECT) {
234                                 has_selected_inputs = 1;
235
236                                 if (!socket_is_available(ntree, sock_to, replace))
237                                         continue;
238
239                                 /* check for an appropriate output socket to connect from */
240                                 sock_fr = best_socket_output(ntree, node_fr, sock_to, allow_multiple);
241                                 if (!sock_fr)
242                                         continue;
243
244                                 if (snode_autoconnect_input(snode, node_fr, sock_fr, node_to, sock_to, replace)) {
245                                         numlinks++;
246                                 }
247                         }
248                 }
249
250                 if (!has_selected_inputs) {
251                         /* no selected inputs, connect by finding suitable match */
252                         int num_inputs = BLI_listbase_count(&node_to->inputs);
253
254                         for (i = 0; i < num_inputs; i++) {
255
256                                 /* find the best guess input socket */
257                                 sock_to = best_socket_input(ntree, node_to, i, replace);
258                                 if (!sock_to)
259                                         continue;
260
261                                 /* check for an appropriate output socket to connect from */
262                                 sock_fr = best_socket_output(ntree, node_fr, sock_to, allow_multiple);
263                                 if (!sock_fr)
264                                         continue;
265
266                                 if (snode_autoconnect_input(snode, node_fr, sock_fr, node_to, sock_to, replace)) {
267                                         numlinks++;
268                                         break;
269                                 }
270                         }
271                 }
272         }
273
274         if (numlinks > 0) {
275                 ntreeUpdateTree(G.main, ntree);
276         }
277
278         BLI_freelistN(nodelist);
279         MEM_freeN(nodelist);
280 }
281
282 /* *************************** link viewer op ******************** */
283
284 static int node_link_viewer(const bContext *C, bNode *tonode)
285 {
286         SpaceNode *snode = CTX_wm_space_node(C);
287         bNode *node;
288         bNodeLink *link;
289         bNodeSocket *sock;
290
291         /* context check */
292         if (tonode == NULL || BLI_listbase_is_empty(&tonode->outputs))
293                 return OPERATOR_CANCELLED;
294         if (ELEM(tonode->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER))
295                 return OPERATOR_CANCELLED;
296
297         /* get viewer */
298         for (node = snode->edittree->nodes.first; node; node = node->next)
299                 if (ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER))
300                         if (node->flag & NODE_DO_OUTPUT)
301                                 break;
302         /* no viewer, we make one active */
303         if (node == NULL) {
304                 for (node = snode->edittree->nodes.first; node; node = node->next) {
305                         if (ELEM(node->type, CMP_NODE_VIEWER, CMP_NODE_SPLITVIEWER)) {
306                                 node->flag |= NODE_DO_OUTPUT;
307                                 break;
308                         }
309                 }
310         }
311
312         sock = NULL;
313
314         /* try to find an already connected socket to cycle to the next */
315         if (node) {
316                 link = NULL;
317                 for (link = snode->edittree->links.first; link; link = link->next)
318                         if (link->tonode == node && link->fromnode == tonode)
319                                 if (link->tosock == node->inputs.first)
320                                         break;
321                 if (link) {
322                         /* unlink existing connection */
323                         sock = link->fromsock;
324                         nodeRemLink(snode->edittree, link);
325
326                         /* find a socket after the previously connected socket */
327                         for (sock = sock->next; sock; sock = sock->next)
328                                 if (!nodeSocketIsHidden(sock))
329                                         break;
330                 }
331         }
332
333         /* find a socket starting from the first socket */
334         if (!sock) {
335                 for (sock = tonode->outputs.first; sock; sock = sock->next)
336                         if (!nodeSocketIsHidden(sock))
337                                 break;
338         }
339
340         if (sock) {
341                 /* add a new viewer if none exists yet */
342                 if (!node) {
343                         /* XXX location is a quick hack, just place it next to the linked socket */
344                         node = node_add_node(C, NULL, CMP_NODE_VIEWER, sock->locx + 100, sock->locy);
345                         if (!node)
346                                 return OPERATOR_CANCELLED;
347
348                         link = NULL;
349                 }
350                 else {
351                         /* get link to viewer */
352                         for (link = snode->edittree->links.first; link; link = link->next)
353                                 if (link->tonode == node && link->tosock == node->inputs.first)
354                                         break;
355                 }
356
357                 if (link == NULL) {
358                         nodeAddLink(snode->edittree, tonode, sock, node, node->inputs.first);
359                 }
360                 else {
361                         link->fromnode = tonode;
362                         link->fromsock = sock;
363                         /* make sure the dependency sorting is updated */
364                         snode->edittree->update |= NTREE_UPDATE_LINKS;
365                 }
366                 ntreeUpdateTree(CTX_data_main(C), snode->edittree);
367                 snode_update(snode, node);
368         }
369
370         return OPERATOR_FINISHED;
371 }
372
373
374 static int node_active_link_viewer_exec(bContext *C, wmOperator *UNUSED(op))
375 {
376         SpaceNode *snode = CTX_wm_space_node(C);
377         bNode *node;
378
379         node = nodeGetActive(snode->edittree);
380
381         if (!node)
382                 return OPERATOR_CANCELLED;
383
384         ED_preview_kill_jobs(CTX_wm_manager(C), CTX_data_main(C));
385
386         if (node_link_viewer(C, node) == OPERATOR_CANCELLED)
387                 return OPERATOR_CANCELLED;
388
389         snode_notify(C, snode);
390
391         return OPERATOR_FINISHED;
392 }
393
394
395 void NODE_OT_link_viewer(wmOperatorType *ot)
396 {
397         /* identifiers */
398         ot->name = "Link to Viewer Node";
399         ot->description = "Link to viewer node";
400         ot->idname = "NODE_OT_link_viewer";
401
402         /* api callbacks */
403         ot->exec = node_active_link_viewer_exec;
404         ot->poll = composite_node_editable;
405
406         /* flags */
407         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
408 }
409
410
411 /* *************************** add link op ******************** */
412
413 static void node_link_update_header(bContext *C, bNodeLinkDrag *UNUSED(nldrag))
414 {
415 #define HEADER_LENGTH 256
416         char header[HEADER_LENGTH];
417
418         BLI_strncpy(header, IFACE_("LMB: drag node link, RMB: cancel"), HEADER_LENGTH);
419         ED_area_headerprint(CTX_wm_area(C), header);
420 #undef HEADER_LENGTH
421 }
422
423 /* update link_count fields to avoid repeated link counting */
424 static int node_count_links(bNodeTree *ntree, bNodeSocket *sock)
425 {
426         bNodeLink *link;
427         int count = 0;
428         for (link = ntree->links.first; link; link = link->next) {
429                 if (link->fromsock == sock)
430                         ++count;
431                 if (link->tosock == sock)
432                         ++count;
433         }
434         return count;
435 }
436
437 /* test if two sockets are interchangeable
438  * XXX this could be made into a tree-type callback for flexibility
439  */
440 static bool node_link_socket_match(bNodeSocket *a, bNodeSocket *b)
441 {
442         /* tests if alphabetic prefix matches
443          * this allows for imperfect matches, such as numeric suffixes,
444          * like Color1/Color2
445          */
446         int prefix_len = 0;
447         char *ca = a->name, *cb = b->name;
448         for (; *ca != '\0' && *cb != '\0'; ++ca, ++cb) {
449                 /* end of common prefix? */
450                 if (*ca != *cb) {
451                         /* prefix delimited by non-alphabetic char */
452                         if (isalpha(*ca) || isalpha(*cb))
453                                 return false;
454                         break;
455                 }
456                 ++prefix_len;
457         }
458         return prefix_len > 0;
459 }
460
461 /* find an eligible socket for linking */
462 static bNodeSocket *node_find_linkable_socket(bNodeTree *ntree, bNode *node, bNodeSocket *cur, bool use_swap)
463 {
464         int cur_link_count = node_count_links(ntree, cur);
465         if (cur_link_count <= cur->limit) {
466                 /* current socket is fine, use it */
467                 return cur;
468         }
469         else if (use_swap) {
470                 /* link swapping: try to find a free slot with a matching name */
471                 
472                 bNodeSocket *first = cur->in_out == SOCK_IN ? node->inputs.first : node->outputs.first;
473                 bNodeSocket *sock;
474                 
475                 sock = cur->next ? cur->next : first; /* wrap around the list end */
476                 while (sock != cur) {
477                         if (!nodeSocketIsHidden(sock) && node_link_socket_match(sock, cur)) {
478                                 int link_count = node_count_links(ntree, sock);
479                                 /* take +1 into account since we would add a new link */
480                                 if (link_count + 1 <= sock->limit)
481                                         return sock; /* found a valid free socket we can swap to */
482                         }
483                         
484                         sock = sock->next ? sock->next : first; /* wrap around the list end */
485                 }
486         }
487         return NULL;
488 }
489
490 static void node_remove_extra_links(SpaceNode *snode, bNodeLink *link, bool use_swap)
491 {
492         bNodeTree *ntree = snode->edittree;
493         bNodeSocket *from = link->fromsock, *to = link->tosock;
494         bNodeLink *tlink, *tlink_next;
495         
496         for (tlink = ntree->links.first; tlink; tlink = tlink_next) {
497                 tlink_next = tlink->next;
498                 if (tlink == link)
499                         continue;
500                 
501                 if (tlink && tlink->fromsock == from) {
502                         bNodeSocket *new_from = node_find_linkable_socket(ntree, tlink->fromnode, from, use_swap);
503                         if (new_from && new_from != from) {
504                                 /* redirect existing link */
505                                 tlink->fromsock = new_from;
506                         }
507                         else if (!new_from) {
508                                 /* no possible replacement, remove tlink */
509                                 nodeRemLink(ntree, tlink);
510                                 tlink = NULL;
511                         }
512                 }
513                 
514                 if (tlink && tlink->tosock == to) {
515                         bNodeSocket *new_to = node_find_linkable_socket(ntree, tlink->tonode, to, use_swap);
516                         if (new_to && new_to != to) {
517                                 /* redirect existing link */
518                                 tlink->tosock = new_to;
519                         }
520                         else if (!new_to) {
521                                 /* no possible replacement, remove tlink */
522                                 nodeRemLink(ntree, tlink);
523                                 tlink = NULL;
524                         }
525                 }
526         }
527 }
528
529 static void node_link_exit(bContext *C, wmOperator *op, bool apply_links)
530 {
531         SpaceNode *snode = CTX_wm_space_node(C);
532         bNodeTree *ntree = snode->edittree;
533         bNodeLinkDrag *nldrag = op->customdata;
534         LinkData *linkdata;
535         
536         for (linkdata = nldrag->links.first; linkdata; linkdata = linkdata->next) {
537                 bNodeLink *link = linkdata->data;
538                 
539                 if (apply_links && link->tosock && link->fromsock) {
540                         /* add link to the node tree */
541                         BLI_addtail(&ntree->links, link);
542                         
543                         ntree->update |= NTREE_UPDATE_LINKS;
544                         
545                         /* tag tonode for update */
546                         link->tonode->update |= NODE_UPDATE;
547                         
548                         /* we might need to remove a link */
549                         node_remove_extra_links(snode, link, true);
550                 }
551                 else
552                         nodeRemLink(ntree, link);
553         }
554         
555         ntreeUpdateTree(CTX_data_main(C), ntree);
556         snode_notify(C, snode);
557         snode_dag_update(C, snode);
558         
559         BLI_remlink(&snode->linkdrag, nldrag);
560         /* links->data pointers are either held by the tree or freed already */
561         BLI_freelistN(&nldrag->links);
562         MEM_freeN(nldrag);
563 }
564
565 static void node_link_find_socket(bContext *C, wmOperator *op, float cursor[2])
566 {
567         SpaceNode *snode = CTX_wm_space_node(C);
568         bNodeLinkDrag *nldrag = op->customdata;
569         bNode *tnode;
570         bNodeSocket *tsock = NULL;
571         LinkData *linkdata;
572
573         if (nldrag->in_out == SOCK_OUT) {
574                 if (node_find_indicated_socket(snode, &tnode, &tsock, cursor, SOCK_IN)) {
575                         for (linkdata = nldrag->links.first; linkdata; linkdata = linkdata->next) {
576                                 bNodeLink *link = linkdata->data;
577                                 
578                                 /* skip if this is already the target socket */
579                                 if (link->tosock == tsock)
580                                         continue;
581                                 /* skip if socket is on the same node as the fromsock */
582                                 if (tnode && link->fromnode == tnode)
583                                         continue;
584                                 
585                                 /* attach links to the socket */
586                                 link->tonode = tnode;
587                                 link->tosock = tsock;
588                         }
589                 }
590                 else {
591                         for (linkdata = nldrag->links.first; linkdata; linkdata = linkdata->next) {
592                                 bNodeLink *link = linkdata->data;
593                                 
594                                 link->tonode = NULL;
595                                 link->tosock = NULL;
596                         }
597                 }
598         }
599         else {
600                 if (node_find_indicated_socket(snode, &tnode, &tsock, cursor, SOCK_OUT)) {
601                         for (linkdata = nldrag->links.first; linkdata; linkdata = linkdata->next) {
602                                 bNodeLink *link = linkdata->data;
603                                 
604                                 /* skip if this is already the target socket */
605                                 if (link->fromsock == tsock)
606                                         continue;
607                                 /* skip if socket is on the same node as the fromsock */
608                                 if (tnode && link->tonode == tnode)
609                                         continue;
610                                 
611                                 /* attach links to the socket */
612                                 link->fromnode = tnode;
613                                 link->fromsock = tsock;
614                         }
615                 }
616                 else {
617                         for (linkdata = nldrag->links.first; linkdata; linkdata = linkdata->next) {
618                                 bNodeLink *link = linkdata->data;
619                                 
620                                 link->fromnode = NULL;
621                                 link->fromsock = NULL;
622                         }
623                 }
624         }
625 }
626
627 /* loop that adds a nodelink, called by function below  */
628 /* in_out = starting socket */
629 static int node_link_modal(bContext *C, wmOperator *op, const wmEvent *event)
630 {
631         bNodeLinkDrag *nldrag = op->customdata;
632         ARegion *ar = CTX_wm_region(C);
633         float cursor[2];
634         
635         UI_view2d_region_to_view(&ar->v2d, event->mval[0], event->mval[1],
636                                  &cursor[0], &cursor[1]);
637         
638         switch (event->type) {
639                 case MOUSEMOVE:
640                         node_link_find_socket(C, op, cursor);
641                         
642                         node_link_update_header(C, nldrag);
643                         ED_region_tag_redraw(ar);
644                         break;
645                         
646                 case LEFTMOUSE:
647                 case RIGHTMOUSE:
648                 case MIDDLEMOUSE:
649                 {
650                         node_link_exit(C, op, true);
651                         
652                         ED_area_headerprint(CTX_wm_area(C), NULL);
653                         ED_region_tag_redraw(ar);
654                         return OPERATOR_FINISHED;
655                 }
656         }
657         
658         return OPERATOR_RUNNING_MODAL;
659 }
660
661 /* return 1 when socket clicked */
662 static bNodeLinkDrag *node_link_init(SpaceNode *snode, float cursor[2], bool detach)
663 {
664         bNode *node;
665         bNodeSocket *sock;
666         bNodeLink *link, *link_next, *oplink;
667         bNodeLinkDrag *nldrag = NULL;
668         LinkData *linkdata;
669         int num_links;
670
671         /* output indicated? */
672         if (node_find_indicated_socket(snode, &node, &sock, cursor, SOCK_OUT)) {
673                 nldrag = MEM_callocN(sizeof(bNodeLinkDrag), "drag link op customdata");
674
675                 num_links = nodeCountSocketLinks(snode->edittree, sock);
676                 if (num_links > 0 && (num_links >= sock->limit || detach)) {
677                         /* dragged links are fixed on input side */
678                         nldrag->in_out = SOCK_IN;
679                         /* detach current links and store them in the operator data */
680                         for (link = snode->edittree->links.first; link; link = link_next) {
681                                 link_next = link->next;
682                                 if (link->fromsock == sock) {
683                                         linkdata = MEM_callocN(sizeof(LinkData), "drag link op link data");
684                                         linkdata->data = oplink = MEM_callocN(sizeof(bNodeLink), "drag link op link");
685                                         *oplink = *link;
686                                         oplink->next = oplink->prev = NULL;
687                                         oplink->flag |= NODE_LINK_VALID;
688                                         
689                                         BLI_addtail(&nldrag->links, linkdata);
690                                         nodeRemLink(snode->edittree, link);
691                                 }
692                         }
693                 }
694                 else {
695                         /* dragged links are fixed on output side */
696                         nldrag->in_out = SOCK_OUT;
697                         /* create a new link */
698                         linkdata = MEM_callocN(sizeof(LinkData), "drag link op link data");
699                         linkdata->data = oplink = MEM_callocN(sizeof(bNodeLink), "drag link op link");
700                         oplink->fromnode = node;
701                         oplink->fromsock = sock;
702                         oplink->flag |= NODE_LINK_VALID;
703                         
704                         BLI_addtail(&nldrag->links, linkdata);
705                 }
706         }
707         /* or an input? */
708         else if (node_find_indicated_socket(snode, &node, &sock, cursor, SOCK_IN)) {
709                 nldrag = MEM_callocN(sizeof(bNodeLinkDrag), "drag link op customdata");
710
711                 num_links = nodeCountSocketLinks(snode->edittree, sock);
712                 if (num_links > 0 && (num_links >= sock->limit || detach)) {
713                         /* dragged links are fixed on output side */
714                         nldrag->in_out = SOCK_OUT;
715                         /* detach current links and store them in the operator data */
716                         for (link = snode->edittree->links.first; link; link = link_next) {
717                                 link_next = link->next;
718                                 if (link->tosock == sock) {
719                                         linkdata = MEM_callocN(sizeof(LinkData), "drag link op link data");
720                                         linkdata->data = oplink = MEM_callocN(sizeof(bNodeLink), "drag link op link");
721                                         *oplink = *link;
722                                         oplink->next = oplink->prev = NULL;
723                                         oplink->flag |= NODE_LINK_VALID;
724                                         
725                                         BLI_addtail(&nldrag->links, linkdata);
726                                         nodeRemLink(snode->edittree, link);
727                                         
728                                         /* send changed event to original link->tonode */
729                                         if (node)
730                                                 snode_update(snode, node);
731                                 }
732                         }
733                 }
734                 else {
735                         /* dragged links are fixed on input side */
736                         nldrag->in_out = SOCK_IN;
737                         /* create a new link */
738                         linkdata = MEM_callocN(sizeof(LinkData), "drag link op link data");
739                         linkdata->data = oplink = MEM_callocN(sizeof(bNodeLink), "drag link op link");
740                         oplink->tonode = node;
741                         oplink->tosock = sock;
742                         oplink->flag |= NODE_LINK_VALID;
743                         
744                         BLI_addtail(&nldrag->links, linkdata);
745                 }
746         }
747         
748         return nldrag;
749 }
750
751 static int node_link_invoke(bContext *C, wmOperator *op, const wmEvent *event)
752 {
753         SpaceNode *snode = CTX_wm_space_node(C);
754         ARegion *ar = CTX_wm_region(C);
755         bNodeLinkDrag *nldrag;
756         float cursor[2];
757         
758         bool detach = RNA_boolean_get(op->ptr, "detach");
759
760         UI_view2d_region_to_view(&ar->v2d, event->mval[0], event->mval[1],
761                                  &cursor[0], &cursor[1]);
762
763         ED_preview_kill_jobs(CTX_wm_manager(C), CTX_data_main(C));
764
765         nldrag = node_link_init(snode, cursor, detach);
766
767         if (nldrag) {
768                 op->customdata = nldrag;
769                 BLI_addtail(&snode->linkdrag, nldrag);
770
771                 /* add modal handler */
772                 WM_event_add_modal_handler(C, op);
773
774                 return OPERATOR_RUNNING_MODAL;
775         }
776         else
777                 return OPERATOR_CANCELLED | OPERATOR_PASS_THROUGH;
778 }
779
780 static void node_link_cancel(bContext *C, wmOperator *op)
781 {
782         SpaceNode *snode = CTX_wm_space_node(C);
783         bNodeLinkDrag *nldrag = op->customdata;
784
785         BLI_remlink(&snode->linkdrag, nldrag);
786
787         BLI_freelistN(&nldrag->links);
788         MEM_freeN(nldrag);
789 }
790
791 void NODE_OT_link(wmOperatorType *ot)
792 {
793         /* identifiers */
794         ot->name = "Link Nodes";
795         ot->idname = "NODE_OT_link";
796         ot->description = "Use the mouse to create a link between two nodes";
797
798         /* api callbacks */
799         ot->invoke = node_link_invoke;
800         ot->modal = node_link_modal;
801 //      ot->exec = node_link_exec;
802         ot->poll = ED_operator_node_editable;
803         ot->cancel = node_link_cancel;
804
805         /* flags */
806         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO | OPTYPE_BLOCKING;
807
808         RNA_def_boolean(ot->srna, "detach", false, "Detach", "Detach and redirect existing links");
809 }
810
811 /* ********************** Make Link operator ***************** */
812
813 /* makes a link between selected output and input sockets */
814 static int node_make_link_exec(bContext *C, wmOperator *op)
815 {
816         SpaceNode *snode = CTX_wm_space_node(C);
817         const bool replace = RNA_boolean_get(op->ptr, "replace");
818
819         ED_preview_kill_jobs(CTX_wm_manager(C), CTX_data_main(C));
820
821         snode_autoconnect(snode, 1, replace);
822
823         /* deselect sockets after linking */
824         node_deselect_all_input_sockets(snode, 0);
825         node_deselect_all_output_sockets(snode, 0);
826
827         ntreeUpdateTree(CTX_data_main(C), snode->edittree);
828         snode_notify(C, snode);
829         snode_dag_update(C, snode);
830
831         return OPERATOR_FINISHED;
832 }
833
834 void NODE_OT_link_make(wmOperatorType *ot)
835 {
836         /* identifiers */
837         ot->name = "Make Links";
838         ot->description = "Makes a link between selected output in input sockets";
839         ot->idname = "NODE_OT_link_make";
840
841         /* callbacks */
842         ot->exec = node_make_link_exec;
843         ot->poll = ED_operator_node_editable; // XXX we need a special poll which checks that there are selected input/output sockets
844
845         /* flags */
846         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
847
848         RNA_def_boolean(ot->srna, "replace", 0, "Replace", "Replace socket connections with the new links");
849 }
850
851 /* ********************** Cut Link operator ***************** */
852 static int cut_links_intersect(bNodeLink *link, float mcoords[][2], int tot)
853 {
854         float coord_array[NODE_LINK_RESOL + 1][2];
855         int i, b;
856
857         if (node_link_bezier_points(NULL, NULL, link, coord_array, NODE_LINK_RESOL)) {
858
859                 for (i = 0; i < tot - 1; i++)
860                         for (b = 0; b < NODE_LINK_RESOL; b++)
861                                 if (isect_line_line_v2(mcoords[i], mcoords[i + 1], coord_array[b], coord_array[b + 1]) > 0)
862                                         return 1;
863         }
864         return 0;
865 }
866
867 static int cut_links_exec(bContext *C, wmOperator *op)
868 {
869         SpaceNode *snode = CTX_wm_space_node(C);
870         ARegion *ar = CTX_wm_region(C);
871         float mcoords[256][2];
872         int i = 0;
873
874         RNA_BEGIN (op->ptr, itemptr, "path")
875         {
876                 float loc[2];
877
878                 RNA_float_get_array(&itemptr, "loc", loc);
879                 UI_view2d_region_to_view(&ar->v2d, (int)loc[0], (int)loc[1],
880                                          &mcoords[i][0], &mcoords[i][1]);
881                 i++;
882                 if (i >= 256) break;
883         }
884         RNA_END;
885
886         if (i > 1) {
887                 bool found = false;
888                 bNodeLink *link, *next;
889                 
890                 ED_preview_kill_jobs(CTX_wm_manager(C), CTX_data_main(C));
891                 
892                 for (link = snode->edittree->links.first; link; link = next) {
893                         next = link->next;
894                         if (nodeLinkIsHidden(link))
895                                 continue;
896
897                         if (cut_links_intersect(link, mcoords, i)) {
898
899                                 if (found == false) {
900                                         /* TODO(sergey): Why did we kill jobs twice? */
901                                         ED_preview_kill_jobs(CTX_wm_manager(C), CTX_data_main(C));
902                                         found = true;
903                                 }
904
905                                 snode_update(snode, link->tonode);
906                                 nodeRemLink(snode->edittree, link);
907                         }
908                 }
909
910                 if (found) {
911                         ntreeUpdateTree(CTX_data_main(C), snode->edittree);
912                         snode_notify(C, snode);
913                         snode_dag_update(C, snode);
914
915                         return OPERATOR_FINISHED;
916                 }
917                 else {
918                         return OPERATOR_CANCELLED;
919                 }
920
921         }
922
923         return OPERATOR_CANCELLED | OPERATOR_PASS_THROUGH;
924 }
925
926 void NODE_OT_links_cut(wmOperatorType *ot)
927 {
928         PropertyRNA *prop;
929
930         ot->name = "Cut Links";
931         ot->idname = "NODE_OT_links_cut";
932         ot->description = "Use the mouse to cut (remove) some links";
933
934         ot->invoke = WM_gesture_lines_invoke;
935         ot->modal = WM_gesture_lines_modal;
936         ot->exec = cut_links_exec;
937         ot->cancel = WM_gesture_lines_cancel;
938
939         ot->poll = ED_operator_node_editable;
940
941         /* flags */
942         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
943
944         prop = RNA_def_property(ot->srna, "path", PROP_COLLECTION, PROP_NONE);
945         RNA_def_property_struct_runtime(prop, &RNA_OperatorMousePath);
946         /* internal */
947         RNA_def_int(ot->srna, "cursor", BC_KNIFECURSOR, 0, INT_MAX, "Cursor", "", 0, INT_MAX);
948 }
949
950 /* ********************** Detach links operator ***************** */
951
952 static int detach_links_exec(bContext *C, wmOperator *UNUSED(op))
953 {
954         SpaceNode *snode = CTX_wm_space_node(C);
955         bNodeTree *ntree = snode->edittree;
956         bNode *node;
957
958         ED_preview_kill_jobs(CTX_wm_manager(C), CTX_data_main(C));
959
960         for (node = ntree->nodes.first; node; node = node->next) {
961                 if (node->flag & SELECT) {
962                         nodeInternalRelink(ntree, node);
963                 }
964         }
965
966         ntreeUpdateTree(CTX_data_main(C), ntree);
967
968         snode_notify(C, snode);
969         snode_dag_update(C, snode);
970
971         return OPERATOR_FINISHED;
972 }
973
974 void NODE_OT_links_detach(wmOperatorType *ot)
975 {
976         ot->name = "Detach Links";
977         ot->idname = "NODE_OT_links_detach";
978         ot->description = "Remove all links to selected nodes, and try to connect neighbor nodes together";
979
980         ot->exec = detach_links_exec;
981         ot->poll = ED_operator_node_editable;
982
983         /* flags */
984         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
985 }
986
987
988 /* ****************** Set Parent ******************* */
989
990 static int node_parent_set_exec(bContext *C, wmOperator *UNUSED(op))
991 {
992         SpaceNode *snode = CTX_wm_space_node(C);
993         bNodeTree *ntree = snode->edittree;
994         bNode *frame = nodeGetActive(ntree), *node;
995         if (!frame || frame->type != NODE_FRAME)
996                 return OPERATOR_CANCELLED;
997
998         for (node = ntree->nodes.first; node; node = node->next) {
999                 if (node == frame)
1000                         continue;
1001                 if (node->flag & NODE_SELECT) {
1002                         nodeDetachNode(node);
1003                         nodeAttachNode(node, frame);
1004                 }
1005         }
1006
1007         ED_node_sort(ntree);
1008         WM_event_add_notifier(C, NC_NODE | ND_DISPLAY, NULL);
1009
1010         return OPERATOR_FINISHED;
1011 }
1012
1013 void NODE_OT_parent_set(wmOperatorType *ot)
1014 {
1015         /* identifiers */
1016         ot->name = "Make Parent";
1017         ot->description = "Attach selected nodes";
1018         ot->idname = "NODE_OT_parent_set";
1019
1020         /* api callbacks */
1021         ot->exec = node_parent_set_exec;
1022         ot->poll = ED_operator_node_editable;
1023
1024         /* flags */
1025         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
1026 }
1027
1028 /* ****************** Join Nodes ******************* */
1029
1030 /* tags for depth-first search */
1031 #define NODE_JOIN_DONE          1
1032 #define NODE_JOIN_IS_DESCENDANT 2
1033
1034 static void node_join_attach_recursive(bNode *node, bNode *frame)
1035 {
1036         node->done |= NODE_JOIN_DONE;
1037
1038         if (node == frame) {
1039                 node->done |= NODE_JOIN_IS_DESCENDANT;
1040         }
1041         else if (node->parent) {
1042                 /* call recursively */
1043                 if (!(node->parent->done & NODE_JOIN_DONE))
1044                         node_join_attach_recursive(node->parent, frame);
1045
1046                 /* in any case: if the parent is a descendant, so is the child */
1047                 if (node->parent->done & NODE_JOIN_IS_DESCENDANT)
1048                         node->done |= NODE_JOIN_IS_DESCENDANT;
1049                 else if (node->flag & NODE_TEST) {
1050                         /* if parent is not an decendant of the frame, reattach the node */
1051                         nodeDetachNode(node);
1052                         nodeAttachNode(node, frame);
1053                         node->done |= NODE_JOIN_IS_DESCENDANT;
1054                 }
1055         }
1056         else if (node->flag & NODE_TEST) {
1057                 nodeAttachNode(node, frame);
1058                 node->done |= NODE_JOIN_IS_DESCENDANT;
1059         }
1060 }
1061
1062 static int node_join_exec(bContext *C, wmOperator *UNUSED(op))
1063 {
1064         SpaceNode *snode = CTX_wm_space_node(C);
1065         bNodeTree *ntree = snode->edittree;
1066         bNode *node, *frame;
1067
1068         /* XXX save selection: node_add_node call below sets the new frame as single active+selected node */
1069         for (node = ntree->nodes.first; node; node = node->next) {
1070                 if (node->flag & NODE_SELECT)
1071                         node->flag |= NODE_TEST;
1072                 else
1073                         node->flag &= ~NODE_TEST;
1074         }
1075
1076         frame = node_add_node(C, NULL, NODE_FRAME, 0.0f, 0.0f);
1077
1078         /* reset tags */
1079         for (node = ntree->nodes.first; node; node = node->next)
1080                 node->done = 0;
1081
1082         for (node = ntree->nodes.first; node; node = node->next) {
1083                 if (!(node->done & NODE_JOIN_DONE))
1084                         node_join_attach_recursive(node, frame);
1085         }
1086
1087         /* restore selection */
1088         for (node = ntree->nodes.first; node; node = node->next) {
1089                 if (node->flag & NODE_TEST)
1090                         node->flag |= NODE_SELECT;
1091         }
1092
1093         ED_node_sort(ntree);
1094         WM_event_add_notifier(C, NC_NODE | ND_DISPLAY, NULL);
1095
1096         return OPERATOR_FINISHED;
1097 }
1098
1099 void NODE_OT_join(wmOperatorType *ot)
1100 {
1101         /* identifiers */
1102         ot->name = "Join Nodes";
1103         ot->description = "Attach selected nodes to a new common frame";
1104         ot->idname = "NODE_OT_join";
1105
1106         /* api callbacks */
1107         ot->exec = node_join_exec;
1108         ot->poll = ED_operator_node_editable;
1109
1110         /* flags */
1111         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
1112 }
1113
1114 /* ****************** Attach ******************* */
1115
1116 static bNode *node_find_frame_to_attach(ARegion *ar, const bNodeTree *ntree, const int mouse_xy[2])
1117 {
1118         bNode *frame;
1119         float cursor[2];
1120
1121         /* convert mouse coordinates to v2d space */
1122         UI_view2d_region_to_view(&ar->v2d, UNPACK2(mouse_xy), &cursor[0], &cursor[1]);
1123
1124         /* check nodes front to back */
1125         for (frame = ntree->nodes.last; frame; frame = frame->prev) {
1126                 /* skip selected, those are the nodes we want to attach */
1127                 if ((frame->type != NODE_FRAME) || (frame->flag & NODE_SELECT))
1128                         continue;
1129                 if (BLI_rctf_isect_pt_v(&frame->totr, cursor))
1130                         return frame;
1131         }
1132
1133         return NULL;
1134 }
1135
1136 static int node_attach_invoke(bContext *C, wmOperator *UNUSED(op), const wmEvent *event)
1137 {
1138         ARegion *ar = CTX_wm_region(C);
1139         SpaceNode *snode = CTX_wm_space_node(C);
1140         bNodeTree *ntree = snode->edittree;
1141         bNode *frame = node_find_frame_to_attach(ar, ntree, event->mval);
1142
1143         if (frame) {
1144                 bNode *node, *parent;
1145                 for (node = ntree->nodes.last; node; node = node->prev) {
1146                         if (node->flag & NODE_SELECT) {
1147                                 if (node->parent == NULL) {
1148                                         /* disallow moving a parent into its child */
1149                                         if (nodeAttachNodeCheck(frame, node) == false) {
1150                                                 /* attach all unparented nodes */
1151                                                 nodeAttachNode(node, frame);
1152                                         }
1153                                 }
1154                                 else {
1155                                         /* attach nodes which share parent with the frame */
1156                                         for (parent = frame->parent; parent; parent = parent->parent) {
1157                                                 if (parent == node->parent) {
1158                                                         break;
1159                                                 }
1160                                         }
1161
1162                                         if (parent) {
1163                                                 /* disallow moving a parent into its child */
1164                                                 if (nodeAttachNodeCheck(frame, node) == false) {
1165                                                         nodeDetachNode(node);
1166                                                         nodeAttachNode(node, frame);
1167                                                 }
1168                                         }
1169                                 }
1170                         }
1171                 }
1172         }
1173
1174         ED_node_sort(ntree);
1175         WM_event_add_notifier(C, NC_NODE | ND_DISPLAY, NULL);
1176
1177         return OPERATOR_FINISHED;
1178 }
1179
1180
1181 void NODE_OT_attach(wmOperatorType *ot)
1182 {
1183         /* identifiers */
1184         ot->name = "Attach Nodes";
1185         ot->description = "Attach active node to a frame";
1186         ot->idname = "NODE_OT_attach";
1187
1188         /* api callbacks */
1189         
1190         ot->invoke = node_attach_invoke;
1191         ot->poll = ED_operator_node_editable;
1192
1193         /* flags */
1194         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
1195 }
1196
1197 /* ****************** Detach ******************* */
1198
1199 /* tags for depth-first search */
1200 #define NODE_DETACH_DONE            1
1201 #define NODE_DETACH_IS_DESCENDANT   2
1202
1203 static void node_detach_recursive(bNode *node)
1204 {
1205         node->done |= NODE_DETACH_DONE;
1206
1207         if (node->parent) {
1208                 /* call recursively */
1209                 if (!(node->parent->done & NODE_DETACH_DONE))
1210                         node_detach_recursive(node->parent);
1211
1212                 /* in any case: if the parent is a descendant, so is the child */
1213                 if (node->parent->done & NODE_DETACH_IS_DESCENDANT)
1214                         node->done |= NODE_DETACH_IS_DESCENDANT;
1215                 else if (node->flag & NODE_SELECT) {
1216                         /* if parent is not a decendant of a selected node, detach */
1217                         nodeDetachNode(node);
1218                         node->done |= NODE_DETACH_IS_DESCENDANT;
1219                 }
1220         }
1221         else if (node->flag & NODE_SELECT) {
1222                 node->done |= NODE_DETACH_IS_DESCENDANT;
1223         }
1224 }
1225
1226
1227 /* detach the root nodes in the current selection */
1228 static int node_detach_exec(bContext *C, wmOperator *UNUSED(op))
1229 {
1230         SpaceNode *snode = CTX_wm_space_node(C);
1231         bNodeTree *ntree = snode->edittree;
1232         bNode *node;
1233
1234         /* reset tags */
1235         for (node = ntree->nodes.first; node; node = node->next)
1236                 node->done = 0;
1237         /* detach nodes recursively
1238          * relative order is preserved here!
1239          */
1240         for (node = ntree->nodes.first; node; node = node->next) {
1241                 if (!(node->done & NODE_DETACH_DONE))
1242                         node_detach_recursive(node);
1243         }
1244
1245         ED_node_sort(ntree);
1246         WM_event_add_notifier(C, NC_NODE | ND_DISPLAY, NULL);
1247
1248         return OPERATOR_FINISHED;
1249 }
1250
1251 void NODE_OT_detach(wmOperatorType *ot)
1252 {
1253         /* identifiers */
1254         ot->name = "Detach Nodes";
1255         ot->description = "Detach selected nodes from parents";
1256         ot->idname = "NODE_OT_detach";
1257
1258         /* api callbacks */
1259         ot->exec = node_detach_exec;
1260         ot->poll = ED_operator_node_editable;
1261
1262         /* flags */
1263         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
1264 }
1265
1266 /* *********************  automatic node insert on dragging ******************* */
1267
1268
1269 /* prevent duplicate testing code below */
1270 static bool ed_node_link_conditions(ScrArea *sa, bool test, SpaceNode **r_snode, bNode **r_select)
1271 {
1272         SpaceNode *snode = sa ? sa->spacedata.first : NULL;
1273         bNode *node, *select = NULL;
1274         bNodeLink *link;
1275
1276         *r_snode = snode;
1277         *r_select = NULL;
1278
1279         /* no unlucky accidents */
1280         if (sa == NULL || sa->spacetype != SPACE_NODE)
1281                 return false;
1282
1283         if (!test) {
1284                 /* no need to look for a node */
1285                 return true;
1286         }
1287
1288         for (node = snode->edittree->nodes.first; node; node = node->next) {
1289                 if (node->flag & SELECT) {
1290                         if (select)
1291                                 break;
1292                         else
1293                                 select = node;
1294                 }
1295         }
1296         /* only one selected */
1297         if (node || select == NULL)
1298                 return false;
1299
1300         /* correct node */
1301         if (BLI_listbase_is_empty(&select->inputs) || BLI_listbase_is_empty(&select->outputs))
1302                 return false;
1303
1304         /* test node for links */
1305         for (link = snode->edittree->links.first; link; link = link->next) {
1306                 if (nodeLinkIsHidden(link))
1307                         continue;
1308                 
1309                 if (link->tonode == select || link->fromnode == select)
1310                         return false;
1311         }
1312
1313         *r_select = select;
1314         return true;
1315 }
1316
1317 /* test == 0, clear all intersect flags */
1318 void ED_node_link_intersect_test(ScrArea *sa, int test)
1319 {
1320         bNode *select;
1321         SpaceNode *snode;
1322         bNodeLink *link, *selink = NULL;
1323         float dist_best = FLT_MAX;
1324
1325         if (!ed_node_link_conditions(sa, test, &snode, &select)) return;
1326
1327         /* clear flags */
1328         for (link = snode->edittree->links.first; link; link = link->next)
1329                 link->flag &= ~NODE_LINKFLAG_HILITE;
1330
1331         if (test == 0) return;
1332
1333         /* find link to select/highlight */
1334         for (link = snode->edittree->links.first; link; link = link->next) {
1335                 float coord_array[NODE_LINK_RESOL + 1][2];
1336
1337                 if (nodeLinkIsHidden(link))
1338                         continue;
1339
1340                 if (node_link_bezier_points(NULL, NULL, link, coord_array, NODE_LINK_RESOL)) {
1341                         float dist = FLT_MAX;
1342                         int i;
1343
1344                         /* loop over link coords to find shortest dist to upper left node edge of a intersected line segment */
1345                         for (i = 0; i < NODE_LINK_RESOL; i++) {
1346                                 /* check if the node rect intersetcts the line from this point to next one */
1347                                 if (BLI_rctf_isect_segment(&select->totr, coord_array[i], coord_array[i + 1])) {
1348                                         /* store the shortest distance to the upper left edge of all intersetctions found so far */
1349                                         const float node_xy[] = {select->totr.xmin, select->totr.ymax};
1350
1351                                         /* to be precise coord_array should be clipped by select->totr,
1352                                          * but not done since there's no real noticeable difference */
1353                                         dist = min_ff(dist_squared_to_line_segment_v2(node_xy, coord_array[i], coord_array[i + 1]),
1354                                                            dist);
1355                                 }
1356                         }
1357
1358                         /* we want the link with the shortest distance to node center */
1359                         if (dist < dist_best) {
1360                                 dist_best = dist;
1361                                 selink = link;
1362                         }
1363                 }
1364         }
1365
1366         if (selink)
1367                 selink->flag |= NODE_LINKFLAG_HILITE;
1368 }
1369
1370 /* assumes sockets in list */
1371 static bNodeSocket *socket_best_match(ListBase *sockets)
1372 {
1373         bNodeSocket *sock;
1374         int type, maxtype = 0;
1375
1376         /* find type range */
1377         for (sock = sockets->first; sock; sock = sock->next)
1378                 maxtype = max_ii(sock->type, maxtype);
1379
1380         /* try all types, starting from 'highest' (i.e. colors, vectors, values) */
1381         for (type = maxtype; type >= 0; --type) {
1382                 for (sock = sockets->first; sock; sock = sock->next) {
1383                         if (!nodeSocketIsHidden(sock) && type == sock->type) {
1384                                 return sock;
1385                         }
1386                 }
1387         }
1388
1389         /* no visible sockets, unhide first of highest type */
1390         for (type = maxtype; type >= 0; --type) {
1391                 for (sock = sockets->first; sock; sock = sock->next) {
1392                         if (type == sock->type) {
1393                                 sock->flag &= ~SOCK_HIDDEN;
1394                                 return sock;
1395                         }
1396                 }
1397         }
1398
1399         return NULL;
1400 }
1401
1402 static bool node_parents_offset_flag_enable_cb(bNode *parent, void *UNUSED(userdata))
1403 {
1404         /* NODE_TEST is used to flag nodes that shouldn't be offset (again) */
1405         parent->flag |= NODE_TEST;
1406
1407         return true;
1408 }
1409
1410 static void node_offset_apply(bNode *node, const float offset_x)
1411 {
1412         /* NODE_TEST is used to flag nodes that shouldn't be offset (again) */
1413         if ((node->flag & NODE_TEST) == 0) {
1414                 node->anim_init_locx = node->locx;
1415                 node->anim_ofsx = (offset_x / UI_DPI_FAC);
1416                 node->flag |= NODE_TEST;
1417         }
1418 }
1419
1420 static void node_parent_offset_apply(NodeInsertOfsData *data, bNode *parent, const float offset_x)
1421 {
1422         bNode *node;
1423
1424         node_offset_apply(parent, offset_x);
1425
1426         /* flag all childs as offset to prevent them from being offset
1427          * separately (they've already moved with the parent) */
1428         for (node = data->ntree->nodes.first; node; node = node->next) {
1429                 if (nodeIsChildOf(parent, node)) {
1430                         /* NODE_TEST is used to flag nodes that shouldn't be offset (again) */
1431                         node->flag |= NODE_TEST;
1432                 }
1433         }
1434 }
1435
1436 #define NODE_INSOFS_ANIM_DURATION 0.25f
1437
1438 /**
1439  * Callback that applies NodeInsertOfsData.offset_x to a node or its parent, similar
1440  * to node_link_insert_offset_output_chain_cb below, but with slightly different logic
1441  */
1442 static bool node_link_insert_offset_frame_chain_cb(
1443         bNode *fromnode, bNode *tonode,
1444         void *userdata,
1445         const bool reversed)
1446 {
1447         NodeInsertOfsData *data = userdata;
1448         bNode *ofs_node = reversed ? fromnode : tonode;
1449
1450         if (ofs_node->parent && ofs_node->parent != data->insert_parent) {
1451                 node_offset_apply(ofs_node->parent, data->offset_x);
1452         }
1453         else {
1454                 node_offset_apply(ofs_node, data->offset_x);
1455         }
1456
1457         return true;
1458 }
1459
1460 /**
1461  * Applies NodeInsertOfsData.offset_x to all childs of \a parent
1462  */
1463 static void node_link_insert_offset_frame_chains(
1464         const bNodeTree *ntree, const bNode *parent,
1465         NodeInsertOfsData *data,
1466         const bool reversed)
1467 {
1468         bNode *node;
1469
1470         for (node = ntree->nodes.first; node; node = node->next) {
1471                 if (nodeIsChildOf(parent, node)) {
1472                         nodeChainIter(ntree, node, node_link_insert_offset_frame_chain_cb, data, reversed);
1473                 }
1474         }
1475 }
1476
1477 /**
1478  * Callback that applies NodeInsertOfsData.offset_x to a node or its parent,
1479  * considering the logic needed for offseting nodes after link insert
1480  */
1481 static bool node_link_insert_offset_chain_cb(
1482         bNode *fromnode, bNode *tonode,
1483         void *userdata,
1484         const bool reversed)
1485 {
1486         NodeInsertOfsData *data = userdata;
1487         bNode *ofs_node = reversed ? fromnode : tonode;
1488
1489         if (data->insert_parent) {
1490                 if (ofs_node->parent && (ofs_node->parent->flag & NODE_TEST) == 0) {
1491                         node_parent_offset_apply(data, ofs_node->parent, data->offset_x);
1492                         node_link_insert_offset_frame_chains(data->ntree, ofs_node->parent, data, reversed);
1493                 }
1494                 else {
1495                         node_offset_apply(ofs_node, data->offset_x);
1496                 }
1497
1498                 if (nodeIsChildOf(data->insert_parent, ofs_node) == false) {
1499                         data->insert_parent = NULL;
1500                 }
1501         }
1502         else if (ofs_node->parent) {
1503                 bNode *node = nodeFindRootParent(ofs_node);
1504                 node_offset_apply(node, data->offset_x);
1505         }
1506         else {
1507                 node_offset_apply(ofs_node, data->offset_x);
1508         }
1509
1510         return true;
1511 }
1512
1513 static void node_link_insert_offset_ntree(
1514         NodeInsertOfsData *iofsd, ARegion *ar,
1515         const int mouse_xy[2], const bool right_alignment)
1516 {
1517         bNodeTree *ntree = iofsd->ntree;
1518         bNode *insert = iofsd->insert;
1519         bNode *prev = iofsd->prev, *next = iofsd->next;
1520         bNode *init_parent = insert->parent; /* store old insert->parent for restoring later */
1521         rctf totr_insert;
1522
1523         const float min_margin = U.node_margin * UI_DPI_FAC;
1524         const float width = NODE_WIDTH(insert);
1525         const bool needs_alignment = (next->totr.xmin - prev->totr.xmax) < (width + (min_margin * 2.0f));
1526
1527         float margin = width;
1528         float dist, addval;
1529
1530
1531         /* NODE_TEST will be used later, so disable for all nodes */
1532         ntreeNodeFlagSet(ntree, NODE_TEST, false);
1533
1534         /* insert->totr isn't updated yet, so totr_insert is used to get the correct worldspace coords */
1535         node_to_updated_rect(insert, &totr_insert);
1536
1537         /* frame attachement was't handled yet so we search the frame that the node will be attached to later */
1538         insert->parent = node_find_frame_to_attach(ar, ntree, mouse_xy);
1539
1540         /* this makes sure nodes are also correctly offset when inserting a node on top of a frame
1541          * without actually making it a part of the frame (because mouse isn't intersecting it)
1542          * - logic here is similar to node_find_frame_to_attach */
1543         if (!insert->parent ||
1544             (prev->parent && (prev->parent == next->parent) && (prev->parent != insert->parent)))
1545         {
1546                 bNode *frame;
1547                 rctf totr_frame;
1548
1549                 /* check nodes front to back */
1550                 for (frame = ntree->nodes.last; frame; frame = frame->prev) {
1551                         /* skip selected, those are the nodes we want to attach */
1552                         if ((frame->type != NODE_FRAME) || (frame->flag & NODE_SELECT))
1553                                 continue;
1554
1555                         /* for some reason frame y coords aren't correct yet */
1556                         node_to_updated_rect(frame, &totr_frame);
1557
1558                         if (BLI_rctf_isect_x(&totr_frame, totr_insert.xmin) &&
1559                             BLI_rctf_isect_x(&totr_frame, totr_insert.xmax))
1560                         {
1561                                 if (BLI_rctf_isect_y(&totr_frame, totr_insert.ymin) ||
1562                                     BLI_rctf_isect_y(&totr_frame, totr_insert.ymax))
1563                                 {
1564                                         /* frame isn't insert->parent actually, but this is needed to make offsetting
1565                                          * nodes work correctly for above checked cases (it is restored later) */
1566                                         insert->parent = frame;
1567                                         break;
1568                                 }
1569                         }
1570                 }
1571         }
1572
1573
1574         /* *** ensure offset at the left (or right for right_alignment case) of insert_node *** */
1575
1576         dist = right_alignment ? totr_insert.xmin - prev->totr.xmax : next->totr.xmin - totr_insert.xmax;
1577         /* distance between insert_node and prev is smaller than min margin */
1578         if (dist < min_margin) {
1579                 addval = (min_margin - dist) * (right_alignment ? 1.0f : -1.0f);
1580
1581                 node_offset_apply(insert, addval);
1582
1583                 totr_insert.xmin  += addval;
1584                 totr_insert.xmax  += addval;
1585                 margin            += min_margin;
1586         }
1587
1588         /* *** ensure offset at the right (or left for right_alignment case) of insert_node *** */
1589
1590         dist = right_alignment ? next->totr.xmin - totr_insert.xmax : totr_insert.xmin - prev->totr.xmax;
1591         /* distance between insert_node and next is smaller than min margin */
1592         if (dist < min_margin) {
1593                 addval = (min_margin - dist) * (right_alignment ? 1.0f : -1.0f);
1594                 if (needs_alignment) {
1595                         bNode *offs_node = right_alignment ? next : prev;
1596                         if (!offs_node->parent ||
1597                             offs_node->parent == insert->parent ||
1598                             nodeIsChildOf(offs_node->parent, insert))
1599                         {
1600                                 node_offset_apply(offs_node, addval);
1601                         }
1602                         else if (!insert->parent && offs_node->parent) {
1603                                 node_offset_apply(offs_node->parent, addval);
1604                         }
1605                         margin = addval;
1606                 }
1607                 /* enough room is available, but we want to ensure the min margin at the right */
1608                 else {
1609                         /* offset inserted node so that min margin is kept at the right */
1610                         node_offset_apply(insert, -addval);
1611                 }
1612         }
1613
1614
1615         if (needs_alignment) {
1616                 iofsd->insert_parent = insert->parent;
1617                 iofsd->offset_x = margin;
1618
1619                 /* flag all parents of insert as offset to prevent them from being offset */
1620                 nodeParentsIter(insert, node_parents_offset_flag_enable_cb, NULL);
1621                 /* iterate over entire chain and apply offsets */
1622                 nodeChainIter(ntree, right_alignment ? next : prev, node_link_insert_offset_chain_cb, iofsd, !right_alignment);
1623         }
1624
1625         insert->parent = init_parent;
1626 }
1627
1628 /**
1629  * Modal handler for insert offset animation
1630  */
1631 static int node_insert_offset_modal(bContext *C, wmOperator *UNUSED(op), const wmEvent *event)
1632 {
1633         SpaceNode *snode = CTX_wm_space_node(C);
1634         NodeInsertOfsData *iofsd = snode->iofsd;
1635         bNode *node;
1636         float duration;
1637
1638         if (!snode || event->type != TIMER || iofsd->anim_timer != event->customdata)
1639                 return OPERATOR_PASS_THROUGH;
1640
1641         /* end timer + free insert offset data */
1642         duration = (float)iofsd->anim_timer->duration;
1643         if (duration > NODE_INSOFS_ANIM_DURATION) {
1644                 WM_event_remove_timer(CTX_wm_manager(C), NULL, iofsd->anim_timer);
1645
1646                 for (node = snode->edittree->nodes.first; node; node = node->next) {
1647                         node->anim_init_locx = node->anim_ofsx = 0.0f;
1648                 }
1649
1650                 snode->iofsd = NULL;
1651                 MEM_freeN(iofsd);
1652
1653                 return (OPERATOR_FINISHED | OPERATOR_PASS_THROUGH);
1654         }
1655
1656         /* handle animation */
1657         for (node = snode->edittree->nodes.first; node; node = node->next) {
1658                 if (node->anim_ofsx) {
1659                         node->locx = BLI_easing_cubic_ease_in_out(duration, node->anim_init_locx, node->anim_ofsx,
1660                                                                   NODE_INSOFS_ANIM_DURATION);
1661                 }
1662         }
1663         ED_region_tag_redraw(CTX_wm_region(C));
1664
1665         return OPERATOR_RUNNING_MODAL;
1666 }
1667
1668 #undef NODE_INSOFS_ANIM_DURATION
1669
1670 static int node_insert_offset_invoke(bContext *C, wmOperator *op, const wmEvent *event)
1671 {
1672         const SpaceNode *snode = CTX_wm_space_node(C);
1673         NodeInsertOfsData *iofsd = snode->iofsd;
1674
1675         if (!iofsd || !iofsd->insert)
1676                 return OPERATOR_CANCELLED;
1677
1678         BLI_assert((snode->flag & SNODE_SKIP_INSOFFSET) == 0);
1679
1680         iofsd->ntree = snode->edittree;
1681         iofsd->anim_timer = WM_event_add_timer(CTX_wm_manager(C), CTX_wm_window(C), TIMER, 0.02);
1682
1683         node_link_insert_offset_ntree(
1684                     iofsd, CTX_wm_region(C),
1685                     event->mval, (snode->insert_ofs_dir == SNODE_INSERTOFS_DIR_RIGHT));
1686
1687         /* add temp handler */
1688         WM_event_add_modal_handler(C, op);
1689
1690         return OPERATOR_RUNNING_MODAL;
1691 }
1692
1693 void NODE_OT_insert_offset(wmOperatorType *ot)
1694 {
1695         /* identifiers */
1696         ot->name = "Insert Offset";
1697         ot->description = "Automatically offset nodes on insertion";
1698         ot->idname = "NODE_OT_insert_offset";
1699
1700         /* callbacks */
1701         ot->invoke = node_insert_offset_invoke;
1702         ot->modal = node_insert_offset_modal;
1703         ot->poll = ED_operator_node_editable;
1704
1705         /* flags */
1706         ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO | OPTYPE_BLOCKING;
1707 }
1708
1709 /* assumes link with NODE_LINKFLAG_HILITE set */
1710 void ED_node_link_insert(ScrArea *sa)
1711 {
1712         bNode *node, *select;
1713         SpaceNode *snode;
1714         bNodeLink *link;
1715         bNodeSocket *sockto;
1716
1717         if (!ed_node_link_conditions(sa, true, &snode, &select)) return;
1718
1719         /* get the link */
1720         for (link = snode->edittree->links.first; link; link = link->next)
1721                 if (link->flag & NODE_LINKFLAG_HILITE)
1722                         break;
1723
1724         if (link) {
1725                 bNodeSocket *best_input = socket_best_match(&select->inputs);
1726                 bNodeSocket *best_output = socket_best_match(&select->outputs);
1727                 
1728                 if (best_input && best_output) {
1729                         node = link->tonode;
1730                         sockto = link->tosock;
1731                         
1732                         link->tonode = select;
1733                         link->tosock = best_input;
1734                         node_remove_extra_links(snode, link, false);
1735                         link->flag &= ~NODE_LINKFLAG_HILITE;
1736                         
1737                         nodeAddLink(snode->edittree, select, best_output, node, sockto);
1738                         
1739                         /* set up insert offset data, it needs stuff from here */
1740                         if ((snode->flag & SNODE_SKIP_INSOFFSET) == 0) {
1741                                 NodeInsertOfsData *iofsd = MEM_callocN(sizeof(NodeInsertOfsData), __func__);
1742
1743                                 iofsd->insert = select;
1744                                 iofsd->prev = link->fromnode;
1745                                 iofsd->next = node;
1746
1747                                 snode->iofsd = iofsd;
1748                         }
1749
1750                         ntreeUpdateTree(G.main, snode->edittree);   /* needed for pointers */
1751                         snode_update(snode, select);
1752                         ED_node_tag_update_id(snode->id);
1753                 }
1754         }
1755 }