#include <assert.h>
#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_ALT = XCB_MOD_MASK_1;
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;
    client->has_old_size = false;
}

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;
    }
}

/*
 * The following hash functions come from [1].
 *
 * Apparently supposed to be overall decent, no independent tests were
 * made here. We have 32-bit and 64-bit versions, as we need hash
 * tables for both data types.
 *
 * [1] https://stackoverflow.com/a/12996028
 */

uint32_t
u32_hash(uint32_t x) {
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = ((x >> 16) ^ x) * 0x45d9f3b;
    x = (x >> 16) ^ x;
    return x;
}

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

// We assume this works as well as for 32 bits, but who knows?
uint64_t
u64_hash(uint64_t x) {
    x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
    x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
    x = x ^ (x >> 31);
    return x;
}

uint64_t
u64_unhash(uint64_t x) {
    x = (x ^ (x >> 31) ^ (x >> 62)) * UINT64_C(0x319642b2d24d8ec3);
    x = (x ^ (x >> 27) ^ (x >> 54)) * UINT64_C(0x96de1b173f119089);
    x = x ^ (x >> 30) ^ (x >> 60);
    return x;
}

struct ClientsMap {
    struct ClientList **buckets;
    size_t num_buckets;
    size_t size;
};

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

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

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

void
clients_map_add(struct ClientsMap *map, struct Client *client) {
    uint32_t hash = u32_hash(client->id);
    uint32_t i = hash % map->num_buckets;
    // collision if (map->buckets[i] != NULL)
    map->buckets[i] = client_list_add(map->buckets[i], client);
    map->size++;
}

struct Client *
clients_map_erase(struct ClientsMap *map, struct Client *client) {
    uint32_t hash = u32_hash(client->id);
    uint32_t i = hash % map->num_buckets;
    struct ClientList *prev = NULL;
    for (struct ClientList *list = map->buckets[i];
         list != NULL;
         list = list->next) {
        if (list->client == client) {
            if (prev == NULL) {
                // It matched the first, update the starting node of
                // the list
                map->buckets[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);
            map->size--;
            return client;
        }
        prev = list;
    }
    // Not found
    return NULL;
}

struct Client *
clients_map_find(const struct ClientsMap *map, xcb_window_t id) {
    uint32_t hash = u32_hash(id);
    uint32_t i = hash % map->num_buckets;
    for (struct ClientList *list = map->buckets[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 *map) {
    for (size_t i = 0; i < map->num_buckets; i++) {
        client_list_free(map->buckets[i], true);
    }
    free(map->buckets);
    free(map);
}

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;
};

typedef void (*Callback)();

struct CallbackList {
    uint64_t key;
    Callback callback;
    struct CallbackList *next;
};

/*
 * Prepends a new callback to list of callbacks.
 */
struct CallbackList *
callback_list_add(struct CallbackList *list, uint64_t key, Callback callback) {
    struct CallbackList *node = calloc(1, sizeof(struct CallbackList));
    if (node == NULL) {
        // Cannot alloc node, just abort. If list was NULL, stays so.
        return list;
    }
    node->key = key;
    node->callback = callback;
    // Also works when list is NULL
    node->next = list;
    list = node;
    return list;
}

void
callback_list_free(struct CallbackList *list) {
    struct CallbackList *next;
    while (list != NULL) {
        next = list->next;
        free(list);
        list = next;
    }
}

struct CallbacksMap {
    struct CallbackList **buckets;
    size_t num_buckets;
    size_t size;
};

struct CallbacksMap *
callbacks_map_new(size_t num_buckets) {
    struct CallbacksMap *map = calloc(1, sizeof(struct CallbacksMap));
    if (!map) {
        return NULL;
    }

    map->buckets = calloc(num_buckets, sizeof(struct CallbackList *));
    if (!map->buckets) {
        free(map);
        return NULL;
    }

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

/*
 * For internal use only. Call callbacks_map_get() for regular usage.
 *
 * Returns a pointer to the callback so we can modify stuff and reuse
 * the search in multiple other functions.
 */
Callback *
callbacks_map_find(const struct CallbacksMap *map, uint64_t key) {
    uint64_t hash = u64_hash(key);
    uint64_t i = hash % map->num_buckets;
    for (struct CallbackList *list = map->buckets[i];
         list != NULL;
         list = list->next) {
        if (list->key == key) {
            return &list->callback;
        }
    }
    // Not found
    return NULL;
}

Callback
callbacks_map_get(struct CallbacksMap *map, uint64_t key) {
    Callback *callback_ptr = callbacks_map_find(map, key);
    if (callback_ptr == NULL) {
        return NULL;
    }
    return *callback_ptr;
}

/*
 * The semantics with set/unset is that we simply replace whatever
 * callback was there, if something already exists with that key.
 *
 * This function also increases the size of the map if a new callback
 * is added and not simply replaced.
 */
void
callbacks_map_set(struct CallbacksMap *map, uint64_t key, Callback callback) {
    Callback *callback_ptr = callbacks_map_find(map, key);
    if (callback_ptr != NULL) {
        if (*callback_ptr == NULL) {
            // Increase size since there was no callback set, even
            // though the node exists
            map->size++;
        }
        *callback_ptr = callback;
    } else {
        uint64_t hash = u64_hash(key);
        uint64_t i = hash % map->num_buckets;
        map->buckets[i] = callback_list_add(map->buckets[i], key, callback);
        map->size++;
    }
}

/*
 * This function replaces the existing stored callback with NULL,
 * returning the old value, if found. It also reduces the size of the
 * map.
 *
 * That means that once the map grows, it is only truly using less
 * memory when callbacks_map_free() is called.
 */
Callback
callbacks_map_unset(struct CallbacksMap *map, uint64_t key) {
    Callback *callback_ptr = callbacks_map_find(map, key);
    if (callback_ptr != NULL) {
        Callback callback = *callback_ptr;
        *callback_ptr = NULL;
        map->size--;
        return callback;
    }
    // Not found
    return NULL;
}

void
callbacks_map_free(struct CallbacksMap *map) {
    for (size_t i = 0; i < map->num_buckets; i++) {
        callback_list_free(map->buckets[i]);
    }
    free(map->buckets);
    free(map);
}

static struct Config {
    uint16_t border_width, outer_border_width, magnet_border_width;
    int16_t offset_x, offset_y;
    uint16_t offset_width, offset_height;
    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 (*EventHandler)(xcb_generic_event_t *);

static struct {
    uint32_t cur_workspace, num_workspaces;
    bool is_running;
    uint16_t mod_key;
    struct Client *focus;
    struct ClientsMap *clients;
    struct Workspace *workspaces;
    struct CallbacksMap *keys;
    struct CallbacksMap *buttons;
    EventHandler 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_wipe(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;
}

bool
dpy_is_protocol_supported(xcb_window_t window, xcb_atom_t atom) {
    xcb_get_property_cookie_t cookie =
        xcb_icccm_get_wm_protocols_unchecked(
            dpy.conn,
            window,
            dpy.ewmh->WM_PROTOCOLS);
    xcb_icccm_get_wm_protocols_reply_t protocols;
    uint8_t reply = xcb_icccm_get_wm_protocols_reply(
        dpy.conn,
        cookie,
        &protocols,
        NULL);
    if (!reply) {
        return false;
    }

    bool is_supported = false;
    for (uint32_t i = 0; i < protocols.atoms_len; i++) {
        if (protocols.atoms[i] == atom) {
            is_supported = true;
            break;
        }
    }
    xcb_icccm_get_wm_protocols_reply_wipe(&protocols);
    return is_supported;
}

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;
}

bool
dpy_should_update_outputs(const xcb_generic_event_t *event) {
    return dpy.has_randr
        && event->response_type == dpy.randr_base + XCB_RANDR_SCREEN_CHANGE_NOTIFY;
}

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(o_reply));
    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 == NULL) {
        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 == NULL) {
            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) {
                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 == NULL || reply->keycodes_per_modifier == 0) {
        goto mod_from_keycode_end;
    }

    xcb_keycode_t *mod_keycodes = xcb_get_modifier_mapping_keycodes(reply);
    if (mod_keycodes == NULL) {
        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 xcb_cursor_t
dpy_create_cursor(uint16_t glyph) {
    xcb_cursor_t cursor = xcb_generate_id(dpy.conn);
    xcb_create_glyph_cursor(
        dpy.conn,
        cursor,
        dpy.cursor_font,
        dpy.cursor_font,
        glyph,
        glyph + 1,
        0x3232,
        0x3232,
        0x3232,
        0xeeee,
        0xeeee,
        0xeeec);
    return cursor;
}

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 = dpy_create_cursor(MOVE_GLYPH);
    dpy.sizing_cursor = dpy_create_cursor(RESIZE_GLYPH);

    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) {
        assert(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(uint32_t num_workspaces) {
    xcb_ewmh_set_number_of_desktops(dpy.ewmh, dpy.screen_num, 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_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);
}

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

#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_ICONIFIED || client->should_ignore_borders) {
        return;
    }

    dpy_set_window_border_width(client->id);

    xcb_rectangle_t inner_rect[] = {
        RECT_INIT(
            client->width,
            0,
            cfg.border_width - cfg.outer_border_width,
            client->height + cfg.border_width - cfg.outer_border_width
        ),
        RECT_INIT(
            client->width + cfg.border_width + cfg.outer_border_width,
            0,
            cfg.border_width - cfg.outer_border_width,
            client->height + cfg.border_width - cfg.outer_border_width
        ),
        RECT_INIT(
            0,
            client->height,
            client->width + cfg.border_width - cfg.outer_border_width,
            cfg.border_width - cfg.outer_border_width
        ),
        RECT_INIT(
            0,
            client->height + cfg.border_width + cfg.outer_border_width,
            client->width + cfg.border_width - cfg.outer_border_width,
            cfg.border_width - cfg.outer_border_width
        ),
        RECT_INIT(
            client->width + cfg.border_width + cfg.outer_border_width,
            client->height + cfg.border_width + cfg.outer_border_width,
            cfg.border_width,
            cfg.border_width
        ),
    };
    xcb_rectangle_t outer_rect[] = {
        RECT_INIT(
            client->width + cfg.border_width - cfg.outer_border_width,
            0,
            cfg.outer_border_width,
            client->height + cfg.border_width * 2
        ),
        RECT_INIT(
            client->width + cfg.border_width,
            0,
            cfg.outer_border_width,
            client->height + cfg.border_width * 2
        ),
        RECT_INIT(
            0,
            client->height + cfg.border_width - cfg.outer_border_width,
            client->width + cfg.border_width * 2,
            cfg.outer_border_width
        ),
        RECT_INIT(
            0,
            client->height + cfg.border_width,
            client->width + cfg.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.border_width * 2,
        client->height + cfg.border_width * 2);

    uint32_t color = client->is_unkillable
                   ? cfg.colors.unkillable : cfg.colors.outer;
    xcb_gcontext_t gc = xcb_generate_id(dpy.conn);
    xcb_create_gc(dpy.conn, gc, pixmap, 0, NULL);
    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->num_buckets; i++) {
            for (struct ClientList *list = clients->buckets[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_send_window_message(xcb_window_t window, xcb_atom_t atom) {
    xcb_client_message_event_t event;
    event.response_type = XCB_CLIENT_MESSAGE;
    event.format = 32;
    event.sequence = 0;
    event.window = window;
    event.type = dpy.ewmh->WM_PROTOCOLS;
    event.data.data32[0] = atom;
    event.data.data32[1] = XCB_CURRENT_TIME;
    xcb_send_event(
        dpy.conn,
        false,
        window,
        XCB_EVENT_MASK_NO_EVENT,
        (char *) &event);
}

void
dpy_kill_window(xcb_window_t window) {
    xcb_kill_client(dpy.conn, window);
}

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

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

    struct Monitor *monitor = dpy.monitors;
    while (dpy.monitors != NULL) {
        dpy.monitors = monitor_ring_erase(dpy.monitors, monitor);
        free(monitor);
        monitor = dpy.monitors;
    }

    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_grab_key_with_mod(xcb_keysym_t keysym, Callback callback);
void wm_grab_key_with_mod_shift(xcb_keysym_t keysym, Callback callback);
void wm_begin_move_client();
void wm_begin_resize_client();
void wm_focus_close();
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();
void wm_run();

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) {
    uint32_t old_workspace = client->workspace;
    bool is_known = clients_map_find(wm.clients, client->id) != NULL;
    if (old_workspace == workspace && is_known) {
        return;
    }

    // assert(workspace != NULL_WORKSPACE && workspace != ALL_WORKSPACES);
    client->workspace = workspace;
    dpy_set_window_workspace(client->id, workspace);
    if (is_known && old_workspace != NULL_WORKSPACE) {
        wm.workspaces[old_workspace].ring = client_ring_erase(wm.workspaces[old_workspace].ring, client);
        dpy_unmap_window(client->id);
    }
    wm.workspaces[workspace].ring = client_ring_add(wm.workspaces[workspace].ring, client);
}

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);
        dpy_draw_borders(client, wm.focus == client);
        break;
    case WS_ICONIFIED:
        dpy_unmap_window(client->id);
        break;
    case WS_MAXIMIZED:
        if (!client->has_old_size) {
            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 - cfg.border_width * 2;
            client->height = mon_rect.height - cfg.border_width * 2;
        }
        dpy_update_window_geometry(client);
        dpy_draw_borders(client, wm.focus == client);
        break;
    case WS_FULLSCREEN:
        break;
    }
    client->prev_state = client->state;
    client->state = state;
    dpy_set_window_state(client->id, client->state);
}

void
wm_move_client(struct Client *client, int16_t dx, int16_t dy, bool in_monitor) {
    client->x += dx;
    client->y += dy;
    if (in_monitor) {
        struct Rect mon_rect;
        wm_client_monitor_size(client, true, &mon_rect);
        // Complete movement by checking for magnets
        if (client->x < cfg.magnet_border_width + mon_rect.x) {
            client->x = mon_rect.x;
        } else if (client->x + client->width + cfg.border_width >
                   mon_rect.x + mon_rect.width - cfg.magnet_border_width) {
            client->x = mon_rect.x + mon_rect.width - client->width - cfg.border_width * 2;
        }
        if (client->y < cfg.magnet_border_width + mon_rect.y) {
            client->y = mon_rect.y;
        } else if (client->y + client->height + cfg.border_width >
                   mon_rect.y + mon_rect.height - cfg.magnet_border_width) {
            client->y = mon_rect.y + mon_rect.height - client->height - cfg.border_width * 2;
        }
    }
    dpy_update_window_position(client);
    // dpy_draw_focused_borders(client);
    dpy_flush();
}

void
wm_resize_client(struct Client *client,
                 uint16_t width_inc,
                 uint16_t height_inc,
                 bool in_monitor) {
    // TODO: honor inc hints
    client->width += width_inc;
    client->height += height_inc;
    wm_apply_size_hints(client);

    if (in_monitor) {
        struct Rect mon_rect;
        wm_client_monitor_size(client, true, &mon_rect);
        if (client->x + client->width + cfg.border_width >
            mon_rect.x + mon_rect.width) {
            client->width = mon_rect.width - ((client->x - mon_rect.x) + cfg.border_width * 2);
        }
        if (client->y + client->height + cfg.border_width >
            mon_rect.y + mon_rect.height) {
            client->height = mon_rect.height - ((client->y - mon_rect.y) + cfg.border_width * 2);
        }
    }
    dpy_update_window_size(client);
    dpy_draw_focused_borders(client);
    dpy_flush();
}

void
wm_move_resize_client(struct Client *client,
                      const struct Rect *rect,
                      bool in_monitor) {
    if (in_monitor) {
    } else {
        client->x = rect->x;
        client->y = rect->y;
        client->width = rect->width;
        client->height = rect->height;
    }
    wm_apply_size_hints(client);
    dpy_update_window_geometry(client);
    dpy_draw_focused_borders(client);
    dpy_flush();
}

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.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.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.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;
}

void
wm_update_client_monitor(struct Client *client) {
    client->monitor = find_monitor(client);
    wm_fit_client(client);
}

void
wm_handle_state(struct Client *client, xcb_atom_t atom, uint32_t action) {
    // `state' holds what the atom wants to tell us about what to do
    enum WindowState state = WS_NORMAL;
    if (atom == dpy.ewmh->_NET_WM_STATE_FULLSCREEN) {
        state = WS_FULLSCREEN;
    } else if (atom == dpy.ewmh->_NET_WM_STATE_HIDDEN) {
        state = WS_ICONIFIED;
    } else {
        fprintf(stderr,
                "handle_state(): Unknown state=%u, action=%u\n",
                state,
                action);
    }

    // `new_state' is what the new state of our window should be
    enum WindowState new_state = state;
    switch (action) {
    case XCB_EWMH_WM_STATE_ADD:
        // This case is assumed to be the default as well
        new_state = state;
        break;
    case XCB_EWMH_WM_STATE_REMOVE:
        new_state = client->prev_state;
        break;
    case XCB_EWMH_WM_STATE_TOGGLE:
        new_state = client->state != state ? state : client->prev_state;
        break;
    default:
        fprintf(stderr, "handle_state(): Unknown action=%u\n", action);
    }
    wm_set_client_state(client, new_state);
}

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

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

void
wm_grab_key(xcb_keysym_t keysym, bool with_shift, Callback callback) {
    /*
     * Key grabbing is done in two stages:
     *
     * 1. Register a function to be called when that key combo is
     * pressed
     */
    uint16_t mod = wm_get_mod_key(with_shift);
    uint64_t map_key = make_key_chord(mod, keysym);
    callbacks_map_set(wm.keys, map_key, callback);

    /*
     * 2. Tell the display server we are interested in a certain
     * mod/key combo
     */
    dpy_grab_key(mod, keysym);
}

void
wm_grab_key_with_mod(xcb_keysym_t keysym, Callback callback) {
    wm_grab_key(keysym, false, callback);
}

void
wm_grab_key_with_mod_shift(xcb_keysym_t keysym, Callback callback) {
    wm_grab_key(keysym, true, callback);
}

/*
 * Event handlers that know what to cast the generic event 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);
    }
    wm_update_client_monitor(client);
    clients_map_add(wm.clients, client);
    if (client->state == WS_NORMAL || client->state == WS_MAXIMIZED) {
        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.keys = callbacks_map_new(64);
    if (wm.keys == NULL) {
        return false;
    }
    wm.buttons = callbacks_map_new(16);
    if (wm.buttons == NULL) {
        return false;
    }

    wm.cur_workspace = 0;
    wm.num_workspaces = 9;
    wm.workspaces = calloc(wm.num_workspaces, sizeof(struct Workspace));
    if (wm.workspaces == NULL) {
        return false;
    }
    dpy_set_num_workspaces(wm.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.
             */
            fprintf(stderr, "wm_init(): could not manage: %x\n", window);
            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.
             */
            dpy_unmap_window(window);
        }
    }
    windows_query_reply_wipe(&reply);

    dpy_update_window_list(wm.clients);
    wm_set_workspace(wm.cur_workspace);
    wm.mod_key = MOD_ALT;
    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);
    callbacks_map_free(wm.keys);
    callbacks_map_free(wm.buttons);
    dpy_destroy();
}

void
wm_reconfigure(uint16_t border_width,
               uint16_t outer_border_width,
               uint16_t magnet_border_width,
               int16_t offset_x,
               int16_t offset_y,
               uint16_t offset_width,
               uint16_t offset_height,
               uint32_t focused,
               uint32_t unfocused,
               uint32_t unkillable,
               uint32_t empty,
               uint32_t outer) {
    cfg.border_width = border_width;
    cfg.outer_border_width = outer_border_width;
    cfg.magnet_border_width = magnet_border_width;
    cfg.offset_x = offset_x;
    cfg.offset_width = offset_width;
    cfg.offset_height = offset_height;
    cfg.colors.focused = focused;
    cfg.colors.unfocused = unfocused;
    cfg.colors.unkillable = unkillable;
    cfg.colors.empty = empty;
    cfg.colors.outer = outer;

    // Set new window border of ALL clients
    for (uint32_t workspace = 0; workspace < wm.num_workspaces; workspace++) {
        struct Client *client = wm.workspaces[workspace].ring;
        if (client == NULL) {
            continue;
        }

        for (;;) {
            dpy_set_window_border_width(client->id);
            wm_fit_client(client);

            client = client->next;
            if (client == wm.workspaces[workspace].ring) {
                break;
            }
        }
    }

    // Redraw borders of clients from current workspace only
    struct Client *client = wm.workspaces[wm.cur_workspace].ring;
    if (client == NULL) {
        return;
    }

    for (;;) {
        dpy_draw_borders(client, wm.focus == client);
        client = client->next;
        if (client == wm.workspaces[wm.cur_workspace].ring) {
            break;
        }
    }
}

void
wm_close(struct Client *client) {
    if (client->is_unkillable) {
        return;
    }

    if (dpy_is_protocol_supported(client->id, dpy.delete_window_atom)) {
        dpy_send_window_message(client->id, dpy.delete_window_atom);
    } else {
        dpy_kill_window(client->id);
    }
}

void
wm_focus_close() {
    if (wm.focus == NULL) {
        return;
    }

    wm_close(wm.focus);
}

void
wm_raise_and_center_cursor(struct Client *client) {
    dpy_raise_window(client->id);
    dpy_center_cursor_client(client);
}

void
wm_focus_other(bool is_next) {
    struct Client *focused = wm.focus;
    if (focused == NULL) {
        // No current focus, pick first client from the ring
        focused = wm.workspaces[wm.cur_workspace].ring;
    } else {
        // We have focus, pick next/prev
        focused = is_next ? focused->next : focused->prev;
    }
    if (focused == NULL) {
        return;
    }

    wm_raise_and_center_cursor(focused);
    wm_set_focus(focused);
}

void
wm_focus_prev() {
    wm_focus_other(false);
}

void
wm_focus_next() {
    wm_focus_other(true);
}

void
wm_toggle_maximize() {
    if (wm.focus == NULL) {
      return;
    }

    if (wm.focus->state == WS_MAXIMIZED) {
        wm_set_client_state(wm.focus, wm.focus->prev_state);
    } else {
        wm_set_client_state(wm.focus, WS_MAXIMIZED);
    }
}

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

enum TileType {
    TILE_HALF_LEFT,
    TILE_HALF_RIGHT,
    TILE_HALF_TOP,
    TILE_HALF_BOTTOM,
    TILE_TOP_LEFT,
    TILE_TOP_RIGHT,
    TILE_BOTTOM_LEFT,
    TILE_BOTTOM_RIGHT,
};

static void
wm_toggle_tile(enum TileType tile_type) {
    if (wm.focus == NULL) {
        return;
    }

    wm_client_ensure_state(wm.focus, WS_NORMAL);
    if (wm.focus->has_old_size) {
        client_restore_size(wm.focus);
        dpy_update_window_geometry(wm.focus);
        dpy_draw_focused_borders(wm.focus);
   } else {
        struct Rect rect;
        // Start with monitor size, then reduce to appropriate target size
        wm_client_monitor_size(wm.focus, true, &rect);
        switch (tile_type) {
        case TILE_HALF_LEFT:
            rect.width = rect.width / 2;
            break;
        case TILE_HALF_RIGHT:
            rect.x += rect.width / 2;
            rect.width = rect.width / 2;
            break;
        case TILE_HALF_TOP:
            rect.height = rect.height / 2;
            break;
        case TILE_HALF_BOTTOM:
            rect.y += rect.height / 2;
            rect.height = rect.height / 2;
            break;
        case TILE_TOP_LEFT:
            rect.width = rect.width / 2;
            rect.height = rect.height / 2;
            break;
        case TILE_TOP_RIGHT:
            rect.x += rect.width / 2;
            rect.width = rect.width / 2;
            rect.height = rect.height / 2;
            break;
        case TILE_BOTTOM_LEFT:
            rect.y += rect.height / 2;
            rect.width = rect.width / 2;
            rect.height = rect.height / 2;
            break;
        case TILE_BOTTOM_RIGHT:
            rect.x += rect.width / 2;
            rect.y += rect.height / 2;
            rect.width = rect.width / 2;
            rect.height = rect.height / 2;
            break;
        }
        // Correct width/height according to borders
        rect.width -= cfg.border_width * 2;
        rect.height -= cfg.border_width * 2;
        // Stores current size so we can toggle it later
        client_store_size(wm.focus);
        wm_move_resize_client(wm.focus, &rect, false);
    }
    wm_raise_and_center_cursor(wm.focus);
}

void
wm_toggle_half_left() {
    wm_toggle_tile(TILE_HALF_LEFT);
}

void
wm_toggle_half_right() {
    wm_toggle_tile(TILE_HALF_RIGHT);
}

void
wm_toggle_half_top() {
    wm_toggle_tile(TILE_HALF_TOP);
}

void
wm_toggle_half_bottom() {
    wm_toggle_tile(TILE_HALF_BOTTOM);
}

void
wm_toggle_top_left() {
    wm_toggle_tile(TILE_TOP_LEFT);
}

void
wm_toggle_top_right() {
    wm_toggle_tile(TILE_TOP_RIGHT);
}

void
wm_toggle_bottom_left() {
    wm_toggle_tile(TILE_BOTTOM_LEFT);
}

void
wm_toggle_bottom_right() {
    wm_toggle_tile(TILE_BOTTOM_RIGHT);
}

enum PackType {
    PACK_LEFT,
    PACK_RIGHT,
    PACK_TOP,
    PACK_BOTTOM,
};

void
wm_pack_client(enum PackType pack_type) {
    if (wm.focus == NULL || wm.focus->state != WS_NORMAL) {
        return;
    }

    struct Rect rect;
    wm_client_monitor_size(wm.focus, true, &rect);
    int16_t dx = 0, dy = 0;
    switch (pack_type) {
    case PACK_LEFT:
        dx = rect.x - wm.focus->x;
        break;
    case PACK_RIGHT:
        dx = rect.width - (wm.focus->x - rect.x + wm.focus->width) - cfg.border_width * 2;
        break;
    case PACK_TOP:
        dy = rect.y - wm.focus->y;
        break;
    case PACK_BOTTOM:
        dy = rect.height - (wm.focus->y - rect.y + wm.focus->height) - cfg.border_width * 2;
        break;
    }
    wm_move_client(wm.focus, dx, dy, false);
    wm_raise_and_center_cursor(wm.focus);
}

void
wm_pack_left() {
    wm_pack_client(PACK_LEFT);
}

void
wm_pack_right() {
    wm_pack_client(PACK_RIGHT);
}

void
wm_pack_top() {
    wm_pack_client(PACK_TOP);
}

void
wm_pack_bottom() {
    wm_pack_client(PACK_BOTTOM);
}

void
wm_set_focused_client_workspace(uint32_t workspace) {
    if (wm.focus == NULL) {
        return;
    }

    wm_set_client_workspace(wm.focus, workspace);
}

static void
relative_pos(const struct Client *client,
             const struct Monitor *m1,
             const struct Monitor *m2,
             struct Point *p) {
    float scale_x = ((float) (client->x - m1->x)) / m1->width;
    float scale_y = ((float) (client->y - m1->y)) / m1->height;
    p->x = (int16_t) (m2->x + m2->width * scale_x + 0.5f);
    p->y = (int16_t) (m2->y + m2->height * scale_y + 0.5f);
}

void
wm_client_monitor_other(struct Client *client, bool is_next) {
    if (client->monitor == NULL || client->monitor->next == client->monitor) {
        return;
    }

    struct Monitor *other_monitor = is_next
        ? client->monitor->next : client->monitor->prev;
    struct Point new_pos;
    relative_pos(client, client->monitor, other_monitor, &new_pos);
    client->monitor = other_monitor;
    if (client->state == WS_NORMAL) {
        client->x = new_pos.x;
        client->y = new_pos.y;
        if (!wm_fit_client(client)) {
            // wm_fit_client() did not update position, force it
            dpy_update_window_position(client);
        }
    } else {
        // We restore size and ensure it is located within the new
        // monitor before maximizing, otherwise it will move between
        // monitors again when restored. We also fool the function
        // into believing we were not maximized before so that it
        // properly maximizes to the new monitor size.
        client_restore_size(client);
        client->x = new_pos.x;
        client->y = new_pos.y;
        client->state = WS_NORMAL;
        wm_set_client_state(client, WS_MAXIMIZED);
    }
    wm_raise_and_center_cursor(client);
    dpy_flush();
}

void
wm_client_monitor_prev() {
    if (wm.focus == NULL) {
        return;
    }

    wm_client_monitor_other(wm.focus, false);
}

void
wm_client_monitor_next() {
    if (wm.focus == NULL) {
        return;
    }

    wm_client_monitor_other(wm.focus, true);
}

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

void
wm_run() {
    while (wm.is_running) {
        /*
         * Flush everything and check connection health before trying
         * to process further events
         */
        dpy_flush();
        if (dpy_has_error()) {
            fprintf(stderr, "display has an error\n");
            break;
        }

        // We usually get ev == NULL when the display server is killed
        xcb_generic_event_t *ev = xcb_wait_for_event(dpy.conn);
        if (ev == NULL) {
            fprintf(stderr, "cannot get display events, aborting\n");
            break;
        }

        EventHandler handler = wm.events[ev_type(ev)];
        if (handler) {
            handler(ev);
        }
        free(ev);
    }
    wm_destroy();
}

/*
 * 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) {
    fprintf(stderr, "ev_configure_request\n");
    xcb_configure_request_event_t *ev = (xcb_configure_request_event_t *) generic_ev;
    if (configure_request_handler) {
        configure_request_handler();
    }

    struct Client *client = wm_find_client(ev->window);
    if (client == NULL) {
        uint16_t mask = 0;
        uint32_t data[7];
        uint8_t i = 0;
        if (ev->value_mask & XCB_CONFIG_WINDOW_X) {
            mask |= XCB_CONFIG_WINDOW_X;
            data[i++] = ev->x;
        }
        if (ev->value_mask & XCB_CONFIG_WINDOW_Y) {
            mask |= XCB_CONFIG_WINDOW_Y;
            data[i++] = ev->y;
        }
        if (ev->value_mask & XCB_CONFIG_WINDOW_WIDTH) {
            mask |= XCB_CONFIG_WINDOW_WIDTH;
            data[i++] = ev->width;
        }
        if (ev->value_mask & XCB_CONFIG_WINDOW_HEIGHT) {
            mask |= XCB_CONFIG_WINDOW_HEIGHT;
            data[i++] = ev->height;
        }
        if (ev->value_mask & XCB_CONFIG_WINDOW_BORDER_WIDTH) {
            mask |= XCB_CONFIG_WINDOW_BORDER_WIDTH;
            data[i++] = ev->border_width;
        }
        if (ev->value_mask & XCB_CONFIG_WINDOW_SIBLING) {
            mask |= XCB_CONFIG_WINDOW_SIBLING;
            data[i++] = ev->sibling;
        }
        if (ev->value_mask & XCB_CONFIG_WINDOW_STACK_MODE) {
            mask |= XCB_CONFIG_WINDOW_STACK_MODE;
            data[i++] = ev->stack_mode;
        }
        if (i > 0) {
            // TODO: should be a dpy_something() function
            xcb_configure_window(dpy.conn, ev->window, mask, data);
        }
    } else if (client->state == WS_NORMAL) {
        // TODO: do we need to handle XCB_CONFIG_WINDOW_SIBLING and
        // XCB_CONFIG_WINDOW_STACK_MODE?
        if (ev->value_mask & XCB_CONFIG_WINDOW_X) {
            client->x = ev->x;
        }
        if (ev->value_mask & XCB_CONFIG_WINDOW_Y) {
            client->y = ev->y;
        }
        if (ev->value_mask & XCB_CONFIG_WINDOW_WIDTH) {
            client->width = ev->width;
        }
        if (ev->value_mask & XCB_CONFIG_WINDOW_HEIGHT) {
            client->height = ev->height;
        }
        wm_apply_size_hints(client);
        dpy_update_window_geometry(client);
        dpy_draw_borders(client, wm.focus == client);
        wm_update_client_monitor(client);
    }
}

// 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) {
    fprintf(stderr, "ev_destroy_notify\n");
    xcb_destroy_notify_event_t *ev = (xcb_destroy_notify_event_t *) generic_ev;
    if (destroy_notify_handler) {
        destroy_notify_handler();
    }

    struct Client *client = wm_find_client(ev->window);
    if (client == NULL) {
        return;
    }

    wm_erase_client(client->id);
    dpy_update_window_list(wm.clients);
    dpy_flush();
}

// 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) {
    xcb_enter_notify_event_t *ev = (xcb_enter_notify_event_t *) generic_ev;
    if (enter_notify_handler) {
        enter_notify_handler();
    }

    if ((ev->mode != XCB_NOTIFY_MODE_NORMAL && ev->mode != XCB_NOTIFY_MODE_UNGRAB)
        || (wm.focus != NULL && wm.focus->id == ev->event)) {
        return;
    }

    struct Client *client = wm_find_client(ev->event);
    if (client != NULL) {
        wm_set_focus(client);
    }
}

// XCB_KEY_PRESS
typedef void (*key_press_handler_t)(uint16_t, xcb_keysym_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) {
    fprintf(stderr, "ev_key_press\n");
    xcb_key_press_event_t *ev = (xcb_key_press_event_t *) generic_ev;
    uint16_t mod = dpy_clean_mod(ev->state);
    xcb_keysym_t keysym = dpy_keysym_from_keycode(ev->detail);

    if (key_press_handler) {
        key_press_handler(mod, keysym);
    }

    uint64_t map_key = make_key_chord(mod, keysym);
    Callback callback = callbacks_map_get(wm.keys, map_key);
    if (callback != NULL) {
        callback();
    }
}

// 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) {
    fprintf(stderr, "ev_map_request\n");
    xcb_map_request_event_t *ev = (xcb_map_request_event_t *) generic_ev;
    if (map_request_handler) {
        map_request_handler();
    }

    struct Client *client = wm_find_client(ev->window);
    if (client != NULL) {
        // Client already known, ignore
        return;
    }

    client = manage_client_maybe_reposition(ev->window, true);
    if (client != NULL) {
        dpy_set_window_state(client->id, WS_NORMAL);
        dpy_center_cursor_client(client);
        dpy_update_window_list(wm.clients);
    }

    // Map as requested, it does not matter if we can manage or not
    dpy_map_window(ev->window);
    dpy_flush();
}

// 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) {
    fprintf(stderr, "ev_unmap_notify\n");
    xcb_unmap_notify_event_t *ev = (xcb_unmap_notify_event_t *) generic_ev;
    if (unmap_notify_handler) {
        unmap_notify_handler();
    }
    return;

    struct Client *client = wm_find_client(ev->window);
    if (client == NULL
        || wm.workspaces[wm.cur_workspace].ring == NULL
        || client->state == WS_ICONIFIED) {
        /*
         * For unknown clients, clients not in our current workspace,
         * or when a client was unmmaped and state is already iconified,
         * we don't have to do anything
         */
        return;
    }

    bool should_ignore = true;
    struct Client *ring_client = wm.workspaces[wm.cur_workspace].ring;
    for (;;) {
        if (ring_client->id == ev->window) {
            /*
             * We found the client in the current workspace, now we
             * must handle the unmapping
             */
            should_ignore = false;
            break;
        }
        ring_client = ring_client->next;
        if (ring_client == wm.workspaces[wm.cur_workspace].ring) {
            break;
        }
    }
    if (should_ignore) {
        return;
    }

    dpy_flush();
}

// XXX: do we need this?
// 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) {
    fprintf(stderr, "ev_mapping_notify\n");
    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) {
    fprintf(stderr, "ev_configure_notify\n");
    xcb_configure_notify_event_t *ev = (xcb_configure_notify_event_t *) generic_ev;
    if (configure_notify_handler) {
        configure_notify_handler(ev->x, ev->y, ev->width, ev->height);
    }

    if (ev->window != dpy.screen->root) {
        // Currently ignoring regular windows being reconfigured
        return;
    }

    if (ev->width != dpy.screen->width_in_pixels ||
        ev->height != dpy.screen->height_in_pixels) {
        dpy.screen->width_in_pixels = ev->width;
        dpy.screen->height_in_pixels = ev->height;

        if (!dpy.has_randr) {
            // TODO: loop over all clients and call fit_client()
            dpy_flush();
        }
    }
}

// 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) {
    fprintf(stderr, "ev_circulate_request\n");
    xcb_circulate_request_event_t *ev = (xcb_circulate_request_event_t *) generic_ev;
    if (circulate_request_handler) {
        circulate_request_handler();
    }

    /*
     * XXX:
     * For proper abstraction, we should be calling
     *
     * dpy_circulate_window(ev->window, ev->place);
     *
     * instead. But this direct call below makes our code smaller.
     */
    xcb_circulate_window(dpy.conn, ev->window, ev->place);
}

// 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) {
    fprintf(stderr, "ev_button_press\n");
    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) {
    fprintf(stderr, "ev_client_message\n");
    xcb_client_message_event_t *ev = (xcb_client_message_event_t *) generic_ev;
    if (client_message_handler) {
        client_message_handler();
    }

    if (ev->type == dpy.ewmh->_NET_CURRENT_DESKTOP) {
        wm_set_workspace(ev->data.data32[0]);
        return;
    }

    struct Client *client = wm_find_client(ev->window);
    if (client == NULL) {
        return;
    }

    if (ev->type == dpy.ewmh->_NET_ACTIVE_WINDOW) {
        wm_set_focus(client);
    } else if (ev->type == dpy.ewmh->_NET_WM_DESKTOP) {
        wm_set_client_workspace(client, ev->data.data32[0]);
    } else if (ev->type == dpy.ewmh->_NET_CLOSE_WINDOW) {
        wm_close(client);
    } else if (ev->type == dpy.ewmh->_NET_WM_STATE) {
        wm_handle_state(client, ev->data.data32[1], ev->data.data32[0]);
        wm_handle_state(client, ev->data.data32[2], ev->data.data32[0]);
    } else if (ev->type == dpy.change_state_atom
               && ev->format == 32
               && ev->data.data32[0] == XCB_ICCCM_WM_STATE_ICONIC) {
        wm_handle_state(
            client,
            dpy.ewmh->_NET_WM_STATE_HIDDEN,
            XCB_EWMH_WM_STATE_TOGGLE);
    }
}