aboutsummaryrefslogtreecommitdiffstats
path: root/src/semantic.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/semantic.c')
-rw-r--r--src/semantic.c1592
1 files changed, 1141 insertions, 451 deletions
diff --git a/src/semantic.c b/src/semantic.c
index fe88249..428cc53 100644
--- a/src/semantic.c
+++ b/src/semantic.c
@@ -1,544 +1,1234 @@
1#include "hashtable.h" 1#include "badlib.h"
2 2
3typedef struct Scope { 3typedef enum {
4 size_t id; 4 SYM_UNKNOWN,
5 struct Scope *parent; 5 SYM_BUILTIN_FUN,
6 HashTable *symbols; 6 SYM_BUILTIN_TYPE,
7 HashTable *types; 7 SYM_FUN,
8} Scope; 8 SYM_VAR,
9 SYM_PARAM,
10 SYM_ENUM,
11 SYM_ENUM_FIELD,
12 SYM_STRUCT,
13 SYM_STRUCT_FIELD,
14} SymbolKind;
9 15
10typedef struct ParseTree { 16Str sym_kind_str[] = {
11 Root *roots; 17 [SYM_UNKNOWN] = cstr("UNKNOWN "),
12 Scope **scopes; 18 [SYM_BUILTIN_FUN] = cstr("BUILTIN FUN "),
13} ParseTree; 19 [SYM_BUILTIN_TYPE] = cstr("BUILTIN TYPE "),
14 20 [SYM_FUN] = cstr("FUNCTION "),
15typedef struct Type { 21 [SYM_VAR] = cstr("VARIABLE "),
16 StringView name; 22 [SYM_PARAM] = cstr("PARAMETER "),
17 size_t size; // (bytes) 23 [SYM_ENUM] = cstr("ENUM "),
18} Type; 24 [SYM_ENUM_FIELD] = cstr("ENUM FIELD "),
19 25 [SYM_STRUCT] = cstr("STRUCT "),
20typedef enum DefaultType { 26 [SYM_STRUCT_FIELD] = cstr("STRUCT FIELD "),
21 TYPE_VOID,
22 TYPE_BOOL,
23 TYPE_STR,
24 TYPE_U8,
25 TYPE_U16,
26 TYPE_U32,
27 TYPE_U64,
28 TYPE_S8,
29 TYPE_S16,
30 TYPE_S32,
31 TYPE_S64,
32 TYPE_F32,
33 TYPE_F64,
34} DefaultType;
35
36static Type default_types[] = {
37 [TYPE_VOID] = {STRING("void"), 0},
38 [TYPE_BOOL] = {STRING("bool"), 1},
39 [TYPE_STR] = {STRING("str"), 16}, // size (8) + pointer to data (8).
40 [TYPE_U8] = {STRING("u8"), 1},
41 [TYPE_U16] = {STRING("u16"), 2},
42 [TYPE_U32] = {STRING("u32"), 4},
43 [TYPE_U64] = {STRING("u64"), 8},
44 [TYPE_S8] = {STRING("s8"), 1},
45 [TYPE_S16] = {STRING("s16"), 2},
46 [TYPE_S32] = {STRING("s32"), 4},
47 [TYPE_S64] = {STRING("s64"), 8},
48 [TYPE_F32] = {STRING("f32"), 4},
49 [TYPE_F64] = {STRING("f64"), 8},
50}; 27};
51 28
52typedef enum SymbolType {
53 SYMBOL_VAR,
54 SYMBOL_PAR,
55 SYMBOL_FUN,
56} SymbolType;
57
58typedef struct Symbol { 29typedef struct Symbol {
59 Node *name; 30 Str name;
60 SymbolType type; 31 SymbolKind kind;
61
62 union {
63 struct {
64 Node *type;
65 } var;
66
67 struct {
68 Node **param_types;
69 Node *return_type;
70 } fun;
71 };
72} Symbol; 32} Symbol;
73 33
74static size_t scope_gen_id = 0; 34typedef struct Fun {
35 Str name;
36 Str param_type;
37 Str return_type;
38} Fun;
75 39
76Symbol * 40typedef struct Enum {
77alloc_symval(Node *name, SymbolType type) { 41 Str name;
78 Symbol *val = malloc(sizeof(Symbol)); 42 Node *val;
79 val->name = name; 43} Enum;
80 val->type = type;
81 return val;
82}
83 44
84u64 sym_hash(const struct HashTable *table, void *bytes) { 45typedef struct Struct {
85 Node *symbol = bytes; 46 Str name;
86 u64 hash = _xor_shift_hash(symbol->string.start, symbol->string.n); 47 Str type;
87 hash = _fibonacci_hash(hash, table->shift_amount); 48 Node *val;
88 return hash; 49} Struct;
89}
90 50
91bool sym_eq(void *a, void *b) { 51MAPDEF(SymbolMap, symmap, Str, Symbol, str_hash, str_eq)
92 Node *a_node = a; 52MAPDEF(FunMap, funmap, Str, Fun, str_hash, str_eq)
93 Node *b_node = b; 53MAPDEF(EnumMap, enummap, Str, Enum, str_hash, str_eq)
94 assert(a_node->type == NODE_SYMBOL); 54MAPDEF(StructMap, structmap, Str, Struct, str_hash, str_eq)
95 assert(b_node->type == NODE_SYMBOL);
96 return sv_equal(&a_node->string, &b_node->string);
97}
98 55
99u64 type_hash(const struct HashTable *table, void *bytes) { 56typedef struct Scope {
100 StringView *type = bytes; 57 sz id;
101 u64 hash = _xor_shift_hash(type->start, type->n); 58 sz depth;
102 hash = _fibonacci_hash(hash, table->shift_amount); 59 Str name;
103 return hash; 60 SymbolMap *symbols;
104} 61 FunMap *funcs;
62 EnumMap *enums;
63 StructMap *structs;
64 struct Scope *parent;
65} Scope;
105 66
106bool type_eq(void *a, void *b) { 67typedef struct Analyzer {
107 StringView *a_type = a; 68 Arena *storage;
108 StringView *b_type = b; 69 Str file_name;
109 return sv_equal(a_type, b_type); 70 sz typescope_gen;
110} 71 Scope **scopes;
72 StrSet *numeric_types;
73 StrSet *integer_types;
74 bool err;
75} Analyzer;
111 76
112Scope * 77Scope *
113alloc_scope(Scope *parent) { 78typescope_alloc(Analyzer *a, Scope *parent) {
114 Scope *scope = malloc(sizeof(Scope)); 79 Scope *scope = arena_calloc(sizeof(Scope), a->storage);
115 scope->id = scope_gen_id++;
116 scope->parent = parent; 80 scope->parent = parent;
117 scope->symbols = ht_init(sym_hash, sym_eq); 81 scope->id = a->typescope_gen++;
118 scope->types = ht_init(type_hash, type_eq); 82 scope->depth = parent == NULL ? 0 : parent->depth + 1;
83 array_push(a->scopes, scope, a->storage);
119 return scope; 84 return scope;
120} 85}
121 86
122Type * 87SymbolMap *
123find_type(Scope *scope, Node *type) { 88find_type(Scope *scope, Str type) {
124 // TODO: Normally default types will be used more often. Since we don't
125 // allow type shadowing, we should search first on the global scope.
126 while (scope != NULL) { 89 while (scope != NULL) {
127 Type *ret = ht_lookup(scope->types, &type->string); 90 SymbolMap *val = symmap_lookup(&scope->symbols, type);
128 if (ret != NULL) { 91 if (val != NULL) {
129 return ret; 92 return val;
130 } 93 }
131 scope = scope->parent; 94 scope = scope->parent;
132 } 95 }
133 push_error(ERR_TYPE_SEMANTIC, ERR_UNKNOWN_TYPE, type->line, type->col);
134 return NULL; 96 return NULL;
135} 97}
136 98
137bool 99FunMap *
138insert_symbol(Scope *scope, Node *symbol, Symbol *val) { 100find_fun(Scope *scope, Str type) {
139 // Check if symbol already exists. 101 while (scope != NULL) {
140 HashTable *symbols = scope->symbols; 102 FunMap *val = funmap_lookup(&scope->funcs, type);
141 if (ht_lookup(symbols, symbol) != NULL) { 103 if (val != NULL) {
142 push_error(ERR_TYPE_SEMANTIC, ERR_SYMBOL_REDEF, symbol->line, symbol->col); 104 return val;
143 return false; 105 }
106 scope = scope->parent;
144 } 107 }
145 ht_insert(symbols, symbol, val); 108 return NULL;
146 return true;
147} 109}
148 110
149Type * 111typedef struct FindEnumResult {
150coerce_numeric_types(Type *a, Type *b) { 112 EnumMap *map;
151 // TODO: Decide what to do with mixed numeric types. What are the promotion 113 Scope *scope;
152 // rules, etc. 114} FindEnumResult;
153 if (a == &default_types[TYPE_U8]) { 115
154 if (b == &default_types[TYPE_U16] || 116FindEnumResult
155 b == &default_types[TYPE_U32] || 117find_enum(Scope *scope, Str type) {
156 b == &default_types[TYPE_U64]) { 118 while (scope != NULL) {
157 return b; 119 EnumMap *val = enummap_lookup(&scope->enums, type);
158 } 120 if (val != NULL) {
159 } else if (a == &default_types[TYPE_U16]) { 121 return (FindEnumResult){.map = val, .scope = scope};
160 if (b == &default_types[TYPE_U32] ||
161 b == &default_types[TYPE_U64]) {
162 return b;
163 }
164 } else if (a == &default_types[TYPE_U32]) {
165 if (b == &default_types[TYPE_U64]) {
166 return b;
167 } 122 }
168 } else if (a == &default_types[TYPE_S8]) { 123 scope = scope->parent;
169 if (b == &default_types[TYPE_S16] || 124 }
170 b == &default_types[TYPE_S32] || 125 return (FindEnumResult){0};
171 b == &default_types[TYPE_S64]) { 126}
172 return b; 127
128typedef struct FindStructResult {
129 StructMap *map;
130 Scope *scope;
131} FindStructResult;
132
133FindStructResult
134find_struct(Scope *scope, Str type) {
135 while (scope != NULL) {
136 StructMap *val = structmap_lookup(&scope->structs, type);
137 if (val != NULL) {
138 return (FindStructResult){.map = val, .scope = scope};
173 } 139 }
174 } else if (a == &default_types[TYPE_S16]) { 140 scope = scope->parent;
175 if (b == &default_types[TYPE_S32] || 141 }
176 b == &default_types[TYPE_S64]) { 142 return (FindStructResult){0};
177 return b; 143}
144
145void
146graph_typescope(Scope *scope, Arena a) {
147 if (!scope->symbols) {
148 return;
149 }
150 SymbolMapIter iter = symmap_iterator(scope->symbols, &a);
151 SymbolMap *type = symmap_next(&iter, &a);
152 print(
153 "%d[shape=\"none\" label=<<TABLE ALIGN=\"left\" STYLE=\"rounded\" "
154 "BORDER=\"1\" CELLBORDER=\"0\" CELLSPACING=\"0\" CELLPADDING=\"6\" "
155 "COLUMNS=\"*\">",
156 scope->id);
157 print(
158 "<TR >"
159 "<TD ALIGN=\"left\" > NAME </TD>"
160 "<TD ALIGN=\"left\" > TYPE </TD>"
161 "</TR>");
162 while (type) {
163 print(
164 "<TR>"
165 "<TD ALIGN=\"left\"> %s </TD>"
166 "<TD ALIGN=\"left\"> %s</TD>"
167 "</TR>",
168 type->key, type->val.name);
169 type = symmap_next(&iter, &a);
170 }
171 println("</TABLE>>];");
172
173 sz this_id = scope->id;
174 while (scope->parent) {
175 if (scope->parent->symbols) {
176 println("%d:e->%d:w;", this_id, scope->parent->id);
177 break;
178 } else {
179 scope = scope->parent;
178 } 180 }
179 } else if (a == &default_types[TYPE_S32]) { 181 }
180 if (b == &default_types[TYPE_S64]) { 182}
181 return b; 183
184void
185graph_functions(Scope *scope, Arena a) {
186 if (!scope->funcs) {
187 return;
188 }
189 FunMapIter iter = funmap_iterator(scope->funcs, &a);
190 FunMap *func = funmap_next(&iter, &a);
191 print(
192 "fun_%d[shape=\"none\" label=<<TABLE ALIGN=\"left\" STYLE=\"rounded\" "
193 "BORDER=\"1\" CELLBORDER=\"0\" CELLSPACING=\"0\" CELLPADDING=\"6\" "
194 "COLUMNS=\"*\">",
195 scope->id);
196 print(
197 "<TR >"
198 "<TD ALIGN=\"left\" > NAME </TD>"
199 "<TD ALIGN=\"left\" > PARAMS </TD>"
200 "<TD ALIGN=\"left\" > RETURN </TD>"
201 "</TR>");
202 while (func) {
203 print(
204 "<TR>"
205 "<TD PORT=\"%s\" ALIGN=\"left\" > %s </TD>"
206 "<TD ALIGN=\"left\" > %s </TD>"
207 "<TD ALIGN=\"left\" > %s </TD>"
208 "</TR>",
209 func->val.name, func->val.name, func->val.param_type,
210 func->val.return_type);
211 func = funmap_next(&iter, &a);
212 }
213 println("</TABLE>>];");
214 sz this_id = scope->id;
215 while (scope->parent) {
216 if (scope->parent->symbols) {
217 println("fun_%d:e->fun_%d:%s:w;", this_id, scope->parent->id,
218 scope->name);
219 break;
220 } else {
221 scope = scope->parent;
182 } 222 }
183 } else if (a == &default_types[TYPE_F32]) { 223 }
184 if (b == &default_types[TYPE_F64]) { 224}
185 return b; 225
226void
227graph_types(Scope **scopes, Arena a) {
228 if (scopes == NULL) return;
229 println("digraph types {");
230 println("rankdir=LR;");
231 println("ranksep=\"0.95 equally\";");
232 println("nodesep=\"0.5 equally\";");
233 println("overlap=scale;");
234 println("bgcolor=\"transparent\";");
235 for (sz i = 0; i < array_size(scopes); i++) {
236 Scope *scope = scopes[i];
237 if (!scope) {
238 continue;
186 } 239 }
240 println("subgraph %d {", i);
241 graph_typescope(scope, a);
242 graph_functions(scope, a);
243 println("}");
187 } 244 }
188 return a; 245 println("}");
246}
247
248void
249emit_semantic_error(Analyzer *a, Node *n, Str msg) {
250 eprintln("%s:%d:%d: error: %s", a->file_name, n->line, n->col, msg);
251 a->err = true;
189} 252}
190 253
191bool 254Str type_inference(Analyzer *a, Node *node, Scope *scope);
192type_is_numeric(Type *t) { 255
193 if (t == &default_types[TYPE_U8] || 256void
194 t == &default_types[TYPE_U16] || 257typecheck_field(Analyzer *a, Node *node, Scope *scope, Str symbol) {
195 t == &default_types[TYPE_U32] || 258 if (node->field_type->kind == NODE_COMPOUND_TYPE) {
196 t == &default_types[TYPE_U64] || 259 Str field_name = str_concat(symbol, cstr("."), a->storage);
197 t == &default_types[TYPE_S8] || 260 field_name = str_concat(field_name, node->value.str, a->storage);
198 t == &default_types[TYPE_S16] || 261 if (structmap_lookup(&scope->structs, field_name)) {
199 t == &default_types[TYPE_S32] || 262 eprintln("%s:%d:%d: error: struct field '%s' already exists",
200 t == &default_types[TYPE_S64] || 263 a->file_name, node->line, node->col, field_name);
201 t == &default_types[TYPE_F32] || 264 a->err = true;
202 t == &default_types[TYPE_F64]) { 265 }
203 return true; 266 Str type = cstr("\\{ ");
267 for (sz i = 0; i < array_size(node->field_type->elements); i++) {
268 Node *field = node->field_type->elements[i];
269 typecheck_field(a, field, scope, field_name);
270 type = str_concat(type, field->type, a->storage);
271 type = str_concat(type, cstr(" "), a->storage);
272 }
273 type = str_concat(type, cstr("\\}"), a->storage);
274 node->type = type;
275 } else {
276 Str field_name = str_concat(symbol, cstr("."), a->storage);
277 field_name = str_concat(field_name, node->value.str, a->storage);
278 Str field_type = node->field_type->value.str;
279 if (!find_type(scope, field_type)) {
280 eprintln("%s:%d:%d: error: unknown type '%s'", a->file_name,
281 node->field_type->line, node->field_type->col, field_type);
282 a->err = true;
283 }
284 if (node->field_type->is_ptr) {
285 field_type = str_concat(cstr("@"), field_type, a->storage);
286 }
287 if (node->field_type->kind == NODE_ARR_TYPE) {
288 field_type = str_concat(cstr("@"), field_type, a->storage);
289 }
290 if (structmap_lookup(&scope->structs, field_name)) {
291 eprintln("%s:%d:%d: error: struct field '%s' already exists",
292 a->file_name, node->line, node->col, field_name);
293 a->err = true;
294 }
295 if (node->field_val) {
296 Str type = type_inference(a, node->field_val, scope);
297 if (!str_eq(type, field_type)) {
298 eprintln(
299 "%s:%d:%d: error: mismatched types in struct "
300 "value "
301 "for '%s': %s expected %s",
302 a->file_name, node->line, node->col, field_name, type,
303 field_type);
304 a->err = true;
305 }
306 }
307 structmap_insert(&scope->structs, field_name,
308 (Struct){
309 .name = field_name,
310 .type = field_type,
311 .val = node->field_val,
312 },
313 a->storage);
314 symmap_insert(&scope->symbols, field_name,
315 (Symbol){.name = field_type, .kind = SYM_STRUCT_FIELD},
316 a->storage);
317 node->type = field_type;
204 } 318 }
205 return false;
206} 319}
207 320
208Symbol * 321void
209find_symbol(Scope *scope, Node *node) { 322typecheck_lit_field(Analyzer *a, Node *node, Scope *scope, Str symbol) {
210 while (scope != NULL) { 323 if (node->field_val->kind == NODE_COMPOUND_TYPE) {
211 Symbol *val = ht_lookup(scope->symbols, node); 324 Str type = cstr("\\{ ");
212 if (val != NULL) { 325 for (sz i = 0; i < array_size(node->field_val->elements); i++) {
213 return val; 326 Node *field = node->field_val->elements[i];
327 Str field_name = str_concat(symbol, cstr("."), a->storage);
328 field_name = str_concat(field_name, field->value.str, a->storage);
329 typecheck_lit_field(a, field, scope, field_name);
330 type = str_concat(type, field->type, a->storage);
331 type = str_concat(type, cstr(" "), a->storage);
214 } 332 }
215 scope = scope->parent; 333 type = str_concat(type, cstr("\\}"), a->storage);
334 node->type = type;
335 } else {
336 StructMap *s = structmap_lookup(&scope->structs, symbol);
337 if (!s) {
338 eprintln("%s:%d:%d: error: unknown struct field '%s'", a->file_name,
339 node->line, node->col, symbol);
340 a->err = true;
341 return;
342 }
343 Str field_type = s->val.type;
344 Str type = type_inference(a, node->field_val, scope);
345 if (!str_eq(type, field_type)) {
346 eprintln(
347 "%s:%d:%d: error: mismatched types in struct "
348 "value "
349 "for '%s': %s expected %s",
350 a->file_name, node->line, node->col, symbol, type, field_type);
351 a->err = true;
352 }
353 node->type = field_type;
216 } 354 }
217 push_error(ERR_TYPE_SEMANTIC, ERR_UNKNOWN_SYMBOL, node->line, node->col);
218 return NULL;
219} 355}
220 356
221bool 357void
222resolve_type(ParseTree *ast, Scope *scope, Node *node) { 358typecheck_returns(Analyzer *a, Node *node, Str expected) {
223 if (node->expr_type != NULL) { 359 if (!node) {
224 return true; 360 return;
225 } 361 }
226 switch (node->type) { 362 // Traverse the tree again.
227 case NODE_BUILTIN: { 363 switch (node->kind) {
228 for (size_t i = 0; i < array_size(node->builtin.args); ++i) { 364 case NODE_COND:
229 Node *arg = node->builtin.args[i]; 365 case NODE_MATCH: {
230 if (!resolve_type(ast, scope, arg)) { 366 for (sz i = 0; i < array_size(node->match_cases); i++) {
231 return false; 367 Node *next = node->match_cases[i];
232 } 368 typecheck_returns(a, next, expected);
233 } 369 }
234 switch (node->builtin.type) { 370 } break;
235 // Numbers. 371 case NODE_RETURN: {
236 case TOKEN_ADD: 372 bool err = !str_eq(node->type, expected);
237 case TOKEN_SUB: 373 if (err) {
238 case TOKEN_MUL: 374 eprintln(
239 case TOKEN_DIV: 375 "%s:%d:%d: error: mismatched return type %s, expected %s",
240 case TOKEN_MOD: { 376 a->file_name, node->line, node->col, node->type, expected);
241 Type *type = NULL; 377 a->err = true;
242 for (size_t i = 0; i < array_size(node->builtin.args); ++i) { 378 }
243 Node *arg = node->builtin.args[i]; 379 } break;
244 380 case NODE_BLOCK: {
245 // Check that all arguments are numbers. 381 for (sz i = 0; i < array_size(node->elements); i++) {
246 if (!type_is_numeric(arg->expr_type)) { 382 Node *next = node->elements[i];
247 push_error(ERR_TYPE_SEMANTIC, ERR_WRONG_TYPE_NUM, 383 typecheck_returns(a, next, expected);
248 arg->line, arg->col); 384 }
249 return false; 385 } break;
250 } 386 case NODE_IF: {
387 if (node->cond_expr) {
388 typecheck_returns(a, node->cond_expr, expected);
389 }
390 if (node->cond_else) {
391 typecheck_returns(a, node->cond_else, expected);
392 }
393 } break;
394 case NODE_SET:
395 case NODE_LET: {
396 if (node->var_val) {
397 typecheck_returns(a, node->var_val, expected);
398 }
399 } break;
400 case NODE_ADD:
401 case NODE_SUB:
402 case NODE_DIV:
403 case NODE_MUL:
404 case NODE_MOD:
405 case NODE_NOT:
406 case NODE_AND:
407 case NODE_OR:
408 case NODE_EQ:
409 case NODE_NEQ:
410 case NODE_LT:
411 case NODE_GT:
412 case NODE_LE:
413 case NODE_GE:
414 case NODE_BITNOT:
415 case NODE_BITAND:
416 case NODE_BITOR:
417 case NODE_BITLSHIFT:
418 case NODE_BITRSHIFT: {
419 if (node->left) {
420 typecheck_returns(a, node->left, expected);
421 }
422 if (node->right) {
423 typecheck_returns(a, node->right, expected);
424 }
425 } break;
426 default: break;
427 }
428}
251 429
252 if (type == NULL) { 430Str
253 type = arg->expr_type; 431type_inference(Analyzer *a, Node *node, Scope *scope) {
254 } else if (type != arg->expr_type) { 432 assert(a);
255 type = coerce_numeric_types(type, arg->expr_type); 433 assert(scope);
256 } 434 if (!node) {
435 return cstr("");
436 }
437 // NOTE: For now we are not going to do implicit numeric conversions.
438 switch (node->kind) {
439 case NODE_LET: {
440 node->type = cstr("nil");
441 Str symbol = node->var_name->value.str;
442 if (symmap_lookup(&scope->symbols, symbol)) {
443 eprintln(
444 "%s:%d:%d: error: symbol '%s' already exists in current "
445 "scope ",
446 a->file_name, node->var_name->line, node->var_name->col,
447 symbol);
448 a->err = true;
449 return cstr("");
450 }
451 if (node->var_type) {
452 Str type_name = node->var_type->value.str;
453 SymbolMap *type = find_type(scope, type_name);
454 if (type == NULL) {
455 eprintln("%s:%d:%d: error: unknown type '%s'", a->file_name,
456 node->var_type->line, node->var_type->col,
457 type_name);
458 a->err = true;
459 return cstr("");
460 }
461 if (node->var_type->is_ptr) {
462 type_name = str_concat(cstr("@"), type_name, a->storage);
463 }
464 if (node->var_type->kind == NODE_ARR_TYPE) {
465 type_name = str_concat(cstr("@"), type_name, a->storage);
466 // TODO: typecheck size
467 // TODO: register array in scope
468 }
469 if (node->var_val) {
470 Str type = type_inference(a, node->var_val, scope);
471 if (!type.size) {
472 eprintln(
473 "%s:%d:%d: error: can't bind `nil` to variable "
474 "'%s'",
475 a->file_name, node->var_type->line,
476 node->var_type->col, symbol);
477 a->err = true;
478 return cstr("");
257 } 479 }
258 node->expr_type = type; 480 // TODO: Consider compatible types.
259 } break; 481 if (!str_eq(type, type_name)) {
260 // Bools. 482 // Special case, enums can be treated as ints.
261 case TOKEN_NOT: 483 FindEnumResult res = find_enum(scope, type_name);
262 // TODO: not should only take one argument and 484 if (!(res.map && str_eq(type, cstr("int")))) {
263 // return the inverse. 485 eprintln(
264 case TOKEN_AND: 486 "%s:%d:%d: error: type mismatch, trying to "
265 case TOKEN_OR: { 487 "assing "
266 // Check that all arguments are boolean. 488 "%s"
267 for (size_t i = 0; i < array_size(node->builtin.args); ++i) { 489 " to a variable of type %s",
268 Node *arg = node->builtin.args[i]; 490 a->file_name, node->var_type->line,
269 if (arg->expr_type != &default_types[TYPE_BOOL]) { 491 node->var_type->col, type, type_name);
270 push_error(ERR_TYPE_SEMANTIC, ERR_WRONG_TYPE_BOOL, 492 a->err = true;
271 arg->line, arg->col); 493 return cstr("");
272 return false;
273 } 494 }
274 } 495 }
275 node->expr_type = &default_types[TYPE_BOOL]; 496 }
276 } break; 497 symmap_insert(&scope->symbols, symbol,
277 case TOKEN_EQ: 498 (Symbol){
278 case TOKEN_LT: 499 .name = type_name,
279 case TOKEN_GT: 500 .kind = SYM_VAR,
280 case TOKEN_LE: 501 },
281 case TOKEN_GE: { 502 a->storage);
282 // Check that all arguments are nums. 503 return node->type;
283 for (size_t i = 0; i < array_size(node->builtin.args); ++i) { 504 }
284 Node *arg = node->builtin.args[i]; 505
285 // TODO: Make sure all arguments have the same type, 506 // We don't know the type for this symbol, perform inference.
286 // like with numeric expressions. 507 Str type = type_inference(a, node->var_val, scope);
287 if (!type_is_numeric(arg->expr_type)) { 508 if (type.size) {
288 push_error(ERR_TYPE_SEMANTIC, ERR_WRONG_TYPE_NUM, 509 symmap_insert(&scope->symbols, symbol,
289 arg->line, arg->col); 510 (Symbol){.name = type, .kind = SYM_VAR},
290 return false; 511 a->storage);
291 } 512 node->var_name->type = type;
513 }
514 return node->type;
515 } break;
516 case NODE_SET: {
517 Str name = type_inference(a, node->var_name, scope);
518 Str val = type_inference(a, node->var_val, scope);
519 if (!str_eq(name, val)) {
520 eprintln(
521 "%s:%d:%d: error: type mismatch, trying to assing "
522 "%s"
523 " to a variable of type %s",
524 a->file_name, node->line, node->col, val, name);
525 a->err = true;
526 return cstr("");
527 }
528 node->type = cstr("nil");
529 return node->type;
530 } break;
531 case NODE_STRUCT: {
532 node->type = cstr("nil");
533 Str symbol = node->value.str;
534 if (symmap_lookup(&scope->symbols, symbol) != NULL) {
535 eprintln(
536 "%s:%d:%d: error: struct '%s' already exists in current "
537 "scope",
538 a->file_name, node->line, node->col, symbol);
539 a->err = true;
540 return cstr("");
541 }
542 structmap_insert(&scope->structs, symbol, (Struct){.name = symbol},
543 a->storage);
544 for (sz i = 0; i < array_size(node->struct_field); i++) {
545 Node *field = node->struct_field[i];
546 typecheck_field(a, field, scope, symbol);
547 }
548 symmap_insert(&scope->symbols, symbol,
549 (Symbol){.name = symbol, .kind = SYM_STRUCT},
550 a->storage);
551 return node->type;
552 } break;
553 case NODE_ENUM: {
554 node->type = cstr("nil");
555 Str symbol = node->value.str;
556 if (symmap_lookup(&scope->symbols, symbol) != NULL) {
557 eprintln(
558 "%s:%d:%d: error: enum '%s' already exists in current "
559 "scope",
560 a->file_name, node->line, node->col, symbol);
561 a->err = true;
562 return cstr("");
563 }
564 enummap_insert(&scope->enums, symbol,
565 (Enum){
566 .name = symbol,
567 .val = node->field_val,
568 },
569 a->storage);
570 for (sz i = 0; i < array_size(node->struct_field); i++) {
571 Node *field = node->struct_field[i];
572 Str field_name = str_concat(symbol, cstr("."), a->storage);
573 field_name =
574 str_concat(field_name, field->value.str, a->storage);
575 if (enummap_lookup(&scope->enums, field_name)) {
576 eprintln("%s:%d:%d: error: enum field '%s' already exists",
577 a->file_name, field->line, field->col, field_name);
578 a->err = true;
579 }
580 if (field->field_val) {
581 Str type = type_inference(a, field->field_val, scope);
582 if (!str_eq(type, cstr("int"))) {
583 eprintln(
584 "%s:%d:%d: error: non int enum value for '%s.%s'",
585 a->file_name, field->line, field->col, symbol,
586 field_name);
587 a->err = true;
292 } 588 }
293 node->expr_type = &default_types[TYPE_BOOL]; 589 }
294 } break; 590 enummap_insert(&scope->enums, field_name,
295 default: break; 591 (Enum){.name = field_name}, a->storage);
592 symmap_insert(
593 &scope->symbols, field_name,
594 (Symbol){.name = field_name, .kind = SYM_ENUM_FIELD},
595 a->storage);
596 field->type = symbol;
296 } 597 }
598 symmap_insert(&scope->symbols, symbol,
599 (Symbol){.name = symbol, .kind = SYM_ENUM},
600 a->storage);
601 return node->type;
297 } break; 602 } break;
298 case NODE_SYMBOL: { 603 case NODE_IF: {
299 Symbol *val = find_symbol(scope, node); 604 Str cond_type = type_inference(a, node->cond_if, scope);
300 if (val == NULL) { 605 if (!str_eq(cond_type, cstr("bool"))) {
301 return false; 606 emit_semantic_error(
607 a, node->cond_if,
608 cstr("non boolean expression on if condition"));
609 return cstr("");
302 } 610 }
303 611 if (node->cond_expr->kind == NODE_BLOCK) {
304 Type *type = NULL; 612 node->type = type_inference(a, node->cond_expr, scope);
305 switch (val->type) { 613 } else {
306 case SYMBOL_PAR: 614 Scope *next = typescope_alloc(a, scope);
307 case SYMBOL_VAR: { 615 node->type = type_inference(a, node->cond_expr, next);
308 type = find_type(scope, val->var.type);
309 } break;
310 case SYMBOL_FUN: {
311 type = find_type(scope, val->fun.return_type);
312 } break;
313 } 616 }
314 if (type == NULL) { 617 if (node->cond_else) {
315 return false; 618 Str else_type;
619 if (node->cond_else->kind == NODE_BLOCK) {
620 else_type = type_inference(a, node->cond_else, scope);
621 } else {
622 Scope *next = typescope_alloc(a, scope);
623 else_type = type_inference(a, node->cond_else, next);
624 }
625 if (!str_eq(node->type, else_type)) {
626 emit_semantic_error(
627 a, node, cstr("mismatch types for if/else branches"));
628 return cstr("");
629 }
316 } 630 }
317 node->expr_type = type; 631 return node->type;
318 } break; 632 } break;
319 case NODE_FUN: { 633 case NODE_WHILE: {
320 // TODO: don't allow parameters of type void 634 Str cond_type = type_inference(a, node->while_cond, scope);
321 node->expr_type = &default_types[TYPE_VOID]; 635 if (!str_eq(cond_type, cstr("bool"))) {
322 636 emit_semantic_error(
323 // Fill up new scope with parameters 637 a, node->cond_if,
324 scope = alloc_scope(scope); 638 cstr("non boolean expression on while condition"));
325 array_push(ast->scopes, scope); 639 return cstr("");
326 640 }
327 // Parameters. 641 if (node->while_expr->kind != NODE_BLOCK) {
328 for (size_t i = 0; i < array_size(node->fun.param_names); ++i) { 642 scope = typescope_alloc(a, scope);
329 Node *param = node->fun.param_names[i]; 643 }
330 Node *type = node->fun.param_types[i]; 644 type_inference(a, node->while_expr, scope);
331 Symbol *var = alloc_symval(param, SYMBOL_PAR); 645 node->type = cstr("nil");
332 var->var.type = type; 646 return node->type;
333 if (!insert_symbol(scope, param, var)) { 647 } break;
334 return false; 648 case NODE_COND: {
649 Str previous = cstr("");
650 for (sz i = 0; i < array_size(node->match_cases); i++) {
651 Node *expr = node->match_cases[i];
652 Str next = type_inference(a, expr, scope);
653 if (i != 0 && !str_eq(next, previous)) {
654 emit_semantic_error(
655 a, node,
656 cstr("non-matching types for cond expressions"));
657 return cstr("");
335 } 658 }
659 previous = next;
336 } 660 }
337 661 node->type = previous;
338 // Body. 662 return node->type;
339 Node *body = node->fun.body; 663 } break;
340 if (body->type == NODE_BLOCK) { 664 case NODE_MATCH: {
341 for (size_t i = 0; i < array_size(body->block.expr); ++i) { 665 Str e = type_inference(a, node->match_expr, scope);
342 Node *expr = body->block.expr[i]; 666 if (str_eq(e, cstr("int"))) {
343 if (!resolve_type(ast, scope, expr)) { 667 // Integer matching.
344 return false; 668 for (sz i = 0; i < array_size(node->match_cases); i++) {
669 Node *field = node->match_cases[i];
670 if (field->case_value) {
671 if (field->case_value->kind != NODE_NUM_INT &&
672 field->case_value->kind != NODE_NUM_UINT) {
673 emit_semantic_error(
674 a, field->case_value,
675 cstr(
676 "non-integer or enum types on match case"));
677 }
345 } 678 }
346 } 679 }
347 Node *last_expr = body->block.expr[array_size(body->block.expr) - 1];
348 node->fun.body->expr_type = last_expr->expr_type;
349 } else { 680 } else {
350 if (!resolve_type(ast, scope, body)) { 681 // Get enum type and de-structure the match.
351 return false; 682 FindEnumResult res = find_enum(scope, e);
683 Str enum_prefix =
684 str_concat(res.map->val.name, cstr("."), a->storage);
685 for (sz i = 0; i < array_size(node->match_cases); i++) {
686 Node *field = node->match_cases[i];
687 if (field->case_value) {
688 Str field_name = str_concat(
689 enum_prefix, field->case_value->value.str,
690 a->storage);
691 if (!enummap_lookup(&res.scope->enums, field_name)) {
692 eprintln("%s:%d:%d: error: unknown enum field '%s'",
693 a->file_name, field->case_value->line,
694 field->case_value->col, field_name);
695 a->err = true;
696 }
697 }
352 } 698 }
353 } 699 }
354 700 Str previous = cstr("");
355 // Check that the type of body matches the return type. 701 for (sz i = 0; i < array_size(node->match_cases); i++) {
356 StringView *type_body = &node->fun.body->expr_type->name; 702 Node *expr = node->match_cases[i];
357 StringView *return_type = &node->fun.return_type->string; 703 Str next = type_inference(a, expr, scope);
358 if (!sv_equal(type_body, return_type)) { 704 if (i != 0 && !str_eq(next, previous)) {
359 push_error(ERR_TYPE_SEMANTIC, ERR_WRONG_RET_TYPE, node->line, node->col); 705 emit_semantic_error(
360 return false; 706 a, node,
707 cstr("non-matching types for match expressions"));
708 return cstr("");
709 }
710 previous = next;
361 } 711 }
712 node->type = previous;
713 return node->type;
362 } break; 714 } break;
363 case NODE_BLOCK: { 715 case NODE_CASE_MATCH: {
364 scope = alloc_scope(scope); 716 if (node->case_expr->kind != NODE_BLOCK) {
365 array_push(ast->scopes, scope); 717 scope = typescope_alloc(a, scope);
366 for (size_t i = 0; i < array_size(node->block.expr); ++i) { 718 }
367 Node *expr = node->block.expr[i]; 719 node->type = type_inference(a, node->case_expr, scope);
368 if (!resolve_type(ast, scope, expr)) { 720 return node->type;
369 return false; 721 } break;
722 case NODE_CASE_COND: {
723 if (node->case_value) {
724 Str cond = type_inference(a, node->case_value, scope);
725 if (!str_eq(cond, cstr("bool"))) {
726 emit_semantic_error(a, node,
727 cstr("non-boolean case condition"));
370 } 728 }
371 } 729 }
372 Node *last_expr = node->block.expr[array_size(node->block.expr) - 1]; 730 if (node->case_expr->kind != NODE_BLOCK) {
373 node->expr_type = last_expr->expr_type; 731 scope = typescope_alloc(a, scope);
732 }
733 node->type = type_inference(a, node->case_expr, scope);
734 return node->type;
374 } break; 735 } break;
375 case NODE_IF: { 736 case NODE_TRUE:
376 // TODO: If we don't have an else, ifexpr.expr_true 737 case NODE_FALSE: {
377 // must be void for consistency. 738 node->type = cstr("bool");
378 if (!resolve_type(ast, scope, node->ifexpr.cond)) { 739 return node->type;
379 return false; 740 } break;
380 } 741 case NODE_NIL: {
381 if (!resolve_type(ast, scope, node->ifexpr.expr_true)) { 742 node->type = cstr("nil");
382 return false; 743 return node->type;
383 } 744 } break;
384 Type *type_true = node->ifexpr.expr_true->expr_type; 745 case NODE_NOT:
385 node->expr_type = type_true; 746 case NODE_AND:
386 if (node->ifexpr.expr_false != NULL) { 747 case NODE_OR: {
387 if (!resolve_type(ast, scope, node->ifexpr.expr_false)) { 748 Str left = type_inference(a, node->left, scope);
388 return false; 749 if (!str_eq(left, cstr("bool"))) {
750 emit_semantic_error(a, node,
751 cstr("expected bool on logic expression"));
752 return cstr("");
753 }
754 if (node->right) {
755 Str right = type_inference(a, node->right, scope);
756 if (!str_eq(right, cstr("bool"))) {
757 emit_semantic_error(
758 a, node, cstr("expected bool on logic expression"));
759 return cstr("");
760 }
761 }
762 node->type = cstr("bool");
763 return node->type;
764 } break;
765 case NODE_EQ:
766 case NODE_NEQ:
767 case NODE_LT:
768 case NODE_GT:
769 case NODE_LE:
770 case NODE_GE: {
771 Str left = type_inference(a, node->left, scope);
772 Str right = type_inference(a, node->right, scope);
773 if (!str_eq(left, right)) {
774 emit_semantic_error(
775 a, node, cstr("mismatched types on binary expression"));
776 return cstr("");
777 }
778 node->type = cstr("bool");
779 return node->type;
780 } break;
781 case NODE_BITNOT: {
782 Str left = type_inference(a, node->left, scope);
783 if (!strset_lookup(&a->integer_types, left)) {
784 emit_semantic_error(
785 a, node, cstr("non integer type on bit twiddling expr"));
786 return cstr("");
787 }
788 node->type = left;
789 return node->type;
790 } break;
791 case NODE_BITAND:
792 case NODE_BITOR:
793 case NODE_BITLSHIFT:
794 case NODE_BITRSHIFT: {
795 Str left = type_inference(a, node->left, scope);
796 Str right = type_inference(a, node->right, scope);
797 if (!strset_lookup(&a->integer_types, left) ||
798 !strset_lookup(&a->integer_types, right)) {
799 emit_semantic_error(
800 a, node, cstr("non integer type on bit twiddling expr"));
801 return cstr("");
802 }
803 node->type = left;
804 return node->type;
805 } break;
806 case NODE_ADD:
807 case NODE_SUB:
808 case NODE_DIV:
809 case NODE_MUL:
810 case NODE_MOD: {
811 Str left = type_inference(a, node->left, scope);
812 Str right = type_inference(a, node->right, scope);
813 if (!strset_lookup(&a->numeric_types, left) ||
814 !strset_lookup(&a->numeric_types, right)) {
815 emit_semantic_error(
816 a, node, cstr("non numeric type on arithmetic expr"));
817 return cstr("");
818 }
819 if (!str_eq(left, right)) {
820 emit_semantic_error(
821 a, node, cstr("mismatched types on binary expression"));
822 return cstr("");
823 }
824 node->type = left;
825 return node->type;
826 } break;
827 case NODE_NUM_UINT: {
828 node->type = cstr("uint");
829 return node->type;
830 } break;
831 case NODE_NUM_INT: {
832 node->type = cstr("int");
833 return node->type;
834 } break;
835 case NODE_NUM_FLOAT: {
836 node->type = cstr("f64");
837 return node->type;
838 } break;
839 case NODE_STRING: {
840 node->type = cstr("str");
841 return node->type;
842 } break;
843 case NODE_ARR_TYPE:
844 case NODE_TYPE: {
845 SymbolMap *type = find_type(scope, node->value.str);
846 if (!type) {
847 emit_semantic_error(a, node, cstr("unknown type"));
848 return cstr("");
849 }
850 node->type = type->val.name;
851 return node->type;
852 } break;
853 case NODE_SYMBOL_IDX:
854 case NODE_SYMBOL: {
855 Str symbol = node->value.str;
856 SymbolMap *type = find_type(scope, symbol);
857 if (!type) {
858 eprintln("%s:%d:%d: error: couldn't resolve symbol '%s'",
859 a->file_name, node->line, node->col, symbol);
860 a->err = true;
861 return cstr("");
862 }
863 Str type_name = type->val.name;
864 if (node->kind == NODE_SYMBOL_IDX) {
865 Str idx_type = type_inference(a, node->arr_size, scope);
866 if (!strset_lookup(&a->integer_types, idx_type)) {
867 emit_semantic_error(
868 a, node, cstr("can't resolve non integer index"));
869 return cstr("");
389 } 870 }
871 type_name = str_remove_prefix(type_name, cstr("@"));
872 }
873 if (node->is_ptr) {
874 type_name = str_concat(cstr("@"), type_name, a->storage);
390 } 875 }
391 876
392 // Check ifexpr.cond is a bool. 877 FindEnumResult e = find_enum(scope, type_name);
393 Type *type_cond = node->ifexpr.cond->expr_type; 878 if (e.map && str_eq(symbol, type_name)) {
394 if (!sv_equal(&type_cond->name, &default_types[TYPE_BOOL].name)) { 879 if (!node->next) {
395 push_error(ERR_TYPE_SEMANTIC, ERR_WRONG_COND_TYPE, 880 eprintln(
396 node->line, node->col); 881 "%s:%d:%d: error: unspecified enum field for symbol "
397 return false; 882 "'%s'",
883 a->file_name, node->line, node->col, symbol);
884 a->err = true;
885 return cstr("");
886 }
887 // Check if there is a next and it matches the enum field.
888 Str field = str_concat(type_name, cstr("."), a->storage);
889 field = str_concat(field, node->next->value.str, a->storage);
890 if (!enummap_lookup(&e.scope->enums, field)) {
891 eprintln(
892 "%s:%d:%d: error: unknown enum field for "
893 "'%s': %s",
894 a->file_name, node->line, node->col, symbol,
895 node->next->value.str);
896 a->err = true;
897 return cstr("");
898 }
899 node->next->type = type_name;
900 node->type = type_name;
901 return node->next->type;
398 } 902 }
399 903
400 // Check if types of expr_true and expr_false match 904 FindStructResult s = find_struct(scope, type_name);
401 if (node->ifexpr.expr_false != NULL) { 905 if (s.map) {
402 Type *type_false = node->ifexpr.expr_false->expr_type; 906 if (str_eq(symbol, type_name)) {
403 if (type_is_numeric(type_true) && type_is_numeric(type_false)) { 907 eprintln(
404 node->expr_type = coerce_numeric_types(type_true, type_false); 908 "%s:%d:%d: error: struct incomplete struct literal "
405 } else if (!sv_equal(&type_true->name, &type_false->name)) { 909 "'%s', did you mean to use %s:{}?",
406 push_error(ERR_TYPE_SEMANTIC, ERR_WRONG_TYPE_T_F, 910 a->file_name, node->line, node->col, symbol, symbol);
407 node->line, node->col); 911 a->err = true;
408 return false; 912 return cstr("");
913 } else {
914 if (node->next) {
915 Str chain = type_name;
916 Node *next = node;
917 while (next->next) {
918 next = next->next;
919 chain = str_concat(chain, cstr("."), a->storage);
920 chain =
921 str_concat(chain, next->value.str, a->storage);
922 }
923 StructMap *field =
924 structmap_lookup(&s.scope->structs, chain);
925 if (!field) {
926 eprintln(
927 "%s:%d:%d: error: unknown struct field '%s'",
928 a->file_name, node->line, node->col, chain);
929 a->err = true;
930 return cstr("");
931 }
932 Str field_type = field->val.type;
933 if (next->kind == NODE_SYMBOL_IDX) {
934 Str idx_type =
935 type_inference(a, next->arr_size, scope);
936 if (!strset_lookup(&a->integer_types, idx_type)) {
937 emit_semantic_error(
938 a, next,
939 cstr("can't resolve non integer index"));
940 return cstr("");
941 }
942 field_type =
943 str_remove_prefix(field_type, cstr("@"));
944 }
945 node->type = field_type;
946 return node->type;
947 }
409 } 948 }
410 } 949 }
950 node->type = type_name;
951 return node->type;
411 } break; 952 } break;
412 case NODE_SET: { 953 case NODE_STRUCT_LIT: {
413 node->expr_type = &default_types[TYPE_VOID]; 954 Str name = node->value.str;
414 if (!resolve_type(ast, scope, node->set.symbol)) { 955 FindStructResult s = find_struct(scope, name);
415 return false; 956 if (!s.map) {
416 } 957 eprintln("%s:%d:%d: error: unknown struct type '%s'",
417 if (!resolve_type(ast, scope, node->set.value)) { 958 a->file_name, node->line, node->col, name);
418 return false; 959 a->err = true;
419 } 960 return cstr("");
420 Node *symbol = node->set.symbol;
421 Node *value = node->set.value;
422 if (!sv_equal(&symbol->expr_type->name, &value->expr_type->name)) {
423 push_error(ERR_TYPE_SEMANTIC, ERR_TYPE_MISMATCH,
424 node->line, node->col);
425 return false;
426 }
427 } break;
428 case NODE_DEF: {
429 // TODO: don't allow assignment of expressions that return void
430 // Prepare value for symbol table.
431 Symbol *var = alloc_symval(node->def.symbol, SYMBOL_VAR);
432 var->var.type = node->def.type;
433 if (!insert_symbol(scope, node->def.symbol, var)) {
434 return false;
435 }
436
437 Type *type = find_type(scope, node->def.type);
438 if (type == NULL) {
439 return false;
440 }
441 node->def.symbol->expr_type = type;
442
443 node->expr_type = &default_types[TYPE_VOID];
444 // TODO: type inference from right side when not annotated?
445 if (!resolve_type(ast, scope, node->def.value)) {
446 return false;
447 }
448 Node *symbol = node->def.symbol;
449 Node *value = node->def.value;
450 if (!sv_equal(&symbol->expr_type->name, &value->expr_type->name)) {
451 push_error(ERR_TYPE_SEMANTIC, ERR_TYPE_MISMATCH,
452 node->line, node->col);
453 return false;
454 }
455 } break;
456 case NODE_NUMBER: {
457 // TODO: Numbers are f64/s64 unless explicitely annotated. Annotated
458 // numbers must fit in the given range (e.g. no negative constants
459 // inside a u64, no numbers bigger than 255 in a u8, etc.).
460 if (node->number.fractional != 0) {
461 // TODO: 1.0 should also be checked as float.
462 node->expr_type = &default_types[TYPE_F64];
463 } else {
464 node->expr_type = &default_types[TYPE_S64];
465 } 961 }
962
963 StrSet *set = NULL;
964 for (sz i = 0; i < array_size(node->elements); i++) {
965 Node *next = node->elements[i];
966 Str field_name = str_concat(name, cstr("."), a->storage);
967 field_name =
968 str_concat(field_name, next->value.str, a->storage);
969
970 if (strset_lookup(&set, field_name)) {
971 eprintln(
972 "%s:%d:%d: error: field '%s' already present in struct "
973 "literal",
974 a->file_name, next->line, next->col, field_name);
975 a->err = true;
976 } else {
977 strset_insert(&set, field_name, a->storage);
978 }
979 typecheck_lit_field(a, next, s.scope, field_name);
980 }
981 node->type = name;
982 return node->type;
466 } break; 983 } break;
467 case NODE_BOOL: { 984 case NODE_FUNCALL: {
468 node->expr_type = &default_types[TYPE_BOOL]; 985 Str symbol = node->value.str;
986 FunMap *fun = find_fun(scope, symbol);
987 if (!fun) {
988 eprintln(
989 "%s:%d:%d: error: function '%s' doesn't exist in current "
990 "scope ",
991 a->file_name, node->line, node->col, symbol);
992 a->err = true;
993 return cstr("");
994 }
995 // Check that actual parameters typecheck
996 Str args = cstr("");
997 for (sz i = 0; i < array_size(node->elements); i++) {
998 Node *expr = node->elements[i];
999 Str type = type_inference(a, expr, scope);
1000 args = str_concat(args, type, a->storage);
1001 if (i != array_size(node->elements) - 1) {
1002 args = str_concat(args, cstr(","), a->storage);
1003 }
1004 }
1005 if (!args.size) {
1006 args = cstr("nil");
1007 }
1008 Str expected = fun->val.param_type;
1009 if (!str_eq(args, expected) && !str_eq(expected, cstr("..."))) {
1010 eprintln(
1011 "%s:%d:%d: error: mismatched parameter types: %s expected "
1012 "%s",
1013 a->file_name, node->line, node->col, args, expected);
1014 a->err = true;
1015 }
1016 node->type = fun->val.return_type;
1017 return node->type;
469 } break; 1018 } break;
470 case NODE_STRING: { 1019 case NODE_BLOCK: {
471 node->expr_type = &default_types[TYPE_STR]; 1020 scope = typescope_alloc(a, scope);
1021 Str type;
1022 for (sz i = 0; i < array_size(node->elements); i++) {
1023 Node *expr = node->elements[i];
1024 type = type_inference(a, expr, scope);
1025 }
1026 node->type = type;
1027 return node->type;
472 } break; 1028 } break;
473 case NODE_FUNCALL: { 1029 case NODE_RETURN: {
474 Symbol *val = find_symbol(scope, node->funcall.name); 1030 Str ret_type = cstr("");
475 if (!resolve_type(ast, scope, node->funcall.name)) { 1031 for (sz i = 0; i < array_size(node->elements); i++) {
476 return false; 1032 Node *expr = node->elements[i];
477 } 1033 Str type = type_inference(a, expr, scope);
478 if (val->type != SYMBOL_FUN) { 1034 ret_type = str_concat(ret_type, type, a->storage);
479 push_error(ERR_TYPE_SEMANTIC, ERR_WRONG_TYPE_FUN, 1035 if (i != array_size(node->elements) - 1) {
480 node->funcall.name->line, node->funcall.name->col); 1036 ret_type = str_concat(ret_type, cstr(","), a->storage);
481 return false; 1037 }
482 } 1038 }
483 if (array_size(node->funcall.args) != array_size(val->fun.param_types)) { 1039 if (!ret_type.size) {
484 push_error(ERR_TYPE_SEMANTIC, ERR_BAD_ARGS, node->line, node->col); 1040 ret_type = cstr("nil");
485 return false; 1041 }
486 } 1042 node->type = ret_type;
487 node->expr_type = node->funcall.name->expr_type; 1043 return node->type;
488 for (size_t i = 0; i < array_size(node->funcall.args); ++i) { 1044 } break;
489 Node *arg = node->funcall.args[i]; 1045 case NODE_FUN: {
490 if (!resolve_type(ast, scope, arg)) { 1046 node->type = cstr("nil");
491 return false; 1047 Scope *prev_scope = scope;
1048 scope = typescope_alloc(a, scope);
1049 Str param_type = cstr("");
1050 for (sz i = 0; i < array_size(node->func_params); i++) {
1051 Node *param = node->func_params[i];
1052 Str symbol = param->param_name->value.str;
1053 Str type = param->param_type->value.str;
1054 if (param->param_type->is_ptr) {
1055 type = str_concat(cstr("@"), type, a->storage);
1056 }
1057 if (param->param_type->kind == NODE_ARR_TYPE) {
1058 type = str_concat(cstr("@"), type, a->storage);
1059 }
1060 param->param_name->type =
1061 type_inference(a, param->param_type, scope);
1062 param->type = type;
1063 symmap_insert(&scope->symbols, symbol,
1064 (Symbol){.name = type, .kind = SYM_PARAM},
1065 a->storage);
1066 param_type = str_concat(param_type, type, a->storage);
1067 if (i != array_size(node->func_params) - 1) {
1068 param_type = str_concat(param_type, cstr(","), a->storage);
1069 }
1070 }
1071 if (!param_type.size) {
1072 param_type = cstr("nil");
1073 }
1074 node->fun_params = param_type;
1075
1076 Str ret_type = cstr("");
1077 for (sz i = 0; i < array_size(node->func_ret); i++) {
1078 Node *expr = node->func_ret[i];
1079 Str type = type_inference(a, expr, scope);
1080 if (expr->is_ptr) {
1081 type = str_concat(cstr("@"), type, a->storage);
1082 }
1083 if (expr->kind == NODE_ARR_TYPE) {
1084 type = str_concat(cstr("@"), type, a->storage);
492 } 1085 }
493 Node *expected = val->fun.param_types[i]; 1086 ret_type = str_concat(ret_type, type, a->storage);
494 if (!sv_equal(&arg->expr_type->name, &expected->string)) { 1087 if (i != array_size(node->func_ret) - 1) {
495 push_error(ERR_TYPE_SEMANTIC, ERR_TYPE_MISMATCH, 1088 ret_type = str_concat(ret_type, cstr(","), a->storage);
496 arg->line, arg->col);
497 return false;
498 } 1089 }
499 } 1090 }
1091 if (!ret_type.size) {
1092 ret_type = cstr("nil");
1093 }
1094 node->fun_return = ret_type;
1095
1096 Str symbol = node->func_name->value.str;
1097 if (prev_scope->parent != NULL) {
1098 if (symmap_lookup(&prev_scope->symbols, symbol)) {
1099 eprintln(
1100 "%s:%d:%d: error: function '%s' already defined in "
1101 "current "
1102 "scope ",
1103 a->file_name, node->var_name->line, node->var_name->col,
1104 symbol);
1105 a->err = true;
1106 return cstr("");
1107 }
1108 symmap_insert(&scope->symbols, symbol,
1109 (Symbol){.name = symbol, .kind = SYM_FUN},
1110 a->storage);
1111 }
1112 scope->name = symbol;
1113 funmap_insert(&prev_scope->funcs, symbol,
1114 (Fun){.name = symbol,
1115 .param_type = param_type,
1116 .return_type = ret_type},
1117 a->storage);
1118
1119 if (node->func_body->kind == NODE_BLOCK) {
1120 Str type;
1121 for (sz i = 0; i < array_size(node->func_body->elements); i++) {
1122 Node *expr = node->func_body->elements[i];
1123 type = type_inference(a, expr, scope);
1124 }
1125 if (!type.size) {
1126 type = cstr("nil");
1127 }
1128 node->func_body->type = type;
1129 } else {
1130 type_inference(a, node->func_body, scope);
1131 }
1132
1133 // Ensure main body return matches the prototype.
1134 if (!str_eq(node->func_body->type, ret_type)) {
1135 eprintln(
1136 "%s:%d:%d: error: mismatched return type %s, expected %s",
1137 a->file_name, node->line, node->col, node->func_body->type,
1138 ret_type);
1139 a->err = true;
1140 }
1141
1142 // Ensure ALL return statements match the function prototype.
1143 typecheck_returns(a, node->func_body, ret_type);
1144
1145 // TODO: should return statements be allowed on let blocks?
1146 return node->type;
1147 } break;
1148 default: {
1149 emit_semantic_error(a, node,
1150 cstr("type inference not implemented for this "
1151 "kind of expression"));
1152 println("KIND: %s", node_str[node->kind]);
500 } break; 1153 } break;
501 default: break;
502 } 1154 }
503 return true; 1155 return cstr("");
504} 1156}
505 1157
506ParseTree * 1158void
507semantic_analysis(Root *roots) { 1159symbolic_analysis(Analyzer *a, Parser *parser) {
508 ParseTree *parse_tree = malloc(sizeof(ParseTree)); 1160 Scope *scope = typescope_alloc(a, NULL);
509 parse_tree->roots = roots; 1161 assert(a);
510 array_init(parse_tree->scopes, 0); 1162 assert(parser);
511 Scope *scope = alloc_scope(NULL);
512 array_push(parse_tree->scopes, scope);
513
514 // Fill global scope with default types.
515 HashTable *types = scope->types;
516 for (size_t i = 0; i < sizeof(default_types)/sizeof(Type); ++i) {
517 Type *type = &default_types[i];
518 ht_insert(types, &type->name, type);
519 }
520 1163
521 // Fill up global function symbols. 1164 // Fill builtin tables.
522 for (size_t i = 0; i < array_size(parse_tree->roots); ++i) { 1165 Str builtin_functions[] = {
523 Node *root = parse_tree->roots[i]; 1166 cstr("print"),
524 if (root->type == NODE_FUN) { 1167 cstr("println"),
525 Node *name = root->fun.name; 1168 };
526 Symbol *fun = alloc_symval(root->fun.name, SYMBOL_FUN); 1169 for (sz i = 0; i < LEN(builtin_functions); i++) {
527 fun->fun.param_types = root->fun.param_types; 1170 Str symbol = builtin_functions[i];
528 fun->fun.return_type = root->fun.return_type; 1171 symmap_insert(&scope->symbols, symbol,
529 if (!insert_symbol(scope, name, fun)) { 1172 (Symbol){.name = symbol, .kind = SYM_BUILTIN_FUN},
530 return NULL; 1173 a->storage);
1174 funmap_insert(&scope->funcs, symbol,
1175 (Fun){.name = symbol,
1176 .param_type = cstr("..."),
1177 .return_type = cstr("nil")},
1178 a->storage);
1179 }
1180 Str builtin_types[] = {
1181 cstr("u8"), cstr("s8"), cstr("u16"), cstr("s16"),
1182 cstr("u32"), cstr("s32"), cstr("u64"), cstr("s64"),
1183 cstr("f32"), cstr("f64"), cstr("ptr"), cstr("int"),
1184 cstr("uint"), cstr("str"), cstr("bool"), cstr("nil")};
1185 for (sz i = 0; i < LEN(builtin_types); i++) {
1186 Str type = builtin_types[i];
1187 symmap_insert(&scope->symbols, type,
1188 (Symbol){.name = type, .kind = SYM_BUILTIN_TYPE},
1189 a->storage);
1190 }
1191 Str numeric_types[] = {
1192 cstr("u8"), cstr("s8"), cstr("u16"), cstr("s16"), cstr("u32"),
1193 cstr("s32"), cstr("u64"), cstr("s64"), cstr("f32"), cstr("f64"),
1194 cstr("ptr"), cstr("int"), cstr("uint"),
1195 };
1196 for (sz i = 0; i < LEN(numeric_types); i++) {
1197 Str type = numeric_types[i];
1198 strset_insert(&a->numeric_types, type, a->storage);
1199 }
1200 Str integer_types[] = {
1201 cstr("u8"), cstr("s8"), cstr("u16"), cstr("s16"),
1202 cstr("u32"), cstr("s32"), cstr("u64"), cstr("s64"),
1203 cstr("ptr"), cstr("int"), cstr("uint"),
1204 };
1205 for (sz i = 0; i < LEN(integer_types); i++) {
1206 Str type = integer_types[i];
1207 strset_insert(&a->integer_types, type, a->storage);
1208 }
1209 // Find top level function declarations.
1210 for (sz i = 0; i < array_size(parser->nodes); i++) {
1211 Node *root = parser->nodes[i];
1212 if (root->kind == NODE_FUN) {
1213 Str symbol = root->func_name->value.str;
1214 if (symmap_lookup(&scope->symbols, symbol)) {
1215 eprintln(
1216 "%s:%d:%d: error: function '%s' already defined in "
1217 "current "
1218 "scope ",
1219 a->file_name, root->var_name->line, root->var_name->col,
1220 symbol);
1221 a->err = true;
531 } 1222 }
1223 symmap_insert(&scope->symbols, symbol,
1224 (Symbol){.name = symbol, .kind = SYM_FUN},
1225 a->storage);
532 } 1226 }
533 } 1227 }
534 1228 // Recursively fill symbol tables.
535 for (size_t i = 0; i < array_size(parse_tree->roots); ++i) { 1229 for (sz i = 0; i < array_size(parser->nodes); i++) {
536 // Fill up symbol tables in proper scope and resolve type of expression 1230 Node *root = parser->nodes[i];
537 // for all elements. 1231 type_inference(a, root, scope);
538 if (!resolve_type(parse_tree, scope, parse_tree->roots[i])) {
539 return NULL;
540 }
541 } 1232 }
542
543 return parse_tree;
544} 1233}
1234
generated by cgit v1.2.1 (git 2.18.0) at 2024-07-05 22:45:12 +0000