#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "ast.h"

Expr* expr_new_int(long long val) {
    Expr *e = calloc(1, sizeof(Expr));
    e->type = EXPR_INT;
    e->int_val = val;
    return e;
}

Expr* expr_new_var(const char *name) {
    Expr *e = calloc(1, sizeof(Expr));
    e->type = EXPR_VAR;
    e->var_name = strdup(name);
    return e;
}

Expr* expr_new_binop(int op, Expr *left, Expr *right) {
    Expr *e = calloc(1, sizeof(Expr));
    e->type = EXPR_BINOP;
    e->op = op;
    e->left = left;
    e->right = right;
    return e;
}

void expr_free(Expr *e) {
    if (!e) return;
    if (e->type == EXPR_VAR) free(e->var_name);
    if (e->type == EXPR_BINOP) {
        expr_free(e->left);
        expr_free(e->right);
    }
    free(e);
}

Word* word_new_literal(const char *text) {
    Word *w = calloc(1, sizeof(Word));
    w->type = WORD_LITERAL;
    w->text = strdup(text);
    return w;
}

Word* word_new_var(const char *name) {
    Word *w = calloc(1, sizeof(Word));
    w->type = WORD_VAR;
    w->text = strdup(name);
    return w;
}

void word_free(Word *w) {
    if (!w) return;
    free(w->text);
    free(w);
}

Test* test_new_file(int op, const char *path) {
    Test *t = calloc(1, sizeof(Test));
    t->type = TEST_FILE;
    t->op = op;
    t->file_path = strdup(path);
    return t;
}

Test* test_new_num(int op, Expr *left, Expr *right) {
    Test *t = calloc(1, sizeof(Test));
    t->type = TEST_NUM;
    t->op = op;
    t->num_left = left;
    t->num_right = right;
    return t;
}

Test* test_new_str(int op, Word *left, Word *right) {
    Test *t = calloc(1, sizeof(Test));
    t->type = TEST_STR;
    t->op = op;
    t->str_left = left;
    t->str_right = right;
    return t;
}

void test_free(Test *t) {
    if (!t) return;
    if (t->type == TEST_FILE) free(t->file_path);
    if (t->type == TEST_NUM) {
        expr_free(t->num_left);
        expr_free(t->num_right);
    }
    if (t->type == TEST_STR) {
        word_free(t->str_left);
        word_free(t->str_right);
    }
    free(t);
}

Stmt* stmt_new(StmtType type) {
    Stmt *s = calloc(1, sizeof(Stmt));
    s->type = type;
    return s;
}

void ast_free(Stmt *stmt) {
    while (stmt) {
        Stmt *next = stmt->next;
        if (stmt->var_name) free(stmt->var_name);
        if (stmt->arith_val) expr_free(stmt->arith_val);
        if (stmt->str_val) free(stmt->str_val);
        if (stmt->echo_args) {
            for (int i = 0; i < stmt->echo_argc; i++) word_free(stmt->echo_args[i]);
            free(stmt->echo_args);
        }
        if (stmt->cond) test_free(stmt->cond);
        if (stmt->then_body) ast_free(stmt->then_body);
        if (stmt->else_body) ast_free(stmt->else_body);
        if (stmt->for_var) free(stmt->for_var);
        if (stmt->for_list) {
            for (int i = 0; i < stmt->for_list_count; i++) free(stmt->for_list[i]);
            free(stmt->for_list);
        }
        if (stmt->body) ast_free(stmt->body);
        if (stmt->exec_argv) {
            for (int i = 0; i < stmt->exec_argc; i++) free(stmt->exec_argv[i]);
            free(stmt->exec_argv);
        }
        if (stmt->exit_expr) expr_free(stmt->exit_expr);
        free(stmt);
        stmt = next;
    }
}

/* ==================== Tokenizer ==================== */

typedef enum {
    TOK_WORD,
    TOK_SEMI,
    TOK_NEWLINE,
    TOK_EOF,
} TokType;

typedef struct {
    TokType type;
    char *text;
    int is_var;
    int is_arith;
} Token;

typedef struct {
    Token *tokens;
    int count;
    int capacity;
    int pos;
} TokenList;

static void tok_add(TokenList *tl, TokType type, const char *text, int is_var, int is_arith) {
    if (tl->count >= tl->capacity) {
        tl->capacity = tl->capacity ? tl->capacity * 2 : 16;
        tl->tokens = realloc(tl->tokens, tl->capacity * sizeof(Token));
    }
    Token *t = &tl->tokens[tl->count++];
    t->type = type;
    t->text = text ? strdup(text) : NULL;
    t->is_var = is_var;
    t->is_arith = is_arith;
}

static int is_word_char(char c) {
    return c && !isspace((unsigned char)c) && c != ';' && c != '"' && c != '\'' && c != '$' && c != '[' && c != ']' && c != '#';
}

static TokenList* tokenize(const char *source) {
    TokenList *tl = calloc(1, sizeof(TokenList));
    const char *p = source;
    while (*p) {
        if (*p == ' ' || *p == '\t') { p++; continue; }
        if (*p == '\n') { tok_add(tl, TOK_NEWLINE, NULL, 0, 0); p++; continue; }
        if (*p == ';') { tok_add(tl, TOK_SEMI, NULL, 0, 0); p++; continue; }
        if (*p == '#') { while (*p && *p != '\n') p++; continue; }
        if (*p == '"') {
            p++;
            char buf[4096]; int bi = 0;
            while (*p && *p != '"') {
                if (*p == '\\' && p[1]) {
                    char c = p[1];
                    if (c == '"' || c == '\\' || c == '$' || c == '`') { buf[bi++] = c; p += 2; }
                    else { buf[bi++] = *p++; }
                } else {
                    buf[bi++] = *p++;
                }
            }
            if (*p == '"') p++;
            buf[bi] = '\0';
            int is_var = 0;
            if (bi > 0 && buf[0] == '$') {
                int j = 1;
                while (j < bi && (isalnum((unsigned char)buf[j]) || buf[j] == '_')) j++;
                if (j == bi) { is_var = 1; memmove(buf, buf+1, bi); }
            }
            tok_add(tl, TOK_WORD, buf, is_var, 0);
            continue;
        }
        if (*p == '\'') {
            p++;
            char buf[4096]; int bi = 0;
            while (*p && *p != '\'') buf[bi++] = *p++;
            if (*p == '\'') p++;
            buf[bi] = '\0';
            tok_add(tl, TOK_WORD, buf, 0, 0);
            continue;
        }
        if (*p == '$' && p[1] == '(' && p[2] == '(') {
            p += 3;
            char buf[4096]; int bi = 0;
            while (*p && !(*p == ')' && p[1] == ')')) buf[bi++] = *p++;
            if (*p == ')') p += 2;
            buf[bi] = '\0';
            tok_add(tl, TOK_WORD, buf, 0, 1);
            continue;
        }
        if (*p == '$') {
            p++;
            char buf[256]; int bi = 0;
            while (*p && (isalnum((unsigned char)*p) || *p == '_')) buf[bi++] = *p++;
            buf[bi] = '\0';
            tok_add(tl, TOK_WORD, buf, 1, 0);
            continue;
        }
        if (*p == '[') {
            tok_add(tl, TOK_WORD, "[", 0, 0);
            p++;
            continue;
        }
        if (*p == ']') {
            tok_add(tl, TOK_WORD, "]", 0, 0);
            p++;
            continue;
        }
        char buf[4096]; int bi = 0;
        while (is_word_char(*p)) buf[bi++] = *p++;
        buf[bi] = '\0';
        if (bi > 0) tok_add(tl, TOK_WORD, buf, 0, 0);
    }
    tok_add(tl, TOK_EOF, NULL, 0, 0);
    return tl;
}

static void tok_free(TokenList *tl) {
    for (int i = 0; i < tl->count; i++) free(tl->tokens[i].text);
    free(tl->tokens);
    free(tl);
}

static Token* tok_peek(TokenList *tl) {
    return &tl->tokens[tl->pos];
}

static Token* tok_next(TokenList *tl) {
    return &tl->tokens[tl->pos++];
}

static void skip_separators(TokenList *tl) {
    while (tok_peek(tl)->type == TOK_SEMI || tok_peek(tl)->type == TOK_NEWLINE)
        tok_next(tl);
}

/* ==================== Arithmetic Parser ==================== */

static Expr* parse_arith_expr(const char *s);

static Expr* parse_arith_primary(const char **p) {
    while (**p == ' ' || **p == '\t') (*p)++;
    if (**p == '(') {
        (*p)++;
        Expr *e = parse_arith_expr(*p);
        while (**p && **p != ')') (*p)++;
        if (**p == ')') (*p)++;
        return e;
    }
    if (**p == '-') {
        (*p)++;
        Expr *e = parse_arith_primary(p);
        return expr_new_binop('-', expr_new_int(0), e);
    }
    if (**p == '$') {
        (*p)++;
        char name[256]; int ni = 0;
        while (**p && (isalnum((unsigned char)**p) || **p == '_')) name[ni++] = *(*p)++;
        name[ni] = '\0';
        return expr_new_var(name);
    }
    if (isalpha((unsigned char)**p) || **p == '_') {
        char name[256]; int ni = 0;
        while (**p && (isalnum((unsigned char)**p) || **p == '_')) name[ni++] = *(*p)++;
        name[ni] = '\0';
        return expr_new_var(name);
    }
    long long val = 0;
    while (**p >= '0' && **p <= '9') { val = val * 10 + (**p - '0'); (*p)++; }
    return expr_new_int(val);
}

static Expr* parse_arith_muldiv(const char **p) {
    Expr *left = parse_arith_primary(p);
    while (1) {
        while (**p == ' ' || **p == '\t') (*p)++;
        if (**p == '*' || **p == '/' || **p == '%') {
            int op = *(*p)++;
            Expr *right = parse_arith_primary(p);
            left = expr_new_binop(op, left, right);
        } else break;
    }
    return left;
}

static Expr* parse_arith_expr(const char *s) {
    const char **p = &s;
    Expr *left = parse_arith_muldiv(p);
    while (1) {
        while (**p == ' ' || **p == '\t') (*p)++;
        if (**p == '+' || **p == '-') {
            int op = *(*p)++;
            Expr *right = parse_arith_muldiv(p);
            left = expr_new_binop(op, left, right);
        } else break;
    }
    return left;
}

/* ==================== Test Parser ==================== */

static int parse_num_op(const char *s) {
    if (strcmp(s, "-eq") == 0) return 'e';
    if (strcmp(s, "-ne") == 0) return 'n';
    if (strcmp(s, "-lt") == 0) return 'l';
    if (strcmp(s, "-le") == 0) return 'L';
    if (strcmp(s, "-gt") == 0) return 'g';
    if (strcmp(s, "-ge") == 0) return 'G';
    return 0;
}

static Word* token_to_word(Token *t) {
    if (t->is_var) return word_new_var(t->text);
    return word_new_literal(t->text);
}

static Test* parse_test(TokenList *tl) {
    skip_separators(tl);
    Token *first = tok_next(tl);
    if (strcmp(first->text, "[") != 0) {
        free(first->text); free(first);
        return NULL;
    }
    skip_separators(tl);
    Token *a = tok_next(tl);
    Test *result = NULL;
    if (a->text && a->text[0] == '-' && strlen(a->text) == 2) {
        int fop = a->text[1];
        skip_separators(tl);
        Token *path = tok_next(tl);
        result = test_new_file(fop, path->text);
    } else {
        skip_separators(tl);
        Token *op = tok_next(tl);
        if (op->text && op->text[0] == '-') {
            int nop = parse_num_op(op->text);
            skip_separators(tl);
            Token *b = tok_next(tl);
            Expr *le = a->is_arith ? parse_arith_expr(a->text)
                      : a->is_var ? expr_new_var(a->text)
                      : expr_new_int(atoll(a->text));
            Expr *re = b->is_arith ? parse_arith_expr(b->text)
                      : b->is_var ? expr_new_var(b->text)
                      : expr_new_int(atoll(b->text));
            result = test_new_num(nop, le, re);
        } else {
            int sop = (op->text && strcmp(op->text, "=") == 0) ? '=' : '!';
            skip_separators(tl);
            Token *b = tok_next(tl);
            result = test_new_str(sop, token_to_word(a), token_to_word(b));
        }
    }
    skip_separators(tl);
    Token *rb = tok_next(tl);
    (void)rb;
    return result;
}

/* ==================== Statement Parser ==================== */

static Stmt* parse_statement(TokenList *tl);
static Stmt* parse_statement_list(TokenList *tl, const char *terminator);

static int is_keyword(Token *t, const char *kw) {
    return t->type == TOK_WORD && !t->is_var && !t->is_arith && strcmp(t->text, kw) == 0;
}

static Stmt* parse_echo(TokenList *tl) {
    Stmt *s = stmt_new(STMT_ECHO);
    Word **args = NULL; int argc = 0;
    while (tok_peek(tl)->type == TOK_WORD) {
        Token *t = tok_next(tl);
        args = realloc(args, (argc + 1) * sizeof(Word*));
        args[argc++] = token_to_word(t);
    }
    s->echo_args = args;
    s->echo_argc = argc;
    return s;
}

static Stmt* parse_assign(TokenList *tl, Token *first) {
    char *eq = strchr(first->text, '=');
    if (!eq) return NULL;
    Stmt *s = stmt_new(STMT_ASSIGN);
    int namelen = (int)(eq - first->text);
    s->var_name = strndup(first->text, namelen);
    char *valtext = eq + 1;
    if (valtext[0] == '\0') {
        if (tok_peek(tl)->type == TOK_WORD) {
            Token *vt = tok_next(tl);
            if (vt->is_arith) s->arith_val = parse_arith_expr(vt->text);
            else if (vt->is_var) {
                s->arith_val = expr_new_var(vt->text);
            } else {
                int allnum = 1;
                const char *p = vt->text;
                if (*p == '-' || *p == '+') p++;
                if (*p == '\0') allnum = 0;
                while (*p) { if (!isdigit((unsigned char)*p)) { allnum = 0; break; } p++; }
                if (allnum) s->arith_val = expr_new_int(atoll(vt->text));
                else s->str_val = strdup(vt->text);
            }
        } else {
            s->str_val = strdup("");
        }
    } else {
        int allnum = 1;
        const char *p = valtext;
        if (*p == '-' || *p == '+') p++;
        if (*p == '\0') allnum = 0;
        while (*p) { if (!isdigit((unsigned char)*p)) { allnum = 0; break; } p++; }
        if (allnum) s->arith_val = expr_new_int(atoll(valtext));
        else s->str_val = strdup(valtext);
    }
    return s;
}

static Stmt* parse_exec(TokenList *tl, Token *first) {
    Stmt *s = stmt_new(STMT_EXEC);
    char **argv = malloc(sizeof(char*));
    argv[0] = strdup(first->text);
    int argc = 1;
    while (tok_peek(tl)->type == TOK_WORD) {
        Token *t = tok_next(tl);
        argv = realloc(argv, (argc + 1) * sizeof(char*));
        argv[argc++] = strdup(t->text);
    }
    s->exec_argv = argv;
    s->exec_argc = argc;
    return s;
}

static Stmt* parse_if(TokenList *tl) {
    Stmt *s = stmt_new(STMT_IF);
    s->cond = parse_test(tl);
    skip_separators(tl);
    if (is_keyword(tok_peek(tl), "then")) tok_next(tl);
    skip_separators(tl);
    s->then_body = parse_statement_list(tl, "fi");
    Stmt **tail = &s->else_body;
    while (1) {
        skip_separators(tl);
        if (is_keyword(tok_peek(tl), "elif")) {
            tok_next(tl);
            Stmt *elif = stmt_new(STMT_IF);
            elif->cond = parse_test(tl);
            skip_separators(tl);
            if (is_keyword(tok_peek(tl), "then")) tok_next(tl);
            skip_separators(tl);
            elif->then_body = parse_statement_list(tl, "fi");
            *tail = elif;
            tail = &elif->else_body;
        } else if (is_keyword(tok_peek(tl), "else")) {
            tok_next(tl);
            skip_separators(tl);
            *tail = parse_statement_list(tl, "fi");
            break;
        } else break;
    }
    skip_separators(tl);
    if (is_keyword(tok_peek(tl), "fi")) tok_next(tl);
    return s;
}

static Stmt* parse_for(TokenList *tl) {
    Stmt *s = stmt_new(STMT_FOR);
    Token *var = tok_next(tl);
    s->for_var = strdup(var->text);
    skip_separators(tl);
    if (is_keyword(tok_peek(tl), "in")) tok_next(tl);
    char **list = NULL; int count = 0;
    while (tok_peek(tl)->type == TOK_WORD && !is_keyword(tok_peek(tl), "do")) {
        Token *t = tok_next(tl);
        list = realloc(list, (count + 1) * sizeof(char*));
        list[count++] = strdup(t->text);
    }
    s->for_list = list;
    s->for_list_count = count;
    skip_separators(tl);
    if (is_keyword(tok_peek(tl), "do")) tok_next(tl);
    skip_separators(tl);
    s->body = parse_statement_list(tl, "done");
    skip_separators(tl);
    if (is_keyword(tok_peek(tl), "done")) tok_next(tl);
    return s;
}

static Stmt* parse_while(TokenList *tl) {
    Stmt *s = stmt_new(STMT_WHILE);
    s->cond = parse_test(tl);
    skip_separators(tl);
    if (is_keyword(tok_peek(tl), "do")) tok_next(tl);
    skip_separators(tl);
    s->body = parse_statement_list(tl, "done");
    skip_separators(tl);
    if (is_keyword(tok_peek(tl), "done")) tok_next(tl);
    return s;
}

static Stmt* parse_statement(TokenList *tl) {
    skip_separators(tl);
    Token *t = tok_peek(tl);
    if (t->type == TOK_EOF) return NULL;
    if (t->type != TOK_WORD) { tok_next(tl); return parse_statement(tl); }
    if (is_keyword(t, "echo")) { tok_next(tl); return parse_echo(tl); }
    if (is_keyword(t, "exit")) {
        tok_next(tl);
        Stmt *s = stmt_new(STMT_EXIT);
        if (tok_peek(tl)->type == TOK_WORD) {
            Token *ct = tok_next(tl);
            s->exit_expr = ct->is_arith ? parse_arith_expr(ct->text)
                          : ct->is_var ? expr_new_var(ct->text)
                          : expr_new_int(atoll(ct->text));
        } else {
            s->exit_expr = expr_new_int(0);
        }
        return s;
    }
    if (is_keyword(t, "if")) { tok_next(tl); return parse_if(tl); }
    if (is_keyword(t, "for")) { tok_next(tl); return parse_for(tl); }
    if (is_keyword(t, "while")) { tok_next(tl); return parse_while(tl); }
    if (strchr(t->text, '=') && t->text[0] != '=' && !t->is_var && !t->is_arith) {
        tok_next(tl);
        return parse_assign(tl, t);
    }
    tok_next(tl);
    return parse_exec(tl, t);
}

static Stmt* parse_statement_list(TokenList *tl, const char *terminator) {
    Stmt *head = NULL, **tail = &head;
    while (tok_peek(tl)->type != TOK_EOF) {
        if (terminator && is_keyword(tok_peek(tl), terminator)) break;
        if (terminator && (is_keyword(tok_peek(tl), "elif") || is_keyword(tok_peek(tl), "else"))) break;
        Stmt *s = parse_statement(tl);
        if (s) {
            *tail = s;
            tail = &s->next;
        }
        skip_separators(tl);
    }
    return head;
}

Stmt* ast_parse(const char *source) {
    TokenList *tl = tokenize(source);
    Stmt *ast = parse_statement_list(tl, NULL);
    tok_free(tl);
    return ast;
}
