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