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