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