]> git.sur5r.net Git - i3/i3/blob - src/con.c
cmd_exit: Let i3_exit handle shutdown (#3600)
[i3/i3] / src / con.c
1 /*
2  * vim:ts=4:sw=4:expandtab
3  *
4  * i3 - an improved dynamic tiling window manager
5  * © 2009 Michael Stapelberg and contributors (see also: LICENSE)
6  *
7  * con.c: Functions which deal with containers directly (creating containers,
8  *        searching containers, getting specific properties from containers,
9  *        …).
10  *
11  */
12 #include "all.h"
13
14 #include "yajl_utils.h"
15
16 static void con_on_remove_child(Con *con);
17
18 /*
19  * force parent split containers to be redrawn
20  *
21  */
22 void con_force_split_parents_redraw(Con *con) {
23     Con *parent = con;
24
25     while (parent != NULL && parent->type != CT_WORKSPACE && parent->type != CT_DOCKAREA) {
26         if (!con_is_leaf(parent)) {
27             FREE(parent->deco_render_params);
28         }
29
30         parent = parent->parent;
31     }
32 }
33
34 /*
35  * Create a new container (and attach it to the given parent, if not NULL).
36  * This function only initializes the data structures.
37  *
38  */
39 Con *con_new_skeleton(Con *parent, i3Window *window) {
40     Con *new = scalloc(1, sizeof(Con));
41     new->on_remove_child = con_on_remove_child;
42     TAILQ_INSERT_TAIL(&all_cons, new, all_cons);
43     new->type = CT_CON;
44     new->window = window;
45     new->border_style = config.default_border;
46     new->current_border_width = -1;
47     if (window) {
48         new->depth = window->depth;
49     } else {
50         new->depth = root_depth;
51     }
52     DLOG("opening window\n");
53
54     TAILQ_INIT(&(new->floating_head));
55     TAILQ_INIT(&(new->nodes_head));
56     TAILQ_INIT(&(new->focus_head));
57     TAILQ_INIT(&(new->swallow_head));
58     TAILQ_INIT(&(new->marks_head));
59
60     if (parent != NULL)
61         con_attach(new, parent, false);
62
63     return new;
64 }
65
66 /* A wrapper for con_new_skeleton, to retain the old con_new behaviour
67  *
68  */
69 Con *con_new(Con *parent, i3Window *window) {
70     Con *new = con_new_skeleton(parent, window);
71     x_con_init(new);
72     return new;
73 }
74
75 /*
76  * Frees the specified container.
77  *
78  */
79 void con_free(Con *con) {
80     free(con->name);
81     FREE(con->deco_render_params);
82     TAILQ_REMOVE(&all_cons, con, all_cons);
83     while (!TAILQ_EMPTY(&(con->swallow_head))) {
84         Match *match = TAILQ_FIRST(&(con->swallow_head));
85         TAILQ_REMOVE(&(con->swallow_head), match, matches);
86         match_free(match);
87         free(match);
88     }
89     while (!TAILQ_EMPTY(&(con->marks_head))) {
90         mark_t *mark = TAILQ_FIRST(&(con->marks_head));
91         TAILQ_REMOVE(&(con->marks_head), mark, marks);
92         FREE(mark->name);
93         FREE(mark);
94     }
95     free(con);
96     DLOG("con %p freed\n", con);
97 }
98
99 static void _con_attach(Con *con, Con *parent, Con *previous, bool ignore_focus) {
100     con->parent = parent;
101     Con *loop;
102     Con *current = previous;
103     struct nodes_head *nodes_head = &(parent->nodes_head);
104     struct focus_head *focus_head = &(parent->focus_head);
105
106     /* Workspaces are handled differently: they need to be inserted at the
107      * right position. */
108     if (con->type == CT_WORKSPACE) {
109         DLOG("it's a workspace. num = %d\n", con->num);
110         if (con->num == -1 || TAILQ_EMPTY(nodes_head)) {
111             TAILQ_INSERT_TAIL(nodes_head, con, nodes);
112         } else {
113             current = TAILQ_FIRST(nodes_head);
114             if (con->num < current->num) {
115                 /* we need to insert the container at the beginning */
116                 TAILQ_INSERT_HEAD(nodes_head, con, nodes);
117             } else {
118                 while (current->num != -1 && con->num > current->num) {
119                     current = TAILQ_NEXT(current, nodes);
120                     if (current == TAILQ_END(nodes_head)) {
121                         current = NULL;
122                         break;
123                     }
124                 }
125                 /* we need to insert con after current, if current is not NULL */
126                 if (current)
127                     TAILQ_INSERT_BEFORE(current, con, nodes);
128                 else
129                     TAILQ_INSERT_TAIL(nodes_head, con, nodes);
130             }
131         }
132         goto add_to_focus_head;
133     }
134
135     if (con->type == CT_FLOATING_CON) {
136         DLOG("Inserting into floating containers\n");
137         TAILQ_INSERT_TAIL(&(parent->floating_head), con, floating_windows);
138     } else {
139         if (!ignore_focus) {
140             /* Get the first tiling container in focus stack */
141             TAILQ_FOREACH(loop, &(parent->focus_head), focused) {
142                 if (loop->type == CT_FLOATING_CON)
143                     continue;
144                 current = loop;
145                 break;
146             }
147         }
148
149         /* When the container is not a split container (but contains a window)
150          * and is attached to a workspace, we check if the user configured a
151          * workspace_layout. This is done in workspace_attach_to, which will
152          * provide us with the container to which we should attach (either the
153          * workspace or a new split container with the configured
154          * workspace_layout).
155          */
156         if (con->window != NULL &&
157             parent->type == CT_WORKSPACE &&
158             parent->workspace_layout != L_DEFAULT) {
159             DLOG("Parent is a workspace. Applying default layout...\n");
160             Con *target = workspace_attach_to(parent);
161
162             /* Attach the original con to this new split con instead */
163             nodes_head = &(target->nodes_head);
164             focus_head = &(target->focus_head);
165             con->parent = target;
166             current = NULL;
167
168             DLOG("done\n");
169         }
170
171         /* Insert the container after the tiling container, if found.
172          * When adding to a CT_OUTPUT, just append one after another. */
173         if (current != NULL && parent->type != CT_OUTPUT) {
174             DLOG("Inserting con = %p after con %p\n", con, current);
175             TAILQ_INSERT_AFTER(nodes_head, current, con, nodes);
176         } else
177             TAILQ_INSERT_TAIL(nodes_head, con, nodes);
178     }
179
180 add_to_focus_head:
181     /* We insert to the TAIL because con_focus() will correct this.
182      * This way, we have the option to insert Cons without having
183      * to focus them. */
184     TAILQ_INSERT_TAIL(focus_head, con, focused);
185     con_force_split_parents_redraw(con);
186 }
187
188 /*
189  * Attaches the given container to the given parent. This happens when moving
190  * a container or when inserting a new container at a specific place in the
191  * tree.
192  *
193  * ignore_focus is to just insert the Con at the end (useful when creating a
194  * new split container *around* some containers, that is, detaching and
195  * attaching them in order without wanting to mess with the focus in between).
196  *
197  */
198 void con_attach(Con *con, Con *parent, bool ignore_focus) {
199     _con_attach(con, parent, NULL, ignore_focus);
200 }
201
202 /*
203  * Detaches the given container from its current parent
204  *
205  */
206 void con_detach(Con *con) {
207     con_force_split_parents_redraw(con);
208     if (con->type == CT_FLOATING_CON) {
209         TAILQ_REMOVE(&(con->parent->floating_head), con, floating_windows);
210         TAILQ_REMOVE(&(con->parent->focus_head), con, focused);
211     } else {
212         TAILQ_REMOVE(&(con->parent->nodes_head), con, nodes);
213         TAILQ_REMOVE(&(con->parent->focus_head), con, focused);
214     }
215 }
216
217 /*
218  * Sets input focus to the given container. Will be updated in X11 in the next
219  * run of x_push_changes().
220  *
221  */
222 void con_focus(Con *con) {
223     assert(con != NULL);
224     DLOG("con_focus = %p\n", con);
225
226     /* 1: set focused-pointer to the new con */
227     /* 2: exchange the position of the container in focus stack of the parent all the way up */
228     TAILQ_REMOVE(&(con->parent->focus_head), con, focused);
229     TAILQ_INSERT_HEAD(&(con->parent->focus_head), con, focused);
230     if (con->parent->parent != NULL)
231         con_focus(con->parent);
232
233     focused = con;
234     /* We can't blindly reset non-leaf containers since they might have
235      * other urgent children. Therefore we only reset leafs and propagate
236      * the changes upwards via con_update_parents_urgency() which does proper
237      * checks before resetting the urgency.
238      */
239     if (con->urgent && con_is_leaf(con)) {
240         con_set_urgency(con, false);
241         con_update_parents_urgency(con);
242         workspace_update_urgent_flag(con_get_workspace(con));
243         ipc_send_window_event("urgent", con);
244     }
245 }
246
247 /*
248  * Raise container to the top if it is floating or inside some floating
249  * container.
250  *
251  */
252 static void con_raise(Con *con) {
253     Con *floating = con_inside_floating(con);
254     if (floating) {
255         floating_raise_con(floating);
256     }
257 }
258
259 /*
260  * Sets input focus to the given container and raises it to the top.
261  *
262  */
263 void con_activate(Con *con) {
264     con_focus(con);
265     con_raise(con);
266 }
267
268 /*
269  * Closes the given container.
270  *
271  */
272 void con_close(Con *con, kill_window_t kill_window) {
273     assert(con != NULL);
274     DLOG("Closing con = %p.\n", con);
275
276     /* We never close output or root containers. */
277     if (con->type == CT_OUTPUT || con->type == CT_ROOT) {
278         DLOG("con = %p is of type %d, not closing anything.\n", con, con->type);
279         return;
280     }
281
282     if (con->type == CT_WORKSPACE) {
283         DLOG("con = %p is a workspace, closing all children instead.\n", con);
284         Con *child, *nextchild;
285         for (child = TAILQ_FIRST(&(con->focus_head)); child;) {
286             nextchild = TAILQ_NEXT(child, focused);
287             DLOG("killing child = %p.\n", child);
288             tree_close_internal(child, kill_window, false);
289             child = nextchild;
290         }
291
292         return;
293     }
294
295     tree_close_internal(con, kill_window, false);
296 }
297
298 /*
299  * Returns true when this node is a leaf node (has no children)
300  *
301  */
302 bool con_is_leaf(Con *con) {
303     return TAILQ_EMPTY(&(con->nodes_head));
304 }
305
306 /*
307  * Returns true when this con is a leaf node with a managed X11 window (e.g.,
308  * excluding dock containers)
309  */
310 bool con_has_managed_window(Con *con) {
311     return (con != NULL && con->window != NULL && con->window->id != XCB_WINDOW_NONE && con_get_workspace(con) != NULL);
312 }
313
314 /*
315  * Returns true if this node has regular or floating children.
316  *
317  */
318 bool con_has_children(Con *con) {
319     return (!con_is_leaf(con) || !TAILQ_EMPTY(&(con->floating_head)));
320 }
321
322 /*
323  * Returns true if a container should be considered split.
324  *
325  */
326 bool con_is_split(Con *con) {
327     if (con_is_leaf(con))
328         return false;
329
330     switch (con->layout) {
331         case L_DOCKAREA:
332         case L_OUTPUT:
333             return false;
334
335         default:
336             return true;
337     }
338 }
339
340 /*
341  * This will only return true for containers which have some parent with
342  * a tabbed / stacked parent of which they are not the currently focused child.
343  *
344  */
345 bool con_is_hidden(Con *con) {
346     Con *current = con;
347
348     /* ascend to the workspace level and memorize the highest-up container
349      * which is stacked or tabbed. */
350     while (current != NULL && current->type != CT_WORKSPACE) {
351         Con *parent = current->parent;
352         if (parent != NULL && (parent->layout == L_TABBED || parent->layout == L_STACKED)) {
353             if (TAILQ_FIRST(&(parent->focus_head)) != current)
354                 return true;
355         }
356
357         current = parent;
358     }
359
360     return false;
361 }
362
363 /*
364  * Returns whether the container or any of its children is sticky.
365  *
366  */
367 bool con_is_sticky(Con *con) {
368     if (con->sticky)
369         return true;
370
371     Con *child;
372     TAILQ_FOREACH(child, &(con->nodes_head), nodes) {
373         if (con_is_sticky(child))
374             return true;
375     }
376
377     return false;
378 }
379
380 /*
381  * Returns true if this node accepts a window (if the node swallows windows,
382  * it might already have swallowed enough and cannot hold any more).
383  *
384  */
385 bool con_accepts_window(Con *con) {
386     /* 1: workspaces never accept direct windows */
387     if (con->type == CT_WORKSPACE)
388         return false;
389
390     if (con_is_split(con)) {
391         DLOG("container %p does not accept windows, it is a split container.\n", con);
392         return false;
393     }
394
395     /* TODO: if this is a swallowing container, we need to check its max_clients */
396     return (con->window == NULL);
397 }
398
399 /*
400  * Gets the output container (first container with CT_OUTPUT in hierarchy) this
401  * node is on.
402  *
403  */
404 Con *con_get_output(Con *con) {
405     Con *result = con;
406     while (result != NULL && result->type != CT_OUTPUT)
407         result = result->parent;
408     /* We must be able to get an output because focus can never be set higher
409      * in the tree (root node cannot be focused). */
410     assert(result != NULL);
411     return result;
412 }
413
414 /*
415  * Gets the workspace container this node is on.
416  *
417  */
418 Con *con_get_workspace(Con *con) {
419     Con *result = con;
420     while (result != NULL && result->type != CT_WORKSPACE)
421         result = result->parent;
422     return result;
423 }
424
425 /*
426  * Searches parents of the given 'con' until it reaches one with the specified
427  * 'orientation'. Aborts when it comes across a floating_con.
428  *
429  */
430 Con *con_parent_with_orientation(Con *con, orientation_t orientation) {
431     DLOG("Searching for parent of Con %p with orientation %d\n", con, orientation);
432     Con *parent = con->parent;
433     if (parent->type == CT_FLOATING_CON)
434         return NULL;
435     while (con_orientation(parent) != orientation) {
436         DLOG("Need to go one level further up\n");
437         parent = parent->parent;
438         /* Abort when we reach a floating con, or an output con */
439         if (parent &&
440             (parent->type == CT_FLOATING_CON ||
441              parent->type == CT_OUTPUT ||
442              (parent->parent && parent->parent->type == CT_OUTPUT)))
443             parent = NULL;
444         if (parent == NULL)
445             break;
446     }
447     DLOG("Result: %p\n", parent);
448     return parent;
449 }
450
451 /*
452  * helper data structure for the breadth-first-search in
453  * con_get_fullscreen_con()
454  *
455  */
456 struct bfs_entry {
457     Con *con;
458
459     TAILQ_ENTRY(bfs_entry)
460     entries;
461 };
462
463 /*
464  * Returns the first fullscreen node below this node.
465  *
466  */
467 Con *con_get_fullscreen_con(Con *con, fullscreen_mode_t fullscreen_mode) {
468     Con *current, *child;
469
470     /* TODO: is breadth-first-search really appropriate? (check as soon as
471      * fullscreen levels and fullscreen for containers is implemented) */
472     TAILQ_HEAD(bfs_head, bfs_entry)
473     bfs_head = TAILQ_HEAD_INITIALIZER(bfs_head);
474
475     struct bfs_entry *entry = smalloc(sizeof(struct bfs_entry));
476     entry->con = con;
477     TAILQ_INSERT_TAIL(&bfs_head, entry, entries);
478
479     while (!TAILQ_EMPTY(&bfs_head)) {
480         entry = TAILQ_FIRST(&bfs_head);
481         current = entry->con;
482         if (current != con && current->fullscreen_mode == fullscreen_mode) {
483             /* empty the queue */
484             while (!TAILQ_EMPTY(&bfs_head)) {
485                 entry = TAILQ_FIRST(&bfs_head);
486                 TAILQ_REMOVE(&bfs_head, entry, entries);
487                 free(entry);
488             }
489             return current;
490         }
491
492         TAILQ_REMOVE(&bfs_head, entry, entries);
493         free(entry);
494
495         TAILQ_FOREACH(child, &(current->nodes_head), nodes) {
496             entry = smalloc(sizeof(struct bfs_entry));
497             entry->con = child;
498             TAILQ_INSERT_TAIL(&bfs_head, entry, entries);
499         }
500
501         TAILQ_FOREACH(child, &(current->floating_head), floating_windows) {
502             entry = smalloc(sizeof(struct bfs_entry));
503             entry->con = child;
504             TAILQ_INSERT_TAIL(&bfs_head, entry, entries);
505         }
506     }
507
508     return NULL;
509 }
510
511 /*
512  * Returns the fullscreen node that covers the given workspace if it exists.
513  * This is either a CF_GLOBAL fullscreen container anywhere or a CF_OUTPUT
514  * fullscreen container in the workspace.
515  *
516  */
517 Con *con_get_fullscreen_covering_ws(Con *ws) {
518     if (!ws) {
519         return NULL;
520     }
521     Con *fs = con_get_fullscreen_con(croot, CF_GLOBAL);
522     if (!fs) {
523         return con_get_fullscreen_con(ws, CF_OUTPUT);
524     }
525     return fs;
526 }
527
528 /*
529  * Returns true if the container is internal, such as __i3_scratch
530  *
531  */
532 bool con_is_internal(Con *con) {
533     return (con->name[0] == '_' && con->name[1] == '_');
534 }
535
536 /*
537  * Returns true if the node is floating.
538  *
539  */
540 bool con_is_floating(Con *con) {
541     assert(con != NULL);
542     DLOG("checking if con %p is floating\n", con);
543     return (con->floating >= FLOATING_AUTO_ON);
544 }
545
546 /*
547  * Returns true if the container is a docked container.
548  *
549  */
550 bool con_is_docked(Con *con) {
551     if (con->parent == NULL)
552         return false;
553
554     if (con->parent->type == CT_DOCKAREA)
555         return true;
556
557     return con_is_docked(con->parent);
558 }
559
560 /*
561  * Checks if the given container is either floating or inside some floating
562  * container. It returns the FLOATING_CON container.
563  *
564  */
565 Con *con_inside_floating(Con *con) {
566     assert(con != NULL);
567     if (con->type == CT_FLOATING_CON)
568         return con;
569
570     if (con->floating >= FLOATING_AUTO_ON)
571         return con->parent;
572
573     if (con->type == CT_WORKSPACE || con->type == CT_OUTPUT)
574         return NULL;
575
576     return con_inside_floating(con->parent);
577 }
578
579 /*
580  * Checks if the given container is inside a focused container.
581  *
582  */
583 bool con_inside_focused(Con *con) {
584     if (con == focused)
585         return true;
586     if (!con->parent)
587         return false;
588     return con_inside_focused(con->parent);
589 }
590
591 /*
592  * Checks if the container has the given parent as an actual parent.
593  *
594  */
595 bool con_has_parent(Con *con, Con *parent) {
596     Con *current = con->parent;
597     if (current == NULL) {
598         return false;
599     }
600
601     if (current == parent) {
602         return true;
603     }
604
605     return con_has_parent(current, parent);
606 }
607
608 /*
609  * Returns the container with the given client window ID or NULL if no such
610  * container exists.
611  *
612  */
613 Con *con_by_window_id(xcb_window_t window) {
614     Con *con;
615     TAILQ_FOREACH(con, &all_cons, all_cons)
616     if (con->window != NULL && con->window->id == window)
617         return con;
618     return NULL;
619 }
620
621 /*
622  * Returns the container with the given container ID or NULL if no such
623  * container exists.
624  *
625  */
626 Con *con_by_con_id(long target) {
627     Con *con;
628     TAILQ_FOREACH(con, &all_cons, all_cons) {
629         if (con == (Con *)target) {
630             return con;
631         }
632     }
633
634     return NULL;
635 }
636
637 /*
638  * Returns true if the given container (still) exists.
639  * This can be used, e.g., to make sure a container hasn't been closed in the meantime.
640  *
641  */
642 bool con_exists(Con *con) {
643     return con_by_con_id((long)con) != NULL;
644 }
645
646 /*
647  * Returns the container with the given frame ID or NULL if no such container
648  * exists.
649  *
650  */
651 Con *con_by_frame_id(xcb_window_t frame) {
652     Con *con;
653     TAILQ_FOREACH(con, &all_cons, all_cons)
654     if (con->frame.id == frame)
655         return con;
656     return NULL;
657 }
658
659 /*
660  * Returns the container with the given mark or NULL if no such container
661  * exists.
662  *
663  */
664 Con *con_by_mark(const char *mark) {
665     Con *con;
666     TAILQ_FOREACH(con, &all_cons, all_cons) {
667         if (con_has_mark(con, mark))
668             return con;
669     }
670
671     return NULL;
672 }
673
674 /*
675  * Returns true if and only if the given containers holds the mark.
676  *
677  */
678 bool con_has_mark(Con *con, const char *mark) {
679     mark_t *current;
680     TAILQ_FOREACH(current, &(con->marks_head), marks) {
681         if (strcmp(current->name, mark) == 0)
682             return true;
683     }
684
685     return false;
686 }
687
688 /*
689  * Toggles the mark on a container.
690  * If the container already has this mark, the mark is removed.
691  * Otherwise, the mark is assigned to the container.
692  *
693  */
694 void con_mark_toggle(Con *con, const char *mark, mark_mode_t mode) {
695     assert(con != NULL);
696     DLOG("Toggling mark \"%s\" on con = %p.\n", mark, con);
697
698     if (con_has_mark(con, mark)) {
699         con_unmark(con, mark);
700     } else {
701         con_mark(con, mark, mode);
702     }
703 }
704
705 /*
706  * Assigns a mark to the container.
707  *
708  */
709 void con_mark(Con *con, const char *mark, mark_mode_t mode) {
710     assert(con != NULL);
711     DLOG("Setting mark \"%s\" on con = %p.\n", mark, con);
712
713     con_unmark(NULL, mark);
714     if (mode == MM_REPLACE) {
715         DLOG("Removing all existing marks on con = %p.\n", con);
716
717         mark_t *current;
718         while (!TAILQ_EMPTY(&(con->marks_head))) {
719             current = TAILQ_FIRST(&(con->marks_head));
720             con_unmark(con, current->name);
721         }
722     }
723
724     mark_t *new = scalloc(1, sizeof(mark_t));
725     new->name = sstrdup(mark);
726     TAILQ_INSERT_TAIL(&(con->marks_head), new, marks);
727     ipc_send_window_event("mark", con);
728
729     con->mark_changed = true;
730 }
731
732 /*
733  * Removes marks from containers.
734  * If con is NULL, all containers are considered.
735  * If name is NULL, this removes all existing marks.
736  * Otherwise, it will only remove the given mark (if it is present).
737  *
738  */
739 void con_unmark(Con *con, const char *name) {
740     Con *current;
741     if (name == NULL) {
742         DLOG("Unmarking all containers.\n");
743         TAILQ_FOREACH(current, &all_cons, all_cons) {
744             if (con != NULL && current != con)
745                 continue;
746
747             if (TAILQ_EMPTY(&(current->marks_head)))
748                 continue;
749
750             mark_t *mark;
751             while (!TAILQ_EMPTY(&(current->marks_head))) {
752                 mark = TAILQ_FIRST(&(current->marks_head));
753                 FREE(mark->name);
754                 TAILQ_REMOVE(&(current->marks_head), mark, marks);
755                 FREE(mark);
756
757                 ipc_send_window_event("mark", current);
758             }
759
760             current->mark_changed = true;
761         }
762     } else {
763         DLOG("Removing mark \"%s\".\n", name);
764         current = (con == NULL) ? con_by_mark(name) : con;
765         if (current == NULL) {
766             DLOG("No container found with this mark, so there is nothing to do.\n");
767             return;
768         }
769
770         DLOG("Found mark on con = %p. Removing it now.\n", current);
771         current->mark_changed = true;
772
773         mark_t *mark;
774         TAILQ_FOREACH(mark, &(current->marks_head), marks) {
775             if (strcmp(mark->name, name) != 0)
776                 continue;
777
778             FREE(mark->name);
779             TAILQ_REMOVE(&(current->marks_head), mark, marks);
780             FREE(mark);
781
782             ipc_send_window_event("mark", current);
783             break;
784         }
785     }
786 }
787
788 /*
789  * Returns the first container below 'con' which wants to swallow this window
790  * TODO: priority
791  *
792  */
793 Con *con_for_window(Con *con, i3Window *window, Match **store_match) {
794     Con *child;
795     Match *match;
796     //DLOG("searching con for window %p starting at con %p\n", window, con);
797     //DLOG("class == %s\n", window->class_class);
798
799     TAILQ_FOREACH(child, &(con->nodes_head), nodes) {
800         TAILQ_FOREACH(match, &(child->swallow_head), matches) {
801             if (!match_matches_window(match, window))
802                 continue;
803             if (store_match != NULL)
804                 *store_match = match;
805             return child;
806         }
807         Con *result = con_for_window(child, window, store_match);
808         if (result != NULL)
809             return result;
810     }
811
812     TAILQ_FOREACH(child, &(con->floating_head), floating_windows) {
813         TAILQ_FOREACH(match, &(child->swallow_head), matches) {
814             if (!match_matches_window(match, window))
815                 continue;
816             if (store_match != NULL)
817                 *store_match = match;
818             return child;
819         }
820         Con *result = con_for_window(child, window, store_match);
821         if (result != NULL)
822             return result;
823     }
824
825     return NULL;
826 }
827
828 static int num_focus_heads(Con *con) {
829     int focus_heads = 0;
830
831     Con *current;
832     TAILQ_FOREACH(current, &(con->focus_head), focused) {
833         focus_heads++;
834     }
835
836     return focus_heads;
837 }
838
839 /*
840  * Iterate over the container's focus stack and return an array with the
841  * containers inside it, ordered from higher focus order to lowest.
842  *
843  */
844 Con **get_focus_order(Con *con) {
845     const int focus_heads = num_focus_heads(con);
846     Con **focus_order = smalloc(focus_heads * sizeof(Con *));
847     Con *current;
848     int idx = 0;
849     TAILQ_FOREACH(current, &(con->focus_head), focused) {
850         assert(idx < focus_heads);
851         focus_order[idx++] = current;
852     }
853
854     return focus_order;
855 }
856
857 /*
858  * Clear the container's focus stack and re-add it using the provided container
859  * array. The function doesn't check if the provided array contains the same
860  * containers with the previous focus stack but will not add floating containers
861  * in the new focus stack if container is not a workspace.
862  *
863  */
864 void set_focus_order(Con *con, Con **focus_order) {
865     int focus_heads = 0;
866     while (!TAILQ_EMPTY(&(con->focus_head))) {
867         Con *current = TAILQ_FIRST(&(con->focus_head));
868
869         TAILQ_REMOVE(&(con->focus_head), current, focused);
870         focus_heads++;
871     }
872
873     for (int idx = 0; idx < focus_heads; idx++) {
874         /* Useful when encapsulating a workspace. */
875         if (con->type != CT_WORKSPACE && con_inside_floating(focus_order[idx])) {
876             focus_heads++;
877             continue;
878         }
879
880         TAILQ_INSERT_TAIL(&(con->focus_head), focus_order[idx], focused);
881     }
882 }
883
884 /*
885  * Returns the number of children of this container.
886  *
887  */
888 int con_num_children(Con *con) {
889     Con *child;
890     int children = 0;
891
892     TAILQ_FOREACH(child, &(con->nodes_head), nodes)
893     children++;
894
895     return children;
896 }
897
898 /*
899  * Returns the number of visible non-floating children of this container.
900  * For example, if the container contains a hsplit which has two children,
901  * this will return 2 instead of 1.
902  */
903 int con_num_visible_children(Con *con) {
904     if (con == NULL)
905         return 0;
906
907     int children = 0;
908     Con *current = NULL;
909     TAILQ_FOREACH(current, &(con->nodes_head), nodes) {
910         /* Visible leaf nodes are a child. */
911         if (!con_is_hidden(current) && con_is_leaf(current))
912             children++;
913         /* All other containers need to be recursed. */
914         else
915             children += con_num_visible_children(current);
916     }
917
918     return children;
919 }
920
921 /*
922  * Count the number of windows (i.e., leaf containers).
923  *
924  */
925 int con_num_windows(Con *con) {
926     if (con == NULL)
927         return 0;
928
929     if (con_has_managed_window(con))
930         return 1;
931
932     int num = 0;
933     Con *current = NULL;
934     TAILQ_FOREACH(current, &(con->nodes_head), nodes) {
935         num += con_num_windows(current);
936     }
937
938     TAILQ_FOREACH(current, &(con->floating_head), floating_windows) {
939         num += con_num_windows(current);
940     }
941
942     return num;
943 }
944
945 /*
946  * Updates the percent attribute of the children of the given container. This
947  * function needs to be called when a window is added or removed from a
948  * container.
949  *
950  */
951 void con_fix_percent(Con *con) {
952     Con *child;
953     int children = con_num_children(con);
954
955     // calculate how much we have distributed and how many containers
956     // with a percentage set we have
957     double total = 0.0;
958     int children_with_percent = 0;
959     TAILQ_FOREACH(child, &(con->nodes_head), nodes) {
960         if (child->percent > 0.0) {
961             total += child->percent;
962             ++children_with_percent;
963         }
964     }
965
966     // if there were children without a percentage set, set to a value that
967     // will make those children proportional to all others
968     if (children_with_percent != children) {
969         TAILQ_FOREACH(child, &(con->nodes_head), nodes) {
970             if (child->percent <= 0.0) {
971                 if (children_with_percent == 0) {
972                     total += (child->percent = 1.0);
973                 } else {
974                     total += (child->percent = total / children_with_percent);
975                 }
976             }
977         }
978     }
979
980     // if we got a zero, just distribute the space equally, otherwise
981     // distribute according to the proportions we got
982     if (total == 0.0) {
983         TAILQ_FOREACH(child, &(con->nodes_head), nodes) {
984             child->percent = 1.0 / children;
985         }
986     } else if (total != 1.0) {
987         TAILQ_FOREACH(child, &(con->nodes_head), nodes) {
988             child->percent /= total;
989         }
990     }
991 }
992
993 /*
994  * Toggles fullscreen mode for the given container. If there already is a
995  * fullscreen container on this workspace, fullscreen will be disabled and then
996  * enabled for the container the user wants to have in fullscreen mode.
997  *
998  */
999 void con_toggle_fullscreen(Con *con, int fullscreen_mode) {
1000     if (con->type == CT_WORKSPACE) {
1001         DLOG("You cannot make a workspace fullscreen.\n");
1002         return;
1003     }
1004
1005     DLOG("toggling fullscreen for %p / %s\n", con, con->name);
1006
1007     if (con->fullscreen_mode == CF_NONE)
1008         con_enable_fullscreen(con, fullscreen_mode);
1009     else
1010         con_disable_fullscreen(con);
1011 }
1012
1013 /*
1014  * Sets the specified fullscreen mode for the given container, sends the
1015  * “fullscreen_mode” event and changes the XCB fullscreen property of the
1016  * container’s window, if any.
1017  *
1018  */
1019 static void con_set_fullscreen_mode(Con *con, fullscreen_mode_t fullscreen_mode) {
1020     con->fullscreen_mode = fullscreen_mode;
1021
1022     DLOG("mode now: %d\n", con->fullscreen_mode);
1023
1024     /* Send an ipc window "fullscreen_mode" event */
1025     ipc_send_window_event("fullscreen_mode", con);
1026
1027     /* update _NET_WM_STATE if this container has a window */
1028     /* TODO: when a window is assigned to a container which is already
1029      * fullscreened, this state needs to be pushed to the client, too */
1030     if (con->window == NULL)
1031         return;
1032
1033     if (con->fullscreen_mode != CF_NONE) {
1034         DLOG("Setting _NET_WM_STATE_FULLSCREEN for con = %p / window = %d.\n", con, con->window->id);
1035         xcb_add_property_atom(conn, con->window->id, A__NET_WM_STATE, A__NET_WM_STATE_FULLSCREEN);
1036     } else {
1037         DLOG("Removing _NET_WM_STATE_FULLSCREEN for con = %p / window = %d.\n", con, con->window->id);
1038         xcb_remove_property_atom(conn, con->window->id, A__NET_WM_STATE, A__NET_WM_STATE_FULLSCREEN);
1039     }
1040 }
1041
1042 /*
1043  * Enables fullscreen mode for the given container, if necessary.
1044  *
1045  * If the container’s mode is already CF_OUTPUT or CF_GLOBAL, the container is
1046  * kept fullscreen but its mode is set to CF_GLOBAL and CF_OUTPUT,
1047  * respectively.
1048  *
1049  * Other fullscreen containers will be disabled first, if they hide the new
1050  * one.
1051  *
1052  */
1053 void con_enable_fullscreen(Con *con, fullscreen_mode_t fullscreen_mode) {
1054     if (con->type == CT_WORKSPACE) {
1055         DLOG("You cannot make a workspace fullscreen.\n");
1056         return;
1057     }
1058
1059     assert(fullscreen_mode == CF_GLOBAL || fullscreen_mode == CF_OUTPUT);
1060
1061     if (fullscreen_mode == CF_GLOBAL)
1062         DLOG("enabling global fullscreen for %p / %s\n", con, con->name);
1063     else
1064         DLOG("enabling fullscreen for %p / %s\n", con, con->name);
1065
1066     if (con->fullscreen_mode == fullscreen_mode) {
1067         DLOG("fullscreen already enabled for %p / %s\n", con, con->name);
1068         return;
1069     }
1070
1071     Con *con_ws = con_get_workspace(con);
1072
1073     /* Disable any fullscreen container that would conflict the new one. */
1074     Con *fullscreen = con_get_fullscreen_con(croot, CF_GLOBAL);
1075     if (fullscreen == NULL)
1076         fullscreen = con_get_fullscreen_con(con_ws, CF_OUTPUT);
1077     if (fullscreen != NULL)
1078         con_disable_fullscreen(fullscreen);
1079
1080     /* Set focus to new fullscreen container. Unless in global fullscreen mode
1081      * and on another workspace restore focus afterwards.
1082      * Switch to the container’s workspace if mode is global. */
1083     Con *cur_ws = con_get_workspace(focused);
1084     Con *old_focused = focused;
1085     if (fullscreen_mode == CF_GLOBAL && cur_ws != con_ws)
1086         workspace_show(con_ws);
1087     con_activate(con);
1088     if (fullscreen_mode != CF_GLOBAL && cur_ws != con_ws)
1089         con_activate(old_focused);
1090
1091     con_set_fullscreen_mode(con, fullscreen_mode);
1092 }
1093
1094 /*
1095  * Disables fullscreen mode for the given container regardless of the mode, if
1096  * necessary.
1097  *
1098  */
1099 void con_disable_fullscreen(Con *con) {
1100     if (con->type == CT_WORKSPACE) {
1101         DLOG("You cannot make a workspace fullscreen.\n");
1102         return;
1103     }
1104
1105     DLOG("disabling fullscreen for %p / %s\n", con, con->name);
1106
1107     if (con->fullscreen_mode == CF_NONE) {
1108         DLOG("fullscreen already disabled for %p / %s\n", con, con->name);
1109         return;
1110     }
1111
1112     con_set_fullscreen_mode(con, CF_NONE);
1113 }
1114
1115 static bool _con_move_to_con(Con *con, Con *target, bool behind_focused, bool fix_coordinates, bool dont_warp, bool ignore_focus, bool fix_percentage) {
1116     Con *orig_target = target;
1117
1118     /* Prevent moving if this would violate the fullscreen focus restrictions. */
1119     Con *target_ws = con_get_workspace(target);
1120     if (!ignore_focus && !con_fullscreen_permits_focusing(target_ws)) {
1121         LOG("Cannot move out of a fullscreen container.\n");
1122         return false;
1123     }
1124
1125     if (con_is_floating(con)) {
1126         DLOG("Container is floating, using parent instead.\n");
1127         con = con->parent;
1128     }
1129
1130     Con *source_ws = con_get_workspace(con);
1131
1132     if (con->type == CT_WORKSPACE) {
1133         /* Re-parent all of the old workspace's floating windows. */
1134         Con *child;
1135         while (!TAILQ_EMPTY(&(source_ws->floating_head))) {
1136             child = TAILQ_FIRST(&(source_ws->floating_head));
1137             con_move_to_workspace(child, target_ws, true, true, false);
1138         }
1139
1140         /* If there are no non-floating children, ignore the workspace. */
1141         if (con_is_leaf(con))
1142             return false;
1143
1144         con = workspace_encapsulate(con);
1145         if (con == NULL) {
1146             ELOG("Workspace failed to move its contents into a container!\n");
1147             return false;
1148         }
1149     }
1150
1151     /* Save the urgency state so that we can restore it. */
1152     bool urgent = con->urgent;
1153
1154     /* Save the current workspace. So we can call workspace_show() by the end
1155      * of this function. */
1156     Con *current_ws = con_get_workspace(focused);
1157
1158     Con *source_output = con_get_output(con),
1159         *dest_output = con_get_output(target_ws);
1160
1161     /* 1: save the container which is going to be focused after the current
1162      * container is moved away */
1163     Con *focus_next = NULL;
1164     if (!ignore_focus && source_ws == current_ws) {
1165         focus_next = con_descend_focused(source_ws);
1166         if (focus_next == con || con_has_parent(focus_next, con)) {
1167             focus_next = con_next_focused(con);
1168         }
1169     }
1170
1171     /* 2: we go up one level, but only when target is a normal container */
1172     if (target->type != CT_WORKSPACE) {
1173         DLOG("target originally = %p / %s / type %d\n", target, target->name, target->type);
1174         target = target->parent;
1175     }
1176
1177     /* 3: if the original target is the direct child of a floating container, we
1178      * can't move con next to it - floating containers have only one child - so
1179      * we get the workspace instead. */
1180     if (target->type == CT_FLOATING_CON) {
1181         DLOG("floatingcon, going up even further\n");
1182         orig_target = target;
1183         target = target->parent;
1184     }
1185
1186     if (con->type == CT_FLOATING_CON) {
1187         Con *ws = con_get_workspace(target);
1188         DLOG("This is a floating window, using workspace %p / %s\n", ws, ws->name);
1189         target = ws;
1190     }
1191
1192     if (source_output != dest_output) {
1193         /* Take the relative coordinates of the current output, then add them
1194          * to the coordinate space of the correct output */
1195         if (fix_coordinates && con->type == CT_FLOATING_CON) {
1196             floating_fix_coordinates(con, &(source_output->rect), &(dest_output->rect));
1197         } else
1198             DLOG("Not fixing coordinates, fix_coordinates flag = %d\n", fix_coordinates);
1199     }
1200
1201     /* If moving a fullscreen container and the destination already has a
1202      * fullscreen window on it, un-fullscreen the target's fullscreen con. */
1203     Con *fullscreen = con_get_fullscreen_con(target_ws, CF_OUTPUT);
1204     if (con->fullscreen_mode != CF_NONE && fullscreen != NULL) {
1205         con_toggle_fullscreen(fullscreen, CF_OUTPUT);
1206         fullscreen = NULL;
1207     }
1208
1209     DLOG("Re-attaching container to %p / %s\n", target, target->name);
1210     /* 4: re-attach the con to the parent of this focused container */
1211     Con *parent = con->parent;
1212     con_detach(con);
1213     _con_attach(con, target, behind_focused ? NULL : orig_target, !behind_focused);
1214
1215     /* 5: fix the percentages */
1216     if (fix_percentage) {
1217         con_fix_percent(parent);
1218         con->percent = 0.0;
1219         con_fix_percent(target);
1220     }
1221
1222     /* 6: focus the con on the target workspace, but only within that
1223      * workspace, that is, don’t move focus away if the target workspace is
1224      * invisible.
1225      * We don’t focus the con for i3 pseudo workspaces like __i3_scratch and
1226      * we don’t focus when there is a fullscreen con on that workspace. We
1227      * also don't do it if the caller requested to ignore focus. */
1228     if (!ignore_focus && !con_is_internal(target_ws) && !fullscreen) {
1229         /* We need to save the focused workspace on the output in case the
1230          * new workspace is hidden and it's necessary to immediately switch
1231          * back to the originally-focused workspace. */
1232         Con *old_focus_ws = TAILQ_FIRST(&(output_get_content(dest_output)->focus_head));
1233         Con *old_focus = focused;
1234         con_activate(con_descend_focused(con));
1235
1236         if (old_focus_ws == current_ws && old_focus->type != CT_WORKSPACE) {
1237             /* Restore focus to the currently focused container. */
1238             con_activate(old_focus);
1239         } else if (con_get_workspace(focused) != old_focus_ws) {
1240             /* Restore focus if the output's focused workspace has changed. */
1241             con_focus(con_descend_focused(old_focus_ws));
1242         }
1243     }
1244
1245     /* 7: when moving to another workspace, we leave the focus on the current
1246      * workspace. (see also #809) */
1247     if (!ignore_focus) {
1248         workspace_show(current_ws);
1249         if (dont_warp) {
1250             DLOG("x_set_warp_to(NULL) because dont_warp is set\n");
1251             x_set_warp_to(NULL);
1252         }
1253     }
1254
1255     /* Set focus only if con was on current workspace before moving.
1256      * Otherwise we would give focus to some window on different workspace. */
1257     if (focus_next)
1258         con_activate(con_descend_focused(focus_next));
1259
1260     /* 8. If anything within the container is associated with a startup sequence,
1261      * delete it so child windows won't be created on the old workspace. */
1262     struct Startup_Sequence *sequence;
1263     xcb_get_property_cookie_t cookie;
1264     xcb_get_property_reply_t *startup_id_reply;
1265
1266     if (!con_is_leaf(con)) {
1267         Con *child;
1268         TAILQ_FOREACH(child, &(con->nodes_head), nodes) {
1269             if (!child->window)
1270                 continue;
1271
1272             cookie = xcb_get_property(conn, false, child->window->id,
1273                                       A__NET_STARTUP_ID, XCB_GET_PROPERTY_TYPE_ANY, 0, 512);
1274             startup_id_reply = xcb_get_property_reply(conn, cookie, NULL);
1275
1276             sequence = startup_sequence_get(child->window, startup_id_reply, true);
1277             if (sequence != NULL)
1278                 startup_sequence_delete(sequence);
1279         }
1280     }
1281
1282     if (con->window) {
1283         cookie = xcb_get_property(conn, false, con->window->id,
1284                                   A__NET_STARTUP_ID, XCB_GET_PROPERTY_TYPE_ANY, 0, 512);
1285         startup_id_reply = xcb_get_property_reply(conn, cookie, NULL);
1286
1287         sequence = startup_sequence_get(con->window, startup_id_reply, true);
1288         if (sequence != NULL)
1289             startup_sequence_delete(sequence);
1290     }
1291
1292     /* 9. If the container was marked urgent, move the urgency hint. */
1293     if (urgent) {
1294         workspace_update_urgent_flag(source_ws);
1295         con_set_urgency(con, true);
1296     }
1297
1298     /* Ensure the container will be redrawn. */
1299     FREE(con->deco_render_params);
1300
1301     CALL(parent, on_remove_child);
1302
1303     ipc_send_window_event("move", con);
1304     ewmh_update_wm_desktop();
1305     return true;
1306 }
1307
1308 /*
1309  * Moves the given container to the given mark.
1310  *
1311  */
1312 bool con_move_to_mark(Con *con, const char *mark) {
1313     Con *target = con_by_mark(mark);
1314     if (target == NULL) {
1315         DLOG("found no container with mark \"%s\"\n", mark);
1316         return false;
1317     }
1318
1319     /* For floating target containers, we just send the window to the same workspace. */
1320     if (con_is_floating(target)) {
1321         DLOG("target container is floating, moving container to target's workspace.\n");
1322         con_move_to_workspace(con, con_get_workspace(target), true, false, false);
1323         return true;
1324     }
1325
1326     if (target->type == CT_WORKSPACE) {
1327         DLOG("target container is a workspace, simply moving the container there.\n");
1328         con_move_to_workspace(con, target, true, false, false);
1329         return true;
1330     }
1331
1332     /* For split containers, we use the currently focused container within it.
1333      * This allows setting marks on, e.g., tabbed containers which will move
1334      * con to a new tab behind the focused tab. */
1335     if (con_is_split(target)) {
1336         DLOG("target is a split container, descending to the currently focused child.\n");
1337         target = TAILQ_FIRST(&(target->focus_head));
1338     }
1339
1340     if (con == target || con_has_parent(target, con)) {
1341         DLOG("cannot move the container to or inside itself, aborting.\n");
1342         return false;
1343     }
1344
1345     return _con_move_to_con(con, target, false, true, false, false, true);
1346 }
1347
1348 /*
1349  * Moves the given container to the currently focused container on the given
1350  * workspace.
1351  *
1352  * The fix_coordinates flag will translate the current coordinates (offset from
1353  * the monitor position basically) to appropriate coordinates on the
1354  * destination workspace.
1355  * Not enabling this behaviour comes in handy when this function gets called by
1356  * floating_maybe_reassign_ws, which will only "move" a floating window when it
1357  * *already* changed its coordinates to a different output.
1358  *
1359  * The dont_warp flag disables pointer warping and will be set when this
1360  * function is called while dragging a floating window.
1361  *
1362  * If ignore_focus is set, the container will be moved without modifying focus
1363  * at all.
1364  *
1365  * TODO: is there a better place for this function?
1366  *
1367  */
1368 void con_move_to_workspace(Con *con, Con *workspace, bool fix_coordinates, bool dont_warp, bool ignore_focus) {
1369     assert(workspace->type == CT_WORKSPACE);
1370
1371     Con *source_ws = con_get_workspace(con);
1372     if (workspace == source_ws) {
1373         DLOG("Not moving, already there\n");
1374         return;
1375     }
1376
1377     Con *target = con_descend_focused(workspace);
1378     _con_move_to_con(con, target, true, fix_coordinates, dont_warp, ignore_focus, true);
1379 }
1380
1381 /*
1382  * Moves the given container to the currently focused container on the
1383  * visible workspace on the given output.
1384  *
1385  */
1386 void con_move_to_output(Con *con, Output *output, bool fix_coordinates) {
1387     Con *ws = NULL;
1388     GREP_FIRST(ws, output_get_content(output->con), workspace_is_visible(child));
1389     assert(ws != NULL);
1390     DLOG("Moving con %p to output %s\n", con, output_primary_name(output));
1391     con_move_to_workspace(con, ws, fix_coordinates, false, false);
1392 }
1393
1394 /*
1395  * Moves the given container to the currently focused container on the
1396  * visible workspace on the output specified by the given name.
1397  * The current output for the container is used to resolve relative names
1398  * such as left, right, up, down.
1399  *
1400  */
1401 bool con_move_to_output_name(Con *con, const char *name, bool fix_coordinates) {
1402     Output *current_output = get_output_for_con(con);
1403     assert(current_output != NULL);
1404
1405     Output *output = get_output_from_string(current_output, name);
1406     if (output == NULL) {
1407         ELOG("Could not find output \"%s\"\n", name);
1408         return false;
1409     }
1410
1411     con_move_to_output(con, output, fix_coordinates);
1412     return true;
1413 }
1414
1415 /*
1416  * Returns the orientation of the given container (for stacked containers,
1417  * vertical orientation is used regardless of the actual orientation of the
1418  * container).
1419  *
1420  */
1421 orientation_t con_orientation(Con *con) {
1422     switch (con->layout) {
1423         case L_SPLITV:
1424         /* stacking containers behave like they are in vertical orientation */
1425         case L_STACKED:
1426             return VERT;
1427
1428         case L_SPLITH:
1429         /* tabbed containers behave like they are in vertical orientation */
1430         case L_TABBED:
1431             return HORIZ;
1432
1433         case L_DEFAULT:
1434             ELOG("Someone called con_orientation() on a con with L_DEFAULT, this is a bug in the code.\n");
1435             assert(false);
1436
1437         case L_DOCKAREA:
1438         case L_OUTPUT:
1439             ELOG("con_orientation() called on dockarea/output (%d) container %p\n", con->layout, con);
1440             assert(false);
1441     }
1442     /* should not be reached */
1443     assert(false);
1444 }
1445
1446 /*
1447  * Returns the container which will be focused next when the given container
1448  * is not available anymore. Called in tree_close_internal and con_move_to_workspace
1449  * to properly restore focus.
1450  *
1451  */
1452 Con *con_next_focused(Con *con) {
1453     /* dock clients cannot be focused, so we focus the workspace instead */
1454     if (con->parent->type == CT_DOCKAREA) {
1455         DLOG("selecting workspace for dock client\n");
1456         return con_descend_focused(output_get_content(con->parent->parent));
1457     }
1458     if (con_is_floating(con)) {
1459         con = con->parent;
1460     }
1461
1462     /* if 'con' is not the first entry in the focus stack, use the first one as
1463      * it’s currently focused already */
1464     Con *next = TAILQ_FIRST(&(con->parent->focus_head));
1465     if (next != con) {
1466         DLOG("Using first entry %p\n", next);
1467     } else {
1468         /* try to focus the next container on the same level as this one or fall
1469          * back to its parent */
1470         if (!(next = TAILQ_NEXT(con, focused))) {
1471             next = con->parent;
1472         }
1473     }
1474
1475     /* now go down the focus stack as far as
1476      * possible, excluding the current container */
1477     while (!TAILQ_EMPTY(&(next->focus_head)) && TAILQ_FIRST(&(next->focus_head)) != con) {
1478         next = TAILQ_FIRST(&(next->focus_head));
1479     }
1480
1481     if (con->type == CT_FLOATING_CON && next != con->parent) {
1482         next = con_descend_focused(next);
1483     }
1484
1485     return next;
1486 }
1487
1488 /*
1489  * Returns the focused con inside this client, descending the tree as far as
1490  * possible. This comes in handy when attaching a con to a workspace at the
1491  * currently focused position, for example.
1492  *
1493  */
1494 Con *con_descend_focused(Con *con) {
1495     Con *next = con;
1496     while (next != focused && !TAILQ_EMPTY(&(next->focus_head)))
1497         next = TAILQ_FIRST(&(next->focus_head));
1498     return next;
1499 }
1500
1501 /*
1502  * Returns the focused con inside this client, descending the tree as far as
1503  * possible. This comes in handy when attaching a con to a workspace at the
1504  * currently focused position, for example.
1505  *
1506  * Works like con_descend_focused but considers only tiling cons.
1507  *
1508  */
1509 Con *con_descend_tiling_focused(Con *con) {
1510     Con *next = con;
1511     Con *before;
1512     Con *child;
1513     if (next == focused)
1514         return next;
1515     do {
1516         before = next;
1517         TAILQ_FOREACH(child, &(next->focus_head), focused) {
1518             if (child->type == CT_FLOATING_CON)
1519                 continue;
1520
1521             next = child;
1522             break;
1523         }
1524     } while (before != next && next != focused);
1525     return next;
1526 }
1527
1528 /*
1529  * Returns the leftmost, rightmost, etc. container in sub-tree. For example, if
1530  * direction is D_LEFT, then we return the rightmost container and if direction
1531  * is D_RIGHT, we return the leftmost container.  This is because if we are
1532  * moving D_LEFT, and thus want the rightmost container.
1533  *
1534  */
1535 Con *con_descend_direction(Con *con, direction_t direction) {
1536     Con *most = NULL;
1537     Con *current;
1538     int orientation = con_orientation(con);
1539     DLOG("con_descend_direction(%p, orientation %d, direction %d)\n", con, orientation, direction);
1540     if (direction == D_LEFT || direction == D_RIGHT) {
1541         if (orientation == HORIZ) {
1542             /* If the direction is horizontal, we can use either the first
1543              * (D_RIGHT) or the last con (D_LEFT) */
1544             if (direction == D_RIGHT)
1545                 most = TAILQ_FIRST(&(con->nodes_head));
1546             else
1547                 most = TAILQ_LAST(&(con->nodes_head), nodes_head);
1548         } else if (orientation == VERT) {
1549             /* Wrong orientation. We use the last focused con. Within that con,
1550              * we recurse to chose the left/right con or at least the last
1551              * focused one. */
1552             TAILQ_FOREACH(current, &(con->focus_head), focused) {
1553                 if (current->type != CT_FLOATING_CON) {
1554                     most = current;
1555                     break;
1556                 }
1557             }
1558         } else {
1559             /* If the con has no orientation set, it’s not a split container
1560              * but a container with a client window, so stop recursing */
1561             return con;
1562         }
1563     }
1564
1565     if (direction == D_UP || direction == D_DOWN) {
1566         if (orientation == VERT) {
1567             /* If the direction is vertical, we can use either the first
1568              * (D_DOWN) or the last con (D_UP) */
1569             if (direction == D_UP)
1570                 most = TAILQ_LAST(&(con->nodes_head), nodes_head);
1571             else
1572                 most = TAILQ_FIRST(&(con->nodes_head));
1573         } else if (orientation == HORIZ) {
1574             /* Wrong orientation. We use the last focused con. Within that con,
1575              * we recurse to chose the top/bottom con or at least the last
1576              * focused one. */
1577             TAILQ_FOREACH(current, &(con->focus_head), focused) {
1578                 if (current->type != CT_FLOATING_CON) {
1579                     most = current;
1580                     break;
1581                 }
1582             }
1583         } else {
1584             /* If the con has no orientation set, it’s not a split container
1585              * but a container with a client window, so stop recursing */
1586             return con;
1587         }
1588     }
1589
1590     if (!most)
1591         return con;
1592     return con_descend_direction(most, direction);
1593 }
1594
1595 /*
1596  * Returns a "relative" Rect which contains the amount of pixels that need to
1597  * be added to the original Rect to get the final position (obviously the
1598  * amount of pixels for normal, 1pixel and borderless are different).
1599  *
1600  */
1601 Rect con_border_style_rect(Con *con) {
1602     if (config.hide_edge_borders == HEBM_SMART && con_num_visible_children(con_get_workspace(con)) <= 1) {
1603         if (!con_is_floating(con)) {
1604             return (Rect){0, 0, 0, 0};
1605         }
1606     }
1607
1608     adjacent_t borders_to_hide = ADJ_NONE;
1609     int border_width = con->current_border_width;
1610     DLOG("The border width for con is set to: %d\n", con->current_border_width);
1611     Rect result;
1612     if (con->current_border_width < 0) {
1613         if (con_is_floating(con)) {
1614             border_width = config.default_floating_border_width;
1615         } else {
1616             border_width = config.default_border_width;
1617         }
1618     }
1619     DLOG("Effective border width is set to: %d\n", border_width);
1620     /* Shortcut to avoid calling con_adjacent_borders() on dock containers. */
1621     int border_style = con_border_style(con);
1622     if (border_style == BS_NONE)
1623         return (Rect){0, 0, 0, 0};
1624     if (border_style == BS_NORMAL) {
1625         result = (Rect){border_width, 0, -(2 * border_width), -(border_width)};
1626     } else {
1627         result = (Rect){border_width, border_width, -(2 * border_width), -(2 * border_width)};
1628     }
1629
1630     borders_to_hide = con_adjacent_borders(con) & config.hide_edge_borders;
1631     if (borders_to_hide & ADJ_LEFT_SCREEN_EDGE) {
1632         result.x -= border_width;
1633         result.width += border_width;
1634     }
1635     if (borders_to_hide & ADJ_RIGHT_SCREEN_EDGE) {
1636         result.width += border_width;
1637     }
1638     if (borders_to_hide & ADJ_UPPER_SCREEN_EDGE && (border_style != BS_NORMAL)) {
1639         result.y -= border_width;
1640         result.height += border_width;
1641     }
1642     if (borders_to_hide & ADJ_LOWER_SCREEN_EDGE) {
1643         result.height += border_width;
1644     }
1645     return result;
1646 }
1647
1648 /*
1649  * Returns adjacent borders of the window. We need this if hide_edge_borders is
1650  * enabled.
1651  */
1652 adjacent_t con_adjacent_borders(Con *con) {
1653     adjacent_t result = ADJ_NONE;
1654     /* Floating windows are never adjacent to any other window, so
1655        don’t hide their border(s). This prevents bug #998. */
1656     if (con_is_floating(con))
1657         return result;
1658
1659     Con *workspace = con_get_workspace(con);
1660     if (con->rect.x == workspace->rect.x)
1661         result |= ADJ_LEFT_SCREEN_EDGE;
1662     if (con->rect.x + con->rect.width == workspace->rect.x + workspace->rect.width)
1663         result |= ADJ_RIGHT_SCREEN_EDGE;
1664     if (con->rect.y == workspace->rect.y)
1665         result |= ADJ_UPPER_SCREEN_EDGE;
1666     if (con->rect.y + con->rect.height == workspace->rect.y + workspace->rect.height)
1667         result |= ADJ_LOWER_SCREEN_EDGE;
1668     return result;
1669 }
1670
1671 /*
1672  * Use this function to get a container’s border style. This is important
1673  * because when inside a stack, the border style is always BS_NORMAL.
1674  * For tabbed mode, the same applies, with one exception: when the container is
1675  * borderless and the only element in the tabbed container, the border is not
1676  * rendered.
1677  *
1678  * For children of a CT_DOCKAREA, the border style is always none.
1679  *
1680  */
1681 int con_border_style(Con *con) {
1682     if (con->fullscreen_mode == CF_OUTPUT || con->fullscreen_mode == CF_GLOBAL) {
1683         DLOG("this one is fullscreen! overriding BS_NONE\n");
1684         return BS_NONE;
1685     }
1686
1687     if (con->parent->layout == L_STACKED)
1688         return (con_num_children(con->parent) == 1 ? con->border_style : BS_NORMAL);
1689
1690     if (con->parent->layout == L_TABBED && con->border_style != BS_NORMAL)
1691         return (con_num_children(con->parent) == 1 ? con->border_style : BS_NORMAL);
1692
1693     if (con->parent->type == CT_DOCKAREA)
1694         return BS_NONE;
1695
1696     return con->border_style;
1697 }
1698
1699 /*
1700  * Sets the given border style on con, correctly keeping the position/size of a
1701  * floating window.
1702  *
1703  */
1704 void con_set_border_style(Con *con, int border_style, int border_width) {
1705     /* Handle the simple case: non-floating containerns */
1706     if (!con_is_floating(con)) {
1707         con->border_style = border_style;
1708         con->current_border_width = border_width;
1709         return;
1710     }
1711
1712     /* For floating containers, we want to keep the position/size of the
1713      * *window* itself. We first add the border pixels to con->rect to make
1714      * con->rect represent the absolute position of the window (same for
1715      * parent). Then, we change the border style and subtract the new border
1716      * pixels. For the parent, we do the same also for the decoration. */
1717     DLOG("This is a floating container\n");
1718
1719     Con *parent = con->parent;
1720     Rect bsr = con_border_style_rect(con);
1721     int deco_height = (con->border_style == BS_NORMAL ? render_deco_height() : 0);
1722
1723     con->rect = rect_add(con->rect, bsr);
1724     parent->rect = rect_add(parent->rect, bsr);
1725     parent->rect.y += deco_height;
1726     parent->rect.height -= deco_height;
1727
1728     /* Change the border style, get new border/decoration values. */
1729     con->border_style = border_style;
1730     con->current_border_width = border_width;
1731     bsr = con_border_style_rect(con);
1732     deco_height = (con->border_style == BS_NORMAL ? render_deco_height() : 0);
1733
1734     con->rect = rect_sub(con->rect, bsr);
1735     parent->rect = rect_sub(parent->rect, bsr);
1736     parent->rect.y -= deco_height;
1737     parent->rect.height += deco_height;
1738 }
1739
1740 /*
1741  * This function changes the layout of a given container. Use it to handle
1742  * special cases like changing a whole workspace to stacked/tabbed (creates a
1743  * new split container before).
1744  *
1745  */
1746 void con_set_layout(Con *con, layout_t layout) {
1747     DLOG("con_set_layout(%p, %d), con->type = %d\n",
1748          con, layout, con->type);
1749
1750     /* Users can focus workspaces, but not any higher in the hierarchy.
1751      * Focus on the workspace is a special case, since in every other case, the
1752      * user means "change the layout of the parent split container". */
1753     if (con->type != CT_WORKSPACE)
1754         con = con->parent;
1755
1756     /* We fill in last_split_layout when switching to a different layout
1757      * since there are many places in the code that don’t use
1758      * con_set_layout(). */
1759     if (con->layout == L_SPLITH || con->layout == L_SPLITV)
1760         con->last_split_layout = con->layout;
1761
1762     /* When the container type is CT_WORKSPACE, the user wants to change the
1763      * whole workspace into stacked/tabbed mode. To do this and still allow
1764      * intuitive operations (like level-up and then opening a new window), we
1765      * need to create a new split container. */
1766     if (con->type == CT_WORKSPACE) {
1767         if (con_num_children(con) == 0) {
1768             layout_t ws_layout = (layout == L_STACKED || layout == L_TABBED) ? layout : L_DEFAULT;
1769             DLOG("Setting workspace_layout to %d\n", ws_layout);
1770             con->workspace_layout = ws_layout;
1771             DLOG("Setting layout to %d\n", layout);
1772             con->layout = layout;
1773         } else if (layout == L_STACKED || layout == L_TABBED || layout == L_SPLITV || layout == L_SPLITH) {
1774             DLOG("Creating new split container\n");
1775             /* 1: create a new split container */
1776             Con *new = con_new(NULL, NULL);
1777             new->parent = con;
1778
1779             /* 2: Set the requested layout on the split container and mark it as
1780              * split. */
1781             new->layout = layout;
1782             new->last_split_layout = con->last_split_layout;
1783
1784             /* 3: move the existing cons of this workspace below the new con */
1785             Con **focus_order = get_focus_order(con);
1786
1787             DLOG("Moving cons\n");
1788             Con *child;
1789             while (!TAILQ_EMPTY(&(con->nodes_head))) {
1790                 child = TAILQ_FIRST(&(con->nodes_head));
1791                 con_detach(child);
1792                 con_attach(child, new, true);
1793             }
1794
1795             set_focus_order(new, focus_order);
1796             free(focus_order);
1797
1798             /* 4: attach the new split container to the workspace */
1799             DLOG("Attaching new split to ws\n");
1800             con_attach(new, con, false);
1801
1802             tree_flatten(croot);
1803         }
1804         con_force_split_parents_redraw(con);
1805         return;
1806     }
1807
1808     if (layout == L_DEFAULT) {
1809         /* Special case: the layout formerly known as "default" (in combination
1810          * with an orientation). Since we switched to splith/splitv layouts,
1811          * using the "default" layout (which "only" should happen when using
1812          * legacy configs) is using the last split layout (either splith or
1813          * splitv) in order to still do the same thing. */
1814         con->layout = con->last_split_layout;
1815         /* In case last_split_layout was not initialized… */
1816         if (con->layout == L_DEFAULT)
1817             con->layout = L_SPLITH;
1818     } else {
1819         con->layout = layout;
1820     }
1821     con_force_split_parents_redraw(con);
1822 }
1823
1824 /*
1825  * This function toggles the layout of a given container. toggle_mode can be
1826  * either 'default' (toggle only between stacked/tabbed/last_split_layout),
1827  * 'split' (toggle only between splitv/splith) or 'all' (toggle between all
1828  * layouts).
1829  *
1830  */
1831 void con_toggle_layout(Con *con, const char *toggle_mode) {
1832     Con *parent = con;
1833     /* Users can focus workspaces, but not any higher in the hierarchy.
1834      * Focus on the workspace is a special case, since in every other case, the
1835      * user means "change the layout of the parent split container". */
1836     if (con->type != CT_WORKSPACE)
1837         parent = con->parent;
1838     DLOG("con_toggle_layout(%p, %s), parent = %p\n", con, toggle_mode, parent);
1839
1840     const char delim[] = " ";
1841
1842     if (strcasecmp(toggle_mode, "split") == 0 || strstr(toggle_mode, delim)) {
1843         /* L_DEFAULT is used as a placeholder value to distinguish if
1844          * the first layout has already been saved. (it can never be L_DEFAULT) */
1845         layout_t new_layout = L_DEFAULT;
1846         bool current_layout_found = false;
1847         char *tm_dup = sstrdup(toggle_mode);
1848         char *cur_tok = strtok(tm_dup, delim);
1849
1850         for (layout_t layout; cur_tok != NULL; cur_tok = strtok(NULL, delim)) {
1851             if (strcasecmp(cur_tok, "split") == 0) {
1852                 /* Toggle between splits. When the current layout is not a split
1853                  * layout, we just switch back to last_split_layout. Otherwise, we
1854                  * change to the opposite split layout. */
1855                 if (parent->layout != L_SPLITH && parent->layout != L_SPLITV) {
1856                     layout = parent->last_split_layout;
1857                     /* In case last_split_layout was not initialized… */
1858                     if (layout == L_DEFAULT) {
1859                         layout = L_SPLITH;
1860                     }
1861                 } else {
1862                     layout = (parent->layout == L_SPLITH) ? L_SPLITV : L_SPLITH;
1863                 }
1864             } else {
1865                 bool success = layout_from_name(cur_tok, &layout);
1866                 if (!success || layout == L_DEFAULT) {
1867                     ELOG("The token '%s' was not recognized and has been skipped.\n", cur_tok);
1868                     continue;
1869                 }
1870             }
1871
1872             /* If none of the specified layouts match the current,
1873              * fall back to the first layout in the list */
1874             if (new_layout == L_DEFAULT) {
1875                 new_layout = layout;
1876             }
1877
1878             /* We found the active layout in the last iteration, so
1879              * now let's activate the current layout (next in list) */
1880             if (current_layout_found) {
1881                 new_layout = layout;
1882                 break;
1883             }
1884
1885             if (parent->layout == layout) {
1886                 current_layout_found = true;
1887             }
1888         }
1889         free(tm_dup);
1890
1891         if (new_layout != L_DEFAULT) {
1892             con_set_layout(con, new_layout);
1893         }
1894     } else if (strcasecmp(toggle_mode, "all") == 0 || strcasecmp(toggle_mode, "default") == 0) {
1895         if (parent->layout == L_STACKED)
1896             con_set_layout(con, L_TABBED);
1897         else if (parent->layout == L_TABBED) {
1898             if (strcasecmp(toggle_mode, "all") == 0)
1899                 con_set_layout(con, L_SPLITH);
1900             else
1901                 con_set_layout(con, parent->last_split_layout);
1902         } else if (parent->layout == L_SPLITH || parent->layout == L_SPLITV) {
1903             if (strcasecmp(toggle_mode, "all") == 0) {
1904                 /* When toggling through all modes, we toggle between
1905                  * splith/splitv, whereas normally we just directly jump to
1906                  * stacked. */
1907                 if (parent->layout == L_SPLITH)
1908                     con_set_layout(con, L_SPLITV);
1909                 else
1910                     con_set_layout(con, L_STACKED);
1911             } else {
1912                 con_set_layout(con, L_STACKED);
1913             }
1914         }
1915     }
1916 }
1917
1918 /*
1919  * Callback which will be called when removing a child from the given con.
1920  * Kills the container if it is empty and replaces it with the child if there
1921  * is exactly one child.
1922  *
1923  */
1924 static void con_on_remove_child(Con *con) {
1925     DLOG("on_remove_child\n");
1926
1927     /* Every container 'above' (in the hierarchy) the workspace content should
1928      * not be closed when the last child was removed */
1929     if (con->type == CT_OUTPUT ||
1930         con->type == CT_ROOT ||
1931         con->type == CT_DOCKAREA ||
1932         (con->parent != NULL && con->parent->type == CT_OUTPUT)) {
1933         DLOG("not handling, type = %d, name = %s\n", con->type, con->name);
1934         return;
1935     }
1936
1937     /* For workspaces, close them only if they're not visible anymore */
1938     if (con->type == CT_WORKSPACE) {
1939         if (TAILQ_EMPTY(&(con->focus_head)) && !workspace_is_visible(con)) {
1940             LOG("Closing old workspace (%p / %s), it is empty\n", con, con->name);
1941             yajl_gen gen = ipc_marshal_workspace_event("empty", con, NULL);
1942             tree_close_internal(con, DONT_KILL_WINDOW, false);
1943
1944             const unsigned char *payload;
1945             ylength length;
1946             y(get_buf, &payload, &length);
1947             ipc_send_event("workspace", I3_IPC_EVENT_WORKSPACE, (const char *)payload);
1948
1949             y(free);
1950         }
1951         return;
1952     }
1953
1954     con_force_split_parents_redraw(con);
1955     con->urgent = con_has_urgent_child(con);
1956     con_update_parents_urgency(con);
1957
1958     /* TODO: check if this container would swallow any other client and
1959      * don’t close it automatically. */
1960     int children = con_num_children(con);
1961     if (children == 0) {
1962         DLOG("Container empty, closing\n");
1963         tree_close_internal(con, DONT_KILL_WINDOW, false);
1964         return;
1965     }
1966 }
1967
1968 /*
1969  * Determines the minimum size of the given con by looking at its children (for
1970  * split/stacked/tabbed cons). Will be called when resizing floating cons
1971  *
1972  */
1973 Rect con_minimum_size(Con *con) {
1974     DLOG("Determining minimum size for con %p\n", con);
1975
1976     if (con_is_leaf(con)) {
1977         DLOG("leaf node, returning 75x50\n");
1978         return (Rect){0, 0, 75, 50};
1979     }
1980
1981     if (con->type == CT_FLOATING_CON) {
1982         DLOG("floating con\n");
1983         Con *child = TAILQ_FIRST(&(con->nodes_head));
1984         return con_minimum_size(child);
1985     }
1986
1987     if (con->layout == L_STACKED || con->layout == L_TABBED) {
1988         uint32_t max_width = 0, max_height = 0, deco_height = 0;
1989         Con *child;
1990         TAILQ_FOREACH(child, &(con->nodes_head), nodes) {
1991             Rect min = con_minimum_size(child);
1992             deco_height += child->deco_rect.height;
1993             max_width = max(max_width, min.width);
1994             max_height = max(max_height, min.height);
1995         }
1996         DLOG("stacked/tabbed now, returning %d x %d + deco_rect = %d\n",
1997              max_width, max_height, deco_height);
1998         return (Rect){0, 0, max_width, max_height + deco_height};
1999     }
2000
2001     /* For horizontal/vertical split containers we sum up the width (h-split)
2002      * or height (v-split) and use the maximum of the height (h-split) or width
2003      * (v-split) as minimum size. */
2004     if (con_is_split(con)) {
2005         uint32_t width = 0, height = 0;
2006         Con *child;
2007         TAILQ_FOREACH(child, &(con->nodes_head), nodes) {
2008             Rect min = con_minimum_size(child);
2009             if (con->layout == L_SPLITH) {
2010                 width += min.width;
2011                 height = max(height, min.height);
2012             } else {
2013                 height += min.height;
2014                 width = max(width, min.width);
2015             }
2016         }
2017         DLOG("split container, returning width = %d x height = %d\n", width, height);
2018         return (Rect){0, 0, width, height};
2019     }
2020
2021     ELOG("Unhandled case, type = %d, layout = %d, split = %d\n",
2022          con->type, con->layout, con_is_split(con));
2023     assert(false);
2024 }
2025
2026 /*
2027  * Returns true if changing the focus to con would be allowed considering
2028  * the fullscreen focus constraints. Specifically, if a fullscreen container or
2029  * any of its descendants is focused, this function returns true if and only if
2030  * focusing con would mean that focus would still be visible on screen, i.e.,
2031  * the newly focused container would not be obscured by a fullscreen container.
2032  *
2033  * In the simplest case, if a fullscreen container or any of its descendants is
2034  * fullscreen, this functions returns true if con is the fullscreen container
2035  * itself or any of its descendants, as this means focus wouldn't escape the
2036  * boundaries of the fullscreen container.
2037  *
2038  * In case the fullscreen container is of type CF_OUTPUT, this function returns
2039  * true if con is on a different workspace, as focus wouldn't be obscured by
2040  * the fullscreen container that is constrained to a different workspace.
2041  *
2042  * Note that this same logic can be applied to moving containers. If a
2043  * container can be focused under the fullscreen focus constraints, it can also
2044  * become a parent or sibling to the currently focused container.
2045  *
2046  */
2047 bool con_fullscreen_permits_focusing(Con *con) {
2048     /* No focus, no problem. */
2049     if (!focused)
2050         return true;
2051
2052     /* Find the first fullscreen ascendent. */
2053     Con *fs = focused;
2054     while (fs && fs->fullscreen_mode == CF_NONE)
2055         fs = fs->parent;
2056
2057     /* fs must be non-NULL since the workspace con doesn’t have CF_NONE and
2058      * there always has to be a workspace con in the hierarchy. */
2059     assert(fs != NULL);
2060     /* The most common case is we hit the workspace level. In this
2061      * situation, changing focus is also harmless. */
2062     assert(fs->fullscreen_mode != CF_NONE);
2063     if (fs->type == CT_WORKSPACE)
2064         return true;
2065
2066     /* Allow it if the container itself is the fullscreen container. */
2067     if (con == fs)
2068         return true;
2069
2070     /* If fullscreen is per-output, the focus being in a different workspace is
2071      * sufficient to guarantee that change won't leave fullscreen in bad shape. */
2072     if (fs->fullscreen_mode == CF_OUTPUT &&
2073         con_get_workspace(con) != con_get_workspace(fs)) {
2074         return true;
2075     }
2076
2077     /* Allow it only if the container to be focused is contained within the
2078      * current fullscreen container. */
2079     return con_has_parent(con, fs);
2080 }
2081
2082 /*
2083  *
2084  * Checks if the given container has an urgent child.
2085  *
2086  */
2087 bool con_has_urgent_child(Con *con) {
2088     Con *child;
2089
2090     if (con_is_leaf(con))
2091         return con->urgent;
2092
2093     /* We are not interested in floating windows since they can only be
2094      * attached to a workspace → nodes_head instead of focus_head */
2095     TAILQ_FOREACH(child, &(con->nodes_head), nodes) {
2096         if (con_has_urgent_child(child))
2097             return true;
2098     }
2099
2100     return false;
2101 }
2102
2103 /*
2104  * Make all parent containers urgent if con is urgent or clear the urgent flag
2105  * of all parent containers if there are no more urgent children left.
2106  *
2107  */
2108 void con_update_parents_urgency(Con *con) {
2109     Con *parent = con->parent;
2110
2111     /* Urgency hints should not be set on any container higher up in the
2112      * hierarchy than the workspace level. Unfortunately, since the content
2113      * container has type == CT_CON, that’s not easy to verify in the loop
2114      * below, so we need another condition to catch that case: */
2115     if (con->type == CT_WORKSPACE)
2116         return;
2117
2118     bool new_urgency_value = con->urgent;
2119     while (parent && parent->type != CT_WORKSPACE && parent->type != CT_DOCKAREA) {
2120         if (new_urgency_value) {
2121             parent->urgent = true;
2122         } else {
2123             /* We can only reset the urgency when the parent
2124              * has no other urgent children */
2125             if (!con_has_urgent_child(parent))
2126                 parent->urgent = false;
2127         }
2128         parent = parent->parent;
2129     }
2130 }
2131
2132 /*
2133  * Set urgency flag to the container, all the parent containers and the workspace.
2134  *
2135  */
2136 void con_set_urgency(Con *con, bool urgent) {
2137     if (urgent && focused == con) {
2138         DLOG("Ignoring urgency flag for current client\n");
2139         return;
2140     }
2141
2142     const bool old_urgent = con->urgent;
2143
2144     if (con->urgency_timer == NULL) {
2145         con->urgent = urgent;
2146     } else
2147         DLOG("Discarding urgency WM_HINT because timer is running\n");
2148
2149     //CLIENT_LOG(con);
2150     if (con->window) {
2151         if (con->urgent) {
2152             gettimeofday(&con->window->urgent, NULL);
2153         } else {
2154             con->window->urgent.tv_sec = 0;
2155             con->window->urgent.tv_usec = 0;
2156         }
2157     }
2158
2159     con_update_parents_urgency(con);
2160
2161     Con *ws;
2162     /* Set the urgency flag on the workspace, if a workspace could be found
2163      * (for dock clients, that is not the case). */
2164     if ((ws = con_get_workspace(con)) != NULL)
2165         workspace_update_urgent_flag(ws);
2166
2167     if (con->urgent != old_urgent) {
2168         LOG("Urgency flag changed to %d\n", con->urgent);
2169         ipc_send_window_event("urgent", con);
2170     }
2171 }
2172
2173 /*
2174  * Create a string representing the subtree under con.
2175  *
2176  */
2177 char *con_get_tree_representation(Con *con) {
2178     /* this code works as follows:
2179      *  1) create a string with the layout type (D/V/H/T/S) and an opening bracket
2180      *  2) append the tree representation of the children to the string
2181      *  3) add closing bracket
2182      *
2183      * The recursion ends when we hit a leaf, in which case we return the
2184      * class_instance of the contained window.
2185      */
2186
2187     /* end of recursion */
2188     if (con_is_leaf(con)) {
2189         if (!con->window)
2190             return sstrdup("nowin");
2191
2192         if (!con->window->class_instance)
2193             return sstrdup("noinstance");
2194
2195         return sstrdup(con->window->class_instance);
2196     }
2197
2198     char *buf;
2199     /* 1) add the Layout type to buf */
2200     if (con->layout == L_DEFAULT)
2201         buf = sstrdup("D[");
2202     else if (con->layout == L_SPLITV)
2203         buf = sstrdup("V[");
2204     else if (con->layout == L_SPLITH)
2205         buf = sstrdup("H[");
2206     else if (con->layout == L_TABBED)
2207         buf = sstrdup("T[");
2208     else if (con->layout == L_STACKED)
2209         buf = sstrdup("S[");
2210     else {
2211         ELOG("BUG: Code not updated to account for new layout type\n");
2212         assert(false);
2213     }
2214
2215     /* 2) append representation of children */
2216     Con *child;
2217     TAILQ_FOREACH(child, &(con->nodes_head), nodes) {
2218         char *child_txt = con_get_tree_representation(child);
2219
2220         char *tmp_buf;
2221         sasprintf(&tmp_buf, "%s%s%s", buf,
2222                   (TAILQ_FIRST(&(con->nodes_head)) == child ? "" : " "), child_txt);
2223         free(buf);
2224         buf = tmp_buf;
2225         free(child_txt);
2226     }
2227
2228     /* 3) close the brackets */
2229     char *complete_buf;
2230     sasprintf(&complete_buf, "%s]", buf);
2231     free(buf);
2232
2233     return complete_buf;
2234 }
2235
2236 /*
2237  * Returns the container's title considering the current title format.
2238  *
2239  */
2240 i3String *con_parse_title_format(Con *con) {
2241     assert(con->title_format != NULL);
2242
2243     i3Window *win = con->window;
2244
2245     /* We need to ensure that we only escape the window title if pango
2246      * is used by the current font. */
2247     const bool pango_markup = font_is_pango();
2248
2249     char *title;
2250     char *class;
2251     char *instance;
2252     if (win == NULL) {
2253         title = pango_escape_markup(con_get_tree_representation(con));
2254         class = sstrdup("i3-frame");
2255         instance = sstrdup("i3-frame");
2256     } else {
2257         title = pango_escape_markup(sstrdup((win->name == NULL) ? "" : i3string_as_utf8(win->name)));
2258         class = pango_escape_markup(sstrdup((win->class_class == NULL) ? "" : win->class_class));
2259         instance = pango_escape_markup(sstrdup((win->class_instance == NULL) ? "" : win->class_instance));
2260     }
2261
2262     placeholder_t placeholders[] = {
2263         {.name = "%title", .value = title},
2264         {.name = "%class", .value = class},
2265         {.name = "%instance", .value = instance}};
2266     const size_t num = sizeof(placeholders) / sizeof(placeholder_t);
2267
2268     char *formatted_str = format_placeholders(con->title_format, &placeholders[0], num);
2269     i3String *formatted = i3string_from_utf8(formatted_str);
2270     i3string_set_markup(formatted, pango_markup);
2271     FREE(formatted_str);
2272
2273     for (size_t i = 0; i < num; i++) {
2274         FREE(placeholders[i].value);
2275     }
2276
2277     return formatted;
2278 }
2279
2280 /*
2281  * Swaps the two containers.
2282  *
2283  */
2284 bool con_swap(Con *first, Con *second) {
2285     assert(first != NULL);
2286     assert(second != NULL);
2287     DLOG("Swapping containers %p / %p\n", first, second);
2288
2289     if (first->type != CT_CON) {
2290         ELOG("Only regular containers can be swapped, but found con = %p with type = %d.\n", first, first->type);
2291         return false;
2292     }
2293
2294     if (second->type != CT_CON) {
2295         ELOG("Only regular containers can be swapped, but found con = %p with type = %d.\n", second, second->type);
2296         return false;
2297     }
2298
2299     if (first == second) {
2300         DLOG("Swapping container %p with itself, nothing to do.\n", first);
2301         return false;
2302     }
2303
2304     if (con_has_parent(first, second) || con_has_parent(second, first)) {
2305         ELOG("Cannot swap containers %p and %p because they are in a parent-child relationship.\n", first, second);
2306         return false;
2307     }
2308
2309     Con *ws1 = con_get_workspace(first);
2310     Con *ws2 = con_get_workspace(second);
2311     Con *restore_focus = NULL;
2312     if (ws1 == ws2 && ws1 == con_get_workspace(focused)) {
2313         /* Preserve focus in the current workspace. */
2314         restore_focus = focused;
2315     } else if (first == focused || con_has_parent(focused, first)) {
2316         restore_focus = second;
2317     } else if (second == focused || con_has_parent(focused, second)) {
2318         restore_focus = first;
2319     }
2320
2321 #define SWAP_CONS_IN_TREE(headname, field)                            \
2322     do {                                                              \
2323         struct headname *head1 = &(first->parent->headname);          \
2324         struct headname *head2 = &(second->parent->headname);         \
2325         Con *first_prev = TAILQ_PREV(first, headname, field);         \
2326         Con *second_prev = TAILQ_PREV(second, headname, field);       \
2327         if (second_prev == first) {                                   \
2328             TAILQ_SWAP(first, second, head1, field);                  \
2329         } else if (first_prev == second) {                            \
2330             TAILQ_SWAP(second, first, head1, field);                  \
2331         } else {                                                      \
2332             TAILQ_REMOVE(head1, first, field);                        \
2333             TAILQ_REMOVE(head2, second, field);                       \
2334             if (second_prev == NULL) {                                \
2335                 TAILQ_INSERT_HEAD(head2, first, field);               \
2336             } else {                                                  \
2337                 TAILQ_INSERT_AFTER(head2, second_prev, first, field); \
2338             }                                                         \
2339             if (first_prev == NULL) {                                 \
2340                 TAILQ_INSERT_HEAD(head1, second, field);              \
2341             } else {                                                  \
2342                 TAILQ_INSERT_AFTER(head1, first_prev, second, field); \
2343             }                                                         \
2344         }                                                             \
2345     } while (0)
2346
2347     SWAP_CONS_IN_TREE(nodes_head, nodes);
2348     SWAP_CONS_IN_TREE(focus_head, focused);
2349     SWAP(first->parent, second->parent, Con *);
2350
2351     /* Floating nodes are children of CT_FLOATING_CONs, they are listed in
2352      * nodes_head and focus_head like all other containers. Thus, we don't need
2353      * to do anything special other than swapping the floating status and the
2354      * relevant rects. */
2355     SWAP(first->floating, second->floating, int);
2356     SWAP(first->rect, second->rect, Rect);
2357     SWAP(first->window_rect, second->window_rect, Rect);
2358
2359     /* We need to copy each other's percentages to ensure that the geometry
2360      * doesn't change during the swap. */
2361     SWAP(first->percent, second->percent, double);
2362
2363     if (restore_focus) {
2364         con_focus(restore_focus);
2365     }
2366
2367     /* Update new parents' & workspaces' urgency. */
2368     con_set_urgency(first, first->urgent);
2369     con_set_urgency(second, second->urgent);
2370
2371     /* Exchange fullscreen modes, can't use SWAP because we need to call the
2372      * correct functions. */
2373     fullscreen_mode_t second_fullscreen_mode = second->fullscreen_mode;
2374     if (first->fullscreen_mode == CF_NONE) {
2375         con_disable_fullscreen(second);
2376     } else {
2377         con_enable_fullscreen(second, first->fullscreen_mode);
2378     }
2379     if (second_fullscreen_mode == CF_NONE) {
2380         con_disable_fullscreen(first);
2381     } else {
2382         con_enable_fullscreen(first, second_fullscreen_mode);
2383     }
2384
2385     /* We don't actually need this since percentages-wise we haven't changed
2386      * anything, but we'll better be safe than sorry and just make sure as we'd
2387      * otherwise crash i3. */
2388     con_fix_percent(first->parent);
2389     con_fix_percent(second->parent);
2390
2391     con_force_split_parents_redraw(first);
2392     con_force_split_parents_redraw(second);
2393
2394     return true;
2395 }
2396
2397 /*
2398  * Returns container's rect size depending on its orientation.
2399  * i.e. its width when horizontal, its height when vertical.
2400  *
2401  */
2402 uint32_t con_rect_size_in_orientation(Con *con) {
2403     return (con_orientation(con) == HORIZ ? con->rect.width : con->rect.height);
2404 }