Implement generic pointers

1 files changed, 208 insertions, 7 deletions

diff --git a/boot/symbol.cc b/boot/symbol.cc
index 0d847e1..9092866 100644
--- a/boot/symbol.cc
+++ b/boot/symbol.cc
@@ -119,6 +119,22 @@ namespace elna::boot
             return right_procedure != nullptr && left_procedure->return_type == right_procedure->return_type
                 && left_procedure->parameters == right_procedure->parameters;
         }
+        if (auto left_parameter = resolved_this.get<parameter_type>())
+        {
+            return left_parameter == resolved_that.get<parameter_type>();
+        }
+        if (auto left_generic = resolved_this.get<generic_type>())
+        {
+            return left_generic == resolved_that.get<generic_type>();
+        }
+        if (auto left_instance = resolved_this.get<instantiated_type>())
+        {
+            auto right_instance = resolved_that.get<instantiated_type>();
+
+            return right_instance != nullptr
+                && left_instance->generic == right_instance->generic
+                && left_instance->arguments == right_instance->arguments;
+        }
         return resolved_this.empty() && resolved_that.empty();
     }
 
@@ -192,6 +208,18 @@ namespace elna::boot
             {
                 return "extern";
             }
+            else if constexpr (std::is_same_v<T, std::shared_ptr<parameter_type>>)
+            {
+                return payload->name;
+            }
+            else if constexpr (std::is_same_v<T, std::shared_ptr<generic_type>>)
+            {
+                return "generic";
+            }
+            else if constexpr (std::is_same_v<T, std::shared_ptr<instantiated_type>>)
+            {
+                return payload->generic.to_string() + "#[" + join(payload->arguments) + "]";
+            }
         }, payload);
     }
 
@@ -240,6 +268,21 @@ namespace elna::boot
     {
     }
 
+    parameter_type::parameter_type(const std::string& name)
+        : name(name)
+    {
+    }
+
+    generic_type::generic_type(std::vector<type>&& parameters, type referent)
+        : parameters(std::move(parameters)), referent(std::move(referent))
+    {
+    }
+
+    instantiated_type::instantiated_type(type generic, std::vector<type>&& arguments)
+        : generic(std::move(generic)), arguments(std::move(arguments))
+    {
+    }
+
     info::~info() = default;
 
     std::shared_ptr<type_info> info::is_type()
@@ -471,12 +514,171 @@ namespace elna::boot
         }
     }
 
+    type unwrap_aliases(const type& checked)
+    {
+        if (auto alias = checked.get<alias_type>())
+        {
+            return unwrap_aliases(alias->referent);
+        }
+        return checked;
+    }
+
+    std::shared_ptr<generic_type> unwrap_generic(const type& checked)
+    {
+        return unwrap_aliases(checked).get<generic_type>();
+    }
+
+    type substitute(const type& subject, const std::vector<type>& parameters,
+            const std::vector<type>& arguments)
+    {
+        if (auto parameter = subject.get<parameter_type>())
+        {
+            for (std::size_t i = 0; i < parameters.size() && i < arguments.size(); ++i)
+            {
+                if (parameters[i].get<parameter_type>() == parameter)
+                {
+                    return arguments[i];
+                }
+            }
+            return subject;
+        }
+        if (auto pointer = subject.get<pointer_type>())
+        {
+            return type(std::make_shared<pointer_type>(
+                        substitute(pointer->base, parameters, arguments)));
+        }
+        if (auto slice = subject.get<slice_type>())
+        {
+            return type(std::make_shared<slice_type>(
+                        substitute(slice->base, parameters, arguments)));
+        }
+        if (auto array = subject.get<array_type>())
+        {
+            return type(std::make_shared<array_type>(
+                        substitute(array->base, parameters, arguments), array->size));
+        }
+        if (auto qualified = subject.get<constant_type>())
+        {
+            return type(std::make_shared<constant_type>(
+                        substitute(qualified->unqualified, parameters, arguments)));
+        }
+        if (auto procedure = subject.get<procedure_type>())
+        {
+            procedure_type::return_t result_return = procedure->return_type;
+
+            if (!result_return.no_return && !result_return.proper_type.empty())
+            {
+                result_return = procedure_type::return_t(
+                        substitute(result_return.proper_type, parameters, arguments));
+            }
+            auto result = std::make_shared<procedure_type>(std::move(result_return));
+
+            result->parameters.reserve(procedure->parameters.size());
+            for (const type& parameter_type : procedure->parameters)
+            {
+                result->parameters.push_back(substitute(parameter_type, parameters, arguments));
+            }
+            return type(result);
+        }
+        if (auto instance = subject.get<instantiated_type>())
+        {
+            std::vector<type> substituted;
+
+            substituted.reserve(instance->arguments.size());
+            for (const type& argument : instance->arguments)
+            {
+                substituted.push_back(substitute(argument, parameters, arguments));
+            }
+            return type(std::make_shared<instantiated_type>(instance->generic, std::move(substituted)));
+        }
+        return subject;
+    }
+
+    type instantiate(const std::shared_ptr<instantiated_type>& instance)
+    {
+        std::shared_ptr<generic_type> const generic = unwrap_generic(instance->generic);
+
+        return generic == nullptr
+            ? type()
+            : substitute(generic->referent, generic->parameters, instance->arguments);
+    }
+
+    type erase_generic(const type& checked)
+    {
+        type resolved = resolve_underlying_type(checked);
+
+        if (auto instance = resolved.get<instantiated_type>())
+        {
+            std::shared_ptr<generic_type> const generic = unwrap_generic(instance->generic);
+
+            return generic == nullptr ? type() : resolve_underlying_type(generic->referent);
+        }
+        if (auto generic = resolved.get<generic_type>())
+        {
+            return resolve_underlying_type(generic->referent);
+        }
+        return resolved;
+    }
+
+    /*
+     * Rewrites a type taken from an instantiation's erased referent so that it
+     * reads as the instantiation sees it. The identity for anything else.
+     */
+    static type substitute_from(const type& subject, const type& taken)
+    {
+        auto instance = subject.get<instantiated_type>();
+
+        if (instance == nullptr)
+        {
+            return taken;
+        }
+        std::shared_ptr<generic_type> const generic = unwrap_generic(instance->generic);
+
+        return generic == nullptr
+            ? type()
+            : substitute(taken, generic->parameters, instance->arguments);
+    }
+
+    type base_of(const type& derived)
+    {
+        const type resolved = resolve_underlying_type(derived);
+        auto record = erase_generic(resolved).get<record_type>();
+
+        return record == nullptr || record->base.empty()
+            ? type()
+            : substitute_from(resolved, record->base);
+    }
+
+    bool is_base_of(const type& base, const type& derived)
+    {
+        for (type current = base_of(derived); !current.empty(); current = base_of(current))
+        {
+            if (current == base)
+            {
+                return true;
+            }
+        }
+        return false;
+    }
+
     type resolve_aliases(const type& checked)
     {
         if (auto alias = checked.get<alias_type>())
         {
             return resolve_aliases(alias->referent);
         }
+        if (auto instance = checked.get<instantiated_type>())
+        {
+            std::shared_ptr<generic_type> const generic = unwrap_generic(instance->generic);
+
+            // A record referent makes the instantiation nominal, so resolution
+            // stops here and Stack#[^File] stays distinct from Stack#[^Socket].
+            if (generic == nullptr || unwrap_aliases(generic->referent).get<record_type>() != nullptr)
+            {
+                return checked;
+            }
+            return resolve_aliases(instantiate(instance));
+        }
         return checked;
     }
 
@@ -535,6 +737,7 @@ namespace elna::boot
     {
         return checked.get<pointer_type>() != nullptr
             || checked.get<procedure_type>() != nullptr
+            || checked.get<parameter_type>() != nullptr
             || is_primitive_type(checked, "Pointer");
     }
 
@@ -575,20 +778,18 @@ namespace elna::boot
     {
         const type resolved_type = resolve_underlying_type(composite_type);
 
-        if (auto record = resolved_type.get<record_type>())
+        if (auto record = erase_generic(resolved_type).get<record_type>())
         {
             for (const auto& [name, field_type] : record->fields)
             {
                 if (name == field_name)
                 {
-                    return field_type;
+                    return substitute_from(resolved_type, field_type);
                 }
             }
-            if (!record->base.empty())
-            {
-                return lookup_field(record->base, field_name);
-            }
         }
-        return type();
+        const type base = base_of(resolved_type);
+
+        return base.empty() ? type() : lookup_field(base, field_name);
     }
 }