/* Type analysis. Copyright (C) 2025 Free Software Foundation, Inc. GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see . */ #include "elna/boot/type_check.h" #include #include namespace elna::boot { trait_error::trait_error(const source_position position, const std::string& trait_name, payload_type payload) : error(position), trait_name(trait_name), m_payload(payload) { } std::string trait_error::what() const { return std::visit([this](auto&& payload) -> std::string { using T = std::decay_t; if constexpr (std::is_same_v) { return "Trait #" + this->trait_name + " expects " + std::to_string(payload.expected) + " argument" + (payload.expected != 1 ? "s" : "") + ", got " + std::to_string(payload.actual); } else { return "The second argument to the #" + this->trait_name + " trait must be a field name"; } }, this->m_payload); } type_mismatch_error::type_mismatch_error(const source_position position, type expected, type actual) : error(position), expected(std::move(expected)), actual(std::move(actual)) { } std::string type_mismatch_error::what() const { return "Expected type '" + expected.to_string() + "', but got '" + actual.to_string() + "'"; } constant_assignment_error::constant_assignment_error(const source_position position, type assignee) : error(position), assignee(std::move(assignee)) { } std::string constant_assignment_error::what() const { return "Cannot assign to a value of type '" + assignee.to_string() + "', because it is constant or contains constant members"; } cyclic_declaration_error::cyclic_declaration_error(const std::vector& cycle, const source_position position) : error(position), cycle(cycle) { } std::string cyclic_declaration_error::what() const { auto segment = std::cbegin(this->cycle); std::string message = "Type declaration forms a cycle: " + *segment; ++segment; for (; segment != std::cend(this->cycle); ++segment) { message += " -> " + *segment; } return message; } return_error::return_error(const std::string& identifier, const source_position position, type return_type) : error(position), identifier(identifier), return_type(std::move(return_type)) { } std::string return_error::what() const { if (!return_type.empty()) { return "Procedure '" + this->identifier + "' does not return a value, but return expression has type '" + return_type.to_string() + "'"; } return "Procedure '" + this->identifier + "' is expected to return, but does not have a return statement"; } type_kind_error::type_kind_error(const source_position position, kind type_kind, const type& actual) : error(position), type_kind(type_kind), actual(actual) { } std::string type_kind_error::what() const { switch (this->type_kind) { case kind::record_base: return "'" + this->actual.to_string() + "' is not a record type"; case kind::for_loop: return "for-loop variable must be an array or a slice, got '" + this->actual.to_string() + "'"; case kind::condition: return "Condition must be a boolean, got '" + this->actual.to_string() + "'"; default: __builtin_unreachable(); } } argument_count_error::argument_count_error(std::size_t expected, std::size_t actual, const source_position position) : error(position), expected(expected), actual(actual) { } std::string argument_count_error::what() const { if (actual > expected) { return "Too many arguments, expected " + std::to_string(expected) + ", got " + std::to_string(actual); } else { return "Too few arguments, expected " + std::to_string(expected) + ", got " + std::to_string(actual); } } unary_operation_error::unary_operation_error(const source_position position, type actual, unary_operator operation) : error(position), actual(std::move(actual)), op(operation) { } char unary_operation_error::unary_operator_symbol(unary_operator operation) { switch (operation) { using enum unary_operator; case reference: return '@'; case negation: case bitwise_negation: case logical_negation: return '~'; case minus: return '-'; case plus: return '+'; } __builtin_unreachable(); } std::string unary_operation_error::what() const { return "Type '" + actual.to_string() + "' cannot be used with unary '" + unary_operator_symbol(op) + "'"; } /* * Whether the type itself is constant or has a constant member at any * nesting level, so that values of this type cannot be reassigned as a * whole. Pointers to constants do not make the type itself constant. */ static bool contains_constant_member(const type& checked) { auto referent = resolve_aliases(checked); if (referent.get() != nullptr) { return true; } else if (auto record = referent.get()) { for (const type_field& field : record->fields) { if (contains_constant_member(field.second)) { return true; } } return !record->base.empty() && contains_constant_member(resolve_underlying_type(record->base)); } else if (auto array = referent.get()) { return contains_constant_member(array->base); } return false; } bool type_analysis_visitor::is_equality_compatible(const type& left, const type& right) { auto resolved_left = resolve_underlying_type(left); auto resolved_right = resolve_underlying_type(right); return resolved_left == resolved_right || (is_primitive_type(resolved_left, "Pointer") && is_any_pointer_type(resolved_right)) || (is_any_pointer_type(resolved_left) && is_primitive_type(resolved_right, "Pointer")) || (resolved_left.get() && resolved_right.get()) || (resolved_left.get() && resolved_right.get()); } bool type_analysis_visitor::check_unresolved_symbol(const std::shared_ptr& alias, std::vector& alias_path) { if (std::ranges::find(alias_path, alias->name) != std::cend(alias_path)) { return false; } alias_path.push_back(alias->name); if (auto another_alias = alias->referent.get()) { return check_unresolved_symbol(another_alias, alias_path); } return true; } void type_analysis_visitor::visit_and_validate_condition(expression& condition) { condition.accept(this); if (!is_primitive_type(condition.type_decoration, "Bool")) { add_error(condition.position(), type_kind_error::kind::condition, condition.type_decoration); } } /* * Checks whether derived has base in its record parent chain. * * Base record type must not be null. Derived record type may be null. */ static bool is_base_of(const std::shared_ptr& base, const std::shared_ptr& derived) { if (derived != nullptr) { if (auto current_record = resolve_underlying_type(derived->base).get()) { 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")) { return verdict::pass; } if (auto ptr = ctx.aliased_assignment.get(); ptr != nullptr && resolve_aliases(ptr->base).get() != nullptr) { return verdict::reject; } if (auto const_assign = ctx.aliased_assignment.get(); const_assign != nullptr && is_primitive_type(const_assign->unqualified, "Pointer")) { return verdict::reject; } return verdict::pass; } assign_check::verdict assign_check::check_exact_match() const { return ctx.resolved_assignee == ctx.resolved_assignment ? verdict::accept : verdict::pass; } assign_check::verdict assign_check::check_pointer_hatch() const { if (is_primitive_type(ctx.resolved_assignee, "Pointer") && is_any_pointer_type(ctx.resolved_assignment)) { return verdict::accept; } if (is_primitive_type(ctx.resolved_assignment, "Pointer") && is_any_pointer_type(ctx.resolved_assignee)) { return verdict::accept; } return verdict::pass; } assign_check::verdict assign_check::check_pointer_conversion() const { auto assignee_ptr = ctx.resolved_assignee.get(); auto assignment_ptr = ctx.resolved_assignment.get(); if (assignee_ptr == nullptr || assignment_ptr == nullptr) { return verdict::reject; } auto assignee_pointee_const = resolve_aliases(assignee_ptr->base).get(); auto assignment_pointee_const = resolve_aliases(assignment_ptr->base).get(); // Constness can be added at the first indirection level, but not removed. if (assignee_pointee_const != nullptr && assignee_pointee_const->unqualified == assignment_ptr->base) { return verdict::accept; } if (assignment_pointee_const != nullptr && assignee_pointee_const == nullptr) { 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()) { return is_base_of(assignee_record, resolve_underlying_type(assignment_ptr->base).get()) ? verdict::accept : verdict::pass; } return verdict::pass; } assign_check::verdict assign_check::check_slice_conversion() const { auto assignee_slice = ctx.resolved_assignee.get(); auto assignment_slice = ctx.resolved_assignment.get(); if (assignee_slice == nullptr || assignment_slice == nullptr) { return verdict::pass; } auto assignee_element_const = resolve_aliases(assignee_slice->base).get(); auto assignment_element_const = resolve_aliases(assignment_slice->base).get(); // Const can be added to the element type, but not removed. if (assignee_element_const != nullptr && assignee_element_const->unqualified == assignment_slice->base) { return verdict::accept; } if (assignment_element_const != nullptr && assignee_element_const == nullptr) { return verdict::reject; } return verdict::pass; } bool assign_check::run() { for (auto handler : {&assign_check::guard_const_laundering, &assign_check::check_exact_match, &assign_check::check_slice_conversion, &assign_check::check_pointer_hatch, &assign_check::check_pointer_conversion}) { switch ((this->*handler)()) { case verdict::accept: return true; case verdict::reject: return false; case verdict::pass:; } } return false; } bool type_analysis_visitor::is_assignable_from(const type& assignee, const type& assignment) { return assign_check{ resolve_aliases(assignee), resolve_aliases(assignment), resolve_underlying_type(assignee), resolve_underlying_type(assignment) }.run(); } type_analysis_visitor::type_analysis_visitor(symbol_bag bag, const target_info& target) : bag(std::move(bag)), target(target) { } void type_analysis_visitor::visit(procedure_declaration *declaration) { this->current_procedure = this->bag.lookup(declaration->identifier.name())->is_procedure(); if (declaration->body.has_value()) { this->bag.enter(this->current_procedure->scope); } walking_visitor::visit(declaration); if (declaration->body.has_value()) { if (declaration->body.value().return_expression != nullptr) { const expression *return_expr = declaration->body.value().return_expression; type const return_type = this->current_procedure->symbol.return_type.proper_type; if (!return_type.empty()) { if (!is_assignable_from(return_type, return_expr->type_decoration)) { add_error( return_expr->position(), return_type, return_expr->type_decoration); } } else { add_error(declaration->identifier.name(), return_expr->position(), return_expr->type_decoration); } } else if (declaration->heading().return_type.proper_type != nullptr) { add_error(declaration->identifier.name(), declaration->position()); } this->bag.leave(); } this->current_procedure.reset(); } void type_analysis_visitor::visit(unit *unit) { walking_visitor::visit(unit); } void type_analysis_visitor::visit(assign_statement *statement) { walking_visitor::visit(statement); if (contains_constant_member(statement->lvalue().type_decoration)) { add_error(statement->position(), statement->lvalue().type_decoration); } else if (!is_assignable_from(statement->lvalue().type_decoration, statement->rvalue().type_decoration)) { add_error(statement->position(), statement->lvalue().type_decoration, statement->rvalue().type_decoration); } } void type_analysis_visitor::visit(variable_declaration *declaration) { walking_visitor::visit(declaration); if (declaration->initializer == nullptr || has_errors()) { return; } for (const identifier_definition& variable_identifier : declaration->identifiers) { auto variable_symbol = this->bag.lookup(variable_identifier.name())->is_variable(); if (!is_assignable_from(variable_symbol->symbol, declaration->initializer->type_decoration)) { add_error(declaration->initializer->position(), variable_symbol->symbol, declaration->initializer->type_decoration); } } } void type_analysis_visitor::visit(case_statement *statement) { walking_visitor::visit(statement); type const condition_type = resolve_underlying_type(statement->condition().type_decoration); for (const switch_case& case_block : statement->cases) { for (const expression *case_label : case_block.labels) { if (!is_equality_compatible(condition_type, case_label->type_decoration)) { add_error( case_label->position(), condition_type, case_label->type_decoration, binary_operator::equals); } } } } void type_analysis_visitor::visit(for_statement *statement) { statement->range().accept(this); auto resolved_range = resolve_underlying_type(statement->range().type_decoration); if (!get_range_base_type(resolved_range)) { add_error(statement->range().position(), type_kind_error::kind::for_loop, statement->range().type_decoration); } this->bag.enter(statement->symbols); for (auto *body_statement : statement->body) { body_statement->accept(this); } this->bag.leave(); } void type_analysis_visitor::visit(repeat_statement *statement) { visit_and_validate_condition(statement->condition()); for (auto *body_statement : statement->body) { body_statement->accept(this); } } void type_analysis_visitor::visit(while_statement *statement) { visit_and_validate_condition(statement->branch().prerequisite()); for (auto *branch_statement : statement->branch().statements) { branch_statement->accept(this); } for (conditional_statements *branch : statement->branches) { visit_and_validate_condition(branch->prerequisite()); for (auto *branch_statement : branch->statements) { branch_statement->accept(this); } } } void type_analysis_visitor::visit(if_statement *statement) { visit_and_validate_condition(statement->branch().prerequisite()); for (auto *branch_statement : statement->branch().statements) { branch_statement->accept(this); } for (conditional_statements *branch : statement->branches) { visit_and_validate_condition(branch->prerequisite()); for (auto *branch_statement : branch->statements) { branch_statement->accept(this); } } if (statement->alternative != nullptr) { for (auto *branch_statement : *statement->alternative) { branch_statement->accept(this); } } } void type_analysis_visitor::visit(type_declaration *declaration) { std::vector alias_path; auto unresolved_type = this->bag.lookup(declaration->identifier.name())->is_type()->symbol.get(); if (!check_unresolved_symbol(unresolved_type, alias_path)) { add_error(alias_path, declaration->position()); } else { walking_visitor::visit(declaration); } } void type_analysis_visitor::visit(record_type_expression *expression) { if (expression->base.has_value()) { auto const base_symbol = this->bag.lookup(expression->base.value().name()); if (base_symbol == nullptr || base_symbol->is_type() == nullptr) { add_error(expression->position(), type_kind_error::kind::record_base, type()); } else { type const base_type = resolve_underlying_type(base_symbol->is_type()->symbol); if (base_type.get() == nullptr) { add_error(expression->position(), type_kind_error::kind::record_base, base_type); } } } walking_visitor::visit(expression); } void type_analysis_visitor::visit(procedure_call *call) { call->callable().accept(this); if (auto procedure = call->callable().type_decoration.get()) { std::vector::const_iterator argument_iterator = std::cbegin(call->arguments); std::vector::const_iterator type_iterator = std::cbegin(procedure->parameters); while (argument_iterator != std::cend(call->arguments) && type_iterator != std::cend(procedure->parameters)) { (*argument_iterator)->accept(this); if (!is_assignable_from(*type_iterator, (*argument_iterator)->type_decoration)) { add_error( (*argument_iterator)->position(), *type_iterator, (*argument_iterator)->type_decoration); } ++argument_iterator; ++type_iterator; } if (call->arguments.size() != procedure->parameters.size()) { add_error(procedure->parameters.size(), call->arguments.size(), call->position()); } } else if (!call->callable().type_decoration.empty()) { add_error(call->position(), type(std::make_shared()), call->callable().type_decoration); } // else callable is not declared which is already reported. } void type_analysis_visitor::visit(record_constructor_expression *expression) { auto record = resolve_underlying_type(expression->type_decoration).get(); if (record == nullptr) { add_error( expression->position(), type(std::make_shared()), expression->type_decoration); return; } for (const field_initializer& initializer : expression->field_initializers) { for (const type_field& field : record->fields) { if (field.first == initializer.name()) { if (!is_assignable_from(field.second, initializer.value().type_decoration)) { add_error( initializer.value().position(), field.second, initializer.value().type_decoration); } break; } } } } void type_analysis_visitor::visit(array_constructor_expression *expression) { auto array = resolve_underlying_type(expression->type_decoration).get(); if (array == nullptr) { add_error( expression->position(), type(std::make_shared(type(), 0)), expression->type_decoration); return; } if (expression->elements.size() > array->size) { add_error(array->size, expression->elements.size(), expression->position()); return; } for (auto *element : expression->elements) { if (!is_assignable_from(array->base, element->type_decoration)) { add_error( element->position(), array->base, element->type_decoration); } } } void type_analysis_visitor::visit(slicing_expression *expression) { walking_visitor::visit(expression); } void type_analysis_visitor::visit(unary_expression *expression) { walking_visitor::visit(expression); auto operation = expression->operation(); type const resolved = resolve_underlying_type(expression->operand().type_decoration); if (operation == unary_operator::plus) { if (!is_numeric_type(resolved)) { add_error(expression->position(), expression->operand().type_decoration, operation); } } else if (operation == unary_operator::minus) { if (!is_primitive_type(resolved, "Int") && !is_primitive_type(resolved, "Float")) { add_error(expression->position(), expression->operand().type_decoration, operation); } } else if (operation == unary_operator::negation) { if (is_primitive_type(resolved, "Bool")) { expression->operation(unary_operator::logical_negation); } else if (is_integral_type(resolved)) { expression->operation(unary_operator::bitwise_negation); } else { add_error(expression->position(), expression->operand().type_decoration, operation); } } else if (operation == unary_operator::reference) { auto *designator = expression->operand().is_designator(); if (designator == nullptr || designator->is_slicing() != nullptr) { add_error(expression->position(), expression->operand().type_decoration, operation); } } } binary_operation_error::binary_operation_error(const source_position position, type left, type right, binary_operator operation) : error(position), left(std::move(left)), right(std::move(right)), op(operation) { } std::string binary_operation_error::what() const { return "Invalid operands of type '" + left.to_string() + "' and '" + right.to_string() + "' for operator " + print_binary_operator(op); } void type_analysis_visitor::visit(binary_expression *expression) { walking_visitor::visit(expression); auto operation = expression->operation(); type const lhs_resolved = resolve_underlying_type(expression->lhs().type_decoration); type const rhs_resolved = resolve_underlying_type(expression->rhs().type_decoration); bool valid = false; switch (operation) { using enum binary_operator; case sum: valid = (is_any_pointer_type(lhs_resolved) && is_integral_type(rhs_resolved)) || (is_integral_type(lhs_resolved) && is_any_pointer_type(rhs_resolved)) || (is_numeric_type(lhs_resolved) && lhs_resolved == rhs_resolved); break; case subtraction: valid = (is_any_pointer_type(lhs_resolved) && is_integral_type(rhs_resolved)) || (is_any_pointer_type(lhs_resolved) && is_any_pointer_type(rhs_resolved)) || (is_numeric_type(lhs_resolved) && lhs_resolved == rhs_resolved); break; case division: case remainder: case multiplication: valid = is_numeric_type(lhs_resolved) && lhs_resolved == rhs_resolved; break; case less: case greater: case less_equal: case greater_equal: valid = (is_numeric_type(lhs_resolved) && lhs_resolved == rhs_resolved) || (is_any_pointer_type(lhs_resolved) && is_any_pointer_type(rhs_resolved)); break; case conjunction: case disjunction: case exclusive_disjunction: if (is_primitive_type(lhs_resolved, "Bool") && lhs_resolved == rhs_resolved) { switch (operation) { case conjunction: expression->operation(logical_conjunction); break; case disjunction: expression->operation(logical_disjunction); break; case exclusive_disjunction: expression->operation(logical_exclusive_disjunction); break; default: break; } valid = true; } else if (is_integral_type(lhs_resolved) && lhs_resolved == rhs_resolved) { switch (operation) { case conjunction: expression->operation(bitwise_conjunction); break; case disjunction: expression->operation(bitwise_disjunction); break; case exclusive_disjunction: expression->operation(bitwise_exclusive_disjunction); break; default: break; } valid = true; } break; case equals: case not_equals: valid = is_equality_compatible(lhs_resolved, rhs_resolved); break; case shift_left: case shift_right: valid = is_integral_type(lhs_resolved) && is_primitive_type(rhs_resolved, "Word"); break; default: __builtin_unreachable(); } if (!valid) { add_error(expression->position(), expression->lhs().type_decoration, expression->rhs().type_decoration, operation); } } void type_analysis_visitor::visit(traits_expression *trait) { walking_visitor::visit(trait); if (trait->name == "size" || trait->name == "alignment" || trait->name == "min" || trait->name == "max") { if (trait->arguments.size() != 1) { add_error(trait->position(), trait->name.name(), trait_error::argument_count{ .expected = 1, .actual = trait->arguments.size() }); } } else if (trait->name == "offset") { if (trait->arguments.size() != 2) { add_error(trait->position(), trait->name.name(), trait_error::argument_count{ .expected = 2, .actual = trait->arguments.size() }); } else if (trait->arguments.at(1)->is_named() == nullptr) { add_error(trait->arguments.at(1)->position(), trait->name.name(), trait_error::offset_not_field_name{}); } } } }