Fix ICEs with recursive type declarations

19 files changed, 340 insertions, 123 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);
                 }
             }
         }
diff --git a/gcc/gcc/elna-builtins.cc b/gcc/gcc/elna-builtins.cc
index c728a00..3d10c44 100644
--- a/gcc/gcc/elna-builtins.cc
+++ b/gcc/gcc/elna-builtins.cc
@@ -170,7 +170,8 @@ namespace elna::gcc
                 static_cast<int>(procedure.parameters.size()), parameter_types.data());
     }
 
-    tree get_inner_alias(const boot::type& type, const std::shared_ptr<symbol_table>& symbols)
+    tree get_inner_alias(const boot::type& type, const std::shared_ptr<symbol_table>& symbols,
+            tree placeholder)
     {
         if (auto reference = type.get<boot::primitive_type>())
         {
@@ -181,7 +182,7 @@ namespace elna::gcc
         }
         else if (auto reference = type.get<boot::record_type>())
         {
-            tree composite_type_node = make_node(RECORD_TYPE);
+            tree composite_type_node = placeholder != NULL_TREE ? placeholder : make_node(RECORD_TYPE);
 
             if (!reference->base.empty())
             {
@@ -217,17 +218,17 @@ namespace elna::gcc
         }
         else if (auto reference = type.get<boot::pointer_type>())
         {
-            return build_pointer_type(get_inner_alias(reference->base, symbols));
+            return build_pointer_type(get_inner_alias(reference->base, symbols, placeholder));
         }
         else if (auto reference = type.get<boot::array_type>())
         {
-            tree base = get_inner_alias(reference->base, symbols);
+            tree base = get_inner_alias(reference->base, symbols, placeholder);
 
             return build_static_array_type(base, reference->size);
         }
         else if (auto reference = type.get<boot::slice_type>())
         {
-            tree base_type = get_inner_alias(reference->base, symbols);
+            tree base_type = get_inner_alias(reference->base, symbols, placeholder);
             tree slice_record = make_node(RECORD_TYPE);
             tree ptr_field = build_field(UNKNOWN_LOCATION, slice_record, "ptr",
                     build_pointer_type(base_type));
@@ -246,7 +247,7 @@ namespace elna::gcc
         }
         else if (auto reference = type.get<boot::constant_type>())
         {
-            tree unqualified = get_inner_alias(reference->unqualified, symbols);
+            tree unqualified = get_inner_alias(reference->unqualified, symbols, placeholder);
             return build_qualified_type(unqualified, TYPE_QUAL_CONST);
         }
         else if (auto reference = type.get<boot::alias_type>())
@@ -264,15 +265,28 @@ namespace elna::gcc
 
         if (looked_up == NULL_TREE)
         {
-            tree type_tree = get_inner_alias(reference->referent, symbols);
+            /*
+             * Enter a placeholder before converting the referent: a
+             * self-reference through a pointer or a slice then finds the
+             * in-progress declaration and breaks the conversion recursion.
+             */
+            tree placeholder = make_node(RECORD_TYPE);
+            looked_up = build_decl(UNKNOWN_LOCATION, TYPE_DECL,
+                    get_identifier(symbol_name.c_str()), placeholder);
+
+            TREE_PUBLIC(looked_up) = 1;
+            TYPE_NAME(placeholder) = DECL_NAME(looked_up);
+            symbols->enter(symbol_name, looked_up);
+
+            tree type_tree = get_inner_alias(reference->referent, symbols, placeholder);
             if (type_tree == error_mark_node)
             {
                 return error_mark_node;
             }
-            looked_up = build_decl(UNKNOWN_LOCATION, TYPE_DECL,
-                    get_identifier(symbol_name.c_str()), type_tree);
-
-            TREE_PUBLIC(looked_up) = 1;
+            if (type_tree != placeholder)
+            {
+                TREE_TYPE(looked_up) = type_tree;
+            }
             if (is_unique_type(type_tree))
             {
                 TYPE_NAME(type_tree) = DECL_NAME(looked_up);
@@ -282,7 +296,6 @@ namespace elna::gcc
             {
                 TYPE_NAME(type_tree) = looked_up;
             }
-            symbols->enter(symbol_name, looked_up);
         }
         return looked_up;
     }
diff --git a/include/elna/boot/name_analysis.h b/include/elna/boot/name_analysis.h
index cd3c4f7..8e945b2 100644
--- a/include/elna/boot/name_analysis.h
+++ b/include/elna/boot/name_analysis.h
@@ -27,6 +27,7 @@ along with GCC; see the file COPYING3.  If not see
 #include <memory>
 #include <optional>
 #include <variant>
+#include <vector>
 
 namespace elna::boot
 {
@@ -66,6 +67,19 @@ namespace elna::boot
     };
 
     /**
+     * Cyclic type declaration.
+     */
+    class cyclic_declaration_error final : public diagnostic
+    {
+        std::vector<std::string> cycle;
+
+    public:
+        cyclic_declaration_error(const source_position position, const std::vector<std::string>& cycle);
+
+        std::string what() const override;
+    };
+
+    /**
      * \c const qualifier used incorrectly — wrong position or duplicate.
      */
     class const_qualifier_error final : public diagnostic
@@ -222,6 +236,24 @@ namespace elna::boot
     {
         using resolving_visitor::visit;
 
+        // Traversal state of the recursive type walk: 
+        struct walk_state
+        {
+            // Whether the path passed through a record.
+            bool record_seen{ false };
+            // Whether the current occurrence is behind a pointer or a slice.
+            bool guarded{ false };
+        };
+
+        // Returns the cycle path if wiring the referent closes an illegal
+        // cycle, nothing otherwise.
+        static std::optional<std::vector<std::string>> find_alias_cycle(
+                const std::shared_ptr<alias_type>& being_resolved, const type& referent);
+
+        // Returns whether the referent is well-founded.
+        static bool find_alias_cycle(const std::shared_ptr<alias_type>& being_resolved,
+                const type& referent, std::vector<std::string>& alias_path, walk_state state);
+
     public:
         declaration_visitor(symbol_bag& bag, const target_info& target,
                 const std::filesystem::path& module_path);
diff --git a/include/elna/boot/type_check.h b/include/elna/boot/type_check.h
index 0b62a4a..330de44 100644
--- a/include/elna/boot/type_check.h
+++ b/include/elna/boot/type_check.h
@@ -107,19 +107,6 @@ namespace elna::boot
     };
 
     /**
-     * Cyclic type declaration.
-     */
-    class cyclic_declaration_error final : public diagnostic
-    {
-        std::vector<std::string> cycle;
-
-    public:
-        cyclic_declaration_error(const source_position position, const std::vector<std::string>& cycle);
-
-        std::string what() const override;
-    };
-
-    /**
      * Argument count in a procedure call or array constructor doesn't match
      * the expected number of parameters or elements.
      */
@@ -222,8 +209,6 @@ namespace elna::boot
          */
         static bool is_assignable_from(const type& assignee, const type& assignment);
         static bool is_equality_compatible(const type& left, const type& right);
-        static bool check_unresolved_symbol(const std::shared_ptr<alias_type>& alias,
-                std::vector<std::string>& path);
 
         void visit_and_validate_condition(expression& condition);
 
diff --git a/include/elna/gcc/elna-builtins.h b/include/elna/gcc/elna-builtins.h
index 9f24b00..75b409d 100644
--- a/include/elna/gcc/elna-builtins.h
+++ b/include/elna/gcc/elna-builtins.h
@@ -37,7 +37,8 @@ namespace elna::gcc
     tree handle_symbol(const std::string& symbol_name,
             const std::shared_ptr<boot::alias_type>& reference,
             const std::shared_ptr<symbol_table>& symbols);
-    tree get_inner_alias(const boot::type& type, const std::shared_ptr<symbol_table>& symbols);
+    tree get_inner_alias(const boot::type& type, const std::shared_ptr<symbol_table>& symbols,
+            tree placeholder = NULL_TREE);
     void declare_procedure(const std::string& name, const boot::procedure_info& info,
             const std::shared_ptr<symbol_table>& symbols);
     tree declare_variable(const std::string& name, const boot::variable_info& info,
diff --git a/testsuite/compilable/self-referencing-record.elna b/testsuite/compilable/self-referencing-record.elna
new file mode 100644
index 0000000..cc98f86
--- /dev/null
+++ b/testsuite/compilable/self-referencing-record.elna
@@ -0,0 +1,5 @@
+type
+  R = record
+    field: ^R
+  end
+end.
diff --git a/testsuite/fail_compilation/alias-cycle-behind-const.elna b/testsuite/fail_compilation/alias-cycle-behind-const.elna
new file mode 100644
index 0000000..0c3b626
--- /dev/null
+++ b/testsuite/fail_compilation/alias-cycle-behind-const.elna
@@ -0,0 +1,4 @@
+type
+  A = B
+  B = const A (* @Error Type declaration forms a cycle: A -> B -> A *)
+end.
diff --git a/testsuite/fail_compilation/alias-cycle.elna b/testsuite/fail_compilation/alias-cycle.elna
new file mode 100644
index 0000000..e6c822b
--- /dev/null
+++ b/testsuite/fail_compilation/alias-cycle.elna
@@ -0,0 +1,4 @@
+type
+  A = B
+  B = A (* @Error Type declaration forms a cycle: A -> B -> A *)
+end.
diff --git a/testsuite/fail_compilation/alias-field-cycle.elna b/testsuite/fail_compilation/alias-field-cycle.elna
new file mode 100644
index 0000000..f4a554a
--- /dev/null
+++ b/testsuite/fail_compilation/alias-field-cycle.elna
@@ -0,0 +1,5 @@
+type
+  A = record (* @Error Type declaration forms a cycle: A -> A *)
+    field: A
+  end
+end.
diff --git a/testsuite/fail_compilation/array-cycle.elna b/testsuite/fail_compilation/array-cycle.elna
new file mode 100644
index 0000000..617e23d
--- /dev/null
+++ b/testsuite/fail_compilation/array-cycle.elna
@@ -0,0 +1,3 @@
+type
+  A = [2]A (* @Error Type declaration forms a cycle: A -> A *)
+end.
diff --git a/testsuite/fail_compilation/non_constant_array_dimension.elna b/testsuite/fail_compilation/non_constant_array_dimension.elna
new file mode 100644
index 0000000..4ab0d34
--- /dev/null
+++ b/testsuite/fail_compilation/non_constant_array_dimension.elna
@@ -0,0 +1,9 @@
+proc f(len: Int)
+var
+  array: [len]Int (* @Error Array dimensions for type 'Int' should be constant *)
+begin
+  return
+
+begin
+  f(5)
+end.
diff --git a/testsuite/fail_compilation/non_constant_array_dimension.elna.s b/testsuite/fail_compilation/non_constant_array_dimension.elna.s
new file mode 100644
index 0000000..8dc704d
--- /dev/null
+++ b/testsuite/fail_compilation/non_constant_array_dimension.elna.s
@@ -0,0 +1 @@
+	.file	"non_constant_array_dimension.elna"
diff --git a/testsuite/fail_compilation/pointer-cycle.elna b/testsuite/fail_compilation/pointer-cycle.elna
new file mode 100644
index 0000000..f9ee649
--- /dev/null
+++ b/testsuite/fail_compilation/pointer-cycle.elna
@@ -0,0 +1,3 @@
+type
+  A = ^A (* @Error Type declaration forms a cycle: A -> A *)
+end.
diff --git a/testsuite/fail_compilation/procedure-cycle.elna b/testsuite/fail_compilation/procedure-cycle.elna
new file mode 100644
index 0000000..aaed14c
--- /dev/null
+++ b/testsuite/fail_compilation/procedure-cycle.elna
@@ -0,0 +1,3 @@
+type
+  A = proc(): A (* @Error Type declaration forms a cycle: A -> A *)
+end.
diff --git a/testsuite/fail_compilation/record-base-cycle.elna b/testsuite/fail_compilation/record-base-cycle.elna
new file mode 100644
index 0000000..f3bcb20
--- /dev/null
+++ b/testsuite/fail_compilation/record-base-cycle.elna
@@ -0,0 +1,4 @@
+type
+  R = record(R) (* @Error Type declaration forms a cycle: R -> R *)
+  end
+end.
diff --git a/testsuite/fail_compilation/record-base-cycle.elna.s b/testsuite/fail_compilation/record-base-cycle.elna.s
new file mode 100644
index 0000000..64f8722
--- /dev/null
+++ b/testsuite/fail_compilation/record-base-cycle.elna.s
@@ -0,0 +1 @@
+	.file	"record-base-cycle.elna"
diff --git a/testsuite/fail_compilation/slice-cycle.elna b/testsuite/fail_compilation/slice-cycle.elna
new file mode 100644
index 0000000..39eb7db
--- /dev/null
+++ b/testsuite/fail_compilation/slice-cycle.elna
@@ -0,0 +1,3 @@
+type
+  A = []A (* @Error Type declaration forms a cycle: A -> A *)
+end.
diff --git a/testsuite/runnable/recursive_record.elna b/testsuite/runnable/recursive_record.elna
new file mode 100644
index 0000000..6f6b4fa
--- /dev/null
+++ b/testsuite/runnable/recursive_record.elna
@@ -0,0 +1,48 @@
+type
+  Node = record
+    value: Int;
+    next: ^Node
+  end
+
+var
+  first: ^Node
+  second: ^Node
+  third: ^Node
+
+proc malloc(size: Word): Pointer
+extern
+
+proc free(ptr: Pointer)
+extern
+
+proc sum(node: ^Node): Int
+var
+  result: Int
+begin
+  result := 0;
+  if node = nil then
+    result := 0
+  else
+    result := node^.value + sum(node^.next)
+  end;
+  return result
+
+begin
+  first := malloc(#size(Node));
+  second := malloc(#size(Node));
+  third := malloc(#size(Node));
+
+  first^.value := 1;
+  first^.next := second;
+  second^.value := 2;
+  second^.next := third;
+  third^.value := 3;
+  third^.next := nil;
+
+  assert(sum(first) = 6);
+  assert(first^.next^.next^.value = 3);
+
+  free(first);
+  free(second);
+  free(third)
+end.