path: root/src/bootstrap/main.c

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

#include "shorthand.h"


// FIXME: We are not worried right now about freeing memory, but we should in
// the future.

typedef struct StringView {
    char *start;
    size_t n;
} StringView;

void
sv_write(StringView sv) {
    for (size_t i = 0; i < sv.n; i++) {
        putchar(sv.start[i]);
    }
}

bool
sv_equal(StringView a, StringView b) {
    if (a.n == b.n) {
        for (size_t i = 0; i < a.n; i++) {
            if (a.start[i] != b.start[i]) {
                return false;
            }
        }
        return true;
    }
    return false;
}

StringView
read_line(void) {
    #define RL_BUF_SIZE 1024
    static char readline_buf[RL_BUF_SIZE];

    // Clear buffer.
    for (size_t i = 0; i < RL_BUF_SIZE; i++) {
        readline_buf[i] = 0;
    }

    // Barebones readline implementation.
    size_t n = 0;
    char c;
    while ((c = getchar()) != '\n') {
        if (c == '\b') {
            readline_buf[n] = '\0';
            n--;
        } else if (((u8)c >= 0x20 && (u8)c <= 0x7F) && n < RL_BUF_SIZE) {
            readline_buf[n] = c;
            n++;
        }
    }

    return (StringView){.start = (char *)&readline_buf, .n = n};
}

typedef struct Tokens {
    StringView *start;
    size_t n;
} Tokens;

Tokens
tokenize(StringView sv) {
    // NOTE: Not allocating any memory for now, but we are limited by a maximum
    // number of tokens we can process.
    #define TOKENS_BUF_SIZE 1024
    static StringView tokens_buf[TOKENS_BUF_SIZE];

    // Clear buffer.
    for (size_t i = 0; i < TOKENS_BUF_SIZE; i++) {
        tokens_buf[i] = (StringView){0};
    }

    size_t n = 0;
    size_t token_n = 0;
    for (size_t i = 0; i < sv.n; i++) {
        switch (sv.start[i]) {
            case ' ':
            case '\f':
            case '\n':
            case '\r':
            case '\t':
            case '\v': {
                if (token_n != 0) {
                    // Push token.
                    tokens_buf[n++] = (StringView){
                        .start = &sv.start[i - token_n],
                        .n = token_n,
                    };
                    token_n = 0;
                }
                continue;
            } break;
            case '"': {
                if (token_n != 0) {
                    fprintf(stderr, "error: string started inside symbol\n");
                    return (Tokens){0};
                }

                // Find end delimiter.
                size_t string_start = i + 1;
                size_t string_end = i + 1;
                while (true) {
                    if (sv.start[string_end] == '"' && sv.start[string_end - 1] != '\\') {
                        break;
                    }
                    if (string_end >= sv.n) {
                        fprintf(stderr, "error: string delimiter not found\n");
                        return (Tokens){0};
                    }
                    string_end++;
                }

                // Push string token.
                tokens_buf[n++] = (StringView){
                    .start = &sv.start[string_start - 1],
                    .n = 1,
                };
                tokens_buf[n++] = (StringView){
                    .start = &sv.start[string_start],
                    .n = string_end - string_start,
                };
                tokens_buf[n++] = (StringView){
                    .start = &sv.start[string_end],
                    .n = 1,
                };
                token_n = 0;
                i += string_end - string_start + 1;
            } break;
            case '(': {
                if ((i + 1) < sv.n) {
                    char next_c = sv.start[i + 1];
                    if (isspace(next_c)) {
                        fprintf(stderr, "error: lparen delimiter followed by space\n");
                        return (Tokens){0};
                    }
                }

                if (token_n != 0) {
                    fprintf(stderr, "error: lparen delimiter within symbol name\n");
                    return (Tokens){0};
                }
                // Push paren token.
                tokens_buf[n++] = (StringView){
                    .start = &sv.start[i],
                    .n = 1,
                };
            } break;
            case ')': {
                if ((i + 1) < sv.n) {
                    char next_c = sv.start[i + 1];
                    if ((next_c != ')' && !isspace(next_c))) {
                        fprintf(stderr, "error: rparen delimiter within symbol name\n");
                        return (Tokens){0};
                    }
                }

                if (token_n != 0) {
                    // Push previous token.
                    tokens_buf[n++] = (StringView){
                        .start = &sv.start[i - token_n],
                        .n = token_n,
                    };
                    token_n = 0;
                }

                // Push paren token.
                tokens_buf[n++] = (StringView){
                    .start = &sv.start[i],
                    .n = 1,
                };
            } break;
            // TODO: Handle double quotes and escaped quotes.
            default: {
                token_n++;
            } break;
        }
    }
    if (token_n != 0) {
        // End of line encountered.
        tokens_buf[n++] = (StringView){
            .start = &sv.start[sv.n - token_n],
            .n = token_n,
        };
    }

    return (Tokens){.start = (StringView *)&tokens_buf, .n = n};
}

StringView *
consume_token(Tokens *tokens) {
    if (tokens->n == 0) {
        return NULL;
    }
    StringView *ret = tokens->start;
    tokens->start = &tokens->start[1];
    tokens->n--;
    return ret;
}

typedef enum ObjectType {
    OBJ_TYPE_FIXNUM,
    OBJ_TYPE_BOOL,
    OBJ_TYPE_NIL,
    OBJ_TYPE_SYMBOL,
    OBJ_TYPE_STRING,
    OBJ_TYPE_PAIR,
    OBJ_TYPE_PROCEDURE,
} ObjectType;

typedef struct Object {
    ObjectType type;
    union {
        // OBJ_TYPE_FIXNUM
        ssize_t fixnum;

        // OBJ_TYPE_BOOL
        bool boolean;

        // OBJ_TYPE_STRING
        struct {
            char *string;
            size_t string_n;
        };

        // OBJ_TYPE_PAIR
        struct {
            struct Object *car;
            struct Object *cdr;
        };

        // OBJ_TYPE_SYMBOL
        struct {
            char *symbol;
            size_t symbol_n;
        };

        // OBJ_TYPE_PROCEDURE
        struct Object *(*proc)(struct Object *args);
    };
} Object;

//
// Singletons.
//

Object *empty_list;

//
// Environment.
//

typedef struct EnvSymbol {
    Object *symbol;
    Object *value;
} EnvSymbol;

#define ENV_SIZE 256
static EnvSymbol environment[ENV_SIZE];
static size_t env_n = 0;

Object *
make_fixnum(ssize_t num) {
    Object *obj = malloc(sizeof(Object));
    obj->type = OBJ_TYPE_FIXNUM;
    obj->fixnum = num;
    return obj;
}

Object *
make_boolean(bool b) {
    Object *obj = malloc(sizeof(Object));
    obj->type = OBJ_TYPE_BOOL;
    obj->boolean = b;
    return obj;
}

Object *
make_empty_string(void) {
    Object *obj = malloc(sizeof(Object));
    obj->type = OBJ_TYPE_STRING;
    obj->string = NULL;
    obj->string_n = 0;
    return obj;
}

void
append_string(Object *string, StringView sv) {
    assert(string != NULL);
    assert(string->type == OBJ_TYPE_STRING);

    if (sv.n == 0) {
        return;
    }

    string->string = realloc(string->string, (string->string_n + sv.n) * sizeof(char));
    memcpy(string->string + string->string_n, sv.start, sv.n);
    string->string_n += sv.n;
}

Object *
make_symbol(const char *str, size_t n) {
    Object *obj = malloc(sizeof(Object));
    obj->type = OBJ_TYPE_SYMBOL;
    obj->string = malloc(sizeof(char) * n);
    memcpy(obj->string, str, n);
    obj->string_n = n;
    return obj;
}

Object *
make_empty_list(void) {
    Object *obj = malloc(sizeof(Object));
    obj->type = OBJ_TYPE_NIL;
    return obj;
}

Object *
make_procedure(Object *(*proc)(struct Object *args)) {
    Object *obj = malloc(sizeof(Object));
    obj->type = OBJ_TYPE_PROCEDURE;
    obj->proc = proc;
    return obj;
}

Object *
cons(Object *car, Object *cdr) {
    Object *obj = malloc(sizeof(Object));
    obj->type = OBJ_TYPE_PAIR;
    obj->car = car;
    obj->cdr = cdr;
    return  obj;
}

bool
token_is_fixnum(StringView token) {
    for (size_t i = 0; i < token.n; i++) {
        char c = token.start[i];
        if (i == 0 && c == '-' && token.n > 1) {
            continue;
        }
        if (!isdigit(c)) {
            return false;
        }
    }
    return true;
}

#define TRUE_TOKEN  (StringView){"true", 4}
#define FALSE_TOKEN (StringView){"false", 5}

Object *
build_ast(Tokens *tokens) {
    // DEBUG: Printing tokens.
    // printf("N_TOKENS: %ld\n", tokens->n);
    // for (size_t i = 0; i < tokens->n; i++) {
    //     printf("TOKEN: ");
    //     sv_write(tokens->start[i]);
    //     printf("\tN: %ld", tokens->start[i].n);
    //     printf("\n");
    // }

    // TODO: Report error if we haven't consumed all the tokens?
    while (tokens->n > 0) {
        StringView *token = consume_token(tokens);
        if (token == NULL) {
            return NULL;
        }

        // OBJ_TYPE_FIXNUM
        if (token_is_fixnum(*token)) {
            // Convert token to fixnum.
            ssize_t num = 0;
            int sign = 1;
            for (size_t i = 0; i < token->n; i++) {
                char c = token->start[i];
                if (c == '-') {
                    sign = -1;
                    continue;
                }
                num = num * 10 + (c - '0');
            }
            return make_fixnum(num * sign);
        }

        // OBJ_TYPE_BOOL
        if (sv_equal(*token, TRUE_TOKEN)) {
            return make_boolean(true);
        }
        if (sv_equal(*token, FALSE_TOKEN)) {
            return make_boolean(false);
        }

        // OBJ_TYPE_LIST
        if (token->start[0] == ')') {
            return NULL;
        }
        if (token->start[0] == '(') {
            if (tokens->n > 0 && tokens->start[0].start[0] == ')') {
                return empty_list;
            }

            Object *next_obj = build_ast(tokens);
            if (next_obj == NULL) {
                return NULL;
            }
            Object *root = cons(next_obj, empty_list);
            Object *list = root;
            while (tokens->n > 0 && (next_obj = build_ast(tokens)) != NULL) {
                list->cdr = cons(next_obj, empty_list);
                list = list->cdr;
            }
            return root;
        }

        // OBJ_TYPE_STRING
        if (token->start[0] == '"') {
            Object *obj = make_empty_string();
            token = consume_token(tokens);
            append_string(obj, *token);
            consume_token(tokens);
            return obj;
        }

        // OBJ_TYPE_SYMBOL
        return make_symbol(token->start, token->n);
    }

    return NULL;
}

void display(Object *root);

void
display_pair(Object *root) {
    display(root->car);
    if (root->cdr->type == OBJ_TYPE_PAIR) {
        printf(" ");
        display_pair(root->cdr);
    } else if (root->cdr->type == OBJ_TYPE_NIL) {
        return;
    } else {
        printf(" . ");
        display(root->cdr);
    }
}

void
display(Object *root) {
    if (root == NULL) {
        return;
    }

    switch (root->type) {
        case OBJ_TYPE_FIXNUM: {
            printf("%zd", root->fixnum);
        } break;
        case OBJ_TYPE_BOOL: {
            if (root->boolean) {
                printf("true");
            } else {
                printf("false");
            }
        } break;
        case OBJ_TYPE_NIL: {
            printf("()");
        } break;
        case OBJ_TYPE_STRING: {
            printf("\"%.*s\"", (int)root->string_n, root->string);
        } break;
        case OBJ_TYPE_SYMBOL: {
            printf(":%.*s", (int)root->symbol_n, root->symbol);
        } break;
        case OBJ_TYPE_PAIR: {
            printf("(");
            display_pair(root);
            printf(")");
        } break;
        default: {
            printf("TYPE NOT IMPLEMENTED FOR DISPLAY.");
        } break;
    }
}

#define REPL_PROMPT "bdl> "

Object * eval(Object *root);

Object *
proc_add(Object *args) {
    ssize_t tot = 0;
    while (args->type == OBJ_TYPE_PAIR) {
        Object *car = eval(args->car);
        if (car->type != OBJ_TYPE_FIXNUM) {
            fprintf(stderr, "addition not supported for type %d\n", car->type);
            return NULL;
        }
        tot += car->fixnum;
        args = args->cdr;
    }
    return make_fixnum(tot);
}

Object *
proc_sub(Object *args) {
    if (args->type != OBJ_TYPE_PAIR) {
        fprintf(stderr, "substraction not supported for type %d\n", args->type);
        return NULL;
    }

    // Extract first parameter.
    Object *car = eval(args->car);
    args = args->cdr;
    ssize_t tot = car->fixnum;

    while (args->type == OBJ_TYPE_PAIR) {
        Object *car = eval(args->car);
        if (car->type != OBJ_TYPE_FIXNUM) {
            fprintf(stderr, "substraction not supported for type %d\n", car->type);
            return NULL;
        }
        tot -= car->fixnum;
        args = args->cdr;
    }
    return make_fixnum(tot);
}

Object *
proc_mul(Object *args) {
    ssize_t tot = 1;
    while (args->type == OBJ_TYPE_PAIR) {
        Object *car = eval(args->car);
        if (car->type != OBJ_TYPE_FIXNUM) {
            fprintf(stderr, "multiply not supported for type %d\n", car->type);
            return NULL;
        }
        tot *= car->fixnum;
        args = args->cdr;
    }
    return make_fixnum(tot);
}

Object *
proc_div(Object *args) {
    if (args->type != OBJ_TYPE_PAIR) {
        fprintf(stderr, "substraction not supported for type %d\n", args->type);
        return NULL;
    }

    // Extract first parameter.
    Object *car = eval(args->car);
    args = args->cdr;
    ssize_t tot = car->fixnum;

    while (args->type == OBJ_TYPE_PAIR) {
        Object *car = eval(args->car);
        if (car->type != OBJ_TYPE_FIXNUM) {
            fprintf(stderr, "div not supported for type %d\n", car->type);
            return NULL;
        }
        tot /= car->fixnum;
        args = args->cdr;
    }
    return make_fixnum(tot);
}

bool
symbol_eq(Object *a, Object *b) {
    if (a->type != b->type || a->type != OBJ_TYPE_SYMBOL || a->symbol_n != b->symbol_n) {
        return false;
    }
    for (size_t i = 0; i < a->symbol_n; i++) {
        if (a->symbol[i] != b->symbol[i]) {
            return false;
        }
    }
    return true;
}

Object *
find_environment_symbol(Object *symbol) {
    for (size_t i = 0; i < env_n; i++) {
        if (symbol_eq(environment[i].symbol, symbol)) {
            return environment[i].value;
        }
    }
    return NULL;
}

void
init(void) {
    // Clear env.
    for (size_t i = 0; i < ENV_SIZE; i++) {
        environment[i] = (EnvSymbol){0};
    }

    // Initialize singletons.
    empty_list = make_empty_list();

    // Add primitive functions.
    environment[env_n++] = (EnvSymbol){make_symbol("+", 1), make_procedure(proc_add)};
    environment[env_n++] = (EnvSymbol){make_symbol("-", 1), make_procedure(proc_sub)};
    environment[env_n++] = (EnvSymbol){make_symbol("*", 1), make_procedure(proc_mul)};
    environment[env_n++] = (EnvSymbol){make_symbol("/", 1), make_procedure(proc_div)};
}

Object *
eval(Object *root) {
    if (root == NULL) {
        return NULL;
    }

    switch (root->type) {
        case OBJ_TYPE_FIXNUM:
        case OBJ_TYPE_BOOL:
        case OBJ_TYPE_NIL:
        case OBJ_TYPE_STRING:
        case OBJ_TYPE_SYMBOL: {
            return root;
        } break;
        case OBJ_TYPE_PAIR: {
            if (root->car->type == OBJ_TYPE_SYMBOL) {
                Object *value = find_environment_symbol(root->car);
                if (value == NULL) {
                    printf("error: symbol not found: `");
                    display(root->car);
                    printf("`\n");
                    return NULL;
                }
                if (value->type == OBJ_TYPE_PROCEDURE) {
                    return value->proc(root->cdr);
                }
            }
        } break;
        default: {
            printf("TYPE NOT IMPLEMENTED FOR EVAL.\n");
        } break;
    }

    return NULL;
}

int
main(void) {
    init();
    printf("BDL REPL (Press Ctrl-C to exit)\n");
    while (true) {
        printf(REPL_PROMPT);
        StringView line = read_line();
        Tokens tokens = tokenize(line);
        Object *ast = build_ast(&tokens);
        if (ast) {
            display(eval(ast));
            printf("\n");
        }
    }
    return 0;
}