diff options
| -rw-r--r-- | boot/ir.c | 36 | ||||
| -rw-r--r-- | boot/lower.c | 93 | ||||
| -rw-r--r-- | boot/transpile.c | 188 | ||||
| -rw-r--r-- | boot/visit/ir.c | 18 |
4 files changed, 296 insertions, 39 deletions
@@ -249,6 +249,7 @@ enum Expression_Kind EXPRESSION_CAST, EXPRESSION_CONSTRUCT, EXPRESSION_INCREMENT_DECREMENT, + EXPRESSION_FUNCTION_REF, }; struct Expression_Integer_Literal @@ -310,6 +311,10 @@ struct Expression_Call struct Expression* subject; // arguments of call in written order, the inner slot decides final ordering. Array(struct Call_Argument) arguments; + // direct calls can emit a simple call without additional syntax, + // however indirect calls which have closed-over state have to call + // them taking into account the function pointer and the state first. + bool is_indirect; }; struct Expression_Member @@ -351,6 +356,14 @@ struct Expression_Increment_Decrement struct Expression* subject; }; +// reference to a known catskill function in a value context. +struct Expression_Function_Ref +{ + Function_Id function_id; + // matching synthetic closure type for the function's signature. + Type_Id closure_type_id; +}; + union Expression_Value { struct Expression_Integer_Literal integer_literal; @@ -367,6 +380,7 @@ union Expression_Value struct Expression_Cast cast; struct Expression_Construct construct; struct Expression_Increment_Decrement increment_decrement; + struct Expression_Function_Ref function_ref; }; struct Expression @@ -402,6 +416,14 @@ struct Function Array(struct Param) params; bool variadic; // is last parameter variadic? + // matching fat-closure struct type for this function's signature. + // synthesized lazily on first reference in value context, or 0. + Type_Id closure_type_id; + + // tree-side header which produced this function node. + // required for synthesizing the closure type after function is lowered. + struct Tree_Function_Header* ast_header; + // first lowering pass only fills out the ast body and not the lowered body, // to collect all top-declarations. struct Tree_Block* ast_body; @@ -647,11 +669,14 @@ ir_make_sizeof(struct Type_Ref target, struct Span span) } struct Expression* -ir_make_call(struct Expression* subject, Array(struct Call_Argument) arguments, struct Span span) +ir_make_call( + struct Expression* subject, Array(struct Call_Argument) arguments, bool is_indirect, + struct Span span) { union Expression_Value v = { 0 }; v.call.subject = subject; v.call.arguments = arguments; + v.call.is_indirect = is_indirect; return expression_new(EXPRESSION_CALL, v, span); } @@ -703,6 +728,15 @@ ir_make_increment_decrement( return expression_new(EXPRESSION_INCREMENT_DECREMENT, v, span); } +struct Expression* +ir_make_function_ref(Function_Id function_id, Type_Id closure_type_id, struct Span span) +{ + union Expression_Value v = { 0 }; + v.function_ref.function_id = function_id; + v.function_ref.closure_type_id = closure_type_id; + return expression_new(EXPRESSION_FUNCTION_REF, v, span); +} + struct Type_Ref type_ref_bare(Type_Id type_id) { diff --git a/boot/lower.c b/boot/lower.c index 696f3e4..ba83b39 100644 --- a/boot/lower.c +++ b/boot/lower.c @@ -644,10 +644,30 @@ lower_fill_function_signature( } fn->variadic = variadic; fn->main_takes_args = fn->is_main && array_length(&fn->params) > 0; + fn->ast_header = &fn_expr->value.function.header; fn->ast_body = &fn_expr->value.function.body; fn->body = nil; } +// synthesize the function's signature as a structural closure type +// the first time the function is referenced in value context, or reuse already +// synthesized type. +Type_Id +lower_function_closure_type(struct Lower_Context* ctx, struct Function* fn) +{ + if (fn->closure_type_id != 0) return fn->closure_type_id; + + struct Tree_Type wrapper = { + .type = TREE_TYPE_FUNCTION, + .value = { .function = { .header = *fn->ast_header } }, + .span = fn->ast_header->span, + .location = fn->ast_header->location, + }; + struct Type_Ref ref = lower_intern_type_ref(ctx, &wrapper); + fn->closure_type_id = ref.type_id; + return ref.type_id; +} + void lower_fill_type_body(struct Lower_Context* ctx, struct Type* type, struct Tree_Type* tree_type) { @@ -837,6 +857,7 @@ lower_pass_1(struct Lower_Context* ctx, struct Tree* tree) struct Block* lower_block(struct Lower_Context* ctx, struct Tree_Block* tree_block); struct Statement* lower_statement(struct Lower_Context* ctx, struct Tree_Statement* tree_stmt); struct Expression* lower_expression(struct Lower_Context* ctx, struct Tree_Expression* tree_expr); +bool lower_name_is_function_typed_local(struct Lower_Context* ctx, struct String name); struct Expression* lower_expression_integer_literal(struct Lower_Context* ctx, struct Tree_Expression* tree_expr) @@ -869,7 +890,15 @@ lower_expression_boolean_literal(struct Lower_Context* ctx, struct Tree_Expressi struct Expression* lower_expression_name(struct Lower_Context* ctx, struct Tree_Expression* tree_expr) { - (void)ctx; + // names that resolve to a catskill function become a function reference. + Function_Id fn_id; + if (lower_function_lookup_by_name(ctx->unit, tree_expr->value.name.name, &fn_id)) { + // since this path is only taken outside direct call-positions, + // the function will need a closure type to wrap it as a value. + struct Function* fn = *array_at(struct Function*, &ctx->unit->functions.entries, fn_id); + Type_Id closure_type_id = lower_function_closure_type(ctx, fn); + return ir_make_function_ref(fn_id, closure_type_id, tree_expr->span); + } return ir_make_name(tree_expr->value.name.name, tree_expr->span); } @@ -1092,13 +1121,24 @@ lower_expression_call(struct Lower_Context* ctx, struct Tree_Expression* tree_ex // only catskill-side functions are in the function table, calls to libc // and the like go through as positional with no named args allowed. struct Function* callee = nil; + Function_Id callee_id = 0; + bool is_indirect = false; if (subject_tree && subject_tree->kind == TREE_EXPRESSION_NAME) { - Function_Id fn_id; - if (lower_function_lookup_by_name(ctx->unit, subject_tree->value.name.name, &fn_id)) - callee = *array_at(struct Function*, &ctx->unit->functions.entries, fn_id); + if (lower_function_lookup_by_name(ctx->unit, subject_tree->value.name.name, &callee_id)) + callee = *array_at(struct Function*, &ctx->unit->functions.entries, callee_id); + else if (lower_name_is_function_typed_local(ctx, subject_tree->value.name.name)) + is_indirect = true; + } else if (subject_tree) { + // any subject that isn't a bare name (member, subscript, call result, closure, anything + // that's not literally just a name) yields a fat closure value at the call site by default. + is_indirect = true; } - struct Expression* subject = lower_expression(ctx, subject_tree); + // for direct calls to a known catskill function, build the reference + // subject directly so we don't drag the function into value-context synthesis! + struct Expression* subject = + callee ? ir_make_function_ref(callee_id, 0, subject_tree->span) + : lower_expression(ctx, subject_tree); Array(struct Call_Argument) arguments; if (callee) { @@ -1126,7 +1166,7 @@ lower_expression_call(struct Lower_Context* ctx, struct Tree_Expression* tree_ex } } - return ir_make_call(subject, arguments, tree_expr->span); + return ir_make_call(subject, arguments, is_indirect, tree_expr->span); } struct Expression* @@ -1181,9 +1221,8 @@ lower_expression_type(struct Lower_Context* ctx, struct Tree_Expression* tree_ex } // anonymous function: lift it up as a synthetic function table entry, -// replace the expression with a name reference. -// TODO: should we have a better kind of reference here than a name? -// maybe a function reference somehow? +// and emit a function reference so the use site can wrap it as a fat +// closure value. struct Expression* lower_expression_function(struct Lower_Context* ctx, struct Tree_Expression* tree_expr) { @@ -1200,7 +1239,10 @@ lower_expression_function(struct Lower_Context* ctx, struct Tree_Expression* tre fn->synthetic = true; lower_fill_function_signature(ctx, fn, tree_expr); - return ir_make_name(name, tree_expr->span); + // a function literal is always in value context, we can synthesize + // the closure type eagerly right here. + Type_Id closure_type_id = lower_function_closure_type(ctx, fn); + return ir_make_function_ref(id, closure_type_id, tree_expr->span); } struct Expression* @@ -1326,6 +1368,37 @@ lower_is_shadowing(struct Lower_Context* ctx, struct String name) return false; } +// look up a local by name across all active scopes, returning its type. +// returns false if no local with that name exists in scope. +bool +lower_local_lookup(struct Lower_Context* ctx, struct String name, struct Type_Ref* out_type) +{ + for (uint i = ctx->scope_stack.length; i > 0; --i) { + struct Scope* scope = array_at(struct Scope, &ctx->scope_stack, i - 1); + + FOR_EACH_ARRAY (struct Local_Variable, var, &scope->variables) { + if (string_equals(var->name, name)) { + if (out_type) *out_type = var->type; + return true; + } + } + } + + return false; +} + +// is the named local a function-typed value? +// (used to decide direct vs. indirect call dispatch when the call subject is a bare name.) +bool +lower_name_is_function_typed_local(struct Lower_Context* ctx, struct String name) +{ + struct Type_Ref ref; + if (!lower_local_lookup(ctx, name, &ref)) return false; + if (array_length(&ref.mods) > 0) return false; // references are not callable! + struct Type* type = *array_at(struct Type*, &ctx->unit->types.entries, ref.type_id); + return type->kind == TYPE_FUNCTION; +} + struct Statement* lower_statement_return(struct Lower_Context* ctx, struct Tree_Statement* tree_stmt) { diff --git a/boot/transpile.c b/boot/transpile.c index 9c94706..9b8f420 100644 --- a/boot/transpile.c +++ b/boot/transpile.c @@ -146,7 +146,9 @@ transpile_visit_type_ref(struct Visit* visit, struct Type_Ref* ref) if (primitive) { TRANSPILE_WRITE("%s", primitive); - } else if (target && (target->kind == TYPE_STRUCTURE || target->kind == TYPE_VARIANT)) { + } else if (target + && (target->kind == TYPE_STRUCTURE || target->kind == TYPE_VARIANT + || target->kind == TYPE_FUNCTION)) { TRANSPILE_WRITE("struct %s", string_c_str(target->name)); } else if (target) { TRANSPILE_WRITE("%s", string_c_str(target->name)); @@ -174,27 +176,23 @@ transpile_visit_type_forward_variant(struct Visit* visit, struct Type* type) TRANSPILE_WRITE("struct %s;\n", string_c_str(type->name)); } +// emit the fat closure struct that represents any function-typed value. +// bare (normal) functions wrap into this via a thunk with a nil state. void transpile_visit_type_forward_function(struct Visit* visit, struct Type* type) { TRANSPILE_PREAMBLE - - // referenced function types are emitted as a typedef - TRANSPILE_WRITE("typedef "); + TRANSPILE_WRITE("struct %s {\n", string_c_str(type->name)); + TRANSPILE_WRITE(" void* state;\n"); + TRANSPILE_WRITE(" "); VISIT(visit_type_ref, &type->value.function.return_type); - TRANSPILE_WRITE(" (*%s)(", string_c_str(type->name)); - if (array_length(&type->value.function.params) == 0) { - TRANSPILE_WRITE("void"); - } else { - bool first = true; - FOR_EACH_ARRAY (struct Type_Ref, param, &type->value.function.params) { - if (!first) TRANSPILE_WRITE(", "); - VISIT(visit_type_ref, param); - first = false; - } - if (type->value.function.variadic) TRANSPILE_WRITE(", ..."); + TRANSPILE_WRITE(" (*call)(void* state"); + FOR_EACH_ARRAY (struct Type_Ref, param, &type->value.function.params) { + TRANSPILE_WRITE(", "); + VISIT(visit_type_ref, param); } - TRANSPILE_WRITE(");\n"); + if (type->value.function.variadic) TRANSPILE_WRITE(", ..."); + TRANSPILE_WRITE(");\n};\n"); } void @@ -280,6 +278,52 @@ transpile_function_c_name(struct Function* function) return string_c_str(function->name); } +// the c-side name of the thunk that wraps a function as a fat closure value. +struct String +transpile_function_thunk_name(struct Function* function) +{ + struct String_Buffer buf = string_buffer_new(64); + string_buffer_append_c_str(&buf, "__cat_thunk_"); + string_buffer_append_c_str(&buf, transpile_function_c_name(function)); + return string_buffer_to_string(&buf); +} + +// emit thunk wrapper for a normal function, allowing them to be used +// like closures. +void +transpile_function_emit_thunk(struct Visit* visit, struct Function* function) +{ + TRANSPILE_PREAMBLE + + VISIT(visit_type_ref, &function->return_type); + struct String thunk_name = transpile_function_thunk_name(function); + TRANSPILE_WRITE(" %s(void* state", string_c_str(thunk_name)); + FOR_EACH_ARRAY (struct Param, param, &function->params) { + TRANSPILE_WRITE(", "); + VISIT(visit_type_ref, ¶m->type); + TRANSPILE_WRITE(" %s", string_c_str(param->name)); + } + if (function->variadic) TRANSPILE_WRITE(", ..."); + TRANSPILE_WRITE(") {\n (void)state;\n "); + + // non-returning functions can't return a value, crazy! + struct Type* return_type = transpile_type_at(transpiler, function->return_type.type_id); + bool returns_void = + return_type && return_type->id == transpiler->unit->types.primitive_void_id + && array_length(&function->return_type.mods) == 0; + if (!returns_void) TRANSPILE_WRITE("return "); + TRANSPILE_WRITE("%s(", transpile_function_c_name(function)); + bool first = true; + FOR_EACH_ARRAY (struct Param, param, &function->params) { + if (!first) TRANSPILE_WRITE(", "); + TRANSPILE_WRITE("%s", string_c_str(param->name)); + first = false; + } + TRANSPILE_WRITE(");\n}\n"); +} + +void transpile_emit_indent(struct Transpiler* transpiler); + // emits c-side format of a function header. // shared by the signature and body passes. void @@ -289,15 +333,21 @@ transpile_function_emit_signature(struct Visit* visit, struct Function* function VISIT(visit_type_ref, &function->return_type); TRANSPILE_WRITE(" %s(", transpile_function_c_name(function)); - if (array_length(&function->params) == 0) { + bool need_separator = false; + if (function->synthetic) { + // synthetic functions implicitly take in state + TRANSPILE_WRITE("void* state"); + need_separator = true; + } + + if (array_length(&function->params) == 0 && !need_separator) { TRANSPILE_WRITE("void"); } else { - bool first = true; FOR_EACH_ARRAY (struct Param, param, &function->params) { - if (!first) TRANSPILE_WRITE(", "); + if (need_separator) TRANSPILE_WRITE(", "); VISIT(visit_type_ref, ¶m->type); TRANSPILE_WRITE(" %s", string_c_str(param->name)); - first = false; + need_separator = true; } if (function->variadic) TRANSPILE_WRITE(", ..."); } @@ -310,6 +360,19 @@ transpile_visit_function_signature(struct Visit* visit, struct Function* functio TRANSPILE_PREAMBLE transpile_function_emit_signature(visit, function); TRANSPILE_WRITE(";\n"); + + // a thunk only exists for thin, named functions referenced as values! + if (function->synthetic || function->closure_type_id == 0) return; + + VISIT(visit_type_ref, &function->return_type); + struct String thunk_name = transpile_function_thunk_name(function); + TRANSPILE_WRITE(" %s(void* state", string_c_str(thunk_name)); + FOR_EACH_ARRAY (struct Param, param, &function->params) { + TRANSPILE_WRITE(", "); + VISIT(visit_type_ref, ¶m->type); + } + if (function->variadic) TRANSPILE_WRITE(", ..."); + TRANSPILE_WRITE(");\n"); } void @@ -317,13 +380,32 @@ transpile_visit_function_body(struct Visit* visit, struct Function* function) { TRANSPILE_PREAMBLE transpile_function_emit_signature(visit, function); - TRANSPILE_WRITE(" "); - if (function->body) { - VISIT(visit_block, function->body); - } else { - TRANSPILE_WRITE("{\n}"); + + if (!function->body) { + TRANSPILE_WRITE(" {\n}\n"); + return; } + + // add a void cast for the implicit state argument, in case synthetic + // function does not need to use it + if (function->synthetic) { + TRANSPILE_WRITE(" {\n"); + transpiler->indent_level++; + transpile_emit_indent(transpiler); + TRANSPILE_WRITE("(void)state;\n"); + FOR_EACH_ARRAY (struct Statement*, statement, &function->body->statements) + VISIT(visit_statement, *statement); + transpiler->indent_level--; + transpile_emit_indent(transpiler); + TRANSPILE_WRITE("}\n"); + return; + } + + TRANSPILE_WRITE(" "); + VISIT(visit_block, function->body); TRANSPILE_WRITE("\n"); + + if (function->closure_type_id != 0) transpile_function_emit_thunk(visit, function); } void @@ -448,14 +530,33 @@ transpile_visit_expression_call(struct Visit* visit, struct Expression* expressi { TRANSPILE_PREAMBLE - transpile_emit_expression(visit, expression->value.call.subject, TRANSPILE_PRECEDENCE_POSTFIX); - TRANSPILE_WRITE("("); + struct Expression* subject = expression->value.call.subject; + bool is_indirect = expression->value.call.is_indirect; + + if (!is_indirect && subject && subject->kind == EXPRESSION_FUNCTION_REF) { + // direct calls emit the subject bare + struct Function* fn = *array_at( + struct Function*, &transpiler->unit->functions.entries, + subject->value.function_ref.function_id); + TRANSPILE_WRITE("%s", transpile_function_c_name(fn)); + } else if (is_indirect) { + // route through the fat closure value's call slot, passing state + transpile_emit_expression(visit, subject, TRANSPILE_PRECEDENCE_POSTFIX); + TRANSPILE_WRITE(".call("); + transpile_emit_expression(visit, subject, TRANSPILE_PRECEDENCE_POSTFIX); + TRANSPILE_WRITE(".state"); + } else { + transpile_emit_expression(visit, subject, TRANSPILE_PRECEDENCE_POSTFIX); + } + + if (!is_indirect) TRANSPILE_WRITE("("); + Array(struct Call_Argument) args = expression->value.call.arguments; uint max_slot = 0; FOR_EACH_ARRAY (struct Call_Argument, a, &args) { if (a->slot > max_slot) max_slot = a->slot; } - bool first = true; + bool first = !is_indirect; for (uint s = 0; s <= max_slot; ++s) { FOR_EACH_ARRAY (struct Call_Argument, a, &args) { if (a->slot != s) continue; @@ -519,6 +620,36 @@ transpile_visit_expression_construct(struct Visit* visit, struct Expression* exp } void +transpile_visit_expression_function_ref(struct Visit* visit, struct Expression* expression) +{ + TRANSPILE_PREAMBLE + + struct Function* fn = *array_at( + struct Function*, &transpiler->unit->functions.entries, + expression->value.function_ref.function_id); + + // we only get here when the function reference is explicitly a *value*, + // any direct calls are filtered out earlier. + struct Type* closure_type = + transpile_type_at(transpiler, expression->value.function_ref.closure_type_id); + + const ascii* call_name; + struct String thunk_name = string_empty(); + if (fn->synthetic) { + // synthetic functions are already fat-by-default, can call directly + call_name = transpile_function_c_name(fn); + } else { + // thin named functions go through their generated thunk to match the + // fat calling convention + thunk_name = transpile_function_thunk_name(fn); + call_name = string_c_str(thunk_name); + } + + TRANSPILE_WRITE( + "(struct %s){ .state = nil, .call = %s }", string_c_str(closure_type->name), call_name); +} + +void transpile_visit_expression_increment_decrement(struct Visit* visit, struct Expression* expression) { TRANSPILE_PREAMBLE @@ -718,6 +849,7 @@ struct Visit_Table transpile_body_visit_functions = { .visit_expression_cast = transpile_visit_expression_cast, .visit_expression_construct = transpile_visit_expression_construct, .visit_expression_increment_decrement = transpile_visit_expression_increment_decrement, + .visit_expression_function_ref = transpile_visit_expression_function_ref, }; // walk a lowered translation unit and emit c source into the transpiler's output. diff --git a/boot/visit/ir.c b/boot/visit/ir.c index 036307f..fa17d9c 100644 --- a/boot/visit/ir.c +++ b/boot/visit/ir.c @@ -63,6 +63,7 @@ struct Visit_Table void (*visit_expression_cast)(struct Visit* visitor, struct Expression* expr); void (*visit_expression_construct)(struct Visit* visitor, struct Expression* expr); void (*visit_expression_increment_decrement)(struct Visit* visitor, struct Expression* expr); + void (*visit_expression_function_ref)(struct Visit* visitor, struct Expression* expr); void (*visit_block)(struct Visit* visitor, struct Block* block); void (*visit_type_ref)(struct Visit* visitor, struct Type_Ref* ref); @@ -289,6 +290,9 @@ walk_expression(struct Visit* visit, struct Expression* expr) case EXPRESSION_INCREMENT_DECREMENT: VISIT(visit_expression_increment_decrement, expr); break; + case EXPRESSION_FUNCTION_REF: + VISIT(visit_expression_function_ref, expr); + break; case EXPRESSION_NONE: break; default: @@ -362,6 +366,8 @@ walk_expression_increment_decrement(struct Visit* visit, struct Expression* expr VISIT(visit_expression, expr->value.increment_decrement.subject); } +WALK_LEAF_FUNCTION(walk_expression_function_ref, struct Expression*); + void walk_block(struct Visit* visit, struct Block* block) { @@ -413,6 +419,7 @@ struct Visit_Table walk_functions = { .visit_expression_cast = walk_expression_cast, .visit_expression_construct = walk_expression_construct, .visit_expression_increment_decrement = walk_expression_increment_decrement, + .visit_expression_function_ref = walk_expression_function_ref, .visit_block = walk_block, .visit_type_ref = walk_type_ref, @@ -943,6 +950,16 @@ printer_visit_expression_increment_decrement(struct Visit* visit, struct Express } void +printer_visit_expression_function_ref(struct Visit* visit, struct Expression* expr) +{ + PRINTER_PREAMBLE + + struct Function* fn = *array_at( + struct Function*, &p->unit->functions.entries, expr->value.function_ref.function_id); + PRINT("(fn-ref %s)", string_c_str(fn->name)); +} + +void printer_visit_block(struct Visit* visit, struct Block* block) { PRINTER_PREAMBLE @@ -1080,6 +1097,7 @@ struct Visit_Table printer_visit_functions = { .visit_expression_cast = printer_visit_expression_cast, .visit_expression_construct = printer_visit_expression_construct, .visit_expression_increment_decrement = printer_visit_expression_increment_decrement, + .visit_expression_function_ref = printer_visit_expression_function_ref, .visit_block = printer_visit_block, .visit_type_ref = printer_visit_type_ref, |