Enforce case label uniqueness and constness

9 files changed, 272 insertions, 81 deletions

diff --git a/include/elna/boot/ast.h b/include/elna/boot/ast.h
index 8ee0e8b..9697d1c 100644
--- a/include/elna/boot/ast.h
+++ b/include/elna/boot/ast.h
@@ -214,8 +214,8 @@ namespace elna::boot
 
         void visit(variable_declaration *) override;
         void visit(procedure_declaration *) override;
-        void visit(assign_statement *) override;
-        void visit(if_statement *) override;
+        void visit(assign_statement *statement) override;
+        void visit(if_statement *statement) override;
         void visit(import_declaration *) override;
         void visit(while_statement *statement) override;
         void visit(repeat_statement *statement) override;
diff --git a/include/elna/boot/dependency.h b/include/elna/boot/dependency.h
index 6a3a412..b3c1155 100644
--- a/include/elna/boot/dependency.h
+++ b/include/elna/boot/dependency.h
@@ -17,13 +17,13 @@ along with GCC; see the file COPYING3.  If not see
 
 #pragma once
 
-#include <filesystem>
-#include <fstream>
-#include "elna/boot/evaluator.h"
 #include "elna/boot/result.h"
 #include "elna/boot/ast.h"
 #include "elna/boot/symbol.h"
 
+#include <filesystem>
+#include <fstream>
+
 namespace elna::boot
 {
     class dependency : public error_container
diff --git a/include/elna/boot/evaluator.h b/include/elna/boot/evaluator.h
index 5812ee8..8b36e1b 100644
--- a/include/elna/boot/evaluator.h
+++ b/include/elna/boot/evaluator.h
@@ -17,28 +17,14 @@ along with GCC; see the file COPYING3.  If not see
 
 #pragma once
 
-#include <cstdint>
-#include <memory>
-#include <optional>
-#include <string>
-#include <variant>
-
 #include "elna/boot/symbol.h"
 #include "elna/boot/ast.h"
 
+#include <memory>
+#include <optional>
+
 namespace elna::boot
 {
-    /**
-     * A module-level variable initializer must be a constant expression.
-     */
-    class non_constant_initializer_error : public error
-    {
-    public:
-        explicit non_constant_initializer_error(const source_position position);
-
-        std::string what() const override;
-    };
-
     std::optional<type_properties> get_type_properties(const type& subject, const target_info& target);
 
     /**
@@ -73,7 +59,6 @@ namespace elna::boot
         std::optional<constant_value> evaluate_cast(cast_expression& subject);
         std::optional<std::size_t> evaluate_traits_size(const type& subject);
         std::optional<std::size_t> evaluate_traits_alignment(const type& subject);
-        void fold_aggregate_field(field_initializer& field_init);
 
     public:
         std::optional<constant_value> evaluate_traits(traits_expression& subject);
@@ -87,44 +72,5 @@ namespace elna::boot
          *         expression is not constant.
          */
         std::optional<constant_value> evaluate(expression& subject);
-
-        /**
-         * Folds an expression into literals.
-         *
-         * For scalars, the original expression is deleted and a new
-         * literal node is returned.  For constructors, fields or
-         * elements are folded recursively and the original node is
-         * returned.
-         *
-         * \param original Expression to fold.
-         * \return The folded expression (either a new literal or the
-         *         original aggregate with folded children).
-         */
-        expression *fold(expression& original);
-    };
-
-    /**
-     * Folding pass that validates constant variable initializers.
-     *
-     * Runs after name analysis and type checking.  Walks all variable
-     * declarations, evaluates constant initializers, and records them
-     * so later declarations can chain through earlier ones.
-     */
-    class constant_folder final : public walking_visitor, public error_container
-    {
-        symbol_bag& bag;
-        const target_info& target;
-        evaluator constant_evaluator;
-
-        expression& fold_trait(expression& expr);
-
-    public:
-        constant_folder(symbol_bag& bag, const target_info& target);
-
-        void visit(variable_declaration* declaration) override;
-        void visit(cast_expression *expr) override;
-        void visit(binary_expression *expr) override;
-        void visit(unary_expression *expr) override;
-        void visit(procedure_call *call) override;
     };
 }
diff --git a/include/elna/boot/name_analysis.h b/include/elna/boot/name_analysis.h
index a4f550d..8f53260 100644
--- a/include/elna/boot/name_analysis.h
+++ b/include/elna/boot/name_analysis.h
@@ -17,16 +17,15 @@ along with GCC; see the file COPYING3.  If not see
 
 #pragma once
 
+#include "elna/boot/ast.h"
+#include "elna/boot/result.h"
+#include "elna/boot/symbol.h"
+
 #include <string>
 #include <memory>
-#include <map>
 #include <optional>
 #include <variant>
 
-#include "elna/boot/ast.h"
-#include "elna/boot/result.h"
-#include "elna/boot/symbol.h"
-
 namespace elna::boot
 {
     /**
@@ -83,8 +82,17 @@ namespace elna::boot
     class member_error : public error
     {
     public:
-        struct not_found { std::string name; type composite; };
-        struct duplicate { std::string name; type aggregate; std::optional<source_position> original; std::optional<std::string> base; };
+        struct not_found
+        {
+            std::string name;
+            type composite;
+        };
+        struct duplicate {
+            std::string name;
+            type aggregate;
+            std::optional<source_position> original;
+            std::optional<std::string> base;
+        };
         using payload_type = std::variant<not_found, duplicate>;
 
         member_error(const source_position position, payload_type payload);
diff --git a/include/elna/boot/result.h b/include/elna/boot/result.h
index 89753c1..42c96f2 100644
--- a/include/elna/boot/result.h
+++ b/include/elna/boot/result.h
@@ -19,6 +19,7 @@ along with GCC; see the file COPYING3.  If not see
 
 #include <cstddef>
 #include <cstdint>
+#include <functional>
 #include <string>
 #include <deque>
 #include <memory>
@@ -201,6 +202,11 @@ namespace elna::boot
         using iterator = std::vector<value_type>::iterator;
         using const_iterator = std::vector<value_type>::const_iterator;
 
+        auto operator<=>(const ordered_map& that) const
+        {
+            return this->payload <=> that.payload;
+        }
+
         /**
          * Finds element with specific key.
          *
@@ -304,6 +310,11 @@ namespace elna::boot
         {
             return this->payload.cend();
         }
+
+        std::size_t size() const
+        {
+            return this->payload.size();
+        }
     };
 
     /**
@@ -370,6 +381,21 @@ namespace elna::boot
         constant_aggregate<std::vector>
     >;
 
+    /**
+     * Hash and equality for \c constant_value, for use with std::unordered_map.
+     */
+    struct constant_value_hash
+    {
+        std::size_t operator()(const constant_value& value) const noexcept;
+        bool operator()(const constant_value& lhs, const constant_value& rhs) const noexcept;
+    };
+
+    /**
+     * Representation of array and record literals.
+     *
+     * \tparam C Used container, like \c std::vector or ordered_map.
+     * \tparam Alloc Allocator passed to the container.
+     */
     template<template<typename, typename> typename C, template<typename> typename Alloc>
     class constant_aggregate
     {
@@ -406,6 +432,88 @@ namespace elna::boot
         {
             return this->container.get();
         }
+
+        bool operator==(const constant_aggregate<std::vector>& that) const
+            requires std::is_same_v<Container, std::vector<constant_value, Alloc<constant_value>>>
+        {
+            if (this->container->size() != that.container->size())
+            {
+                return false;
+            }
+            return std::ranges::equal(*this->container, *that.container, constant_value_hash{});
+        }
+
+        bool operator==(const constant_aggregate<ordered_map>& that) const
+            requires std::is_same_v<Container, ordered_map<constant_value, Alloc<constant_value>>>
+        {
+            if (this->container->size() != that.container->size())
+            {
+                return false;
+            }
+            const constant_value_hash comparator{};
+
+            return std::ranges::equal(*this->container, *that.container,
+                    [comparator](const auto& lhs, const auto& rhs) {
+                        return lhs.first == rhs.first && comparator(lhs.second, rhs.second);
+                    });
+        }
+
+        bool operator!=(const constant_aggregate& that) const
+        {
+            return !(*this == that);
+        }
+    };
+
+    /**
+	 * Primary template, intentionally left undefined. Attempting to use this trait
+	 * trait with a second template argument that is not a \c std::variant results
+     * in a compile error, since no matching specialization exists.
+	 *
+	 * \tparam T The type to search for among the variant's alternatives.
+	 * \tparam V A \c std::variant type to search within.
+	 *
+	 * \see is_in_variant_v
+	 */
+    template<typename T, typename V>
+    struct is_in_variant;
+
+    /**
+     * Partial specialization implementing the check for std::variant<Ts...>.
+     * The first argument is the tested type, the second is \c std::variant.
+     *
+     * \tparam T The type to search for.
+     * \tparam Ts The variant's alternative types.
+	 *
+	 * \see is_in_variant_v
+     */
+    template<typename T, typename... Ts>
+    struct is_in_variant<T, std::variant<Ts...>>
+        : std::disjunction<std::is_same<T, Ts>...>
+    {
+    };
+
+    /**
+     * Convenience variable template for is_in_variant.
+     *
+     * \tparam T The type to search for among the variant's alternatives.
+     * \tparam V A \c std::variant type to search within.
+     *
+     * \return Whether \p T is one of \p V's alternative types.
+     *
+     * \see is_in_variant
+     */
+    template <typename T, typename V>
+    inline constexpr bool is_in_variant_v = is_in_variant<T, V>::value;
+
+    struct hash_accumulator
+    {
+        hash_accumulator operator+(const std::size_t& that) const;
+
+        std::size_t seed() const;
+
+    private:
+        static constexpr std::size_t golden_ratio = 0x9e3779b9;
+        std::size_t m_seed{ 0 };
     };
 }
 
@@ -414,3 +522,21 @@ struct std::hash<elna::boot::identifier>
 {
     std::size_t operator()(const elna::boot::identifier& key) const noexcept;
 };
+
+template<>
+struct std::hash<elna::boot::global_address>
+{
+    std::size_t operator()(const elna::boot::global_address& key) const noexcept;
+};
+
+template<>
+struct std::hash<elna::boot::constant_aggregate<std::vector>>
+{
+    std::size_t operator()(const elna::boot::constant_aggregate<std::vector>& key) const noexcept;
+};
+
+template<>
+struct std::hash<elna::boot::constant_aggregate<elna::boot::ordered_map>>
+{
+    std::size_t operator()(const elna::boot::constant_aggregate<elna::boot::ordered_map>& key) const noexcept;
+};
diff --git a/include/elna/boot/symbol.h b/include/elna/boot/symbol.h
index 46d9c2c..dd3e8ff 100644
--- a/include/elna/boot/symbol.h
+++ b/include/elna/boot/symbol.h
@@ -41,9 +41,15 @@ namespace elna::boot
     struct procedure_type;
     struct enumeration_type;
 
+    /**
+     * Represents a type stored in the symbol table.
+     *
+     * All types are wrapped in \c std::shared_ptr so that copying is cheap.
+     * There is also an empty type representing an error.
+     */
     class type
     {
-        std::variant<
+        using Payload = std::variant<
             std::monostate,
             std::weak_ptr<alias_type>,
             std::shared_ptr<primitive_type>,
@@ -54,21 +60,45 @@ namespace elna::boot
             std::shared_ptr<slice_type>,
             std::shared_ptr<procedure_type>,
             std::shared_ptr<enumeration_type>
-        > payload;
+        >;
+        Payload payload;
 
     public:
+        /**
+         * Constructs an empty, invalid type.
+         */
         type() = default;
 
+        /**
+         * Constructs a type alias.
+         *
+         * The specialization is required because the type is internally stored
+         * as \c std::weak_ptr.
+         *
+         * \param alias Stored type.
+         */
         explicit type(std::shared_ptr<alias_type> alias);
-        explicit type(std::shared_ptr<primitive_type> primitive);
-        explicit type(std::shared_ptr<record_type> record);
-        explicit type(std::shared_ptr<pointer_type> pointer);
-        explicit type(std::shared_ptr<constant_type> constant);
-        explicit type(std::shared_ptr<array_type> array);
-        explicit type(std::shared_ptr<slice_type> slice);
-        explicit type(std::shared_ptr<procedure_type> procedure);
-        explicit type(std::shared_ptr<enumeration_type> enumeration);
 
+        /**
+         * Constructs a non empty type.
+         *
+         * \tparam T Type kind.
+         * \param value Concrete type.
+         */
+        template<typename T>
+        explicit type(std::shared_ptr<T> value)
+            requires is_in_variant_v<std::shared_ptr<T>, Payload>
+            : payload(std::move(value))
+        {
+        }
+
+        /**
+         * Checks whether \p T is currently stored and returns this concrete
+         * type.
+         *
+         * \tparam T Type kind to check.
+         * \return Concrete type or \c nullptr.
+         */
         template<typename T>
         std::shared_ptr<T> get() const;
 
@@ -76,6 +106,9 @@ namespace elna::boot
         bool operator==(const type& other) const;
         explicit operator bool() const;
 
+        /**
+         * \return Whether type holds no concrete type.
+         */
         bool empty() const;
 
         /**
@@ -129,8 +162,6 @@ namespace elna::boot
         explicit primitive_type(const std::string& identifier);
     };
 
-    using type_field = std::pair<std::string, type>;
-
     struct record_type
     {
         ordered_map<type> fields;
diff --git a/include/elna/boot/validation.h b/include/elna/boot/validation.h
new file mode 100644
index 0000000..c11a652
--- /dev/null
+++ b/include/elna/boot/validation.h
@@ -0,0 +1,76 @@
+/* Final validation after constant folding.
+   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/>.  */
+
+#pragma once
+
+#include "elna/boot/ast.h"
+#include "elna/boot/evaluator.h"
+
+#include <string>
+
+namespace elna::boot
+{
+    /**
+     * Validation error.
+     */
+    class validation_error : public error
+    {
+    public:
+        struct non_constant_initializer
+        {
+            std::vector<identifier> identifiers;
+        };
+        struct duplicate_case
+        {
+            source_position first;
+        };
+        struct non_constant_case_label
+        {
+        };
+        using payload_type = std::variant<non_constant_initializer, duplicate_case, non_constant_case_label>;
+
+        validation_error(const source_position position, payload_type payload);
+
+        std::string what() const override;
+        std::optional<std::pair<std::string, source_position>> note() const override;
+
+        static validation_error non_constant_initializer_error(const source_position position,
+                const std::vector<identifier_definition>& identifiers);
+
+    private:
+        payload_type payload;
+    };
+
+    /**
+     * Validates:
+     * - case label uniqueness
+     * - Initializer constness.
+     */
+    class validation_visitor final : public walking_visitor, public error_container
+    {
+        symbol_bag& bag;
+        const target_info& target;
+        evaluator constant_evaluator;
+
+    public:
+        validation_visitor(symbol_bag& bag, const target_info& target);
+
+        void visit(variable_declaration* declaration) override;
+        void visit(procedure_declaration* declaration) override;
+        void visit(case_statement *statement) override;
+    };
+}
diff --git a/include/elna/gcc/elna-generic.h b/include/elna/gcc/elna-generic.h
index c2f154f..b5ba5e0 100644
--- a/include/elna/gcc/elna-generic.h
+++ b/include/elna/gcc/elna-generic.h
@@ -37,6 +37,7 @@ namespace elna::gcc
         elna::boot::symbol_bag bag;
         std::shared_ptr<symbol_table> symbols;
         const elna::boot::target_info& target;
+        elna::boot::evaluator constant_evaluator;
 
         static tree build_equality(boot::binary_expression *expression, tree left, tree right);
         static tree build_equality_comparison(location_t loc, tree left, tree right,
@@ -79,6 +80,7 @@ namespace elna::gcc
         void visit(boot::literal<unsigned char> *character) override;
         void visit(boot::literal<std::nullptr_t> *) override;
         void visit(boot::literal<std::string> *string) override;
+        void visit(boot::traits_expression *trait) override;
         void visit(boot::binary_expression *expression) override;
         void visit(boot::unary_expression *expression) override;
         void visit(boot::variable_declaration *declaration) override;
diff --git a/include/elna/gcc/elna-tree.h b/include/elna/gcc/elna-tree.h
index a989656..71cc13b 100644
--- a/include/elna/gcc/elna-tree.h
+++ b/include/elna/gcc/elna-tree.h
@@ -68,6 +68,8 @@ namespace elna::gcc
     const elna::boot::target_info& get_host_target();
 
     tree extract_constant(tree expression);
+    tree constant_to_tree(const boot::constant_value& value,
+            const std::shared_ptr<symbol_table>& symbols, tree type = NULL_TREE);
 
     template<typename... Args>
     tree call_built_in(location_t call_location, const char *name, tree return_type, Args... arguments)