-
Notifications
You must be signed in to change notification settings - Fork 0
orso Lang #2: Eager Resolution
Here's the agenda for this article:
- Language Updates
- For Loops
- Prefix operators and Compound Assignment Operators
- Branch-Scope Declarations and Expressions
- Arrays
- Function Generics
- Static Analysis
- Eager Resolution
- Generic Functions Implementation in Orso
I'll be showing several code examples and I'll be walking through what things do. To reference parts of the code, I'll put use this notation "(x)" where x is a number. You'll be able to then look in the code example for the "// (x)" to see what I'm referencing.
Here's an example where I'm going to reference the (1) print for hello world to show you what I mean.
int main() {
printf("hello, world!\"); // (1)
return 0;
}Alright let's get started.
I finally added a proper for loop, the syntax looks like this
for i := 0; i < 10; ++i {
// do stuff
};They allow a (1) then clause like this
for i := 0; i < 10; ++i do
printint(i)
then //(1)
println();The then clause only evaluates if the for loop finishes naturally, as in, the condition evaluates to false. Otherwise, if there's a jmp to outside of the loop scope, with a break, return or labelled continue, the then clause does not get evaluated.
I'm still thinking about it, but this might be the only type of "for-loop" in orso. I don't know if I'll implement a foreach type of thing.
You might have noticed the prefix-increment operator. In orso, only the prefix-increment and prefix-decrement operator exist. There is no post-fix, and thus, no equivalent to that behavior.
Personally, I like the post-fix operators but the reason it's not implemented is due to design goals mostly.
orso is meant to be minimal code volume wise. Adding postfix operator would add an extra type of expression that cannot really be represented efficiently with any of the other types of expressions. It would need its own type of AST node and it's own code generation for both the virtual machine and the C representation.
The prefix operator, on the other hand, can be easily transformed from ++x to x += 1. In fact, ++x is unknown to the orso AST. During parse-time, ++x is treated as unary node, and then there's a special if-condition that catches the ++ operator, and immediately converts it into x += 1, which is already handled by the compiler pipeline. This was literally like ~10 lines of new code.
Look, this is where unary operations are parsed in the parser.
You can see that first I (1) check the type of unary token that is being parsed, and then (2) convert it to a compound assignment expression.
static ast_node_t *parse_unary(parser_t *parser) {
token_t operator = parser->previous;
ast_node_t *operand = parse_precedence(parser, PREC_UNARY);
unless (operator.type == TOKEN_PLUS_PLUS || operator.type == TOKEN_MINUS_MINUS) { // (1)
// creates a normal unary operator
ast_node_t *unary = ast_unary(parser->ast, operator, operand);
return unary;
} else {
// parse `++expr` or `--expr` as `expr += 1` or `expr -= 1` respectively
token_t equals = operator;
equals.type= (equals.type == TOKEN_MINUS_MINUS ? TOKEN_MINUS_EQUAL : TOKEN_PLUS_EQUAL);
equals.view.length = 0;
ast_node_t *one = ast_implicit_expr(parser->ast, parser->ast->type_set.u64_, WORDU(1), equals);
one->is_free_number = true;
ast_node_t *assignment = ast_assignment(parser->ast, operand, one, equals); // (2)
return assignment;
}
}Adding 1 to an lvalue is... beyond common, and is totally worth the extra 10 lines of code it took to implement it.
Oh yeah, and there's compound assignment operators now.
So all these guys
+= -= *= /= %= %%= and= or=They all do what you think, and the logical ones still short-circuit the right hand side depending on the value inside the given lvalue (and the operator of course).
These were not ~10 lines of code to implement but they're convenient enough that it was worth the 100s of lines it added to the codebase.
You can scope declarations and expressions to if/while expressions by listing them before the condition
if sum := calc_sum(args); sum > threshold then
printint(sum)
else
printint(threshold-sum);and with loops as well, which allows you to manually write something similar to a for
sum := 0;
while i := 0; i < 10 {
sum += i;
++i;
} then sum *= i;The variables defined before the condition are evaluated once before the condition is tested, and they are available in their respective clauses.
This means you cannot do something like this with loops
while i := 0; ++i; i < 10 do i;++i would run only once.
I'm not sure if I should change this behaviour, but I think this is consistent and less confusing.
These were fairly simple to implement as well... They basically just get converted to structures that already exist at parse-time.
So something like this:
if x := get_x(); x == 10 then x;Is converted to this:
{
x := get_x();
if x == 10 then x;
};And it works out because the last expression in the block is an if, which means the entire block would evaluate to whatever the if expression evaluates to.
So the behavior between the versions is the same, but there was no need to write any extra code for generation or static analysis.
Array types, yay!
nums: [10]intYou can initialize arrays like this
nums := [10]int.{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};.{...} is an array initialization list when dotting with an array type.
You can access elements like this:
first_element := nums[0]You can set elements as well:
nums[0] = 10;You can use array access on inlined array types:
num := [5]int.{0, 1, 2, 3, 4}[3]Obviously, since an inlined array type is a value, you cannot set to it like this:
[5]int.{0, 1, 2, 3, 4}[3] = 10;Arrays are copied-by-value
arr := [2]int.{0, 1};
arr_copy := arr;You can also use (1) the item access brackets on pointers to arrays
arr := [5]int.{0, 1, 2, 3, 4};
arr_ptr := &arr;
arr_ptr[4]; // (1)One note on arrays is that their sizes need to be known at compile-time because I want the compiler to know the sizes of all the types in the program before code generation.
Specifically for arrays, the compiler will need to generate bound-checking code (both on the C and VM side) to crash gracefully if the user tries to access an index that's out of range. This is not possible with an array with a run-time size unless I store the size of all arrays along with the array data together. Not only does this add a lot of volume to both codegens to deal with different operations that work on run-time sized arrays, but it's also not very efficient memory wise.
In orso, the next thing I'll be adding to the language is array-programming. So, I want the array data structure to be as space efficient as possible - at least in the C representation.
I've also added implicit typing for dot operations...
For arrays
nums: [10]int = .{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};In this case, the type of the array to perform the dot on is inferred from the type declaration for nums, and the static analyzer implicitly adds the inferred type to the left-hand side of the dot.
There are other cases where the implicit type can be inferred...
Array items
vecs := [2][2]f32.{.{0, 0}, .{1, 1}};
// instead of
vecs := [2][2]f32.{[2]f32.{0, 0}, [2]f32.{1, 1}};Function returns
add :: (a: [2]f32, b: [2]f32) -> [2]f32 {
return .{a[0]+b[0], a[1]+b[1]};
};And function arguments too
add(.{5, 7}, .{5, 3});When I add structs, this should be useful as well since they'll use very similar syntax to be initialized.
This is the most powerful feature I spent time on time between the last and this article.
First, here's an example of an "inferred function definition" so you can see how they look like
add :: (a: [2]!u, b: [2]u) -> [2]u {
return .{a[0]+b[0], a[1] + b[1]};
};The !u declares a type constant called u that must be resolved at compile-time at the function's call-site. This is what orso calls an "inferred type declaration", and if it's present in an argument list for a function definition, it can be used as a regular constant variable anywhere in the function definition.
What's important about the placement of the !u is that it determines how the u type is inferred for the rest of the function. And thus it combos nicely with the implicit types once the function definition is inferred.
You call inferred functions like this:
add([2]int.{0, 0}, .{1, 1}); // (1)The (1) second argument above uses an implicit type
At compile-time, the static analyzer infers that int is u, and a copy of add is created as if u where defined as a constant in a nearby scope, and this "child" function is what's ultimately called at run-time.
I think this way of implementing generics is called using a monomorphic strategy, since a function is created for every type-unique function call. At least that's what I read on Rust's FAQ.
I'm honestly not sure how else to implement this for a statically-typed language without making copies of the generic function though. If you know of any other interesting strategies to implement this, let me know!
Since the user might want to use an argument later in the function definition to infer the function signature, I made it so you don't need the inferred type declaration to come before its usage.
append(val: u, arr: &[10]!u /* (1) */) { ... };In this case, despite (1) !u syntax being placed after its usage in the val definition, this function can be inferred just fine.
Of course, you can have multiple inferred type declarations in a function definition
get :: (arr: &[!n]!value_t, key: !key_t) -> value_t {
key_index := find_entry(arr, key);
if key_index < 0 then return .{}; // default value for implicit type value_t
return arr[key_index];
};This is a generic get function for an imaginary dictionary implemented with an array. The inferred type declarations would be n value_t and key_t.
And this works with the @run directive that evaluates any expression composed of constants at run-time.
In terms of how this was actually implemented... Well, that's that's going to be the main focus of this article!
First, I wanted to give a little primer on how the orso static analyzer works, and for that, you'll already need some knowledge in how languages are created.
If you know what an AST is and how it's created at a high-level, then you should be good to go.
Otherwise, this chapter of "Crafting Interpreters" does a pretty great job in giving you the run-down of a language implementation.
The static analyzer in orso uses a "recursive-descent" strategy to resolve all the types, resolve all their sizes, resolve all constant values, run compile-time expressions and report errors in a single mega-pass of the entire AST.
It does this using a strategy I call in my head "eager resolution", I'm not sure if it's common to have multiple passes for resolving an AST, so if there's already a term for this, let me know!
Essentially, during the descent down the AST to resolve everything, every single time the analyzer encounters an AST node that is unresolved, it immediately tries to resolve it before anything else.
This is trivial for local and even global mutable variables, where I want to force the language user to define them before their usage in expressions.
// allowed
a := 10;
b := a;
// not allowed
a := b;
b := 10;However, I did not want this behavior for constants.
Since constants are the main way to store functions, and I don't want forward declarations in my language, for (1) functions to be used before their physical declarations, the static analyzer needs to at least know that it potentially exists...
add(1, 1); // (1)
add :: (a: int, b: int) -> int {
return a + b;
};This means I need to forward scan the top-level local constants each time I enter a new scope that can define constants.
The forward scanned constants are stored somewhere and are given an unresolved type status, this essentially acts as automatic forward declarations during static analyses.
The only issue was resolving circular references, for example like this:
A :: B;
B :: A;There needs to be special code to catch this case because now constants can reference each other circularly since their usage-site is flexible.
Eager resolution is a really important design decision for the analyzer because many parts of the analysis depend on the idea that calling resolve_expression (the super function that resolves everything) produces either a valid or invalid type, not an unresolved one. So unresolved types are only returned in very special cases and handled almost immediately before anything else is resolved.
The way the static analyzer figures out if there are any circular dependencies for evaluating arbitrary expressions at compile-time also relies on the fact above.
In general, finding circular dependencies can be quite difficult if you don't already have a way implemented to backtrack through the data to find trivially looping situations. Since the orso static analyzer resolves everything through its descent down the AST, the paths it takes doubles as the dependency list for the expressions that need to be resolved. This allows the static analyzer to find circular dependencies as soon as they occur.
Again, I'm not sure if "eager resolution" is a common strategy for a static analyzer that require evaluating arbitrary expressions at compile-time. Implementations I've seen often do some analysis on an AST and then some on the IR. Zig, for example, uses its IR language for resolving its comptime stuff. And from what I understand from Jon Blow's compiler for Jai, is that it actually does multiple passes of the AST to try and resolve it. I'm not sure if this is still accurate, but I remember specifically asking him on a stream one time if he did any forward scanning during his static analysis for usage-before-declarations, and he responded with a definitive no.
If there are any languages with a handwritten arbitrary expression evaluation at compile-time implementation, that does not use llvm, or a JIT library, please send it my way! Super interested in seeing other implementations for this. Especially in solving the circular dependency problem.
With all that in mind, we can move on to the high-level implementation details for generic functions in orso.
Let's start at the point the static analyzer encounters an unresolved function definition like this
add :: (a: !u, b: u) -> u { return a + b; };The static analyzer knows it's looking at a function definition, but it doesn't know yet that it's supposed to be inferred.
The first thing the analyzer does is do a (1) forward scan of the arguments' types in the function definition while keeping track of the path it's taking to find the inferred type declaration, if there is one...
Here's the real code loop that does this inside the function that resolves function defintions:
bool is_inferred_function = false;
{
for (size_t i = an_func_def_arg_start(funcdef); i < an_func_def_arg_end(funcdef); ++i) { // (1)
ast_node_t *decl = funcdef->children.items[i];
ast_node_t *decl_type = an_decl_type(decl);
type_patterns_t patterns = {.allocator=ast->arena}; // (2)
forward_scan_inferred_types(decl, decl_type, ast->arena, &patterns); // (4)
if (patterns.count > 0) { // (3)
decl->type_decl_patterns = patterns;
is_inferred_function = true;
}
}
}The (2) patterns array holds all the type patterns for a declaration, since one declaration can have many type patterns.
A function is considered inferred if (3) at least one of its arguments uses an inferred type declaration.
What the (4) forward_scan_inferred_types function does is try to find "type patterns" - these are basically just "directions" for finding the inferred type. It looks like this:
static void forward_scan_inferred_types(ast_node_t *decl, ast_node_t *decl_type, arena_t *arena, type_patterns_t *patterns) {
switch (decl_type->node_type) {
case AST_NODE_TYPE_NONE:
case AST_NODE_TYPE_DECLARATION_STATEMENT:
case AST_NODE_TYPE_MODULE:
case AST_NODE_TYPE_EXPRESSION_ASSIGNMENT:
case AST_NODE_TYPE_DECLARATION_DEFINITION: UNREACHABLE(); break;
case AST_NODE_TYPE_EXPRESSION_ARRAY_ITEM_ACCESS:
case AST_NODE_TYPE_EXPRESSION_CAST:
case AST_NODE_TYPE_EXPRESSION_BINARY:
case AST_NODE_TYPE_EXPRESSION_DOT:
case AST_NODE_TYPE_EXPRESSION_BUILTIN_CALL:
case AST_NODE_TYPE_EXPRESSION_CALL:
case AST_NODE_TYPE_EXPRESSION_PRIMARY:
case AST_NODE_TYPE_EXPRESSION_DEF_VALUE:
case AST_NODE_TYPE_EXPRESSION_BLOCK:
case AST_NODE_TYPE_EXPRESSION_BRANCHING:
case AST_NODE_TYPE_EXPRESSION_FUNCTION_DEFINITION:
case AST_NODE_TYPE_EXPRESSION_NIL:
case AST_NODE_TYPE_EXPRESSION_STRUCT_DEFINITION:
case AST_NODE_TYPE_EXPRESSION_INITIALIZER_LIST:
case AST_NODE_TYPE_EXPRESSION_DIRECTIVE:
case AST_NODE_TYPE_EXPRESSION_JMP: break;
case AST_NODE_TYPE_EXPR_INFERRED_TYPE_DECL: {
decl_type->node_type = AST_NODE_TYPE_EXPRESSION_DEF_VALUE;
decl_type->value_type = typeid(TYPE_UNRESOLVED);
type_path_t *path = new_type_path(MATCH_TYPE_IDENTIFIER, NULL, arena);
type_pattern_t pattern = {
.identifier = decl_type->identifier,
.expected = path,
};
array_push(patterns, pattern);
break;
}
case AST_NODE_TYPE_EXPRESSION_UNARY: {
unless (decl_type->operator.type == TOKEN_AMPERSAND) {
break;
}
forward_scan_inferred_types(decl, an_expression(decl_type), arena, patterns);
for (size_t i = 0; i < patterns->count; ++i) {
type_path_t *current = patterns->items[i].expected;
type_path_t *path = new_type_path(MATCH_TYPE_POINTER, current, arena);
patterns->items[i].expected = path;
}
break;
}
case AST_NODE_TYPE_EXPRESSION_ARRAY_TYPE: {
tmp_arena_t *tmp = allocator_borrow();
{
type_patterns_t array_type_patterns = {.allocator=tmp->allocator};
forward_scan_inferred_types(decl, an_array_type_expr(decl_type), arena, &array_type_patterns);
for (size_t i = 0; i < array_type_patterns.count; ++i) {
type_path_t *current = array_type_patterns.items[i].expected;
type_path_t *path = new_type_path(MATCH_TYPE_ARRAY_TYPE, current, arena);
array_type_patterns.items[i].expected = path;
array_push(patterns, array_type_patterns.items[i]);
}
}
{
type_patterns_t array_size_patterns = {.allocator=tmp->allocator};
if (an_is_notnone(an_array_size_expr(decl_type))) {
forward_scan_inferred_types(decl, an_array_size_expr(decl_type), arena, &array_size_patterns);
}
for (size_t i = 0; i < array_size_patterns.count; ++i) {
type_path_t *current = array_size_patterns.items[i].expected;
type_path_t *path = new_type_path(MATCH_TYPE_ARRAY_SIZE, current, arena);
array_size_patterns.items[i].expected = path;
array_push(patterns, array_size_patterns.items[i]);
}
}
allocator_return(tmp);
break;
}
case AST_NODE_TYPE_EXPRESSION_FUNCTION_SIGNATURE: {
UNREACHABLE(); // todo
break;
}
case AST_NODE_TYPE_EXPRESSION_GROUPING: {
forward_scan_inferred_types(decl, an_expression(decl_type), arena, patterns);
break;
}
}
}If you look closely, you'll see I haven't done the implementation for function signatures yet. I've just been a little lazy about it, but it should be very straightforward.
In the case of the add function, the path this creates is simple: -> IDENTIFIER
For a signature like this: append :: (&[10]!u, u) the type pattern for u would look like this:
-> PTR -> ARRAY_TYPE -> IDENTIFIER
If a function is found to be inferred, then resolution for that function stops immediately, and instead it's marked as an inferred function type for when it might be called later.
That's it for resolving inferred function declarations. The resolution for them pretty much does nothing and dips out immediately. This a rare case where the resolve_expression function returns a node with a bunch of unresolved types... The way I reconcile this is by considering the function definition as resolved to a special type called an "inferred function". This is a type that is only available at compile-time to the static analyzer, which means it's a constant-only expression, you cannot pass around an "inferred function" at run-time.
Now, the next part of the resolution happens at the call-site for the inferred function definition.
The very first thing that happens during call resolution, is (1) figure out the type of the callee is. "callee" is how I refer to the expression that is being called. Then immediately after, (2) I check if the callee is an inferred function type and is (3) also referring to a constant expression to dip out if it isn't a constant. If that's good, (4) the analyzer tries to realize the function. If (5) that succeeds, and then we simply (6) replace the callee we process for this call expression with the realized function definition instead, and continue resolving the call as usual.
Here's how that looks like
ast_node_t *callee = an_callee(expr);
resolve_expression(analyzer, ast, state, implicit_type, callee); // (1)
type_t callee_type = callee->value_type;
typedata_t *callee_td = ast_type2td(ast, callee_type);
if (callee_td->kind == TYPE_INFERRED_FUNCTION) { // (2)
unless (callee->expr_val.is_concrete) { // (3)
stan_error(analyzer, make_error_node(ERROR_ANALYSIS_INFERRED_CALLEE_MUST_BE_CONSTANT, callee));
INVALIDATE(expr);
break;
}
ast_node_t *inferred_funcdef = (ast_node_t*)callee->expr_val.word.as.p;
ast_node_t *realized_funcdef = stan_realize_inferred_funcdef_or_error_and_null(analyzer, state, expr, inferred_funcdef); // (4)
unless (realized_funcdef) { // (5)
INVALIDATE(expr);
break;
}
if (TYPE_IS_INVALID(realized_funcdef->value_type)) { // (5)
INVALIDATE(expr);
break;
}
// (6)
callee = ast_implicit_expr(ast, realized_funcdef->value_type, realized_funcdef->expr_val.word, callee->start);
callee_type = callee->value_type;
callee_td = ast_type2td(ast, callee_type);
an_callee(expr) = callee;
}The important function in there is the stan_realize_inferred_funcdef_or_error_and_null.
This function uses the call expression node to try to infer the function definition. To do this the first thing it does is (1) start a scope that will contain the inferred type definitions. In our add function, I'm referring to u which will be realized into a constant variable on this new scope.
scope_t scope = {0};
scope_init(&scope, analyzer->ast->arena, SCOPE_TYPE_INFERRED_PARAMS, inferred_funcdef->scope, call); // (1)It uses the scope of the inferred function definition as its "outer scope" because sometimes functions refer to constants in the local scopes they were originally defined in. Usually, these constants are resolved if the function definition is not inferred, so there's no need to store the scope path after it's resolved. However, since inferred definitions are resolved at the call-site, they need a way to recall the scope path for when they were initially created.
After this I loop through the arguments and try to (1) pattern match the arg types against the expected type patterns.
size_t inferred_arg_start = an_func_def_arg_start(inferred_funcdef);
size_t inferred_arg_end = an_func_def_arg_end(inferred_funcdef);
for (size_t i = inferred_arg_start; i < inferred_arg_end; ++i) {
ast_node_t *decl = inferred_funcdef->children.items[i];
size_t arg_call_start = an_call_arg_start(call);
ast_node_t *call_arg = call->children.items[i-inferred_arg_start+arg_call_start];
for (size_t t = 0; t < decl->type_decl_patterns.count; ++t) {
type_pattern_t pattern = decl->type_decl_patterns.items[t];
resolve_expression(analyzer, analyzer->ast, state, typeid(TYPE_UNRESOLVED), call_arg);
matched_value_t matched_value = stan_pattern_match_or_error(analyzer, decl, pattern.expected, call_arg->value_type); // (1)
array_push(&matched_values, matched_value);
if (TYPE_IS_INVALID(matched_value.type)) {
had_error = true;
continue;
}
ast_node_t *implicit_type_decl = ast_implicit_expr(analyzer->ast, typeid(TYPE_TYPE), WORDT(matched_value.type), token_implicit_at_end(pattern.identifier));
ast_node_t *implicit_init_expr = ast_implicit_expr(analyzer->ast, matched_value.type, matched_value.word, token_implicit_at_end(pattern.identifier));
ast_node_t *implicit_constant_decl = ast_decldef(analyzer->ast, pattern.identifier, implicit_type_decl, implicit_init_expr);
implicit_constant_decl->is_mutable = false;
resolve_declaration_definition(analyzer, analyzer->ast, new_state, implicit_constant_decl);
}
}If the matches are successful, then an implicit constant declaration is created and put into the inferred function scope with whatever the type resolved to.
In the case that the add gets called like this add(1, 2), once 1 is resolved to be an integer type, it tries to match the argument types with their corresponding "type pattern" by walking down the type pattern path, and checking if the subtypes are valid. Since the type pattern immediately leads to a type, u is resolved as an int.
append :: (&[10]!u, u)For a signature like the one above, if you tried calling it like this append(10, 10), the type of 10 is an int, and when the pattern matcher tries to match it with u it will see that it cannot progress past the integer type and will error out.
Here's the pattern matching function it's quite simple and short right now, since there aren't many ways to create types with subtypes:
static matched_value_t stan_pattern_match_or_error(analyzer_t *analyzer, ast_node_t *decl, type_path_t *expected, type_t actual) {
typedata_t *td = ast_type2td(analyzer->ast, actual);
switch (expected->kind) {
case MATCH_TYPE_POINTER: {
if (td->kind != TYPE_POINTER) {
stan_error(analyzer, make_error_node(ERROR_ANALYSIS_COULD_NOT_PATTERN_MATCH_TYPE, decl));
return (matched_value_t){.type=typeid(TYPE_INVALID)};
}
return stan_pattern_match_or_error(analyzer, decl, expected->next, td->as.ptr.type);
}
case MATCH_TYPE_ARRAY_TYPE: {
if (td->kind != TYPE_ARRAY) {
stan_error(analyzer, make_error_node(ERROR_ANALYSIS_COULD_NOT_PATTERN_MATCH_TYPE, decl));
return (matched_value_t){.type=typeid(TYPE_INVALID)};
}
return stan_pattern_match_or_error(analyzer, decl, expected->next, td->as.arr.type);
}
case MATCH_TYPE_ARRAY_SIZE: {
if (td->kind != TYPE_ARRAY) {
stan_error(analyzer, make_error_node(ERROR_ANALYSIS_COULD_NOT_PATTERN_MATCH_TYPE, decl));
return (matched_value_t){.type=typeid(TYPE_INVALID)};
}
if (expected->next->kind != MATCH_TYPE_IDENTIFIER) {
stan_error(analyzer, make_error_node(ERROR_ANALYSIS_COULD_NOT_PATTERN_MATCH_TYPE, decl));
return (matched_value_t){.type=typeid(TYPE_INVALID)};
}
return (matched_value_t){
.type=analyzer->ast->type_set.size_t_,
.word=WORDU(td->as.arr.count),
};
}
case MATCH_TYPE_IDENTIFIER: {
return (matched_value_t){
.type=typeid(TYPE_TYPE),
.word=WORDT(actual),
};
}
default: UNREACHABLE();
}
}Finally, back to stan_realize_inferred_funcdef_or_error_and_null we are ready to try and realize the function. First I (1) check to see if I've already inferred a function with the same resolved matched types. (2) Unless I already have a copy, I need to (3) create one. From there, result holds an unresolved function definition, and that's (4) passed into the function that resolves it. Then I just (5) make sure to cache it so I don't duplicate this again for the same types.
ast_node_t *result = NULL;
unless (had_error) {
result = find_realized_funcdef_or_null_by_inferred_types(inferred_funcdef->realized_funcdef_copies, matched_values); // (1)
unless(result) { // (2)
result = ast_node_copy(analyzer->ast, inferred_funcdef); // (3)
resolve_funcdef(analyzer, analyzer->ast, new_state, result); // (4)
matched_values_t matched_values_ = {.allocator=analyzer->ast->arena};
for (size_t i = 0; i < matched_values.count; ++i) array_push(&matched_values_, matched_values.items[i]);
inferred_funcdef_copy_t copy = {
.key = matched_values_,
.funcdef = result,
};
array_push(&inferred_funcdef->realized_funcdef_copies, copy); // (5)
}
}And that's it! That's pretty much all the new code I needed to write to implement generics within orso. I'm pretty happy with how little changes I needed to make to the entire compiler pipeline, it was pretty much all in just two parts of the static analyzer.
For codegen, if I encounter an inferred function type, I just skip it, and instead generate code for its copies.
What's cool about this is that it reuses almost the entire pipeline used for resolving function definitions, including the circular dependency checks needed for CTFE.
And the rest of the compiler pipeline continues to function as normal.
Anyways... Off to writing a bunch of tests... Hopefully next time I'll be back with the base language being almost complete.