struct Lexer {
    Allocator allocator;
    char *at;
    char *start;
    char *end;
    char *name;
    int line, column;
};

enum TriggerKind {
    TriggerKind_Error,
    TriggerKind_Key,
    TriggerKind_Mouse,
    TriggerKind_Binary,
};

struct Trigger {
    TriggerKind kind;
    Trigger *left;
    Trigger *right;
    SDL_Keycode key;
    struct {
        EventKind event_kind : 8;
        U32 ctrl : 1;
        U32 alt : 1;
        U32 shift : 1;
    };
};

void Advance(Lexer *lex) {
    if (lex->at < lex->end) {
        if (lex->at[0] == '\n') {
            lex->line += 1;
            lex->column = 0;
        } else {
            lex->column += 1;
        }
        lex->at += 1;
    }
}

void Advance(Lexer *lex, int n) {
    for (int i = 0; i < n; i += 1) Advance(lex);
}

char At(Lexer *lex) {
    if (lex->at < lex->end) {
        return lex->at[0];
    }
    return 0;
}

String AsString(Lexer *lex) {
    String result = {lex->at, lex->end - lex->at};
    return result;
}

void EatWhitespace(Lexer *lex) {
    while (At(lex) != '\n' && IsWhitespace(At(lex))) {
        Advance(lex);
    }
}

Trigger *TriggerBinary(Lexer *lex, Trigger *left, Trigger *right, int key) {
    Trigger *result = AllocType(lex->allocator, Trigger);
    result->kind = TriggerKind_Binary;
    result->key = key;
    result->left = left;
    result->right = right;
    return result;
}

Trigger *ParseKeyAtom(Lexer *lex) {
    Trigger *result = AllocType(lex->allocator, Trigger);
    result->kind = TriggerKind_Key;
    EatWhitespace(lex);
    for (;;) {
        String lex_string = AsString(lex);
        if (StartsWith(lex_string, "ctrl")) {
            result->ctrl = true;
            Advance(lex, 4);
        } else if (StartsWith(lex_string, "shift")) {
            result->shift = true;
            Advance(lex, 5);
        } else if (StartsWith(lex_string, "alt")) {
            result->alt = true;
            Advance(lex, 3);
        } else if (IsAlphanumeric(At(lex))) {
            char *start = lex->at;
            while (IsAlphanumeric(At(lex))) {
                Advance(lex);
            }
            String a = {start, lex->at - start};
            Advance(lex);

            bool found = false;
            for (int i = 0; !found && i < Lengthof(MouseConversionTable); i += 1) {
                if (a == MouseConversionTable[i].string) {
                    result->event_kind = MouseConversionTable[i].value;
                    result->kind = TriggerKind_Mouse;
                    found = true;
                }
            }

            for (int i = 0; !found && i < Lengthof(SDLKeycodeConversionTable); i += 1) {
                if (a == SDLKeycodeConversionTable[i].string) {
                    result->key = SDLKeycodeConversionTable[i].value;
                    found = true;
                }
            }

            if (!found) {
                result->kind = TriggerKind_Error;
                ReportErrorf("%s:%d:%d: Failed to parse key trigger, unexpected identifier: '%d'", lex->name, lex->line, lex->column, result->key);
                return result;
            }
        } else {
            result->kind = TriggerKind_Error;
            ReportErrorf("%s:%d:%d: Failed to parse key trigger, unexpected character: '%c'", lex->name, lex->line, lex->column, At(lex));
            return result;
        }

        if (At(lex) == '-') {
            Advance(lex);
        } else {
            break;
        }
    }
    return result;
}

Trigger *ParseKeyChord(Lexer *lex) {
    Trigger *left = ParseKeyAtom(lex);
    EatWhitespace(lex);
    while (IsAlphanumeric(At(lex))) {
        int op = At(lex);
        left = TriggerBinary(lex, left, ParseKeyChord(lex), ' ');
        EatWhitespace(lex);
    }
    return left;
}

Trigger *ParseKeyExpr(Lexer *lex) {
    Trigger *left = ParseKeyChord(lex);
    EatWhitespace(lex);
    while (At(lex) == '|') {
        Advance(lex);
        left = TriggerBinary(lex, left, ParseKeyExpr(lex), '|');
        EatWhitespace(lex);
    }
    return left;
}

Trigger *ParseKey(Allocator allocator, String key, char *debug_name) {
    Lexer lex = {allocator, key.data, key.data, key.data + key.len, debug_name};
    Trigger *result = ParseKeyExpr(&lex);
    return result;
}

struct CachedTrigger {
    Trigger *trigger;
    String key;
};
Array<CachedTrigger> CachedTriggers;

Trigger *ParseKeyCached(String key) {
    if (key.len == 0) {
        return NULL;
    }
    For (CachedTriggers) {
        if (it.key == key) {
            return it.trigger;
        }
    }

    Allocator allocator = GetSystemAllocator();
    Trigger *result = ParseKey(allocator, key, key.data);
    if (!result) {
        return NULL;
    }

    Add(&CachedTriggers, {result, key});
    return result;
}

bool MatchEvent(Trigger *trigger, Event *event) {
    if (trigger->kind == TriggerKind_Key) {
        if (trigger->key == event->key && trigger->ctrl == event->ctrl && trigger->alt == event->alt && trigger->shift == event->shift) {
            return true;
        }
    } else if (trigger->kind == TriggerKind_Mouse) {
        if (trigger->event_kind == event->kind) {
            return true;
        }
    } else if (trigger->kind == TriggerKind_Binary) {
        if (trigger->key == ' ') {
            return false;
        } else if (trigger->key == '|') {
            bool ok = MatchEvent(trigger->left, event);
            if (ok) return ok;
            ok = MatchEvent(trigger->right, event);
            if (ok) return ok;
        } ElseInvalidCodepath();
    } else {
        return false;
    }
    return false;
}

void TestParser() {
    Scratch scratch;
    {
        char *cmd = "ctrl-b";
        Lexer base_lex = {scratch, cmd, cmd, cmd + strlen(cmd), "keybinding"};
        Trigger *trigger = ParseKeyExpr(&base_lex);
        Assert(trigger->kind == TriggerKind_Key);
        Assert(trigger->key == SDLK_B);
        Assert(trigger->ctrl);
        Assert(trigger->shift == 0);
    }

    {
        char *cmd = "ctrl-b shift-ctrl-a";
        Lexer base_lex = {scratch, cmd, cmd, cmd + strlen(cmd), "keybinding"};
        Trigger *trigger = ParseKeyExpr(&base_lex);
        Assert(trigger->kind == TriggerKind_Binary);
        Assert(trigger->key == ' ');
        Assert(trigger->left->kind == TriggerKind_Key);
        Assert(trigger->left->key == SDLK_B);
        Assert(trigger->left->ctrl);
        Assert(trigger->left->shift == 0);
        Assert(trigger->right->kind == TriggerKind_Key);
        Assert(trigger->right->key == SDLK_A);
        Assert(trigger->right->ctrl);
        Assert(trigger->right->shift);
    }

    {
        char *cmd = "ctrl-b shift-ctrl-a | ctrl-c | ctrl-d";
        Lexer base_lex = {scratch, cmd, cmd, cmd + strlen(cmd), "keybinding"};
        Trigger *trigger = ParseKeyExpr(&base_lex);
        Assert(trigger->kind == TriggerKind_Binary);
        Assert(trigger->key == '|');

        Assert(trigger->left->kind == TriggerKind_Binary);
        Assert(trigger->left->key == ' ');

        Assert(trigger->right->kind == TriggerKind_Binary);
        Assert(trigger->right->key == '|');


        Event event = {};
        event.kind = EVENT_KEY_PRESS;
        event.key = SDLK_D;
        event.ctrl = 1;
        bool ok = MatchEvent(trigger, &event);
        Assert(ok);

        event.key = SDLK_F1;
        ok = MatchEvent(trigger, &event);
        Assert(ok == 0);

        event.ctrl = 1;
        event.shift = 1;
        event.key = SDLK_A;
        ok = MatchEvent(trigger, &event);
        Assert(!ok);
    }


} RegisterFunction(&TestFunctions, TestParser);
