hacking-howto: update 'Data structures' for v4

[i3/i3] / docs / hacking-howto

Hacking i3: How To
==================
Michael Stapelberg <michael+i3@stapelberg.de>
July 2011

This document is intended to be the first thing you read before looking and/or
touching i3’s source code. It should contain all important information to help
you understand why things are like they are. If it does not mention something
you find necessary, please do not hesitate to contact me.

== Window Managers

A window manager is not necessarily needed to run X, but it is usually used in
combination with X to facilitate some things. The window manager's job is to
take care of the placement of windows, to provide the user with some mechanisms
to change the position/size of windows and to communicate with clients to a
certain extent (for example handle fullscreen requests of clients such as
MPlayer).

There are no different contexts in which X11 clients run, so a window manager
is just another client, like all other X11 applications. However, it handles
some events which normal clients usually don’t handle.

In the case of i3, the tasks (and order of them) are the following:

. Grab the key bindings (events will be sent upon keypress/keyrelease)
. Iterate through all existing windows (if the window manager is not started as
  the first client of X) and manage them (reparent them, create window
  decorations, etc.)
. When new windows are created, manage them
. Handle the client’s `_WM_STATE` property, but only the `_WM_STATE_FULLSCREEN`
. Handle the client’s `WM_NAME` property
. Handle the client’s size hints to display them proportionally
. Handle the client’s urgency hint
. Handle enter notifications (focus follows mouse)
. Handle button (as in mouse buttons) presses for focus/raise on click
. Handle expose events to re-draw own windows such as decorations
. React to the user’s commands: Change focus, Move windows, Switch workspaces,
  Change the layout mode of a container (default/stacking/tabbed), start a new
  application, restart the window manager

In the following chapters, each of these tasks and their implementation details
will be discussed.

=== Tiling window managers

Traditionally, there are two approaches to managing windows: The most common
one nowadays is floating, which means the user can freely move/resize the
windows. The other approach is called tiling, which means that your window
manager distributes windows to use as much space as possible while not
overlapping each other.

The idea behind tiling is that you should not need to waste your time
moving/resizing windows while you usually want to get some work done. After
all, most users sooner or later tend to lay out their windows in a way which
corresponds to tiling or stacking mode in i3. Therefore, why not let i3 do this
for you? Certainly, it’s faster than you could ever do it.

The problem with most tiling window managers is that they are too unflexible.
In my opinion, a window manager is just another tool, and similar to vim which
can edit all kinds of text files (like source code, HTML, …) and is not limited
to a specific file type, a window manager should not limit itself to a certain
layout (like dwm, awesome, …) but provide mechanisms for you to easily create
the layout you need at the moment.

=== The layout table

*********************************************************************************
This section has not been updated for v4.0 yet, sorry! We wanted to release on
time, but we will update this soon. Please talk to us on IRC if you need to
know stuff *NOW* :).
*********************************************************************************

/////////////////////////////////////////////////////////////////////////////////
To accomplish flexible layouts, we decided to simply use a table. The table
grows and shrinks as you need it. Each cell holds a container which then holds
windows (see picture below). You can use different layouts for each container
(default layout and stacking layout).

So, when you open a terminal and immediately open another one, they reside in
the same container, in default layout. The layout table has exactly one column,
one row and therefore one cell. When you move one of the terminals to the
right, the table needs to grow. It will be expanded to two columns and one row.
This enables you to have different layouts for each container. The table then
looks like this:

[width="15%",cols="^,^"]
|========
| T1 | T2
|========

When moving terminal 2 to the bottom, the table will be expanded again.

[width="15%",cols="^,^"]
|========
| T1 |
|    | T2
|========

You can really think of the layout table like a traditional HTML table, if
you’ve ever designed one. Especially col- and rowspan work similarly. Below,
you see an example of colspan=2 for the first container (which has T1 as
window).

[width="15%",cols="^asciidoc"]
|========
| T1
|
[cols="^,^",frame="none"]
!========
! T2 ! T3
!========
|========

Furthermore, you can freely resize table cells.
/////////////////////////////////////////////////////////////////////////////////

== Files

include/atoms.xmacro::
A file containing all X11 atoms which i3 uses. This file will be included
various times (for defining, requesting and receiving the atoms), each time
with a different definition of xmacro().

include/data.h::
Contains data definitions used by nearly all files. You really need to read
this first.

include/*.h::
Contains forward definitions for all public functions, as well as
doxygen-compatible comments (so if you want to get a bit more of the big
picture, either browse all header files or use doxygen if you prefer that).

src/cfgparse.l::
Contains the lexer for i3’s configuration file, written for +flex(1)+.

src/cfgparse.y::
Contains the parser for i3’s configuration file, written for +bison(1)+.

src/click.c::
Contains all functions which handle mouse button clicks (right mouse button
clicks initiate resizing and thus are relatively complex).

src/cmdparse.l::
Contains the lexer for i3 commands, written for +flex(1)+.

src/cmdparse.y::
Contains the parser for i3 commands, written for +bison(1)+.

src/con.c::
Contains all functions which deal with containers directly (creating
containers, searching containers, getting specific properties from containers,
…).

src/config.c::
Contains all functions handling the configuration file (calling the parser
(src/cfgparse.y) with the correct path, switching key bindings mode).

src/debug.c::
Contains debugging functions to print unhandled X events.

src/ewmh.c::
iFunctions to get/set certain EWMH properties easily.

src/floating.c::
Contains functions for floating mode (mostly resizing/dragging).

src/handlers.c::
Contains all handlers for all kinds of X events (new window title, new hints,
unmapping, key presses, button presses, …).

src/ipc.c::
Contains code for the IPC interface.

src/load_layout.c::
Contains code for loading layouts from JSON files.

src/log.c::
Handles the setting of loglevels, contains the logging functions.

src/main.c::
Initializes the window manager.

src/manage.c::
Looks at existing or new windows and decides whether to manage them. If so, it
reparents the window and inserts it into our data structures.

src/match.c::
A "match" is a data structure which acts like a mask or expression to match
certain windows or not. For example, when using commands, you can specify a
command like this: [title="*Firefox*"] kill. The title member of the match
data structure will then be filled and i3 will check each window using
match_matches_window() to find the windows affected by this command.

src/move.c::
Contains code to move a container in a specific direction.

src/output.c::
Functions to handle CT_OUTPUT cons.

src/randr.c::
The RandR API is used to get (and re-query) the configured outputs (monitors,
…).

src/render.c::
Renders the tree data structure by assigning coordinates to every node. These
values will later be pushed to X11 in +src/x.c+.

src/resize.c::
Contains the functions to resize containers.

src/sighandler.c::
Handles +SIGSEGV+, +SIGABRT+ and +SIGFPE+ by showing a dialog that i3 crashed.
You can chose to let it dump core, to restart it in-place or to restart it
in-place but forget about the layout.

src/tree.c::
Contains functions which open or close containers in the tree, change focus or
cleanup ("flatten") the tree. See also +src/move.c+ for another similar
function, which was moved into its own file because it is so long.

src/util.c::
Contains useful functions which are not really dependant on anything.

src/window.c::
Handlers to update X11 window properties like +WM_CLASS+, +_NET_WM_NAME+,
+CLIENT_LEADER+, etc.

src/workspace.c::
Contains all functions related to workspaces (displaying, hiding, renaming…)

src/x.c::
Transfers our in-memory tree (see +src/render.c+) to X11.

src/xcb.c::
Contains wrappers to use xcb more easily.

src/xcursor.c::
XCursor functions (for cursor themes).

src/xinerama.c::
Legacy support for Xinerama. See +src/randr.c+ for the preferred API.

== Data structures


See include/data.h for documented data structures. The most important ones are
explained right here.

/////////////////////////////////////////////////////////////////////////////////
// TODO: update image

image:bigpicture.png[The Big Picture]

/////////////////////////////////////////////////////////////////////////////////

So, the hierarchy is:

. *X11 root window*, the root container
. *Output container* (LVDS1 in this example)
. *Content container* (there are also containers for dock windows)
. *Workspaces* (Workspace 1 in this example, with horizontal orientation)
. *Split container* (vertically split)
. *X11 window containers*

The data type is +Con+, in all cases.

=== X11 root window

The X11 root window is a single window per X11 display (a display is identified
by +:0+ or +:1+ etc.). The root window is what you draw your background image
on. It spans all the available outputs, e.g. +VGA1+ is a specific part of the
root window and +LVDS1+ is a specific part of the root window.

=== Output container

Every active output obtained through RandR is represented by one output
container. Outputs are considered active when a mode is configured (meaning
something is actually displayed on the output) and the output is not a clone.

For example, if your notebook has a screen resolution of 1280x800 px and you
connect a video projector with a resolution of 1024x768 px, set it up in clone
mode (+xrandr \--output VGA1 \--mode 1024x768 \--same-as LVDS1+), i3 will
reduce the resolution to the lowest common resolution and disable one of the
cloned outputs afterwards.

However, if you configure it using +xrandr \--output VGA1 \--mode 1024x768
\--right-of LVDS1+, i3 will set both outputs active. For each output, a new
workspace will be assigned. New workspaces are created on the output you are
currently on.

=== Content container

Each output has multiple children. Two of them are dock containers which hold
dock clients. The other one is the content container, which holds the actual
content (workspaces) of this output.

=== Workspace

A workspace is identified by its name. Basically, you could think of
workspaces as different desks in your office, if you like the desktop
methaphor. They just contain different sets of windows and are completely
separate of each other. Other window managers also call this ``Virtual
desktops''.

=== Split container

A split container is a container which holds an arbitrary amount of split
containers or X11 window containers. It has an orientation (horizontal or
vertical) and a layout.

Split containers (and X11 window containers, which are a subtype of split
containers) can have different border styles.

=== X11 window container

An X11 window container holds exactly one X11 window. These are the leaf nodes
of the layout tree, they cannot have any children.

== List/queue macros

i3 makes heavy use of the list macros defined in BSD operating systems. To
ensure that the operating system on which i3 is compiled has all the expected
features, i3 comes with `include/queue.h`. On BSD systems, you can use man
`queue(3)`. On Linux, you have to use google (or read the source).

The lists used are +SLIST+ (single linked lists), +CIRCLEQ+ (circular
queues) and +TAILQ+ (tail queues). Usually, only forward traversal is necessary,
so an `SLIST` works fine. If inserting elements at arbitrary positions or at
the end of a list is necessary, a +TAILQ+ is used instead. However, for the
windows inside a container, a +CIRCLEQ+ is necessary to go from the currently
selected window to the window above/below.

== Naming conventions

There is a row of standard variables used in many events. The following names
should be chosen for those:

 * ``conn'' is the xcb_connection_t
 * ``event'' is the event of the particular type
 * ``con'' names a container
 * ``current'' is a loop variable when using +TAILQ_FOREACH+ etc.

== Startup (src/mainx.c, main())

 * Establish the xcb connection
 * Check for XKB extension on the separate X connection, load Xcursor
 * Check for RandR screens (with a fall-back to Xinerama)
 * Grab the keycodes for which bindings exist
 * Manage all existing windows
 * Enter the event loop

== Keybindings

=== Grabbing the bindings

Grabbing the bindings is quite straight-forward. You pass X your combination of
modifiers and the keycode you want to grab and whether you want to grab them
actively or passively. Most bindings (everything except for bindings using
Mode_switch) are grabbed passively, that is, just the window manager gets the
event and cannot replay it.

We need to grab bindings that use Mode_switch actively because of a bug in X.
When the window manager receives the keypress/keyrelease event for an actively
grabbed keycode, it has to decide what to do with this event: It can either
replay it so that other applications get it or it can prevent other
applications from receiving it.

So, why do we need to grab keycodes actively? Because X does not set the
state-property of keypress/keyrelease events properly. The Mode_switch bit is
not set and we need to get it using XkbGetState. This means we cannot pass X
our combination of modifiers containing Mode_switch when grabbing the key and
therefore need to grab the keycode itself without any modifiers. This means,
if you bind Mode_switch + keycode 38 ("a"), i3 will grab keycode 38 ("a") and
check on each press of "a" if the Mode_switch bit is set using XKB. If yes, it
will handle the event, if not, it will replay the event.

=== Handling a keypress

As mentioned in "Grabbing the bindings", upon a keypress event, i3 first gets
the correct state.

Then, it looks through all bindings and gets the one which matches the received
event.

The bound command is parsed by the cmdparse lexer/parser, see +parse_cmd+ in
+src/cmdparse.y+.

== Manage windows (src/main.c, manage_window() and reparent_window())

`manage_window()` does some checks to decide whether the window should be
managed at all:

 * Windows have to be mapped, that is, visible on screen
 * The override_redirect must not be set. Windows with override_redirect shall
   not be managed by a window manager

Afterwards, i3 gets the intial geometry and reparents the window (see
`reparent_window()`) if it wasn’t already managed.

Reparenting means that for each window which is reparented, a new window,
slightly larger than the original one, is created. The original window is then
reparented to the bigger one (called "frame").

After reparenting, the window type (`_NET_WM_WINDOW_TYPE`) is checked to see
whether this window is a dock (`_NET_WM_WINDOW_TYPE_DOCK`), like dzen2 for
example. Docks are handled differently, they don’t have decorations and are not
assigned to a specific container. Instead, they are positioned at the bottom
of the screen. To get the height which needs to be reserved for the window,
the `_NET_WM_STRUT_PARTIAL` property is used.

Furthermore, the list of assignments (to other workspaces, which may be on
other screens) is checked. If the window matches one of the user’s criteria,
it may either be put in floating mode or moved to a different workspace. If the
target workspace is not visible, the window will not be mapped.

== What happens when an application is started?

i3 does not care for applications. All it notices is when new windows are
mapped (see `src/handlers.c`, `handle_map_request()`). The window is then
reparented (see section "Manage windows").

After reparenting the window, `render_tree()` is called which renders the
internal layout table. The new window has been placed in the currently focused
container and therefore the new window and the old windows (if any) need to be
moved/resized so that the currently active layout (default/stacking/tabbed mode)
is rendered correctly. To move/resize windows, a window is ``configured'' in
X11-speak.

Some applications, such as MPlayer obviously assume the window manager is
stupid and try to configure their windows by themselves. This generates an
event called configurerequest. i3 handles these events and tells the window the
size it had before the configurerequest (with the exception of not yet mapped
windows, which get configured like they want to, and floating windows, which
can reconfigure themselves).

== _NET_WM_STATE

Only the _NET_WM_STATE_FULLSCREEN atom is handled. It calls
``toggle_fullscreen()'' for the specific client which just configures the
client to use the whole screen on which it currently is. Also, it is set as
fullscreen_client for the i3Screen.

== WM_NAME

When the WM_NAME property of a window changes, its decoration (containing the
title) is re-rendered. Note that WM_NAME is in COMPOUND_TEXT encoding which is
totally uncommon and cumbersome. Therefore, the _NET_WM_NAME atom will be used
if present.

== _NET_WM_NAME

Like WM_NAME, this atom contains the title of a window. However, _NET_WM_NAME
is encoded in UTF-8. i3 will recode it to UCS-2 in order to be able to pass it
to X. Using an appropriate font (ISO-10646), you can see most special
characters (every special character contained in your font).

== Size hints

Size hints specify the minimum/maximum size for a given window as well as its
aspect ratio.  This is important for clients like mplayer, who only set the
aspect ratio and resize their window to be as small as possible (but only with
some video outputs, for example in Xv, while when using x11, mplayer does the
necessary centering for itself).

So, when an aspect ratio was specified, i3 adjusts the height of the window
until the size maintains the correct aspect ratio. For the code to do this, see
src/layout.c, function resize_client().

== Rendering (src/layout.c, render_layout() and render_container())

*********************************************************************************
This section has not been updated for v4.0 yet, sorry! We wanted to release on
time, but we will update this soon. Please talk to us on IRC if you need to
know stuff *NOW* :).
*********************************************************************************

/////////////////////////////////////////////////////////////////////////////////


There are several entry points to rendering: `render_layout()`,
`render_workspace()` and `render_container()`. The former one calls
`render_workspace()` for every screen, which in turn will call
`render_container()` for every container inside its layout table. Therefore, if
you need to render only a single container, for example because a window was
removed, added or changed its title, you should directly call
render_container().

Rendering consists of two steps: In the first one, in `render_workspace()`, each
container gets its position (screen offset + offset in the table) and size
(container's width times colspan/rowspan). Then, `render_container()` is called,
which takes different approaches, depending on the mode the container is in:

=== Common parts

On the frame (the window which was created around the client’s window for the
decorations), a black rectangle is drawn as a background for windows like
MPlayer, which do not completely fit into the frame.

=== Default mode

Each clients gets the container’s width and an equal amount of height.

=== Stack mode

In stack mode, a window containing the decorations of all windows inside the
container is placed at the top. The currently focused window is then given the
whole remaining space.

=== Tabbed mode

Tabbed mode is like stack mode, except that the window decorations are drawn
in one single line at the top of the container.

=== Window decorations

The window decorations consist of a rectangle in the appropriate color (depends
on whether this window is the currently focused one, the last focused one in a
not focused container or not focused at all) forming the background.
Afterwards, two lighter lines are drawn and the last step is drawing the
window’s title (see WM_NAME) onto it.

=== Fullscreen windows

For fullscreen windows, the `rect` (x, y, width, height) is not changed to
allow the client to easily go back to its previous position. Instead,
fullscreen windows are skipped when rendering.

=== Resizing containers

By clicking and dragging the border of a container, you can resize the whole
column (respectively row) which this container is in. This is necessary to keep
the table layout working and consistent.

The resizing works similarly to the resizing of floating windows or movement of
floating windows:

* A new, invisible window with the size of the root window is created
  (+grabwin+)
* Another window, 2px width and as high as your screen (or vice versa for
  horizontal resizing) is created. Its background color is the border color and
  it is only there to inform the user how big the container will be (it
  creates the impression of dragging the border out of the container).
* The +drag_pointer+ function of +src/floating.c+ is called to grab the pointer
  and enter its own event loop which will pass all events (expose events) but
  motion notify events. This function then calls the specified callback
  (+resize_callback+) which does some boundary checking and moves the helper
  window. As soon as the mouse button is released, this loop will be
  terminated.
* The new width_factor for each involved column (respectively row) will be
  calculated.

/////////////////////////////////////////////////////////////////////////////////

== User commands / commandmode (src/cmdparse.{l,y})

*********************************************************************************
This section has not been updated for v4.0 yet, sorry! We wanted to release on
time, but we will update this soon. Please talk to us on IRC if you need to
know stuff *NOW* :).
*********************************************************************************

/////////////////////////////////////////////////////////////////////////////////


Like in vim, you can control i3 using commands. They are intended to be a
powerful alternative to lots of shortcuts, because they can be combined. There
are a few special commands, which are the following:

exec <command>::
Starts the given command by passing it to `/bin/sh`.

restart::
Restarts i3 by executing `argv[0]` (the path with which you started i3) without
forking.

w::
"With". This is used to select a bunch of windows. Currently, only selecting
the whole container in which the window is in, is supported by specifying "w".

f, s, d::
Toggle fullscreen, stacking, default mode for the current window/container.

The other commands are to be combined with a direction. The directions are h,
j, k and l, like in vim (h = left, j = down, k = up, l = right). When you just
specify the direction keys, i3 will move the focus in that direction. You can
provide "m" or "s" before the direction to move a window respectively or snap.

/////////////////////////////////////////////////////////////////////////////////

== Moving containers

The movement code is pretty delicate. You need to consider all cases before
making any changes or before being able to fully understand how it works.

=== Case 1: Moving inside the same container

The reference layout for this case is a single workspace in horizontal
orientation with two containers on it. Focus is on the left container (1).


[width="15%",cols="^,^"]
|========
| 1 | 2
|========

When moving the left window to the right (command +move right+), tree_move will
look for a container with horizontal orientation and finds the parent of the
left container, that is, the workspace. Afterwards, it runs the code branch
commented with "the easy case": it calls TAILQ_NEXT to get the container right
of the current one and swaps both containers.

=== Case 2: Move a container into a split container

The reference layout for this case is a horizontal workspace with two
containers. The right container is a v-split with two containers. Focus is on
the left container (1).

[width="15%",cols="^,^"]
|========
1.2+^.^| 1 | 2
| 3
|========

When moving to the right (command +move right+), i3 will work like in case 1
("the easy case"). However, as the right container is not a leaf container, but
a v-split, the left container (1) will be inserted at the right position (below
2, assuming that 2 is focused inside the v-split) by calling +insert_con_into+.

+insert_con_into+ detaches the container from its parent and inserts it
before/after the given target container. Afterwards, the on_remove_child
callback is called on the old parent container which will then be closed, if
empty.

Afterwards, +con_focus+ will be called to fix the focus stack and the tree will
be flattened.

=== Case 3: Moving to non-existant top/bottom

Like in case 1, the reference layout for this case is a single workspace in
horizontal orientation with two containers on it. Focus is on the left
container:

[width="15%",cols="^,^"]
|========
| 1 | 2
|========

This time however, the command is +move up+ or +move down+. tree_move will look
for a container with vertical orientation. As it will not find any,
+same_orientation+ is NULL and therefore i3 will perform a forced orientation
change on the workspace by creating a new h-split container, moving the
workspace contents into it and then changing the workspace orientation to
vertical. Now it will again search for parent containers with vertical
orientation and it will find the workspace.

This time, the easy case code path will not be run as we are not moving inside
the same container. Instead, +insert_con_into+ will be called with the focused
container and the container above/below the current one (on the level of
+same_orientation+).

Now, +con_focus+ will be called to fix the focus stack and the tree will be
flattened.

=== Case 4: Moving to existant top/bottom

The reference layout for this case is a vertical workspace with two containers.
The bottom one is a h-split containing two containers (1 and 2). Focus is on
the bottom left container (1).

[width="15%",cols="^,^"]
|========
2+| 3
| 1 | 2
|========

This case is very much like case 3, only this time the forced workspace
orientation change does not need to be performed because the workspace already
is in vertical orientation.

=== Case 5: Moving in one-child h-split

The reference layout for this case is a horizontal workspace with two
containers having a v-split on the left side with a one-child h-split on the
bottom. Focus is on the bottom left container (2(h)):

[width="15%",cols="^,^"]
|========
| 1 1.2+^.^| 3
| 2(h)
|========

In this case, +same_orientation+ will be set to the h-split container around
the focused container. However, when trying the easy case, the next/previous
container +swap+ will be NULL. Therefore, i3 will search again for a
+same_orientation+ container, this time starting from the parent of the h-split
container.

After determining a new +same_orientation+ container (if it is NULL, the
orientation will be force-changed), this case is equivalent to case 2 or case
4.


=== Case 6: Floating containers

The reference layout for this case is a horizontal workspace with two
containers plus one floating h-split container. Focus is on the floating
container.

TODO: nice illustration. table not possible?

When moving up/down, the container needs to leave the floating container and it
needs to be placed on the workspace (at workspace level). This is accomplished
by calling the function +attach_to_workspace+.

== Click handling

Without much ado, here is the list of cases which need to be considered:

* click to focus (tiling + floating) and raise (floating)
* click to focus/raise when in stacked/tabbed mode
* floating_modifier + left mouse button to drag a floating con
* floating_modifier + right mouse button to resize a floating con
* click on decoration in a floating con to either initiate a resize (if there
  is more than one child in the floating con) or to drag the
  floating con (if it’s the one at the top).
* click on border in a floating con to resize the floating con
* floating_modifier + right mouse button to resize a tiling con
* click on border/decoration to resize a tiling con

== Gotchas

* Forgetting to call `xcb_flush(conn);` after sending a request. This usually
  leads to code which looks like it works fine but which does not work under
  certain conditions.

== Using git / sending patches

For a short introduction into using git, see
http://www.spheredev.org/wiki/Git_for_the_lazy or, for more documentation, see
http://git-scm.com/documentation

When you want to send a patch because you fixed a bug or implemented a cool
feature (please talk to us before working on features to see whether they are
maybe already implemented, not possible for some some reason, or don’t fit
into the concept), please use git to create a patchfile.

First of all, update your working copy to the latest version of the master
branch:

--------
git pull
--------

Afterwards, make the necessary changes for your bugfix/feature. Then, review
the changes using +git diff+ (you might want to enable colors in the diff using
+git config diff.color auto+).  When you are definitely done, use +git commit
-a+ to commit all changes you’ve made.

Then, use the following command to generate a patchfile which we can directly
apply to the branch, preserving your commit message and name:

-----------------------
git format-patch origin
-----------------------

Just send us the generated file via email.