diff options
Diffstat (limited to 'boot/type_check.cc')
| -rw-r--r-- | boot/type_check.cc | 476 |
1 files changed, 445 insertions, 31 deletions
diff --git a/boot/type_check.cc b/boot/type_check.cc index cdc78df..ab22a1c 100644 --- a/boot/type_check.cc +++ b/boot/type_check.cc @@ -114,6 +114,51 @@ namespace elna::boot }, this->payload); } + generic_error::generic_error(const source_position position, const std::string& generic_name, + payload_type payload) + : diagnostic(position), generic_name(generic_name), payload(std::move(payload)) + { + } + + std::string generic_error::what() const + { + return std::visit([this](auto&& payload) -> std::string + { + using T = std::decay_t<decltype(payload)>; + + if constexpr (std::is_same_v<T, not_generic>) + { + return "'" + this->generic_name + "' is not generic and cannot take type arguments"; + } + else if constexpr (std::is_same_v<T, unused_parameter>) + { + return "Type parameter '" + payload.parameter + "' of '" + + this->generic_name + "' is not used"; + } + else if constexpr (std::is_same_v<T, argument_not_pointer>) + { + return "Type '" + payload.actual.to_string() + "' cannot be a type argument of '" + + this->generic_name + "', it is not a pointer type"; + } + else if constexpr (std::is_same_v<T, constant_argument>) + { + return "Constant type '" + payload.actual.to_string() + + "' cannot be a type argument of '" + this->generic_name + "'"; + } + else if constexpr (std::is_same_v<T, uninferrable_parameter>) + { + return "Type parameter '" + payload.parameter + "' of '" + this->generic_name + + "' cannot be inferred, give the type arguments explicitly"; + } + else if constexpr (std::is_same_v<T, shape_mismatch>) + { + return "Cannot infer the type arguments of '" + this->generic_name + + "': parameter type '" + payload.declared.to_string() + + "' does not match argument type '" + payload.actual.to_string() + "'"; + } + }, this->payload); + } + /// The program body is the only callable without a name. static std::string describe_callable(const std::string& identifier) { @@ -228,6 +273,12 @@ namespace elna::boot case opaque_arithmetic: return "Opaque type '" + this->actual.to_string() + "' cannot be used as an element type in pointer arithmetic"; + case dereference_of_parameter: + return "Type parameter '" + this->actual.to_string() + + "' cannot be dereferenced, its pointee is unknown"; + case parameter_arithmetic: + return "Type parameter '" + this->actual.to_string() + + "' cannot be used in pointer arithmetic, its element size is unknown"; case zero_sized: return "Zero-sized type '" + this->actual.to_string() + "' cannot be declared"; @@ -261,8 +312,20 @@ namespace elna::boot case array: entity = "array initializer '" + this->applicand + "'"; break; + case generic: + entity = "generic '" + this->applicand + "'"; + break; + } + std::string noun = "arguments"; + + if (this->m_kind == kind::array) + { + noun = "elements"; + } + else if (this->m_kind == kind::generic) + { + noun = "type arguments"; } - const std::string noun = this->m_kind == kind::array ? "elements" : "arguments"; const std::string quantifier = actual > expected ? "many" : "few"; return "Too " + quantifier + " " + noun + " for " + entity @@ -348,17 +411,25 @@ namespace elna::boot } /* - * Scaling an offset needs the pointee size, which an opaque type doesn't - * have. Only a pointer_type scales; the generic Pointer and procedure - * values advance byte-wise. + * Scaling an offset needs the pointee size, which neither an opaque type + * nor a type parameter has. Only a pointer_type scales; the generic + * Pointer and procedure values advance byte-wise. */ - static std::optional<type> find_opaque_arithmetic(binary_operator operation, + static std::optional<type> find_arithmetic_violation(binary_operator operation, const type& lhs, const type& rhs) { if (operation != binary_operator::sum && operation != binary_operator::subtraction) { return std::nullopt; } + if (lhs.get<parameter_type>() != nullptr) + { + return lhs; + } + if (rhs.get<parameter_type>() != nullptr) + { + return rhs; + } const bool lhs_integral = is_integral_type(lhs); if (lhs_integral == is_integral_type(rhs)) @@ -444,19 +515,6 @@ namespace elna::boot * * Base record type must not be null. Derived record type may be null. */ - static bool is_base_of(const std::shared_ptr<record_type>& base, - const std::shared_ptr<record_type>& derived) - { - if (derived != nullptr) - { - if (auto current_record = resolve_underlying_type(derived->base).get<record_type>()) - { - return current_record == base || is_base_of(base, current_record); - } - } - return false; - } - assign_check::verdict assign_check::guard_const_laundering() const { if (!is_primitive_type(ctx.aliased_assignee, "Pointer")) @@ -519,10 +577,11 @@ namespace elna::boot return verdict::reject; } // A pointer to a record can be assigned to a pointer to its base type. - if (auto assignee_record = resolve_underlying_type(assignee_ptr->base).get<record_type>()) + // An instantiation is terminal in resolution, so the erased view is + // what decides whether a record is in play at all. + if (erase_generic(assignee_ptr->base).get<record_type>() != nullptr) { - return is_base_of(assignee_record, - resolve_underlying_type(assignment_ptr->base).get<record_type>()) + return is_base_of(assignee_ptr->base, assignment_ptr->base) ? verdict::accept : verdict::pass; } return verdict::pass; @@ -631,6 +690,10 @@ namespace elna::boot } walking_visitor::visit(declaration); + check_parameters_used(declaration->position(), declaration->identifier.name(), + this->current_procedure->parameters, + type(std::make_shared<procedure_type>(this->current_procedure->symbol))); + std::size_t parameter_index = 0; for (const type& parameter : this->current_procedure->symbol.parameters) @@ -870,6 +933,13 @@ namespace elna::boot { walking_visitor::visit(declaration); auto unresolved_type = this->bag.lookup(declaration->identifier.name())->is_type()->symbol.get<alias_type>(); + + if (auto generic = unresolved_type->referent.get<generic_type>()) + { + check_parameters_used(declaration->position(), declaration->identifier.name(), + generic->parameters, generic->referent); + return; + } const type referent = resolve_aliases(unresolved_type->referent); if (auto record = referent.get<record_type>()) @@ -948,7 +1018,7 @@ namespace elna::boot } else { - type const base_type = resolve_underlying_type(base_symbol->is_type()->symbol); + type const base_type = erase_generic(base_symbol->is_type()->symbol); if (base_type.get<record_type>() == nullptr) { add_error<type_requirement_error>(expression->position(), @@ -959,11 +1029,343 @@ namespace elna::boot walking_visitor::visit(expression); } + /* + * Aliases are not entered: a parameter is only in scope in its own + * declaration, so another declaration can never mention it. Instantiations + * contribute their arguments and not their generic, which is what makes + * the walk terminate on a recursive generic. + */ + static bool occurs_in(const type& parameter, const type& subject) + { + if (subject.get<parameter_type>() == parameter.get<parameter_type>()) + { + return true; + } + if (auto pointer = subject.get<pointer_type>()) + { + return occurs_in(parameter, pointer->base); + } + if (auto slice = subject.get<slice_type>()) + { + return occurs_in(parameter, slice->base); + } + if (auto array = subject.get<array_type>()) + { + return occurs_in(parameter, array->base); + } + if (auto qualified = subject.get<constant_type>()) + { + return occurs_in(parameter, qualified->unqualified); + } + if (auto record = subject.get<record_type>()) + { + for (const auto& [field_name, field_type] : record->fields) + { + if (occurs_in(parameter, field_type)) + { + return true; + } + } + return !record->base.empty() && occurs_in(parameter, record->base); + } + if (auto procedure = subject.get<procedure_type>()) + { + for (const type& parameter_type : procedure->parameters) + { + if (occurs_in(parameter, parameter_type)) + { + return true; + } + } + return !procedure->return_type.proper_type.empty() + && occurs_in(parameter, procedure->return_type.proper_type); + } + if (auto instance = subject.get<instantiated_type>()) + { + for (const type& argument : instance->arguments) + { + if (occurs_in(parameter, argument)) + { + return true; + } + } + } + return false; + } + + void type_analysis_visitor::check_parameters_used(const source_position position, + const std::string& name, const std::vector<type>& parameters, const type& heading) + { + for (const type& parameter : parameters) + { + if (!occurs_in(parameter, heading)) + { + add_error<generic_error>(position, name, + generic_error::unused_parameter{ parameter.to_string() }); + } + } + } + + /* + * Walks a declared parameter type and an actual argument type in parallel, + * binding a parameter the first time it is met and leaving every later + * occurrence to the ordinary assignability check. Both sides are resolved + * at every step, so a transparent instantiation is seen through and only a + * record-referent one is compared as an instantiation. + * + * Returns false when the walk fails on shape rather than on type. + */ + static bool bind_arguments(const std::vector<type>& parameters, std::vector<type>& bindings, + const type& declared, const type& actual) + { + const type left = resolve_aliases(declared); + const type right = resolve_aliases(actual); + + if (auto parameter = left.get<parameter_type>()) + { + for (std::size_t i = 0; i < parameters.size(); ++i) + { + if (parameters[i].get<parameter_type>() == parameter && bindings[i].empty()) + { + // The actual type is recorded as it stands, which inside a + // generic body may itself be an abstract parameter. + bindings[i] = actual; + } + } + return true; + } + if (auto left_pointer = left.get<pointer_type>()) + { + auto right_pointer = right.get<pointer_type>(); + + return right_pointer != nullptr + && bind_arguments(parameters, bindings, left_pointer->base, right_pointer->base); + } + if (auto left_slice = left.get<slice_type>()) + { + auto right_slice = right.get<slice_type>(); + + return right_slice != nullptr + && bind_arguments(parameters, bindings, left_slice->base, right_slice->base); + } + if (auto left_array = left.get<array_type>()) + { + auto right_array = right.get<array_type>(); + + return right_array != nullptr + && bind_arguments(parameters, bindings, left_array->base, right_array->base); + } + if (auto left_constant = left.get<constant_type>()) + { + auto right_constant = right.get<constant_type>(); + + return right_constant != nullptr + && bind_arguments(parameters, bindings, + left_constant->unqualified, right_constant->unqualified); + } + if (auto left_instance = left.get<instantiated_type>()) + { + for (type candidate = right; !candidate.empty(); candidate = base_of(candidate)) + { + auto right_instance = resolve_aliases(candidate).get<instantiated_type>(); + + if (right_instance == nullptr + || !(left_instance->generic == right_instance->generic) + || left_instance->arguments.size() != right_instance->arguments.size()) + { + continue; + } + for (std::size_t i = 0; i < left_instance->arguments.size(); ++i) + { + if (!bind_arguments(parameters, bindings, + left_instance->arguments.at(i), right_instance->arguments.at(i))) + { + return false; + } + } + return true; + } + return false; + } + if (auto left_procedure = left.get<procedure_type>()) + { + auto right_procedure = right.get<procedure_type>(); + + if (right_procedure == nullptr + || left_procedure->parameters.size() != right_procedure->parameters.size()) + { + return false; + } + for (std::size_t i = 0; i < left_procedure->parameters.size(); ++i) + { + if (!bind_arguments(parameters, bindings, + left_procedure->parameters.at(i), right_procedure->parameters.at(i))) + { + return false; + } + } + return left_procedure->return_type.proper_type.empty() + || bind_arguments(parameters, bindings, + left_procedure->return_type.proper_type, + right_procedure->return_type.proper_type); + } + return true; + } + + void type_analysis_visitor::check_arguments(const named_expression& reference, + const std::vector<type>& arguments) + { + for (const type& argument : arguments) + { + const type resolved = resolve_aliases(argument); + + if (resolved.get<constant_type>() != nullptr) + { + add_error<generic_error>(reference.position(), reference.name, + generic_error::constant_argument{ argument }); + } + else if (!argument.empty() && !is_any_pointer_type(resolve_underlying_type(argument))) + { + add_error<generic_error>(reference.position(), reference.name, + generic_error::argument_not_pointer{ argument }); + } + } + } + + void type_analysis_visitor::visit(named_expression *expression) + { + walking_visitor::visit(expression); + + // A generic procedure keeps its parameters on the symbol rather than in + // its type, which erasure has already substituted away. + std::shared_ptr<info> const symbol = this->bag.lookup(expression->name); + std::shared_ptr<procedure_info> const procedure = + symbol == nullptr ? nullptr : symbol->is_procedure(); + + if (procedure != nullptr && !procedure->parameters.empty()) + { + // An omitted list is inferred at the call, and only there: in value + // position there is nothing to infer from. + const bool omitted = expression->arguments.empty() && this->in_callable_position; + + if (!omitted && expression->arguments.size() != procedure->parameters.size()) + { + add_error<argument_count_error>(expression->position(), + argument_count_error::kind::generic, expression->name, + procedure->parameters.size(), expression->arguments.size()); + } + else if (!expression->arguments.empty()) + { + check_arguments(*expression, expression->argument_types); + } + return; + } + const type denoted = expression->type_decoration; + + if (auto instance = denoted.get<instantiated_type>()) + { + std::shared_ptr<generic_type> const generic = unwrap_generic(instance->generic); + + if (generic == nullptr) + { + add_error<generic_error>(expression->position(), expression->name, + generic_error::not_generic{}); + } + else if (instance->arguments.size() != generic->parameters.size()) + { + add_error<argument_count_error>(expression->position(), + argument_count_error::kind::generic, expression->name, + generic->parameters.size(), instance->arguments.size()); + } + else + { + check_arguments(*expression, expression->argument_types); + } + } + else if (std::shared_ptr<generic_type> const generic = unwrap_generic(denoted)) + { + // A bare generic is not a type at all, which is simply zero + // arguments where some were expected. + add_error<argument_count_error>(expression->position(), + argument_count_error::kind::generic, expression->name, + generic->parameters.size(), 0); + } + else if (procedure != nullptr && !expression->arguments.empty()) + { + add_error<generic_error>(expression->position(), expression->name, + generic_error::not_generic{}); + } + } + + type type_analysis_visitor::infer_call(procedure_call& call, const named_expression& reference, + const procedure_info& procedure) + { + std::vector<type> bindings(procedure.parameters.size()); + auto argument_iterator = std::cbegin(call.arguments); + auto declared_iterator = std::cbegin(procedure.symbol.parameters); + + while (argument_iterator != std::cend(call.arguments) + && declared_iterator != std::cend(procedure.symbol.parameters)) + { + if (!bind_arguments(procedure.parameters, bindings, + *declared_iterator, (*argument_iterator)->type_decoration)) + { + add_error<generic_error>((*argument_iterator)->position(), reference.name, + generic_error::shape_mismatch{ + .declared = *declared_iterator, + .actual = (*argument_iterator)->type_decoration + }); + } + ++argument_iterator; + ++declared_iterator; + } + for (std::size_t i = 0; i < bindings.size(); ++i) + { + if (bindings.at(i).empty()) + { + add_error<generic_error>(call.position(), reference.name, + generic_error::uninferrable_parameter{ + procedure.parameters.at(i).to_string() + }); + return type(); + } + } + check_arguments(reference, bindings); + + return substitute(type(std::make_shared<procedure_type>(procedure.symbol)), + procedure.parameters, bindings); + } + void type_analysis_visitor::visit(procedure_call *call) { + const named_expression *reference = call->callable().is_named(); + + this->in_callable_position = reference != nullptr; call->callable().accept(this); + this->in_callable_position = false; + + type callable_type = call->callable().type_decoration; + std::shared_ptr<procedure_info> inferred; + + if (reference != nullptr && reference->arguments.empty()) + { + std::shared_ptr<info> const symbol = this->bag.lookup(reference->name); + std::shared_ptr<procedure_info> const procedure = + symbol == nullptr ? nullptr : symbol->is_procedure(); - if (auto procedure = call->callable().type_decoration.get<procedure_type>()) + if (procedure != nullptr && !procedure->parameters.empty()) + { + // Inference reads the argument types, so they are decorated + // before the parameter types they will be checked against exist. + for (expression *argument : call->arguments) + { + argument->accept(this); + } + inferred = procedure; + callable_type = infer_call(*call, *reference, *procedure); + } + } + if (auto procedure = callable_type.get<procedure_type>()) { std::vector<expression *>::const_iterator argument_iterator = std::cbegin(call->arguments); std::vector<type>::const_iterator type_iterator = std::cbegin(procedure->parameters); @@ -971,7 +1373,10 @@ namespace elna::boot while (argument_iterator != std::cend(call->arguments) && type_iterator != std::cend(procedure->parameters)) { - (*argument_iterator)->accept(this); + if (inferred == nullptr) + { + (*argument_iterator)->accept(this); + } if (!is_assignable_from(*type_iterator, (*argument_iterator)->type_decoration)) { add_error<type_mismatch_error>( @@ -998,18 +1403,18 @@ namespace elna::boot } } } - else if (!call->callable().type_decoration.empty()) + else if (inferred == nullptr && !call->callable().type_decoration.empty()) { add_error<type_mismatch_error>(call->position(), call->callable().type_decoration, type_mismatch_error::expected_type{ type(std::make_shared<procedure_type>()) }); } - // else callable is not declared which is already reported. + // else callable is not declared, or inference failed and reported. } void type_analysis_visitor::visit(record_constructor_expression *expression) { - auto record = resolve_underlying_type(expression->type_decoration).get<record_type>(); + auto record = erase_generic(expression->type_decoration).get<record_type>(); if (record == nullptr) { @@ -1139,7 +1544,14 @@ namespace elna::boot { walking_visitor::visit(expression); - if (resolve_underlying_type(expression->base().type_decoration).get<pointer_type>() == nullptr) + const type resolved_base = resolve_underlying_type(expression->base().type_decoration); + + if (resolved_base.get<parameter_type>() != nullptr) + { + add_error<type_requirement_error>(expression->position(), expression->base().type_decoration, + type_requirement_error::kind::dereference_of_parameter); + } + else if (resolved_base.get<pointer_type>() == nullptr) { add_error<type_requirement_error>(expression->position(), expression->base().type_decoration, type_requirement_error::kind::dereference_of_non_pointer); @@ -1265,10 +1677,12 @@ namespace elna::boot }; add_error<type_mismatch_error>(expression->position(), expression->lhs().type_decoration, binary_error); } - else if (auto opaque = find_opaque_arithmetic(operation, lhs_resolved, rhs_resolved)) + else if (auto violation = find_arithmetic_violation(operation, lhs_resolved, rhs_resolved)) { - add_error<type_requirement_error>(expression->position(), - opaque.value(), type_requirement_error::kind::opaque_arithmetic); + add_error<type_requirement_error>(expression->position(), violation.value(), + violation->get<parameter_type>() != nullptr + ? type_requirement_error::kind::parameter_arithmetic + : type_requirement_error::kind::opaque_arithmetic); } } |