From 2625019add3d16d3ee5d210bcebdd999d3b0cc32 Mon Sep 17 00:00:00 2001 From: Bad Diode Date: Thu, 21 Oct 2021 18:23:18 +0200 Subject: Change environments to be a hash table --- src/bootstrap/environment.c | 59 ++--- src/bootstrap/environment.h | 7 +- src/bootstrap/gc.c | 12 +- src/bootstrap/hashtable.h | 20 +- src/bootstrap/main.c | 553 ++++++++++++++++++++------------------------ 5 files changed, 280 insertions(+), 371 deletions(-) (limited to 'src/bootstrap') diff --git a/src/bootstrap/environment.c b/src/bootstrap/environment.c index cb9e2f0..dd4a648 100644 --- a/src/bootstrap/environment.c +++ b/src/bootstrap/environment.c @@ -7,8 +7,7 @@ env_create(Environment *parent) { Environment *env = alloc_env(); env->parent = parent; env->marked = false; - env->entries = NULL; - array_init(env->entries, ENV_BUF_CAP); + env->table = ht_init(); return env; } @@ -23,18 +22,15 @@ env_add_symbol(Environment *env, Object *symbol, Object *value) { }); return; } - EnvEntry entry = (EnvEntry){symbol, value}; - array_push(env->entries, entry); + ht_insert(env->table, symbol, value); } Object * env_lookup(Environment *env, Object *symbol) { while (env != NULL) { - for (size_t i = 0; i < array_size(env->entries); i++) { - EnvEntry entry = env->entries[i]; - if (obj_eq(symbol, entry.symbol)) { - return entry.value; - } + Object *obj = ht_lookup(env->table, symbol); + if (obj != NULL) { + return obj; } env = env->parent; } @@ -44,12 +40,10 @@ env_lookup(Environment *env, Object *symbol) { Object * env_update(Environment *env, Object *symbol, Object *value) { while (env != NULL) { - for (size_t i = 0; i < array_size(env->entries); i++) { - EnvEntry entry = env->entries[i]; - if (obj_eq(symbol, entry.symbol)) { - env->entries[i].value = value; - return obj_nil; - } + Object *obj = ht_lookup(env->table, symbol); + if (obj != NULL) { + ht_insert(env->table, symbol, value); + return obj_nil; } env = env->parent; } @@ -60,43 +54,18 @@ env_update(Environment *env, Object *symbol, Object *value) { return obj_err; } -ssize_t -env_index_current(Environment *env, Object *symbol) { - for (size_t i = 0; i < array_size(env->entries); i++) { - EnvEntry entry = env->entries[i]; - if (obj_eq(symbol, entry.symbol)) { - return i; - } - } - return -1; -} - void env_add_or_update_current(Environment *env, Object *symbol, Object *value) { - ssize_t index = env_index_current(env, symbol); - if (index == -1) { - env_add_symbol(env, symbol, value); - } else { - env->entries[index].value = value; - } + ht_insert(env->table, symbol, value); } Environment * env_extend(Environment *parent, Environment *extra) { Environment *env = parent; - for (size_t i = 0; i < array_size(extra->entries); i++) { - EnvEntry entry = extra->entries[i]; - Environment *tmp = env; - bool found = false; - while (tmp != NULL) { - if (env_index_current(tmp, entry.symbol) != -1) { - found = true; - break; - } - tmp = tmp->parent; - } - if (!found) { - env_add_symbol(env, entry.symbol, entry.value); + HashTablePair *pairs = extra->table->pairs; + for (size_t i = 0; i < array_cap(pairs); i++) { + if (pairs[i].key != NULL) { + ht_insert(env->table, pairs[i].key, pairs[i].value); } } return env; diff --git a/src/bootstrap/environment.h b/src/bootstrap/environment.h index 2d6a34e..5ee21ad 100644 --- a/src/bootstrap/environment.h +++ b/src/bootstrap/environment.h @@ -3,14 +3,9 @@ #include "objects.h" -typedef struct EnvEntry { - Object *symbol; - Object *value; -} EnvEntry; - typedef struct Environment { struct Environment *parent; - EnvEntry *entries; + HashTable *table; bool marked; } Environment; diff --git a/src/bootstrap/gc.c b/src/bootstrap/gc.c index a188279..358a07e 100644 --- a/src/bootstrap/gc.c +++ b/src/bootstrap/gc.c @@ -63,10 +63,12 @@ mark_environment(Environment *env) { return; } env->marked = true; - for (size_t i = 0; i < array_size(env->entries); i++) { - EnvEntry *entry = &env->entries[i]; - mark_obj(entry->symbol); - mark_obj(entry->value); + HashTablePair *pairs = env->table->pairs; + for (size_t i = 0; i < array_cap(pairs); i++) { + if (pairs[i].key != NULL) { + mark_obj(pairs[i].key); + mark_obj(pairs[i].value); + } } } @@ -120,7 +122,7 @@ mark_and_sweep(void) { for (size_t i = 0; i < array_cap(gc.envs); i++) { Environment *env = &gc.envs[i]; if (!env->marked) { - array_free(env->entries); + ht_free(env->table); gc.free_envs.offsets[array_head(gc.free_envs.offsets)->size++] = i; } env->marked = false; diff --git a/src/bootstrap/hashtable.h b/src/bootstrap/hashtable.h index ca4ced8..ea24d04 100644 --- a/src/bootstrap/hashtable.h +++ b/src/bootstrap/hashtable.h @@ -35,7 +35,6 @@ _xor_shift_hash(const char *key, size_t n) { uint64_t hash = 0x65d9d65f6a19574f; char *last = (char *)key + n; while (key != last) { - putchar(*key); hash ^= (uint64_t)*key++; hash = (hash << 8) | (hash >> (64 - 8)); } @@ -50,7 +49,7 @@ _fibonacci_hash(uint64_t hash, size_t shift_amount) { uint64_t ht_hash(const HashTable *table, const Object *key) { - uint64_t hash; + uint64_t hash = 0; switch (key->type) { case OBJ_TYPE_FIXNUM: { hash = key->fixnum; @@ -177,23 +176,6 @@ ht_lookup(const HashTable *table, const Object *key) { return pairs[probe_position].value; } -void -ht_debug(HashTable *table) { - HashTablePair *pairs = table->pairs; - for (size_t i = 0; i < array_cap(pairs); i++) { - printf("i: %ld ", i); - if (pairs[i].key == NULL) { - printf("EMPTY\n"); - } else { - printf("key: "); - display(pairs[i].key); - printf(" value: "); - display(pairs[i].value); - printf("\n"); - } - } -} - void ht_free(HashTable *table) { if (table == NULL) { diff --git a/src/bootstrap/main.c b/src/bootstrap/main.c index 1cb7c82..a5888fd 100755 --- a/src/bootstrap/main.c +++ b/src/bootstrap/main.c @@ -21,307 +21,268 @@ #include "read_line.c" #include "string_view.c" -int main(void) { - // Initialize GC. +void +init(void) { + // Initialize garbage collector. gc_init(); - // Initialize key-value objects. - Object *k1 = MAKE_SYM("Alice"); - Object *k2 = MAKE_SYM("Bob"); - Object *k3 = MAKE_SYM("Dog"); - Object *v1 = make_fixnum(10); - Object *v2 = make_fixnum(49); - Object *v3 = make_fixnum(333); - - // Initialize hash table. - HashTable *table = ht_init(); - - // Add some key-value pairs. - ht_insert(table, k1, v1); - ht_insert(table, k2, v2); - ht_insert(table, k3, v3); - - // Test lookups. - Object *alice_val = ht_lookup(table, k1); - Object *bob_val = ht_lookup(table, MAKE_SYM("Bob")); - Object *dog_val = ht_lookup(table, k3); - - if (v1 == alice_val) { - printf("Alice match!\n"); + // Initialize singletons. + obj_nil = alloc_object(OBJ_TYPE_NIL); + obj_true = alloc_object(OBJ_TYPE_BOOL); + obj_false = alloc_object(OBJ_TYPE_BOOL); + obj_err = alloc_object(OBJ_TYPE_ERR); + obj_quote = make_symbol((StringView){"quote", 5}); + proc_if = alloc_object(OBJ_TYPE_ERR); + push_root(obj_nil); + push_root(obj_true); + push_root(obj_false); + push_root(obj_err); + push_root(obj_quote); + push_root(proc_if); + + // Global environment. + global_env = env_create(NULL); + // TODO: make sure we create symbols and strings only once (interning + // strings?) + push_active_env(global_env); + + // Primitive symbols. + MAKE_ENV_VAR(global_env, "else", obj_true); + MAKE_ENV_VAR(global_env, "nil", obj_nil); + MAKE_ENV_VAR(global_env, "if", proc_if); + + // Primitive procedures. + MAKE_ENV_PROC(global_env, "eval", proc_eval); + MAKE_ENV_PROC(global_env, "quote", proc_quote); + MAKE_ENV_PROC(global_env, "car", proc_car); + MAKE_ENV_PROC(global_env, "cdr", proc_cdr); + MAKE_ENV_PROC(global_env, "cons", proc_cons); + MAKE_ENV_PROC(global_env, "list", proc_list); + MAKE_ENV_PROC(global_env, "+", proc_sum); + MAKE_ENV_PROC(global_env, "-", proc_sub); + MAKE_ENV_PROC(global_env, "*", proc_mul); + MAKE_ENV_PROC(global_env, "/", proc_div); + MAKE_ENV_PROC(global_env, "%", proc_mod); + MAKE_ENV_PROC(global_env, "print", proc_print); + MAKE_ENV_PROC(global_env, "display", proc_display); + MAKE_ENV_PROC(global_env, "newline", proc_newline); + MAKE_ENV_PROC(global_env, "boolean?", proc_is_boolean); + MAKE_ENV_PROC(global_env, "nil?", proc_is_nil); + MAKE_ENV_PROC(global_env, "symbol?", proc_is_symbol); + MAKE_ENV_PROC(global_env, "string?", proc_is_string); + MAKE_ENV_PROC(global_env, "fixnum?", proc_is_fixnum); + MAKE_ENV_PROC(global_env, "pair?", proc_is_pair); + MAKE_ENV_PROC(global_env, "procedure?", proc_is_procedure); + MAKE_ENV_PROC(global_env, "error?", proc_is_error); + MAKE_ENV_PROC(global_env, "not", proc_not); + MAKE_ENV_PROC(global_env, "and", proc_and); + MAKE_ENV_PROC(global_env, "or", proc_or); + MAKE_ENV_PROC(global_env, "cond", proc_cond); + MAKE_ENV_PROC(global_env, "<", proc_num_less_than); + MAKE_ENV_PROC(global_env, "<=", proc_num_lesseq_than); + MAKE_ENV_PROC(global_env, ">", proc_num_greater_than); + MAKE_ENV_PROC(global_env, ">=", proc_num_greatereq_than); + MAKE_ENV_PROC(global_env, "=", proc_num_equal); + MAKE_ENV_PROC(global_env, "eq?", proc_equal); + MAKE_ENV_PROC(global_env, "def", proc_define); + MAKE_ENV_PROC(global_env, "set!", proc_set); + MAKE_ENV_PROC(global_env, "lambda", proc_lambda); + MAKE_ENV_PROC(global_env, "fun", proc_fun); + + // Runtime procedures. + MAKE_ENV_PROC(global_env, "supress-errors", proc_supress_errors); +} + +void +process_source(const StringView *source) { + Token *tokens = tokenize(source); + if (errors_n != 0) { + if (tokens != NULL) { + array_free(tokens); + } + return; + } + + Visitor visitor = (Visitor){ + .tokens = tokens, + .current = 0, + }; + while (has_next_token(&visitor) && peek_token(&visitor).type != TOKEN_EOF) { + // Check the root node stack size before parsing + size_t root_stack_size = array_size(gc.roots); + Object *root = parse_tree(&visitor); + array_head(gc.roots)->size = root_stack_size; + if (root == obj_err || errors_n != 0) { + break; + } + push_root(root); + + Object *result = eval(global_env, root); + if (result != obj_nil) { + display(result); + printf("\n"); + } + pop_root(); } - if (v2 == bob_val) { - printf("Bob match!\n"); + + if (tokens != NULL) { + array_free(tokens); + } +} + +#define REPL_PROMPT "bdl> " + +void +run_repl(void) { + printf("BDL REPL (Press Ctrl-D or Ctrl-C to exit)\n"); + while (true) { + printf(REPL_PROMPT); + StringView sv = read_line(); + if (sv.start == NULL) { + return; + } + process_source(&sv); + + // Check if there were any errors. + if (errors_n != 0 && !supress_errors) { + for (size_t i = 0; i < errors_n; i++) { + Error err = errors[i]; + for (size_t j = 0; j < err.col + sizeof(REPL_PROMPT) - 2; j++) { + putchar(' '); + } + printf("|\n"); + for (size_t j = 0; j < err.col + sizeof(REPL_PROMPT) - 2; j++) { + putchar(' '); + } + printf("%s\n", error_msgs[err.value]); + } + errors_n = 0; + continue; + } + } +} + +void +run_file(char *file_name) { + FILE *file = fopen(file_name, "r"); + if (!file) { + fprintf(stderr, "error: couldn't open input file: %s\n", file_name); + exit(EXIT_FAILURE); + } + + // Read entire file into memory. + fseek(file, 0, SEEK_END); + size_t file_size = ftell(file); + fseek(file, 0, SEEK_SET); + + char *source = malloc(file_size + 1); + fread(source, 1, file_size, file); + source[file_size] = 0; + + StringView sv = (StringView){ + .start = source, + .n = file_size, + }; + + process_source(&sv); + + // Check if there were any errors. + if (errors_n != 0 && !supress_errors) { + for (size_t i = 0; i < errors_n; i++) { + Error err = errors[i]; + fprintf(stderr, "%s", file_name); + if (err.line != 0) { + fprintf(stderr, ":%ld:%ld", err.line, err.col); + } + fprintf(stderr, ": %s\n", error_msgs[err.value]); + } + errors_n = 0; + } + + free(source); + fclose(file); +} + +#define STDIN_BUF_CAP 16 + +void +run_stdin(void) { + size_t buf_size = 0; + char *source = NULL; + array_init(source, STDIN_BUF_CAP); + + char c; + while ((c = getchar()) != EOF) { + array_push(source, c); + buf_size++; } - if (v3 == dog_val) { - printf("Dog match!\n"); + + StringView sv = (StringView){ + .start = source, + .n = buf_size, + }; + + process_source(&sv); + + // Check if there were any errors. + if (errors_n != 0 && !supress_errors) { + for (size_t i = 0; i < errors_n; i++) { + Error err = errors[i]; + fprintf(stderr, "stdin"); + if (err.line != 0) { + fprintf(stderr, ":%ld:%ld", err.line, err.col); + } + fprintf(stderr, ": %s\n", error_msgs[err.value]); + } + errors_n = 0; } - ht_debug(table); - return 0; + array_free(source); +} + +#ifndef BIN_NAME +#define BIN_NAME "bdl" +#endif + +void +print_usage(void) { + printf("Usage: %s [options] \n", BIN_NAME); + printf("\n"); + printf("\t-i\tInteractive mode (REPL).\n"); + printf("\n"); } -// void -// init(void) { -// // Initialize garbage collector. -// gc_init(); - -// // Initialize singletons. -// obj_nil = alloc_object(OBJ_TYPE_NIL); -// obj_true = alloc_object(OBJ_TYPE_BOOL); -// obj_false = alloc_object(OBJ_TYPE_BOOL); -// obj_err = alloc_object(OBJ_TYPE_ERR); -// obj_quote = make_symbol((StringView){"quote", 5}); -// proc_if = alloc_object(OBJ_TYPE_ERR); -// push_root(obj_nil); -// push_root(obj_true); -// push_root(obj_false); -// push_root(obj_err); -// push_root(obj_quote); -// push_root(proc_if); - -// // Global environment. -// global_env = env_create(NULL); -// // TODO: make sure we create symbols and strings only once (interning -// // strings?) -// push_active_env(global_env); - -// // Primitive symbols. -// MAKE_ENV_VAR(global_env, "else", obj_true); -// MAKE_ENV_VAR(global_env, "nil", obj_nil); -// MAKE_ENV_VAR(global_env, "if", proc_if); - -// // Primitive procedures. -// MAKE_ENV_PROC(global_env, "eval", proc_eval); -// MAKE_ENV_PROC(global_env, "quote", proc_quote); -// MAKE_ENV_PROC(global_env, "car", proc_car); -// MAKE_ENV_PROC(global_env, "cdr", proc_cdr); -// MAKE_ENV_PROC(global_env, "cons", proc_cons); -// MAKE_ENV_PROC(global_env, "list", proc_list); -// MAKE_ENV_PROC(global_env, "+", proc_sum); -// MAKE_ENV_PROC(global_env, "-", proc_sub); -// MAKE_ENV_PROC(global_env, "*", proc_mul); -// MAKE_ENV_PROC(global_env, "/", proc_div); -// MAKE_ENV_PROC(global_env, "%", proc_mod); -// MAKE_ENV_PROC(global_env, "print", proc_print); -// MAKE_ENV_PROC(global_env, "display", proc_display); -// MAKE_ENV_PROC(global_env, "newline", proc_newline); -// MAKE_ENV_PROC(global_env, "boolean?", proc_is_boolean); -// MAKE_ENV_PROC(global_env, "nil?", proc_is_nil); -// MAKE_ENV_PROC(global_env, "symbol?", proc_is_symbol); -// MAKE_ENV_PROC(global_env, "string?", proc_is_string); -// MAKE_ENV_PROC(global_env, "fixnum?", proc_is_fixnum); -// MAKE_ENV_PROC(global_env, "pair?", proc_is_pair); -// MAKE_ENV_PROC(global_env, "procedure?", proc_is_procedure); -// MAKE_ENV_PROC(global_env, "error?", proc_is_error); -// MAKE_ENV_PROC(global_env, "not", proc_not); -// MAKE_ENV_PROC(global_env, "and", proc_and); -// MAKE_ENV_PROC(global_env, "or", proc_or); -// MAKE_ENV_PROC(global_env, "cond", proc_cond); -// MAKE_ENV_PROC(global_env, "<", proc_num_less_than); -// MAKE_ENV_PROC(global_env, "<=", proc_num_lesseq_than); -// MAKE_ENV_PROC(global_env, ">", proc_num_greater_than); -// MAKE_ENV_PROC(global_env, ">=", proc_num_greatereq_than); -// MAKE_ENV_PROC(global_env, "=", proc_num_equal); -// MAKE_ENV_PROC(global_env, "eq?", proc_equal); -// MAKE_ENV_PROC(global_env, "def", proc_define); -// MAKE_ENV_PROC(global_env, "set!", proc_set); -// MAKE_ENV_PROC(global_env, "lambda", proc_lambda); -// MAKE_ENV_PROC(global_env, "fun", proc_fun); - -// // Runtime procedures. -// MAKE_ENV_PROC(global_env, "supress-errors", proc_supress_errors); -// } - -// void -// process_source(const StringView *source) { -// Token *tokens = tokenize(source); -// if (errors_n != 0) { -// if (tokens != NULL) { -// array_free(tokens); -// } -// return; -// } - -// Visitor visitor = (Visitor){ -// .tokens = tokens, -// .current = 0, -// }; -// while (has_next_token(&visitor) && peek_token(&visitor).type != TOKEN_EOF) { -// // Check the root node stack size before parsing -// size_t root_stack_size = array_size(gc.roots); -// Object *root = parse_tree(&visitor); -// array_head(gc.roots)->size = root_stack_size; -// if (root == obj_err || errors_n != 0) { -// break; -// } -// push_root(root); - -// Object *result = eval(global_env, root); -// if (result != obj_nil) { -// display(result); -// printf("\n"); -// } -// pop_root(); -// } - -// if (tokens != NULL) { -// array_free(tokens); -// } -// } - -// #define REPL_PROMPT "bdl> " - -// void -// run_repl(void) { -// printf("BDL REPL (Press Ctrl-D or Ctrl-C to exit)\n"); -// while (true) { -// printf(REPL_PROMPT); -// StringView sv = read_line(); -// if (sv.start == NULL) { -// return; -// } -// process_source(&sv); - -// // Check if there were any errors. -// if (errors_n != 0 && !supress_errors) { -// for (size_t i = 0; i < errors_n; i++) { -// Error err = errors[i]; -// for (size_t j = 0; j < err.col + sizeof(REPL_PROMPT) - 2; j++) { -// putchar(' '); -// } -// printf("|\n"); -// for (size_t j = 0; j < err.col + sizeof(REPL_PROMPT) - 2; j++) { -// putchar(' '); -// } -// printf("%s\n", error_msgs[err.value]); -// } -// errors_n = 0; -// continue; -// } -// } -// } - -// void -// run_file(char *file_name) { -// FILE *file = fopen(file_name, "r"); -// if (!file) { -// fprintf(stderr, "error: couldn't open input file: %s\n", file_name); -// exit(EXIT_FAILURE); -// } - -// // Read entire file into memory. -// fseek(file, 0, SEEK_END); -// size_t file_size = ftell(file); -// fseek(file, 0, SEEK_SET); - -// char *source = malloc(file_size + 1); -// fread(source, 1, file_size, file); -// source[file_size] = 0; - -// StringView sv = (StringView){ -// .start = source, -// .n = file_size, -// }; - -// process_source(&sv); - -// // Check if there were any errors. -// if (errors_n != 0 && !supress_errors) { -// for (size_t i = 0; i < errors_n; i++) { -// Error err = errors[i]; -// fprintf(stderr, "%s", file_name); -// if (err.line != 0) { -// fprintf(stderr, ":%ld:%ld", err.line, err.col); -// } -// fprintf(stderr, ": %s\n", error_msgs[err.value]); -// } -// errors_n = 0; -// } - -// free(source); -// fclose(file); -// } - -// #define STDIN_BUF_CAP 16 - -// void -// run_stdin(void) { -// size_t buf_size = 0; -// char *source = NULL; -// array_init(source, STDIN_BUF_CAP); - -// char c; -// while ((c = getchar()) != EOF) { -// array_push(source, c); -// buf_size++; -// } - -// StringView sv = (StringView){ -// .start = source, -// .n = buf_size, -// }; - -// process_source(&sv); - -// // Check if there were any errors. -// if (errors_n != 0 && !supress_errors) { -// for (size_t i = 0; i < errors_n; i++) { -// Error err = errors[i]; -// fprintf(stderr, "stdin"); -// if (err.line != 0) { -// fprintf(stderr, ":%ld:%ld", err.line, err.col); -// } -// fprintf(stderr, ": %s\n", error_msgs[err.value]); -// } -// errors_n = 0; -// } - -// array_free(source); -// } - -// #ifndef BIN_NAME -// #define BIN_NAME "bdl" -// #endif - -// void -// print_usage(void) { -// printf("Usage: %s [options] \n", BIN_NAME); -// printf("\n"); -// printf("\t-i\tInteractive mode (REPL).\n"); -// printf("\n"); -// } - -// int -// main(int argc, char *argv[]) { -// init(); - -// int option; -// while ((option = getopt(argc, argv, "i")) != -1) { -// switch (option) { -// case 'i': { -// // Interactive mode. -// run_repl(); -// return EXIT_SUCCESS; -// } break; -// default: { -// print_usage(); -// return EXIT_FAILURE; -// } break; -// } -// } - -// // Run from stdin. -// if (optind == argc) { -// run_stdin(); -// return EXIT_SUCCESS; -// } - -// // Run from file. -// while (optind < argc) { -// char *file_name = argv[optind]; -// run_file(file_name); -// optind++; -// } - -// return EXIT_SUCCESS; -// } +int +main(int argc, char *argv[]) { + init(); + + int option; + while ((option = getopt(argc, argv, "i")) != -1) { + switch (option) { + case 'i': { + // Interactive mode. + run_repl(); + return EXIT_SUCCESS; + } break; + default: { + print_usage(); + return EXIT_FAILURE; + } break; + } + } + + // Run from stdin. + if (optind == argc) { + run_stdin(); + return EXIT_SUCCESS; + } + + // Run from file. + while (optind < argc) { + char *file_name = argv[optind]; + run_file(file_name); + optind++; + } + + return EXIT_SUCCESS; +} -- cgit v1.2.1