improve generics expansion

4 files changed, 548 insertions, 2 deletions

diff --git a/include/ek/ast.h b/include/ek/ast.h
index 2ee9f6f..f6e83cb 100644
--- a/include/ek/ast.h
+++ b/include/ek/ast.h
@@ -194,6 +194,9 @@ enum ast_flags {
 	AST_FLAG_NOMANGLE = (1 << 14),
 	AST_FLAG_DOEXPR = (1 << 15),
 	AST_FLAG_LOWERED = (1 << 16),
+	AST_FLAG_UFCS_SIMPLE = (1 << 17),
+	AST_FLAG_UFCS_REF = (1 << 18),
+	AST_FLAG_UFCS_TRIVIAL = (1 << 19),
 };
 
 struct ast;
@@ -578,13 +581,15 @@ static inline bool is_primitive(struct type *t)
 
 #define struct_id(x) return_s(x, AST_STRUCT_DEF)
 #define struct_params(x) return_a0(x, AST_STRUCT_DEF)
-#define struct_body(x) return_a1(x, AST_STRUCT_DEF)
+#define struct_body(x) return_a2(x, AST_STRUCT_DEF)
+#define struct_raw_body(x) return_a1(x, AST_STRUCT_DEF)
 #define gen_struct(id, params, body, loc) \
 	gen_str2(AST_STRUCT_DEF, id, params, body, loc)
 
 #define struct_cont_id(x) return_s(x, AST_STRUCT_CONT_DEF)
 #define struct_cont_params(x) return_a0(x, AST_STRUCT_CONT_DEF)
-#define struct_cont_body(x) return_a1(x, AST_STRUCT_CONT_DEF)
+#define struct_cont_body(x) return_a2(x, AST_STRUCT_CONT_DEF)
+#define struct_cont_raw_body(x) return_a1(x, AST_STRUCT_CONT_DEF)
 #define gen_struct_cont(id, params, body, loc)                              \
 	gen_ast(AST_STRUCT_CONT_DEF, params, body, NULL, NULL, NULL, id, 0, \
 		loc)
diff --git a/include/ek/conts.h b/include/ek/conts.h
new file mode 100644
index 0000000..c1e4d24
--- /dev/null
+++ b/include/ek/conts.h
@@ -0,0 +1,14 @@
+#ifndef CONTS_H
+#define CONTS_H
+
+#define CONTS_JOIN2(a, b) a##_##b
+#define CONTS_JOIN(a, b) CONTS_JOIN2(a, b)
+
+#define CONTAINER_OF(ptr, type, member) \
+	(type *)((char *)(ptr) - offsetof(type, member))
+
+#define foreach(name, i, s)                       \
+	for (auto i = CONTS_JOIN(name, begin)(s); \
+	     !CONTS_JOIN(name, end)(s, i);        \
+	     i = CONTS_JOIN(name, next)(i))
+#endif /* CONTS_H */
diff --git a/include/ek/map.h b/include/ek/map.h
new file mode 100644
index 0000000..5a6a22d
--- /dev/null
+++ b/include/ek/map.h
@@ -0,0 +1,105 @@
+#ifndef MAP_KEY
+#error "Need map key"
+#endif
+
+#ifndef MAP_TYPE
+#error "Need map type"
+#endif
+
+#ifndef MAP_CMP
+#error "Need map cmp"
+#endif
+
+#ifndef MAP_NAME
+#error "Need map name"
+#endif
+
+#include "conts.h"
+
+#define MAP(a) CONTS_JOIN(MAP_NAME, a)
+
+#define MAP_NODE MAP(node)
+#define MAP_ROOT MAP_NAME
+
+struct MAP_NODE {
+	MAP_KEY key;
+	MAP_TYPE data;
+};
+
+static inline int MAP(cmp)(struct MAP_NODE a, struct MAP_NODE b)
+{
+	return MAP_CMP(a.key, b.key);
+}
+
+#define BASE(a) CONTS_JOIN(MAP(map_base), a)
+
+#define SPTREE_TYPE struct MAP_NODE
+#define SPTREE_CMP MAP(cmp)
+#define SPTREE_NAME MAP(map_base)
+#include "sptree.h"
+
+struct MAP_ROOT {
+	struct MAP(map_base) root;
+};
+
+static inline struct MAP_ROOT MAP(create)()
+{
+	return (struct MAP_ROOT){.root = BASE(create)()};
+}
+
+static inline void MAP(destroy)(struct MAP_ROOT *root)
+{
+	BASE(destroy)(&root->root);
+}
+
+static inline MAP_TYPE *MAP(insert)(struct MAP_ROOT *root, MAP_KEY key,
+                                    MAP_TYPE data)
+{
+	struct MAP_NODE node = {.key = key, .data = data};
+	struct MAP_NODE *res = BASE(insert)(&root->root, node);
+	if (!res)
+		return NULL;
+
+	return &res->data;
+}
+
+static inline MAP_TYPE *MAP(find)(struct MAP_ROOT *root, MAP_KEY key)
+{
+	struct MAP_NODE node = {.key = key};
+	struct MAP_NODE *res = BASE(find)(&root->root, node);
+	if (!res)
+		return NULL;
+
+	return &res->data;
+}
+
+static inline void MAP(remove)(struct MAP_ROOT *root, MAP_KEY key)
+{
+	struct MAP_NODE node = {.key = key};
+	BASE(remove)(&root->root, node);
+}
+
+static inline struct MAP_NODE *MAP(begin)(struct MAP_ROOT *root)
+{
+	return BASE(begin)(&root->root);
+}
+
+static inline struct MAP_NODE *MAP(next)(struct MAP_NODE *n)
+{
+	return BASE(next)(n);
+}
+
+static inline bool MAP(end)(struct MAP_ROOT *root, struct MAP_NODE *n)
+{
+	return BASE(end)(&root->root, n);
+}
+
+static inline size_t MAP(len)(struct MAP_ROOT *root)
+{
+	return BASE(len)(&root->root);
+}
+
+#undef MAP_KEY
+#undef MAP_TYPE
+#undef MAP_CMP
+#undef MAP_NAME
diff --git a/include/ek/sptree.h b/include/ek/sptree.h
new file mode 100644
index 0000000..4718c26
--- /dev/null
+++ b/include/ek/sptree.h
@@ -0,0 +1,422 @@
+#include <stdint.h>
+#include <stdlib.h>
+#include <stddef.h>
+#include <stdbool.h>
+
+#ifndef SPTREE_TYPE
+#error "Need sptree type"
+#endif
+
+#ifndef SPTREE_CMP
+#error "Need sptree cmp"
+#endif
+
+#ifndef SPTREE_NAME
+#error "Need sptree name"
+#endif
+
+#include "conts.h"
+
+#define SPTREE(a) CONTS_JOIN(SPTREE_NAME, a)
+
+#define SPNODE SPTREE(node)
+#define SPROOT SPTREE_NAME
+
+#ifndef SPTREE_H
+#define SPTREE_H
+
+#define sp_left(n) ((n)->left)
+#define sp_right(n) ((n)->right)
+#define sp_paren(n) ((n)->parent)
+#define sp_lparen(n) (sp_left(n)->parent)
+#define sp_rparen(n) (sp_right(n)->parent)
+
+#endif /* SPTREE_H */
+
+struct SPNODE {
+	int_fast16_t hint;
+	struct SPNODE *left, *right, *parent;
+	SPTREE_TYPE data;
+};
+
+struct SPROOT {
+	size_t n;
+	struct SPNODE *root;
+};
+
+static inline struct SPROOT SPTREE(create)()
+{
+	return (struct SPROOT){.n = 0, .root = NULL};
+}
+
+static inline size_t SPTREE(len)(struct SPROOT *s)
+{
+	return s->n;
+}
+
+static inline struct SPNODE *SPTREE(first)(struct SPNODE *n)
+{
+	while (sp_left(n))
+		n = sp_left(n);
+
+	return n;
+}
+
+static inline struct SPNODE *SPTREE(last)(struct SPNODE *n)
+{
+	while (sp_right(n))
+		n = sp_right(n);
+
+	return n;
+}
+
+static inline SPTREE_TYPE *SPTREE(begin)(struct SPROOT *s)
+{
+	return &SPTREE(first)(s->root)->data;
+}
+
+static inline SPTREE_TYPE *SPTREE(next)(SPTREE_TYPE *prev)
+{
+	struct SPNODE *n = CONTAINER_OF(prev, struct SPNODE, data);
+	if (sp_right(n)) {
+		n = sp_right(n);
+		while (sp_left(n))
+			n = sp_left(n);
+
+		return &n->data;
+	}
+
+	while (n) {
+		struct SPNODE *p = sp_paren(n);
+		if (!p)
+			return NULL;
+
+		if (sp_left(p) == n)
+			return &p->data;
+
+		n = p;
+	}
+
+	return NULL;
+}
+
+static inline bool SPTREE(end)(struct SPROOT *s, SPTREE_TYPE *prev)
+{
+	(void)s;
+	return prev == NULL;
+}
+
+static inline void SPTREE(turn_left)(struct SPNODE *n)
+{
+	struct SPNODE *l = sp_left(n);
+	struct SPNODE *p = sp_paren(n);
+
+	assert(l);
+
+	sp_paren(l) = sp_paren(n);
+	sp_left(n) = sp_right(l);
+	sp_paren(n) = l;
+	sp_right(l) = n;
+
+	if (p && sp_left(p) == n)
+		sp_left(p) = l;
+	else if (p)
+		sp_right(p) = l;
+
+	if (sp_left(n))
+		sp_lparen(n) = n;
+}
+
+static inline void SPTREE(turn_right)(struct SPNODE *n)
+{
+	struct SPNODE *r = sp_right(n);
+	struct SPNODE *p = sp_paren(n);
+
+	assert(r);
+
+	sp_paren(r) = sp_paren(n);
+	sp_right(n) = sp_left(r);
+	sp_paren(n) = r;
+	sp_left(r) = n;
+
+	if (p && sp_left(p) == n)
+		sp_left(p) = r;
+	else if (p)
+		sp_right(p) = r;
+
+	if (sp_right(n))
+		sp_rparen(n) = n;
+}
+
+static inline int_fast16_t SPTREE(leaning)(struct SPNODE *n)
+{
+	int_fast16_t l = 0;
+	int_fast16_t r = 0;
+
+	if (sp_left(n))
+		l = sp_left(n)->hint + 1;
+
+	if (sp_right(n))
+		r = sp_right(n)->hint + 1;
+
+	return l - r;
+}
+
+static inline int_fast16_t SPTREE(max_hint)(struct SPNODE *n)
+{
+	int_fast16_t l = 0;
+	int_fast16_t r = 0;
+
+	if (sp_left(n))
+		l = sp_left(n)->hint + 1;
+
+	if (sp_right(n))
+		r = sp_right(n)->hint + 1;
+
+	if (l > r)
+		return l;
+	else
+		return r;
+}
+
+static inline void SPTREE(update)(struct SPROOT *r, struct SPNODE *n)
+{
+	while (n) {
+		int b = SPTREE(leaning)(n);
+		int prev_hint = n->hint;
+		struct SPNODE *p = sp_paren(n);
+
+		if (b < -1) {
+			/* leaning to the right */
+			if (n == r->root)
+				r->root = sp_right(n);
+
+			SPTREE(turn_right)(n);
+		}
+
+		else if (b > 1) {
+			/* leaning to the left */
+			if (n == r->root)
+				r->root = sp_left(n);
+
+			SPTREE(turn_left)(n);
+		}
+
+		n->hint = SPTREE(max_hint)(n);
+		if (n->hint == 0 || n->hint != prev_hint)
+			n = p;
+		else
+			return;
+	}
+}
+
+static inline SPTREE_TYPE *SPTREE(insert)(struct SPROOT *s, SPTREE_TYPE data)
+{
+	if (!s->root) {
+		assert(s->n == 0);
+		struct SPNODE *new = malloc(sizeof(struct SPNODE));
+		if (!new)
+			return NULL;
+
+		new->left = new->right = new->parent = NULL;
+		new->data = data;
+		new->hint = 0;
+
+		s->root = new;
+		s->n = 1;
+		return &new->data;
+	}
+
+	bool insert_left = false;
+
+	struct SPNODE *n = s->root;
+	struct SPNODE *p = NULL;
+	while (n) {
+		p = n;
+		int c = SPTREE_CMP(n->data, data);
+		if (c < 0) {
+			n = sp_left(n);
+			insert_left = true;
+			continue;
+		}
+		if (c > 0) {
+			n = sp_right(n);
+			insert_left = false;
+			continue;
+		}
+
+		/* we already have a node like this */
+		return &n->data;
+	}
+
+	struct SPNODE *new = malloc(sizeof(struct SPNODE));
+	if (!new)
+		return NULL;
+
+	new->left = new->right = NULL;
+	new->parent = p;
+	new->data = data;
+	new->hint = 0;
+
+	if (insert_left)
+		sp_left(p) = new;
+	else
+		sp_right(p) = new;
+
+	SPTREE(update)(s, new);
+	s->n++;
+	return &new->data;
+}
+
+static inline void SPTREE(replace_right)(struct SPNODE *n, struct SPNODE *r)
+{
+	struct SPNODE *p = sp_paren(n);
+	struct SPNODE *rp = sp_paren(r);
+
+	if (sp_left(rp) == r) {
+		sp_left(rp) = sp_right(r);
+		if (sp_right(r))
+			sp_rparen(r) = rp;
+	}
+
+	if (sp_paren(rp) == n)
+		sp_paren(rp) = r;
+
+	sp_paren(r) = p;
+	sp_left(r) = sp_left(n);
+
+	if (sp_right(n) != r) {
+		sp_right(r) = sp_right(n);
+		sp_rparen(n) = r;
+	}
+
+	if (p && sp_left(p) == n)
+		sp_left(p) = r;
+	else if (p)
+		sp_right(p) = r;
+
+	if (sp_left(n))
+		sp_lparen(n) = r;
+}
+
+static inline void SPTREE(replace_left)(struct SPNODE *n, struct SPNODE *l)
+{
+	struct SPNODE *p = sp_paren(n);
+	struct SPNODE *lp = sp_paren(l);
+
+	if (sp_right(lp) == l) {
+		sp_right(lp) = sp_left(l);
+		if (sp_left(l))
+			sp_lparen(l) = lp;
+	}
+
+	if (sp_paren(lp) == n)
+		sp_paren(lp) = l;
+
+	sp_paren(l) = p;
+	sp_right(l) = sp_right(n);
+
+	if (sp_left(n) != l) {
+		sp_left(l) = sp_left(n);
+		sp_lparen(n) = l;
+	}
+
+	if (p && sp_left(p) == n)
+		sp_left(p) = l;
+	else if (p)
+		sp_right(p) = l;
+
+	if (sp_right(n))
+		sp_rparen(n) = l;
+}
+
+static inline SPTREE_TYPE *SPTREE(find)(struct SPROOT *s, SPTREE_TYPE data)
+{
+	struct SPNODE *n = s->root;
+	while (n) {
+		int c = SPTREE_CMP(n->data, data);
+		if (c < 0) {
+			n = n->left;
+			continue;
+		}
+
+		if (c > 0) {
+			n = n->right;
+			continue;
+		}
+
+		return &n->data;
+	}
+
+	return NULL;
+}
+
+static inline void SPTREE(remove_found)(struct SPROOT *s, SPTREE_TYPE *found)
+{
+	s->n--;
+	struct SPNODE *del = CONTAINER_OF(found, struct SPNODE, data);
+	if (sp_right(del)) {
+		struct SPNODE *least = SPTREE(first)(sp_right(del));
+
+		if (del == s->root)
+			s->root = least;
+
+		SPTREE(replace_right)(del, least);
+		SPTREE(update)(s, sp_right(least));
+		return;
+	}
+
+	if (sp_left(del)) {
+		struct SPNODE *most = SPTREE(last)(sp_left(del));
+
+		if (del == s->root)
+			s->root = most;
+
+		SPTREE(replace_left)(del, most);
+		SPTREE(update)(s, sp_left(most));
+		return;
+	}
+
+	if (del == s->root) {
+		s->root = NULL;
+		return;
+	}
+
+	/* empty node */
+	struct SPNODE *paren = sp_paren(del);
+
+	if (sp_left(paren) == del)
+		sp_left(paren) = NULL;
+	else
+		sp_right(paren) = NULL;
+
+	SPTREE(update)(s, paren);
+}
+
+static inline void SPTREE(remove)(struct SPROOT *s, SPTREE_TYPE data)
+{
+	SPTREE_TYPE *found = SPTREE(find)(s, data);
+	if (!found)
+		return;
+
+	SPTREE(remove_found)(s, found);
+	struct SPNODE *del = CONTAINER_OF(found, struct SPNODE, data);
+	free(del);
+}
+
+static inline void SPTREE(destroy)(struct SPROOT *s)
+{
+	while (s->root) {
+		SPTREE_TYPE *top = &s->root->data;
+		SPTREE(remove_found)(s, top);
+		struct SPNODE *del = CONTAINER_OF(top, struct SPNODE, data);
+		free(del);
+	}
+}
+
+#undef SPTREE
+#undef SPNODE
+#undef SPROOT
+#undef SPTREE_NAME
+#undef SPTREE_TYPE
+#undef SPTREE_CMP