#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>

#include <xcb/randr.h>
#include <xcb/xcb_ewmh.h>
#include <xcb/xcb_icccm.h>
#include <xcb/xcb_keysyms.h>
#include <X11/Xlib.h>
#include <X11/keysym.h>

// Workspace values which are special for us
const uint32_t ALL_WORKSPACES = 0xffffffff;
const uint32_t NULL_WORKSPACE = 0xfffffffe;

// Glyphs (mouse cursor types)
const uint16_t MOVE_GLYPH = 52;
const uint16_t RESIZE_GLYPH = 120;

// Key modifiers
const uint16_t MOD_META = XCB_MOD_MASK_4;
const uint16_t MOD_SHIFT = XCB_MOD_MASK_SHIFT;

uint32_t
keysym_from_str(const char *s) {
    return (uint32_t) XStringToKeysym(s);
}

// General utility functions
uint32_t
parse_color(const char *s) {
    unsigned int r, g, b;
    if (s == NULL
        || strlen(s) != 7
        || sscanf(s, "#%2x%2x%2x", &r, &g, &b) != 3) {
        // Parse error
        return 0;
    }
    return 0xff000000 | (r << 16) | (g << 8) | (b << 0);
}

uint64_t
make_key_chord(uint16_t mod, xcb_keysym_t keysym) {
    uint64_t chord = mod;
    chord = (chord << 32) | keysym;
    return chord;
}

uint32_t
make_button_chord(uint16_t mod, xcb_button_t button) {
    uint32_t chord = mod;
    chord = (chord << 16) | button;
    return chord;
}

void
parse_key_chord(uint64_t chord, uint16_t *mod, xcb_keysym_t *keysym) {
    *mod = chord >> 32;
    *keysym = chord & 0xffff;
}

void
parse_button_chord(uint32_t chord, uint16_t *mod, xcb_button_t *button) {
    *mod = chord >> 16;
    *button = chord & 0xf;
}

struct Point {
    int16_t x, y;
};

struct Rect {
    int16_t x, y;
    uint16_t width, height;
};

int16_t
rect_center_x(const struct Rect *rect) {
    return rect->x + rect->width / 2;
}

int16_t
rect_center_y(const struct Rect *rect) {
    return rect->y + rect->height / 2;
}

void
rect_center(const struct Rect *rect, struct Point *p) {
    p->x = rect_center_x(rect);
    p->y = rect_center_y(rect);
}

int16_t
max(int16_t a, int16_t b) {
    return a > b ? a : b;
}

int16_t
min(int16_t a, int16_t b) {
    return a < b ? a : b;
}

uint32_t
rect_intersect_area(const struct Rect *r1, const struct Rect *r2) {
    int32_t x1 = max(r1->x, r2->x);
    int32_t y1 = max(r1->y, r2->y);
    int32_t x2 = min(r1->x + r1->width, r2->x + r2->width);
    int32_t y2 = min(r1->y + r1->height, r2->y + r2->height);
    return (x1 > x2 || y1 > y2) ? 0 : (x2 - x1) * (y2 - y1);
}

enum WindowState {
    WS_NORMAL = 0,
    WS_ICONIFIED,
    WS_MAXIMIZED,
    WS_FULLSCREEN,
};

struct Client {
    xcb_window_t id;
    int16_t x, y;
    uint16_t width, height;
    uint16_t min_width, min_height, max_width, max_height;
    uint16_t width_inc, height_inc, base_width, base_height;
    uint32_t workspace;
    bool user_coord;
    enum WindowState state, prev_state;
    bool is_unkillable;
    bool should_ignore_borders;
    bool has_old_size;
    int16_t old_x, old_y;
    uint16_t old_width, old_height;
    struct Monitor *monitor;
    struct Client *prev, *next;
};

struct Client *
client_new(xcb_window_t id) {
    struct Client *client = calloc(1, sizeof(struct Client));
    if (client == NULL) {
        return NULL;
    }

    client->id = id;
    client->width_inc = 1;
    client->height_inc = 1;
    client->workspace = NULL_WORKSPACE;
    /*
     * Supposed to be 0 anyway:
     *
     * client->state = WS_NORMAL;
     * client->prev_state = WS_NORMAL;
     */
    return client;
}

/*
 * Adds a new client to the ring, adjusting the necessary next/prev
 * pointers.
 */
struct Client *
client_ring_add(struct Client *ring, struct Client *client) {
    if (ring == NULL || ring->next == NULL || ring->prev == NULL) {
        ring = client;
        client->next = client;
    }

    client->prev = ring;
    client->next = ring->next;
    ring->next->prev = client;
    ring->next = client;
    return client;
}

/*
 * Removes a client from the ring. We do not manage memory here, so
 * the caller must free the memory of the client struct if that's
 * needed.
 */
struct Client *
client_ring_erase(struct Client *ring, struct Client *client) {
    if (ring == NULL) {
        return NULL;
    }
    if (ring == client && client->next == client) {
        // client_free(ring);
        return NULL;
    }

    client->next->prev = client->prev;
    client->prev->next = client->next;
    if (ring == client) {
        ring = client->next;
        // client_free(client);
    }
    return ring;
}

void
client_store_size(struct Client *client) {
    client->old_x = client->x;
    client->old_y = client->y;
    client->old_width = client->width;
    client->old_height = client->height;
    client->has_old_size = true;
}

void
client_restore_size(struct Client *client) {
    if (!client->has_old_size) {
        return;
    }

    client->x = client->old_x;
    client->y = client->old_y;
    client->width = client->old_width;
    client->height = client->old_height;
}

struct ClientList {
    struct Client *client;
    struct ClientList *next;
};

/*
 * Prepends a new client to list of clients.
 */
struct ClientList *
client_list_add(struct ClientList *list, struct Client *client) {
    struct ClientList *node = calloc(1, sizeof(struct ClientList));
    if (node == NULL) {
        // Cannot alloc node, just abort. If list was NULL, stays so.
        return list;
    }
    node->client = client;
    // Also works when list is NULL
    node->next = list;
    list = node;
    return list;
}

/*
 * `deep' indicates whether we should also free the clients referenced
 * by the list elements.
 */
void
client_list_free(struct ClientList *list, bool deep) {
    struct ClientList *next;
    while (list != NULL) {
        next = list->next;
        if (deep) {
            free(list->client);
        }
        free(list);
        list = next;
    }
}

// xcb_window_t is uint32_t
uint32_t
wid_hash(uint32_t x) {
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = (x >> 16) ^ x;
    return x;
}

uint32_t
wid_unhash(uint32_t x) {
    x = ((x >> 16) ^ x) * 0x119de1f3;
    x = ((x >> 16) ^ x) * 0x119de1f3;
    x = (x >> 16) ^ x;
    return x;
}

struct ClientsMap {
    struct ClientList **table;
    // Please never modify this
    size_t table_size;
    size_t size;
};

struct ClientsMap *
clients_map_new(size_t size) {
    struct ClientsMap *map = calloc(1, sizeof(struct ClientsMap));
    if (!map) {
        return NULL;
    }

    map->table = calloc(size, sizeof(struct ClientList *));
    if (!map->table) {
        free(map);
        return NULL;
    }

    map->table_size = size;
    map->size = 0;
    return map;
}

void
clients_map_add(struct ClientsMap *clients, struct Client *client) {
    uint32_t hash = wid_hash(client->id);
    uint32_t i = hash % clients->table_size;
    // collision if (clients->table[i] != NULL)
    clients->table[i] = client_list_add(clients->table[i], client);
    clients->size++;
}

struct Client *
clients_map_erase(struct ClientsMap *clients, struct Client *client) {
    uint32_t hash = wid_hash(client->id);
    uint32_t i = hash % clients->table_size;
    struct ClientList *prev = NULL;
    for (struct ClientList *list = clients->table[i];
         list != NULL;
         list = list->next) {
        if (list->client == client) {
            if (prev == NULL) {
                // It matched the first, update the starting node of
                // the list
                clients->table[i] = list->next;
            }
            if (prev != NULL) {
                // We are not at the first, make prev skip the node we
                // just found
                prev->next = list->next;
            }
            free(list);
            clients->size--;
            return client;
        }
        prev = list;
    }
    // Not found
    return NULL;
}

struct Client *
clients_map_find(const struct ClientsMap *clients, xcb_window_t id) {
    uint32_t hash = wid_hash(id);
    uint32_t i = hash % clients->table_size;
    for (struct ClientList *list = clients->table[i];
         list != NULL;
         list = list->next) {
        if (list->client->id == id) {
            return list->client;
        }
    }
    // Not found
    return NULL;
}

/*
 * This function frees the memory of clients as well.
 */
void
clients_map_free(struct ClientsMap *clients) {
    for (size_t i = 0; i < clients->table_size; i++) {
      client_list_free(clients->table[i], true);
    }
    free(clients->table);
    free(clients);
}

struct Monitor {
    xcb_randr_output_t id;
    const char *name;
    int16_t x, y;
    uint16_t width, height;
    struct Monitor *prev, *next;
};

/*
 * Add a new monitor to the ring, keeping it circular and adjusting
 * the necessary next/prev pointers.
 */
struct Monitor *
monitor_ring_add(struct Monitor *ring, struct Monitor *monitor) {
    if (ring == NULL || ring->next == NULL || ring->prev == NULL) {
        ring = monitor;
        monitor->next = monitor;
    }

    monitor->prev = ring;
    monitor->next = ring->next;
    ring->next->prev = monitor;
    ring->next = monitor;
    return monitor;
}

/*
 * Same as for clients, we also don't manage memory here, just the
 * structure of the ring. The caller should free the monitor struct if
 * needed.
 */
struct Monitor *
monitor_ring_erase(struct Monitor *ring, struct Monitor *monitor) {
    if (ring == NULL) {
        return NULL;
    }
    if (ring == monitor && monitor->next == monitor) {
        // free(ring);
        return NULL;
    }

    monitor->next->prev = monitor->prev;
    monitor->prev->next = monitor->next;
    if (ring == monitor) {
        ring = monitor->next;
        // free(monitor);
    }
    return ring;
}

void
monitor_rect(const struct Monitor *monitor, struct Rect *rect) {
    rect->x = monitor->x;
    rect->y = monitor->y;
    rect->width = monitor->width;
    rect->height = monitor->height;
}

struct Workspace {
    struct Client *ring;
};

static struct {
    uint16_t inner_border_width, outer_border_width, magnet_border_width;
    int16_t offset_x, offset_y;
    uint16_t offset_width, offset_height;
    uint32_t pointer_motion_interval;
    struct {
        uint32_t focused, unfocused, unkillable, empty, outer;
    } colors;
} cfg;

/*
 * Display server-specific information.
 */
static struct {
    xcb_connection_t *conn;
    xcb_ewmh_connection_t *ewmh;
    bool has_error;
    xcb_atom_t delete_window_atom, change_state_atom;
    xcb_key_symbols_t *keysyms;
    uint16_t num_lock, caps_lock, scroll_lock;
    xcb_font_t cursor_font;
    xcb_cursor_t fleur_cursor, sizing_cursor;
    xcb_screen_t *screen;
    bool has_randr;
    int randr_base, screen_num;
    struct Monitor *monitors;
} dpy;

/*
 * Function pointer type for event handlers that take a generic event
 * and know what to do with it.
 */
typedef void (*generic_event_handler_t)(xcb_generic_event_t *);

static struct {
    uint32_t cur_workspace, num_workspaces;
    bool is_running;
    struct Client *focus;
    struct ClientsMap *clients;
    struct Workspace *workspaces;
    struct xcb_connection_t *conn;
    generic_event_handler_t events[XCB_NO_OPERATION];
} wm;

static xcb_screen_t *get_screen();
static bool request_has_error(xcb_void_cookie_t);
static bool dpy_init();
static void dpy_flush();

static xcb_screen_t *
get_screen() {
    const xcb_setup_t* setup = xcb_get_setup(dpy.conn);
    xcb_screen_iterator_t iter = xcb_setup_roots_iterator(setup);
    for (int i = dpy.screen_num; iter.rem; --i) {
        if (i == 0) {
            return iter.data;
        }
        xcb_screen_next(&iter);
    }
    return NULL;
}

static bool
request_has_error(xcb_void_cookie_t cookie) {
    xcb_generic_error_t *error = xcb_request_check(dpy.conn, cookie);
    if (error) {
        free(error);
        return true;
    }
    return false;
}

struct WindowsQueryReply {
    xcb_window_t *data;
    int length;
};

void
windows_query(xcb_window_t root, struct WindowsQueryReply *reply) {
    xcb_query_tree_cookie_t cookie = xcb_query_tree(dpy.conn, root);
    xcb_query_tree_reply_t *data = xcb_query_tree_reply(dpy.conn, cookie, NULL);
    if (!data) {
        return;
    }
    reply->length = 0;
    int length = xcb_query_tree_children_length(data);
    // Assume length is OK, but reply->length holds the length of
    // clients we are really interested in
    reply->data = calloc(length, sizeof(xcb_window_t));
    xcb_window_t *children = xcb_query_tree_children(data);
    for (int i = 0; i < length; i++) {
        xcb_get_window_attributes_cookie_t attr_cookie = xcb_get_window_attributes(
            dpy.conn,
            children[i]);
        xcb_get_window_attributes_reply_t *attr_reply = xcb_get_window_attributes_reply(
            dpy.conn,
            attr_cookie,
            NULL);
        /*
         * From the 2bwm source:
         * Ignore windows in override redirect mode. This mode means
         * they wouldn't have been reported to us with a
         * XCB_MAP_REQUEST if we had been running, so in the normal
         * case we wouldn't have seen them. Only handle visible
         * windows.
         */
        if (attr_reply
            && !attr_reply->override_redirect
            && attr_reply->map_state == XCB_MAP_STATE_VIEWABLE) {
            reply->data[reply->length++] = children[i];
        }
        free(attr_reply);
    }
}

void
windows_query_reply_free(struct WindowsQueryReply *reply) {
    if (reply->length > 0) {
        free(reply->data);
    }
}

static void
dpy_set_window_state(xcb_window_t window, enum WindowState state) {
    if (state == WS_NORMAL) {
        long data[] = { XCB_ICCCM_WM_STATE_NORMAL, XCB_NONE };
        xcb_change_property(
            dpy.conn,
            XCB_PROP_MODE_REPLACE,
            window,
            dpy.ewmh->_NET_WM_STATE,
            dpy.ewmh->_NET_WM_STATE,
            32,
            2,
            data);
    } else if (state == WS_ICONIFIED) {
        xcb_atom_t data[] = { dpy.ewmh->_NET_WM_STATE_HIDDEN };
        xcb_ewmh_set_wm_state(dpy.ewmh, window, 1, data);
    } else if (state == WS_MAXIMIZED) {
        xcb_atom_t data[] = {
            dpy.ewmh->_NET_WM_STATE_MAXIMIZED_VERT,
            dpy.ewmh->_NET_WM_STATE_MAXIMIZED_HORZ,
        };
        xcb_ewmh_set_wm_state(dpy.ewmh, window, 2, data);
    } else if (state == WS_FULLSCREEN) {
        xcb_atom_t data[] = { dpy.ewmh->_NET_WM_STATE_FULLSCREEN };
        xcb_ewmh_set_wm_state(dpy.ewmh, window, 1, data);
    }
}

static void
dpy_set_focus(xcb_window_t window) {
    xcb_window_t focus_window = window;
    uint8_t revert_to = XCB_INPUT_FOCUS_POINTER_ROOT;
    if (window == XCB_NONE) {
        focus_window = XCB_INPUT_FOCUS_POINTER_ROOT;
        revert_to = XCB_INPUT_FOCUS_NONE;
    } else {
        dpy_set_window_state(window, WS_NORMAL);
    }
    xcb_set_input_focus(dpy.conn, revert_to, focus_window, XCB_CURRENT_TIME);
    xcb_ewmh_set_active_window(dpy.ewmh, dpy.screen_num, window);
}

bool
dpy_has_error() {
    return dpy.has_error || xcb_connection_has_error(dpy.conn) > 0;
}

struct Monitor *
dpy_find_monitor(xcb_randr_output_t id) {
    if (dpy.monitors == NULL) {
        return NULL;
    }

    struct Monitor *monitor = dpy.monitors;
    for (;;) {
        if (monitor->id == id) {
            return monitor;
        }
        monitor = monitor->next;
        if (monitor == dpy.monitors) {
            break;
        }
    }
    return NULL;
}

static bool
dpy_update_output(xcb_randr_output_t output,
                  xcb_timestamp_t timestamp,
                  xcb_randr_get_output_info_reply_t *o_reply) {
    xcb_randr_get_crtc_info_cookie_t c_cookie =
        xcb_randr_get_crtc_info(dpy.conn, o_reply->crtc, timestamp);
    xcb_randr_get_crtc_info_reply_t *c_reply =
        xcb_randr_get_crtc_info_reply(dpy.conn, c_cookie, NULL);
    if (!c_reply) {
        return false;
    }

    bool any_change = false;
    struct Monitor *monitor = dpy_find_monitor(output);
    if (monitor != NULL) {
        // Monitor already known, update info
        if (c_reply->x != monitor->x) {
            monitor->x = c_reply->x;
            any_change = true;
        }
        if (c_reply->y != monitor->y) {
            monitor->y = c_reply->y;
            any_change = true;
        }
        if (c_reply->width != monitor->width) {
            monitor->width = c_reply->width;
            any_change = true;
        }
        if (c_reply->height != monitor->height) {
            monitor->height = c_reply->height;
            any_change = true;
        }
        goto dpy_update_output_end;
    }

    // Check if we have a clone of an existing monitor, since we did
    // not find a monitor with same id
    if (dpy.monitors != NULL) {
        monitor = dpy.monitors;
        for (;;) {
            if (monitor->x == c_reply->x
                && monitor->y == c_reply->y
                && monitor->width == c_reply->width
                && monitor->height == c_reply->height) {
                // Found a clone, can be ignored
                goto dpy_update_output_end;
            }
            monitor = monitor->next;
            if (monitor == dpy.monitors) {
                break;
            }
        }
    }

    // It is a new monitor
    // XXX: should we care about name length?
    // int name_len = min(16, xcb_randr_get_output_info_name_length(output_info_reply.get()));
    const char *name = (const char *) xcb_randr_get_output_info_name(o_reply);
    monitor = calloc(1, sizeof(struct Monitor));
    if (monitor == NULL) {
        goto dpy_update_output_end;
    }
    monitor->id = output;
    monitor->name = name;
    monitor->x = c_reply->x;
    monitor->y = c_reply->y;
    monitor->width = c_reply->width;
    monitor->height = c_reply->height;
    dpy.monitors = monitor_ring_add(dpy.monitors, monitor);
    any_change = true;

dpy_update_output_end:
    free(c_reply);
    return any_change;
}

/*
 * Attempts to update monitor info and returns whether there were any
 * changes.
 */
static bool
dpy_update_outputs() {
    if (!dpy.has_randr) {
        return false;
    }

    xcb_randr_get_screen_resources_current_cookie_t s_cookie =
        xcb_randr_get_screen_resources_current(dpy.conn, dpy.screen->root);
    xcb_randr_get_screen_resources_current_reply_t *s_reply =
        xcb_randr_get_screen_resources_current_reply(dpy.conn, s_cookie, NULL);
    if (!s_reply) {
        return false;
    }

    bool any_change = false;
    xcb_timestamp_t timestamp = s_reply->config_timestamp;
    int length = xcb_randr_get_screen_resources_current_outputs_length(s_reply);
    xcb_randr_output_t *outputs = xcb_randr_get_screen_resources_current_outputs(s_reply);
    for (int i = 0; i < length; i++) {
        xcb_randr_get_output_info_cookie_t o_cookie =
            xcb_randr_get_output_info(dpy.conn, outputs[i], timestamp);
        xcb_randr_get_output_info_reply_t *o_reply =
            xcb_randr_get_output_info_reply(dpy.conn, o_cookie, NULL);
        if (!o_reply) {
            continue;
        }

        if (o_reply->crtc == XCB_NONE) {
            // Output no longer active, delete if we had any info about it
            struct Monitor *monitor = dpy_find_monitor(outputs[i]);
            if (monitor == NULL) {
                continue;
            }

            dpy.monitors = monitor_ring_erase(dpy.monitors, monitor);
            free(monitor);
            any_change = true;
        } else {
            // New monitor or existing one changed its info
            any_change = any_change || dpy_update_output(outputs[i], timestamp, o_reply);
        }

        free(o_reply);
    }
    free(s_reply);
    return any_change;
}

static void
dpy_flush() {
    xcb_flush(dpy.conn);
}

static uint16_t
mod_from_keycode(xcb_keycode_t keycode) {
    uint16_t mod = 0;
    xcb_get_modifier_mapping_cookie_t cookie =
        xcb_get_modifier_mapping(dpy.conn);
    xcb_get_modifier_mapping_reply_t *reply =
        xcb_get_modifier_mapping_reply(dpy.conn, cookie, NULL);
    if (!reply || reply->keycodes_per_modifier == 0) {
        goto mod_from_keycode_end;
    }

    xcb_keycode_t *mod_keycodes = xcb_get_modifier_mapping_keycodes(reply);
    if (!mod_keycodes) {
        goto mod_from_keycode_end;
    }

    int length = xcb_get_modifier_mapping_keycodes_length(reply) / reply->keycodes_per_modifier;
    for (int i = 0; i < length; i++) {
        for (int j = 0; j < reply->keycodes_per_modifier; j++) {
            xcb_keycode_t mod_keycode = mod_keycodes[i * reply->keycodes_per_modifier + j];
            if (mod_keycode != XCB_NO_SYMBOL && mod_keycode == keycode) {
                mod |= 1 << i;
            }
        }
    }

mod_from_keycode_end:
    free(reply);
    return mod;
}

static uint16_t
mod_from_keysym(xcb_keysym_t keysym) {
    uint16_t mod = 0;
    const xcb_setup_t *setup = xcb_get_setup(dpy.conn);
    if (!setup) {
        return mod;
    }

    /*
     * We go through every keycode in the setup, looking for the ones
     * matching our keysym request. Then, we transform those into a
     * mod we can use and return.
     *
     * Also, don't use xcb_keycode_t for kc. It overflows when
     * max_keycode coincides with the maximum value of xcb_keycode_t.
     */
    unsigned int kc;
    for (kc = setup->min_keycode; kc <= setup->max_keycode; kc++) {
        for (unsigned int col = 0; col < 4 /* KEYSYMS_PER_KEYCODE */; col++) {
            xcb_keysym_t ks = xcb_key_symbols_get_keysym(dpy.keysyms, kc, col);
            if (ks == keysym) {
                mod |= mod_from_keycode(kc);
            }
        }
    }
    return mod;
}

static xcb_atom_t
dpy_get_atom(const char *name) {
    xcb_intern_atom_cookie_t cookie = xcb_intern_atom(dpy.conn, 0, strlen(name), name);
    xcb_intern_atom_reply_t *reply = xcb_intern_atom_reply(dpy.conn, cookie, NULL);
    if (!reply) {
        return 0;
    }

    xcb_atom_t atom = reply->atom;
    free(reply);
    return atom;
}

static bool
dpy_init(const char *wm_name) {
    // This is initially NULL on purpose: we always try to dealloc
    // later and it might happen that we dealloc before we even tried
    // to setup the keysym stuff. This way we ensure we know whether
    // keysyms is a valid ptr or not.
    dpy.keysyms = NULL;
    dpy.has_error = false;
    dpy.has_randr = false;
    dpy.randr_base = -1;
    dpy.monitors = NULL;

    dpy.conn = xcb_connect(NULL, &dpy.screen_num);
    if (dpy_has_error()) {
        return false;
    }

    dpy.screen = get_screen();
    if (!dpy.screen) {
        dpy.has_error = true;
        return false;
    }

    dpy.ewmh = calloc(1, sizeof(xcb_ewmh_connection_t));
    if (!dpy.ewmh) {
        dpy.has_error = true;
        return false;
    }

    xcb_intern_atom_cookie_t *ewmh_cookie = xcb_ewmh_init_atoms(
        dpy.conn,
        dpy.ewmh);
    if (xcb_ewmh_init_atoms_replies(dpy.ewmh, ewmh_cookie, NULL) == 0) {
        dpy.has_error = true;
        return false;
    }

    xcb_atom_t net_atoms[] = {
        dpy.ewmh->_NET_SUPPORTED,
        dpy.ewmh->_NET_WM_DESKTOP,
        dpy.ewmh->_NET_NUMBER_OF_DESKTOPS,
        dpy.ewmh->_NET_CURRENT_DESKTOP,
        dpy.ewmh->_NET_ACTIVE_WINDOW,
        dpy.ewmh->_NET_WM_ICON,
        dpy.ewmh->_NET_WM_STATE,
        dpy.ewmh->_NET_WM_NAME,
        dpy.ewmh->_NET_SUPPORTING_WM_CHECK,
        dpy.ewmh->_NET_WM_STATE_HIDDEN,
        dpy.ewmh->_NET_WM_ICON_NAME,
        dpy.ewmh->_NET_WM_WINDOW_TYPE,
        dpy.ewmh->_NET_WM_WINDOW_TYPE_DOCK,
        dpy.ewmh->_NET_WM_WINDOW_TYPE_DESKTOP,
        dpy.ewmh->_NET_WM_WINDOW_TYPE_TOOLBAR,
        dpy.ewmh->_NET_WM_PID,
        dpy.ewmh->_NET_CLIENT_LIST,
        dpy.ewmh->WM_PROTOCOLS,
        dpy.ewmh->_NET_WM_STATE,
        dpy.ewmh->_NET_WM_STATE_DEMANDS_ATTENTION,
        dpy.ewmh->_NET_WM_STATE_FULLSCREEN,
    };
    xcb_ewmh_set_supported(
        dpy.ewmh,
        dpy.screen_num,
        sizeof(net_atoms) / sizeof(net_atoms[0]),
        net_atoms);

    // Setup RandR
    const struct xcb_query_extension_reply_t *reply =
        xcb_get_extension_data(dpy.conn, &xcb_randr_id);
    if (!reply || !reply->present) {
        dpy.has_randr = false;
    } else {
        dpy.has_randr = true;
        dpy_update_outputs();
        dpy.randr_base = reply->first_event;
        xcb_randr_select_input(
            dpy.conn,
            dpy.screen->root,
            XCB_RANDR_NOTIFY_MASK_SCREEN_CHANGE
            | XCB_RANDR_NOTIFY_MASK_OUTPUT_CHANGE
            | XCB_RANDR_NOTIFY_MASK_CRTC_CHANGE
            | XCB_RANDR_NOTIFY_MASK_OUTPUT_PROPERTY);
    }

    // Ask display server for window manager capabilities
    dpy.delete_window_atom = dpy_get_atom("WM_DELETE_WINDOW");
    dpy.change_state_atom = dpy_get_atom("WM_CHANGE_STATE");

    // Setup keys
    xcb_ungrab_key(dpy.conn, XCB_GRAB_ANY, dpy.screen->root, XCB_MOD_MASK_ANY);
    dpy.keysyms = xcb_key_symbols_alloc(dpy.conn);
    if (!dpy.keysyms) {
        dpy.has_error = true;
        return false;
    }
    dpy.num_lock = mod_from_keysym(XK_Num_Lock);
    dpy.caps_lock = mod_from_keysym(XK_Caps_Lock);
    dpy.scroll_lock = mod_from_keysym(XK_Scroll_Lock);

    // Setup cursors
    const char *cursor_font_name = "cursor";
    dpy.cursor_font = xcb_generate_id(dpy.conn);
    xcb_open_font(dpy.conn, dpy.cursor_font, strlen(cursor_font_name), cursor_font_name);
    dpy.fleur_cursor = xcb_generate_id(dpy.conn);
    xcb_create_glyph_cursor(
        dpy.conn,
        dpy.fleur_cursor,
        dpy.cursor_font,
        dpy.cursor_font,
        MOVE_GLYPH,
        MOVE_GLYPH + 1,
        0x3232,
        0x3232,
        0x3232,
        0xeeee,
        0xeeee,
        0xeeec);
    dpy.sizing_cursor = xcb_generate_id(dpy.conn);
    xcb_create_glyph_cursor(
        dpy.conn,
        dpy.sizing_cursor,
        dpy.cursor_font,
        dpy.cursor_font,
        RESIZE_GLYPH,
        RESIZE_GLYPH + 1,
        0x3232,
        0x3232,
        0x3232,
        0xeeee,
        0xeeee,
        0xeeec);

    xcb_event_mask_t event_mask = XCB_EVENT_MASK_SUBSTRUCTURE_REDIRECT
        | XCB_EVENT_MASK_SUBSTRUCTURE_NOTIFY
        | XCB_EVENT_MASK_PROPERTY_CHANGE
        | XCB_EVENT_MASK_BUTTON_PRESS;
    xcb_void_cookie_t cookie = xcb_change_window_attributes_checked(
        dpy.conn,
        dpy.screen->root,
        XCB_CW_EVENT_MASK,
        &event_mask);
    if (request_has_error(cookie)) {
        dpy.has_error = true;
        return false;
    }

    xcb_ewmh_set_wm_name(dpy.ewmh, dpy.screen->root, strlen(wm_name), wm_name);
    xcb_ewmh_set_wm_pid(dpy.ewmh, dpy.screen->root, getpid());
    dpy_flush();
    return !dpy.has_error;
}

static bool
dpy_grab_keycode(uint16_t mod, xcb_keycode_t keycode) {
    xcb_void_cookie_t cookie = xcb_grab_key_checked(
        dpy.conn,
        true,
        dpy.screen->root,
        mod,
        keycode,
        XCB_GRAB_MODE_ASYNC,
        XCB_GRAB_MODE_ASYNC);
    xcb_generic_error_t *error = xcb_request_check(dpy.conn, cookie);
    return !error;
}

static void
dpy_grab_keycode_with_lock_mods(uint16_t mod, xcb_keycode_t keycode) {
    dpy_grab_keycode(mod, keycode);
    if (mod == XCB_MOD_MASK_ANY) {
        return;
    }

    if (dpy.num_lock != 0) {
        dpy_grab_keycode(mod | dpy.num_lock, keycode);
    }
    if (dpy.caps_lock != 0) {
        dpy_grab_keycode(mod | dpy.caps_lock, keycode);
    }
    if (dpy.scroll_lock != 0) {
        dpy_grab_keycode(mod | dpy.scroll_lock, keycode);
    }
    if (dpy.num_lock != 0 && dpy.caps_lock != 0) {
        dpy_grab_keycode(mod | dpy.num_lock | dpy.caps_lock, keycode);
    }
    if (dpy.caps_lock != 0 && dpy.scroll_lock != 0) {
        dpy_grab_keycode(mod | dpy.caps_lock | dpy.scroll_lock, keycode);
    }
    if (dpy.num_lock != 0 && dpy.scroll_lock != 0) {
        dpy_grab_keycode(mod | dpy.num_lock | dpy.scroll_lock, keycode);
    }
    if (dpy.num_lock != 0 && dpy.caps_lock != 0 && dpy.scroll_lock != 0) {
        dpy_grab_keycode(mod | dpy.num_lock | dpy.caps_lock | dpy.scroll_lock, keycode);
    }
}

static void
dpy_grab_key(uint16_t mod, xcb_keysym_t keysym) {
    const xcb_setup_t *setup = xcb_get_setup(dpy.conn);
    if (!setup) {
        return;
    }

    /*
     * We go through every keycode in the setup, looking for the ones
     * matching our keysym request.
     */
    unsigned int kc;
    for (kc = setup->min_keycode; kc <= setup->max_keycode; kc++) {
        for (unsigned int col = 0; col < 4 /* KEYSYMS_PER_KEYCODE */; col++) {
            xcb_keysym_t ks = xcb_key_symbols_get_keysym(dpy.keysyms, kc, col);
            if (ks == keysym) {
                dpy_grab_keycode_with_lock_mods(mod, kc);
            }
        }
    }
}

static uint16_t
dpy_clean_mod(uint16_t mod) {
    return mod & ~(dpy.num_lock | dpy.caps_lock | dpy.scroll_lock);
}

static xcb_keysym_t
dpy_keysym_from_keycode(xcb_keycode_t keycode) {
    return xcb_key_symbols_get_keysym(dpy.keysyms, keycode, 0);
}

static void
dpy_set_workspace(uint32_t workspace) {
    xcb_ewmh_set_current_desktop(dpy.ewmh, dpy.screen_num, workspace);
}

static void
dpy_set_num_workspaces() {
    xcb_ewmh_set_number_of_desktops(dpy.ewmh, dpy.screen_num, wm.num_workspaces);
}

static void
dpy_map_window(xcb_window_t window) {
    xcb_map_window(dpy.conn, window);
}

static void
dpy_unmap_window(xcb_window_t window) {
    xcb_unmap_window(dpy.conn, window);
}

static void
dpy_raise_window(xcb_window_t window) {
    if (window == dpy.screen->root || window == XCB_NONE) {
        return;
    }

    uint32_t mode = XCB_STACK_MODE_ABOVE;
    xcb_configure_window(dpy.conn, window, XCB_CONFIG_WINDOW_STACK_MODE, &mode);
}

void
dpy_set_window_border_width(xcb_window_t window) {
    xcb_configure_window(
        dpy.conn,
        window,
        XCB_CONFIG_WINDOW_BORDER_WIDTH,
        &cfg.inner_border_width);
}

void
dpy_set_window_workspace(xcb_window_t window, uint32_t workspace) {
    xcb_ewmh_set_wm_desktop(dpy.ewmh, window, workspace);
}

uint32_t
dpy_get_window_workspace(xcb_window_t window) {
    xcb_get_property_cookie_t cookie = xcb_ewmh_get_wm_desktop(dpy.ewmh, window);
    uint32_t workspace = NULL_WORKSPACE;
    // We don't check the return of the call below because, if anything goes
    // wrong, we'd just assume o3::NULL_WORKSPACE anyway
    xcb_ewmh_get_wm_desktop_reply(dpy.ewmh, cookie, &workspace, NULL);
    return workspace;
}

void
dpy_update_window_geometry(const struct Client *client) {
    xcb_window_t window = client->id;
    if (dpy.screen->root == window || window == XCB_NONE) {
        return;
    }

    uint32_t data[] = {
        (uint32_t) client->x,
        (uint32_t) client->y,
        (uint32_t) client->width,
        (uint32_t) client->height,
    };
    uint16_t mask = XCB_CONFIG_WINDOW_X
        | XCB_CONFIG_WINDOW_Y
        | XCB_CONFIG_WINDOW_WIDTH
        | XCB_CONFIG_WINDOW_HEIGHT;
    xcb_configure_window(dpy.conn, window, mask, data);
}

void
dpy_update_window_position(const struct Client *client) {
    xcb_window_t window = client->id;
    if (dpy.screen->root == window || window == XCB_NONE) {
        return;
    }

    uint32_t data[] = {
        (uint32_t) client->x,
        (uint32_t) client->y,
    };
    uint16_t mask = XCB_CONFIG_WINDOW_X | XCB_CONFIG_WINDOW_Y;
    xcb_configure_window(dpy.conn, window, mask, data);
}

void
dpy_update_window_size(const struct Client *client) {
    xcb_window_t window = client->id;
    if (dpy.screen->root == window || window == XCB_NONE) {
        return;
    }

    uint32_t data[] = {
        (uint32_t) client->width,
        (uint32_t) client->height,
    };
    uint16_t mask = XCB_CONFIG_WINDOW_WIDTH | XCB_CONFIG_WINDOW_HEIGHT;
    xcb_configure_window(dpy.conn, window, mask, data);
}

#define RECT_INIT(x, y, w, h) { \
        (int16_t) (x), \
        (int16_t) (y), \
        (uint16_t) (w), \
        (uint16_t) (h), \
}

static void
dpy_draw_borders(struct Client *client, bool is_focused) {
    if (client->state != WS_NORMAL || client->should_ignore_borders) {
        return;
    }

    dpy_set_window_border_width(client->id);

    xcb_rectangle_t inner_rect[] = {
        RECT_INIT(
            client->width,
            0,
            cfg.inner_border_width - cfg.outer_border_width,
            client->height + cfg.inner_border_width - cfg.outer_border_width
        ),
        RECT_INIT(
            client->width + cfg.inner_border_width + cfg.outer_border_width,
            0,
            cfg.inner_border_width - cfg.outer_border_width,
            client->height + cfg.inner_border_width - cfg.outer_border_width
        ),
        RECT_INIT(
            0,
            client->height,
            client->width + cfg.inner_border_width - cfg.outer_border_width,
            cfg.inner_border_width - cfg.outer_border_width
        ),
        RECT_INIT(
            0,
            client->height + cfg.inner_border_width + cfg.outer_border_width,
            client->width + cfg.inner_border_width - cfg.outer_border_width,
            cfg.inner_border_width - cfg.outer_border_width
        ),
        RECT_INIT(
            client->width + cfg.inner_border_width + cfg.outer_border_width,
            client->height + cfg.inner_border_width + cfg.outer_border_width,
            cfg.inner_border_width,
            cfg.inner_border_width
        ),
    };
    xcb_rectangle_t outer_rect[] = {
        RECT_INIT(
            client->width + cfg.inner_border_width - cfg.outer_border_width,
            0,
            cfg.outer_border_width,
            client->height + cfg.inner_border_width * 2
        ),
        RECT_INIT(
            client->width + cfg.inner_border_width,
            0,
            cfg.outer_border_width,
            client->height + cfg.inner_border_width * 2
        ),
        RECT_INIT(
            0,
            client->height + cfg.inner_border_width - cfg.outer_border_width,
            client->width + cfg.inner_border_width * 2,
            cfg.outer_border_width
        ),
        RECT_INIT(
            0,
            client->height + cfg.inner_border_width,
            client->width + cfg.inner_border_width * 2,
            cfg.outer_border_width
        ),
        RECT_INIT(
            1,
            1,
            1,
            1
        ),
    };

    xcb_pixmap_t pixmap = xcb_generate_id(dpy.conn);
    xcb_create_pixmap(
        dpy.conn,
        dpy.screen->root_depth,
        pixmap,
        dpy.screen->root,
        client->width + cfg.inner_border_width * 2,
        client->height + cfg.inner_border_width * 2);

    xcb_gcontext_t gc = xcb_generate_id(dpy.conn);
    xcb_create_gc(dpy.conn, gc, pixmap, 0, NULL);

    uint32_t color = client->is_unkillable
                   ? cfg.colors.unkillable : cfg.colors.outer;
    xcb_change_gc(dpy.conn, gc, XCB_GC_FOREGROUND, &color);
    xcb_poly_fill_rectangle(dpy.conn, pixmap, gc, 5, outer_rect);

    color = is_focused ? cfg.colors.focused : cfg.colors.unfocused;
    xcb_change_gc(dpy.conn, gc, XCB_GC_FOREGROUND, &color);
    xcb_poly_fill_rectangle(dpy.conn, pixmap, gc, 5, inner_rect);
    xcb_change_window_attributes(dpy.conn, client->id, XCB_CW_BORDER_PIXMAP, &pixmap);
    xcb_free_gc(dpy.conn, gc);
    xcb_free_pixmap(dpy.conn, pixmap);
}

#undef RECT_INIT

void
dpy_draw_focused_borders(struct Client *client) {
    dpy_draw_borders(client, true);
}

void
dpy_draw_unfocused_borders(struct Client *client) {
    dpy_draw_borders(client, false);
}

xcb_window_t
dpy_window_under_cursor() {
    xcb_query_pointer_cookie_t cookie =
        xcb_query_pointer(dpy.conn, dpy.screen->root);
    xcb_query_pointer_reply_t *reply =
        xcb_query_pointer_reply(dpy.conn, cookie, NULL);
    if (!reply) {
        return XCB_NONE;
    }

    xcb_window_t window = reply->child;
    free(reply);
    return window;
}

void
dpy_center_cursor_client(const struct Client *client) {
    int16_t x = client->width / 2;
    int16_t y = client->height / 2;
    xcb_warp_pointer(dpy.conn, XCB_NONE, client->id, 0, 0, 0, 0, x, y);
}

void
dpy_grab_buttons(struct Client *client) {
}

bool
dpy_fetch_geometry(struct Client *client) {
    xcb_get_geometry_cookie_t cookie = xcb_get_geometry(dpy.conn, client->id);
    xcb_get_geometry_reply_t *reply =
        xcb_get_geometry_reply(dpy.conn, cookie, NULL);
    if (!reply) {
        return false;
    }

    client->x = reply->x;
    client->y = reply->y;
    client->width = reply->width;
    client->height = reply->height;
    free(reply);
    return true;
}

bool
dpy_fetch_hints(struct Client *client) {
    xcb_size_hints_t hints;
    xcb_get_property_cookie_t cookie =
        xcb_icccm_get_wm_normal_hints_unchecked(dpy.conn, client->id);
    uint8_t reply = xcb_icccm_get_wm_normal_hints_reply(dpy.conn, cookie, &hints, NULL);
    if (!reply) {
        return false;
    }

    if (hints.flags & XCB_ICCCM_SIZE_HINT_US_POSITION) {
        client->user_coord = true;
        client->x = hints.x;
        client->y = hints.y;
    }
    if (hints.flags & XCB_ICCCM_SIZE_HINT_P_MIN_SIZE) {
        client->min_width = hints.min_width;
        client->min_height = hints.min_height;
    }
    if (hints.flags & XCB_ICCCM_SIZE_HINT_P_MAX_SIZE) {
        client->max_width = hints.max_width;
        client->max_height = hints.max_height;
    }
    if (hints.flags & XCB_ICCCM_SIZE_HINT_BASE_SIZE) {
        client->base_width = hints.base_width;
        client->base_height = hints.base_height;
    }
    return true;
}

bool
dpy_fetch_cursor_position(struct Point *p) {
    xcb_query_pointer_cookie_t cookie =
        xcb_query_pointer(dpy.conn, dpy.screen->root);
    xcb_query_pointer_reply_t *reply =
        xcb_query_pointer_reply(dpy.conn, cookie, NULL);
    if (!reply) {
        return false;
    }

    p->x = reply->win_x;
    p->y = reply->win_y;
    free(reply);
    return true;
}

static bool
dpy_should_ignore_window(xcb_window_t window) {
    xcb_ewmh_get_atoms_reply_t window_type;
    xcb_get_property_cookie_t cookie =
        xcb_ewmh_get_wm_window_type(dpy.ewmh, window);
    uint8_t reply = xcb_ewmh_get_wm_window_type_reply(
        dpy.ewmh,
        cookie,
        &window_type,
        NULL);
    if (!reply) {
        return false;
    }

    // Figure out from window type if we should ignore it
    bool should_ignore = false;
    for (uint32_t i = 0; i < window_type.atoms_len; i++) {
        xcb_atom_t atom = window_type.atoms[i];
        if (atom == dpy.ewmh->_NET_WM_WINDOW_TYPE_TOOLBAR
            || atom == dpy.ewmh->_NET_WM_WINDOW_TYPE_DESKTOP
            || atom == dpy.ewmh->_NET_WM_WINDOW_TYPE_DOCK) {
            // Ignore those windows
            should_ignore = true;
            break;
        }
    }
    // TODO: test/check if this is necessary only if reply is valid
    xcb_ewmh_get_atoms_reply_wipe(&window_type);
    return should_ignore;
}

struct Client *
dpy_make_client(xcb_window_t window) {
    if (dpy_should_ignore_window(window)) {
        return NULL;
    }

    uint32_t event_mask[] = { XCB_EVENT_MASK_ENTER_WINDOW, XCB_NONE };
    xcb_change_window_attributes(dpy.conn, window, XCB_CW_EVENT_MASK, event_mask);
    xcb_change_window_attributes(dpy.conn, window, XCB_CW_BACK_PIXEL, &cfg.colors.empty);
    xcb_change_save_set(dpy.conn, XCB_SET_MODE_INSERT, window);

    struct Client *client = client_new(window);
    if (client) {
        dpy_fetch_geometry(client);
        // Assume a reasonable max_width/max_height, then fetch hints
        client->max_width = dpy.screen->width_in_pixels;
        client->max_height = dpy.screen->height_in_pixels;
        dpy_fetch_hints(client);
    }
    return client;
}

/*
 * Finds the monitor which contains most of the client's rect.
 */
struct Monitor *
find_monitor(const struct Client *client) {
    if (dpy.monitors == NULL) {
        return NULL;
    }
    if (dpy.monitors->next == dpy.monitors) {
        // We only have one monitor
        return dpy.monitors;
    }

    struct Rect c_rect;
    c_rect.x = client->x;
    c_rect.y = client->y;
    c_rect.width = client->width;
    c_rect.height = client->height;

    uint32_t max_area = 0;
    struct Monitor *iter = dpy.monitors;
    struct Monitor *monitor = iter;
    for (;;) {
        struct Rect mon_rect;
        monitor_rect(iter, &mon_rect);
        uint32_t area = rect_intersect_area(&c_rect, &mon_rect);
        if (area > max_area) {
            max_area = area;
            monitor = iter;
        }
        iter = iter->next;
        if (iter == dpy.monitors) {
            // We reached the first monitor in the ring again
            break;
        }
    }
    return monitor;
}

void
dpy_update_window_list(const struct ClientsMap *clients) {
    xcb_window_t *windows = NULL;
    size_t num_windows = 0;
    if (clients->size != 0) {
        windows = malloc(clients->size * sizeof(xcb_window_t));
        for (size_t i = 0; i < clients->table_size; i++) {
            for (struct ClientList *list = clients->table[i];
                 list != NULL;
                 list = list->next) {
                windows[num_windows++] = list->client->id;
            }
        }
    }

    xcb_ewmh_set_client_list(dpy.ewmh, dpy.screen_num, num_windows, windows);
    free(windows);
}

void
dpy_destroy() {
    if (dpy.ewmh) {
        xcb_ewmh_connection_wipe(dpy.ewmh);
        free(dpy.ewmh);
    }

    if (dpy.keysyms) {
        xcb_key_symbols_free(dpy.keysyms);
    }

    if (!dpy_has_error()) {
        xcb_free_cursor(dpy.conn, dpy.fleur_cursor);
        xcb_free_cursor(dpy.conn, dpy.sizing_cursor);
        xcb_close_font(dpy.conn, dpy.cursor_font);
        xcb_set_input_focus(
            dpy.conn,
            XCB_NONE,
            XCB_INPUT_FOCUS_POINTER_ROOT,
            XCB_CURRENT_TIME);
        dpy_flush();
    }
    xcb_disconnect(dpy.conn);
}

/*
 * Window Manager API.
 */
struct Client *wm_find_client(xcb_window_t id);
void wm_erase_client(xcb_window_t id);
bool wm_update_outputs();
bool wm_has_error();
bool wm_init();
void wm_quit();
void wm_close_client();
void wm_begin_move_client();
void wm_begin_resize_client();
void wm_focus_prev();
void wm_focus_next();
void wm_toggle_maximize();
void wm_toggle_half_left();
void wm_toggle_half_right();
void wm_toggle_half_top();
void wm_toggle_half_bottom();
void wm_toggle_top_left();
void wm_toggle_top_right();
void wm_toggle_bottom_left();
void wm_toggle_bottom_right();
void wm_pack_left();
void wm_pack_right();
void wm_pack_top();
void wm_pack_bottom();
void wm_set_workspace(uint32_t workspace);
void wm_set_focused_client_workspace(uint32_t workspace);
void wm_client_monitor_prev();
void wm_client_monitor_next();

struct Client *
wm_find_client(xcb_window_t id) {
    return clients_map_find(wm.clients, id);
}

void
wm_erase_client(xcb_window_t id) {
    struct Client *client = wm_find_client(id);
    if (client == NULL) {
        return;
    }

    struct Workspace *workspace = &wm.workspaces[client->workspace];
    // Workspace being NULL is a bug!
    workspace->ring = client_ring_erase(workspace->ring, client);
    clients_map_erase(wm.clients, client);
    free(client);
    if (!wm.focus) {
        dpy_set_focus(XCB_NONE);
    }
}

bool
wm_apply_size_hints(struct Client *client) {
    if (client->state != WS_NORMAL) {
        return false;
    }

    bool any_change = false;
    if (client->min_width > 0 && client->width < client->min_width) {
        client->width = client->min_width;
        any_change = true;
    }
    if (client->max_width > 0 && client->width > client->max_width) {
        client->width = client->max_width;
        any_change = true;
    }
    if (client->min_height > 0 && client->height < client->min_height) {
        client->height = client->min_height;
        any_change = true;
    }
    if (client->max_height > 0 && client->height > client->max_height) {
        client->height = client->max_height;
        any_change = true;
    }
    return any_change;
}

void
wm_set_focus(struct Client *client) {
    if (wm.focus != NULL) {
        if (wm.focus == client) {
            return;
        }
        dpy_draw_unfocused_borders(wm.focus);
    }

    wm.focus = client;
    dpy_set_focus(client->id);
    dpy_grab_buttons(client);
    dpy_draw_focused_borders(client);
    dpy_flush();
}

void
wm_set_workspace(uint32_t workspace) {
    struct Client *client;
    if (workspace > wm.num_workspaces) {
        return;
    }

    if (workspace != wm.cur_workspace) {
        // Unmap all clients in current workspace
        struct Workspace *ws_ptr = &wm.workspaces[wm.cur_workspace];
        client = ws_ptr->ring;
        while (client != NULL) {
            if (client->state != WS_ICONIFIED) {
                dpy_unmap_window(client->id);
            }
            client = client->next;

            if (client == ws_ptr->ring) {
                break;
            }
        }

        wm.cur_workspace = workspace;
    }

    // Update current workspace and map all clients at new current workspace
    dpy_set_workspace(wm.cur_workspace);
    struct Workspace *ws_ptr = &wm.workspaces[wm.cur_workspace];
    client = ws_ptr->ring;
    while (client != NULL) {
        if (client->state != WS_ICONIFIED) {
            dpy_map_window(client->id);
        }
        client = client->next;

        if (client == ws_ptr->ring) {
            break;
        }
    }

    xcb_window_t window = dpy_window_under_cursor();
    client = clients_map_find(wm.clients, window);
    if (client == NULL) {
        wm.focus = NULL;
        dpy_set_focus(XCB_NONE);
        dpy_flush();
    } else {
        wm_set_focus(client);
    }
}

void
wm_set_client_workspace(struct Client *client, uint32_t workspace) {
}

void
wm_client_monitor_size(const struct Client *client,
                       bool with_offsets,
                       struct Rect *rect) {
    if (client->monitor == NULL) {
        // No monitor means that the default screen is our monitor
        rect->x = rect->y = 0;
        rect->width = dpy.screen->width_in_pixels;
        rect->height = dpy.screen->height_in_pixels;
    } else {
        rect->x = client->monitor->x;
        rect->y = client->monitor->y;
        rect->width = client->monitor->width;
        rect->height = client->monitor->height;
    }

    if (with_offsets) {
        rect->x += cfg.offset_x;
        rect->y += cfg.offset_y;
        rect->width -= cfg.offset_width;
        rect->height -= cfg.offset_height;
    }
}

void
wm_set_client_state(struct Client *client, enum WindowState state) {
    if (state == client->state) {
        return;
    }

    switch (state) {
    case WS_NORMAL:
        if (client->state == WS_ICONIFIED) {
            dpy_map_window(client->id);
            // TODO: check size restoration
        }
        client_restore_size(client);
        dpy_update_window_geometry(client);
        break;
    case WS_ICONIFIED:
        dpy_unmap_window(client->id);
        break;
    case WS_MAXIMIZED:
        client_store_size(client);
        {
            struct Rect mon_rect;
            wm_client_monitor_size(client, true, &mon_rect);
            client->x = mon_rect.x;
            client->y = mon_rect.y;
            client->width = mon_rect.width;
            client->height = mon_rect.height;
        }
        dpy_update_window_geometry(client);
        break;
    case WS_FULLSCREEN:
        break;
    }
    client->prev_state = client->state;
    client->state = state;
    dpy_set_window_state(client->id, client->state);
}

bool
wm_fit_client(struct Client *client) {
    if (client->state == WS_ICONIFIED) {
        return false;
    }

    struct Rect mon_rect;
    wm_client_monitor_size(client, true, &mon_rect);

    // Check if client *looks* maximized, event though it is not
    if (client->state == WS_NORMAL
        && client->width >= mon_rect.width
        && client->height >= mon_rect.height) {
        wm_set_client_state(client, WS_MAXIMIZED);
        return true;
    }

    bool should_move = false;
    // Check if client is located outside monitor coords
    if (client->x > mon_rect.x + mon_rect.width) {
        client->x = mon_rect.x + mon_rect.width - client->width - cfg.inner_border_width * 2;
        should_move = true;
    }
    if (client->y > mon_rect.y + mon_rect.height) {
        client->y = mon_rect.y + mon_rect.height - client->height - cfg.inner_border_width * 2;
        should_move = true;
    }
    if (client->x < mon_rect.x) {
        client->x = mon_rect.x;
        should_move = true;
    }
    if (client->y < mon_rect.y) {
        client->y = mon_rect.y;
        should_move = true;
    }

    // Check if client is larger than monitor, if so move to upper corner and
    // resize to fill
    bool should_resize = wm_apply_size_hints(client);
    uint16_t border_width = client->should_ignore_borders ? 0 : cfg.inner_border_width;
    if (client->width + border_width * 2 > mon_rect.width) {
        client->x = mon_rect.x;
        client->width = mon_rect.width - border_width * 2;
        should_move = true;
        should_resize = true;
    } else if (client->x + client->width + border_width * 2 > mon_rect.x + mon_rect.width) {
        client->x = mon_rect.x + mon_rect.width - (client->width + border_width * 2);
        should_move = true;
    }
    if (client->height + border_width * 2 > mon_rect.height) {
        client->y = mon_rect.y;
        client->height = mon_rect.height - border_width * 2;
        should_move = true;
        should_resize = true;
    } else if (client->y + client->height + border_width * 2 > mon_rect.y + mon_rect.height) {
        client->y = mon_rect.y + mon_rect.height - (client->height + border_width * 2);
        should_move = true;
    }

    if (should_move && should_resize) {
        dpy_update_window_geometry(client);
    } else if (should_move) {
        dpy_update_window_position(client);
    } else if (should_resize) {
        dpy_update_window_size(client);
    }

    return should_move || should_resize;
}

/*
 * event handlers which take a generic event and know what to cast it into.
 */
static void ev_configure_request(xcb_generic_event_t *);
static void ev_destroy_notify(xcb_generic_event_t *);
static void ev_enter_notify(xcb_generic_event_t *);
static void ev_key_press(xcb_generic_event_t *);
static void ev_map_request(xcb_generic_event_t *);
static void ev_unmap_notify(xcb_generic_event_t *);
static void ev_mapping_notify(xcb_generic_event_t *);
static void ev_configure_notify(xcb_generic_event_t *);
static void ev_circulate_request(xcb_generic_event_t *);
static void ev_button_press(xcb_generic_event_t *);
static void ev_client_message(xcb_generic_event_t *);

static struct Client *
manage_client_maybe_reposition(xcb_window_t window, bool set_position) {
    struct Client *client = dpy_make_client(window);
    if (!client) {
        return NULL;
    }
    // TODO: check if unkillable
    uint32_t workspace = dpy_get_window_workspace(client->id);
    if (workspace == ALL_WORKSPACES) {
        fprintf(stderr, "client was supposed to be sticky;"
                        " mapping to current workspace\n");
        workspace = wm.cur_workspace;
    } else if (workspace == NULL_WORKSPACE || workspace >= wm.num_workspaces) {
        workspace = wm.cur_workspace;
    }
    wm_set_client_workspace(client, workspace);
    if (set_position && !client->user_coord) {
        // No predefined position, map at cursor position if possible
        struct Point p;
        if (!dpy_fetch_cursor_position(&p)) {
            p.x = p.y = 0;
        }
        client->x = p.x - client->width / 2;
        client->y = p.y - client->height / 2;
        dpy_update_window_position(client);
    }
    client->monitor = find_monitor(client);
    wm_fit_client(client);
    clients_map_add(wm.clients, client);
    if (client->state == WS_NORMAL) {
        dpy_draw_unfocused_borders(client);
    }
    return client;
}

static struct Client *
manage_client(xcb_window_t window) {
    return manage_client_maybe_reposition(window, false);
}

bool
wm_init() {
    if (!dpy_init("schewm")) {
        return false;
    }

    wm.is_running = true;
    wm.focus = NULL;
    wm.clients = clients_map_new(128);
    if (wm.clients == NULL) {
        return false;
    }

    wm.cur_workspace = 0;
    wm.num_workspaces = 10;
    wm.workspaces = calloc(wm.num_workspaces, sizeof(struct Workspace));
    if (wm.workspaces == NULL) {
        return false;
    }
    dpy_set_num_workspaces();

    // Look into all existing windows and set them up
    struct WindowsQueryReply reply;
    windows_query(dpy.screen->root, &reply);
    for (int i = 0; i < reply.length; i++) {
        xcb_window_t window = reply.data[i];
        if (!manage_client(window)) {
            /*
             * Could not be managed, just map it on screen because we
             * probably should not own it.
             */
            dpy_map_window(window);
        } else {
            /*
             * Unmap everything we grab initially because they may be
             * mapped currently, but belong to another workspace; this
             * way, we can map again only the correct windows at the
             * wm_set_workspace() call below.
             */
            dpy_unmap_window(window);
        }
    }
    windows_query_reply_free(&reply);

    dpy_update_window_list(wm.clients);
    wm_set_workspace(wm.cur_workspace);
    // grab_keys();
    dpy_grab_key(XCB_MOD_MASK_ANY, XK_q);
    dpy_flush();

    memset(wm.events, 0, sizeof(wm.events));
    wm.events[XCB_CONFIGURE_REQUEST]   = ev_configure_request;
    wm.events[XCB_DESTROY_NOTIFY]      = ev_destroy_notify;
    wm.events[XCB_ENTER_NOTIFY]        = ev_enter_notify;
    wm.events[XCB_KEY_PRESS]           = ev_key_press;
    wm.events[XCB_MAP_REQUEST]         = ev_map_request;
    wm.events[XCB_UNMAP_NOTIFY]        = ev_unmap_notify;
    wm.events[XCB_MAPPING_NOTIFY]      = ev_mapping_notify;
    wm.events[XCB_CONFIGURE_NOTIFY]    = ev_configure_notify;
    wm.events[XCB_CIRCULATE_REQUEST]   = ev_circulate_request;
    wm.events[XCB_BUTTON_PRESS]        = ev_button_press;
    wm.events[XCB_CLIENT_MESSAGE]      = ev_client_message;

    return !dpy.has_error;
}

void
wm_quit() {
    wm.is_running = false;
}

void
wm_destroy() {
    free(wm.workspaces);
    clients_map_free(wm.clients);
    dpy_destroy();
}

static uint8_t
ev_type(const xcb_generic_event_t *ev) {
    return ev->response_type & ~0x80;
}

void
wm_run() {
    while (wm.is_running) {
        xcb_generic_event_t *ev = xcb_wait_for_event(dpy.conn);
        fprintf(stderr, "ev: %u\n", ev_type(ev));
        generic_event_handler_t handler = wm.events[ev_type(ev)];
        if (handler) {
            handler(ev);
        }
        free(ev);
    }
    wm_destroy();
}

static uint16_t mod_key = MOD_META;

void
wm_set_mod_key(uint16_t mod) {
    mod_key = mod;
}

uint16_t
wm_get_mod_key(bool with_shift) {
    if (with_shift) {
        return mod_key | MOD_SHIFT;
    }
    return mod_key;
}

/*
 * NOTE:
 * Don't do the thing below. Create hooks for relevant stuff the user
 * might care about, call them at the appropriate places. Design should be:
 * - Event handlers: the WMs job
 * - Hooks: user customization
 *
 * Current sketch is too complex and we don't need to customize
 * behavior that much anyway.
 */

// XCB_CONFIGURE_REQUEST
typedef void (*configure_request_handler_t)();
static configure_request_handler_t configure_request_handler = NULL;

void
wm_set_configure_request_handler(configure_request_handler_t handler) {
    configure_request_handler = handler;
}

static void
ev_configure_request(xcb_generic_event_t *generic_ev) {
    if (configure_request_handler) {
        xcb_configure_request_event_t *ev = (xcb_configure_request_event_t *) generic_ev;
        configure_request_handler();
    }
}

// XCB_DESTROY_NOTIFY
typedef void (*destroy_notify_handler_t)();
static destroy_notify_handler_t destroy_notify_handler = NULL;

void
wm_set_destroy_notify_handler(destroy_notify_handler_t handler) {
    destroy_notify_handler = handler;
}

static void
ev_destroy_notify(xcb_generic_event_t *generic_ev) {
    if (destroy_notify_handler) {
        xcb_destroy_notify_event_t *ev = (xcb_destroy_notify_event_t *) generic_ev;
        destroy_notify_handler();
    }
}

// XCB_ENTER_NOTIFY
typedef void (*enter_notify_handler_t)();
static enter_notify_handler_t enter_notify_handler = NULL;

void
wm_set_enter_notify_handler(enter_notify_handler_t handler) {
    enter_notify_handler = handler;
}

static void
ev_enter_notify(xcb_generic_event_t *generic_ev) {
    if (enter_notify_handler) {
        xcb_enter_notify_event_t *ev = (xcb_enter_notify_event_t *) generic_ev;
        enter_notify_handler();
    }
}

// XCB_KEY_PRESS
typedef void (*key_press_handler_t)(uint16_t, uint8_t);
static key_press_handler_t key_press_handler = NULL;

void
wm_set_key_press_handler(key_press_handler_t handler) {
    key_press_handler = handler;
}

static void
ev_key_press(xcb_generic_event_t *generic_ev) {
    if (key_press_handler) {
        xcb_key_press_event_t *ev = (xcb_key_press_event_t *) generic_ev;
        key_press_handler(ev->state, ev->detail);
    }
}

// XCB_MAP_REQUEST
typedef void (*map_request_handler_t)();
static map_request_handler_t map_request_handler = NULL;

void
wm_set_map_request_handler(map_request_handler_t handler) {
    map_request_handler = handler;
}

static void
ev_map_request(xcb_generic_event_t *generic_ev) {
    if (map_request_handler) {
        xcb_map_request_event_t *ev = (xcb_map_request_event_t *) generic_ev;
        map_request_handler();
    }
}

// XCB_UNMAP_NOTIFY
typedef void (*unmap_notify_handler_t)();
static unmap_notify_handler_t unmap_notify_handler = NULL;

void
wm_set_unmap_notify_handler(unmap_notify_handler_t handler) {
    unmap_notify_handler = handler;
}

static void
ev_unmap_notify(xcb_generic_event_t *generic_ev) {
    if (unmap_notify_handler) {
        xcb_unmap_notify_event_t *ev = (xcb_unmap_notify_event_t *) generic_ev;
        unmap_notify_handler();
    }
}

// XCB_MAPPING_NOTIFY
typedef void (*mapping_notify_handler_t)();
static mapping_notify_handler_t mapping_notify_handler = NULL;

void
wm_set_mapping_notify_handler(mapping_notify_handler_t handler) {
    mapping_notify_handler = handler;
}

static void
ev_mapping_notify(xcb_generic_event_t *generic_ev) {
    if (mapping_notify_handler) {
        xcb_mapping_notify_event_t *ev = (xcb_mapping_notify_event_t *) generic_ev;
        mapping_notify_handler();
    }
}

// XCB_CONFIGURE_NOTIFY
typedef void (*configure_notify_handler_t)(int16_t, int16_t, uint16_t, uint16_t);
static configure_notify_handler_t configure_notify_handler = NULL;

void
wm_set_configure_notify_handler(configure_notify_handler_t handler) {
    configure_notify_handler = handler;
}

static void
ev_configure_notify(xcb_generic_event_t *generic_ev) {
    if (configure_notify_handler) {
        xcb_configure_notify_event_t *ev = (xcb_configure_notify_event_t *) generic_ev;
        configure_notify_handler(ev->x, ev->y, ev->width, ev->height);
    }
}

// XCB_CIRCULATE_REQUEST
typedef void (*circulate_request_handler_t)();
static circulate_request_handler_t circulate_request_handler = NULL;

void
wm_set_circulate_request_handler(circulate_request_handler_t handler) {
    circulate_request_handler = handler;
}

static void
ev_circulate_request(xcb_generic_event_t *generic_ev) {
    if (circulate_request_handler) {
        xcb_circulate_request_event_t *ev = (xcb_circulate_request_event_t *) generic_ev;
        circulate_request_handler();
    }
}

// XCB_BUTTON_PRESS
typedef void (*button_press_handler_t)();
static button_press_handler_t button_press_handler = NULL;

void
wm_set_button_press_handler(button_press_handler_t handler) {
    button_press_handler = handler;
}

static void
ev_button_press(xcb_generic_event_t *generic_ev) {
    if (button_press_handler) {
        xcb_button_press_event_t *ev = (xcb_button_press_event_t *) generic_ev;
        button_press_handler();
    }
}

// XCB_CLIENT_MESSAGE
typedef void (*client_message_handler_t)();
static client_message_handler_t client_message_handler = NULL;

void
wm_set_client_message_handler(client_message_handler_t handler) {
    client_message_handler = handler;
}

static void
ev_client_message(xcb_generic_event_t *generic_ev) {
    if (client_message_handler) {
        xcb_client_message_event_t *ev = (xcb_client_message_event_t *) generic_ev;
        client_message_handler();
    }
}