i3
src/tree.c
Go to the documentation of this file.
00001 /*
00002  * vim:ts=4:sw=4:expandtab
00003  */
00004 
00005 #include "all.h"
00006 
00007 struct Con *croot;
00008 struct Con *focused;
00009 
00010 struct all_cons_head all_cons = TAILQ_HEAD_INITIALIZER(all_cons);
00011 
00012 /*
00013  * Loads tree from ~/.i3/_restart.json (used for in-place restarts).
00014  *
00015  */
00016 bool tree_restore(const char *path, xcb_get_geometry_reply_t *geometry) {
00017     char *globbed = resolve_tilde(path);
00018 
00019     if (!path_exists(globbed)) {
00020         LOG("%s does not exist, not restoring tree\n", globbed);
00021         free(globbed);
00022         return false;
00023     }
00024 
00025     /* TODO: refactor the following */
00026     croot = con_new(NULL, NULL);
00027     croot->rect = (Rect){
00028         geometry->x,
00029         geometry->y,
00030         geometry->width,
00031         geometry->height
00032     };
00033     focused = croot;
00034 
00035     tree_append_json(globbed);
00036 
00037     printf("appended tree, using new root\n");
00038     croot = TAILQ_FIRST(&(croot->nodes_head));
00039     printf("new root = %p\n", croot);
00040     Con *out = TAILQ_FIRST(&(croot->nodes_head));
00041     printf("out = %p\n", out);
00042     Con *ws = TAILQ_FIRST(&(out->nodes_head));
00043     printf("ws = %p\n", ws);
00044 
00045     return true;
00046 }
00047 
00048 /*
00049  * Initializes the tree by creating the root node. The CT_OUTPUT Cons below the
00050  * root node are created in randr.c for each Output.
00051  *
00052  */
00053 void tree_init(xcb_get_geometry_reply_t *geometry) {
00054     croot = con_new(NULL, NULL);
00055     FREE(croot->name);
00056     croot->name = "root";
00057     croot->type = CT_ROOT;
00058     croot->rect = (Rect){
00059         geometry->x,
00060         geometry->y,
00061         geometry->width,
00062         geometry->height
00063     };
00064 }
00065 
00066 /*
00067  * Opens an empty container in the current container
00068  *
00069  */
00070 Con *tree_open_con(Con *con, i3Window *window) {
00071     if (con == NULL) {
00072         /* every focusable Con has a parent (outputs have parent root) */
00073         con = focused->parent;
00074         /* If the parent is an output, we are on a workspace. In this case,
00075          * the new container needs to be opened as a leaf of the workspace. */
00076         if (con->parent->type == CT_OUTPUT && con->type != CT_DOCKAREA) {
00077             con = focused;
00078         }
00079 
00080         /* If the currently focused container is a floating container, we
00081          * attach the new container to the currently focused spot in its
00082          * workspace. */
00083         if (con->type == CT_FLOATING_CON) {
00084             con = con_descend_tiling_focused(con->parent);
00085             if (con->type != CT_WORKSPACE)
00086                 con = con->parent;
00087         }
00088         DLOG("con = %p\n", con);
00089     }
00090 
00091     assert(con != NULL);
00092 
00093     /* 3. create the container and attach it to its parent */
00094     Con *new = con_new(con, window);
00095 
00096     /* 4: re-calculate child->percent for each child */
00097     con_fix_percent(con);
00098 
00099     return new;
00100 }
00101 
00102 static bool _is_con_mapped(Con *con) {
00103     Con *child;
00104 
00105     TAILQ_FOREACH(child, &(con->nodes_head), nodes)
00106         if (_is_con_mapped(child))
00107             return true;
00108 
00109     return con->mapped;
00110 }
00111 
00112 /*
00113  * Closes the given container including all children.
00114  * Returns true if the container was killed or false if just WM_DELETE was sent
00115  * and the window is expected to kill itself.
00116  *
00117  */
00118 bool tree_close(Con *con, kill_window_t kill_window, bool dont_kill_parent) {
00119     bool was_mapped = con->mapped;
00120     Con *parent = con->parent;
00121 
00122     if (!was_mapped) {
00123         /* Even if the container itself is not mapped, its children may be
00124          * mapped (for example split containers don't have a mapped window on
00125          * their own but usually contain mapped children). */
00126         was_mapped = _is_con_mapped(con);
00127     }
00128 
00129     /* Get the container which is next focused */
00130     Con *next = con_next_focused(con);
00131     DLOG("next = %p, focused = %p\n", next, focused);
00132 
00133     DLOG("closing %p, kill_window = %d\n", con, kill_window);
00134     Con *child, *nextchild;
00135     bool abort_kill = false;
00136     /* We cannot use TAILQ_FOREACH because the children get deleted
00137      * in their parent’s nodes_head */
00138     for (child = TAILQ_FIRST(&(con->nodes_head)); child; ) {
00139         nextchild = TAILQ_NEXT(child, nodes);
00140         DLOG("killing child=%p\n", child);
00141         if (!tree_close(child, kill_window, true))
00142             abort_kill = true;
00143         child = nextchild;
00144     }
00145 
00146     if (abort_kill) {
00147         DLOG("One of the children could not be killed immediately (WM_DELETE sent), aborting.\n");
00148         return false;
00149     }
00150 
00151     if (con->window != NULL) {
00152         if (kill_window != DONT_KILL_WINDOW) {
00153             x_window_kill(con->window->id, kill_window);
00154             return false;
00155         } else {
00156             xcb_void_cookie_t cookie;
00157             /* un-parent the window */
00158             cookie = xcb_reparent_window(conn, con->window->id, root, 0, 0);
00159 
00160             /* Ignore X11 errors for the ReparentWindow request.
00161              * X11 Errors are returned when the window was already destroyed */
00162             add_ignore_event(cookie.sequence, 0);
00163 
00164             /* We are no longer handling this window, thus set WM_STATE to
00165              * WM_STATE_WITHDRAWN (see ICCCM 4.1.3.1) */
00166             long data[] = { XCB_ICCCM_WM_STATE_WITHDRAWN, XCB_NONE };
00167             cookie = xcb_change_property(conn, XCB_PROP_MODE_REPLACE,
00168                         con->window->id, A_WM_STATE, A_WM_STATE, 32, 2, data);
00169 
00170             /* Ignore X11 errors for the ReparentWindow request.
00171              * X11 Errors are returned when the window was already destroyed */
00172             add_ignore_event(cookie.sequence, 0);
00173         }
00174         FREE(con->window->class_class);
00175         FREE(con->window->class_instance);
00176         FREE(con->window->name_x);
00177         FREE(con->window->name_json);
00178         free(con->window);
00179     }
00180 
00181     /* kill the X11 part of this container */
00182     x_con_kill(con);
00183 
00184     con_detach(con);
00185     if (con->type != CT_FLOATING_CON) {
00186         /* If the container is *not* floating, we might need to re-distribute
00187          * percentage values for the resized containers. */
00188         con_fix_percent(parent);
00189     }
00190 
00191     if (con_is_floating(con)) {
00192         Con *ws = con_get_workspace(con);
00193         DLOG("Container was floating, killing floating container\n");
00194         tree_close(parent, DONT_KILL_WINDOW, false);
00195         DLOG("parent container killed\n");
00196         if (con == focused) {
00197             DLOG("This is the focused container, i need to find another one to focus. I start looking at ws = %p\n", ws);
00198             /* go down the focus stack as far as possible */
00199             next = con_descend_focused(ws);
00200 
00201             dont_kill_parent = true;
00202             DLOG("Alright, focusing %p\n", next);
00203         } else {
00204             next = NULL;
00205         }
00206     }
00207 
00208     free(con->name);
00209     FREE(con->deco_render_params);
00210     TAILQ_REMOVE(&all_cons, con, all_cons);
00211     free(con);
00212 
00213     /* in the case of floating windows, we already focused another container
00214      * when closing the parent, so we can exit now. */
00215     if (!next) {
00216         DLOG("No next container, i will just exit now\n");
00217         return true;
00218     }
00219 
00220     if (was_mapped || con == focused) {
00221         if ((kill_window != DONT_KILL_WINDOW) || !dont_kill_parent || con == focused) {
00222             DLOG("focusing %p / %s\n", next, next->name);
00223             /* TODO: check if the container (or one of its children) was focused */
00224             if (next->type == CT_DOCKAREA) {
00225                 /* Instead of focusing the dockarea, we need to restore focus to the workspace */
00226                 con_focus(con_descend_focused(output_get_content(next->parent)));
00227             } else {
00228                 con_focus(next);
00229             }
00230         }
00231         else {
00232             DLOG("not focusing because we're not killing anybody");
00233         }
00234     } else {
00235         DLOG("not focusing, was not mapped\n");
00236     }
00237 
00238     /* check if the parent container is empty now and close it */
00239     if (!dont_kill_parent)
00240         CALL(parent, on_remove_child);
00241 
00242     return true;
00243 }
00244 
00245 /*
00246  * Closes the current container using tree_close().
00247  *
00248  */
00249 void tree_close_con(kill_window_t kill_window) {
00250     assert(focused != NULL);
00251     if (focused->type == CT_WORKSPACE) {
00252         LOG("Cannot close workspace\n");
00253         return;
00254     }
00255 
00256     /* There *should* be no possibility to focus outputs / root container */
00257     assert(focused->type != CT_OUTPUT);
00258     assert(focused->type != CT_ROOT);
00259 
00260     /* Kill con */
00261     tree_close(focused, kill_window, false);
00262 }
00263 
00264 /*
00265  * Splits (horizontally or vertically) the given container by creating a new
00266  * container which contains the old one and the future ones.
00267  *
00268  */
00269 void tree_split(Con *con, orientation_t orientation) {
00270     /* for a workspace, we just need to change orientation */
00271     if (con->type == CT_WORKSPACE) {
00272         DLOG("Workspace, simply changing orientation to %d\n", orientation);
00273         con->orientation = orientation;
00274         return;
00275     }
00276 
00277     Con *parent = con->parent;
00278     /* if we are in a container whose parent contains only one
00279      * child (its split functionality is unused so far), we just change the
00280      * orientation (more intuitive than splitting again) */
00281     if (con_num_children(parent) == 1) {
00282         parent->orientation = orientation;
00283         DLOG("Just changing orientation of existing container\n");
00284         return;
00285     }
00286 
00287     DLOG("Splitting in orientation %d\n", orientation);
00288 
00289     /* 2: replace it with a new Con */
00290     Con *new = con_new(NULL, NULL);
00291     TAILQ_REPLACE(&(parent->nodes_head), con, new, nodes);
00292     TAILQ_REPLACE(&(parent->focus_head), con, new, focused);
00293     new->parent = parent;
00294     new->orientation = orientation;
00295 
00296     /* 3: swap 'percent' (resize factor) */
00297     new->percent = con->percent;
00298     con->percent = 0.0;
00299 
00300     /* 4: add it as a child to the new Con */
00301     con_attach(con, new, false);
00302 }
00303 
00304 /*
00305  * Moves focus one level up.
00306  *
00307  */
00308 void level_up() {
00309     /* We cannot go up when we are in fullscreen mode at the moment, that would
00310      * be totally not intuitive */
00311     if (focused->fullscreen_mode != CF_NONE) {
00312         LOG("Currently in fullscreen, not going up\n");
00313         return;
00314     }
00315     /* We can focus up to the workspace, but not any higher in the tree */
00316     if ((focused->parent->type != CT_CON &&
00317         focused->parent->type != CT_WORKSPACE) ||
00318         focused->type == CT_WORKSPACE) {
00319         LOG("Cannot go up any further\n");
00320         return;
00321     }
00322     con_focus(focused->parent);
00323 }
00324 
00325 /*
00326  * Moves focus one level down.
00327  *
00328  */
00329 void level_down() {
00330     /* Go down the focus stack of the current node */
00331     Con *next = TAILQ_FIRST(&(focused->focus_head));
00332     if (next == TAILQ_END(&(focused->focus_head))) {
00333         printf("cannot go down\n");
00334         return;
00335     }
00336     con_focus(next);
00337 }
00338 
00339 static void mark_unmapped(Con *con) {
00340     Con *current;
00341 
00342     con->mapped = false;
00343     TAILQ_FOREACH(current, &(con->nodes_head), nodes)
00344         mark_unmapped(current);
00345     if (con->type == CT_WORKSPACE) {
00346         /* We need to call mark_unmapped on floating nodes aswell since we can
00347          * make containers floating. */
00348         TAILQ_FOREACH(current, &(con->floating_head), floating_windows)
00349             mark_unmapped(current);
00350     }
00351 }
00352 
00353 /*
00354  * Renders the tree, that is rendering all outputs using render_con() and
00355  * pushing the changes to X11 using x_push_changes().
00356  *
00357  */
00358 void tree_render() {
00359     if (croot == NULL)
00360         return;
00361 
00362     DLOG("-- BEGIN RENDERING --\n");
00363     /* Reset map state for all nodes in tree */
00364     /* TODO: a nicer method to walk all nodes would be good, maybe? */
00365     mark_unmapped(croot);
00366     croot->mapped = true;
00367 
00368     render_con(croot, false);
00369 
00370     x_push_changes(croot);
00371     DLOG("-- END RENDERING --\n");
00372 }
00373 
00374 /*
00375  * Recursive function to walk the tree until a con can be found to focus.
00376  *
00377  */
00378 static bool _tree_next(Con *con, char way, orientation_t orientation, bool wrap) {
00379     /* Stop recursing at workspaces */
00380     if (con->type == CT_WORKSPACE)
00381         return false;
00382 
00383     if (con->type == CT_FLOATING_CON) {
00384         /* TODO: implement focus for floating windows */
00385         return false;
00386     }
00387 
00388     Con *parent = con->parent;
00389 
00390     /* If the orientation does not match or there is no other con to focus, we
00391      * need to go higher in the hierarchy */
00392     if (con_orientation(parent) != orientation ||
00393         con_num_children(parent) == 1)
00394         return _tree_next(parent, way, orientation, wrap);
00395 
00396     Con *current = TAILQ_FIRST(&(parent->focus_head));
00397     /* TODO: when can the following happen (except for floating windows, which
00398      * are handled above)? */
00399     if (TAILQ_EMPTY(&(parent->nodes_head))) {
00400         DLOG("nothing to focus\n");
00401         return false;
00402     }
00403 
00404     Con *next;
00405     if (way == 'n')
00406         next = TAILQ_NEXT(current, nodes);
00407     else next = TAILQ_PREV(current, nodes_head, nodes);
00408 
00409     if (!next) {
00410         if (!config.force_focus_wrapping) {
00411             /* If there is no next/previous container, we check if we can focus one
00412              * when going higher (without wrapping, though). If so, we are done, if
00413              * not, we wrap */
00414             if (_tree_next(parent, way, orientation, false))
00415                 return true;
00416 
00417             if (!wrap)
00418                 return false;
00419         }
00420 
00421         if (way == 'n')
00422             next = TAILQ_FIRST(&(parent->nodes_head));
00423         else next = TAILQ_LAST(&(parent->nodes_head), nodes_head);
00424     }
00425 
00426     /* 3: focus choice comes in here. at the moment we will go down
00427      * until we find a window */
00428     /* TODO: check for window, atm we only go down as far as possible */
00429     con_focus(con_descend_focused(next));
00430     return true;
00431 }
00432 
00433 /*
00434  * Changes focus in the given way (next/previous) and given orientation
00435  * (horizontal/vertical).
00436  *
00437  */
00438 void tree_next(char way, orientation_t orientation) {
00439     _tree_next(focused, way, orientation, true);
00440 }
00441 
00442 /*
00443  * tree_flatten() removes pairs of redundant split containers, e.g.:
00444  *       [workspace, horizontal]
00445  *   [v-split]           [child3]
00446  *   [h-split]
00447  * [child1] [child2]
00448  * In this example, the v-split and h-split container are redundant.
00449  * Such a situation can be created by moving containers in a direction which is
00450  * not the orientation of their parent container. i3 needs to create a new
00451  * split container then and if you move containers this way multiple times,
00452  * redundant chains of split-containers can be the result.
00453  *
00454  */
00455 void tree_flatten(Con *con) {
00456     Con *current, *child, *parent = con->parent;
00457     DLOG("Checking if I can flatten con = %p / %s\n", con, con->name);
00458 
00459     /* We only consider normal containers without windows */
00460     if (con->type != CT_CON || con->window != NULL)
00461         goto recurse;
00462 
00463     /* Ensure it got only one child */
00464     child = TAILQ_FIRST(&(con->nodes_head));
00465     if (child == NULL || TAILQ_NEXT(child, nodes) != NULL)
00466         goto recurse;
00467 
00468     /* The child must have a different orientation than the con but the same as
00469      * the con’s parent to be redundant */
00470     if (con->orientation == NO_ORIENTATION ||
00471         child->orientation == NO_ORIENTATION ||
00472         con->orientation == child->orientation ||
00473         child->orientation != parent->orientation)
00474         goto recurse;
00475 
00476     DLOG("Alright, I have to flatten this situation now. Stay calm.\n");
00477     /* 1: save focus */
00478     Con *focus_next = TAILQ_FIRST(&(child->focus_head));
00479 
00480     DLOG("detaching...\n");
00481     /* 2: re-attach the children to the parent before con */
00482     while (!TAILQ_EMPTY(&(child->nodes_head))) {
00483         current = TAILQ_FIRST(&(child->nodes_head));
00484         DLOG("detaching current=%p / %s\n", current, current->name);
00485         con_detach(current);
00486         DLOG("re-attaching\n");
00487         /* We don’t use con_attach() here because for a CT_CON, the special
00488          * case handling of con_attach() does not trigger. So all it would do
00489          * is calling TAILQ_INSERT_AFTER, but with the wrong container. So we
00490          * directly use the TAILQ macros. */
00491         current->parent = parent;
00492         TAILQ_INSERT_BEFORE(con, current, nodes);
00493         DLOG("attaching to focus list\n");
00494         TAILQ_INSERT_TAIL(&(parent->focus_head), current, focused);
00495         current->percent = con->percent;
00496     }
00497     DLOG("re-attached all\n");
00498 
00499     /* 3: restore focus, if con was focused */
00500     if (focus_next != NULL &&
00501         TAILQ_FIRST(&(parent->focus_head)) == con) {
00502         DLOG("restoring focus to focus_next=%p\n", focus_next);
00503         TAILQ_REMOVE(&(parent->focus_head), focus_next, focused);
00504         TAILQ_INSERT_HEAD(&(parent->focus_head), focus_next, focused);
00505         DLOG("restored focus.\n");
00506     }
00507 
00508     /* 4: close the redundant cons */
00509     DLOG("closing redundant cons\n");
00510     tree_close(con, DONT_KILL_WINDOW, true);
00511 
00512     /* Well, we got to abort the recursion here because we destroyed the
00513      * container. However, if tree_flatten() is called sufficiently often,
00514      * there can’t be the situation of having two pairs of redundant containers
00515      * at once. Therefore, we can safely abort the recursion on this level
00516      * after flattening. */
00517     return;
00518 
00519 recurse:
00520     /* We cannot use normal foreach here because tree_flatten might close the
00521      * current container. */
00522     current = TAILQ_FIRST(&(con->nodes_head));
00523     while (current != NULL) {
00524         Con *next = TAILQ_NEXT(current, nodes);
00525         tree_flatten(current);
00526         current = next;
00527     }
00528 
00529     current = TAILQ_FIRST(&(con->floating_head));
00530     while (current != NULL) {
00531         Con *next = TAILQ_NEXT(current, floating_windows);
00532         tree_flatten(current);
00533         current = next;
00534     }
00535 }