WasmUtil.hpp

Go to the documentation of this file.

#pragma once
 
#include "backend/WasmDSL.hpp"
#include <functional>
#include <mutable/catalog/Schema.hpp>
#include <mutable/IR/PhysicalOptimizer.hpp>
#include <mutable/parse/AST.hpp>
#include <mutable/util/concepts.hpp>
#include <optional>
#include <variant>
 
#include <mutable/util/macro.hpp>
 
 
namespace m {
 
namespace wasm {
 
// forward declarations
struct Environment;
template<bool IsGlobal> struct Buffer;
template<bool IsGlobal> struct buffer_load_proxy_t;
template<bool IsGlobal> struct buffer_store_proxy_t;
template<bool IsGlobal> struct buffer_swap_proxy_t;
 
 
/*======================================================================================================================
 * Declare SQL helper type for character sequences
 *====================================================================================================================*/
 
struct NChar : Ptr<Charx1>
{
    using primitive_type = NChar;
 
    private:
    bool can_be_null_;
    const CharacterSequence *type_;
 
    public:
    NChar(Ptr<Charx1> ptr, bool can_be_null, const CharacterSequence *type)
        : Ptr<Charx1>(ptr), can_be_null_(can_be_null), type_(type)
    { }
    NChar(Ptr<Charx1> ptr, bool can_be_null, std::size_t length, bool guarantees_terminating_nul)
        : Ptr<Charx1>(ptr)
        , can_be_null_(can_be_null)
        , type_(guarantees_terminating_nul ? Type::Get_Varchar(Type::TY_Scalar, length)
                                           : Type::Get_Char(Type::TY_Scalar, length))
    { }
 
    NChar(NChar&) = default;
    NChar(NChar&&) = default;
 
    NChar clone() const { return NChar(Ptr<Charx1>::clone(), can_be_null_, type_); }
 
    Ptr<Charx1> val() { return *this; }
 
    Ptr<Charx1> insist_not_null() {
        if (can_be_null())
            Wasm_insist(clone().not_null(), "must not be NULL");
        return val();
    }
 
    Boolx1 is_null() {
        if (can_be_null()) {
            return Ptr<Charx1>::is_null();
        } else {
            discard();
            return Boolx1(false);
        }
    }
    Boolx1 not_null() {
        if (can_be_null()) {
            return Ptr<Charx1>::not_null();
        } else {
            discard();
            return Boolx1(true);
        }
    }
 
    bool can_be_null() const { return can_be_null_; }
    std::size_t length() const { return type_->length; }
    uint64_t size_in_bytes() const { return type_->size() / 8; }
    bool guarantees_terminating_nul() const { return type_->is_varying; }
};
 
 
/*======================================================================================================================
 * Decimal
 *====================================================================================================================*/
 
template<signed_integral Base>
struct Decimal : Expr<Base>
{
    using expr_type = Expr<Base>;
    using arithmetic_type = Base;
 
    private:
    uint32_t scale_;
 
    public:
    Decimal(Base value, uint32_t scale) : expr_type(value), scale_(scale) {
        M_insist(scale != 0);
    }
 
    Decimal(expr_type value, uint32_t scale) : expr_type(value), scale_(scale) { }
 
    Decimal(Decimal &other) : Decimal(other.val(), other.scale_) { }
    Decimal(Decimal &&other) : Decimal(other.val(), other.scale_) { }
 
    static Decimal Scaled(expr_type value, uint32_t scale) {
        const arithmetic_type scaling_factor = powi(arithmetic_type(10), scale);
        return Decimal(value * scaling_factor, scale);
    }
 
 
    public:
    expr_type val() { return *this; }
 
    uint32_t scale() const { return scale_; }
 
    template<signed_integral To>
    Expr<To> to() { return val().template to<To>() / powi(To(10), To(scale_)); }
 
    Decimal clone() const { return Decimal(expr_type::clone(), scale_); }
 
 
    /*------------------------------------------------------------------------------------------------------------------
     * Unary operations
     *----------------------------------------------------------------------------------------------------------------*/
 
    Decimal operator~()
    requires false
    { M_unreachable("modulo division on decimals is not defined"); }
 
 
    /*------------------------------------------------------------------------------------------------------------------
     * Binary operations
     *----------------------------------------------------------------------------------------------------------------*/
 
    Decimal operator+(Decimal other) {
        if (this->scale_ == other.scale_)
            return Decimal(this->val() + other.val(), scale_); // fall back to regular integer arithmetic
 
        if (this->scale() > other.scale()) {
            const arithmetic_type scaling_factor = powi(arithmetic_type(10), this->scale() - other.scale());
            return Decimal(this->val() + (other * scaling_factor).val() , this->scale());
        } else {
            const arithmetic_type scaling_factor = powi(arithmetic_type(10), other.scale() - this->scale());
            return Decimal((*this * scaling_factor).val() + other.val() , other.scale());
        }
    }
 
    template<typename T>
    requires expr_convertible<T> and signed_integral<typename expr_t<T>::type>
    Decimal operator+(T &&other) { return Decimal(*this + Scaled(expr_t<T>(other), scale_)); }
 
    Decimal operator-(Decimal other) {
        if (this->scale_ == other.scale_)
            return Decimal(this->val() - other.val(), scale_); // fall back to regular integer arithmetic
 
        if (this->scale() > other.scale()) {
            const arithmetic_type scaling_factor = powi(arithmetic_type(10), this->scale() - other.scale());
            return Decimal(this->val() - (other * scaling_factor).val() , this->scale());
        } else {
            const arithmetic_type scaling_factor = powi(arithmetic_type(10), other.scale() - this->scale());
            return Decimal((*this * scaling_factor).val() - other.val() , other.scale());
        }
    }
 
    template<typename T>
    requires expr_convertible<T> and signed_integral<typename expr_t<T>::type>
    Decimal operator-(T &&other) { return Decimal(*this - Scaled(expr_t<T>(other), scale_)); }
 
    Decimal operator*(Decimal other) {
        uint32_t smaller_scale = this->scale();
        uint32_t higher_scale = other.scale();
        if (smaller_scale > higher_scale)
            std::swap(smaller_scale, higher_scale);
        M_insist(smaller_scale <= higher_scale);
        const arithmetic_type scaling_factor = powi(arithmetic_type(10), smaller_scale);
        return Decimal((this->val() * other.val()) / scaling_factor, higher_scale);
    }
 
    template<typename T>
    requires expr_convertible<T> and signed_integral<typename expr_t<T>::type>
    Decimal operator*(T &&other) { return Decimal(this->val() * expr_t<T>(other), scale()); }
 
    Decimal operator/(Decimal other) {
        const uint32_t scale_res = std::max(this->scale(), other.scale());
        const arithmetic_type scaling_factor = powi(arithmetic_type(10), scale_res + other.scale() - this->scale());
        return Decimal((this->val() * scaling_factor) / other.val(), scale_res);
    }
 
    template<typename T>
    requires expr_convertible<T> and signed_integral<typename expr_t<T>::type>
    Decimal operator/(T &&other) { return Decimal(this->val() / expr_t<T>(other), scale()); }
 
    template<typename T>
    requires false
    Decimal operator%(T&&) { M_unreachable("modulo division on decimals is not defined"); }
 
    template<typename T>
    requires false
    Decimal operator bitand(T&&) { M_unreachable("bitwise and on decimals is not defined"); }
 
    template<typename T>
    requires false
    Decimal operator bitor(T&&) { M_unreachable("bitwise or on decimals is not defined"); }
 
    template<typename T>
    requires false
    Decimal operator xor(T&&) { M_unreachable("exclusive or on decimals is not defined"); }
 
    template<typename T>
    requires false
    Decimal operator<<(T&&) { M_unreachable("shift left on decimals is not defined"); }
 
    template<typename T>
    requires false
    Decimal operator>>(T&&) { M_unreachable("shift right on decimals is not defined"); }
 
    template<typename T>
    requires false
    Decimal rotl(T&&) { M_unreachable("rotate left on decimals is not defined"); }
 
    template<typename T>
    requires false
    Decimal rotr(T&&) { M_unreachable("rotate right on decimals is not defined"); }
 
 
    friend std::ostream & operator<<(std::ostream &out, const Decimal &d) {
        return out << "Decimal: " << static_cast<const expr_type&>(d) << ", scale = " << d.scale_;
    }
 
    void dump(std::ostream &out) const { out << *this << std::endl; }
    void dump() const { dump(std::cerr); }
};
 
/*----------------------------------------------------------------------------------------------------------------------
 * Binary operations
 *--------------------------------------------------------------------------------------------------------------------*/
 
template<typename Base>
requires expr_convertible<Base> and signed_integral<typename expr_t<Base>::type>
Decimal<typename expr_t<Base>::type> operator+(Base &&left, Decimal<typename expr_t<Base>::type> right)
{
    return right + left;
}
 
template<typename Base>
requires expr_convertible<Base> and signed_integral<typename expr_t<Base>::type>
Decimal<typename expr_t<Base>::type> operator-(Base &&left, Decimal<typename expr_t<Base>::type> right)
{
    return Decimal<typename expr_t<Base>::type>::Scaled(expr_t<Base>(left), right.scale()) - right;
}
 
template<typename Base>
requires expr_convertible<Base> and signed_integral<typename expr_t<Base>::type>
Decimal<typename expr_t<Base>::type> operator*(Base &&left, Decimal<typename expr_t<Base>::type> right)
{
    return right * left;
}
 
template<typename Base>
requires expr_convertible<Base> and signed_integral<typename expr_t<Base>::type>
Decimal<typename expr_t<Base>::type> operator/(Base &&left, Decimal<typename expr_t<Base>::type> right)
{
    return Decimal<typename expr_t<Base>::type>(expr_t<Base>(left), 0) / right;
}
 
using Decimal32 = Decimal<int32_t>;
using Decimal64 = Decimal<int64_t>;
 
 
 
/*======================================================================================================================
 * Declare valid SQL types
 *====================================================================================================================*/
 
template<typename>
struct is_sql_type;
 
template<typename>
struct is_sql_addr_type;
 
#define SQL_TYPES_SCALAR(X) \
    X(_Boolx1) \
    X(_I8x1) \
    X(_I16x1) \
    X(_I32x1) \
    X(_I64x1) \
    X(_Floatx1) \
    X(_Doublex1) \
    X(NChar)
 
#define SQL_ADDR_TYPES_SCALAR(X) \
    X(Ptr<Boolx1>) \
    X(Ptr<I8x1>) \
    X(Ptr<I16x1>) \
    X(Ptr<I32x1>) \
    X(Ptr<I64x1>) \
    X(Ptr<Floatx1>) \
    X(Ptr<Doublex1>) \
    X(NChar)
 
#define SQL_TYPES(X) \
    SQL_TYPES_SCALAR(X) \
    X(_Boolx16) \
    X(_Boolx32) \
    X(_I8x16) \
    X(_I8x32) \
    X(_I16x8) \
    X(_I16x16) \
    X(_I16x32) \
    X(_I32x4) \
    X(_I32x8) \
    X(_I32x16) \
    X(_I32x32) \
    X(_I64x2) \
    X(_I64x4) \
    X(_I64x8) \
    X(_I64x16) \
    X(_I64x32) \
    X(_Floatx4) \
    X(_Floatx8) \
    X(_Floatx16) \
    X(_Floatx32) \
    X(_Doublex2) \
    X(_Doublex4) \
    X(_Doublex8) \
    X(_Doublex16) \
    X(_Doublex32)
 
#define SQL_ADDR_TYPES(X) \
    SQL_ADDR_TYPES_SCALAR(X) \
    X(Ptr<Boolx16>) \
    X(Ptr<Boolx32>) \
    X(Ptr<I8x16>) \
    X(Ptr<I8x32>) \
    X(Ptr<I16x8>) \
    X(Ptr<I16x16>) \
    X(Ptr<I16x32>) \
    X(Ptr<I32x4>) \
    X(Ptr<I32x8>) \
    X(Ptr<I32x16>) \
    X(Ptr<I32x32>) \
    X(Ptr<I64x2>) \
    X(Ptr<I64x4>) \
    X(Ptr<I64x8>) \
    X(Ptr<I64x16>) \
    X(Ptr<I64x32>) \
    X(Ptr<Floatx4>) \
    X(Ptr<Floatx8>) \
    X(Ptr<Floatx16>) \
    X(Ptr<Floatx32>) \
    X(Ptr<Doublex2>) \
    X(Ptr<Doublex4>) \
    X(Ptr<Doublex8>) \
    X(Ptr<Doublex16>) \
    X(Ptr<Doublex32>)
 
#define ADD_EXPR_SQL_TYPE(TYPE) template<> struct is_sql_type<TYPE>{};
SQL_TYPES(ADD_EXPR_SQL_TYPE)
#undef ADD_EXPR_SQL_TYPE
 
#define ADD_EXPR_SQL_ADDR_TYPE(TYPE) template<> struct is_sql_addr_type<TYPE>{};
SQL_ADDR_TYPES(ADD_EXPR_SQL_ADDR_TYPE)
#undef ADD_EXPR_SQL_ADDR_TYPE
 
template<typename T>
concept sql_type = requires { is_sql_type<T>{}; };
 
template<typename T>
concept sql_addr_type = requires { is_sql_addr_type<T>{}; };
 
using SQL_t = std::variant<
    std::monostate
#define ADD_TYPE(TYPE) , TYPE
    SQL_TYPES(ADD_TYPE)
#undef ADD_TYPE
>;
 
using SQL_addr_t = std::variant<
    std::monostate
#define ADD_TYPE(TYPE) , TYPE
    SQL_ADDR_TYPES(ADD_TYPE)
#undef ADD_TYPE
>;
 
template<typename T>
concept sql_boolean_type = sql_type<T> and boolean<typename T::type>;
 
using SQL_boolean_t = std::variant<std::monostate, _Boolx1, _Boolx16, _Boolx32>;
 
 
/*======================================================================================================================
 * Helper functions for SQL types
 *====================================================================================================================*/
 
inline void discard(SQL_t &variant)
{
    std::visit(overloaded {
        []<sql_type T>(T actual) -> void { actual.discard(); },
        [](std::monostate) -> void { M_unreachable("invalid variant"); },
    }, variant);
}
 
inline void discard(SQL_addr_t &variant)
{
    std::visit(overloaded {
        []<sql_addr_type T>(T actual) -> void { actual.discard(); },
        [](std::monostate) -> void { M_unreachable("invalid variant"); },
    }, variant);
}
 
template<sql_type To>
inline To convert(SQL_t &variant)
{
    using type = typename To::type;
    static constexpr std::size_t num_simd_lanes = To::num_simd_lanes;
 
    return std::visit(overloaded {
        [](auto actual) -> To requires requires { actual.template to<type, num_simd_lanes>(); } {
            return actual.template to<type, num_simd_lanes>();
        },
        [](NChar actual) -> NChar requires std::same_as<To, NChar> {
            return actual;
        },
        [](auto actual) -> To requires (not requires { actual.template to<type, num_simd_lanes>(); }) {
            M_unreachable("illegal conversion");
        },
        [](std::monostate) -> To { M_unreachable("invalid variant"); },
    }, variant);
}
 
inline bool can_be_null(const SQL_t &variant)
{
    return std::visit(overloaded {
        []<sql_type T>(const T &actual) -> bool { return actual.can_be_null(); },
        [](std::monostate) -> bool { M_unreachable("invalid variant"); },
    }, variant);
}
 
template<std::size_t L = 1>
inline Bool<L> is_null(SQL_t &variant)
{
    return std::visit(overloaded {
        []<sql_type T>(T actual) -> Bool<L> requires requires { { actual.is_null() } -> std::same_as<Bool<L>>; } {
            return actual.is_null();
        },
        []<sql_type T>(T actual) -> Bool<L> requires (not requires { { actual.is_null() } -> std::same_as<Bool<L>>; }) {
            M_unreachable("invalid type for given number of SIMD lanes");
        },
        [](std::monostate) -> Bool<L> { M_unreachable("invalid variant"); },
    }, variant);
}
 
template<std::size_t L = 1>
inline Bool<L> not_null(SQL_t &variant)
{
    return std::visit(overloaded {
        []<sql_type T>(T actual) -> Bool<L> requires requires { { actual.not_null() } -> std::same_as<Bool<L>>; } {
            return actual.not_null();
        },
        []<sql_type T>(T actual) -> Bool<L> requires (not requires { { actual.not_null() } -> std::same_as<Bool<L>>; }) {
            M_unreachable("invalid type for given number of SIMD lanes");
        },
        [](std::monostate) -> Bool<L> { M_unreachable("invalid variant"); },
    }, variant);
}
 
 
/*======================================================================================================================
 * ExprCompiler
 *====================================================================================================================*/
 
struct ExprCompiler : ast::ConstASTExprVisitor
{
    private:
    SQL_t intermediate_result_;
    const Environment &env_;
 
    public:
    ExprCompiler(const Environment &env) : env_(env) { }
 
    SQL_t compile(const m::ast::Expr &e) {
        (*this)(e);
        return std::move(intermediate_result_);
    }
    template<sql_type T>
    T compile(const m::ast::Expr &e) {
        (*this)(e);
        M_insist(std::holds_alternative<T>(intermediate_result_));
        return *std::get_if<T>(&intermediate_result_);
    }
 
    SQL_boolean_t compile(const cnf::CNF &cnf);
 
    template<sql_boolean_type T>
    T compile(const cnf::CNF &cnf) {
        auto result = compile(cnf);
        M_insist(std::holds_alternative<T>(result));
        return *std::get_if<T>(&result);
    }
 
    private:
    using ConstASTExprVisitor::operator();
    void operator()(const ast::ErrorExpr&) override;
    void operator()(const ast::Designator &op) override;
    void operator()(const ast::Constant &op) override;
    void operator()(const ast::UnaryExpr &op) override;
    void operator()(const ast::BinaryExpr &op) override;
    void operator()(const ast::FnApplicationExpr &op) override;
    void operator()(const ast::QueryExpr &op) override;
 
    SQL_t get() { return std::move(intermediate_result_); }
 
    template<sql_type T>
    T get() {
        M_insist(std::holds_alternative<T>(intermediate_result_));
        return *std::get_if<T>(&intermediate_result_);
    }
 
    void set(SQL_t &&value) {
        intermediate_result_.~SQL_t(); // destroy old
        new (&intermediate_result_) SQL_t(std::move(value)); // placement-new
    }
 
    template<sql_type T>
    void set(T &&value) { set(SQL_t(std::forward<T>(value))); }
};
 
 
/*======================================================================================================================
 * Environment
 *====================================================================================================================*/
 
struct Environment
{
    private:
    std::unordered_map<Schema::Identifier, SQL_t> exprs_;
    std::unordered_map<Schema::Identifier, SQL_addr_t> expr_addrs_;
    SQL_boolean_t predicate_;
 
    public:
    Environment() = default;
    Environment(const Environment&) = delete;
    Environment(Environment&&) = default;
 
    ~Environment() {
        for (auto &p : exprs_)
            discard(p.second);
        for (auto &p : expr_addrs_)
            discard(p.second);
        /* do not discard `predicate_` to make sure predication predicate is used if it was set */
    }
 
    /*----- Access methods -------------------------------------------------------------------------------------------*/
    bool has(const Schema::Identifier &id) const { return exprs_.find(id) != exprs_.end(); }
    bool has_addr(const Schema::Identifier &id) const { return expr_addrs_.find(id) != expr_addrs_.end(); }
    template<sql_type T>
    bool is(const Schema::Identifier &id) const {
        auto it = exprs_.find(id);
        M_insist(it != exprs_.end(), "identifier not found");
        return std::holds_alternative<T>(it->second);
    }
    template<sql_addr_type T>
    bool is_addr(Schema::Identifier id) const {
        auto it = expr_addrs_.find(id);
        M_insist(it != expr_addrs_.end(), "identifier not found");
        return std::holds_alternative<T>(it->second);
    }
    bool empty() const { return exprs_.empty() and expr_addrs_.empty(); }
 
    void clear() {
        for (auto &p : exprs_)
            discard(p.second);
        for (auto &p : expr_addrs_)
            discard(p.second);
        exprs_.clear();
        expr_addrs_.clear();
    }
 
    template<sql_type T>
    void add(Schema::Identifier id, T &&expr) {
        auto res = exprs_.emplace(std::move(id), std::forward<T>(expr));
        M_insist(res.second, "duplicate ID");
    }
    void add(Schema::Identifier id, SQL_t &&expr) {
        auto res = exprs_.emplace(std::move(id), std::move(expr));
        M_insist(res.second, "duplicate ID");
    }
 
    template<sql_addr_type T>
    void add_addr(Schema::Identifier id, T &&expr) {
        auto res = expr_addrs_.emplace(id, std::forward<T>(expr));
        M_insist(res.second, "duplicate ID");
    }
    void add_addr(Schema::Identifier id, SQL_addr_t &&expr) {
        auto res = expr_addrs_.emplace(id, std::move(expr));
        M_insist(res.second, "duplicate ID");
    }
 
    void add(const Environment &other) {
        for (auto &p : other.exprs_) {
            std::visit(overloaded {
                [](std::monostate) -> void { M_unreachable("invalid expression"); },
                [this, &p](auto &e) -> void { this->add(p.first, e.clone()); },
            }, p.second);
        }
        for (auto &p : other.expr_addrs_) {
            std::visit(overloaded {
                [](std::monostate) -> void { M_unreachable("invalid expression"); },
                [this, &p](auto &e) -> void { this->add_addr(p.first, e.clone()); },
            }, p.second);
        }
    }
    void add(Environment &&other) {
        this->exprs_.merge(other.exprs_);
        M_insist(other.exprs_.empty(), "duplicate ID not moved from other to this");
        this->expr_addrs_.merge(other.expr_addrs_);
        M_insist(other.expr_addrs_.empty(), "duplicate ID not moved from other to this");
    }
 
    SQL_t extract(const Schema::Identifier &id) {
        auto it = exprs_.find(id);
        M_insist(it != exprs_.end(), "identifier not found");
        auto nh = exprs_.extract(it);
        return std::move(nh.mapped());
    }
    template<sql_type T>
    T extract(const Schema::Identifier &id) {
        auto it = exprs_.find(id);
        M_insist(it != exprs_.end(), "identifier not found");
        auto nh = exprs_.extract(it);
        M_insist(std::holds_alternative<T>(nh.mapped()));
        return *std::get_if<T>(&nh.mapped());
    }
 
    SQL_addr_t extract_addr(const Schema::Identifier &id) {
        auto it = expr_addrs_.find(id);
        M_insist(it != expr_addrs_.end(), "identifier not found");
        auto nh = expr_addrs_.extract(it);
        return std::move(nh.mapped());
    }
    template<sql_addr_type T>
    T extract_addr(const Schema::Identifier &id) {
        auto it = expr_addrs_.find(id);
        M_insist(it != expr_addrs_.end(), "identifier not found");
        auto nh = expr_addrs_.extract(it);
        M_insist(std::holds_alternative<T>(nh.mapped()));
        return *std::get_if<T>(&nh.mapped());
    }
 
    SQL_t get(const Schema::Identifier &id) const {
        auto it = exprs_.find(id);
        M_insist(it != exprs_.end(), "identifier not found");
        return std::visit(overloaded {
            [](auto &e) -> SQL_t { return e.clone(); },
            [](std::monostate) -> SQL_t { M_unreachable("invalid expression"); },
        }, it->second);
    }
    template<sql_type T>
    T get(const Schema::Identifier &id) const {
        auto it = exprs_.find(id);
        M_insist(it != exprs_.end(), "identifier not found");
        M_insist(std::holds_alternative<T>(it->second));
        return std::get_if<T>(&it->second)->clone();
    }
 
    SQL_addr_t get_addr(const Schema::Identifier &id) const {
        auto it = expr_addrs_.find(id);
        M_insist(it != expr_addrs_.end(), "identifier not found");
        return std::visit(overloaded {
            [](auto &e) -> SQL_addr_t { return e.clone(); },
            [](std::monostate) -> SQL_addr_t { M_unreachable("invalid expression"); },
        }, it->second);
    }
    template<sql_addr_type T>
    T get_addr(const Schema::Identifier &id) const {
        auto it = expr_addrs_.find(id);
        M_insist(it != expr_addrs_.end(), "identifier not found");
        M_insist(std::holds_alternative<T>(it->second));
        return std::get_if<T>(&it->second)->clone();
    }
 
    SQL_t operator[](const Schema::Identifier &id) const { return get(id); }
 
 
    /*----- Expression and CNF compilation ---------------------------------------------------------------------------*/
    template<typename T>
    requires requires (ExprCompiler C, T &&t) { C.compile(std::forward<T>(t)); }
    auto compile(T &&t) const {
        ExprCompiler C(*this);
        return C.compile(std::forward<T>(t));
    }
    template<typename T, typename U>
    requires requires (ExprCompiler C, U &&u) { C.compile<T>(std::forward<U>(u)); }
    auto compile(U &&u) const {
        ExprCompiler C(*this);
        return C.compile<T>(std::forward<U>(u));
    }
 
    /*----- Predication ----------------------------------------------------------------------------------------------*/
    bool predicated() const { return not std::holds_alternative<std::monostate>(predicate_); }
 
    void add_predicate(SQL_boolean_t &&pred) {
        std::visit(overloaded {
            [](std::monostate) -> void { M_unreachable("invalid predicate"); },
            [this]<sql_boolean_type T>(T &&e) -> void { this->add_predicate<T>(std::forward<T>(e)); },
        }, std::forward<SQL_boolean_t>(pred));
    }
    template<sql_boolean_type T>
    void add_predicate(T &&pred) {
        if (predicated()) {
            auto old = extract_predicate<T>();
            new (&predicate_) SQL_boolean_t(old and std::forward<T>(pred)); // placement-new
        } else {
            new (&predicate_) SQL_boolean_t(std::forward<T>(pred)); // placement-new
        }
    }
    void add_predicate(const cnf::CNF &cnf) { add_predicate(compile(cnf)); }
 
    SQL_boolean_t extract_predicate() {
        M_insist(predicated(), "cannot access an undefined or already extracted predicate");
        auto tmp = std::move(predicate_);
        new (&predicate_) SQL_boolean_t(std::monostate()); // placement-new
        return tmp;
    }
    template<sql_boolean_type T>
    T extract_predicate() {
        M_insist(predicated(), "cannot access an undefined or already extracted predicate");
        M_insist(std::holds_alternative<T>(predicate_));
        auto tmp = *std::get_if<T>(&predicate_);
        predicate_.~SQL_boolean_t(); // destroy old
        new (&predicate_) SQL_boolean_t(std::monostate()); // placement-new
        return tmp;
    }
 
    SQL_boolean_t get_predicate() const {
        return std::visit(overloaded {
            [](const std::monostate&) -> SQL_boolean_t {
                M_unreachable("cannot access an undefined or already extracted predicate");
            },
            [](const auto &e) -> SQL_boolean_t { return e.clone(); },
        }, predicate_);
    }
    template<sql_boolean_type T>
    T get_predicate() const {
        M_insist(predicated(), "cannot access an undefined or already extracted predicate");
        M_insist(std::holds_alternative<T>(predicate_));
        return std::get_if<T>(&predicate_)->clone();
    }
 
    void dump(std::ostream &out) const;
    void dump() const;
};
 
 
/*======================================================================================================================
 * CodeGenContext
 *====================================================================================================================*/
 
struct Scope
{
    friend struct CodeGenContext;
 
    private:
    Environment inner_; 
    Environment *outer_; 
 
    Scope() = delete;
    Scope(Environment inner);
 
    Scope(const Scope&) = delete;
    Scope(Scope&&) = default;
 
    public:
    ~Scope();
 
    Environment extract();
};
 
struct CodeGenContext
{
    friend struct Scope;
 
    private:
    Environment *env_ = nullptr; 
    Global<U32x1> num_tuples_; 
    std::unordered_map<const char*, std::pair<uint32_t, NChar>> literals_; 
    std::size_t num_simd_lanes_ = 1;
    std::size_t num_simd_lanes_preferred_ = 1;
 
    public:
    CodeGenContext() = default;
    CodeGenContext(const CodeGenContext&) = delete;
 
    ~CodeGenContext() {
#ifdef M_ENABLE_SANITY_FIELDS
        num_tuples_.val().discard();  // artificial use of `num_tuples_` to silence diagnostics if unittests are executed
#endif
        for (auto &p : literals_)
            p.second.second.discard();
    }
 
    /*----- Thread-local instance ------------------------------------------------------------------------------------*/
    private:
    static thread_local std::unique_ptr<CodeGenContext> the_context_;
 
    public:
    static void Init() {
        M_insist(not the_context_, "must not have a context yet");
        the_context_ = std::make_unique<CodeGenContext>();
    }
    static void Dispose() {
        M_insist(bool(the_context_), "must have a context");
        the_context_ = nullptr;
    }
    static CodeGenContext & Get() {
        M_insist(bool(the_context_), "must have a context");
        return *the_context_;
    }
 
    Scope scoped_environment() { return Scope(Environment()); }
    Scope scoped_environment(Environment env) { return Scope(std::move(env)); }
 
    /*----- Access methods -------------------------------------------------------------------------------------------*/
    Environment & env() { M_insist(bool(env_)); return *env_; }
    const Environment & env() const { M_insist(bool(env_)); return *env_; }
 
    U32x1 num_tuples() const { return num_tuples_; }
    void set_num_tuples(U32x1 n) { num_tuples_ = n; }
    void inc_num_tuples(U32x1 n = U32x1(1)) { num_tuples_ += n; }
 
    void add_literal(const char *literal, uint32_t ptr) {
        auto [_, inserted] = literals_.emplace(
            std::piecewise_construct,
            std::forward_as_tuple(literal),
            std::forward_as_tuple(ptr, NChar(Ptr<Charx1>(U32x1(ptr)), false, strlen(literal) + 1, true))
        );
        M_insist(inserted);
    }
    uint32_t get_literal_raw_address(const char *literal) const {
        auto it = literals_.find(literal);
        M_insist(it != literals_.end(), "unknown literal");
        return it->second.first;
    }
    NChar get_literal_address(const char *literal) const {
        auto it = literals_.find(literal);
        M_insist(it != literals_.end(), "unknown literal");
        return it->second.second.clone();
    }
 
    std::size_t num_simd_lanes() const { return num_simd_lanes_; }
    void set_num_simd_lanes(std::size_t n) { num_simd_lanes_ = n; }
 
    std::size_t num_simd_lanes_preferred() const { return num_simd_lanes_preferred_; }
    void update_num_simd_lanes_preferred(std::size_t n) {
        num_simd_lanes_preferred_ = std::max(num_simd_lanes_preferred_, n);
    }
};
 
inline Scope::Scope(Environment inner)
    : inner_(std::move(inner))
{
    outer_ = std::exchange(CodeGenContext::Get().env_, &inner_);
}
 
inline Scope::~Scope()
{
    CodeGenContext::Get().env_ = outer_;
}
 
inline Environment Scope::extract()
{
    CodeGenContext::Get().env_ = outer_;
    return std::move(inner_);
}
 
 
/*======================================================================================================================
 * compile data layout
 *====================================================================================================================*/
 
template<VariableKind Kind>
std::tuple<Block, Block, Block>
compile_store_sequential(const Schema &tuple_value_schema, const Schema &tuple_addr_schema, Ptr<void> base_address,
                         const storage::DataLayout &layout, std::size_t num_simd_lanes, const Schema &layout_schema,
                         Variable<uint32_t, Kind, false> &tuple_id);
 
template<VariableKind Kind>
std::tuple<Block, Block, Block>
compile_store_sequential_single_pass(const Schema &tuple_value_schema, const Schema &tuple_addr_schema,
                                     Ptr<void> base_address, const storage::DataLayout &layout,
                                     std::size_t num_simd_lanes, const Schema &layout_schema,
                                     Variable<uint32_t, Kind, false> &tuple_id);
 
template<VariableKind Kind>
std::tuple<Block, Block, Block>
compile_load_sequential(const Schema &tuple_value_schema, const Schema &tuple_addr_schema, Ptr<void> base_address,
                        const storage::DataLayout &layout, std::size_t num_simd_lanes, const Schema &layout_schema,
                        Variable<uint32_t, Kind, false> &tuple_id);
 
void compile_store_point_access(const Schema &tuple_value_schema, const Schema &tuple_addr_schema,
                                Ptr<void> base_address, const storage::DataLayout &layout, const Schema &layout_schema,
                                U32x1 tuple_id);
 
void compile_load_point_access(const Schema &tuple_value_schema, const Schema &tuple_addr_schema,
                               Ptr<void> base_address, const storage::DataLayout &layout, const Schema &layout_schema,
                               U32x1 tuple_id);
 
 
/*======================================================================================================================
 * Buffer
 *====================================================================================================================*/
 
template<bool IsGlobal>
class buffer_storage;
 
template<>
class buffer_storage<false> {};
 
template<>
class buffer_storage<true>
{
    friend struct Buffer<true>;
 
    Global<Ptr<void>> base_address_; 
    Global<U32x1> size_; 
    std::optional<Global<U32x1>> capacity_;
};
 
template<bool IsGlobal>
struct Buffer
{
    private:
    using param_t = std::optional<std::reference_wrapper<const Schema>>;
 
    std::reference_wrapper<const Schema> schema_; 
    storage::DataLayout layout_; 
    bool load_simdfied_ = false; 
    std::optional<Var<Ptr<void>>> base_address_; 
    std::optional<Var<U32x1>> size_; 
    std::optional<Var<U32x1>> capacity_; 
    std::optional<Var<Boolx1>> first_iteration_; 
    buffer_storage<IsGlobal> storage_; 
    setup_t setup_; 
    pipeline_t pipeline_; 
    teardown_t teardown_; 
    mutable std::optional<FunctionProxy<void(void*, uint32_t)>> resume_pipeline_;
 
    public:
    Buffer(const Schema &schema, const storage::DataLayoutFactory &factory, bool load_simdfied = false,
           std::size_t num_tuples = 0, setup_t setup = setup_t::Make_Without_Parent(),
           pipeline_t pipeline = pipeline_t(), teardown_t teardown = teardown_t::Make_Without_Parent());
 
    Buffer(const Buffer&) = delete;
    Buffer(Buffer&&) = default;
 
    ~Buffer();
 
    Buffer & operator=(Buffer&&) = default;
 
    const Schema & schema() const { return schema_; }
    const storage::DataLayout & layout() const { return layout_; }
    Ptr<void> base_address() const {
        if constexpr (IsGlobal) {
            return base_address_ ? base_address_->val() : storage_.base_address_.val(); // since global may be outdated
        } else {
            M_insist(bool(base_address_));
            return *base_address_;
        }
    }
    U32x1 size() const {
        if constexpr (IsGlobal) {
            return size_ ? size_->val() : storage_.size_.val(); // since global may be outdated
        } else {
            M_insist(bool(size_));
            return *size_;
        }
    }
 
    buffer_load_proxy_t<IsGlobal> create_load_proxy(param_t tuple_value_schema = param_t(),
                                                    param_t tuple_addr_schema = param_t()) const;
    buffer_store_proxy_t<IsGlobal> create_store_proxy(param_t tuple_schema = param_t()) const;
    buffer_swap_proxy_t<IsGlobal> create_swap_proxy(param_t tuple_schema = param_t()) const;
 
    void setup();
    void teardown();
 
    void setup_base_address() requires IsGlobal {
        M_insist(not base_address_, "must not call `setup_base_address()` twice");
        if (not layout_.is_finite()) {
            M_insist(bool(storage_.capacity_));
            Wasm_insist(*storage_.capacity_ != 0U, "buffer must be already allocated");
        }
        base_address_.emplace(storage_.base_address_);
    }
    void teardown_base_address() requires IsGlobal {
        M_insist(bool(base_address_), "must call `setup_base_address()` before");
        base_address_.reset();
    }
 
    void resume_pipeline(param_t tuple_value_schema = param_t(), param_t tuple_addr_schema = param_t()) const;
    void resume_pipeline_inline(param_t tuple_value_schema = param_t(), param_t tuple_addr_schema = param_t()) const;
 
    void execute_pipeline(setup_t setup, pipeline_t pipeline, teardown_t teardown,
                          param_t tuple_value_schema = param_t(), param_t tuple_addr_schema = param_t()) const;
    void execute_pipeline_inline(setup_t setup, pipeline_t pipeline, teardown_t teardown,
                                 param_t tuple_value_schema = param_t(), param_t tuple_addr_schema = param_t()) const;
 
    void consume();
};
 
using LocalBuffer = Buffer<false>;
using GlobalBuffer = Buffer<true>;
 
 
/*======================================================================================================================
 * buffer accesses
 *====================================================================================================================*/
 
template<bool IsGlobal>
struct buffer_load_proxy_t
{
    friend struct Buffer<IsGlobal>;
 
    private:
    std::reference_wrapper<const Buffer<IsGlobal>> buffer_; 
    std::reference_wrapper<const Schema> value_schema_; 
    std::reference_wrapper<const Schema> addr_schema_; 
 
    buffer_load_proxy_t(const Buffer<IsGlobal> &buffer, const Schema &value_schema, const Schema &addr_schema)
        : buffer_(std::cref(buffer))
        , value_schema_(std::cref(value_schema))
        , addr_schema_(std::cref(addr_schema))
    { }
 
    public:
    buffer_load_proxy_t(const buffer_load_proxy_t&) = delete;
    buffer_load_proxy_t(buffer_load_proxy_t&&) = default;
 
    buffer_load_proxy_t & operator=(buffer_load_proxy_t&&) = default;
 
    const Schema & value_schema() const { return value_schema_; }
    const Schema & addr_schema() const { return addr_schema_; }
 
    void operator()(U32x1 tuple_id) {
        Wasm_insist(tuple_id.clone() < buffer_.get().size(), "tuple ID out of bounds");
        compile_load_point_access(value_schema_, addr_schema_, buffer_.get().base_address(), buffer_.get().layout(),
                                  buffer_.get().schema(), tuple_id);
    }
};
 
template<bool IsGlobal>
struct buffer_store_proxy_t
{
    friend struct Buffer<IsGlobal>;
 
    private:
    std::reference_wrapper<const Buffer<IsGlobal>> buffer_; 
    std::reference_wrapper<const Schema> schema_; 
 
    buffer_store_proxy_t(const Buffer<IsGlobal> &buffer, const Schema &schema)
        : buffer_(std::cref(buffer))
        , schema_(std::cref(schema))
    { }
 
    public:
    buffer_store_proxy_t(const buffer_store_proxy_t&) = delete;
    buffer_store_proxy_t(buffer_store_proxy_t&&) = default;
 
    buffer_store_proxy_t & operator=(buffer_store_proxy_t&&) = default;
 
    const Schema & schema() const { return schema_; }
 
    void operator()(U32x1 tuple_id) {
        static Schema empty_schema;
        Wasm_insist(tuple_id.clone() < buffer_.get().size(), "tuple ID out of bounds");
        compile_store_point_access(schema_, empty_schema, buffer_.get().base_address(), buffer_.get().layout(),
                                   buffer_.get().schema(), tuple_id);
    }
};
 
template<bool IsGlobal>
struct buffer_swap_proxy_t
{
    friend struct Buffer<IsGlobal>;
 
    private:
    std::reference_wrapper<const Buffer<IsGlobal>> buffer_; 
    std::reference_wrapper<const Schema> schema_; 
 
    buffer_swap_proxy_t(const Buffer<IsGlobal> &buffer, const Schema &schema)
        : buffer_(std::cref(buffer))
        , schema_(std::cref(schema))
    { }
 
    public:
    const Schema & schema() const { return schema_; }
 
    void operator()(U32x1 first, U32x1 second);
    void operator()(U32x1 first, U32x1 second, const Environment &env_first);
    void operator()(U32x1 first, U32x1 second, const Environment &env_first, const Environment &env_second);
};
 
 
/*======================================================================================================================
 * bit operations
 *====================================================================================================================*/
 
template<typename T, std::size_t L>
requires integral<typename T::type> and (T::num_simd_lanes == L)
void setbit(Ptr<T> bytes, Bool<L> value, uint8_t n)
{
    *bytes ^= (-value.template to<typename T::type>() xor *bytes.clone()) bitand T(1 << n);
}
template<typename T, std::size_t L>
requires integral<typename T::type> and (T::num_simd_lanes == L)
void setbit(Ptr<T> bytes, Bool<L> value, T mask)
{
    *bytes ^= (-value.template to<typename T::type>() xor *bytes.clone()) bitand mask;
}
 
 
/*======================================================================================================================
 * string comparison
 *====================================================================================================================*/
 
enum cmp_op
{
    EQ, NE, LT, LE, GT, GE
};
 
_I32x1 strncmp(NChar left, NChar right, U32x1 len, bool reverse = false);
_I32x1 strcmp(NChar left, NChar right, bool reverse = false);
_Boolx1 strncmp(NChar left, NChar right, U32x1 len, cmp_op op, bool reverse = false);
_Boolx1 strcmp(NChar left, NChar right, cmp_op op, bool reverse = false);
 
 
/*======================================================================================================================
 * string copy
 *====================================================================================================================*/
 
Ptr<Charx1> strncpy(Ptr<Charx1> dst, Ptr<Charx1> src, U32x1 count);
 
 
/*======================================================================================================================
 * SQL LIKE
 *====================================================================================================================*/
 
_Boolx1 like(NChar str, NChar pattern, const char escape_char = '\\');
_Boolx1 like_contains(NChar str, const ThreadSafePooledString &pattern);
_Boolx1 like_prefix(NChar str, const ThreadSafePooledString &pattern);
_Boolx1 like_suffix(NChar str, const ThreadSafePooledString &pattern);
 
 
/*======================================================================================================================
 * signum and comparator
 *====================================================================================================================*/
 
template<typename T>
requires arithmetic<typename T::type>
T signum(T value)
{
    using type = typename T::type;
    return (value.clone() > type(0)).template to<type>() - (value < type(0)).template to<type>();
}
 
template<bool Predicated>
I32x1 compare(const Environment &env_left, const Environment &env_right,
              const std::vector<SortingOperator::order_type> &order);
 
 
/*======================================================================================================================
 * explicit instantiation declarations
 *====================================================================================================================*/
 
template void Environment::add_predicate(_Boolx1 &&);
template void Environment::add_predicate(_Boolx16&&);
template void Environment::add_predicate(_Boolx32&&);
template _Boolx1  Environment::extract_predicate();
template _Boolx16 Environment::extract_predicate();
template _Boolx32 Environment::extract_predicate();
template _Boolx1  Environment::get_predicate() const;
template _Boolx16 Environment::get_predicate() const;
template _Boolx32 Environment::get_predicate() const;
extern template std::tuple<Block, Block, Block> compile_store_sequential(
    const Schema&, const Schema&, Ptr<void>, const storage::DataLayout&, std::size_t, const Schema&, Var<U32x1>&
);
extern template std::tuple<Block, Block, Block> compile_store_sequential(
    const Schema&, const Schema&, Ptr<void>, const storage::DataLayout&, std::size_t, const Schema&, Global<U32x1>&
);
extern template std::tuple<Block, Block, Block> compile_store_sequential(
    const Schema&, const Schema&, Ptr<void>, const storage::DataLayout&, std::size_t, const Schema&,
    Variable<uint32_t, VariableKind::Param, false>&
);
extern template std::tuple<Block, Block, Block> compile_store_sequential_single_pass(
    const Schema&, const Schema&, Ptr<void>, const storage::DataLayout&, std::size_t, const Schema&, Var<U32x1>&
);
extern template std::tuple<Block, Block, Block> compile_store_sequential_single_pass(
    const Schema&, const Schema&, Ptr<void>, const storage::DataLayout&, std::size_t, const Schema&, Global<U32x1>&
);
extern template std::tuple<Block, Block, Block> compile_store_sequential_single_pass(
    const Schema&, const Schema&, Ptr<void>, const storage::DataLayout&, std::size_t, const Schema&,
    Variable<uint32_t, VariableKind::Param, false>&
);
extern template std::tuple<Block, Block, Block> compile_load_sequential(
    const Schema&, const Schema&, Ptr<void>, const storage::DataLayout&, std::size_t, const Schema&, Var<U32x1>&
);
extern template std::tuple<Block, Block, Block> compile_load_sequential(
    const Schema&, const Schema&, Ptr<void>, const storage::DataLayout&, std::size_t, const Schema&, Global<U32x1>&
);
extern template std::tuple<Block, Block, Block> compile_load_sequential(
    const Schema&, const Schema&, Ptr<void>, const storage::DataLayout&, std::size_t, const Schema&,
    Variable<uint32_t, VariableKind::Param, false>&
);
extern template struct Buffer<false>;
extern template struct Buffer<true>;
extern template struct buffer_swap_proxy_t<false>;
extern template struct buffer_swap_proxy_t<true>;
extern template I32x1 compare<false>(
    const Environment&, const Environment&, const std::vector<SortingOperator::order_type>&
);
extern template I32x1 compare<true>(
    const Environment&, const Environment&, const std::vector<SortingOperator::order_type>&
);
 
}
 
}