src/tint/builtin_table.cc

// Copyright 2021 The Tint Authors.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#include "src/tint/builtin_table.h"

#include <algorithm>
#include <limits>
#include <unordered_map>
#include <utility>

#include "src/tint/program_builder.h"
#include "src/tint/sem/atomic.h"
#include "src/tint/sem/depth_multisampled_texture.h"
#include "src/tint/sem/depth_texture.h"
#include "src/tint/sem/external_texture.h"
#include "src/tint/sem/multisampled_texture.h"
#include "src/tint/sem/pipeline_stage_set.h"
#include "src/tint/sem/sampled_texture.h"
#include "src/tint/sem/storage_texture.h"
#include "src/tint/utils/hash.h"
#include "src/tint/utils/map.h"
#include "src/tint/utils/math.h"
#include "src/tint/utils/scoped_assignment.h"

namespace tint {
namespace {

// Forward declarations
struct OverloadInfo;
class Matchers;
class NumberMatcher;
class TypeMatcher;

/// A special type that matches all TypeMatchers
class Any final : public Castable<Any, sem::Type> {
  public:
    Any() = default;
    ~Any() override = default;

    // Stub implementations for sem::Type conformance.
    size_t Hash() const override { return 0; }
    bool Equals(const sem::Type&) const override { return false; }
    std::string FriendlyName(const SymbolTable&) const override { return "<any>"; }
};

/// Number is an 32 bit unsigned integer, which can be in one of three states:
/// * Invalid - Number has not been assigned a value
/// * Valid   - a fixed integer value
/// * Any     - matches any other non-invalid number
struct Number {
    static const Number any;
    static const Number invalid;

    /// Constructed as a valid number with the value v
    explicit Number(uint32_t v) : value_(v), state_(kValid) {}

    /// @returns the value of the number
    inline uint32_t Value() const { return value_; }

    /// @returns the true if the number is valid
    inline bool IsValid() const { return state_ == kValid; }

    /// @returns the true if the number is any
    inline bool IsAny() const { return state_ == kAny; }

    /// Assignment operator.
    /// The number becomes valid, with the value n
    inline Number& operator=(uint32_t n) {
        value_ = n;
        state_ = kValid;
        return *this;
    }

  private:
    enum State {
        kInvalid,
        kValid,
        kAny,
    };

    constexpr explicit Number(State state) : state_(state) {}

    uint32_t value_ = 0;
    State state_ = kInvalid;
};

const Number Number::any{Number::kAny};
const Number Number::invalid{Number::kInvalid};

/// ClosedState holds the state of the open / closed numbers and types.
/// Used by the MatchState.
class ClosedState {
  public:
    explicit ClosedState(ProgramBuilder& b) : builder(b) {}

    /// If the type with index `idx` is open, then it is closed with type `ty` and
    /// Type() returns true. If the type is closed, then `Type()` returns true iff
    /// it is equal to `ty`.
    bool Type(uint32_t idx, const sem::Type* ty) {
        auto res = types_.emplace(idx, ty);
        return res.second || res.first->second == ty;
    }

    /// If the number with index `idx` is open, then it is closed with number
    /// `number` and Num() returns true. If the number is closed, then `Num()`
    /// returns true iff it is equal to `ty`.
    bool Num(uint32_t idx, Number number) {
        auto res = numbers_.emplace(idx, number.Value());
        return res.second || res.first->second == number.Value();
    }

    /// Type returns the closed type with index `idx`.
    /// An ICE is raised if the type is not closed.
    const sem::Type* Type(uint32_t idx) const {
        auto it = types_.find(idx);
        if (it == types_.end()) {
            TINT_ICE(Resolver, builder.Diagnostics())
                << "type with index " << idx << " is not closed";
            return nullptr;
        }
        TINT_ASSERT(Resolver, it != types_.end());
        return it->second;
    }

    /// Type returns the number type with index `idx`.
    /// An ICE is raised if the number is not closed.
    Number Num(uint32_t idx) const {
        auto it = numbers_.find(idx);
        if (it == numbers_.end()) {
            TINT_ICE(Resolver, builder.Diagnostics())
                << "number with index " << idx << " is not closed";
            return Number::invalid;
        }
        return Number(it->second);
    }

  private:
    ProgramBuilder& builder;
    std::unordered_map<uint32_t, const sem::Type*> types_;
    std::unordered_map<uint32_t, uint32_t> numbers_;
};

/// Index type used for matcher indices
using MatcherIndex = uint8_t;

/// Index value used for open types / numbers that do not have a constraint
constexpr MatcherIndex kNoMatcher = std::numeric_limits<MatcherIndex>::max();

/// MatchState holds the state used to match an overload.
class MatchState {
  public:
    MatchState(ProgramBuilder& b,
               ClosedState& c,
               const Matchers& m,
               const OverloadInfo& o,
               MatcherIndex const* matcher_indices)
        : builder(b), closed(c), matchers(m), overload(o), matcher_indices_(matcher_indices) {}

    /// The program builder
    ProgramBuilder& builder;
    /// The open / closed types and numbers
    ClosedState& closed;
    /// The type and number matchers
    Matchers const& matchers;
    /// The current overload being evaluated
    OverloadInfo const& overload;

    /// Type uses the next TypeMatcher from the matcher indices to match the type
    /// `ty`. If the type matches, the canonical expected type is returned. If the
    /// type `ty` does not match, then nullptr is returned.
    /// @note: The matcher indices are progressed on calling.
    const sem::Type* Type(const sem::Type* ty);

    /// Num uses the next NumMatcher from the matcher indices to match the number
    /// `num`. If the number matches, the canonical expected number is returned.
    /// If the number `num` does not match, then an invalid number is returned.
    /// @note: The matcher indices are progressed on calling.
    Number Num(Number num);

    /// @returns a string representation of the next TypeMatcher from the matcher
    /// indices.
    /// @note: The matcher indices are progressed on calling.
    std::string TypeName();

    /// @returns a string representation of the next NumberMatcher from the
    /// matcher indices.
    /// @note: The matcher indices are progressed on calling.
    std::string NumName();

  private:
    MatcherIndex const* matcher_indices_ = nullptr;
};

/// A TypeMatcher is the interface used to match an type used as part of an
/// overload's parameter or return type.
class TypeMatcher {
  public:
    /// Destructor
    virtual ~TypeMatcher() = default;

    /// Checks whether the given type matches the matcher rules, and returns the
    /// expected, canonicalized type on success.
    /// Match may close open types and numbers in state.
    /// @param type the type to match
    /// @returns the canonicalized type on match, otherwise nullptr
    virtual const sem::Type* Match(MatchState& state, const sem::Type* type) const = 0;

    /// @return a string representation of the matcher. Used for printing error
    /// messages when no overload is found.
    virtual std::string String(MatchState& state) const = 0;
};

/// A NumberMatcher is the interface used to match a number or enumerator used
/// as part of an overload's parameter or return type.
class NumberMatcher {
  public:
    /// Destructor
    virtual ~NumberMatcher() = default;

    /// Checks whether the given number matches the matcher rules.
    /// Match may close open numbers in state.
    /// @param number the number to match
    /// @returns true if the argument type is as expected.
    virtual Number Match(MatchState& state, Number number) const = 0;

    /// @return a string representation of the matcher. Used for printing error
    /// messages when no overload is found.
    virtual std::string String(MatchState& state) const = 0;
};

/// OpenTypeMatcher is a Matcher for an open type.
/// The OpenTypeMatcher will match against any type (so long as it is consistent
/// across all uses in the overload)
class OpenTypeMatcher : public TypeMatcher {
  public:
    /// Constructor
    explicit OpenTypeMatcher(uint32_t index) : index_(index) {}

    const sem::Type* Match(MatchState& state, const sem::Type* type) const override {
        if (type->Is<Any>()) {
            return state.closed.Type(index_);
        }
        return state.closed.Type(index_, type) ? type : nullptr;
    }

    std::string String(MatchState& state) const override;

  private:
    uint32_t index_;
};

/// OpenNumberMatcher is a Matcher for an open number.
/// The OpenNumberMatcher will match against any number (so long as it is
/// consistent for the overload)
class OpenNumberMatcher : public NumberMatcher {
  public:
    explicit OpenNumberMatcher(uint32_t index) : index_(index) {}

    Number Match(MatchState& state, Number number) const override {
        if (number.IsAny()) {
            return state.closed.Num(index_);
        }
        return state.closed.Num(index_, number) ? number : Number::invalid;
    }

    std::string String(MatchState& state) const override;

  private:
    uint32_t index_;
};

////////////////////////////////////////////////////////////////////////////////
// Binding functions for use in the generated builtin_table.inl
// TODO(bclayton): See if we can move more of this hand-rolled code to the
// template
////////////////////////////////////////////////////////////////////////////////
using TexelFormat = ast::TexelFormat;
using Access = ast::Access;
using StorageClass = ast::StorageClass;
using ParameterUsage = sem::ParameterUsage;
using PipelineStageSet = sem::PipelineStageSet;
using PipelineStage = ast::PipelineStage;

bool match_bool(const sem::Type* ty) {
    return ty->IsAnyOf<Any, sem::Bool>();
}

const sem::Bool* build_bool(MatchState& state) {
    return state.builder.create<sem::Bool>();
}

bool match_f32(const sem::Type* ty) {
    return ty->IsAnyOf<Any, sem::F32>();
}

const sem::I32* build_i32(MatchState& state) {
    return state.builder.create<sem::I32>();
}

bool match_i32(const sem::Type* ty) {
    return ty->IsAnyOf<Any, sem::I32>();
}

const sem::U32* build_u32(MatchState& state) {
    return state.builder.create<sem::U32>();
}

bool match_u32(const sem::Type* ty) {
    return ty->IsAnyOf<Any, sem::U32>();
}

const sem::F32* build_f32(MatchState& state) {
    return state.builder.create<sem::F32>();
}

bool match_vec(const sem::Type* ty, Number& N, const sem::Type*& T) {
    if (ty->Is<Any>()) {
        N = Number::any;
        T = ty;
        return true;
    }

    if (auto* v = ty->As<sem::Vector>()) {
        N = v->Width();
        T = v->type();
        return true;
    }
    return false;
}

const sem::Vector* build_vec(MatchState& state, Number N, const sem::Type* el) {
    return state.builder.create<sem::Vector>(el, N.Value());
}

template <int N>
bool match_vec(const sem::Type* ty, const sem::Type*& T) {
    if (ty->Is<Any>()) {
        T = ty;
        return true;
    }

    if (auto* v = ty->As<sem::Vector>()) {
        if (v->Width() == N) {
            T = v->type();
            return true;
        }
    }
    return false;
}

bool match_vec2(const sem::Type* ty, const sem::Type*& T) {
    return match_vec<2>(ty, T);
}

const sem::Vector* build_vec2(MatchState& state, const sem::Type* T) {
    return build_vec(state, Number(2), T);
}

bool match_vec3(const sem::Type* ty, const sem::Type*& T) {
    return match_vec<3>(ty, T);
}

const sem::Vector* build_vec3(MatchState& state, const sem::Type* T) {
    return build_vec(state, Number(3), T);
}

bool match_vec4(const sem::Type* ty, const sem::Type*& T) {
    return match_vec<4>(ty, T);
}

const sem::Vector* build_vec4(MatchState& state, const sem::Type* T) {
    return build_vec(state, Number(4), T);
}

bool match_mat(const sem::Type* ty, Number& M, Number& N, const sem::Type*& T) {
    if (ty->Is<Any>()) {
        M = Number::any;
        N = Number::any;
        T = ty;
        return true;
    }
    if (auto* m = ty->As<sem::Matrix>()) {
        M = m->columns();
        N = m->ColumnType()->Width();
        T = m->type();
        return true;
    }
    return false;
}

const sem::Matrix* build_mat(MatchState& state, Number N, Number M, const sem::Type* T) {
    auto* column_type = state.builder.create<sem::Vector>(T, M.Value());
    return state.builder.create<sem::Matrix>(column_type, N.Value());
}

bool match_array(const sem::Type* ty, const sem::Type*& T) {
    if (ty->Is<Any>()) {
        T = ty;
        return true;
    }

    if (auto* a = ty->As<sem::Array>()) {
        if (a->Count() == 0) {
            T = a->ElemType();
            return true;
        }
    }
    return false;
}

const sem::Array* build_array(MatchState& state, const sem::Type* el) {
    return state.builder.create<sem::Array>(el,
                                            /* count */ 0u,
                                            /* align */ 0u,
                                            /* size */ 0u,
                                            /* stride */ 0u,
                                            /* stride_implicit */ 0u);
}

bool match_ptr(const sem::Type* ty, Number& S, const sem::Type*& T, Number& A) {
    if (ty->Is<Any>()) {
        S = Number::any;
        T = ty;
        A = Number::any;
        return true;
    }

    if (auto* p = ty->As<sem::Pointer>()) {
        S = Number(static_cast<uint32_t>(p->StorageClass()));
        T = p->StoreType();
        A = Number(static_cast<uint32_t>(p->Access()));
        return true;
    }
    return false;
}

const sem::Pointer* build_ptr(MatchState& state, Number S, const sem::Type* T, Number& A) {
    return state.builder.create<sem::Pointer>(T, static_cast<ast::StorageClass>(S.Value()),
                                              static_cast<ast::Access>(A.Value()));
}

bool match_atomic(const sem::Type* ty, const sem::Type*& T) {
    if (ty->Is<Any>()) {
        T = ty;
        return true;
    }

    if (auto* a = ty->As<sem::Atomic>()) {
        T = a->Type();
        return true;
    }
    return false;
}

const sem::Atomic* build_atomic(MatchState& state, const sem::Type* T) {
    return state.builder.create<sem::Atomic>(T);
}

bool match_sampler(const sem::Type* ty) {
    if (ty->Is<Any>()) {
        return true;
    }
    return ty->Is([](const sem::Sampler* s) { return s->kind() == ast::SamplerKind::kSampler; });
}

const sem::Sampler* build_sampler(MatchState& state) {
    return state.builder.create<sem::Sampler>(ast::SamplerKind::kSampler);
}

bool match_sampler_comparison(const sem::Type* ty) {
    if (ty->Is<Any>()) {
        return true;
    }
    return ty->Is(
        [](const sem::Sampler* s) { return s->kind() == ast::SamplerKind::kComparisonSampler; });
}

const sem::Sampler* build_sampler_comparison(MatchState& state) {
    return state.builder.create<sem::Sampler>(ast::SamplerKind::kComparisonSampler);
}

bool match_texture(const sem::Type* ty, ast::TextureDimension dim, const sem::Type*& T) {
    if (ty->Is<Any>()) {
        T = ty;
        return true;
    }
    if (auto* v = ty->As<sem::SampledTexture>()) {
        if (v->dim() == dim) {
            T = v->type();
            return true;
        }
    }
    return false;
}

#define JOIN(a, b) a##b

#define DECLARE_SAMPLED_TEXTURE(suffix, dim)                                      \
    bool JOIN(match_texture_, suffix)(const sem::Type* ty, const sem::Type*& T) { \
        return match_texture(ty, dim, T);                                         \
    }                                                                             \
    const sem::SampledTexture* JOIN(build_texture_, suffix)(MatchState & state,   \
                                                            const sem::Type* T) { \
        return state.builder.create<sem::SampledTexture>(dim, T);                 \
    }

DECLARE_SAMPLED_TEXTURE(1d, ast::TextureDimension::k1d)
DECLARE_SAMPLED_TEXTURE(2d, ast::TextureDimension::k2d)
DECLARE_SAMPLED_TEXTURE(2d_array, ast::TextureDimension::k2dArray)
DECLARE_SAMPLED_TEXTURE(3d, ast::TextureDimension::k3d)
DECLARE_SAMPLED_TEXTURE(cube, ast::TextureDimension::kCube)
DECLARE_SAMPLED_TEXTURE(cube_array, ast::TextureDimension::kCubeArray)
#undef DECLARE_SAMPLED_TEXTURE

bool match_texture_multisampled(const sem::Type* ty,
                                ast::TextureDimension dim,
                                const sem::Type*& T) {
    if (ty->Is<Any>()) {
        T = ty;
        return true;
    }
    if (auto* v = ty->As<sem::MultisampledTexture>()) {
        if (v->dim() == dim) {
            T = v->type();
            return true;
        }
    }
    return false;
}

#define DECLARE_MULTISAMPLED_TEXTURE(suffix, dim)                                              \
    bool JOIN(match_texture_multisampled_, suffix)(const sem::Type* ty, const sem::Type*& T) { \
        return match_texture_multisampled(ty, dim, T);                                         \
    }                                                                                          \
    const sem::MultisampledTexture* JOIN(build_texture_multisampled_, suffix)(                 \
        MatchState & state, const sem::Type* T) {                                              \
        return state.builder.create<sem::MultisampledTexture>(dim, T);                         \
    }

DECLARE_MULTISAMPLED_TEXTURE(2d, ast::TextureDimension::k2d)
#undef DECLARE_MULTISAMPLED_TEXTURE

bool match_texture_depth(const sem::Type* ty, ast::TextureDimension dim) {
    if (ty->Is<Any>()) {
        return true;
    }
    return ty->Is([&](const sem::DepthTexture* t) { return t->dim() == dim; });
}

#define DECLARE_DEPTH_TEXTURE(suffix, dim)                                            \
    bool JOIN(match_texture_depth_, suffix)(const sem::Type* ty) {                    \
        return match_texture_depth(ty, dim);                                          \
    }                                                                                 \
    const sem::DepthTexture* JOIN(build_texture_depth_, suffix)(MatchState & state) { \
        return state.builder.create<sem::DepthTexture>(dim);                          \
    }

DECLARE_DEPTH_TEXTURE(2d, ast::TextureDimension::k2d)
DECLARE_DEPTH_TEXTURE(2d_array, ast::TextureDimension::k2dArray)
DECLARE_DEPTH_TEXTURE(cube, ast::TextureDimension::kCube)
DECLARE_DEPTH_TEXTURE(cube_array, ast::TextureDimension::kCubeArray)
#undef DECLARE_DEPTH_TEXTURE

bool match_texture_depth_multisampled_2d(const sem::Type* ty) {
    if (ty->Is<Any>()) {
        return true;
    }
    return ty->Is([&](const sem::DepthMultisampledTexture* t) {
        return t->dim() == ast::TextureDimension::k2d;
    });
}

sem::DepthMultisampledTexture* build_texture_depth_multisampled_2d(MatchState& state) {
    return state.builder.create<sem::DepthMultisampledTexture>(ast::TextureDimension::k2d);
}

bool match_texture_storage(const sem::Type* ty, ast::TextureDimension dim, Number& F, Number& A) {
    if (ty->Is<Any>()) {
        F = Number::any;
        A = Number::any;
        return true;
    }
    if (auto* v = ty->As<sem::StorageTexture>()) {
        if (v->dim() == dim) {
            F = Number(static_cast<uint32_t>(v->texel_format()));
            A = Number(static_cast<uint32_t>(v->access()));
            return true;
        }
    }
    return false;
}

#define DECLARE_STORAGE_TEXTURE(suffix, dim)                                                      \
    bool JOIN(match_texture_storage_, suffix)(const sem::Type* ty, Number& F, Number& A) {        \
        return match_texture_storage(ty, dim, F, A);                                              \
    }                                                                                             \
    const sem::StorageTexture* JOIN(build_texture_storage_, suffix)(MatchState & state, Number F, \
                                                                    Number A) {                   \
        auto format = static_cast<TexelFormat>(F.Value());                                        \
        auto access = static_cast<Access>(A.Value());                                             \
        auto* T = sem::StorageTexture::SubtypeFor(format, state.builder.Types());                 \
        return state.builder.create<sem::StorageTexture>(dim, format, access, T);                 \
    }

DECLARE_STORAGE_TEXTURE(1d, ast::TextureDimension::k1d)
DECLARE_STORAGE_TEXTURE(2d, ast::TextureDimension::k2d)
DECLARE_STORAGE_TEXTURE(2d_array, ast::TextureDimension::k2dArray)
DECLARE_STORAGE_TEXTURE(3d, ast::TextureDimension::k3d)
#undef DECLARE_STORAGE_TEXTURE

bool match_texture_external(const sem::Type* ty) {
    return ty->IsAnyOf<Any, sem::ExternalTexture>();
}

const sem::ExternalTexture* build_texture_external(MatchState& state) {
    return state.builder.create<sem::ExternalTexture>();
}

// Builtin types starting with a _ prefix cannot be declared in WGSL, so they
// can only be used as return types. Because of this, they must only match Any,
// which is used as the return type matcher.
bool match_modf_result(const sem::Type* ty) {
    return ty->Is<Any>();
}
bool match_modf_result_vec(const sem::Type* ty, Number& N) {
    if (!ty->Is<Any>()) {
        return false;
    }
    N = Number::any;
    return true;
}
bool match_frexp_result(const sem::Type* ty) {
    return ty->Is<Any>();
}
bool match_frexp_result_vec(const sem::Type* ty, Number& N) {
    if (!ty->Is<Any>()) {
        return false;
    }
    N = Number::any;
    return true;
}

struct NameAndType {
    std::string name;
    sem::Type* type;
};
const sem::Struct* build_struct(MatchState& state,
                                std::string name,
                                std::initializer_list<NameAndType> member_names_and_types) {
    uint32_t offset = 0;
    uint32_t max_align = 0;
    sem::StructMemberList members;
    for (auto& m : member_names_and_types) {
        uint32_t align = m.type->Align();
        uint32_t size = m.type->Size();
        offset = utils::RoundUp(align, offset);
        max_align = std::max(max_align, align);
        members.emplace_back(state.builder.create<sem::StructMember>(
            /* declaration */ nullptr,
            /* name */ state.builder.Sym(m.name),
            /* type */ m.type,
            /* index */ static_cast<uint32_t>(members.size()),
            /* offset */ offset,
            /* align */ align,
            /* size */ size));
        offset += size;
    }
    uint32_t size_without_padding = offset;
    uint32_t size_with_padding = utils::RoundUp(max_align, offset);
    return state.builder.create<sem::Struct>(
        /* declaration */ nullptr,
        /* name */ state.builder.Sym(name),
        /* members */ members,
        /* align */ max_align,
        /* size */ size_with_padding,
        /* size_no_padding */ size_without_padding);
}

const sem::Struct* build_modf_result(MatchState& state) {
    auto* f32 = state.builder.create<sem::F32>();
    return build_struct(state, "__modf_result", {{"fract", f32}, {"whole", f32}});
}
const sem::Struct* build_modf_result_vec(MatchState& state, Number& n) {
    auto* vec_f32 = state.builder.create<sem::Vector>(state.builder.create<sem::F32>(), n.Value());
    return build_struct(state, "__modf_result_vec" + std::to_string(n.Value()),
                        {{"fract", vec_f32}, {"whole", vec_f32}});
}
const sem::Struct* build_frexp_result(MatchState& state) {
    auto* f32 = state.builder.create<sem::F32>();
    auto* i32 = state.builder.create<sem::I32>();
    return build_struct(state, "__frexp_result", {{"sig", f32}, {"exp", i32}});
}
const sem::Struct* build_frexp_result_vec(MatchState& state, Number& n) {
    auto* vec_f32 = state.builder.create<sem::Vector>(state.builder.create<sem::F32>(), n.Value());
    auto* vec_i32 = state.builder.create<sem::Vector>(state.builder.create<sem::I32>(), n.Value());
    return build_struct(state, "__frexp_result_vec" + std::to_string(n.Value()),
                        {{"sig", vec_f32}, {"exp", vec_i32}});
}

/// ParameterInfo describes a parameter
struct ParameterInfo {
    /// The parameter usage (parameter name in definition file)
    const ParameterUsage usage;

    /// Pointer to a list of indices that are used to match the parameter type.
    /// The matcher indices index on Matchers::type and / or Matchers::number.
    /// These indices are consumed by the matchers themselves.
    /// The first index is always a TypeMatcher.
    MatcherIndex const* const matcher_indices;
};

/// OpenTypeInfo describes an open type
struct OpenTypeInfo {
    /// Name of the open type (e.g. 'T')
    const char* name;
    /// Optional type matcher constraint.
    /// Either an index in Matchers::type, or kNoMatcher
    const MatcherIndex matcher_index;
};

/// OpenNumberInfo describes an open number
struct OpenNumberInfo {
    /// Name of the open number (e.g. 'N')
    const char* name;
    /// Optional number matcher constraint.
    /// Either an index in Matchers::number, or kNoMatcher
    const MatcherIndex matcher_index;
};

/// OverloadInfo describes a single function overload
struct OverloadInfo {
    /// Total number of parameters for the overload
    const uint8_t num_parameters;
    /// Total number of open types for the overload
    const uint8_t num_open_types;
    /// Total number of open numbers for the overload
    const uint8_t num_open_numbers;
    /// Pointer to the first open type
    OpenTypeInfo const* const open_types;
    /// Pointer to the first open number
    OpenNumberInfo const* const open_numbers;
    /// Pointer to the first parameter
    ParameterInfo const* const parameters;
    /// Pointer to a list of matcher indices that index on Matchers::type and
    /// Matchers::number, used to build the return type. If the function has no
    /// return type then this is null
    MatcherIndex const* const return_matcher_indices;
    /// The pipeline stages that this overload can be used in
    PipelineStageSet supported_stages;
    /// True if the overload is marked as deprecated
    bool is_deprecated;
};

/// BuiltinInfo describes a builtin function
struct BuiltinInfo {
    /// Number of overloads of the builtin function
    const uint8_t num_overloads;
    /// Pointer to the start of the overloads for the function
    OverloadInfo const* const overloads;
};

#include "builtin_table.inl"

/// BuiltinPrototype describes a fully matched builtin function, which is
/// used as a lookup for building unique sem::Builtin instances.
struct BuiltinPrototype {
    /// Parameter describes a single parameter
    struct Parameter {
        /// Parameter type
        const sem::Type* const type;
        /// Parameter usage
        ParameterUsage const usage = ParameterUsage::kNone;
    };

    /// Hasher provides a hash function for the BuiltinPrototype
    struct Hasher {
        /// @param i the BuiltinPrototype to create a hash for
        /// @return the hash value
        inline std::size_t operator()(const BuiltinPrototype& i) const {
            size_t hash = utils::Hash(i.parameters.size());
            for (auto& p : i.parameters) {
                utils::HashCombine(&hash, p.type, p.usage);
            }
            return utils::Hash(hash, i.type, i.return_type, i.supported_stages, i.is_deprecated);
        }
    };

    sem::BuiltinType type = sem::BuiltinType::kNone;
    std::vector<Parameter> parameters;
    sem::Type const* return_type = nullptr;
    PipelineStageSet supported_stages;
    bool is_deprecated = false;
};

/// Equality operator for BuiltinPrototype
bool operator==(const BuiltinPrototype& a, const BuiltinPrototype& b) {
    if (a.type != b.type || a.supported_stages != b.supported_stages ||
        a.return_type != b.return_type || a.is_deprecated != b.is_deprecated ||
        a.parameters.size() != b.parameters.size()) {
        return false;
    }
    for (size_t i = 0; i < a.parameters.size(); i++) {
        auto& pa = a.parameters[i];
        auto& pb = b.parameters[i];
        if (pa.type != pb.type || pa.usage != pb.usage) {
            return false;
        }
    }
    return true;
}

/// Impl is the private implementation of the BuiltinTable interface.
class Impl : public BuiltinTable {
  public:
    explicit Impl(ProgramBuilder& builder);

    const sem::Builtin* Lookup(sem::BuiltinType builtin_type,
                               const std::vector<const sem::Type*>& args,
                               const Source& source) override;

  private:
    const sem::Builtin* Match(sem::BuiltinType builtin_type,
                              const OverloadInfo& overload,
                              const std::vector<const sem::Type*>& args,
                              int& match_score);

    MatchState Match(ClosedState& closed,
                     const OverloadInfo& overload,
                     MatcherIndex const* matcher_indices) const;

    void PrintOverload(std::ostream& ss,
                       const OverloadInfo& overload,
                       sem::BuiltinType builtin_type) const;

    ProgramBuilder& builder;
    Matchers matchers;
    std::unordered_map<BuiltinPrototype, sem::Builtin*, BuiltinPrototype::Hasher> builtins;
};

/// @return a string representing a call to a builtin with the given argument
/// types.
std::string CallSignature(ProgramBuilder& builder,
                          sem::BuiltinType builtin_type,
                          const std::vector<const sem::Type*>& args) {
    std::stringstream ss;
    ss << sem::str(builtin_type) << "(";
    {
        bool first = true;
        for (auto* arg : args) {
            if (!first) {
                ss << ", ";
            }
            first = false;
            ss << arg->UnwrapRef()->FriendlyName(builder.Symbols());
        }
    }
    ss << ")";

    return ss.str();
}

std::string OpenTypeMatcher::String(MatchState& state) const {
    return state.overload.open_types[index_].name;
}

std::string OpenNumberMatcher::String(MatchState& state) const {
    return state.overload.open_numbers[index_].name;
}

Impl::Impl(ProgramBuilder& b) : builder(b) {}

const sem::Builtin* Impl::Lookup(sem::BuiltinType builtin_type,
                                 const std::vector<const sem::Type*>& args,
                                 const Source& source) {
    // Candidate holds information about a mismatched overload that could be what
    // the user intended to call.
    struct Candidate {
        const OverloadInfo* overload;
        int score;
    };

    // The list of failed matches that had promise.
    std::vector<Candidate> candidates;

    auto& builtin = kBuiltins[static_cast<uint32_t>(builtin_type)];
    for (uint32_t o = 0; o < builtin.num_overloads; o++) {
        int match_score = 1000;
        auto& overload = builtin.overloads[o];
        if (auto* match = Match(builtin_type, overload, args, match_score)) {
            return match;
        }
        if (match_score > 0) {
            candidates.emplace_back(Candidate{&overload, match_score});
        }
    }

    // Sort the candidates with the most promising first
    std::stable_sort(candidates.begin(), candidates.end(),
                     [](const Candidate& a, const Candidate& b) { return a.score > b.score; });

    // Generate an error message
    std::stringstream ss;
    ss << "no matching call to " << CallSignature(builder, builtin_type, args) << std::endl;
    if (!candidates.empty()) {
        ss << std::endl;
        ss << candidates.size() << " candidate function" << (candidates.size() > 1 ? "s:" : ":")
           << std::endl;
        for (auto& candidate : candidates) {
            ss << "  ";
            PrintOverload(ss, *candidate.overload, builtin_type);
            ss << std::endl;
        }
    }
    builder.Diagnostics().add_error(diag::System::Resolver, ss.str(), source);
    return nullptr;
}

const sem::Builtin* Impl::Match(sem::BuiltinType builtin_type,
                                const OverloadInfo& overload,
                                const std::vector<const sem::Type*>& args,
                                int& match_score) {
    // Score wait for argument <-> parameter count matches / mismatches
    constexpr int kScorePerParamArgMismatch = -1;
    constexpr int kScorePerMatchedParam = 2;
    constexpr int kScorePerMatchedOpenType = 1;
    constexpr int kScorePerMatchedOpenNumber = 1;

    auto num_parameters = overload.num_parameters;
    auto num_arguments = static_cast<decltype(num_parameters)>(args.size());

    bool overload_matched = true;

    if (num_parameters != num_arguments) {
        match_score += kScorePerParamArgMismatch * (std::max(num_parameters, num_arguments) -
                                                    std::min(num_parameters, num_arguments));
        overload_matched = false;
    }

    ClosedState closed(builder);

    std::vector<BuiltinPrototype::Parameter> parameters;

    auto num_params = std::min(num_parameters, num_arguments);
    for (uint32_t p = 0; p < num_params; p++) {
        auto& parameter = overload.parameters[p];
        auto* indices = parameter.matcher_indices;
        auto* type = Match(closed, overload, indices).Type(args[p]->UnwrapRef());
        if (type) {
            parameters.emplace_back(BuiltinPrototype::Parameter{type, parameter.usage});
            match_score += kScorePerMatchedParam;
        } else {
            overload_matched = false;
        }
    }

    if (overload_matched) {
        // Check all constrained open types matched
        for (uint32_t ot = 0; ot < overload.num_open_types; ot++) {
            auto& open_type = overload.open_types[ot];
            if (open_type.matcher_index != kNoMatcher) {
                auto* index = &open_type.matcher_index;
                if (Match(closed, overload, index).Type(closed.Type(ot))) {
                    match_score += kScorePerMatchedOpenType;
                } else {
                    overload_matched = false;
                }
            }
        }
    }

    if (overload_matched) {
        // Check all constrained open numbers matched
        for (uint32_t on = 0; on < overload.num_open_numbers; on++) {
            auto& open_number = overload.open_numbers[on];
            if (open_number.matcher_index != kNoMatcher) {
                auto* index = &open_number.matcher_index;
                if (Match(closed, overload, index).Num(closed.Num(on)).IsValid()) {
                    match_score += kScorePerMatchedOpenNumber;
                } else {
                    overload_matched = false;
                }
            }
        }
    }

    if (!overload_matched) {
        return nullptr;
    }

    // Build the return type
    const sem::Type* return_type = nullptr;
    if (auto* indices = overload.return_matcher_indices) {
        Any any;
        return_type = Match(closed, overload, indices).Type(&any);
        if (!return_type) {
            std::stringstream ss;
            PrintOverload(ss, overload, builtin_type);
            TINT_ICE(Resolver, builder.Diagnostics())
                << "MatchState.Match() returned null for " << ss.str();
            return nullptr;
        }
    } else {
        return_type = builder.create<sem::Void>();
    }

    BuiltinPrototype builtin;
    builtin.type = builtin_type;
    builtin.return_type = return_type;
    builtin.parameters = std::move(parameters);
    builtin.supported_stages = overload.supported_stages;
    builtin.is_deprecated = overload.is_deprecated;

    // De-duplicate builtins that are identical.
    return utils::GetOrCreate(builtins, builtin, [&] {
        std::vector<sem::Parameter*> params;
        params.reserve(builtin.parameters.size());
        for (auto& p : builtin.parameters) {
            params.emplace_back(builder.create<sem::Parameter>(
                nullptr, static_cast<uint32_t>(params.size()), p.type, ast::StorageClass::kNone,
                ast::Access::kUndefined, p.usage));
        }
        return builder.create<sem::Builtin>(builtin.type, builtin.return_type, std::move(params),
                                            builtin.supported_stages, builtin.is_deprecated);
    });
}

MatchState Impl::Match(ClosedState& closed,
                       const OverloadInfo& overload,
                       MatcherIndex const* matcher_indices) const {
    return MatchState(builder, closed, matchers, overload, matcher_indices);
}

void Impl::PrintOverload(std::ostream& ss,
                         const OverloadInfo& overload,
                         sem::BuiltinType builtin_type) const {
    ClosedState closed(builder);

    ss << builtin_type << "(";
    for (uint32_t p = 0; p < overload.num_parameters; p++) {
        auto& parameter = overload.parameters[p];
        if (p > 0) {
            ss << ", ";
        }
        if (parameter.usage != ParameterUsage::kNone) {
            ss << sem::str(parameter.usage) << ": ";
        }
        auto* indices = parameter.matcher_indices;
        ss << Match(closed, overload, indices).TypeName();
    }
    ss << ")";
    if (overload.return_matcher_indices) {
        ss << " -> ";
        auto* indices = overload.return_matcher_indices;
        ss << Match(closed, overload, indices).TypeName();
    }

    bool first = true;
    auto separator = [&] {
        ss << (first ? "  where: " : ", ");
        first = false;
    };
    for (uint32_t i = 0; i < overload.num_open_types; i++) {
        auto& open_type = overload.open_types[i];
        if (open_type.matcher_index != kNoMatcher) {
            separator();
            ss << open_type.name;
            auto* index = &open_type.matcher_index;
            ss << " is " << Match(closed, overload, index).TypeName();
        }
    }
    for (uint32_t i = 0; i < overload.num_open_numbers; i++) {
        auto& open_number = overload.open_numbers[i];
        if (open_number.matcher_index != kNoMatcher) {
            separator();
            ss << open_number.name;
            auto* index = &open_number.matcher_index;
            ss << " is " << Match(closed, overload, index).NumName();
        }
    }
}

const sem::Type* MatchState::Type(const sem::Type* ty) {
    MatcherIndex matcher_index = *matcher_indices_++;
    auto* matcher = matchers.type[matcher_index];
    return matcher->Match(*this, ty);
}

Number MatchState::Num(Number number) {
    MatcherIndex matcher_index = *matcher_indices_++;
    auto* matcher = matchers.number[matcher_index];
    return matcher->Match(*this, number);
}

std::string MatchState::TypeName() {
    MatcherIndex matcher_index = *matcher_indices_++;
    auto* matcher = matchers.type[matcher_index];
    return matcher->String(*this);
}

std::string MatchState::NumName() {
    MatcherIndex matcher_index = *matcher_indices_++;
    auto* matcher = matchers.number[matcher_index];
    return matcher->String(*this);
}

}  // namespace

std::unique_ptr<BuiltinTable> BuiltinTable::Create(ProgramBuilder& builder) {
    return std::make_unique<Impl>(builder);
}

BuiltinTable::~BuiltinTable() = default;

/// TypeInfo for the Any type declared in the anonymous namespace above
TINT_INSTANTIATE_TYPEINFO(Any);

}  // namespace tint