<commit_before>/*

Licensed under the Apache License, Version 2.0 (the "License"); you may not use
this file except in compliance with the License. You may obtain a copy of the
License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed
under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR
CONDITIONS OF ANY KIND, either express or implied. See the License for the
specific language governing permissions and limitations under the License.

*/

#include <time.h>
#include <unistd.h>
#include <stdarg.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <xcb/xcb.h>
#include <xcb/xcb_icccm.h>
#include <xcb/xcb_ewmh.h>
#include <xcb/xcb_keysyms.h>


// TODO (fixes)
// sort out error handling (exit codes, man xcb-requests), memory management, exit cleanup
// mask usages (x3): what should the order be?  doc says just pass in one
// open font once, globally
// structures for:
//  - wsetups, size, new wsetups, new size
//  - wsetup.overlay_*, wsetup.window
// change wsetup->overlay_rect to be just size
// xcb_image_text_8: handle case with text size > 255

// TODO (improvements)
// help/manpage
// configurable font/text size/colours/placement/padding, better defaults
// take window IDs as whitelist/blacklist
// options for output format (hex)
// better expose redrawing (only some windows/rects?)
// work out how to clear a window instead of having a gc just for it


// -- types

/**
 * Part of a keysym lookup, used to translate between keysyms and characters.
 *
 * character: the ASCII character
 * keysym: the Xorg keysym to interpret the character as
 */
typedef struct keysyms_lookup_t {
    char character;
    xcb_keysym_t keysym;
} keysyms_lookup_t;

/**
 * A recursive structure holding data about windows, used to track the windows
 * we care about.  Exactly one of `window` (paired with `overlay_*`) and
 * `children` is non-NULL.
 *
 * ?overlay_window: the window we created over the top of the tracked window
 * ?overlay_font_gc: for drawing the text on `overlay_window`
 * ?overlay_fbg_gc: for drawing the background on `overlay_window`
 * ?overlay_rect: the on-screen area covered by `overlay_window`
 * ?window: the pre-existing tracked window
 * character: the character that must be typed to select `window`, or to descend
 *     into `children`
 * ?children: the continuation of the structure
 * children_size: size of `children` (0 if `children` is NULL)
 */
typedef struct window_setup_t {
    xcb_window_t* overlay_window;
    xcb_gcontext_t* overlay_font_gc;
    xcb_gcontext_t* overlay_bg_gc;
    xcb_rectangle_t* overlay_rect;
    xcb_window_t* window;
    char character;
    struct window_setup_t* children;
    int children_size;
} window_setup_t;


/**
 * Collection of data needed throughout the runtime of the program.
 *
 * xcon: the connection to the X server
 * xroot: the root window
 * ewmh: the state for `xcb_ewmh`
 * ksymbols: cached key symbols
 * ksl: keys available for use
 * wsetups: array of setup structures
 */
typedef struct xcw_state_t {
    xcb_connection_t* xcon;
    xcb_window_t xroot;
    xcb_ewmh_connection_t ewmh;
    xcb_key_symbols_t* ksymbols;
    keysyms_lookup_t* ksl;
    int ksl_size;
    window_setup_t* wsetups;
    int wsetups_size;
} xcw_state_t;


// -- constants

/**
 * Text colour for overlay windows.
 */
int FG_COLOUR = 0xffffffff;
/**
 * Background colour for overlay windows.
 */
int BG_COLOUR = 0xff333333;
/**
 * Window class set on overlay windows.
 */
char* OVERLAY_WINDOW_CLASS = "overlay\0xorg-choose-window";
/**
 * Number of windows requested from _NET_CLIENT_LIST.
 */
int MAX_WINDOWS = 1024;

/**
 * Keysyms with an obvious 1-character representation.  Only these characters
 * may be used as input.
 */
keysyms_lookup_t ALL_KEYSYMS_LOOKUP[] = {
    {'0', 0x0030},
    {'1', 0x0031},
    {'2', 0x0032},
    {'3', 0x0033},
    {'4', 0x0034},
    {'5', 0x0035},
    {'6', 0x0036},
    {'7', 0x0037},
    {'8', 0x0038},
    {'9', 0x0039},
    {'a', 0x0061},
    {'b', 0x0062},
    {'c', 0x0063},
    {'d', 0x0064},
    {'e', 0x0065},
    {'f', 0x0066},
    {'g', 0x0067},
    {'h', 0x0068},
    {'i', 0x0069},
    {'j', 0x006a},
    {'k', 0x006b},
    {'l', 0x006c},
    {'m', 0x006d},
    {'n', 0x006e},
    {'o', 0x006f},
    {'p', 0x0070},
    {'q', 0x0071},
    {'r', 0x0072},
    {'s', 0x0073},
    {'t', 0x0074},
    {'u', 0x0075},
    {'v', 0x0076},
    {'w', 0x0077},
    {'x', 0x0078},
    {'y', 0x0079},
    {'z', 0x007a}
};
/**
 * Size of `ALL_KEYSYMS_LOOKUP`.
 */
int ALL_KEYSYMS_LOOKUP_SIZE = (
    sizeof(ALL_KEYSYMS_LOOKUP) / sizeof(*ALL_KEYSYMS_LOOKUP));


// -- utilities

/**
 * Compute the smaller of two numbers.
 */
int min (int a, int b) {
    return a < b ? a : b;
}


/**
 * Compute the larger of two numbers.
 */
int max (int a, int b) {
    return a < b ? b : a;
}


/**
 * Print a message to stderr and exit the process with a failure status.  Takes
 * arguments like `*printf`.
 */
void die (char *fmt, ...) {
    va_list args;
    va_start(args, fmt);
    vfprintf(stderr, fmt, args);
    va_end(args);
    exit(1);
}


/**
 * Exit the process with a status indicating a window was chosen.
 */
void exit_match () {
    exit(0);
}


/**
 * Exit the process with a status indicating no window was chosen.
 */
void exit_no_match () {
    exit(0);
}


/**
 * Print the chosen window to stdout and exit the process.
 */
void choose_window (xcb_window_t window) {
    printf("%d\n", window);
    exit_match();
}


// -- xorg utilities

/**
 * Perform the check for a checked, reply-less xcb request.
 *
 * cookie: corresponding to the request
 * msg: to print in case of error
 */
void xorg_check_request (xcb_connection_t* xcon,
                         xcb_void_cookie_t cookie, char *msg) {
    xcb_generic_error_t *error = xcb_request_check(xcon, cookie);
    if (error) die("xcb error: %s (%d)\n", msg, error->error_code);
}


/**
 * Move and resize a window.
 *
 * x, y: new absolute screen location
 */
void xorg_window_move_resize (xcb_connection_t* xcon, xcb_window_t window,
                              int x, int y, int w, int h) {
    int mask = (XCB_CONFIG_WINDOW_X | XCB_CONFIG_WINDOW_Y |
                XCB_CONFIG_WINDOW_WIDTH | XCB_CONFIG_WINDOW_HEIGHT);
    uint32_t values[] = { x, y, w, h };
    xcb_configure_window(xcon, window, mask, values);
}


/**
 * Determine whether a window has a property defined.
 *
 * prop: property ID
 */
int xorg_window_has_property (xcb_connection_t* xcon,
                              xcb_window_t window, xcb_atom_t prop) {
    xcb_list_properties_cookie_t lpc = xcb_list_properties(xcon, window);
    xcb_list_properties_reply_t* lpr;
    if (!(lpr = xcb_list_properties_reply(xcon, lpc, NULL))) {
        die("list_properties");
    }

    xcb_atom_t* props = xcb_list_properties_atoms(lpr);
    int result = 0;
    for (int i = 0; i < xcb_list_properties_atoms_length(lpr); i++) {
        if (props[i] == prop) {
            result = 1;
            break;
        }
    }

    free(lpr);
    return result;
}


/**
 * Determine whether a window is 'normal' and visible according to the base Xorg
 * specification.
 */
int xorg_window_normal (xcb_connection_t* xcon, xcb_window_t window) {
    xcb_get_window_attributes_cookie_t gwac = (
        xcb_get_window_attributes(xcon, window));
    xcb_get_window_attributes_reply_t* gwar;
    if (!(gwar = xcb_get_window_attributes_reply(xcon, gwac, NULL))) {
        die("get_window_attributes\n");
    }

    return (
        gwar->map_state == XCB_MAP_STATE_VIEWABLE &&
        gwar->override_redirect == 0
    );
}


/**
 * Determine whether a window is 'normal' according EWMH.
 */
int ewmh_window_normal (xcw_state_t* state, xcb_window_t window) {
    xcb_get_property_cookie_t gpc = (
        xcb_get_property(state->xcon, 0, window,
                         state->ewmh._NET_WM_WINDOW_TYPE, XCB_ATOM_ATOM, 0, 1));
    xcb_get_property_reply_t* gpr;
    if (!(gpr = xcb_get_property_reply(state->xcon, gpc, NULL))) {
        die("get_property _NET_WM_WINDOW_TYPE\n");
    }
    uint32_t* window_type = (uint32_t*)xcb_get_property_value(gpr);
    int prop_len = xcb_get_property_value_length(gpr);
    free(gpr);

    // if reply length is 0, window type isn't defined, so treat it as normal
    return (
        prop_len == 0 ||
        window_type[0] != state->ewmh._NET_WM_WINDOW_TYPE_NORMAL);
}


/**
 * Get all windows from the X server.
 *
 * windows (output): window IDs
 * windows_size (output): size of `windows`
 */
void xorg_get_windows (xcw_state_t* state,
                       xcb_window_t** windows, int* windows_size) {
    xcb_query_tree_cookie_t qtc = xcb_query_tree(state->xcon, state->xroot);
    xcb_query_tree_reply_t* qtr;
    if (!(qtr = xcb_query_tree_reply(state->xcon, qtc, NULL))) {
        die("query_tree\n");
    }
    xcb_window_t* referenced_windows = xcb_query_tree_children(qtr);
    int size = xcb_query_tree_children_length(qtr);

    // copy for easier usage
    *windows = calloc(size, sizeof(xcb_window_t));
    for (int i = 0; i < size; i++) (*windows)[i] = referenced_windows[i];
    free(qtr);

    *windows_size = size;
}


/**
 * Get windows managed by the window manager.
 *
 * is_defined (output): whether the window manager defines the windows it
 *     tracks; if 0, `windows` and `windows_size` will not be set
 * windows (output): window IDs
 * windows_size (output): size of `windows`
 */
void xorg_get_managed_windows (xcw_state_t* state, int* is_defined,
                               xcb_window_t** windows, int* windows_size) {
    *is_defined = xorg_window_has_property(
        state->xcon, state->xroot, state->ewmh._NET_CLIENT_LIST);

    if (*is_defined) {
        xcb_get_property_cookie_t gpc = (
            xcb_get_property(state->xcon, 0, state->xroot,
                             state->ewmh._NET_CLIENT_LIST, XCB_ATOM_WINDOW, 0,
                             MAX_WINDOWS));
        xcb_get_property_reply_t* gpr;
        if (!(gpr = xcb_get_property_reply(state->xcon, gpc, NULL))) {
            die("get_property _NET_CLIENT_LIST\n");
        }
        xcb_window_t* referenced_windows = (
            (xcb_window_t*)xcb_get_property_value(gpr));
        // each window ID is 4 bytes
        int size = xcb_get_property_value_length(gpr) / 4;

        // copy for easier usage
        *windows = calloc(size, sizeof(xcb_window_t));
        for (int i = 0; i < size; i++) (*windows)[i] = referenced_windows[i];
        free(gpr);

        *windows_size = size;
    }
}


/**
 * Determine whether a window is managed by the window manager.
 *
 * managed_windows: windows that are managed by the window manager
 */
int xorg_window_managed (xcb_window_t window, xcb_window_t* managed_windows,
                         int managed_windows_size) {
    int found = 0;
    for (int i = 0; i < managed_windows_size; i++) {
        if (managed_windows[i] == window) {
            found = 1;
            break;
        }
    }
    return found;
}


/**
 * Initialise the connection to the X server.
 *
 * state (output): pointer to program state; `ksl` and `wsetups` are not
 *     initialised
 */
void initialise_xorg (xcw_state_t** state) {
    int default_screen; // unused
    xcb_screen_t *screen;
    xcb_connection_t* xcon = xcb_connect(NULL, &default_screen);
    if (xcb_connection_has_error(xcon)) die("connect\n");

    screen = xcb_setup_roots_iterator(xcb_get_setup(xcon)).data;
    if (screen == NULL) die("no screens\n");
    xcb_window_t xroot = screen->root;

    xcb_ewmh_connection_t ewmh;
    xcb_intern_atom_cookie_t *ewmhc = xcb_ewmh_init_atoms(xcon, &ewmh);
    if (!xcb_ewmh_init_atoms_replies(&ewmh, ewmhc, NULL)) die("ewmh init\n");

    xcb_key_symbols_t* ksymbols;
    ksymbols = xcb_key_symbols_alloc(xcon);
    if (ksymbols == NULL) die("key_symbols_alloc\n");

    *state = malloc(sizeof(xcw_state_t));
    xcw_state_t local_state = { xcon, xroot, ewmh, ksymbols, NULL, 0, NULL, 0 };
    **state = local_state;
}


// -- input handling

/**
 * Find an item in a keysym lookup given its character.
 *
 * ksl: keysym lookup to search
 * c: character to search for
 *
 * returns: found item, NULL if no matching items were found
 */
keysyms_lookup_t* keysyms_lookup_find_char (
    keysyms_lookup_t* ksl, int ksl_size, char c
) {
    for (int i = 0; i < ksl_size; i++) {
        if (ksl[i].character == c) {
            return &(ksl[i]);
        }
    }
    return NULL;
}


/**
 * Find an item in a keysym lookup given its keysym.
 *
 * ksl: keysym lookup to search
 * ksym: keysym to search for
 *
 * returns: found item, NULL if no matching items were found
 */
keysyms_lookup_t* keysyms_lookup_find_keysym (
    keysyms_lookup_t* ksl, int ksl_size, xcb_keysym_t ksym
) {
    for (int i = 0; i < ksl_size; i++) {
        if (ksl[i].keysym == ksym) {
            return &(ksl[i]);
        }
    }
    return NULL;
}


/**
 * Parse command-line arguments.
 *
 * argc, argv: as passed to `main`
 * ksl (output): keysym lookup containing allowed characters
 * ksl_size (output): size of `ksl`
 */
void parse_args (int argc, char** argv, keysyms_lookup_t** ksl, int* ksl_size) {
    if (argc != 2) die("expected exactly one argument\n");

    // character pool argument: check validity of characters, compile lookup
    char* char_pool = argv[1];
    // we won't put more than `char_pool` items in `ksl`
    *ksl = calloc(strlen(char_pool), sizeof(keysyms_lookup_t));
    int size = 0;

    for (int i = 0; i < strlen(char_pool); i++) {
        char c = char_pool[i];
        keysyms_lookup_t* ksl_item = keysyms_lookup_find_char(
            ALL_KEYSYMS_LOOKUP, ALL_KEYSYMS_LOOKUP_SIZE, c);
        if (ksl_item == NULL) die("unknown character: %c\n", c);
        // don't allow duplicates in lookup
        if (keysyms_lookup_find_char(*ksl, size, c) == NULL) {
            (*ksl)[size] = *ksl_item;
            size += 1;
        }
    }

    if (size < 2) die("expected at least two characters\n");
    *ksl = realloc(*ksl, sizeof(keysyms_lookup_t) * size);
    *ksl_size = size;
}


/**
 * Acquire a Xorg keyboard grab on the root window.
 */
void initialise_input (xcw_state_t* state) {
    // wait a little for other programs to release the keyboard
    // since this program is likely to be launched from a hotkey daemon
    struct timespec ts = { 0, 1000000 }; // 1ms
    int status;
    for (int s = 0; s < 1000; s++) { // up to 1s total
        xcb_grab_keyboard_cookie_t gkc = xcb_grab_keyboard(
            state->xcon, 0, state->xroot, XCB_CURRENT_TIME,
            XCB_GRAB_MODE_ASYNC, XCB_GRAB_MODE_ASYNC);
        xcb_grab_keyboard_reply_t* gkr;

        if ((gkr = xcb_grab_keyboard_reply(state->xcon, gkc, NULL))) {
            status = gkr->status;
            free(gkr);
            if (status == XCB_GRAB_STATUS_ALREADY_GRABBED) {
                nanosleep(&ts, NULL);
                continue;
            } else if (status == XCB_GRAB_STATUS_SUCCESS) {
                break;
            } else {
                die("grab_keyboard: %d\n", status);
            }
        } else {
            die("grab_keyboard\n");
        }
    }

    if (status == XCB_GRAB_STATUS_ALREADY_GRABBED) {
        die("grab_keyboard: %d\n", status);
    }
}


// -- overlay windows

/**
 * Create an overlay window.
 *
 * x, y: absolute screen location
 * w, h: window size
 */
xcb_window_t* overlay_create (xcw_state_t* state, int x, int y, int w, int h) {
    xcb_window_t* win = malloc(sizeof(xcb_window_t));
    *win = xcb_generate_id(state->xcon);
    uint32_t mask = (XCB_CW_BACK_PIXEL | XCB_CW_OVERRIDE_REDIRECT |
                     XCB_CW_SAVE_UNDER | XCB_CW_EVENT_MASK);
    uint32_t values[] = {
        BG_COLOUR, 1, 1, XCB_EVENT_MASK_EXPOSURE | XCB_EVENT_MASK_KEY_PRESS
    };
    xcb_void_cookie_t cwc = xcb_create_window_checked(
        state->xcon, XCB_COPY_FROM_PARENT, *win, state->xroot, 0, 0, 1, 1, 0,
        XCB_WINDOW_CLASS_INPUT_OUTPUT, XCB_COPY_FROM_PARENT, mask, values);
    xorg_check_request(state->xcon, cwc, "create_window");

    xcb_icccm_set_wm_class(
        state->xcon, *win, sizeof(OVERLAY_WINDOW_CLASS), OVERLAY_WINDOW_CLASS);
    xorg_window_move_resize(state->xcon, *win, x, y, w, h);
    xcb_void_cookie_t mwc = xcb_map_window_checked(state->xcon, *win);
    xorg_check_request(state->xcon, mwc, "map_window");
    return win;
}


/**
 * Create a graphics context for drawing the background of an overlay window.
 *
 * win: the overlay window
 */
xcb_gc_t* overlay_get_bg_gc (xcb_connection_t* xcon, xcb_window_t win) {
    xcb_gcontext_t* gc = malloc(sizeof(xcb_gcontext_t));
    *gc = xcb_generate_id(xcon);
    uint32_t mask = XCB_GC_FOREGROUND;
    uint32_t value_list[] = { BG_COLOUR };
    xcb_void_cookie_t cgc = (
        xcb_create_gc_checked(xcon, *gc, win, mask, value_list));
    xorg_check_request(xcon, cgc, "create_gc");
    return gc;
}


/**
 * Create a graphics context for drawing the text of an overlay window.
 *
 * win: the overlay window
 * font_name: name of the font used to render the text
 */
xcb_gc_t* overlay_get_font_gc (xcb_connection_t* xcon,
                               xcb_window_t win, char *font_name) {
    xcb_font_t font = xcb_generate_id(xcon);
    xcb_void_cookie_t ofc = (
        xcb_open_font_checked(xcon, font, strlen(font_name), font_name));
    xorg_check_request(xcon, ofc, "open_font");

    xcb_gcontext_t* gc = malloc(sizeof(xcb_gcontext_t));
    *gc = xcb_generate_id(xcon);
    uint32_t mask = XCB_GC_FOREGROUND | XCB_GC_BACKGROUND | XCB_GC_FONT;
    uint32_t value_list[] = { FG_COLOUR, BG_COLOUR, font };
    xcb_void_cookie_t cgc = (
        xcb_create_gc_checked(xcon, *gc, win, mask, value_list));
    xorg_check_request(xcon, cgc, "create_gc");

    xcb_close_font(xcon, font);
    return gc;
}


/**
 * Set the text on an overlay window.  `xcb_flush` should be called after
 * calling this function.
 *
 * wsetup: containing the overlay window (if there is no overlay window, this
 *     function does nothing)
 * text: text to render (null-terminated)
 */
void overlay_set_text (xcb_connection_t* xcon,
                       window_setup_t* wsetup, char* text) {
    if (wsetup->overlay_window == NULL) return;
    xcb_window_t win = *(wsetup->overlay_window);

    if (wsetup->overlay_bg_gc == NULL) {
        wsetup->overlay_bg_gc = overlay_get_bg_gc(xcon, win);
    }
    if (wsetup->overlay_font_gc == NULL) {
        wsetup->overlay_font_gc = overlay_get_font_gc(xcon, win, "fixed");
    }

    xcb_poly_fill_rectangle(xcon, win, *(wsetup->overlay_bg_gc), 1,
                            wsetup->overlay_rect);
    xcb_image_text_8(xcon, strlen(text), win, *(wsetup->overlay_font_gc),
                     30, 20, text);
}


/**
 * See `overlays_set_text`.  `xcb_flush` should be called after calling * this
 * function.
 *
 * text: prefix to text rendered to every overlay window (null-terminated)
 */
void _overlays_set_text (xcb_connection_t* xcon, window_setup_t* wsetups,
                         int wsetups_size, char* text) {
    for (int i = 0; i < wsetups_size; i++) {
        window_setup_t* wsetup = &(wsetups[i]);
        int text_size = strlen(text);
        // next level down is 1 character longer, plus 1 for null
        char* new_text = calloc(text_size + 2, sizeof(char));
        strcpy(new_text, text);
        new_text[text_size] = wsetup->character;
        new_text[text_size + 1] = '\0';

        overlay_set_text(xcon, wsetup, new_text);
        if (wsetup->children != NULL) {
            _overlays_set_text(xcon, wsetup->children, wsetup->children_size,
                               new_text);
        }

        free(new_text);
    }
}


/**
 * Update text on all overlay windows.
 */
void overlays_set_text (xcw_state_t* state) {
    char* text = "";
    _overlays_set_text(state->xcon, state->wsetups, state->wsetups_size, text);
    xcb_flush(state->xcon);
}


// -- wsetup utilities


/**
 * See `initialise_window_tracking`.
 *<commit_msg>only open the font once, not once for each window<commit_after>/*

Licensed under the Apache License, Version 2.0 (the "License"); you may not use
this file except in compliance with the License. You may obtain a copy of the
License at

    http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed
under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR
CONDITIONS OF ANY KIND, either express or implied. See the License for the
specific language governing permissions and limitations under the License.

*/

#include <time.h>
#include <unistd.h>
#include <stdarg.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <xcb/xcb.h>
#include <xcb/xcb_icccm.h>
#include <xcb/xcb_ewmh.h>
#include <xcb/xcb_keysyms.h>


// TODO (fixes)
// sort out error handling (exit codes, man xcb-requests), memory management, exit cleanup
// mask usages (x3): what should the order be?  doc says just pass in one
// structures for:
//  - wsetups, size, new wsetups, new size
//  - wsetup.overlay_*, wsetup.window
// change wsetup->overlay_rect to be just size
// xcb_image_text_8: handle case with text size > 255

// TODO (improvements)
// help/manpage
// configurable font/text size/colours/placement/padding, better defaults
// take window IDs as whitelist/blacklist
// options for output format (hex)
// better expose redrawing (only some windows/rects?)
// work out how to clear a window instead of having a gc just for it


// -- types

/**
 * Part of a keysym lookup, used to translate between keysyms and characters.
 *
 * character: the ASCII character
 * keysym: the Xorg keysym to interpret the character as
 */
typedef struct keysyms_lookup_t {
    char character;
    xcb_keysym_t keysym;
} keysyms_lookup_t;

/**
 * A recursive structure holding data about windows, used to track the windows
 * we care about.  Exactly one of `window` (paired with `overlay_*`) and
 * `children` is non-NULL.
 *
 * ?overlay_window: the window we created over the top of the tracked window
 * ?overlay_font_gc: for drawing the text on `overlay_window`
 * ?overlay_fbg_gc: for drawing the background on `overlay_window`
 * ?overlay_rect: the on-screen area covered by `overlay_window`
 * ?window: the pre-existing tracked window
 * character: the character that must be typed to select `window`, or to descend
 *     into `children`
 * ?children: the continuation of the structure
 * children_size: size of `children` (0 if `children` is NULL)
 */
typedef struct window_setup_t {
    xcb_window_t* overlay_window;
    xcb_gcontext_t* overlay_font_gc;
    xcb_gcontext_t* overlay_bg_gc;
    xcb_rectangle_t* overlay_rect;
    xcb_window_t* window;
    char character;
    struct window_setup_t* children;
    int children_size;
} window_setup_t;


/**
 * Collection of data needed throughout the runtime of the program.
 *
 * xcon: the connection to the X server
 * xroot: the root window
 * ewmh: the state for `xcb_ewmh`
 * ksymbols: cached key symbols
 * overlay_font: font used to render text on overlays
 * ksl: keys available for use
 * wsetups: array of setup structures
 */
typedef struct xcw_state_t {
    xcb_connection_t* xcon;
    xcb_window_t xroot;
    xcb_ewmh_connection_t ewmh;
    xcb_key_symbols_t* ksymbols;
    xcb_font_t overlay_font;
    keysyms_lookup_t* ksl;
    int ksl_size;
    window_setup_t* wsetups;
    int wsetups_size;
} xcw_state_t;


// -- constants

/**
 * Text colour for overlay windows.
 */
int FG_COLOUR = 0xffffffff;
/**
 * Name of the font used to render text on overlay windows.
 */
char* OVERLAY_FONT_NAME = "fixed";
/**
 * Background colour for overlay windows.
 */
int BG_COLOUR = 0xff333333;
/**
 * Window class set on overlay windows.
 */
char* OVERLAY_WINDOW_CLASS = "overlay\0xorg-choose-window";
/**
 * Number of windows requested from _NET_CLIENT_LIST.
 */
int MAX_WINDOWS = 1024;

/**
 * Keysyms with an obvious 1-character representation.  Only these characters
 * may be used as input.
 */
keysyms_lookup_t ALL_KEYSYMS_LOOKUP[] = {
    {'0', 0x0030},
    {'1', 0x0031},
    {'2', 0x0032},
    {'3', 0x0033},
    {'4', 0x0034},
    {'5', 0x0035},
    {'6', 0x0036},
    {'7', 0x0037},
    {'8', 0x0038},
    {'9', 0x0039},
    {'a', 0x0061},
    {'b', 0x0062},
    {'c', 0x0063},
    {'d', 0x0064},
    {'e', 0x0065},
    {'f', 0x0066},
    {'g', 0x0067},
    {'h', 0x0068},
    {'i', 0x0069},
    {'j', 0x006a},
    {'k', 0x006b},
    {'l', 0x006c},
    {'m', 0x006d},
    {'n', 0x006e},
    {'o', 0x006f},
    {'p', 0x0070},
    {'q', 0x0071},
    {'r', 0x0072},
    {'s', 0x0073},
    {'t', 0x0074},
    {'u', 0x0075},
    {'v', 0x0076},
    {'w', 0x0077},
    {'x', 0x0078},
    {'y', 0x0079},
    {'z', 0x007a}
};
/**
 * Size of `ALL_KEYSYMS_LOOKUP`.
 */
int ALL_KEYSYMS_LOOKUP_SIZE = (
    sizeof(ALL_KEYSYMS_LOOKUP) / sizeof(*ALL_KEYSYMS_LOOKUP));


// -- utilities

/**
 * Compute the smaller of two numbers.
 */
int min (int a, int b) {
    return a < b ? a : b;
}


/**
 * Compute the larger of two numbers.
 */
int max (int a, int b) {
    return a < b ? b : a;
}


/**
 * Print a message to stderr and exit the process with a failure status.  Takes
 * arguments like `*printf`.
 */
void die (char *fmt, ...) {
    va_list args;
    va_start(args, fmt);
    vfprintf(stderr, fmt, args);
    va_end(args);
    exit(1);
}


/**
 * Exit the process with a status indicating a window was chosen.
 */
void exit_match () {
    exit(0);
}


/**
 * Exit the process with a status indicating no window was chosen.
 */
void exit_no_match () {
    exit(0);
}


/**
 * Print the chosen window to stdout and exit the process.
 */
void choose_window (xcb_window_t window) {
    printf("%d\n", window);
    exit_match();
}


// -- xorg utilities

/**
 * Perform the check for a checked, reply-less xcb request.
 *
 * cookie: corresponding to the request
 * msg: to print in case of error
 */
void xorg_check_request (xcb_connection_t* xcon,
                         xcb_void_cookie_t cookie, char *msg) {
    xcb_generic_error_t *error = xcb_request_check(xcon, cookie);
    if (error) die("xcb error: %s (%d)\n", msg, error->error_code);
}


/**
 * Move and resize a window.
 *
 * x, y: new absolute screen location
 */
void xorg_window_move_resize (xcb_connection_t* xcon, xcb_window_t window,
                              int x, int y, int w, int h) {
    int mask = (XCB_CONFIG_WINDOW_X | XCB_CONFIG_WINDOW_Y |
                XCB_CONFIG_WINDOW_WIDTH | XCB_CONFIG_WINDOW_HEIGHT);
    uint32_t values[] = { x, y, w, h };
    xcb_configure_window(xcon, window, mask, values);
}


/**
 * Determine whether a window has a property defined.
 *
 * prop: property ID
 */
int xorg_window_has_property (xcb_connection_t* xcon,
                              xcb_window_t window, xcb_atom_t prop) {
    xcb_list_properties_cookie_t lpc = xcb_list_properties(xcon, window);
    xcb_list_properties_reply_t* lpr;
    if (!(lpr = xcb_list_properties_reply(xcon, lpc, NULL))) {
        die("list_properties");
    }

    xcb_atom_t* props = xcb_list_properties_atoms(lpr);
    int result = 0;
    for (int i = 0; i < xcb_list_properties_atoms_length(lpr); i++) {
        if (props[i] == prop) {
            result = 1;
            break;
        }
    }

    free(lpr);
    return result;
}


/**
 * Determine whether a window is 'normal' and visible according to the base Xorg
 * specification.
 */
int xorg_window_normal (xcb_connection_t* xcon, xcb_window_t window) {
    xcb_get_window_attributes_cookie_t gwac = (
        xcb_get_window_attributes(xcon, window));
    xcb_get_window_attributes_reply_t* gwar;
    if (!(gwar = xcb_get_window_attributes_reply(xcon, gwac, NULL))) {
        die("get_window_attributes\n");
    }

    return (
        gwar->map_state == XCB_MAP_STATE_VIEWABLE &&
        gwar->override_redirect == 0
    );
}


/**
 * Determine whether a window is 'normal' according EWMH.
 */
int ewmh_window_normal (xcw_state_t* state, xcb_window_t window) {
    xcb_get_property_cookie_t gpc = (
        xcb_get_property(state->xcon, 0, window,
                         state->ewmh._NET_WM_WINDOW_TYPE, XCB_ATOM_ATOM, 0, 1));
    xcb_get_property_reply_t* gpr;
    if (!(gpr = xcb_get_property_reply(state->xcon, gpc, NULL))) {
        die("get_property _NET_WM_WINDOW_TYPE\n");
    }
    uint32_t* window_type = (uint32_t*)xcb_get_property_value(gpr);
    int prop_len = xcb_get_property_value_length(gpr);
    free(gpr);

    // if reply length is 0, window type isn't defined, so treat it as normal
    return (
        prop_len == 0 ||
        window_type[0] != state->ewmh._NET_WM_WINDOW_TYPE_NORMAL);
}


/**
 * Get all windows from the X server.
 *
 * windows (output): window IDs
 * windows_size (output): size of `windows`
 */
void xorg_get_windows (xcw_state_t* state,
                       xcb_window_t** windows, int* windows_size) {
    xcb_query_tree_cookie_t qtc = xcb_query_tree(state->xcon, state->xroot);
    xcb_query_tree_reply_t* qtr;
    if (!(qtr = xcb_query_tree_reply(state->xcon, qtc, NULL))) {
        die("query_tree\n");
    }
    xcb_window_t* referenced_windows = xcb_query_tree_children(qtr);
    int size = xcb_query_tree_children_length(qtr);

    // copy for easier usage
    *windows = calloc(size, sizeof(xcb_window_t));
    for (int i = 0; i < size; i++) (*windows)[i] = referenced_windows[i];
    free(qtr);

    *windows_size = size;
}


/**
 * Get windows managed by the window manager.
 *
 * is_defined (output): whether the window manager defines the windows it
 *     tracks; if 0, `windows` and `windows_size` will not be set
 * windows (output): window IDs
 * windows_size (output): size of `windows`
 */
void xorg_get_managed_windows (xcw_state_t* state, int* is_defined,
                               xcb_window_t** windows, int* windows_size) {
    *is_defined = xorg_window_has_property(
        state->xcon, state->xroot, state->ewmh._NET_CLIENT_LIST);

    if (*is_defined) {
        xcb_get_property_cookie_t gpc = (
            xcb_get_property(state->xcon, 0, state->xroot,
                             state->ewmh._NET_CLIENT_LIST, XCB_ATOM_WINDOW, 0,
                             MAX_WINDOWS));
        xcb_get_property_reply_t* gpr;
        if (!(gpr = xcb_get_property_reply(state->xcon, gpc, NULL))) {
            die("get_property _NET_CLIENT_LIST\n");
        }
        xcb_window_t* referenced_windows = (
            (xcb_window_t*)xcb_get_property_value(gpr));
        // each window ID is 4 bytes
        int size = xcb_get_property_value_length(gpr) / 4;

        // copy for easier usage
        *windows = calloc(size, sizeof(xcb_window_t));
        for (int i = 0; i < size; i++) (*windows)[i] = referenced_windows[i];
        free(gpr);

        *windows_size = size;
    }
}


/**
 * Determine whether a window is managed by the window manager.
 *
 * managed_windows: windows that are managed by the window manager
 */
int xorg_window_managed (xcb_window_t window, xcb_window_t* managed_windows,
                         int managed_windows_size) {
    int found = 0;
    for (int i = 0; i < managed_windows_size; i++) {
        if (managed_windows[i] == window) {
            found = 1;
            break;
        }
    }
    return found;
}


/**
 * Initialise the connection to the X server.
 *
 * state (output): pointer to program state; `ksl` and `wsetups` are not
 *     initialised
 */
void initialise_xorg (xcw_state_t** state) {
    int default_screen; // unused
    xcb_screen_t *screen;
    xcb_connection_t* xcon = xcb_connect(NULL, &default_screen);
    if (xcb_connection_has_error(xcon)) die("connect\n");

    screen = xcb_setup_roots_iterator(xcb_get_setup(xcon)).data;
    if (screen == NULL) die("no screens\n");
    xcb_window_t xroot = screen->root;

    xcb_ewmh_connection_t ewmh;
    xcb_intern_atom_cookie_t *ewmhc = xcb_ewmh_init_atoms(xcon, &ewmh);
    if (!xcb_ewmh_init_atoms_replies(&ewmh, ewmhc, NULL)) die("ewmh init\n");

    xcb_key_symbols_t* ksymbols;
    ksymbols = xcb_key_symbols_alloc(xcon);
    if (ksymbols == NULL) die("key_symbols_alloc\n");

    xcb_font_t overlay_font = xcb_generate_id(xcon);
    xcb_void_cookie_t ofc = xcb_open_font_checked(
        xcon, overlay_font, strlen(OVERLAY_FONT_NAME), OVERLAY_FONT_NAME);
    xorg_check_request(xcon, ofc, "open_font");

    *state = malloc(sizeof(xcw_state_t));
    xcw_state_t local_state = {
        xcon, xroot, ewmh, ksymbols, overlay_font, NULL, 0, NULL, 0
    };
    **state = local_state;
}


// -- input handling

/**
 * Find an item in a keysym lookup given its character.
 *
 * ksl: keysym lookup to search
 * c: character to search for
 *
 * returns: found item, NULL if no matching items were found
 */
keysyms_lookup_t* keysyms_lookup_find_char (
    keysyms_lookup_t* ksl, int ksl_size, char c
) {
    for (int i = 0; i < ksl_size; i++) {
        if (ksl[i].character == c) {
            return &(ksl[i]);
        }
    }
    return NULL;
}


/**
 * Find an item in a keysym lookup given its keysym.
 *
 * ksl: keysym lookup to search
 * ksym: keysym to search for
 *
 * returns: found item, NULL if no matching items were found
 */
keysyms_lookup_t* keysyms_lookup_find_keysym (
    keysyms_lookup_t* ksl, int ksl_size, xcb_keysym_t ksym
) {
    for (int i = 0; i < ksl_size; i++) {
        if (ksl[i].keysym == ksym) {
            return &(ksl[i]);
        }
    }
    return NULL;
}


/**
 * Parse command-line arguments.
 *
 * argc, argv: as passed to `main`
 * ksl (output): keysym lookup containing allowed characters
 * ksl_size (output): size of `ksl`
 */
void parse_args (int argc, char** argv, keysyms_lookup_t** ksl, int* ksl_size) {
    if (argc != 2) die("expected exactly one argument\n");

    // character pool argument: check validity of characters, compile lookup
    char* char_pool = argv[1];
    // we won't put more than `char_pool` items in `ksl`
    *ksl = calloc(strlen(char_pool), sizeof(keysyms_lookup_t));
    int size = 0;

    for (int i = 0; i < strlen(char_pool); i++) {
        char c = char_pool[i];
        keysyms_lookup_t* ksl_item = keysyms_lookup_find_char(
            ALL_KEYSYMS_LOOKUP, ALL_KEYSYMS_LOOKUP_SIZE, c);
        if (ksl_item == NULL) die("unknown character: %c\n", c);
        // don't allow duplicates in lookup
        if (keysyms_lookup_find_char(*ksl, size, c) == NULL) {
            (*ksl)[size] = *ksl_item;
            size += 1;
        }
    }

    if (size < 2) die("expected at least two characters\n");
    *ksl = realloc(*ksl, sizeof(keysyms_lookup_t) * size);
    *ksl_size = size;
}


/**
 * Acquire a Xorg keyboard grab on the root window.
 */
void initialise_input (xcw_state_t* state) {
    // wait a little for other programs to release the keyboard
    // since this program is likely to be launched from a hotkey daemon
    struct timespec ts = { 0, 1000000 }; // 1ms
    int status;
    for (int s = 0; s < 1000; s++) { // up to 1s total
        xcb_grab_keyboard_cookie_t gkc = xcb_grab_keyboard(
            state->xcon, 0, state->xroot, XCB_CURRENT_TIME,
            XCB_GRAB_MODE_ASYNC, XCB_GRAB_MODE_ASYNC);
        xcb_grab_keyboard_reply_t* gkr;

        if ((gkr = xcb_grab_keyboard_reply(state->xcon, gkc, NULL))) {
            status = gkr->status;
            free(gkr);
            if (status == XCB_GRAB_STATUS_ALREADY_GRABBED) {
                nanosleep(&ts, NULL);
                continue;
            } else if (status == XCB_GRAB_STATUS_SUCCESS) {
                break;
            } else {
                die("grab_keyboard: %d\n", status);
            }
        } else {
            die("grab_keyboard\n");
        }
    }

    if (status == XCB_GRAB_STATUS_ALREADY_GRABBED) {
        die("grab_keyboard: %d\n", status);
    }
}


// -- overlay windows

/**
 * Create an overlay window.
 *
 * x, y: absolute screen location
 * w, h: window size
 */
xcb_window_t* overlay_create (xcw_state_t* state, int x, int y, int w, int h) {
    xcb_window_t* win = malloc(sizeof(xcb_window_t));
    *win = xcb_generate_id(state->xcon);
    uint32_t mask = (XCB_CW_BACK_PIXEL | XCB_CW_OVERRIDE_REDIRECT |
                     XCB_CW_SAVE_UNDER | XCB_CW_EVENT_MASK);
    uint32_t values[] = {
        BG_COLOUR, 1, 1, XCB_EVENT_MASK_EXPOSURE | XCB_EVENT_MASK_KEY_PRESS
    };
    xcb_void_cookie_t cwc = xcb_create_window_checked(
        state->xcon, XCB_COPY_FROM_PARENT, *win, state->xroot, 0, 0, 1, 1, 0,
        XCB_WINDOW_CLASS_INPUT_OUTPUT, XCB_COPY_FROM_PARENT, mask, values);
    xorg_check_request(state->xcon, cwc, "create_window");

    xcb_icccm_set_wm_class(
        state->xcon, *win, sizeof(OVERLAY_WINDOW_CLASS), OVERLAY_WINDOW_CLASS);
    xorg_window_move_resize(state->xcon, *win, x, y, w, h);
    xcb_void_cookie_t mwc = xcb_map_window_checked(state->xcon, *win);
    xorg_check_request(state->xcon, mwc, "map_window");
    return win;
}


/**
 * Create a graphics context for drawing the background of an overlay window.
 *
 * win: the overlay window
 */
xcb_gc_t* overlay_get_bg_gc (xcb_connection_t* xcon, xcb_window_t win) {
    xcb_gcontext_t* gc = malloc(sizeof(xcb_gcontext_t));
    *gc = xcb_generate_id(xcon);
    uint32_t mask = XCB_GC_FOREGROUND;
    uint32_t value_list[] = { BG_COLOUR };
    xcb_void_cookie_t cgc = (
        xcb_create_gc_checked(xcon, *gc, win, mask, value_list));
    xorg_check_request(xcon, cgc, "create_gc");
    return gc;
}


/**
 * Create a graphics context for drawing the text of an overlay window.
 *
 * win: the overlay window
 */
xcb_gc_t* overlay_get_font_gc (xcw_state_t* state, xcb_window_t win) {
    xcb_gcontext_t* gc = malloc(sizeof(xcb_gcontext_t));
    *gc = xcb_generate_id(state->xcon);
    uint32_t mask = XCB_GC_FOREGROUND | XCB_GC_BACKGROUND | XCB_GC_FONT;
    uint32_t value_list[] = { FG_COLOUR, BG_COLOUR, state->overlay_font };
    xcb_void_cookie_t cgc = (
        xcb_create_gc_checked(state->xcon, *gc, win, mask, value_list));
    xorg_check_request(state->xcon, cgc, "create_gc");
    return gc;
}


/**
 * Set the text on an overlay window.  `xcb_flush` should be called after
 * calling this function.
 *
 * wsetup: containing the overlay window (if there is no overlay window, this
 *     function does nothing)
 * text: text to render (null-terminated)
 */
void overlay_set_text (xcw_state_t* state,
                       window_setup_t* wsetup, char* text) {
    if (wsetup->overlay_window == NULL) return;
    xcb_window_t win = *(wsetup->overlay_window);

    if (wsetup->overlay_bg_gc == NULL) {
        wsetup->overlay_bg_gc = overlay_get_bg_gc(state->xcon, win);
    }
    if (wsetup->overlay_font_gc == NULL) {
        wsetup->overlay_font_gc = overlay_get_font_gc(state, win);
    }

    xcb_poly_fill_rectangle(state->xcon, win, *(wsetup->overlay_bg_gc), 1,
                            wsetup->overlay_rect);
    xcb_image_text_8(state->xcon, strlen(text), win, *(wsetup->overlay_font_gc),
                     30, 20, text);
}


/**
 * See `overlays_set_text`.  `xcb_flush` should be called after calling * this
 * function.
 *
 * wsetups: array of setup structures containing overlay windows to render text
 *     on (recursively)
 * text: prefix to text rendered to every overlay window (null-terminated)
 */
void _overlays_set_text (xcw_state_t* state, window_setup_t* wsetups,
                         int wsetups_size, char* text) {
    for (int i = 0; i < wsetups_size; i++) {
        window_setup_t* wsetup = &(wsetups[i]);
        int text_size = strlen(text);
        // next level down is 1 character longer, plus 1 for null
        char* new_text = calloc(text_size + 2, sizeof(char));
        strcpy(new_text, text);
        new_text[text_size] = wsetup->character;
        new_text[text_size + 1] = '\0';

        overlay_set_text(state, wsetup, new_text);
        if (wsetup->children != NULL) {
            _overlays_set_text(state, wsetup->children, wsetup->children_size,
                               new_text);
        }

        free(new_text);
    }
}


/**
 * Update text on all overlay windows.
 */
void overlays_set_text (xcw_state_t* state) {
    char* text = "";
    _overlays_set_text(state, state->wsetups, state->wsetups_size, text);
    xcb_flush(state->xcon);
}


// -- wsetup utilities


/**
 * See `initialise_window_tracking`.
 *
{'fraction_non_alphanumeric': 0.11783352732856188, 'fraction_numerical': 0.014512494118229772, 'mean_word_length': 2.985786200769914, 'pattern_counts': {'":': 0, '<': 51, '<?xml version=': 0, '>': 131, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6471542', 'n_tokens_mistral': 14964, 'n_tokens_neox': 14181, 'n_words': 3751}