use maps in scope

5 files changed, 49 insertions, 104 deletions

diff --git a/deps/conts b/deps/conts
-Subproject 8946fa4b77fef3002d78bb1c5a19cc05c97a71c
+Subproject 56edd66ae3e8661d40d499bd7c72f3ffc7aac4e
diff --git a/include/fwd/scope.h b/include/fwd/scope.h
index 2e71cdb..e49eb0a 100644
--- a/include/fwd/scope.h
+++ b/include/fwd/scope.h
@@ -13,29 +13,17 @@
 #include "ast.h"
 #include "debug.h"
 
-/**
- * An AST node visible to the scope we're in.
- * The same AST node can be referenced by multiple visible nodes,
- * but only the owning scope is allowed to destroy the node.
- * Check that \p owner is identical to the scope the visible node
- * belongs to.
- *
- * Basic linked list for now, can probably be optimized into some kind of hash
- * table later.
- */
-struct visible {
-	/** Name of the visible node. */
-	char *id;
-	/** AST node that is visible. */
-	struct ast *node;
-	/** Next visible object in the scope we're in. */
-	struct visible *next;
-};
-
 enum scope_flags {
 	SCOPE_PROC = (1 << 0),
 };
 
+#define MAP_KEY char *
+#define MAP_TYPE struct ast *
+#define MAP_CMP(a, b) strcmp((a), (b))
+#define MAP_HASH(a) CONTS_MAP_STR_HASH(a)
+#define MAP_NAME visible
+#include <conts/map.h>
+
 /**
  * Scope.
  * Responsible for keeping track of visibilities and
@@ -63,7 +51,7 @@ struct scope {
 	/** List of child scopes. */
 	struct scope *children;
 
-	struct visible *symbols;
+	struct visible symbols;
 
 	enum scope_flags flags;
 };
@@ -194,7 +182,4 @@ struct ast *file_scope_find_symbol(struct scope *scope, char *id);
  */
 struct ast *file_scope_find_proc(struct scope *scope, char *id);
 
-#define foreach_visible(iter, init) \
-	for (struct visible *iter = init; iter; iter = iter->next)
-
 #endif /* SCOPE_H */
diff --git a/src/lower.c b/src/lower.c
index 21844ae..89d9aca 100644
--- a/src/lower.c
+++ b/src/lower.c
@@ -476,8 +476,8 @@ static int lower_block_vars(struct state *state, struct ast *block)
 	struct scope *scope = block->scope;
 
 	bool populated = false;
-	foreach_visible(n, scope->symbols) {
-		struct ast *def = n->node;
+	foreach(visible, n, &scope->symbols) {
+		struct ast *def = n->data;
 		if (def->k != AST_VAR_DEF)
 			continue;
 
@@ -626,15 +626,15 @@ int lower(struct scope *root)
 {
 	printf("#include <fwdlib.hpp>\n");
 
-	foreach_visible(visible, root->symbols) {
-		struct ast *proc = visible->node;
+	foreach(visible, visible, &root->symbols) {
+		struct ast *proc = visible->data;
 		assert(proc->k == AST_PROC_DEF);
 		if (lower_proto(proc))
 			return -1;
 	}
 
-	foreach_visible(visible, root->symbols) {
-		struct ast *proc = visible->node;
+	foreach(visible, visible, &root->symbols) {
+		struct ast *proc = visible->data;
 		if (lower_proc(proc))
 			return -1;
 	}
diff --git a/src/move.c b/src/move.c
index dc50cac..602b620 100644
--- a/src/move.c
+++ b/src/move.c
@@ -270,8 +270,8 @@ static int mvcheck_proc(struct state *state, struct ast *node)
 static int total_check_single(struct state *state, struct scope *scope)
 {
 	int ret = 0;
-	foreach_visible(n, scope->symbols) {
-		struct ast *def = n->node;
+	foreach(visible, n, &scope->symbols) {
+		struct ast *def = n->data;
 		if (def->k != AST_VAR_DEF)
 			continue;
 
diff --git a/src/scope.c b/src/scope.c
index a7dfa69..367384a 100644
--- a/src/scope.c
+++ b/src/scope.c
@@ -28,19 +28,10 @@ struct scope *create_scope()
 	}
 
 	scope->number = counter++;
+	scope->symbols = visible_create(16); /* arbitrary number */
 	return scope;
 }
 
-static void destroy_visible(struct visible *visible)
-{
-	struct visible *prev = visible, *cur;
-	if (prev)
-		do {
-			cur = prev->next;
-			free(prev);
-		} while ((prev = cur));
-}
-
 void destroy_scope(struct scope *scope)
 {
 	if (!scope)
@@ -51,7 +42,7 @@ void destroy_scope(struct scope *scope)
 		free((void *)scope->fctx.fname);
 	}
 
-	destroy_visible(scope->symbols);
+	visible_destroy(&scope->symbols);
 
 	struct scope *prev = scope->children, *cur;
 	if (prev)
@@ -63,88 +54,50 @@ void destroy_scope(struct scope *scope)
 	free(scope);
 }
 
-static struct visible *create_visible(char *id, struct ast *node)
-{
-	struct visible *visible = calloc(1, sizeof(struct visible));
-	if (!visible)
-		return NULL;
-
-	visible->id = id;
-	visible->node = node;
-	return visible;
-}
-
-struct visible *create_var(struct scope *scope, char *id, struct ast *var)
-{
-	struct visible *n = create_visible(id, var);
-	if (!n)
-		return NULL;
-
-	n->next = scope->symbols;
-	scope->symbols = n;
-
-	return n;
-}
-
-struct visible *create_proc(struct scope *scope, char *id, struct ast *proc)
-{
-	struct visible *n = create_visible(id, proc);
-	if (!n)
-		return NULL;
-
-	n->next = scope->symbols;
-	scope->symbols = n;
-
-	return n;
-}
-
 int scope_add_var(struct scope *scope, struct ast *var)
 {
-	struct ast *exists = scope_find_symbol(scope, var_id(var));
-	if (exists) {
+	assert(var->k == AST_VAR_DEF);
+	struct ast **exists = visible_insert(&scope->symbols, var_id(var), var);
+	if (!exists) {
+		internal_error("failed inserting var into scope");
+		return -1;
+	}
+
+	if (*exists != var) {
 		semantic_error(scope, var, "var redefined");
-		semantic_info(scope, exists, "previously here");
+		semantic_info(scope, *exists, "previously here");
 		return -1;
 	}
 
-	create_var(scope, var_id(var), var);
 	return 0;
 }
 
 int scope_add_proc(struct scope *scope, struct ast *proc)
 {
 	assert(proc->k == AST_PROC_DEF);
-	struct ast *exists = file_scope_find_symbol(scope, proc_id(proc));
-	if (exists) {
+	struct ast **exists = visible_insert(&scope->symbols, proc_id(proc), proc);
+	if (!exists) {
+		internal_error("failed inserting proc into scope");
+		return -1;
+	}
+
+	if (*exists != proc) {
 		semantic_error(scope, proc, "proc redefined");
-		semantic_info(scope, exists, "previously here");
+		semantic_info(scope, *exists, "previously here");
 		return -1;
 	}
 
-	/* always add to scope, do resolve checking later */
-	create_proc(scope, proc_id(proc), proc);
 	return 0;
 }
 
-static struct ast *scope_find_visible(struct visible *v, char *id)
+struct ast *scope_find_proc(struct scope *scope, char *id)
 {
+	struct ast **v = visible_find(&scope->symbols, id);
 	if (!v)
 		return NULL;
 
-	foreach_visible(n, v) {
-		struct ast *node = n->node;
-		if (same_id(node->s, id))
-			return node;
-	}
-
-	return NULL;
-}
-
-struct ast *scope_find_proc(struct scope *scope, char *id)
-{
-	struct ast *n = scope_find_visible(scope->symbols, id);
-	if (!n)
-		return NULL;
+	struct ast *n = *v;
+	assert(n);
 
 	if (n->k != AST_PROC_DEF)
 		return NULL;
@@ -166,7 +119,11 @@ struct ast *file_scope_find_proc(struct scope *scope, char *id)
 
 struct ast *scope_find_symbol(struct scope *scope, char *id)
 {
-	return scope_find_visible(scope->symbols, id);
+	struct ast **v = visible_find(&scope->symbols, id);
+	if (!v)
+		return NULL;
+
+	return *v;
 }
 
 struct ast *file_scope_find_symbol(struct scope *scope, char *id)
@@ -183,10 +140,13 @@ struct ast *file_scope_find_symbol(struct scope *scope, char *id)
 
 struct ast *scope_find_var(struct scope *scope, char *id)
 {
-	struct ast *n = scope_find_visible(scope->symbols, id);
-	if (!n)
+	struct ast **v = visible_find(&scope->symbols, id);
+	if (!v)
 		return NULL;
 
+	struct ast *n = *v;
+	assert(n);
+
 	if (n->k != AST_VAR_DEF)
 		return NULL;