Fix ICEs with recursive type declarations

2 files changed, 188 insertions, 95 deletions

diff --git a/boot/name_analysis.cc b/boot/name_analysis.cc
index cf90e3d..620a32f 100644
--- a/boot/name_analysis.cc
+++ b/boot/name_analysis.cc
@@ -70,6 +70,25 @@ namespace elna::boot
         }
     }
 
+    cyclic_declaration_error::cyclic_declaration_error(const source_position position,
+            const std::vector<std::string>& cycle)
+        : diagnostic(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 + " -> " + this->cycle.front();
+    }
+
     const_qualifier_error::const_qualifier_error(const source_position position, payload_type payload)
         : diagnostic(position), payload(std::move(payload))
     {
@@ -436,12 +455,21 @@ namespace elna::boot
                     const_qualifier_error::kind::array_position);
         }
         expression->dimensions().accept(this);
+        if (expression->dimensions().type_decoration.empty())
+        {
+            // The dimension expression failed to resolve and reported its own
+            // error already.
+            this->current_type = type();
+            return;
+        }
         const auto size_constant = this->constant_evaluator.evaluate_index(expression->dimensions());
 
         if (!size_constant.has_value())
         {
             add_error<non_constant_expression_error>(expression->position(),
                     non_constant_expression_error::array_dimensions{ array_base });
+            this->current_type = type();
+            return;
         }
         this->current_type = type(std::make_shared<array_type>(array_base, size_constant.value()));
     }
@@ -977,6 +1005,107 @@ namespace elna::boot
     {
     }
 
+    std::optional<std::vector<std::string>> declaration_visitor::find_alias_cycle(
+            const std::shared_ptr<alias_type>& being_resolved, const type& referent)
+    {
+        std::vector<std::string> alias_path;
+
+        return find_alias_cycle(being_resolved, referent, alias_path, walk_state{})
+            ? std::nullopt : std::make_optional(alias_path);
+    }
+
+    bool declaration_visitor::find_alias_cycle(const std::shared_ptr<alias_type>& being_resolved,
+            const type& referent, std::vector<std::string>& alias_path, walk_state state)
+    {
+        /*
+         * A recursive type is legal only if the cycle passes through a record,
+         * which materializes the recursion, and the occurrence closing the
+         * cycle is behind a pointer or a slice, so that the record layout
+         * stays finite. All other cycles are rejected.
+         */
+        if (auto link = referent.get<alias_type>())
+        {
+            if (std::ranges::find(alias_path, link->name) != std::cend(alias_path))
+            {
+                // A legal cycle already checked on this path.
+                return true;
+            }
+            alias_path.push_back(link->name);
+            if (being_resolved == link)
+            {
+                return state.record_seen && state.guarded;
+            }
+            const bool acyclic = find_alias_cycle(being_resolved, link->referent, alias_path, state);
+            if (acyclic)
+            {
+                alias_path.pop_back();
+            }
+            return acyclic;
+        }
+        else if (auto link = referent.get<constant_type>())
+        {
+            return find_alias_cycle(being_resolved, link->unqualified, alias_path, state);
+        }
+        else if (auto link = referent.get<pointer_type>())
+        {
+            walk_state guarded_state = state;
+            guarded_state.guarded = true;
+            return find_alias_cycle(being_resolved, link->base, alias_path, guarded_state);
+        }
+        else if (auto link = referent.get<slice_type>())
+        {
+            walk_state guarded_state = state;
+            guarded_state.guarded = true;
+            return find_alias_cycle(being_resolved, link->base, alias_path, guarded_state);
+        }
+        else if (auto link = referent.get<array_type>())
+        {
+            return find_alias_cycle(being_resolved, link->base, alias_path, state);
+        }
+        else if (auto link = referent.get<procedure_type>())
+        {
+            const std::size_t saved_path = alias_path.size();
+
+            for (const type& parameter : link->parameters)
+            {
+                alias_path.resize(saved_path);
+                if (!find_alias_cycle(being_resolved, parameter, alias_path, state))
+                {
+                    return false;
+                }
+            }
+            if (!link->return_type.proper_type.empty())
+            {
+                alias_path.resize(saved_path);
+                return find_alias_cycle(being_resolved, link->return_type.proper_type, alias_path, state);
+            }
+            return true;
+        }
+        else if (auto link = referent.get<record_type>())
+        {
+            const std::size_t saved_path = alias_path.size();
+            walk_state in_record = state;
+            in_record.record_seen = true;
+            in_record.guarded = false;
+
+            if (!link->base.empty()
+                    && !find_alias_cycle(being_resolved, link->base, alias_path, in_record))
+            {
+                return false;
+            }
+            for (const auto& [field_name, field_type] : link->fields)
+            {
+                alias_path.resize(saved_path);
+                if (!find_alias_cycle(being_resolved, field_type, alias_path, in_record))
+                {
+                    return false;
+                }
+            }
+            return true;
+        }
+        return true;
+    }
+
     void declaration_visitor::visit(unit *unit)
     {
         for (type_declaration *const type : unit->types)
@@ -996,7 +1125,18 @@ namespace elna::boot
     void declaration_visitor::visit(type_declaration *declaration)
     {
         declaration->underlying_type().accept(this);
-        auto resolved = this->bag.resolve(declaration->identifier.name(), this->current_type);
+        type underlying = this->current_type;
+
+        // Reject the cycle and wire an empty referent: the declaration still
+        // resolves and is entered, so its uses degrade silently.
+        if (auto cycle = find_alias_cycle(
+                this->bag.declared(declaration->identifier.name()), underlying))
+        {
+            add_error<cyclic_declaration_error>(declaration->position(), *cycle);
+            underlying = type();
+        }
+        const std::shared_ptr<alias_type> resolved =
+            this->bag.resolve(declaration->identifier.name(), underlying);
         auto info = std::make_shared<type_info>(type(resolved));
 
         info->exported = declaration->identifier.exported();
diff --git a/boot/type_check.cc b/boot/type_check.cc
index ad27337..8f7a30f 100644
--- a/boot/type_check.cc
+++ b/boot/type_check.cc
@@ -18,7 +18,6 @@ along with GCC; see the file COPYING3.  If not see
 #include "elna/boot/type_check.h"
 #include "elna/boot/evaluator.h"
 
-#include <algorithm>
 #include <utility>
 
 namespace elna::boot
@@ -222,25 +221,6 @@ namespace elna::boot
         }
     }
 
-    cyclic_declaration_error::cyclic_declaration_error(const source_position position,
-            const std::vector<std::string>& cycle)
-        : diagnostic(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;
-    }
-
     argument_count_error::argument_count_error(const source_position position, kind kind,
             std::string applicand, std::size_t expected, std::size_t actual)
         : diagnostic(position), m_kind(kind), applicand(std::move(applicand)), expected(expected), actual(actual)
@@ -301,7 +281,9 @@ namespace elna::boot
 
     /*
      * Finds the first opaque type in a value position, following aliases,
-     * qualifiers, arrays, slices, records and procedures but not pointers.
+     * qualifiers, arrays, records and procedures but not pointers or slices.
+     * Pointers and slices don't store their base type by value, so an opaque
+     * behind them is only reachable as a transient value.
      */
     static std::optional<type> find_opaque_type(const type& checked)
     {
@@ -326,10 +308,6 @@ namespace elna::boot
         {
             return find_opaque_type(array->base);
         }
-        else if (auto slice = referent.get<slice_type>())
-        {
-            return find_opaque_type(slice->base);
-        }
         else if (auto procedure = referent.get<procedure_type>())
         {
             for (const type& parameter : procedure->parameters)
@@ -387,22 +365,6 @@ namespace elna::boot
             || (resolved_left.get<record_type>() && resolved_right.get<record_type>());
     }
 
-    bool type_analysis_visitor::check_unresolved_symbol(const std::shared_ptr<alias_type>& alias,
-            std::vector<std::string>& 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<alias_type>())
-        {
-            return check_unresolved_symbol(another_alias, alias_path);
-        }
-        return true;
-    }
-
     void type_analysis_visitor::visit_and_validate_condition(expression& condition)
     {
         condition.accept(this);
@@ -797,78 +759,69 @@ namespace elna::boot
 
     void type_analysis_visitor::visit(type_declaration *declaration)
     {
-        std::vector<std::string> alias_path;
+        walking_visitor::visit(declaration);
         auto unresolved_type = this->bag.lookup(declaration->identifier.name())->is_type()->symbol.get<alias_type>();
+        const type referent = resolve_aliases(unresolved_type->referent);
 
-        if (!check_unresolved_symbol(unresolved_type, alias_path))
-        {
-            add_error<cyclic_declaration_error>(declaration->position(), alias_path);
-        }
-        else
+        if (auto record = referent.get<record_type>())
         {
-            walking_visitor::visit(declaration);
-            const type referent = resolve_aliases(unresolved_type->referent);
-
-            if (auto record = referent.get<record_type>())
+            for (const auto& [field_name, field_type] : record->fields)
             {
-                for (const auto& [field_name, field_type] : record->fields)
+                if (auto opaque = find_opaque_type(field_type))
                 {
-                    if (auto opaque = find_opaque_type(field_type))
-                    {
-                        add_error<type_requirement_error>(declaration->position(),
-                                opaque.value(), type_requirement_error::kind::opaque_field);
-                    }
-                    else if (has_zero_size(field_type, this->target))
-                    {
-                        add_error<type_requirement_error>(declaration->position(),
-                                field_type, type_requirement_error::kind::zero_sized);
-                    }
+                    add_error<type_requirement_error>(declaration->position(),
+                            opaque.value(), type_requirement_error::kind::opaque_field);
                 }
-            }
-            else if (auto array = referent.get<array_type>())
-            {
-                if (auto opaque = find_opaque_type(array->base))
+                else if (has_zero_size(field_type, this->target))
                 {
                     add_error<type_requirement_error>(declaration->position(),
-                            opaque.value(), type_requirement_error::kind::opaque_element);
+                            field_type, type_requirement_error::kind::zero_sized);
                 }
             }
-            else if (auto slice = referent.get<slice_type>())
+        }
+        else if (auto array = referent.get<array_type>())
+        {
+            if (auto opaque = find_opaque_type(array->base))
+            {
+                add_error<type_requirement_error>(declaration->position(),
+                        opaque.value(), type_requirement_error::kind::opaque_element);
+            }
+        }
+        else if (auto slice = referent.get<slice_type>())
+        {
+            if (auto opaque = find_opaque_type(slice->base))
             {
-                if (auto opaque = find_opaque_type(slice->base))
+                add_error<type_requirement_error>(declaration->position(),
+                        opaque.value(), type_requirement_error::kind::opaque_element);
+            }
+        }
+        else if (auto procedure = referent.get<procedure_type>())
+        {
+            for (const type& parameter : procedure->parameters)
+            {
+                if (auto opaque = find_opaque_type(parameter))
+                {
+                    add_error<type_requirement_error>(declaration->position(),
+                            opaque.value(), type_requirement_error::kind::opaque_parameter);
+                }
+                else if (has_zero_size(parameter, this->target))
                 {
                     add_error<type_requirement_error>(declaration->position(),
-                            opaque.value(), type_requirement_error::kind::opaque_element);
+                            parameter, type_requirement_error::kind::zero_sized);
                 }
             }
-            else if (auto procedure = referent.get<procedure_type>())
+            if (!procedure->return_type.proper_type.empty())
             {
-                for (const type& parameter : procedure->parameters)
+                if (auto opaque = find_opaque_type(procedure->return_type.proper_type))
                 {
-                    if (auto opaque = find_opaque_type(parameter))
-                    {
-                        add_error<type_requirement_error>(declaration->position(),
-                                opaque.value(), type_requirement_error::kind::opaque_parameter);
-                    }
-                    else if (has_zero_size(parameter, this->target))
-                    {
-                        add_error<type_requirement_error>(declaration->position(),
-                                parameter, type_requirement_error::kind::zero_sized);
-                    }
+                    add_error<type_requirement_error>(declaration->position(),
+                            opaque.value(), type_requirement_error::kind::opaque_return);
                 }
-                if (!procedure->return_type.proper_type.empty())
+                else if (has_zero_size(procedure->return_type.proper_type, this->target))
                 {
-                    if (auto opaque = find_opaque_type(procedure->return_type.proper_type))
-                    {
-                        add_error<type_requirement_error>(declaration->position(),
-                                opaque.value(), type_requirement_error::kind::opaque_return);
-                    }
-                    else if (has_zero_size(procedure->return_type.proper_type, this->target))
-                    {
-                        add_error<type_requirement_error>(declaration->position(),
-                                procedure->return_type.proper_type,
-                                type_requirement_error::kind::zero_sized);
-                    }
+                    add_error<type_requirement_error>(declaration->position(),
+                            procedure->return_type.proper_type,
+                            type_requirement_error::kind::zero_sized);
                 }
             }
         }