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