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_LIST,
} 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_LIST
        struct {
            // NOTE: Probably want to do this as a linked list using pairs.
            struct Object **list;
            size_t list_n;
        };

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

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;
    obj->list = NULL;
    obj->list_n = 0;
    return obj;
}

void
push_obj_to_list(Object *list, Object **obj) {
    assert(list != NULL);
    assert(list->type == OBJ_TYPE_NIL || list->type == OBJ_TYPE_LIST);

    if (obj == NULL || *obj == NULL) {
        return;
    }

    if (list->type == OBJ_TYPE_NIL) {
        list->type = OBJ_TYPE_LIST;
    }
    list->list = realloc(list->list, (list->list_n + 1) * sizeof(struct Object *));
    list->list[list->list_n++] = *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 == '-') {
            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 make_empty_list();
            }

            Object *list = make_empty_list();
            Object *next_obj = NULL;
            while (tokens->n > 0 && (next_obj = build_ast(tokens)) != NULL) {
                push_obj_to_list(list, &next_obj);
            }
            return list;
        }

        // 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) {
    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_LIST: {
            printf("(");
            for (size_t i = 0; i < root->list_n; i++) {
                display(root->list[i]);
                if ((i + 1) < root->list_n) {
                    printf(" ");
                }
            }
            printf(")");
        } break;
        default: {
            printf("TYPE NOT IMPLEMENTED FOR DISPLAY.");
        } break;
    }
}

#define REPL_PROMPT "bdl> "

int
main(void) {
    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(ast);
            printf("\n");
        }
    }
    return 0;
}