diff options
Diffstat (limited to 'boot/name_analysis.cc')
| -rw-r--r-- | boot/name_analysis.cc | 765 |
1 files changed, 765 insertions, 0 deletions
diff --git a/boot/name_analysis.cc b/boot/name_analysis.cc new file mode 100644 index 0000000..cfc4e35 --- /dev/null +++ b/boot/name_analysis.cc @@ -0,0 +1,765 @@ +/* Name 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 +<http://www.gnu.org/licenses/>. */ + +#include "elna/boot/name_analysis.h" + +#include <algorithm> + +namespace elna::boot +{ + declaration_error::declaration_error(const kind error_kind, + const boot::identifier& identifier) + : error(identifier.position()), identifier(identifier.name()), error_kind(error_kind) + { + } + + std::string declaration_error::what() const + { + switch (this->error_kind) + { + case kind::undeclared: + return "Type '" + identifier + "' not declared"; + case kind::local_export: + return "Local symbol '" + this->identifier + "' cannot be exported"; + default: + __builtin_unreachable(); + } + } + + redefinition_error::redefinition_error(const boot::identifier& identifier, + std::optional<source_position> original) + : error(identifier.position()), identifier(identifier.name()), original(original) + { + } + + std::string redefinition_error::what() const + { + return "Symbol '" + identifier + "' has been already defined"; + } + + std::optional<std::pair<std::string, source_position>> + redefinition_error::note() const + { + if (original.has_value() && original->start().available()) + { + return std::make_pair("previously declared here", *original); + } + return std::nullopt; + } + + // Members of a constant aggregate are constant themselves. + static type qualify_member_type(const type& element, const type& aggregate) + { + if (resolve_aliases(aggregate).get<constant_type>() != nullptr + && resolve_aliases(element).get<constant_type>() == nullptr) + { + return type(std::make_shared<constant_type>(element)); + } + else + { + return element; + } + } + + name_analysis_visitor::name_analysis_visitor(symbol_bag bag) + : error_container(), bag(bag) + { + } + + std::pair<procedure_type, std::vector<std::string>> name_analysis_visitor::build_procedure( + procedure_type_expression& expression) + { + procedure_type::return_t result_return; + + if (expression.return_type.no_return) + { + result_return = procedure_type::return_t(std::monostate{}); + } + else if (expression.return_type.proper_type != nullptr) + { + expression.return_type.proper_type->accept(this); + result_return = procedure_type::return_t(this->current_type); + } + else + { + result_return = procedure_type::return_t(); + } + std::pair<procedure_type, std::vector<std::string>> result_type{ + procedure_type(result_return), std::vector<std::string>() + }; + for (auto& [parameter_names, parameters_type] : expression.parameters) + { + parameters_type->accept(this); + for (auto& parameter_name : parameter_names) + { + result_type.first.parameters.push_back(this->current_type); + result_type.second.push_back(parameter_name.name()); + } + } + return result_type; + } + + type name_analysis_visitor::lookup_primitive_type(const std::string& name) + { + return this->bag.lookup(name)->is_type()->symbol; + } + + type name_analysis_visitor::lookup_field(const type& composite_type, const std::string& field_name) + { + type resolved_type = resolve_underlying_type(composite_type); + + if (auto record = resolved_type.get<record_type>()) + { + for (auto& field : record->fields) + { + if (field.first == field_name) + { + return field.second; + } + } + if (!record->base.empty()) + { + return lookup_field(record->base, field_name); + } + } + else if (auto primitive = resolved_type.get<primitive_type>(); primitive != nullptr && primitive->identifier == "String") + { + if (field_name == "length") + { + return lookup_primitive_type("Word"); + } + else if (field_name == "ptr") + { + return type(std::make_shared<pointer_type>(lookup_primitive_type("Char"))); + } + } + return type(); + } + + void name_analysis_visitor::visit(type_declaration *declaration) + { + walking_visitor::visit(declaration); + auto resolved = this->bag.resolve(declaration->identifier.name(), this->current_type); + auto info = std::make_shared<type_info>(type(resolved)); + + info->exported = declaration->identifier.exported(); + info->position.emplace(declaration->position()); + this->bag.enter(declaration->identifier.name(), info); + } + + void name_analysis_visitor::visit(pointer_type_expression *expression) + { + walking_visitor::visit(expression); + this->current_type = type(std::make_shared<pointer_type>(this->current_type)); + } + + void name_analysis_visitor::visit(constant_type_expression *expression) + { + walking_visitor::visit(expression); + this->current_type = type(std::make_shared<constant_type>(this->current_type)); + } + + void name_analysis_visitor::visit(array_type_expression *expression) + { + walking_visitor::visit(expression); + auto result_type = std::make_shared<array_type>(this->current_type, expression->size); + + this->current_type = type(result_type); + } + + /** + * Collects field names from a record type recursively, base first. + */ + static void collect_field_names(const type& composite_type, + std::map<std::string, field_origin>& names) + { + auto record = resolve_underlying_type(composite_type).get<record_type>(); + if (record == nullptr) + { + return; + } + if (!record->base.empty()) + { + collect_field_names(record->base, names); + } + for (auto& field : record->fields) + { + names.insert({ field.first, field_origin{ std::nullopt, composite_type } }); + } + } + + std::vector<type_field> name_analysis_visitor::build_composite_type( + const std::vector<field_declaration>& fields, + std::map<std::string, field_origin>& field_names, + type aggregate) + { + std::vector<type_field> result; + + for (auto& field : fields) + { + field.second->accept(this); + for (auto& field_name : field.first) + { + auto existing = field_names.find(field_name.name()); + if (existing != field_names.end()) + { + std::optional<std::string> base_name; + + if (!existing->second.declaration.has_value() + && !existing->second.base_type.empty()) + { + if (auto alias = existing->second.base_type.get<alias_type>()) + { + base_name = alias->name; + } + } + add_error<duplicate_member_error>(field_name, aggregate, + existing->second.declaration, base_name); + } + else + { + field_names.insert({ field_name.name(), + field_origin{ field.second->position(), type() } }); + result.push_back(std::make_pair(field_name.name(), this->current_type)); + } + } + } + return result; + } + + void name_analysis_visitor::visit(record_type_expression *expression) + { + std::shared_ptr<record_type> result_type; + if (expression->base.has_value()) + { + if (auto unresolved_alias = this->bag.declared(expression->base.value().name())) + { + result_type = std::make_shared<record_type>(type(unresolved_alias)); + } + else if (auto base_symbol = this->bag.lookup(expression->base.value().name())) + { + if (auto base_type_info = base_symbol->is_type()) + { + result_type = std::make_shared<record_type>(base_type_info->symbol); + } + else + { + type actual; + + if (auto var = base_symbol->is_variable()) + { + actual = var->symbol; + } + else if (auto proc = base_symbol->is_procedure()) + { + actual = type(std::make_shared<procedure_type>(proc->symbol)); + } + add_error<base_type_error>(actual, expression->position()); + this->current_type = type(); + return; + } + } + else + { + add_error<declaration_error>(declaration_error::kind::undeclared, + expression->base.value()); + this->current_type = type(); + return; + } + } + else + { + result_type = std::make_shared<record_type>(); + } + + std::map<std::string, field_origin> field_names; + collect_field_names(result_type->base, field_names); + result_type->fields = build_composite_type(expression->fields, field_names, type(result_type)); + + this->current_type = type(result_type); + } + + void name_analysis_visitor::visit(record_constructor_expression *expression) + { + if (auto type_symbol = this->bag.lookup(expression->type_name.name())) + { + if (auto type_info = type_symbol->is_type()) + { + expression->type_decoration = type_info->symbol; + } + } + else + { + add_error<declaration_error>(declaration_error::kind::undeclared, + expression->type_name); + } + for (const field_initializer& initializer : expression->field_initializers) + { + initializer.value().accept(this); + if (!expression->type_decoration.empty() + && lookup_field(expression->type_decoration, initializer.name()).empty()) + { + add_error<declaration_error>(declaration_error::kind::undeclared, + initializer.id()); + } + } + } + + void name_analysis_visitor::visit(array_constructor_expression *expression) + { + expression->m_element_type->accept(this); + auto element_type = this->current_type; + for (auto element : expression->elements) + { + element->accept(this); + } + expression->type_decoration = type(std::make_shared<array_type>(element_type, expression->size)); + } + + void name_analysis_visitor::visit(procedure_type_expression *expression) + { + std::shared_ptr<procedure_type> result_type = + std::make_shared<procedure_type>(std::move(build_procedure(*expression).first)); + + this->current_type = type(result_type); + } + + void name_analysis_visitor::visit(enumeration_type_expression *expression) + { + std::vector<std::string> member_names; + for (auto& member : expression->members) + { + member_names.emplace_back(member.name()); + } + std::shared_ptr<enumeration_type> result_type = std::make_shared<enumeration_type>( + member_names); + std::map<std::string, source_position> seen; + type aggregate(result_type); + + for (auto& member : expression->members) + { + auto existing = seen.find(member.name()); + if (existing != seen.end()) + { + add_error<duplicate_member_error>(member, aggregate, existing->second); + } + else + { + seen.insert({ member.name(), member.position() }); + } + } + this->current_type = type(result_type); + } + + std::shared_ptr<variable_info> name_analysis_visitor::register_variable(const std::string& name, + const bool is_extern, const source_position position) + { + auto variable_symbol = std::make_shared<variable_info>(this->current_type, is_extern); + variable_symbol->position.emplace(position); + + if (!this->bag.enter(name, variable_symbol)) + { + auto original = this->bag.lookup(name); + add_error<redefinition_error>(boot::identifier(name, position), + original->position); + } + return variable_symbol; + } + + void name_analysis_visitor::visit(variable_declaration *declaration) + { + declaration->variable_type().accept(this); + auto variable_type = this->current_type; + if (declaration->initializer != nullptr) + { + declaration->initializer->accept(this); + this->current_type = variable_type; + } + for (const identifier_definition& variable_identifier : declaration->identifiers) + { + auto variable_symbol = register_variable(variable_identifier.name(), declaration->is_extern, + declaration->position()); + variable_symbol->exported = variable_identifier.exported(); + } + } + + + void name_analysis_visitor::visit(procedure_declaration *declaration) + { + std::shared_ptr<procedure_info> info; + auto [heading, parameter_names] = build_procedure(declaration->heading()); + + if (declaration->body.has_value()) + { + info = std::make_shared<procedure_info>(heading, std::move(parameter_names), this->bag.enter()); + auto name_iterator = std::cbegin(info->names); + auto type_iterator = std::cbegin(heading.parameters); + + while (name_iterator != std::cend(info->names) && type_iterator != std::cend(heading.parameters)) + { + this->current_type = *type_iterator; + auto variable_symbol = register_variable(*name_iterator, false, declaration->heading().position()); + variable_symbol->exported = false; + + ++name_iterator; + ++type_iterator; + } + for (variable_declaration *const variable : declaration->body.value().variables) + { + variable->accept(this); + } + for (statement *const statement : declaration->body.value().entry_point) + { + statement->accept(this); + } + if (declaration->body.value().return_expression != nullptr) + { + declaration->body.value().return_expression->accept(this); + } + this->bag.leave(); + } + else + { + info = std::make_shared<procedure_info>(heading, std::move(parameter_names)); + } + info->exported = declaration->identifier.exported(); + info->position.emplace(declaration->position()); + this->bag.enter(declaration->identifier.name(), info); + } + + void name_analysis_visitor::visit(procedure_call *call) + { + call->callable().accept(this); + if (auto procedure = call->callable().type_decoration.get<procedure_type>()) + { + call->type_decoration = procedure->return_type.proper_type; + } + else if (call->callable().is_named() != nullptr) + { + call->type_decoration = this->current_type; + } + for (expression *const argument : call->arguments) + { + argument->accept(this); + } + } + + void name_analysis_visitor::visit(unit *unit) + { + for (type_declaration *const type : unit->types) + { + type->accept(this); + } + for (variable_declaration *const variable : unit->variables) + { + variable->accept(this); + } + for (procedure_declaration *const procedure : unit->procedures) + { + procedure->accept(this); + } + if (unit->has_body()) + { + this->bag.enter(); + auto variable_type = lookup_primitive_type("Int"); + this->bag.enter("count", std::make_shared<variable_info>(variable_type, false)); + + variable_type = lookup_primitive_type("Char"); + variable_type = type(std::make_shared<pointer_type>(variable_type)); + variable_type = type(std::make_shared<pointer_type>(variable_type)); + this->bag.enter("parameters", std::make_shared<variable_info>(variable_type, false)); + + for (statement *const statement : unit->entry_point) + { + statement->accept(this); + } + this->bag.leave(); + } + } + + void name_analysis_visitor::visit(traits_expression *trait) + { + if (!trait->arguments.empty()) + { + trait->arguments.front()->accept(this); + trait->types.push_back(this->current_type); + } + + if (trait->name == "size" || trait->name == "alignment" || trait->name == "offset") + { + trait->type_decoration = lookup_primitive_type("Word"); + } + else if (trait->name == "min" || trait->name == "max") + { + trait->type_decoration = trait->types.empty() ? type() : trait->types.front(); + + if (!trait->type_decoration.empty()) + { + type resolved = resolve_underlying_type(trait->type_decoration); + bool is_enum = resolved.get<enumeration_type>() != nullptr; + bool is_integral = false; + + if (auto prim = resolved.get<primitive_type>()) + { + is_integral = prim->identifier == "Int" || prim->identifier == "Word" + || prim->identifier == "Bool" || prim->identifier == "Char"; + } + if (!is_enum && !is_integral) + { + add_error<unsupported_trait_type_error>(trait->name, + trait->type_decoration); + trait->type_decoration = type(); + } + } + } + else + { + add_error<declaration_error>(declaration_error::kind::undeclared, + trait->name); + } + } + + void name_analysis_visitor::visit(binary_expression *expression) + { + walking_visitor::visit(expression); + + switch (expression->operation()) + { + case binary_operator::equals: + case binary_operator::not_equals: + case binary_operator::less: + case binary_operator::greater: + case binary_operator::less_equal: + case binary_operator::greater_equal: + expression->type_decoration = lookup_primitive_type("Bool"); + break; + case binary_operator::subtraction: + if (expression->lhs().type_decoration.get<pointer_type>() + && expression->rhs().type_decoration.get<pointer_type>()) + { + expression->type_decoration = lookup_primitive_type("Int"); + } + else + { + expression->type_decoration = expression->lhs().type_decoration; + } + break; + default: + expression->type_decoration = expression->lhs().type_decoration; + break; + } + } + + void name_analysis_visitor::visit(unary_expression *expression) + { + walking_visitor::visit(expression); + + if (expression->operation() == unary_operator::reference) + { + expression->type_decoration = this->current_type + = type(std::make_shared<pointer_type>(expression->operand().type_decoration)); + } + else + { + expression->type_decoration = expression->operand().type_decoration; + } + } + + void name_analysis_visitor::visit(array_access_expression *expression) + { + walking_visitor::visit(expression); + auto resolved_base = resolve_underlying_type(expression->base().type_decoration); + + if (auto array = resolved_base.get<array_type>()) + { + expression->type_decoration = array->base; + } + else if (resolved_base == lookup_primitive_type("String")) + { + expression->type_decoration = lookup_primitive_type("Char"); + } + // Elements of a constant array are constant themselves since a static + // array is a holistic type. + if (!expression->type_decoration.empty()) + { + expression->type_decoration = qualify_member_type(expression->type_decoration, + expression->base().type_decoration); + } + } + + void name_analysis_visitor::visit(field_access_expression *expression) + { + walking_visitor::visit(expression); + expression->type_decoration = lookup_field(expression->base().type_decoration, expression->field().name()); + auto is_designator = expression->base().is_designator(); + + if (expression->type_decoration.empty() && is_designator != nullptr && is_designator->is_named() != nullptr) + { + expression->type_decoration = this->current_type; + } + if (expression->type_decoration.empty()) + { + add_error<field_not_found_error>(expression->field(), expression->base().type_decoration); + } + else + { + expression->type_decoration = qualify_member_type(expression->type_decoration, + expression->base().type_decoration); + } + } + + void name_analysis_visitor::visit(dereference_expression *expression) + { + walking_visitor::visit(expression); + + if (auto pointer = resolve_underlying_type(expression->base().type_decoration).get<pointer_type>()) + { + expression->type_decoration = pointer->base; + } + } + + void name_analysis_visitor::visit(cast_expression *expression) + { + walking_visitor::visit(expression); + expression->type_decoration = this->current_type; + } + + void name_analysis_visitor::visit(named_expression *expression) + { + this->current_type = type(); + + if (auto unresolved_alias = this->bag.declared(expression->name)) + { + this->current_type = type(unresolved_alias); + } + else if (auto from_symbol_table = this->bag.lookup(expression->name)) + { + if (auto type_symbol = from_symbol_table->is_type()) + { + this->current_type = type_symbol->symbol; + } + else if (auto variable_symbol = from_symbol_table->is_variable()) + { + expression->type_decoration = variable_symbol->symbol; + } + else if (auto procedure_symbol = from_symbol_table->is_procedure()) + { + expression->type_decoration = type(std::make_shared<procedure_type>(procedure_symbol->symbol)); + } + } + else + { + add_error<declaration_error>(declaration_error::kind::undeclared, + boot::identifier(expression->name, expression->position())); + } + } + + void name_analysis_visitor::visit(literal<std::int32_t> *literal) + { + literal->type_decoration = lookup_primitive_type("Int"); + } + + void name_analysis_visitor::visit(literal<std::uint32_t> *literal) + { + literal->type_decoration = lookup_primitive_type("Word"); + } + + void name_analysis_visitor::visit(literal<double> *literal) + { + literal->type_decoration = lookup_primitive_type("Float"); + } + + void name_analysis_visitor::visit(literal<bool> *literal) + { + literal->type_decoration = lookup_primitive_type("Bool"); + } + + void name_analysis_visitor::visit(literal<unsigned char> *literal) + { + literal->type_decoration = lookup_primitive_type("Char"); + } + + void name_analysis_visitor::visit(literal<std::nullptr_t> *literal) + { + literal->type_decoration = lookup_primitive_type("Pointer"); + } + + void name_analysis_visitor::visit(literal<std::string> *literal) + { + literal->type_decoration = lookup_primitive_type("String"); + } + + declaration_visitor::declaration_visitor() + : error_container() + { + } + + void declaration_visitor::visit(import_declaration *) + { + } + + void declaration_visitor::visit(unit *unit) + { + for (import_declaration *const _import : unit->imports) + { + _import->accept(this); + } + for (type_declaration *const type : unit->types) + { + type->accept(this); + } + for (procedure_declaration *const procedure : unit->procedures) + { + procedure->accept(this); + } + } + + void declaration_visitor::visit(type_declaration *declaration) + { + const std::string& type_identifier = declaration->identifier.name(); + + if (!this->unresolved.insert({ type_identifier, std::make_shared<alias_type>(type_identifier) }).second) + { + add_error<redefinition_error>(declaration->identifier.id(), + declaration->position()); + } + } + + void declaration_visitor::visit(procedure_declaration *declaration) + { + if (!declaration->body.has_value()) + { + return; + } + for (variable_declaration *const variable : declaration->body.value().variables) + { + variable->accept(this); + } + } + + void declaration_visitor::visit(variable_declaration *declaration) + { + for (const identifier_definition& variable_identifier : declaration->identifiers) + { + if (variable_identifier.exported()) + { + add_error<declaration_error>(declaration_error::kind::local_export, + variable_identifier.id()); + } + } + } +} |