diff options
author | Bad Diode <bd@badd10de.dev> | 2024-06-23 13:48:59 +0200 |
---|---|---|
committer | Bad Diode <bd@badd10de.dev> | 2024-06-23 13:48:59 +0200 |
commit | b9397e53034b08dd9ffb69c94b5283dc46863d33 (patch) | |
tree | d474d8a1948cd2703631802e87d58473e6297df0 /src | |
parent | ec7936226a2e82b10bc1fdac132a1d26d178dbcd (diff) | |
download | bdl-b9397e53034b08dd9ffb69c94b5283dc46863d33.tar.gz bdl-b9397e53034b08dd9ffb69c94b5283dc46863d33.zip |
Start basic type checking/inference
Diffstat (limited to 'src')
-rw-r--r-- | src/main.c | 211 |
1 files changed, 89 insertions, 122 deletions
@@ -55,6 +55,11 @@ Str sym_kind_str[] = { | |||
55 | [SYM_STRUCT_FIELD] = cstr("STRUCT FIELD "), | 55 | [SYM_STRUCT_FIELD] = cstr("STRUCT FIELD "), |
56 | }; | 56 | }; |
57 | 57 | ||
58 | typedef struct Type { | ||
59 | Str name; | ||
60 | sz size; | ||
61 | } Type; | ||
62 | |||
58 | typedef struct Symbol { | 63 | typedef struct Symbol { |
59 | SymbolKind kind; | 64 | SymbolKind kind; |
60 | Str name; | 65 | Str name; |
@@ -62,11 +67,13 @@ typedef struct Symbol { | |||
62 | } Symbol; | 67 | } Symbol; |
63 | 68 | ||
64 | MAPDEF(SymbolMap, symmap, Str, Symbol, str_hash, str_eq) | 69 | MAPDEF(SymbolMap, symmap, Str, Symbol, str_hash, str_eq) |
70 | MAPDEF(TypeMap, typemap, Str, Type, str_hash, str_eq) | ||
65 | 71 | ||
66 | typedef struct Scope { | 72 | typedef struct Scope { |
67 | sz id; | 73 | sz id; |
68 | sz depth; | 74 | sz depth; |
69 | SymbolMap *symbols; | 75 | SymbolMap *symbols; |
76 | TypeMap *types; | ||
70 | struct Scope *parent; | 77 | struct Scope *parent; |
71 | } Scope; | 78 | } Scope; |
72 | 79 | ||
@@ -100,6 +107,18 @@ find_symbol(Scope *scope, Str symbol) { | |||
100 | return NULL; | 107 | return NULL; |
101 | } | 108 | } |
102 | 109 | ||
110 | TypeMap * | ||
111 | find_type(Scope *scope, Str type) { | ||
112 | while (scope != NULL) { | ||
113 | TypeMap *val = typemap_lookup(&scope->types, type); | ||
114 | if (val != NULL) { | ||
115 | return val; | ||
116 | } | ||
117 | scope = scope->parent; | ||
118 | } | ||
119 | return NULL; | ||
120 | } | ||
121 | |||
103 | void | 122 | void |
104 | graph_scope(Scope *scope, Arena a) { | 123 | graph_scope(Scope *scope, Arena a) { |
105 | if (!scope->symbols) { | 124 | if (!scope->symbols) { |
@@ -163,6 +182,11 @@ graph_symbols(Scope **scopes, Arena a) { | |||
163 | println("}"); | 182 | println("}"); |
164 | } | 183 | } |
165 | 184 | ||
185 | Type | ||
186 | type_inference(Analyzer *a, Node *node, Scope *scope) { | ||
187 | return (Type){0}; | ||
188 | } | ||
189 | |||
166 | void | 190 | void |
167 | analyzer_symbols(Analyzer *a, Node *node, Scope *scope) { | 191 | analyzer_symbols(Analyzer *a, Node *node, Scope *scope) { |
168 | // TODO: Struct field initializers need to be checked... when we | 192 | // TODO: Struct field initializers need to be checked... when we |
@@ -197,6 +221,7 @@ analyzer_symbols(Analyzer *a, Node *node, Scope *scope) { | |||
197 | "scope", | 221 | "scope", |
198 | a->file_name, node->func_name->line, | 222 | a->file_name, node->func_name->line, |
199 | node->func_name->col, symbol); | 223 | node->func_name->col, symbol); |
224 | return; | ||
200 | } | 225 | } |
201 | symmap_insert(&scope->symbols, symbol, | 226 | symmap_insert(&scope->symbols, symbol, |
202 | (Symbol){.kind = SYM_FUN, .name = symbol}, | 227 | (Symbol){.kind = SYM_FUN, .name = symbol}, |
@@ -272,6 +297,7 @@ analyzer_symbols(Analyzer *a, Node *node, Scope *scope) { | |||
272 | "%s:%d:%d: error: enum field '%s.%s' already exists", | 297 | "%s:%d:%d: error: enum field '%s.%s' already exists", |
273 | a->file_name, field->line, field->col, symbol, | 298 | a->file_name, field->line, field->col, symbol, |
274 | field_name); | 299 | field_name); |
300 | return; | ||
275 | } | 301 | } |
276 | Symbol s = | 302 | Symbol s = |
277 | (Symbol){.kind = node->kind == NODE_ENUM ? SYM_ENUM_FIELD | 303 | (Symbol){.kind = node->kind == NODE_ENUM ? SYM_ENUM_FIELD |
@@ -322,6 +348,7 @@ analyzer_symbols(Analyzer *a, Node *node, Scope *scope) { | |||
322 | "%s:%d:%d: error: symbol '%s' doesn't exists in current " | 348 | "%s:%d:%d: error: symbol '%s' doesn't exists in current " |
323 | " scope ", | 349 | " scope ", |
324 | a->file_name, node->line, node->col, symbol); | 350 | a->file_name, node->line, node->col, symbol); |
351 | return; | ||
325 | } | 352 | } |
326 | for (sz i = 0; i < array_size(node->elements); i++) { | 353 | for (sz i = 0; i < array_size(node->elements); i++) { |
327 | Node *expr = node->elements[i]; | 354 | Node *expr = node->elements[i]; |
@@ -336,6 +363,7 @@ analyzer_symbols(Analyzer *a, Node *node, Scope *scope) { | |||
336 | "%s:%d:%d: error: symbol '%s' doesn't exists in current " | 363 | "%s:%d:%d: error: symbol '%s' doesn't exists in current " |
337 | " scope ", | 364 | " scope ", |
338 | a->file_name, node->line, node->col, symbol); | 365 | a->file_name, node->line, node->col, symbol); |
366 | return; | ||
339 | } | 367 | } |
340 | // TODO: Resolve symbol chains. | 368 | // TODO: Resolve symbol chains. |
341 | } break; | 369 | } break; |
@@ -354,128 +382,29 @@ analyzer_symbols(Analyzer *a, Node *node, Scope *scope) { | |||
354 | " scope ", | 382 | " scope ", |
355 | a->file_name, node->var_name->line, node->var_name->col, | 383 | a->file_name, node->var_name->line, node->var_name->col, |
356 | symbol); | 384 | symbol); |
385 | return; | ||
357 | } | 386 | } |
358 | symmap_insert(&scope->symbols, symbol, | 387 | symmap_insert(&scope->symbols, symbol, |
359 | (Symbol){.kind = SYM_VAR, .name = symbol}, | 388 | (Symbol){.kind = SYM_VAR, .name = symbol}, |
360 | a->storage); | 389 | a->storage); |
361 | } break; | ||
362 | // Binary ops | ||
363 | case NODE_ADD: | ||
364 | case NODE_SUB: | ||
365 | case NODE_DIV: | ||
366 | case NODE_MUL: | ||
367 | case NODE_MOD: | ||
368 | case NODE_NOT: | ||
369 | case NODE_AND: | ||
370 | case NODE_OR: | ||
371 | case NODE_EQ: | ||
372 | case NODE_NEQ: | ||
373 | case NODE_LT: | ||
374 | case NODE_GT: | ||
375 | case NODE_LE: | ||
376 | case NODE_GE: | ||
377 | case NODE_BITNOT: | ||
378 | case NODE_BITAND: | ||
379 | case NODE_BITOR: | ||
380 | case NODE_BITLSHIFT: | ||
381 | case NODE_BITRSHIFT: { | ||
382 | analyzer_symbols(a, node->left, scope); | ||
383 | analyzer_symbols(a, node->right, scope); | ||
384 | } break; | ||
385 | default: break; | ||
386 | } | ||
387 | } | ||
388 | |||
389 | void | ||
390 | propagate_type(Analyzer *a, Node *node, Scope *scope) { | ||
391 | if (!node) { | ||
392 | return; | ||
393 | } | ||
394 | switch (node->kind) { | ||
395 | // case NODE_LET: { | ||
396 | // } break; | ||
397 | // Binary ops | ||
398 | case NODE_NUM_INT: | ||
399 | case NODE_NUM_UINT: { | ||
400 | // Check if the terminal correspond to an integer numeric type. | ||
401 | } break; | ||
402 | case NODE_ADD: | ||
403 | case NODE_SUB: | ||
404 | case NODE_DIV: | ||
405 | case NODE_MUL: | ||
406 | case NODE_MOD: | ||
407 | case NODE_NOT: | ||
408 | case NODE_AND: | ||
409 | case NODE_OR: | ||
410 | case NODE_EQ: | ||
411 | case NODE_NEQ: | ||
412 | case NODE_LT: | ||
413 | case NODE_GT: | ||
414 | case NODE_LE: | ||
415 | case NODE_GE: | ||
416 | case NODE_BITNOT: | ||
417 | case NODE_BITAND: | ||
418 | case NODE_BITOR: | ||
419 | case NODE_BITLSHIFT: | ||
420 | case NODE_BITRSHIFT: { | ||
421 | if (node->left) { | ||
422 | node->left->type = node->type; | ||
423 | propagate_type(a, node->left, scope); | ||
424 | } | ||
425 | if (node->right) { | ||
426 | node->right->type = node->type; | ||
427 | propagate_type(a, node->right, scope); | ||
428 | } | ||
429 | } break; | ||
430 | default: break; | ||
431 | } | ||
432 | } | ||
433 | |||
434 | void | ||
435 | analyzer_typecheck(Analyzer *a, Node *node, Scope *scope) { | ||
436 | assert(a); | ||
437 | assert(scope); | ||
438 | if (!node) { | ||
439 | return; | ||
440 | } | ||
441 | switch (node->kind) { | ||
442 | case NODE_NUM_INT: | ||
443 | case NODE_NUM_UINT: { | ||
444 | // TODO: Check if the terminal correspond to an integer numeric type. | ||
445 | // printf("DING\n"); | ||
446 | } break; | ||
447 | case NODE_LET: { | ||
448 | // Check the value first to avoid recursive symbol usage. | ||
449 | // analyzer_symbols(a, node->var_val, scope); | ||
450 | 390 | ||
451 | if (node->var_type) { | 391 | if (node->var_type) { |
452 | Str type = node->var_type->value.str; | 392 | Str type_name = node->var_type->value.str; |
453 | // TODO: register type on symbol table? | 393 | TypeMap *type = find_type(scope, type_name); |
454 | // println("found let type: %s", type); | 394 | if (type == NULL) { |
455 | // Propagate down. | 395 | eprintln("%s:%d:%d: error: unknown type '%s'", a->file_name, |
456 | if (node->var_val) { | 396 | node->var_type->line, node->var_type->col, |
457 | node->var_val->type = type; | 397 | type_name); |
458 | propagate_type(a, node->var_val, scope); | 398 | return; |
459 | analyzer_typecheck(a, node->var_val, scope); | ||
460 | } | 399 | } |
400 | typemap_insert(&scope->types, symbol, type->val, a->storage); | ||
461 | return; | 401 | return; |
462 | } | 402 | } |
463 | // TODO: perform inference | 403 | // We don't know the type for this symbol, perform inference. |
464 | if (node->var_val) { | 404 | type_inference(a, node->var_val, scope); |
465 | // analyzer_typecheck(a, node->var_val, scope); | 405 | |
466 | } | ||
467 | // TODO: Type check | ||
468 | // if (symmap_lookup(&scope->symbols, symbol) != NULL) { | ||
469 | // eprintln( | ||
470 | // "%s:%d:%d: error: symbol '%s' already exists in current " | ||
471 | // " scope ", | ||
472 | // a->file_name, node->var_name->line, node->var_name->col, | ||
473 | // symbol); | ||
474 | // } | ||
475 | // symmap_insert(&scope->symbols, symbol, | ||
476 | // (Symbol){.kind = SYM_VAR, .name = symbol}, | ||
477 | // a->storage); | ||
478 | } break; | 406 | } break; |
407 | // Binary ops | ||
479 | case NODE_ADD: | 408 | case NODE_ADD: |
480 | case NODE_SUB: | 409 | case NODE_SUB: |
481 | case NODE_DIV: | 410 | case NODE_DIV: |
@@ -495,12 +424,8 @@ analyzer_typecheck(Analyzer *a, Node *node, Scope *scope) { | |||
495 | case NODE_BITOR: | 424 | case NODE_BITOR: |
496 | case NODE_BITLSHIFT: | 425 | case NODE_BITLSHIFT: |
497 | case NODE_BITRSHIFT: { | 426 | case NODE_BITRSHIFT: { |
498 | if (node->left) { | 427 | analyzer_symbols(a, node->left, scope); |
499 | analyzer_typecheck(a, node->left, scope); | 428 | analyzer_symbols(a, node->right, scope); |
500 | } | ||
501 | if (node->right) { | ||
502 | analyzer_typecheck(a, node->right, scope); | ||
503 | } | ||
504 | } break; | 429 | } break; |
505 | default: break; | 430 | default: break; |
506 | } | 431 | } |
@@ -524,6 +449,48 @@ symbolic_analysis(Analyzer *a, Parser *parser) { | |||
524 | symmap_insert(&scope->symbols, symbol, sym, a->storage); | 449 | symmap_insert(&scope->symbols, symbol, sym, a->storage); |
525 | } | 450 | } |
526 | 451 | ||
452 | // Fill builtin types. | ||
453 | Type builtin_types[] = { | ||
454 | {cstr("u8"), 1}, | ||
455 | {cstr("s8"), 1}, | ||
456 | {cstr("u16"), 2}, | ||
457 | {cstr("s16"), 2}, | ||
458 | {cstr("u32"), 4}, | ||
459 | {cstr("s32"), 4}, | ||
460 | {cstr("u64"), 8}, | ||
461 | {cstr("s64"), 8}, | ||
462 | {cstr("f32"), 4}, | ||
463 | {cstr("f64"), 8}, | ||
464 | // TODO: down here is machine dependant, we could insert 0 for now and | ||
465 | // fill it up later maybe? Dunno. | ||
466 | {cstr("ptr"), 8}, | ||
467 | {cstr("int"), 8}, | ||
468 | {cstr("uint"), 8}, | ||
469 | {cstr("str"), 8 + 8}, // (u8*, sz) | ||
470 | }; | ||
471 | for (sz i = 0; i < LEN(builtin_types); i++) { | ||
472 | Type type = builtin_types[i]; | ||
473 | typemap_insert(&scope->types, type.name, type, a->storage); | ||
474 | } | ||
475 | |||
476 | // Str valid_int_types[] = { | ||
477 | // cstr("u8"), cstr("u16"), cstr("u32"), cstr("u64"), cstr("s8"), | ||
478 | // cstr("s16"), cstr("s32"), cstr("s64"), cstr("int"), cstr("uint"), | ||
479 | // }; | ||
480 | // for (sz i = 0; i < LEN(valid_int_types); i++) { | ||
481 | // Str type = valid_int_types[i]; | ||
482 | // strset_insert(&a->valid_int_types, type, a->storage); | ||
483 | // } | ||
484 | |||
485 | // Str valid_float_types[] = { | ||
486 | // cstr("f32"), | ||
487 | // cstr("f64"), | ||
488 | // }; | ||
489 | // for (sz i = 0; i < LEN(valid_float_types); i++) { | ||
490 | // Str type = valid_float_types[i]; | ||
491 | // strset_insert(&a->valid_float_types, type, a->storage); | ||
492 | // } | ||
493 | |||
527 | // Find top level function declarations. | 494 | // Find top level function declarations. |
528 | for (sz i = 0; i < array_size(parser->nodes); i++) { | 495 | for (sz i = 0; i < array_size(parser->nodes); i++) { |
529 | Node *root = parser->nodes[i]; | 496 | Node *root = parser->nodes[i]; |
@@ -547,10 +514,10 @@ symbolic_analysis(Analyzer *a, Parser *parser) { | |||
547 | Node *root = parser->nodes[i]; | 514 | Node *root = parser->nodes[i]; |
548 | analyzer_symbols(a, root, scope); | 515 | analyzer_symbols(a, root, scope); |
549 | } | 516 | } |
550 | for (sz i = 0; i < array_size(parser->nodes); i++) { | 517 | // for (sz i = 0; i < array_size(parser->nodes); i++) { |
551 | Node *root = parser->nodes[i]; | 518 | // Node *root = parser->nodes[i]; |
552 | analyzer_typecheck(a, root, scope); | 519 | // analyzer_typecheck(a, root, scope); |
553 | } | 520 | // } |
554 | } | 521 | } |
555 | 522 | ||
556 | void | 523 | void |