| // 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/resolver/intrinsic_table.h" |
| |
| #include <algorithm> |
| #include <limits> |
| #include <unordered_map> |
| #include <utility> |
| |
| #include "src/tint/ast/binary_expression.h" |
| #include "src/tint/program_builder.h" |
| #include "src/tint/sem/abstract_float.h" |
| #include "src/tint/sem/abstract_int.h" |
| #include "src/tint/sem/abstract_numeric.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/sem/type_constructor.h" |
| #include "src/tint/sem/type_conversion.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::resolver { |
| namespace { |
| |
| // Forward declarations |
| struct OverloadInfo; |
| class Matchers; |
| class NumberMatcher; |
| class TypeMatcher; |
| |
| /// The utils::Vector `N` template argument value for arrays of parameters. |
| constexpr static const size_t kNumFixedParams = 8; |
| |
| /// The utils::Vector `N` template argument value for arrays of overload candidates. |
| constexpr static const size_t kNumFixedCandidates = 8; |
| |
| /// 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}; |
| |
| /// TemplateState holds the state of the template numbers and types. |
| /// Used by the MatchState. |
| class TemplateState { |
| public: |
| /// If the template type with index `idx` is undefined, then it is defined with the `ty` and |
| /// Type() returns `ty`. |
| /// If the template type is defined, and `ty` can be converted to the template type then the |
| /// template type is returned. |
| /// If the template type is defined, and the template type can be converted to `ty`, then the |
| /// template type is replaced with `ty`, and `ty` is returned. |
| /// If none of the above applies, then `ty` is a type mismatch for the template type, and |
| /// nullptr is returned. |
| const sem::Type* Type(size_t idx, const sem::Type* ty) { |
| if (idx >= types_.Length()) { |
| types_.Resize(idx + 1); |
| } |
| auto& t = types_[idx]; |
| if (t == nullptr) { |
| t = ty; |
| return ty; |
| } |
| ty = sem::Type::Common(utils::Vector{t, ty}); |
| if (ty) { |
| t = ty; |
| } |
| return ty; |
| } |
| |
| /// If the number with index `idx` is undefined, then it is defined with the number `number` and |
| /// Num() returns true. If the number is defined, then `Num()` returns true iff it is equal to |
| /// `ty`. |
| bool Num(size_t idx, Number number) { |
| if (idx >= numbers_.Length()) { |
| numbers_.Resize(idx + 1, Number::invalid); |
| } |
| auto& n = numbers_[idx]; |
| if (!n.IsValid()) { |
| n = number.Value(); |
| return true; |
| } |
| return n.Value() == number.Value(); |
| } |
| |
| /// Type returns the template type with index `idx`, or nullptr if the type was not defined. |
| const sem::Type* Type(size_t idx) const { |
| if (idx >= types_.Length()) { |
| return nullptr; |
| } |
| return types_[idx]; |
| } |
| |
| /// SetType replaces the template type with index `idx` with type `ty`. |
| void SetType(size_t idx, const sem::Type* ty) { |
| if (idx >= types_.Length()) { |
| types_.Resize(idx + 1); |
| } |
| types_[idx] = ty; |
| } |
| |
| /// Type returns the number type with index `idx`. |
| Number Num(size_t idx) const { |
| if (idx >= numbers_.Length()) { |
| return Number::invalid; |
| } |
| return numbers_[idx]; |
| } |
| |
| private: |
| utils::Vector<const sem::Type*, 4> types_; |
| utils::Vector<Number, 2> numbers_; |
| }; |
| |
| /// Index type used for matcher indices |
| using MatcherIndex = uint8_t; |
| |
| /// Index value used for template 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, |
| TemplateState& t, |
| const Matchers& m, |
| const OverloadInfo* o, |
| MatcherIndex const* matcher_indices) |
| : builder(b), templates(t), matchers(m), overload(o), matcher_indices_(matcher_indices) {} |
| |
| /// The program builder |
| ProgramBuilder& builder; |
| /// The template types and numbers |
| TemplateState& templates; |
| /// 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 define and refine the template 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 define template 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; |
| }; |
| |
| /// TemplateTypeMatcher is a Matcher for a template type. |
| /// The TemplateTypeMatcher will initially match against any type, and then will only be further |
| /// constrained based on the conversion rules defined at https://www.w3.org/TR/WGSL/#conversion-rank |
| class TemplateTypeMatcher : public TypeMatcher { |
| public: |
| /// Constructor |
| explicit TemplateTypeMatcher(size_t index) : index_(index) {} |
| |
| const sem::Type* Match(MatchState& state, const sem::Type* type) const override { |
| if (type->Is<Any>()) { |
| return state.templates.Type(index_); |
| } |
| if (auto* templates = state.templates.Type(index_, type)) { |
| return templates; |
| } |
| return nullptr; |
| } |
| |
| std::string String(MatchState* state) const override; |
| |
| private: |
| size_t index_; |
| }; |
| |
| /// TemplateNumberMatcher is a Matcher for a template number. |
| /// The TemplateNumberMatcher will match against any number (so long as it is |
| /// consistent for all uses in the overload) |
| class TemplateNumberMatcher : public NumberMatcher { |
| public: |
| explicit TemplateNumberMatcher(size_t index) : index_(index) {} |
| |
| Number Match(MatchState& state, Number number) const override { |
| if (number.IsAny()) { |
| return state.templates.Num(index_); |
| } |
| return state.templates.Num(index_, number) ? number : Number::invalid; |
| } |
| |
| std::string String(MatchState* state) const override; |
| |
| private: |
| size_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 PipelineStage = ast::PipelineStage; |
| |
| /// Unique flag bits for overloads |
| enum class OverloadFlag { |
| kIsBuiltin, // The overload is a builtin ('fn') |
| kIsOperator, // The overload is an operator ('op') |
| kIsConstructor, // The overload is a type constructor ('ctor') |
| kIsConverter, // The overload is a type converter ('conv') |
| kSupportsVertexPipeline, // The overload can be used in vertex shaders |
| kSupportsFragmentPipeline, // The overload can be used in fragment shaders |
| kSupportsComputePipeline, // The overload can be used in compute shaders |
| kIsDeprecated, // The overload is deprecated |
| }; |
| |
| // An enum set of OverloadFlag, used by OperatorInfo |
| using OverloadFlags = utils::EnumSet<OverloadFlag>; |
| |
| bool match_bool(const sem::Type* ty) { |
| return ty->IsAnyOf<Any, sem::Bool>(); |
| } |
| |
| const sem::AbstractFloat* build_fa(MatchState& state) { |
| return state.builder.create<sem::AbstractFloat>(); |
| } |
| |
| bool match_fa(const sem::Type* ty) { |
| return ty->IsAnyOf<Any, sem::AbstractFloat>(); |
| } |
| |
| const sem::AbstractInt* build_ia(MatchState& state) { |
| return state.builder.create<sem::AbstractInt>(); |
| } |
| |
| bool match_ia(const sem::Type* ty) { |
| return ty->IsAnyOf<Any, sem::AbstractInt>(); |
| } |
| |
| const sem::Bool* build_bool(MatchState& state) { |
| return state.builder.create<sem::Bool>(); |
| } |
| |
| const sem::F16* build_f16(MatchState& state) { |
| return state.builder.create<sem::F16>(); |
| } |
| |
| bool match_f16(const sem::Type* ty) { |
| return ty->IsAnyOf<Any, sem::F16, sem::AbstractNumeric>(); |
| } |
| |
| const sem::F32* build_f32(MatchState& state) { |
| return state.builder.create<sem::F32>(); |
| } |
| |
| bool match_f32(const sem::Type* ty) { |
| return ty->IsAnyOf<Any, sem::F32, sem::AbstractNumeric>(); |
| } |
| |
| 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, sem::AbstractInt>(); |
| } |
| |
| 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, sem::AbstractInt>(); |
| } |
| |
| 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; |
| } |
| |
| template <uint32_t 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; |
| } |
| |
| const sem::Vector* build_vec(MatchState& state, Number N, const sem::Type* el) { |
| return state.builder.create<sem::Vector>(el, N.Value()); |
| } |
| |
| template <uint32_t N> |
| const sem::Vector* build_vec(MatchState& state, const sem::Type* el) { |
| return state.builder.create<sem::Vector>(el, N); |
| } |
| |
| constexpr auto match_vec2 = match_vec<2>; |
| constexpr auto match_vec3 = match_vec<3>; |
| constexpr auto match_vec4 = match_vec<4>; |
| |
| constexpr auto build_vec2 = build_vec<2>; |
| constexpr auto build_vec3 = build_vec<3>; |
| constexpr auto build_vec4 = build_vec<4>; |
| |
| 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; |
| } |
| |
| template <uint32_t C, uint32_t R> |
| bool match_mat(const sem::Type* ty, const sem::Type*& T) { |
| if (ty->Is<Any>()) { |
| T = ty; |
| return true; |
| } |
| if (auto* m = ty->As<sem::Matrix>()) { |
| if (m->columns() == C && m->rows() == R) { |
| T = m->type(); |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| const sem::Matrix* build_mat(MatchState& state, Number C, Number R, const sem::Type* T) { |
| auto* column_type = state.builder.create<sem::Vector>(T, R.Value()); |
| return state.builder.create<sem::Matrix>(column_type, C.Value()); |
| } |
| |
| template <uint32_t C, uint32_t R> |
| const sem::Matrix* build_mat(MatchState& state, const sem::Type* T) { |
| auto* column_type = state.builder.create<sem::Vector>(T, R); |
| return state.builder.create<sem::Matrix>(column_type, C); |
| } |
| |
| constexpr auto build_mat2x2 = build_mat<2, 2>; |
| constexpr auto build_mat2x3 = build_mat<2, 3>; |
| constexpr auto build_mat2x4 = build_mat<2, 4>; |
| constexpr auto build_mat3x2 = build_mat<3, 2>; |
| constexpr auto build_mat3x3 = build_mat<3, 3>; |
| constexpr auto build_mat3x4 = build_mat<3, 4>; |
| constexpr auto build_mat4x2 = build_mat<4, 2>; |
| constexpr auto build_mat4x3 = build_mat<4, 3>; |
| constexpr auto build_mat4x4 = build_mat<4, 4>; |
| |
| constexpr auto match_mat2x2 = match_mat<2, 2>; |
| constexpr auto match_mat2x3 = match_mat<2, 3>; |
| constexpr auto match_mat2x4 = match_mat<2, 4>; |
| constexpr auto match_mat3x2 = match_mat<3, 2>; |
| constexpr auto match_mat3x3 = match_mat<3, 3>; |
| constexpr auto match_mat3x4 = match_mat<3, 4>; |
| constexpr auto match_mat4x2 = match_mat<4, 2>; |
| constexpr auto match_mat4x3 = match_mat<4, 3>; |
| constexpr auto match_mat4x4 = match_mat<4, 4>; |
| |
| 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, const sem::Type*& T) { |
| if (!ty->Is<Any>()) { |
| return false; |
| } |
| T = ty; |
| return true; |
| } |
| bool match_modf_result_vec(const sem::Type* ty, Number& N, const sem::Type*& T) { |
| if (!ty->Is<Any>()) { |
| return false; |
| } |
| N = Number::any; |
| T = ty; |
| return true; |
| } |
| bool match_frexp_result(const sem::Type* ty, const sem::Type*& T) { |
| if (!ty->Is<Any>()) { |
| return false; |
| } |
| T = ty; |
| return true; |
| } |
| bool match_frexp_result_vec(const sem::Type* ty, Number& N, const sem::Type*& T) { |
| if (!ty->Is<Any>()) { |
| return false; |
| } |
| N = Number::any; |
| T = ty; |
| return true; |
| } |
| |
| bool match_atomic_compare_exchange_result(const sem::Type* ty, const sem::Type*& T) { |
| if (ty->Is<Any>()) { |
| T = ty; |
| return true; |
| } |
| return false; |
| } |
| |
| struct NameAndType { |
| std::string name; |
| const 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, const sem::Type* el) { |
| std::string display_name; |
| if (el->Is<sem::F16>()) { |
| display_name = "__modf_result_f16"; |
| } else { |
| display_name = "__modf_result"; |
| } |
| return build_struct(state, display_name, {{"fract", el}, {"whole", el}}); |
| } |
| const sem::Struct* build_modf_result_vec(MatchState& state, Number& n, const sem::Type* el) { |
| std::string display_name; |
| if (el->Is<sem::F16>()) { |
| display_name = "__modf_result_vec" + std::to_string(n.Value()) + "_f16"; |
| } else { |
| display_name = "__modf_result_vec" + std::to_string(n.Value()); |
| } |
| auto* vec = state.builder.create<sem::Vector>(el, n.Value()); |
| return build_struct(state, display_name, {{"fract", vec}, {"whole", vec}}); |
| } |
| const sem::Struct* build_frexp_result(MatchState& state, const sem::Type* el) { |
| std::string display_name; |
| if (el->Is<sem::F16>()) { |
| display_name = "__frexp_result_f16"; |
| } else { |
| display_name = "__frexp_result"; |
| } |
| auto* i32 = state.builder.create<sem::I32>(); |
| return build_struct(state, display_name, {{"sig", el}, {"exp", i32}}); |
| } |
| const sem::Struct* build_frexp_result_vec(MatchState& state, Number& n, const sem::Type* el) { |
| std::string display_name; |
| if (el->Is<sem::F16>()) { |
| display_name = "__frexp_result_vec" + std::to_string(n.Value()) + "_f16"; |
| } else { |
| display_name = "__frexp_result_vec" + std::to_string(n.Value()); |
| } |
| auto* vec = state.builder.create<sem::Vector>(el, n.Value()); |
| auto* vec_i32 = state.builder.create<sem::Vector>(state.builder.create<sem::I32>(), n.Value()); |
| return build_struct(state, display_name, {{"sig", vec}, {"exp", vec_i32}}); |
| } |
| const sem::Struct* build_atomic_compare_exchange_result(MatchState& state, const sem::Type* ty) { |
| return build_struct( |
| state, "__atomic_compare_exchange_result" + ty->FriendlyName(state.builder.Symbols()), |
| {{"old_value", const_cast<sem::Type*>(ty)}, |
| {"exchanged", state.builder.create<sem::Bool>()}}); |
| } |
| |
| /// 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; |
| }; |
| |
| /// TemplateTypeInfo describes an template type |
| struct TemplateTypeInfo { |
| /// Name of the template type (e.g. 'T') |
| const char* name; |
| /// Optional type matcher constraint. |
| /// Either an index in Matchers::type, or kNoMatcher |
| const MatcherIndex matcher_index; |
| }; |
| |
| /// TemplateNumberInfo describes a template number |
| struct TemplateNumberInfo { |
| /// Name of the template 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 template types for the overload |
| const uint8_t num_template_types; |
| /// Total number of template numbers for the overload |
| const uint8_t num_template_numbers; |
| /// Pointer to the first template type |
| TemplateTypeInfo const* const template_types; |
| /// Pointer to the first template number |
| TemplateNumberInfo const* const template_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 flags for the overload |
| OverloadFlags flags; |
| /// The function used to evaluate the overload at shader-creation time. |
| ConstEval::Function const const_eval_fn; |
| }; |
| |
| /// IntrinsicInfo describes a builtin function or operator overload |
| struct IntrinsicInfo { |
| /// Number of overloads of the intrinsic |
| const uint8_t num_overloads; |
| /// Pointer to the start of the overloads for the function |
| OverloadInfo const* const overloads; |
| }; |
| |
| #include "intrinsic_table.inl" |
| |
| /// IntrinsicPrototype describes a fully matched intrinsic. |
| struct IntrinsicPrototype { |
| /// 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 IntrinsicPrototype |
| struct Hasher { |
| /// @param i the IntrinsicPrototype to create a hash for |
| /// @return the hash value |
| inline std::size_t operator()(const IntrinsicPrototype& i) const { |
| size_t hash = utils::Hash(i.parameters.Length()); |
| for (auto& p : i.parameters) { |
| utils::HashCombine(&hash, p.type, p.usage); |
| } |
| return utils::Hash(hash, i.overload, i.return_type); |
| } |
| }; |
| |
| const OverloadInfo* overload = nullptr; |
| sem::Type const* return_type = nullptr; |
| utils::Vector<Parameter, kNumFixedParams> parameters; |
| }; |
| |
| /// Equality operator for IntrinsicPrototype |
| bool operator==(const IntrinsicPrototype& a, const IntrinsicPrototype& b) { |
| if (a.overload != b.overload || a.return_type != b.return_type || |
| a.parameters.Length() != b.parameters.Length()) { |
| return false; |
| } |
| for (size_t i = 0; i < a.parameters.Length(); 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 IntrinsicTable interface. |
| class Impl : public IntrinsicTable { |
| public: |
| explicit Impl(ProgramBuilder& builder); |
| |
| Builtin Lookup(sem::BuiltinType builtin_type, |
| utils::VectorRef<const sem::Type*> args, |
| const Source& source) override; |
| |
| UnaryOperator Lookup(ast::UnaryOp op, const sem::Type* arg, const Source& source) override; |
| |
| BinaryOperator Lookup(ast::BinaryOp op, |
| const sem::Type* lhs, |
| const sem::Type* rhs, |
| const Source& source, |
| bool is_compound) override; |
| |
| CtorOrConv Lookup(CtorConvIntrinsic type, |
| const sem::Type* template_arg, |
| utils::VectorRef<const sem::Type*> args, |
| const Source& source) override; |
| |
| private: |
| /// Candidate holds information about an overload evaluated for resolution. |
| struct Candidate { |
| /// The candidate overload |
| const OverloadInfo* overload; |
| /// The template types and numbers |
| TemplateState templates; |
| /// The parameter types for the candidate overload |
| utils::Vector<IntrinsicPrototype::Parameter, kNumFixedParams> parameters; |
| /// The match-score of the candidate overload. |
| /// A score of zero indicates an exact match. |
| /// Non-zero scores are used for diagnostics when no overload matches. |
| /// Lower scores are displayed first (top-most). |
| size_t score; |
| }; |
| |
| /// A list of candidates |
| using Candidates = utils::Vector<Candidate, kNumFixedCandidates>; |
| |
| /// Callback function when no overloads match. |
| using OnNoMatch = std::function<void(utils::VectorRef<Candidate>)>; |
| |
| /// Sorts the candidates based on their score, with the lowest (best-ranking) scores first. |
| static inline void SortCandidates(Candidates& candidates) { |
| std::stable_sort(candidates.begin(), candidates.end(), |
| [&](const Candidate& a, const Candidate& b) { return a.score < b.score; }); |
| } |
| |
| /// Attempts to find a single intrinsic overload that matches the provided argument types. |
| /// @param intrinsic the intrinsic being called |
| /// @param intrinsic_name the name of the intrinsic |
| /// @param args the argument types |
| /// @param templates initial template state. This may contain explicitly specified template |
| /// arguments. For example `vec3<f32>()` would have the first template-type |
| /// defined as `f32`. |
| /// @param on_no_match an error callback when no intrinsic overloads matched the provided |
| /// arguments. |
| /// @returns the matched intrinsic. If no intrinsic could be matched then IntrinsicPrototype |
| /// will hold nullptrs for IntrinsicPrototype::overload and |
| /// IntrinsicPrototype::return_type. |
| IntrinsicPrototype MatchIntrinsic(const IntrinsicInfo& intrinsic, |
| const char* intrinsic_name, |
| utils::VectorRef<const sem::Type*> args, |
| TemplateState templates, |
| OnNoMatch on_no_match) const; |
| |
| /// Evaluates the single overload for the provided argument types. |
| /// @param overload the overload being considered |
| /// @param args the argument types |
| /// @param templates initial template state. This may contain explicitly specified template |
| /// arguments. For example `vec3<f32>()` would have the first template-type |
| /// template as `f32`. |
| /// @returns the evaluated Candidate information. |
| Candidate ScoreOverload(const OverloadInfo* overload, |
| utils::VectorRef<const sem::Type*> args, |
| TemplateState templates) const; |
| |
| /// Performs overload resolution given the list of candidates, by ranking the conversions of |
| /// arguments to the each of the candidate's parameter types. |
| /// @param candidates the list of candidate overloads |
| /// @param intrinsic_name the name of the intrinsic |
| /// @param args the argument types |
| /// @param templates initial template state. This may contain explicitly specified template |
| /// arguments. For example `vec3<f32>()` would have the first template-type |
| /// template as `f32`. |
| /// @see https://www.w3.org/TR/WGSL/#overload-resolution-section |
| /// @returns the resolved Candidate. |
| Candidate ResolveCandidate(Candidates&& candidates, |
| const char* intrinsic_name, |
| utils::VectorRef<const sem::Type*> args, |
| TemplateState templates) const; |
| |
| /// Match constructs a new MatchState |
| /// @param templates the template state used for matcher evaluation |
| /// @param overload the overload being evaluated |
| /// @param matcher_indices pointer to a list of matcher indices |
| MatchState Match(TemplateState& templates, |
| const OverloadInfo* overload, |
| MatcherIndex const* matcher_indices) const; |
| |
| // Prints the overload for emitting diagnostics |
| void PrintOverload(std::ostream& ss, |
| const OverloadInfo* overload, |
| const char* intrinsic_name) const; |
| |
| // Prints the list of candidates for emitting diagnostics |
| void PrintCandidates(std::ostream& ss, |
| utils::VectorRef<Candidate> candidates, |
| const char* intrinsic_name) const; |
| |
| /// Raises an error when no overload is a clear winner of overload resolution |
| void ErrAmbiguousOverload(const char* intrinsic_name, |
| utils::VectorRef<const sem::Type*> args, |
| TemplateState templates, |
| utils::VectorRef<Candidate> candidates) const; |
| |
| ProgramBuilder& builder; |
| Matchers matchers; |
| std::unordered_map<IntrinsicPrototype, sem::Builtin*, IntrinsicPrototype::Hasher> builtins; |
| std::unordered_map<IntrinsicPrototype, sem::TypeConstructor*, IntrinsicPrototype::Hasher> |
| constructors; |
| std::unordered_map<IntrinsicPrototype, sem::TypeConversion*, IntrinsicPrototype::Hasher> |
| converters; |
| }; |
| |
| /// @return a string representing a call to a builtin with the given argument |
| /// types. |
| std::string CallSignature(ProgramBuilder& builder, |
| const char* intrinsic_name, |
| utils::VectorRef<const sem::Type*> args, |
| const sem::Type* template_arg = nullptr) { |
| std::stringstream ss; |
| ss << intrinsic_name; |
| if (template_arg) { |
| ss << "<" << template_arg->FriendlyName(builder.Symbols()) << ">"; |
| } |
| ss << "("; |
| { |
| bool first = true; |
| for (auto* arg : args) { |
| if (!first) { |
| ss << ", "; |
| } |
| first = false; |
| ss << arg->UnwrapRef()->FriendlyName(builder.Symbols()); |
| } |
| } |
| ss << ")"; |
| |
| return ss.str(); |
| } |
| |
| std::string TemplateTypeMatcher::String(MatchState* state) const { |
| return state->overload->template_types[index_].name; |
| } |
| |
| std::string TemplateNumberMatcher::String(MatchState* state) const { |
| return state->overload->template_numbers[index_].name; |
| } |
| |
| Impl::Impl(ProgramBuilder& b) : builder(b) {} |
| |
| Impl::Builtin Impl::Lookup(sem::BuiltinType builtin_type, |
| utils::VectorRef<const sem::Type*> args, |
| const Source& source) { |
| const char* intrinsic_name = sem::str(builtin_type); |
| |
| // Generates an error when no overloads match the provided arguments |
| auto on_no_match = [&](utils::VectorRef<Candidate> candidates) { |
| std::stringstream ss; |
| ss << "no matching call to " << CallSignature(builder, intrinsic_name, args) << std::endl; |
| if (!candidates.IsEmpty()) { |
| ss << std::endl |
| << candidates.Length() << " candidate function" |
| << (candidates.Length() > 1 ? "s:" : ":") << std::endl; |
| PrintCandidates(ss, candidates, intrinsic_name); |
| } |
| builder.Diagnostics().add_error(diag::System::Resolver, ss.str(), source); |
| }; |
| |
| // Resolve the intrinsic overload |
| auto match = MatchIntrinsic(kBuiltins[static_cast<size_t>(builtin_type)], intrinsic_name, args, |
| TemplateState{}, on_no_match); |
| if (!match.overload) { |
| return {}; |
| } |
| |
| // De-duplicate builtins that are identical. |
| auto* sem = utils::GetOrCreate(builtins, match, [&] { |
| utils::Vector<sem::Parameter*, kNumFixedParams> params; |
| params.Reserve(match.parameters.Length()); |
| for (auto& p : match.parameters) { |
| params.Push(builder.create<sem::Parameter>( |
| nullptr, static_cast<uint32_t>(params.Length()), p.type, ast::StorageClass::kNone, |
| ast::Access::kUndefined, p.usage)); |
| } |
| sem::PipelineStageSet supported_stages; |
| if (match.overload->flags.Contains(OverloadFlag::kSupportsVertexPipeline)) { |
| supported_stages.Add(ast::PipelineStage::kVertex); |
| } |
| if (match.overload->flags.Contains(OverloadFlag::kSupportsFragmentPipeline)) { |
| supported_stages.Add(ast::PipelineStage::kFragment); |
| } |
| if (match.overload->flags.Contains(OverloadFlag::kSupportsComputePipeline)) { |
| supported_stages.Add(ast::PipelineStage::kCompute); |
| } |
| auto eval_stage = match.overload->const_eval_fn ? sem::EvaluationStage::kConstant |
| : sem::EvaluationStage::kRuntime; |
| return builder.create<sem::Builtin>( |
| builtin_type, match.return_type, std::move(params), eval_stage, supported_stages, |
| match.overload->flags.Contains(OverloadFlag::kIsDeprecated)); |
| }); |
| return Builtin{sem, match.overload->const_eval_fn}; |
| } |
| |
| IntrinsicTable::UnaryOperator Impl::Lookup(ast::UnaryOp op, |
| const sem::Type* arg, |
| const Source& source) { |
| auto [intrinsic_index, intrinsic_name] = [&]() -> std::pair<size_t, const char*> { |
| switch (op) { |
| case ast::UnaryOp::kComplement: |
| return {kUnaryOperatorComplement, "operator ~ "}; |
| case ast::UnaryOp::kNegation: |
| return {kUnaryOperatorMinus, "operator - "}; |
| case ast::UnaryOp::kNot: |
| return {kUnaryOperatorNot, "operator ! "}; |
| default: |
| return {0, "<unknown>"}; |
| } |
| }(); |
| |
| utils::Vector args{arg}; |
| |
| // Generates an error when no overloads match the provided arguments |
| auto on_no_match = [&, name = intrinsic_name](utils::VectorRef<Candidate> candidates) { |
| std::stringstream ss; |
| ss << "no matching overload for " << CallSignature(builder, name, args) << std::endl; |
| if (!candidates.IsEmpty()) { |
| ss << std::endl |
| << candidates.Length() << " candidate operator" |
| << (candidates.Length() > 1 ? "s:" : ":") << std::endl; |
| PrintCandidates(ss, candidates, name); |
| } |
| builder.Diagnostics().add_error(diag::System::Resolver, ss.str(), source); |
| }; |
| |
| // Resolve the intrinsic overload |
| auto match = MatchIntrinsic(kUnaryOperators[intrinsic_index], intrinsic_name, args, |
| TemplateState{}, on_no_match); |
| if (!match.overload) { |
| return {}; |
| } |
| |
| return UnaryOperator{ |
| match.return_type, |
| match.parameters[0].type, |
| match.overload->const_eval_fn, |
| }; |
| } |
| |
| IntrinsicTable::BinaryOperator Impl::Lookup(ast::BinaryOp op, |
| const sem::Type* lhs, |
| const sem::Type* rhs, |
| const Source& source, |
| bool is_compound) { |
| auto [intrinsic_index, intrinsic_name] = [&]() -> std::pair<size_t, const char*> { |
| switch (op) { |
| case ast::BinaryOp::kAnd: |
| return {kBinaryOperatorAnd, is_compound ? "operator &= " : "operator & "}; |
| case ast::BinaryOp::kOr: |
| return {kBinaryOperatorOr, is_compound ? "operator |= " : "operator | "}; |
| case ast::BinaryOp::kXor: |
| return {kBinaryOperatorXor, is_compound ? "operator ^= " : "operator ^ "}; |
| case ast::BinaryOp::kLogicalAnd: |
| return {kBinaryOperatorLogicalAnd, "operator && "}; |
| case ast::BinaryOp::kLogicalOr: |
| return {kBinaryOperatorLogicalOr, "operator || "}; |
| case ast::BinaryOp::kEqual: |
| return {kBinaryOperatorEqual, "operator == "}; |
| case ast::BinaryOp::kNotEqual: |
| return {kBinaryOperatorNotEqual, "operator != "}; |
| case ast::BinaryOp::kLessThan: |
| return {kBinaryOperatorLessThan, "operator < "}; |
| case ast::BinaryOp::kGreaterThan: |
| return {kBinaryOperatorGreaterThan, "operator > "}; |
| case ast::BinaryOp::kLessThanEqual: |
| return {kBinaryOperatorLessThanEqual, "operator <= "}; |
| case ast::BinaryOp::kGreaterThanEqual: |
| return {kBinaryOperatorGreaterThanEqual, "operator >= "}; |
| case ast::BinaryOp::kShiftLeft: |
| return {kBinaryOperatorShiftLeft, is_compound ? "operator <<= " : "operator << "}; |
| case ast::BinaryOp::kShiftRight: |
| return {kBinaryOperatorShiftRight, is_compound ? "operator >>= " : "operator >> "}; |
| case ast::BinaryOp::kAdd: |
| return {kBinaryOperatorPlus, is_compound ? "operator += " : "operator + "}; |
| case ast::BinaryOp::kSubtract: |
| return {kBinaryOperatorMinus, is_compound ? "operator -= " : "operator - "}; |
| case ast::BinaryOp::kMultiply: |
| return {kBinaryOperatorStar, is_compound ? "operator *= " : "operator * "}; |
| case ast::BinaryOp::kDivide: |
| return {kBinaryOperatorDivide, is_compound ? "operator /= " : "operator / "}; |
| case ast::BinaryOp::kModulo: |
| return {kBinaryOperatorModulo, is_compound ? "operator %= " : "operator % "}; |
| default: |
| return {0, "<unknown>"}; |
| } |
| }(); |
| |
| utils::Vector args{lhs, rhs}; |
| |
| // Generates an error when no overloads match the provided arguments |
| auto on_no_match = [&, name = intrinsic_name](utils::VectorRef<Candidate> candidates) { |
| std::stringstream ss; |
| ss << "no matching overload for " << CallSignature(builder, name, args) << std::endl; |
| if (!candidates.IsEmpty()) { |
| ss << std::endl |
| << candidates.Length() << " candidate operator" |
| << (candidates.Length() > 1 ? "s:" : ":") << std::endl; |
| PrintCandidates(ss, candidates, name); |
| } |
| builder.Diagnostics().add_error(diag::System::Resolver, ss.str(), source); |
| }; |
| |
| // Resolve the intrinsic overload |
| auto match = MatchIntrinsic(kBinaryOperators[intrinsic_index], intrinsic_name, args, |
| TemplateState{}, on_no_match); |
| if (!match.overload) { |
| return {}; |
| } |
| |
| return BinaryOperator{ |
| match.return_type, |
| match.parameters[0].type, |
| match.parameters[1].type, |
| match.overload->const_eval_fn, |
| }; |
| } |
| |
| IntrinsicTable::CtorOrConv Impl::Lookup(CtorConvIntrinsic type, |
| const sem::Type* template_arg, |
| utils::VectorRef<const sem::Type*> args, |
| const Source& source) { |
| auto name = str(type); |
| |
| // Generates an error when no overloads match the provided arguments |
| auto on_no_match = [&](utils::VectorRef<Candidate> candidates) { |
| std::stringstream ss; |
| ss << "no matching constructor for " << CallSignature(builder, name, args, template_arg) |
| << std::endl; |
| Candidates ctor, conv; |
| for (auto candidate : candidates) { |
| if (candidate.overload->flags.Contains(OverloadFlag::kIsConstructor)) { |
| ctor.Push(candidate); |
| } else { |
| conv.Push(candidate); |
| } |
| } |
| if (!ctor.IsEmpty()) { |
| ss << std::endl |
| << ctor.Length() << " candidate constructor" << (ctor.Length() > 1 ? "s:" : ":") |
| << std::endl; |
| PrintCandidates(ss, ctor, name); |
| } |
| if (!conv.IsEmpty()) { |
| ss << std::endl |
| << conv.Length() << " candidate conversion" << (conv.Length() > 1 ? "s:" : ":") |
| << std::endl; |
| PrintCandidates(ss, conv, name); |
| } |
| builder.Diagnostics().add_error(diag::System::Resolver, ss.str(), source); |
| }; |
| |
| // If a template type was provided, then close the 0'th type with this. |
| TemplateState templates; |
| if (template_arg) { |
| templates.Type(0, template_arg); |
| } |
| |
| // Resolve the intrinsic overload |
| auto match = MatchIntrinsic(kConstructorsAndConverters[static_cast<size_t>(type)], name, args, |
| templates, on_no_match); |
| if (!match.overload) { |
| return {}; |
| } |
| |
| // Was this overload a constructor or conversion? |
| if (match.overload->flags.Contains(OverloadFlag::kIsConstructor)) { |
| utils::Vector<const sem::Parameter*, 8> params; |
| params.Reserve(match.parameters.Length()); |
| for (auto& p : match.parameters) { |
| params.Push(builder.create<sem::Parameter>( |
| nullptr, static_cast<uint32_t>(params.Length()), p.type, ast::StorageClass::kNone, |
| ast::Access::kUndefined, p.usage)); |
| } |
| auto eval_stage = match.overload->const_eval_fn ? sem::EvaluationStage::kConstant |
| : sem::EvaluationStage::kRuntime; |
| auto* target = utils::GetOrCreate(constructors, match, [&]() { |
| return builder.create<sem::TypeConstructor>(match.return_type, std::move(params), |
| eval_stage); |
| }); |
| return CtorOrConv{target, match.overload->const_eval_fn}; |
| } |
| |
| // Conversion. |
| auto* target = utils::GetOrCreate(converters, match, [&]() { |
| auto param = builder.create<sem::Parameter>( |
| nullptr, 0u, match.parameters[0].type, ast::StorageClass::kNone, |
| ast::Access::kUndefined, match.parameters[0].usage); |
| auto eval_stage = match.overload->const_eval_fn ? sem::EvaluationStage::kConstant |
| : sem::EvaluationStage::kRuntime; |
| return builder.create<sem::TypeConversion>(match.return_type, param, eval_stage); |
| }); |
| return CtorOrConv{target, match.overload->const_eval_fn}; |
| } |
| |
| IntrinsicPrototype Impl::MatchIntrinsic(const IntrinsicInfo& intrinsic, |
| const char* intrinsic_name, |
| utils::VectorRef<const sem::Type*> args, |
| TemplateState templates, |
| OnNoMatch on_no_match) const { |
| size_t num_matched = 0; |
| size_t match_idx = 0; |
| utils::Vector<Candidate, kNumFixedCandidates> candidates; |
| candidates.Reserve(intrinsic.num_overloads); |
| for (size_t overload_idx = 0; overload_idx < static_cast<size_t>(intrinsic.num_overloads); |
| overload_idx++) { |
| auto candidate = ScoreOverload(&intrinsic.overloads[overload_idx], args, templates); |
| if (candidate.score == 0) { |
| match_idx = overload_idx; |
| num_matched++; |
| } |
| candidates.Push(std::move(candidate)); |
| } |
| |
| // How many candidates matched? |
| if (num_matched == 0) { |
| // Sort the candidates with the most promising first |
| SortCandidates(candidates); |
| on_no_match(std::move(candidates)); |
| return {}; |
| } |
| |
| Candidate match; |
| |
| if (num_matched == 1) { |
| match = std::move(candidates[match_idx]); |
| } else { |
| match = ResolveCandidate(std::move(candidates), intrinsic_name, args, std::move(templates)); |
| if (!match.overload) { |
| // Ambiguous overload. ResolveCandidate() will have already raised an error diagnostic. |
| return {}; |
| } |
| } |
| |
| // Build the return type |
| const sem::Type* return_type = nullptr; |
| if (auto* indices = match.overload->return_matcher_indices) { |
| Any any; |
| return_type = Match(match.templates, match.overload, indices).Type(&any); |
| if (!return_type) { |
| TINT_ICE(Resolver, builder.Diagnostics()) << "MatchState.Match() returned null"; |
| return {}; |
| } |
| } else { |
| return_type = builder.create<sem::Void>(); |
| } |
| |
| return IntrinsicPrototype{match.overload, return_type, std::move(match.parameters)}; |
| } |
| |
| Impl::Candidate Impl::ScoreOverload(const OverloadInfo* overload, |
| utils::VectorRef<const sem::Type*> args, |
| TemplateState templates) const { |
| // Penalty weights for overload mismatching. |
| // This scoring is used to order the suggested overloads in diagnostic on overload mismatch, and |
| // has no impact for a correct program. |
| // The overloads with the lowest score will be displayed first (top-most). |
| constexpr int kMismatchedParamCountPenalty = 3; |
| constexpr int kMismatchedParamTypePenalty = 2; |
| constexpr int kMismatchedTemplateTypePenalty = 1; |
| constexpr int kMismatchedTemplateNumberPenalty = 1; |
| |
| size_t num_parameters = static_cast<size_t>(overload->num_parameters); |
| size_t num_arguments = static_cast<size_t>(args.Length()); |
| |
| size_t score = 0; |
| |
| if (num_parameters != num_arguments) { |
| score += kMismatchedParamCountPenalty * (std::max(num_parameters, num_arguments) - |
| std::min(num_parameters, num_arguments)); |
| } |
| |
| // Invoke the matchers for each parameter <-> argument pair. |
| // If any arguments cannot be matched, then `score` will be increased. |
| // If the overload has any template types or numbers then these will be set based on the |
| // argument types. Template types may be refined by constraining with later argument types. For |
| // example calling `F<T>(T, T)` with the argument types (abstract-int, i32) will first set T to |
| // abstract-int when matching the first argument, and then constrained down to i32 when matching |
| // the second argument. |
| // Note that inferred template types are not tested against their matchers at this point. |
| auto num_params = std::min(num_parameters, num_arguments); |
| for (size_t p = 0; p < num_params; p++) { |
| auto& parameter = overload->parameters[p]; |
| auto* indices = parameter.matcher_indices; |
| if (!Match(templates, overload, indices).Type(args[p]->UnwrapRef())) { |
| score += kMismatchedParamTypePenalty; |
| } |
| } |
| |
| if (score == 0) { |
| // Check all constrained template types matched their constraint matchers. |
| // If the template type *does not* match any of the types in the constraint matcher, then |
| // `score` is incremented. If the template type *does* match a type, then the template type |
| // is replaced with the first matching type. The order of types in the template matcher is |
| // important here, which can be controlled with the [[precedence(N)]] decorations on the |
| // types in intrinsics.def. |
| for (size_t ot = 0; ot < overload->num_template_types; ot++) { |
| auto* matcher_index = &overload->template_types[ot].matcher_index; |
| if (*matcher_index != kNoMatcher) { |
| if (auto* template_type = templates.Type(ot)) { |
| if (auto* ty = Match(templates, overload, matcher_index).Type(template_type)) { |
| // Template type matched one of the types in the template type's matcher. |
| // Replace the template type with this type. |
| templates.SetType(ot, ty); |
| continue; |
| } |
| } |
| score += kMismatchedTemplateTypePenalty; |
| } |
| } |
| } |
| |
| if (score == 0) { |
| // Check all constrained open numbers matched. |
| // Unlike template types, numbers are not constrained, so we're just checking that the |
| // inferred number matches the constraints on the overload. Increments `score` if the |
| // template numbers do not match their constraint matchers. |
| for (size_t on = 0; on < overload->num_template_numbers; on++) { |
| auto* matcher_index = &overload->template_numbers[on].matcher_index; |
| if (*matcher_index != kNoMatcher) { |
| auto template_num = templates.Num(on); |
| if (!template_num.IsValid() || |
| !Match(templates, overload, matcher_index).Num(template_num).IsValid()) { |
| score += kMismatchedTemplateNumberPenalty; |
| } |
| } |
| } |
| } |
| |
| // Now that all the template types have been finalized, we can construct the parameters. |
| utils::Vector<IntrinsicPrototype::Parameter, kNumFixedParams> parameters; |
| if (score == 0) { |
| parameters.Reserve(num_params); |
| for (size_t p = 0; p < num_params; p++) { |
| auto& parameter = overload->parameters[p]; |
| auto* indices = parameter.matcher_indices; |
| auto* ty = Match(templates, overload, indices).Type(args[p]->UnwrapRef()); |
| parameters.Emplace(ty, parameter.usage); |
| } |
| } |
| |
| return Candidate{overload, templates, parameters, score}; |
| } |
| |
| Impl::Candidate Impl::ResolveCandidate(Impl::Candidates&& candidates, |
| const char* intrinsic_name, |
| utils::VectorRef<const sem::Type*> args, |
| TemplateState templates) const { |
| utils::Vector<uint32_t, kNumFixedParams> best_ranks; |
| best_ranks.Resize(args.Length(), 0xffffffff); |
| size_t num_matched = 0; |
| Candidate* best = nullptr; |
| for (auto& candidate : candidates) { |
| if (candidate.score > 0) { |
| continue; // Candidate has already been ruled out. |
| } |
| bool some_won = false; // An argument ranked less than the 'best' overload's argument |
| bool some_lost = false; // An argument ranked more than the 'best' overload's argument |
| for (size_t i = 0; i < args.Length(); i++) { |
| auto rank = sem::Type::ConversionRank(args[i], candidate.parameters[i].type); |
| if (best_ranks[i] > rank) { |
| best_ranks[i] = rank; |
| some_won = true; |
| } else if (best_ranks[i] < rank) { |
| some_lost = true; |
| } |
| } |
| // If no arguments of this candidate ranked worse than the previous best candidate, then |
| // this candidate becomes the new best candidate. |
| // If no arguments of this candidate ranked better than the previous best candidate, then |
| // this candidate is removed from the list of matches. |
| // If neither of the above apply, then we have two candidates with no clear winner, which |
| // results in an ambiguous overload error. In this situation the loop ends with |
| // `num_matched > 1`. |
| if (some_won) { |
| // One or more arguments of this candidate ranked better than the previous best |
| // candidate's argument(s). |
| num_matched++; |
| if (!some_lost) { |
| // All arguments were at as-good or better than the previous best. |
| if (best) { |
| // Mark the previous best candidate as no longer being in the running, by |
| // setting its score to a non-zero value. We pick 1 as this is the closest to 0 |
| // (match) as we can get. |
| best->score = 1; |
| num_matched--; |
| } |
| // This candidate is the new best. |
| best = &candidate; |
| } |
| } else { |
| // No arguments ranked better than the current best. |
| // Change the score of this candidate to a non-zero value, so that it's not considered a |
| // match. |
| candidate.score = 1; |
| } |
| } |
| |
| if (num_matched > 1) { |
| // Re-sort the candidates with the most promising first |
| SortCandidates(candidates); |
| // Raise an error |
| ErrAmbiguousOverload(intrinsic_name, args, templates, candidates); |
| return {}; |
| } |
| |
| return std::move(*best); |
| } |
| |
| MatchState Impl::Match(TemplateState& templates, |
| const OverloadInfo* overload, |
| MatcherIndex const* matcher_indices) const { |
| return MatchState(builder, templates, matchers, overload, matcher_indices); |
| } |
| |
| void Impl::PrintOverload(std::ostream& ss, |
| const OverloadInfo* overload, |
| const char* intrinsic_name) const { |
| TemplateState templates; |
| |
| ss << intrinsic_name << "("; |
| for (size_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(templates, overload, indices).TypeName(); |
| } |
| ss << ")"; |
| if (overload->return_matcher_indices) { |
| ss << " -> "; |
| auto* indices = overload->return_matcher_indices; |
| ss << Match(templates, overload, indices).TypeName(); |
| } |
| |
| bool first = true; |
| auto separator = [&] { |
| ss << (first ? " where: " : ", "); |
| first = false; |
| }; |
| for (size_t i = 0; i < overload->num_template_types; i++) { |
| auto& template_type = overload->template_types[i]; |
| if (template_type.matcher_index != kNoMatcher) { |
| separator(); |
| ss << template_type.name; |
| auto* index = &template_type.matcher_index; |
| ss << " is " << Match(templates, overload, index).TypeName(); |
| } |
| } |
| for (size_t i = 0; i < overload->num_template_numbers; i++) { |
| auto& template_number = overload->template_numbers[i]; |
| if (template_number.matcher_index != kNoMatcher) { |
| separator(); |
| ss << template_number.name; |
| auto* index = &template_number.matcher_index; |
| ss << " is " << Match(templates, overload, index).NumName(); |
| } |
| } |
| } |
| |
| void Impl::PrintCandidates(std::ostream& ss, |
| utils::VectorRef<Candidate> candidates, |
| const char* intrinsic_name) const { |
| for (auto& candidate : candidates) { |
| ss << " "; |
| PrintOverload(ss, candidate.overload, intrinsic_name); |
| ss << std::endl; |
| } |
| } |
| |
| 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); |
| } |
| |
| void Impl::ErrAmbiguousOverload(const char* intrinsic_name, |
| utils::VectorRef<const sem::Type*> args, |
| TemplateState templates, |
| utils::VectorRef<Candidate> candidates) const { |
| std::stringstream ss; |
| ss << "ambiguous overload while attempting to match " << intrinsic_name; |
| for (size_t i = 0; i < std::numeric_limits<size_t>::max(); i++) { |
| if (auto* ty = templates.Type(i)) { |
| ss << ((i == 0) ? "<" : ", ") << ty->FriendlyName(builder.Symbols()); |
| } else { |
| if (i > 0) { |
| ss << ">"; |
| } |
| break; |
| } |
| } |
| ss << "("; |
| bool first = true; |
| for (auto* arg : args) { |
| if (!first) { |
| ss << ", "; |
| } |
| first = false; |
| ss << arg->FriendlyName(builder.Symbols()); |
| } |
| ss << "):\n"; |
| for (auto& candidate : candidates) { |
| if (candidate.score == 0) { |
| ss << " "; |
| PrintOverload(ss, candidate.overload, intrinsic_name); |
| ss << std::endl; |
| } |
| } |
| TINT_ICE(Resolver, builder.Diagnostics()) << ss.str(); |
| } |
| |
| } // namespace |
| |
| std::unique_ptr<IntrinsicTable> IntrinsicTable::Create(ProgramBuilder& builder) { |
| return std::make_unique<Impl>(builder); |
| } |
| |
| IntrinsicTable::~IntrinsicTable() = default; |
| |
| } // namespace tint::resolver |
| |
| /// TypeInfo for the Any type declared in the anonymous namespace above |
| TINT_INSTANTIATE_TYPEINFO(tint::resolver::Any); |