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