use maps for scope

5 files changed, 74 insertions, 193 deletions

diff --git a/include/ek/ast.h b/include/ek/ast.h
index f6e83cb..81b1a85 100644
--- a/include/ek/ast.h
+++ b/include/ek/ast.h
@@ -752,4 +752,6 @@ struct type *reverse_type_list(struct type *root);
 struct ast *chain_base(struct ast *node);
 struct ast *clone_chain(struct ast *chain);
 
+int type_lists_match(struct type *a, struct type *b);
+
 #endif /* AST_H */
diff --git a/include/ek/scope.h b/include/ek/scope.h
index d63d2fc..ab27cc6 100644
--- a/include/ek/scope.h
+++ b/include/ek/scope.h
@@ -10,6 +10,8 @@
  * Scope handling stuff.
  */
 
+#include <string.h>
+
 #include "ast.h"
 #include "debug.h"
 
@@ -22,37 +24,36 @@ enum scope_flags {
 	SCOPE_FILE = (1 << 1),
 };
 
-/**
- * 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;
+struct visible_tuple {
+	struct ast *def;
 };
 
-struct expanded {
-	struct ast *node;
+#define MAP_KEY char *
+#define MAP_TYPE struct ast *
+#define MAP_CMP(a, b) strcmp((a), (b))
+#define MAP_NAME visible
+#include "map.h"
+
+struct expanded_key {
+	struct ast *def;
 	struct type *types;
-	struct ast *expd;
-	struct expanded *next;
 };
 
-struct type_defs {
-	char *id;
-	struct ast *type_def;
-	struct type_defs *next;
-};
+static inline int expanded_key_cmp(struct expanded_key a, struct expanded_key b)
+{
+	uintptr_t na = (uintptr_t)a.def;
+	uintptr_t nb = (uintptr_t)b.def;
+	if (na != nb)
+		return na - nb;
+
+	return !type_lists_match(a.types, b.types);
+}
+
+#define MAP_KEY struct expanded_key
+#define MAP_TYPE struct ast *
+#define MAP_CMP(a, b) expanded_key_cmp((a), (b))
+#define MAP_NAME expanded
+#include "map.h"
 
 /**
  * Scope.
@@ -81,13 +82,11 @@ struct scope {
 	/** List of child scopes. */
 	struct scope *children;
 
-	struct expanded *expanded;
-
-	struct visible *symbols;
-	struct visible *macros;
-	struct visible *types;
+	struct expanded expanded;
 
-	struct visible *type_constructs;
+	struct visible symbols;
+	struct visible macros;
+	struct visible types;
 };
 
 /**
@@ -106,24 +105,6 @@ struct scope *create_scope();
 void destroy_scope(struct scope *scope);
 
 /**
- * Add default stuff to scope, mainly builtin types.
- *
- * @param root Scope to add default stuff to.
- * @note Only has to be called on the file scope, all child scopes will
- * look up stuff from the file scope anyway.
- * @return \c 0 if succesful, non-zero otherwise.
- */
-int scope_add_defaults(struct scope *root);
-
-/**
- * Destroy defaults in scope that might otherwise not be freed.
- *
- * @param root Scope to destroy added defaults in.
- * @todo not sure if this should be private.
- */
-void scope_destroy_defaults(struct scope *root);
-
-/**
  * Add a scratch AST node.
  *
  * @param scope Scope to add scratch AST node to.
@@ -355,8 +336,6 @@ struct ast *file_scope_find_trait(struct scope *scope, char *id);
 struct ast *file_scope_find_expd_struct(struct scope *scope, struct ast *def,
                                         struct type *types);
 
-bool same_src(struct ast *a, struct ast *b);
-
 #define foreach_visible(iter, init) \
 	for (struct visible *iter = init; iter; iter = iter->next)
 
diff --git a/include/ek/sptree.h b/include/ek/sptree.h
index 4718c26..8dfdfbf 100644
--- a/include/ek/sptree.h
+++ b/include/ek/sptree.h
@@ -1,6 +1,7 @@
 #include <stdint.h>
 #include <stdlib.h>
 #include <stddef.h>
+#include <assert.h>
 #include <stdbool.h>
 
 #ifndef SPTREE_TYPE
diff --git a/src/compiler.c b/src/compiler.c
index 2041efd..7ce6167 100644
--- a/src/compiler.c
+++ b/src/compiler.c
@@ -132,8 +132,8 @@ static int process(struct scope **parent, int public, const char *file)
 static int copy_scope(struct scope *to, struct scope *from)
 {
 	/** @todo handle duplicates */
-	foreach_visible(n, from->symbols) {
-		struct ast *def = n->node;
+	foreach(visible, n, &from->symbols) {
+		struct ast *def = n->data;
 		if (!ast_flags(def, AST_FLAG_PUBLIC))
 			continue;
 
@@ -206,6 +206,7 @@ int process_file(struct scope **scope, int public, const char *file)
 		if (copy_scope(*scope, *exists))
 			goto out;
 
+		free(real);
 	} else {
 		if (process(scope, public, base))
 			goto out;
diff --git a/src/scope.c b/src/scope.c
index 8ffe2f9..52028a8 100644
--- a/src/scope.c
+++ b/src/scope.c
@@ -34,30 +34,15 @@ struct scope *create_scope()
 		return NULL;
 	}
 
+	scope->expanded = expanded_create();
+	scope->symbols = visible_create();
+	scope->macros = visible_create();
+	scope->types = visible_create();
+
 	scope->number = counter++;
 	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));
-}
-
-static void destroy_expanded(struct expanded *expanded)
-{
-	struct expanded *prev = expanded, *cur;
-	if (prev)
-		do {
-			cur = prev->next;
-			free(prev);
-		} while ((prev = cur));
-}
-
 void destroy_scope(struct scope *scope)
 {
 	if (!scope)
@@ -68,11 +53,11 @@ void destroy_scope(struct scope *scope)
 		free((void *)scope->fctx.fname);
 	}
 
-	destroy_visible(scope->symbols);
-	destroy_visible(scope->macros);
-	destroy_visible(scope->types);
+	visible_destroy(&scope->symbols);
+	visible_destroy(&scope->macros);
+	visible_destroy(&scope->types);
 
-	destroy_expanded(scope->expanded);
+	expanded_destroy(&scope->expanded);
 
 	struct scope *prev = scope->children, *cur;
 	if (prev)
@@ -96,80 +81,31 @@ unsigned scope_flags(struct scope *scope, enum scope_flags flags)
 	return (scope->flags & flags) == flags;
 }
 
-static struct visible *create_visible(char *id, struct ast *node)
+struct ast **create_type(struct scope *scope, char *id, struct ast *type)
 {
-	struct visible *visible = calloc(1, sizeof(struct visible));
-	if (!visible)
-		return NULL;
-
-	visible->id = id;
-	visible->node = node;
-	return visible;
+	return visible_insert(&scope->types, id, type);
 }
 
-struct visible *create_type(struct scope *scope, char *id, struct ast *type)
-{
-	struct visible *n = create_visible(id, type);
-	if (!n)
-		return NULL;
-
-	n->next = scope->types;
-	scope->types = n;
-
-	return n;
-}
-
-struct expanded *create_expanded(struct scope *scope, struct ast *def,
+struct ast **create_expanded(struct scope *scope, struct ast *def,
                                  struct type *types, struct ast *expd)
 {
-	struct expanded *n = calloc(1, sizeof(struct expanded));
-	if (!n)
-		return NULL;
-
-	n->node = def;
-	n->types = types;
-	n->expd = expd;
-
-	n->next = scope->expanded;
-	scope->expanded = n;
-
-	return n;
+	struct expanded_key key = {.def = def, .types = types};
+	return expanded_insert(&scope->expanded, key, expd);
 }
 
-struct visible *create_var(struct scope *scope, char *id, struct ast *var)
+struct ast **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;
+	return visible_insert(&scope->symbols, id, var);
 }
 
-struct visible *create_macro(struct scope *scope, char *id, struct ast *macro)
+struct ast **create_macro(struct scope *scope, char *id, struct ast *macro)
 {
-	struct visible *n = create_visible(id, macro);
-	if (!n)
-		return NULL;
-
-	n->next = scope->macros;
-	scope->macros = n;
-
-	return n;
+	return visible_insert(&scope->macros, id, macro);
 }
 
-struct visible *create_proc(struct scope *scope, char *id, struct ast *proc)
+struct ast **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;
+	return visible_insert(&scope->symbols, id, proc);
 }
 
 static bool scope_add_recurse(struct scope *scope, struct ast *node)
@@ -218,32 +154,17 @@ int scope_add_type(struct scope *scope, char *id, struct ast *type)
 	return 0;
 }
 
-static struct visible *scope_find_visible(struct visible *v, char *id)
-{
-	if (!v)
-		return NULL;
-
-	foreach_visible(n, v) {
-		struct ast *node = n->node;
-		if (same_id(node->s, id))
-			return n;
-	}
-
-	return NULL;
-}
-
 static void insert_chain(struct scope *scope, char *id, struct ast *type)
 {
-	struct visible *v = scope_find_visible(scope->types, id);
+	struct ast **v = visible_find(&scope->types, id);
 	assert(v);
 
-	struct ast *n = v->node;
-	assert(n);
+	struct ast *n = *v;
 
 	if (ast_flags(n, AST_FLAG_PUBLIC)
 	    || !ast_flags(type, AST_FLAG_PUBLIC)) {
-		type->chain = v->node;
-		v->node = type;
+		type->chain = n;
+		*v = type;
 		return;
 	}
 
@@ -344,23 +265,6 @@ int scope_add_expd_struct(struct scope *scope, struct ast *def,
 	return 0;
 }
 
-static struct expanded *scope_find_expanded(struct expanded *e, struct ast *def,
-                                            struct type *types)
-{
-	if (!e)
-		return NULL;
-
-	foreach_expanded(n, e) {
-		if (n->node != def)
-			continue;
-
-		if (type_lists_match(n->types, types))
-			return n;
-	}
-
-	return NULL;
-}
-
 int scope_add_expd_chain(struct scope *scope, struct ast *def,
                          struct type *types, struct ast *expd)
 {
@@ -377,11 +281,11 @@ int scope_add_expd_chain(struct scope *scope, struct ast *def,
 
 struct ast *scope_find_type(struct scope *scope, char *id)
 {
-	struct visible *v = scope_find_visible(scope->types, id);
+	struct ast **v = visible_find(&scope->types, id);
 	if (!v)
 		return NULL;
 
-	return v->node;
+	return *v;
 }
 
 struct ast *file_scope_find_type(struct scope *scope, char *id)
@@ -401,11 +305,11 @@ struct ast *file_scope_find_type(struct scope *scope, char *id)
 
 struct ast *scope_find_macro(struct scope *scope, char *id)
 {
-	struct visible *v = scope_find_visible(scope->macros, id);
+	struct ast **v = visible_find(&scope->macros, id);
 	if (!v)
 		return NULL;
 
-	return v->node;
+	return *v;
 }
 
 struct ast *file_scope_find_macro(struct scope *scope, char *id)
@@ -425,11 +329,11 @@ struct ast *file_scope_find_macro(struct scope *scope, char *id)
 
 struct ast *scope_find_proc(struct scope *scope, char *id)
 {
-	struct visible *v = scope_find_visible(scope->symbols, id);
+	struct ast **v = visible_find(&scope->symbols, id);
 	if (!v)
 		return NULL;
 
-	struct ast *n = v->node;
+	struct ast *n = *v;
 	assert(n);
 
 	if (n->k != AST_PROC_DEF)
@@ -452,11 +356,11 @@ struct ast *file_scope_find_proc(struct scope *scope, char *id)
 
 struct ast *scope_find_symbol(struct scope *scope, char *id)
 {
-	struct visible *v = scope_find_visible(scope->symbols, id);
+	struct ast **v = visible_find(&scope->symbols, id);
 	if (!v)
 		return NULL;
 
-	return v->node;
+	return *v;
 }
 
 struct ast *file_scope_find_symbol(struct scope *scope, char *id)
@@ -476,11 +380,11 @@ struct ast *file_scope_find_symbol(struct scope *scope, char *id)
 
 struct ast *scope_find_var(struct scope *scope, char *id)
 {
-	struct visible *v = scope_find_visible(scope->symbols, id);
+	struct ast **v = visible_find(&scope->symbols, id);
 	if (!v)
 		return NULL;
 
-	struct ast *n = v->node;
+	struct ast *n = *v;
 	assert(n);
 
 	if (n->k != AST_VAR_DEF)
@@ -508,12 +412,12 @@ struct ast *scope_find_expd_struct(struct scope *scope, struct ast *def,
                                    struct type *types)
 {
 	assert(def->k == AST_STRUCT_DEF || def->k == AST_STRUCT_CONT_DEF);
-	struct expanded *expd = scope_find_expanded(scope->expanded, def,
-	                                            types);
+	struct expanded_key key = {.def = def, .types = types};
+	struct ast **expd = expanded_find(&scope->expanded, key);
 	if (!expd)
 		return NULL;
 
-	struct ast *exists = expd->expd;
+	struct ast *exists = *expd;
 	assert(exists->k == AST_STRUCT_DEF || exists->k == AST_STRUCT_CONT_DEF);
 	return exists;
 }
@@ -545,9 +449,3 @@ void scope_add_scope(struct scope *parent, struct scope *child)
 	child->next = parent->children;
 	parent->children = child;
 }
-
-bool same_src(struct ast *a, struct ast *b)
-{
-	return same_src_scope(a->scope, b->scope);
-}
-