Implement initializer evaluator

1 files changed, 563 insertions, 0 deletions

diff --git a/boot/evaluator.cc b/boot/evaluator.cc
new file mode 100644
index 0000000..f782dd6
--- /dev/null
+++ b/boot/evaluator.cc
@@ -0,0 +1,563 @@
+/* Constant expression evaluation.
+   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/>.  */
+
+#include "elna/boot/evaluator.h"
+#include "elna/boot/ast.h"
+
+#include <numeric>
+#include <algorithm>
+#include <limits>
+
+namespace elna::boot
+{
+    evaluator::evaluator(symbol_bag& bag, const target_info& target,
+            const std::map<std::string, expression*>& evaluated_initializers)
+        : bag(bag), target(target), evaluated_initializers(evaluated_initializers)
+    {
+    }
+
+    std::optional<constant_value> evaluator::evaluate(expression& subject)
+    {
+        if (auto *literal_expression = subject.is_literal())
+        {
+            return evaluate_literal(*literal_expression);
+        }
+        else if (auto *designator = subject.is_designator())
+        {
+            if (auto *named = designator->is_named())
+            {
+                return evaluate_named(*named);
+            }
+        }
+        else if (auto *unary = subject.is_unary())
+        {
+            return evaluate_unary(*unary);
+        }
+        else if (auto *binary = subject.is_binary())
+        {
+            return evaluate_binary(*binary);
+        }
+        else if (auto *cast = subject.is_cast())
+        {
+            return evaluate_cast(*cast);
+        }
+        else if (auto *traits = subject.is_traits())
+        {
+            return evaluate_traits(*traits);
+        }
+        else if (auto *record_constructor = subject.is_record_constructor())
+        {
+            for (const field_initializer& field_initializer : record_constructor->field_initializers)
+            {
+                if (!evaluate(field_initializer.value()))
+                {
+                    return std::nullopt;
+                }
+            }
+            return constant_value{ compound_constant{} };
+        }
+        else if (auto *array_constructor = subject.is_array_constructor())
+        {
+            for (expression *element : array_constructor->elements)
+            {
+                if (!evaluate(*element))
+                {
+                    return std::nullopt;
+                }
+            }
+            return constant_value{ compound_constant{} };
+        }
+        return std::nullopt;
+    }
+
+    std::optional<constant_value> evaluator::evaluate_literal(literal_expression& subject)
+    {
+        type decoration = subject.type_decoration;
+
+        if (is_primitive_type(decoration, "Int"))
+        {
+            return constant_value{ static_cast<literal<std::int32_t>&>(subject).value };
+        }
+        if (is_primitive_type(decoration, "Word"))
+        {
+            return constant_value{ static_cast<literal<std::uint32_t>&>(subject).value };
+        }
+        if (is_primitive_type(decoration, "Float"))
+        {
+            return constant_value{ static_cast<literal<double>&>(subject).value };
+        }
+        if (is_primitive_type(decoration, "Bool"))
+        {
+            return constant_value{ static_cast<literal<bool>&>(subject).value };
+        }
+        if (is_primitive_type(decoration, "Char"))
+        {
+            return constant_value{ static_cast<literal<unsigned char>&>(subject).value };
+        }
+        if (is_primitive_type(decoration, "Pointer"))
+        {
+            return constant_value{ std::nullptr_t{} };
+        }
+        return std::nullopt;
+    }
+
+    std::optional<constant_value> evaluator::evaluate_named(named_expression& subject)
+    {
+        auto symbol = this->bag.lookup(subject.name);
+
+        if (symbol == nullptr)
+        {
+            return std::nullopt;
+        }
+        auto variable = symbol->is_variable();
+
+        if (variable == nullptr
+                || resolve_aliases(variable->symbol).get<constant_type>() == nullptr)
+        {
+            return std::nullopt;
+        }
+        auto initializer = this->evaluated_initializers.find(subject.name);
+
+        return initializer == this->evaluated_initializers.end()
+            ? std::nullopt
+            : evaluate(*initializer->second);
+    }
+
+    std::optional<constant_value> evaluator::evaluate_unary(unary_expression& subject)
+    {
+        if (subject.operation() == unary_operator::reference)
+        {
+            // The address of a module-level entity is a compile-time
+            // constant.  The caller (type analysis) validates the context.
+            return constant_value{ std::nullptr_t{} };
+        }
+        auto operand = evaluate(subject.operand());
+
+        if (!operand)
+        {
+            return std::nullopt;
+        }
+        if (subject.operation() == unary_operator::minus)
+        {
+            return std::visit([](auto&& value) -> std::optional<constant_value> {
+                using T = std::decay_t<decltype(value)>;
+
+                if constexpr (std::is_same_v<T, std::int32_t>)
+                {
+                    return value == std::numeric_limits<std::int32_t>::min()
+                        ? std::nullopt
+                        : std::make_optional<constant_value>(constant_value{ -value });
+                }
+                if constexpr (std::is_same_v<T, double>)
+                {
+                    return constant_value{ -value };
+                }
+                return std::nullopt;
+            }, operand.value());
+        }
+        if (subject.operation() == unary_operator::negation)
+        {
+            return std::visit([](auto v) -> std::optional<constant_value> {
+                using T = std::decay_t<decltype(v)>;
+
+                if constexpr (std::is_same_v<T, bool>)
+                {
+                    return constant_value{ !v };
+                }
+                else if constexpr (std::is_integral_v<T>)
+                {
+                    return constant_value{ ~v };
+                }
+                return std::nullopt;
+            }, operand.value());
+        }
+        return std::nullopt;
+    }
+
+    template<typename T>
+    static std::optional<T> add_overflow(T lhs, T rhs)
+    {
+        if constexpr (std::is_integral_v<T> && !std::is_same_v<T, bool>)
+        {
+            T result;
+            return __builtin_add_overflow(lhs, rhs, &result)
+                ? std::nullopt
+                : std::make_optional<T>(result);
+        }
+        return std::make_optional<T>(lhs + rhs);
+    }
+
+    template<typename T>
+    static std::optional<T> sub_overflow(T lhs, T rhs)
+    {
+        if constexpr (std::is_integral_v<T> && !std::is_same_v<T, bool>)
+        {
+            T result;
+            return __builtin_sub_overflow(lhs, rhs, &result)
+                ? std::nullopt
+                : std::make_optional<T>(result);
+        }
+        return std::make_optional<T>(lhs - rhs);
+    }
+
+    template<typename T>
+    static std::optional<T> mul_overflow(T lhs, T rhs)
+    {
+        if constexpr (std::is_integral_v<T> && !std::is_same_v<T, bool>)
+        {
+            T result;
+            return __builtin_mul_overflow(lhs, rhs, &result)
+                ? std::nullopt
+                : std::make_optional<T>(result);
+        }
+        return std::make_optional<T>(lhs * rhs);
+    }
+
+    template<typename T>
+    static std::optional<constant_value> evaluate_operation(binary_operator op, T lhs, T rhs)
+    {
+        if constexpr (std::is_same_v<T, std::nullptr_t>
+                || std::is_same_v<T, compound_constant>)
+        {
+            switch (op)
+            {
+                case binary_operator::equals:
+                    return constant_value{ true };
+                case binary_operator::not_equals:
+                    return constant_value{ false };
+                default:
+                    return std::nullopt;
+            }
+        }
+        else
+        {
+            switch (op)
+            {
+                case binary_operator::sum:
+                    if constexpr (std::is_arithmetic_v<T> && !std::is_same_v<T, bool>)
+                    {
+                        if (auto r = add_overflow(lhs, rhs))
+                        {
+                            return constant_value{ *r };
+                        }
+                    }
+                    return std::nullopt;
+                case binary_operator::subtraction:
+                    if constexpr (std::is_arithmetic_v<T> && !std::is_same_v<T, bool>)
+                    {
+                        if (auto r = sub_overflow(lhs, rhs))
+                        {
+                            return constant_value{ *r };
+                        }
+                    }
+                    return std::nullopt;
+                case binary_operator::multiplication:
+                    if constexpr (std::is_arithmetic_v<T> && !std::is_same_v<T, bool>)
+                    {
+                        if (auto r = mul_overflow(lhs, rhs))
+                        {
+                            return constant_value{ *r };
+                        }
+                    }
+                    return std::nullopt;
+                case binary_operator::division:
+                    if constexpr (std::is_arithmetic_v<T> && !std::is_same_v<T, bool>)
+                    {
+                        if (rhs != static_cast<T>(0))
+                        {
+                            return constant_value{ lhs / rhs };
+                        }
+                    }
+                    return std::nullopt;
+                case binary_operator::remainder:
+                    if constexpr (std::is_integral_v<T> && !std::is_same_v<T, bool>)
+                    {
+                        if (rhs != static_cast<T>(0))
+                        {
+                            return constant_value{ lhs % rhs };
+                        }
+                    }
+                    return std::nullopt;
+                case binary_operator::disjunction:
+                    if constexpr (std::is_integral_v<T>)
+                    {
+                        return constant_value{ lhs | rhs };
+                    }
+                    return std::nullopt;
+                case binary_operator::conjunction:
+                    if constexpr (std::is_integral_v<T>)
+                    {
+                        return constant_value{ lhs & rhs };
+                    }
+                    return std::nullopt;
+                case binary_operator::exclusive_disjunction:
+                    if constexpr (std::is_integral_v<T>)
+                    {
+                        return constant_value{ lhs ^ rhs };
+                    }
+                    return std::nullopt;
+                case binary_operator::shift_left:
+                    if constexpr (std::is_integral_v<T> && !std::is_same_v<T, bool>)
+                    {
+                        if (rhs < 0 || static_cast<std::make_unsigned_t<T>>(rhs) >= std::numeric_limits<T>::digits)
+                        {
+                            return std::nullopt;
+                        }
+                        return constant_value{ lhs << rhs };
+                    }
+                    return std::nullopt;
+                case binary_operator::shift_right:
+                    if constexpr (std::is_integral_v<T>)
+                    {
+                        return constant_value{ lhs >> rhs };
+                    }
+                    return std::nullopt;
+                case binary_operator::equals:
+                    return constant_value{ lhs == rhs };
+                case binary_operator::not_equals:
+                    return constant_value{ lhs != rhs };
+                case binary_operator::less:
+                    if constexpr (std::is_arithmetic_v<T> && !std::is_same_v<T, bool>)
+                    {
+                        return constant_value{ lhs < rhs };
+                    }
+                    return std::nullopt;
+                case binary_operator::greater:
+                    if constexpr (std::is_arithmetic_v<T> && !std::is_same_v<T, bool>)
+                    {
+                        return constant_value{ lhs > rhs };
+                    }
+                    return std::nullopt;
+                case binary_operator::less_equal:
+                    if constexpr (std::is_arithmetic_v<T> && !std::is_same_v<T, bool>)
+                    {
+                        return constant_value{ lhs <= rhs };
+                    }
+                    return std::nullopt;
+                case binary_operator::greater_equal:
+                    if constexpr (std::is_arithmetic_v<T> && !std::is_same_v<T, bool>)
+                    {
+                        return constant_value{ lhs >= rhs };
+                    }
+                    return std::nullopt;
+                default:
+                    return std::nullopt;
+            }
+        }
+    }
+
+    std::optional<constant_value> evaluator::evaluate_binary(binary_expression& subject)
+    {
+        std::optional<constant_value> lhs = evaluate(subject.lhs());
+        std::optional<constant_value> rhs = evaluate(subject.rhs());
+
+        if (!lhs || !rhs || lhs->index() != rhs->index())
+        {
+            return std::nullopt;
+        }
+        return std::visit([this, &rhs, operation = subject.operation()](auto&& lhs_value) {
+            using T = std::decay_t<decltype(lhs_value)>;
+            auto rhs_value = std::get<T>(rhs.value());
+
+            return evaluate_operation<T>(operation, lhs_value, rhs_value);
+        }, lhs.value());
+    }
+
+    std::optional<constant_value> evaluator::evaluate_cast(cast_expression& subject)
+    {
+        if (auto value = evaluate(subject.value()))
+        {
+            return constant_value{ value.value() };
+        }
+        else
+        {
+            return std::nullopt;
+        }
+    }
+
+    std::optional<std::size_t> evaluator::evaluate_traits_size(const type& subject)
+    {
+        type resolved = resolve_underlying_type(subject);
+
+        if (is_primitive_type(resolved, "Int"))
+        {
+            return target.int_size;
+        }
+        else if (is_primitive_type(resolved, "Word"))
+        {
+            return target.word_size;
+        }
+        else if (is_primitive_type(resolved, "Char"))
+        {
+            return target.char_size;
+        }
+        else if (is_primitive_type(resolved, "Float"))
+        {
+            return target.float_size;
+        }
+        else if (is_primitive_type(resolved, "Pointer"))
+        {
+            return target.pointer_size;
+        }
+        else if (resolved.get<pointer_type>() != nullptr)
+        {
+            return target.pointer_size;
+        }
+        else if (auto array = resolved.get<array_type>())
+        {
+            if (auto element_size = evaluate_traits_size(array->base))
+            {
+                return array->size * element_size.value();
+            }
+        }
+        return std::nullopt;
+    }
+
+    std::optional<std::size_t> evaluator::evaluate_traits_alignment(const type& subject)
+    {
+        type resolved = resolve_underlying_type(subject);
+
+        if (is_primitive_type(resolved, "Int"))
+        {
+            return target.int_alignment;
+        }
+        if (is_primitive_type(resolved, "Word"))
+        {
+            return target.word_alignment;
+        }
+        if (is_primitive_type(resolved, "Char"))
+        {
+            return target.char_alignment;
+        }
+        if (is_primitive_type(resolved, "Float"))
+        {
+            return target.float_alignment;
+        }
+        if (is_primitive_type(resolved, "Pointer"))
+        {
+            return target.pointer_alignment;
+        }
+        if (resolved.get<pointer_type>() != nullptr)
+        {
+            return target.pointer_alignment;
+        }
+        if (auto array = resolved.get<array_type>())
+        {
+            // The alignment of the array equals that of its element.
+            return evaluate_traits_alignment(array->base);
+        }
+        if (auto record = resolved.get<record_type>())
+        {
+            // An empty record has alignment 1.
+            std::optional<std::size_t> by_field_alignment = std::accumulate(
+                std::begin(record->fields), std::end(record->fields), std::make_optional<std::size_t>(1),
+                [this](std::optional<std::size_t> max_alignment, auto& field) {
+                    std::optional<std::size_t> field_alignment = evaluate_traits_alignment(field.second);
+
+                    return field_alignment.has_value() && max_alignment.has_value()
+                        ? std::make_optional(std::max(field_alignment.value(), max_alignment.value()))
+                        : std::nullopt;
+                }
+            );
+            if (!by_field_alignment.has_value())
+            {
+                return by_field_alignment;
+            }
+            std::size_t max_alignment = by_field_alignment.value();
+
+            if (!record->base.empty())
+            {
+                if (auto base_alignment = evaluate_traits_alignment(record->base))
+                {
+                    max_alignment = std::max(base_alignment.value(), max_alignment);
+                }
+                else
+                {
+                    return std::nullopt;
+                }
+            }
+            return max_alignment;
+        }
+        return std::nullopt;
+    }
+
+    std::optional<constant_value> evaluator::evaluate_traits(traits_expression& subject)
+    {
+        if (subject.types.size() != 1)
+        {
+            return std::nullopt;
+        }
+        else if (subject.name.name() == "size")
+        {
+            if (auto size = evaluate_traits_size(subject.types.front()))
+            {
+                return constant_value{ static_cast<std::uint32_t>(size.value()) };
+            }
+        }
+        else if (subject.name.name() == "alignment")
+        {
+            if (auto alignment = evaluate_traits_alignment(subject.types.front()))
+            {
+                return constant_value{ static_cast<std::uint32_t>(alignment.value()) };
+            }
+        }
+        else if (subject.name.name() == "min")
+        {
+            type resolved = resolve_underlying_type(subject.types.front());
+
+            if (is_primitive_type(resolved, "Int"))
+            {
+                return constant_value{ std::numeric_limits<std::int32_t>::min() };
+            }
+            if (is_primitive_type(resolved, "Word"))
+            {
+                return constant_value{ static_cast<std::uint32_t>(0) };
+            }
+            if (is_primitive_type(resolved, "Char"))
+            {
+                return constant_value{ static_cast<unsigned char>(0) };
+            }
+            if (auto enumeration = resolved.get<enumeration_type>())
+            {
+                return constant_value{ 1 };
+            }
+        }
+        else if (subject.name.name() == "max")
+        {
+            type resolved = resolve_underlying_type(subject.types.front());
+
+            if (is_primitive_type(resolved, "Int"))
+            {
+                return constant_value{ std::numeric_limits<std::int32_t>::max() };
+            }
+            if (is_primitive_type(resolved, "Word"))
+            {
+                return constant_value{ std::numeric_limits<std::uint32_t>::max() };
+            }
+            if (is_primitive_type(resolved, "Char"))
+            {
+                return constant_value{ static_cast<unsigned char>(255) };
+            }
+            if (auto enumeration = resolved.get<enumeration_type>())
+            {
+                return constant_value{ static_cast<std::int32_t>(enumeration->members.size()) };
+            }
+        }
+        // #offset(T, field) stays in codegen - needs GCC record layout.
+        return std::nullopt;
+    }
+}