Implement generic pointers

4 files changed, 218 insertions, 2 deletions

diff --git a/include/elna/boot/ast.h b/include/elna/boot/ast.h
index 4919510..f697b44 100644
--- a/include/elna/boot/ast.h
+++ b/include/elna/boot/ast.h
@@ -445,11 +445,20 @@ namespace elna::boot
     public:
         const std::vector<field_declaration> fields;
         const std::optional<identifier> base;
+        /**
+         * Type arguments of a generic base. Empty when the base is plain or
+         * absent.
+         */
+        std::vector<type_expression *> base_arguments;
 
         record_type_expression(const source_position position,
                 std::vector<field_declaration>&& fields);
         record_type_expression(const source_position position,
                 std::vector<field_declaration>&& fields, identifier&& base);
+        record_type_expression(const source_position position,
+                std::vector<field_declaration>&& fields, identifier&& base,
+                std::vector<type_expression *>&& base_arguments);
+        ~record_type_expression() override;
 
         void accept(parser_visitor *visitor) override;
         record_type_expression *is_record() override;
@@ -481,10 +490,19 @@ namespace elna::boot
     public:
         const identifier type_name;
         const std::vector<field_initializer> field_initializers;
+        /**
+         * Type arguments naming the instantiation being constructed. Empty
+         * when no argument list was written.
+         */
+        const std::vector<type_expression *> arguments;
 
         record_constructor_expression(const source_position position,
                 identifier&& type_name,
                 std::vector<field_initializer>&& field_initializers);
+        record_constructor_expression(const source_position position,
+                identifier&& type_name, std::vector<type_expression *>&& arguments,
+                std::vector<field_initializer>&& field_initializers);
+        ~record_constructor_expression() override;
         void accept(parser_visitor *visitor) override;
         record_constructor_expression *is_record_constructor() override;
     };
@@ -609,6 +627,12 @@ namespace elna::boot
     public:
         std::optional<procedure_body> body;
 
+        /**
+         * Type parameters bound by this declaration. Empty for a plain
+         * procedure.
+         */
+        std::vector<elna::boot::identifier> parameters;
+
         procedure_declaration(const source_position position, identifier_definition identifier,
                 procedure_type_expression *heading, procedure_body&& body);
         procedure_declaration(const source_position position, identifier_definition identifier,
@@ -628,6 +652,11 @@ namespace elna::boot
         type_expression *m_underlying_type;
 
     public:
+        /**
+         * Type parameters bound by this declaration. Empty for a plain type.
+         */
+        std::vector<elna::boot::identifier> parameters;
+
         type_declaration(const source_position position, identifier_definition identifier,
                 type_expression *underlying_type);
         ~type_declaration() override;
@@ -752,8 +781,19 @@ namespace elna::boot
     {
     public:
         const std::string name;
+        /**
+         * Type arguments of a generic instantiation. Empty when no argument
+         * list was written, the lists being non-empty where they appear.
+         */
+        std::vector<type_expression *> arguments;
+        /// Resolved form of \c arguments, filled by name analysis.
+        std::vector<type> argument_types;
 
         named_expression(const source_position position, const std::string& name);
+        named_expression(const source_position position, const std::string& name,
+                std::vector<type_expression *>&& arguments);
+        ~named_expression() override;
+
         void accept(parser_visitor *visitor) override;
 
         named_expression *is_named() override;
diff --git a/include/elna/boot/name_analysis.h b/include/elna/boot/name_analysis.h
index 4a22df7..46a3e2d 100644
--- a/include/elna/boot/name_analysis.h
+++ b/include/elna/boot/name_analysis.h
@@ -186,6 +186,12 @@ namespace elna::boot
          * other than a type.
          */
         type resolve_type(type_expression& expression);
+        /*
+         * Opens a scope holding the given type parameters, which the caller
+         * closes once the declaration they belong to is resolved.
+         */
+        std::vector<type> enter_parameters(const std::vector<elna::boot::identifier>& parameters);
+        std::vector<type> resolve_arguments(const std::vector<type_expression *>& arguments);
         type lookup_primitive_type(const std::string& name);
         std::filesystem::path redefinition_file(const std::shared_ptr<info>& original) const;
         std::shared_ptr<variable_info> register_variable(const std::string& name,
diff --git a/include/elna/boot/symbol.h b/include/elna/boot/symbol.h
index 40cbbc6..8646f48 100644
--- a/include/elna/boot/symbol.h
+++ b/include/elna/boot/symbol.h
@@ -42,6 +42,9 @@ namespace elna::boot
     struct procedure_type;
     struct enumeration_type;
     struct extern_type;
+    struct parameter_type;
+    struct generic_type;
+    struct instantiated_type;
 
     /**
      * Represents a type stored in the symbol table.
@@ -62,7 +65,10 @@ namespace elna::boot
             std::shared_ptr<slice_type>,
             std::shared_ptr<procedure_type>,
             std::shared_ptr<enumeration_type>,
-            std::shared_ptr<extern_type>
+            std::shared_ptr<extern_type>,
+            std::shared_ptr<parameter_type>,
+            std::shared_ptr<generic_type>,
+            std::shared_ptr<instantiated_type>
         >;
         Payload payload;
 
@@ -200,6 +206,50 @@ namespace elna::boot
     {
     };
 
+    /**
+     * Type parameter of a generic declaration.
+     *
+     * It denotes an unknown pointer type chosen at instantiation, so it is
+     * usable wherever a pointer is, and erases to a pointer in the backend.
+     * Each declaration gets fresh parameters; two parameters spelled alike in
+     * different declarations never compare equal.
+     */
+    struct parameter_type
+    {
+        const std::string name;
+
+        explicit parameter_type(const std::string& name);
+    };
+
+    /**
+     * Generic declaration.
+     *
+     * Not usable as a type by itself; it carries the parameter names so that a
+     * missing or miscounted argument list can be reported against them.
+     */
+    struct generic_type
+    {
+        /// Parameters of this declaration, each holding a \c parameter_type.
+        const std::vector<type> parameters;
+        type referent;
+
+        explicit generic_type(std::vector<type>&& parameters, type referent = type());
+    };
+
+    /**
+     * Generic applied to type arguments.
+     *
+     * \c generic holds the alias the arguments were applied to, so that two
+     * mentions of the same instantiation share the generic's identity.
+     */
+    struct instantiated_type
+    {
+        const type generic;
+        const std::vector<type> arguments;
+
+        instantiated_type(type generic, std::vector<type>&& arguments);
+    };
+
     class type_info;
     class procedure_info;
     class variable_info;
@@ -378,6 +428,10 @@ namespace elna::boot
         /// Local definitions.
         std::shared_ptr<symbol_table> scope;
 
+        /// Type parameters, each holding a \c parameter_type. Empty for a
+        /// plain procedure.
+        std::vector<type> parameters;
+
         /**
          * Constructs procedure symbol information.
          *
@@ -568,6 +622,66 @@ namespace elna::boot
     type resolve_aliases(const type& checked);
 
     /**
+     * Resolves an alias chain without seeing through instantiations, which
+     * \c resolve_aliases does.
+     *
+     * \param checked The type to resolve.
+     * \return The first non-alias type in the chain.
+     */
+    type unwrap_aliases(const type& checked);
+
+    /**
+     * \param checked A type naming a generic, possibly through aliases.
+     * \return The generic, or \c nullptr if \p checked does not name one.
+     */
+    std::shared_ptr<generic_type> unwrap_generic(const type& checked);
+
+    /**
+     * Replaces type parameters with the arguments standing at their position.
+     *
+     * The substitution is structural and stops at record boundaries, whose
+     * fields are substituted when they are looked up instead.
+     *
+     * \param subject Type to substitute in.
+     * \param parameters Parameters of the generic being substituted.
+     * \param arguments Arguments to replace them with.
+     * \return The substituted type.
+     */
+    type substitute(const type& subject, const std::vector<type>& parameters,
+            const std::vector<type>& arguments);
+
+    /**
+     * Resolves a type to the view layout and codegen see, in which an
+     * instantiation is its generic's referent with the arguments dropped.
+     *
+     * \param checked The type to resolve.
+     * \return The erased type, empty if a generic is unresolved.
+     */
+    type erase_generic(const type& checked);
+
+    /**
+     * \param derived A record type or an instantiation of a generic record.
+     * \return The type it extends, with the arguments of \p derived
+     *         substituted into it. Empty if it extends nothing.
+     */
+    type base_of(const type& derived);
+
+    /**
+     * \param base Candidate base type.
+     * \param derived Candidate derived type.
+     * \return Whether \p base occurs in \p derived's base chain.
+     */
+    bool is_base_of(const type& base, const type& derived);
+
+    /**
+     * Applies an instantiation's arguments to its generic's referent.
+     *
+     * \param instance The instantiation to apply.
+     * \return The substituted referent, empty if the generic is unresolved.
+     */
+    type instantiate(const std::shared_ptr<instantiated_type>& instance);
+
+    /**
      * Checks whether the given type is the built-in type \a name.
      *
      * \param checked The type to check.
diff --git a/include/elna/boot/type_check.h b/include/elna/boot/type_check.h
index 50b9225..e948ada 100644
--- a/include/elna/boot/type_check.h
+++ b/include/elna/boot/type_check.h
@@ -94,6 +94,8 @@ namespace elna::boot
             opaque_element,
             opaque_cast,
             opaque_arithmetic,
+            dereference_of_parameter,
+            parameter_arithmetic,
             zero_sized,
             not_addressable
         };
@@ -119,7 +121,8 @@ namespace elna::boot
         {
             trait,
             call,
-            array
+            array,
+            generic
         };
     private:
         kind m_kind;
@@ -161,6 +164,51 @@ namespace elna::boot
     };
 
     /**
+     * Error applying a generic or declaring its parameters.
+     */
+    class generic_error final : public diagnostic
+    {
+    public:
+        struct not_generic
+        {
+        };
+        struct unused_parameter
+        {
+            std::string parameter;
+        };
+        struct argument_not_pointer
+        {
+            type actual;
+        };
+        struct constant_argument
+        {
+            type actual;
+        };
+        struct uninferrable_parameter
+        {
+            std::string parameter;
+        };
+        struct shape_mismatch
+        {
+            type declared;
+            type actual;
+        };
+
+        using payload_type = std::variant<not_generic, unused_parameter,
+              argument_not_pointer, constant_argument, uninferrable_parameter,
+              shape_mismatch>;
+
+        generic_error(const source_position position, const std::string& generic_name,
+                payload_type payload);
+
+        std::string what() const override;
+
+    private:
+        std::string generic_name;
+        payload_type payload;
+    };
+
+    /**
      * Chain of responsibility for type compatibility checks.
      *
      * Populate \c ctx with pre-resolved types, then call \c run().
@@ -205,6 +253,8 @@ namespace elna::boot
         symbol_bag bag;
         std::shared_ptr<procedure_info> current_procedure;
         const target_info& target;
+        /// Whether the name being visited stands in a call's callable position.
+        bool in_callable_position{ false };
 
         /*
          * Whether an expression of type assignment can be assigned to a variable
@@ -214,6 +264,11 @@ namespace elna::boot
         static bool is_equality_compatible(const type& left, const type& right);
 
         void visit_and_validate_condition(expression& condition);
+        void check_arguments(const named_expression& reference, const std::vector<type>& arguments);
+        void check_parameters_used(const source_position position, const std::string& name,
+                const std::vector<type>& parameters, const type& heading);
+        type infer_call(procedure_call& call, const named_expression& reference,
+                const procedure_info& procedure);
         void check_return(const procedure_body& body, const source_position position,
                 const std::string& name);
 
@@ -240,6 +295,7 @@ namespace elna::boot
         void visit(slicing_expression *expression) override;
         void visit(array_access_expression *expression) override;
         void visit(dereference_expression *expression) override;
+        void visit(named_expression *expression) override;
         void visit(cast_expression *expression) override;
         void visit(unary_expression *expression) override;
         void visit(binary_expression *expression) override;