parser.c

#include "include/parser.h"
#include "include/lexer.h"
#include <assert.h>
#include <stdio.h>

void parser_print_node(Node *node) {
    switch (node->type) {
    case NT_BREAK_STMT: {
        BreakStmt *stmt = node->break_stmt;
        printf("BreakStmt:\n");
        if (stmt->label != NULL)
            parser_print_node(stmt->label);
    } break;
    case NT_FOR_LOOP_STMT: {
        ForLoopStmt *for_loop_stmt = node->for_loop_stmt;
        printf("ForLoopStmt:\n");
        if (for_loop_stmt->init_clause != NULL)
            parser_print_node(for_loop_stmt->init_clause);
        if (for_loop_stmt->cond_expression != NULL)
            parser_print_node(for_loop_stmt->cond_expression);
        if (for_loop_stmt->iteration_expression != NULL)
            parser_print_node(for_loop_stmt->iteration_expression);
        parser_print_node(for_loop_stmt->body);
    } break;
    case NT_WHILE_STMT: {
        WhileStmt *stmt = node->while_stmt;
        printf("WhileStmt\n");
        parser_print_node(stmt->condition);
        parser_print_node(stmt->body);
    } break;
    case NT_VAR_DECL_STMT: {
        VarDeclStmt *stmt = node->var_decl_stmt;
        printf("VarDeclStmt: (%.*s)\n", SV_Arg(stmt->name));
        parser_print_node(stmt->type);
        parser_print_node(stmt->decl);
    } break;
    case NT_BIN_EXPR: {
        printf("BinExpr:\n");
        parser_print_node(node->bin_expr->lhs);
        printf(SV_Fmt "\n", SV_Arg(node->bin_expr->operand.lexme));
        parser_print_node(node->bin_expr->rhs);
    } break;
    case NT_FN_DECL: {
        FnDeclStmt *stmt = node->fn_decl_stmt;
        printf("FnDeclStmt: name:(" SV_Fmt ")\n", SV_Arg(stmt->name));
        parser_print_node(stmt->typename);
        for (int i = 0; i < stmt->parameters.count; i += 1) {
            FnParam param = stmt->parameters.items[i];
            parser_print_node(param.type);
            printf("name:(" SV_Fmt ")\n", SV_Arg(param.name));
        }
        parser_print_node(stmt->block);
    } break;
    case NT_BLOCK: {
        BlockStmt *block = node->block_stmt;
        printf("BlockStmt:\n");
        for (int i = 0; i < block->nodes.count; i += 1) {
            parser_print_node(block->nodes.items[i]);
        }
    } break;
    case NT_EXPR_STMT: {
        parser_print_node(node->expr_stmt->expr);
    } break;
    case NT_LIT_STRING: {
        LitStringExpr *expr = node->lit_string_expr;
        printf("LitStringExpr: `%.*s`\n", SV_Arg(expr->lit));
    } break;
    case NT_IDENT_EXPR: {
        IdentExpr *expr = node->ident_expr;
        printf("IdentExpr: `%.*s`\n", SV_Arg(expr->lit));
    } break;
    case NT_FN_CALL_EXPR: {
        FnCallExpr *expr = node->fn_call_expr;
        printf("FnCallExpr: `%.*s`\n", SV_Arg(expr->name));
        for (int i = 0; i < expr->args.count; i += 1) {
            parser_print_node(expr->args.items[i]);
        }
    } break;
    case NT_LIT_NUMBER: {
        LitNumberExpr *expr = node->lit_number_expr;
        printf("LitNumberExpr: `%.*s`\n", SV_Arg(expr->lit));
    } break;
    case NT_IF_STMT: {
        IfStmt *stmt = node->if_stmt;
        printf("IfStmt\n");
        parser_print_node(stmt->condition);
        parser_print_node(stmt->block);
        if (stmt->_else != NULL) {
            printf("else_ block:\n");
            parser_print_node(stmt->_else);
        }
    } break;
    }
}

Token parser_get_token(Parser *p) {
    return p->tokens.items[p->cursor];
}

// is end of file or end of tokens
bool is_eof_or_eot(Parser *p) {
    return p->cursor >= p->tokens.count || parser_get_token(p).type == TT_EOF;
}

bool parser_get_token_off(Parser *p, int off, Token *token) {
    if (p->cursor + off >= p->tokens.count)
        return false;
    *token = p->tokens.items[p->cursor + off];
    return true;
}

bool parser_advance(Parser *p) {
    if (p->cursor + 1 >= p->tokens.count)
        return false;
    p->cursor += 1;
    return true;
}

bool expect(Parser *p, TokenType tt) {
    bool ok = parser_get_token(p).type == tt;
    if (!ok)
        return false;
    p->cursor += 1;
    return true;
}

bool expect_and_get(Parser *p, TokenType tt, Token *token) {
    Token t = parser_get_token(p);
    bool ok = t.type == tt;
    if (!ok)
        return false;
    *token = t;
    p->cursor += 1;
    return true;
}

ParseResult parser_parse_stmt(Parser *);
ParseResult parser_parse_expr(Parser *);
ParseResult parser_parse_expr_with_precedence(Parser *, int);
ParseResult parser_parse_ident_expr(Parser *);

ParseResult parser_parse_type_expr(Parser *p) {
    Token token = parser_get_token(p);
    switch (token.type) {
    case TT_IDENT:
        return parser_parse_ident_expr(p);
    default:
        printf("Invalid token as type expression:" SV_Fmt "\n", SV_Arg(token.lexme));
        return INVALID_RES;
    }

    return INVALID_RES;
}

ParseResult parser_parse_block_stmt(Parser *p) {
    Token start;
    if (!expect_and_get(p, TT_OPEN_CURLY, &start)) {
        printf("Invalid token as start of block stmt\n");
        return INVALID_RES;
    }

    Nodes stmts = {0};
    while (parser_get_token(p).type != TT_CLOSE_CURLY && !is_eof_or_eot(p)) {
        ParseResult res = parser_parse_stmt(p);
        if (!res.ok) {
            printf("Failed to parse stmt inside block at %d:%d\n", start.loc.row, start.loc.col);
            return INVALID_RES;
        }
        da_append(&stmts, res.node);
    }

    Token end;
    if (!expect_and_get(p, TT_CLOSE_CURLY, &end)) {
        printf("Invalid token as start of block stmt\n");
        return INVALID_RES;
    }

    Node *node = temp_alloc(sizeof(Node));
    node->type = NT_BLOCK;
    node->start = start.loc;
    node->end = end.loc;
    BlockStmt *stmt = temp_alloc(sizeof(BlockStmt));
    stmt->base = node;
    stmt->nodes = stmts;
    node->block_stmt = stmt;

    return PARSE_SUCC(node);
}

ParseResult parser_parse_lit_number_expr(Parser *p) {

    Token start;
    if (!expect_and_get(p, TT_INT_NUMBER, &start)) {
        printf("expect number literal when parse a number literal.\n");
        return INVALID_RES;
    }

    Node *node = temp_alloc(sizeof(Node));
    node->type = NT_LIT_NUMBER;
    node->start = start.loc;
    node->end = (TokenLoc){node->start.col + start.lexme.count, node->start.row, ""};
    LitNumberExpr *lit = temp_alloc(sizeof(LitNumberExpr));
    lit->base = node;
    // note(marco): storing the actual representation, later use atoi to convert into int
    lit->lit = start.lexme;
    node->lit_number_expr = lit;
    return PARSE_SUCC(node);
}

ParseResult parser_parse_lit_string_expr(Parser *p) {
    Token start;
    if (!expect_and_get(p, TT_STRING, &start)) {
        printf("expect string literal when parse a string literal.\n");
        return INVALID_RES;
    }

    Node *node = temp_alloc(sizeof(Node));
    node->type = NT_LIT_STRING;
    node->start = start.loc;
    node->end = (TokenLoc){node->start.col + start.lexme.count, node->start.row, ""};
    LitStringExpr *lit = temp_alloc(sizeof(LitStringExpr));
    lit->base = node;
    lit->lit = start.lexme;
    if (!sv_chop_prefix(&lit->lit, sv_from_cstr("\""))) {
        printf("Failed to unquote string\n");
        return INVALID_RES;
    }
    if (!sv_chop_suffix(&lit->lit, sv_from_cstr("\""))) {
        printf("Failed to unquote string\n");
        return INVALID_RES;
    }
    node->lit_string_expr = lit;
    return PARSE_SUCC(node);
}

ParseResult parser_parse_ident_expr(Parser *p) {
    Token start;
    if (!expect_and_get(p, TT_IDENT, &start)) {
        printf("expected identifier\n");
        return INVALID_RES;
    }

    Node *node = temp_alloc(sizeof(Node));
    node->type = NT_IDENT_EXPR;
    node->start = start.loc;
    node->end = (TokenLoc){node->start.col + start.lexme.count, node->start.row, ""};
    IdentExpr *expr = temp_alloc(sizeof(IdentExpr));
    expr->base = node;
    expr->lit = start.lexme;
    node->ident_expr = expr;
    return PARSE_SUCC(node);
}

ParseResult parser_parse_primary(Parser *p) {
    Token token = parser_get_token(p);
    switch (token.type) {
    case TT_STRING:
        return parser_parse_lit_string_expr(p);
    case TT_IDENT:
        return parser_parse_ident_expr(p);
    case TT_INT_NUMBER:
        return parser_parse_lit_number_expr(p);
    default:
        printf("invalid token as primary: `%.*s`\n", SV_Arg(token.lexme));
        return INVALID_RES;
    }
    return INVALID_RES;
}

ParseResult parser_parse_fn_call_expr(Parser *p, Node *lhs) {
    if (!expect(p, TT_OPEN_PAREN)) {
        Token token = parser_get_token(p);
        printf("expected `(` got `%.*s`\n", SV_Arg(token.lexme));
        return INVALID_RES;
    }

    Nodes args = {0};
    while (parser_get_token(p).type != TT_CLOSE_PAREN && !is_eof_or_eot(p)) {
        ParseResult res = parser_parse_expr(p);
        if (!res.ok)
            return INVALID_RES;
        da_append(&args, res.node);
        if (parser_get_token(p).type == TT_COMMA)
            expect(p, TT_COMMA);
    }

    Token end;
    if (!expect_and_get(p, TT_CLOSE_PAREN, &end)) {
        printf("expected `(` got `%.*s`\n", SV_Arg(end.lexme));
        return INVALID_RES;
    }

    Node *node = temp_alloc(sizeof(Node));
    node->type = NT_FN_CALL_EXPR;
    node->start = lhs->start;
    node->end = end.loc;
    FnCallExpr *expr = temp_alloc(sizeof(FnCallExpr));
    expr->base = node;
    assert(lhs->type == NT_IDENT_EXPR);
    expr->name = lhs->ident_expr->lit;
    expr->args = args;
    node->fn_call_expr = expr;
    return PARSE_SUCC(node);
}

int parser_get_precedence(TokenType tt) {
    switch (tt) {
    case TT_ASTERISK:
        return 20;
    case TT_PLUS:
        return 10;
    case TT_LT:
        return 5;
    case TT_EQ:
    case TT_PLUSEQ:
        return 2;
    default:
        return 0;
    }
    return 0;
}

ParseResult parser_try_parse_rhs(Parser *p, Node *lhs, int operand_precedence) {
    Token token = parser_get_token(p);
    if (token.type != TT_PLUS && token.type != TT_ASTERISK && token.type != TT_LT && token.type != TT_EQ && token.type != TT_PLUSEQ)
        return PARSE_SUCC(lhs);

    while (true) {
        int precedence = parser_get_precedence(token.type);
        if (precedence < operand_precedence)
            return PARSE_SUCC(lhs);

        Token operand = token;
        if (!parser_advance(p)) {
            printf("Reached end of file\n");
            return INVALID_RES;
        }

        ParseResult rhs = parser_parse_expr_with_precedence(p, precedence);
        if (!rhs.ok) {
            return INVALID_RES;
        }
        int new_precedence = parser_get_precedence(token.type);
        if (new_precedence > precedence) {
            ParseResult newlhs = parser_try_parse_rhs(p, rhs.node, new_precedence);
            if (!newlhs.ok) {
                return INVALID_RES;
            }
            lhs = newlhs.node;
        }

        Node *node = temp_alloc(sizeof(Node));
        node->type = NT_BIN_EXPR;
        node->start = lhs->start;
        node->end = rhs.node->end;
        BinExpr *bin = temp_alloc(sizeof(BinExpr));
        bin->base = node;
        bin->lhs = lhs;
        bin->operand = operand;
        bin->rhs = rhs.node;
        node->bin_expr = bin;
        return PARSE_SUCC(node);
    }
}

ParseResult parser_parse_expr_with_precedence(Parser *p, int precedence) {

    ParseResult res = parser_parse_primary(p);
    if (!res.ok) {
        return INVALID_RES;
    }

    Node *lhs = res.node;

    Token token = parser_get_token(p);
    switch (token.type) {
    case TT_OPEN_PAREN: {
        res = parser_parse_fn_call_expr(p, lhs);
        if (!res.ok)
            return INVALID_RES;
        lhs = res.node;
    } break;
    default:
        break;
    }

    return parser_try_parse_rhs(p, lhs, precedence);
}

ParseResult parser_parse_expr(Parser *p) {
    return parser_parse_expr_with_precedence(p, 0);
}

ParseResult parser_parse_expr_stmt(Parser *p) {
    ParseResult res = parser_parse_expr(p);
    if (!res.ok)
        return INVALID_RES;

    Token end;
    if (!expect_and_get(p, TT_SEMICOLON, &end)) {
        printf("expected `;` but got `%.*s`\n", SV_Arg(end.lexme));
        return INVALID_RES;
    }

    Node *node = temp_alloc(sizeof(Node));
    node->type = NT_EXPR_STMT;
    node->start = res.node->start;
    node->end = end.loc;
    ExprStmt *stmt = temp_alloc(sizeof(ExprStmt));
    stmt->base = node;
    stmt->expr = res.node;
    node->expr_stmt = stmt;
    return PARSE_SUCC(node);
}

ParseResult parser_parse_var_decl_stmt(Parser *p) {
    ParseResult type = parser_parse_type_expr(p);
    if (!type.ok) {
        return INVALID_RES;
    }

    Token name;
    if (!expect_and_get(p, TT_IDENT, &name)) {
        printf("expected identifier after the variable type, but got `%.*s`.\n", SV_Arg(name.lexme));
        return INVALID_RES;
    }

    if (!expect(p, TT_EQ)) {
        printf("expect `=` after variable name\n");
        return INVALID_RES;
    }

    ParseResult decl = parser_parse_expr(p);
    if (!decl.ok) {
        return INVALID_RES;
    }

    Token end;
    if (!expect_and_get(p, TT_SEMICOLON, &end)) {
        printf("expected `;` at the end of a variable declaration, but got `%.*s`\n", SV_Arg(end.lexme));
        return INVALID_RES;
    }

    Node *node = temp_alloc(sizeof(Node));
    node->type = NT_VAR_DECL_STMT;
    node->start = type.node->start;
    node->end = end.loc;
    VarDeclStmt *stmt = temp_alloc(sizeof(VarDeclStmt));
    stmt->base = node;
    stmt->type = type.node;
    stmt->name = name.lexme;
    stmt->decl = decl.node;
    node->var_decl_stmt = stmt;

    return PARSE_SUCC(node);
}

ParseResult parser_parse_if_stmt(Parser *p) {
    Token start;
    if (!expect_and_get(p, TT_IDENT, &start)) {
        printf("expected `if` keyword.\n");
        return INVALID_RES;
    }

    ParseResult condition = parser_parse_expr(p);
    if (!condition.ok) {
        printf("Failed to parse condition of `if` statment\n");
        return INVALID_RES;
    }

    ParseResult block = parser_parse_stmt(p);
    if (!block.ok) {
        printf("failed to parse `if` block\n");
        return INVALID_RES;
    }

    ParseResult _else = INVALID_RES;

    Token token = parser_get_token(p);
    if (token.type == TT_IDENT && sv_eq(token.lexme, sv_from_cstr("else"))) {
        expect(p, TT_IDENT);
        _else = parser_parse_stmt(p);
        if (!_else.ok) {
            return INVALID_RES;
        }
    }

    Node *node = temp_alloc(sizeof(Node));
    node->type = NT_IF_STMT;
    node->start = start.loc;
    node->end = _else.ok ? _else.node->end : block.node->end;
    IfStmt *stmt = temp_alloc(sizeof(IfStmt));
    stmt->base = node;
    stmt->condition = condition.node;
    stmt->block = block.node;
    stmt->_else = _else.node;
    node->if_stmt = stmt;
    return PARSE_SUCC(node);
}

ParseResult parser_parse_while_stmt(Parser *p) {
    Token start;
    if (!expect_and_get(p, TT_IDENT, &start)) {
        printf("failed to parse while begin.\n");
        return INVALID_RES;
    }

    if (!expect(p, TT_OPEN_PAREN)) {
        printf("expected `(` after `while keyword.\n");
        return INVALID_RES;
    }

    ParseResult cond = parser_parse_expr(p);
    if (!cond.ok) {
        return INVALID_RES;
    }

    if (!expect(p, TT_CLOSE_PAREN)) {
        printf("expected `)` after condition expression.\n");
        return INVALID_RES;
    }

    ParseResult body = parser_parse_stmt(p);
    if (!body.ok) {
        return INVALID_RES;
    }

    Node *node = temp_alloc(sizeof(Node));
    node->type = NT_WHILE_STMT;
    node->start = start.loc;
    node->end = body.node->end;
    WhileStmt *stmt = temp_alloc(sizeof(WhileStmt));
    stmt->base = node;
    stmt->condition = cond.node;
    stmt->body = body.node;
    node->while_stmt = stmt;
    return PARSE_SUCC(node);
}

ParseResult parser_parse_for_loop_stmt(Parser *p) {
    Token start;
    if (!expect_and_get(p, TT_IDENT, &start)) {
        printf("failed to parse for begin.\n");
        return INVALID_RES;
    }

    if (!expect(p, TT_OPEN_PAREN)) {
        printf("expected `(` after `for` keyword.\n");
        return INVALID_RES;
    }

    ParseResult init_clause = INVALID_RES;
    if (parser_get_token(p).type != TT_SEMICOLON) {
        init_clause = parser_parse_expr(p);
        if (!init_clause.ok)
            return INVALID_RES;
    }

    if (!expect(p, TT_SEMICOLON)) {
        printf("Expected `;` after init clause.\n");
        return INVALID_RES;
    }

    ParseResult cond_expr = INVALID_RES;
    if (parser_get_token(p).type != TT_SEMICOLON) {
        cond_expr = parser_parse_expr(p);
        if (!cond_expr.ok)
            return INVALID_RES;
    }

    if (!expect(p, TT_SEMICOLON)) {
        printf("expect `;` after condition expression.\n");
        return INVALID_RES;
    }

    ParseResult iter_expr = INVALID_RES;
    if (parser_get_token(p).type != TT_CLOSE_PAREN) {
        iter_expr = parser_parse_expr(p);
        if (!iter_expr.ok)
            return INVALID_RES;
    }

    if (!expect(p, TT_CLOSE_PAREN)) {
        printf("expect ')' after iteration expression.\n");
        return INVALID_RES;
    }

    ParseResult body = parser_parse_stmt(p);
    if (!body.ok)
        return INVALID_RES;

    Node *node = temp_alloc(sizeof(Node));
    node->type = NT_FOR_LOOP_STMT;
    node->start = start.loc;
    node->end = body.node->end;
    ForLoopStmt *stmt = temp_alloc(sizeof(ForLoopStmt));
    stmt->base = node;
    stmt->init_clause = init_clause.node;
    stmt->cond_expression = cond_expr.node;
    stmt->iteration_expression = iter_expr.node;
    stmt->body = body.node;
    node->for_loop_stmt = stmt;

    return PARSE_SUCC(node);
}

ParseResult parser_parse_break_stmt(Parser *p) {
    Token start;
    if (!expect_and_get(p, TT_IDENT, &start)) {
        return INVALID_RES;
    }

    ParseResult label = INVALID_RES;
    if (parser_get_token(p).type != TT_SEMICOLON) {
        label = parser_parse_expr(p);
        if (!label.ok) {
            return INVALID_RES;
        }
    }

    Token end;
    if (!expect_and_get(p, TT_SEMICOLON, &end)) {
        printf("expected `;` at the end of a break statment.\n");
        return INVALID_RES;
    }

    Node *node = temp_alloc(sizeof(Node));
    node->type = NT_BREAK_STMT;
    node->start = start.loc;
    node->end = end.loc;
    BreakStmt *stmt = temp_alloc(sizeof(BreakStmt));
    stmt->base = node;
    stmt->label = label.node;
    node->break_stmt = stmt;
    return PARSE_SUCC(node);
}

ParseResult parser_parse_stmt(Parser *p) {
    Token token = parser_get_token(p);
    switch (token.type) {
    case TT_OPEN_CURLY: {
        return parser_parse_block_stmt(p);
    } break;
    default: {
        Token peek;
        if (!parser_get_token_off(p, 2, &peek)) {
            printf("Couldn't peek that far.\n");
            return INVALID_RES;
        }
        if (peek.type == TT_EQ) {
            return parser_parse_var_decl_stmt(p);
        } else if (sv_eq(token.lexme, sv_from_cstr("if"))) {
            return parser_parse_if_stmt(p);
        } else if (sv_eq(token.lexme, sv_from_cstr("while"))) {
            return parser_parse_while_stmt(p);
        } else if (sv_eq(token.lexme, sv_from_cstr("for"))) {
            return parser_parse_for_loop_stmt(p);
        } else if (sv_eq(token.lexme, sv_from_cstr("break"))) {
            return parser_parse_break_stmt(p);
        } else {
            return parser_parse_expr_stmt(p);
        }
    }
    }

    return INVALID_RES;
}

ParseResult parser_parse_fn_decl_stmt(Parser *p) {

    ParseResult type_res = parser_parse_type_expr(p);
    if (!type_res.ok)
        return INVALID_RES;

    Token name;
    if (!expect_and_get(p, TT_IDENT, &name)) {
        printf("Failed to parse name of function declaration.\n");
        return INVALID_RES;
    }

    if (!expect(p, TT_OPEN_PAREN)) {
        printf("Expected `(` after function name.\n");
        return INVALID_RES;
    }

    FnParams params = {0};
    while (!is_eof_or_eot(p) && parser_get_token(p).type != TT_CLOSE_PAREN) {
        ParseResult type_expr = parser_parse_type_expr(p);
        if (!type_expr.ok)
            return INVALID_RES;
        Token name;
        if (!expect_and_get(p, TT_IDENT, &name)) {
            printf("expected name after type parameter.\n");
            return INVALID_RES;
        }
        FnParam param = {
            .name = name.lexme,
            .type = type_expr.node,
        };
        da_append(&params, param);
        if (parser_get_token(p).type == TT_COMMA)
            expect(p, TT_COMMA);
    }

    if (!expect(p, TT_CLOSE_PAREN)) {
        printf("Expected `(` after function name.\n");
        return INVALID_RES;
    }

    ParseResult block_res = parser_parse_stmt(p);
    if (!block_res.ok) {
        printf("Failed to parse function body.\n");
        return INVALID_RES;
    }

    Node *node = temp_alloc(sizeof(Node));
    node->type = NT_FN_DECL;
    node->start = type_res.node->start;
    node->end = block_res.node->end;
    FnDeclStmt *fn = temp_alloc(sizeof(FnDeclStmt));
    fn->base = node;
    fn->typename = type_res.node;
    fn->name = name.lexme;
    fn->block = block_res.node;
    fn->parameters = params;
    node->fn_decl_stmt = fn;
    return PARSE_SUCC(node);
}

ParseResult parser_parse_top_level_stmt(Parser *p) {
    Token token = parser_get_token(p);
    switch (token.type) {
    case TT_IDENT: {
        Token peek;
        if (!parser_get_token_off(p, 2, &peek)) {
            printf("something went wrong: Reached end of file.\n");
            return INVALID_RES;
        }
        if (peek.type == TT_OPEN_PAREN) {
            return parser_parse_fn_decl_stmt(p);
        } else {
            printf("Invalid token: %.*s\n", SV_Arg(token.lexme));
            return INVALID_RES;
        }
    } break;
    default:
        printf("Invalid top level token\n");
        return INVALID_RES;
    }

    return INVALID_RES;
}

bool parser_parse(Parser *p) {
    while (!is_eof_or_eot(p)) {
        ParseResult res = parser_parse_top_level_stmt(p);
        if (!res.ok)
            return false;
        da_append(&p->nodes, res.node);
    }
    return true;
}