blob: 30fae3698ffc9c696607f64e3c6181cabbea1c47 [file] [log] [blame]
// Copyright 2023 The Dawn & Tint Authors
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// 1. Redistributions of source code must retain the above copyright notice, this
// list of conditions and the following disclaimer.
//
// 2. Redistributions in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimer in the documentation
// and/or other materials provided with the distribution.
//
// 3. Neither the name of the copyright holder nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#ifndef SRC_TINT_LANG_CORE_INTRINSIC_TABLE_DATA_H_
#define SRC_TINT_LANG_CORE_INTRINSIC_TABLE_DATA_H_
#include <stdint.h>
#include <limits>
#include <string>
#include "src/tint/lang/core/constant/eval.h"
#include "src/tint/lang/core/evaluation_stage.h"
#include "src/tint/lang/core/parameter_usage.h"
#include "src/tint/utils/containers/enum_set.h"
#include "src/tint/utils/containers/slice.h"
#include "src/tint/utils/text/styled_text.h"
#include "src/tint/utils/text/text_style.h"
/// Forward declaration
namespace tint::core::intrinsic {
struct TableData;
} // namespace tint::core::intrinsic
namespace tint::core::intrinsic {
/// An enumerator of index namespaces.
enum class TableIndexNamespace : uint8_t {
kTemplate,
kMatcher,
kMatcherIndices,
kTypeMatcher,
kNumberMatcher,
kParameter,
kOverload,
kConstEvalFunction,
};
/// A wrapper around an integer type, used to index intrinsic table data
/// @tparam T the index data type
/// @tparam N the index namespace
template <TableIndexNamespace N, typename T>
struct TableIndex {
static_assert(std::is_integral_v<T> && std::is_unsigned_v<T>,
"T must be an unsigned integer type");
/// The value used to represent an invalid index
static constexpr T kInvalid = std::numeric_limits<T>::max();
/// Constructor for invalid index
constexpr TableIndex() : value(kInvalid) {}
/// Constructor
/// @param index the index value
constexpr explicit TableIndex(T index) : value(index) {}
/// @returns true if this index is not invalid
bool IsValid() const { return value != kInvalid; }
/// Equality operator
/// @param other the index to compare against
/// @returns true if this index is equal to @p other
bool operator==(const TableIndex& other) { return value == other.value; }
/// Inequality operator
/// @param other the index to compare against
/// @returns true if this index is equal to @p other
bool operator!=(const TableIndex& other) { return value != other.value; }
/// @param offset the offset to apply to this index
/// @returns a new index offset by @p offset
template <typename U>
auto operator+(U offset) const {
static_assert(std::is_integral_v<U> && std::is_unsigned_v<U>,
"T must be an unsigned integer type");
using C = std::conditional_t<(sizeof(U) > sizeof(T)), U, T>;
C new_value = static_cast<C>(value) + static_cast<C>(offset);
return TableIndex<N, decltype(new_value)>(new_value);
}
/// @param arr a C-style array
/// @returns true if the integer type `T` has enough bits to index all the
/// elements in the array @p arr.
template <typename U, size_t COUNT>
static constexpr bool CanIndex(U (&arr)[COUNT]) {
(void)arr; // The array isn't actually used
/// kInvalid is the largest value representable by `T`. It is not a valid index.
return COUNT < kInvalid;
}
/// The index value
const T value = kInvalid;
};
/// Index type used to index TableData::template_types
using TemplateIndex = TableIndex<TableIndexNamespace::kTemplate, uint8_t>;
/// Index type used to index TableData::type_matchers or TableData::number_matchers
using MatcherIndex = TableIndex<TableIndexNamespace::kMatcher, uint8_t>;
/// Index type used to index TableData::matcher_indices
using MatcherIndicesIndex = TableIndex<TableIndexNamespace::kMatcherIndices, uint16_t>;
/// Index type used to index TableData::type_matchers
using TypeMatcherIndex = TableIndex<TableIndexNamespace::kTypeMatcher, uint8_t>;
/// Index type used to index TableData::number_matchers
using NumberMatcherIndex = TableIndex<TableIndexNamespace::kNumberMatcher, uint8_t>;
/// Index type used to index TableData::parameters
using ParameterIndex = TableIndex<TableIndexNamespace::kParameter, uint16_t>;
/// Index type used to index TableData::overloads
using OverloadIndex = TableIndex<TableIndexNamespace::kOverload, uint16_t>;
/// Index type used to index TableData::const_eval_functions
using ConstEvalFunctionIndex = TableIndex<TableIndexNamespace::kConstEvalFunction, uint8_t>;
/// Unique flag bits for overloads
enum class OverloadFlag : uint8_t {
kIsBuiltin, // The overload is a builtin ('fn')
kIsOperator, // The overload is an operator ('op')
kIsConstructor, // The overload is a value constructor ('ctor')
kIsConverter, // The overload is a value 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
kMustUse, // The overload cannot be called as a statement
kIsDeprecated, // The overload is deprecated
};
/// An enum set of OverloadFlag, used by OperatorInfo
using OverloadFlags = tint::EnumSet<OverloadFlag>;
/// ParameterInfo describes a parameter
struct ParameterInfo {
/// The parameter usage (parameter name in definition file)
const ParameterUsage usage;
/// Index of the matcher indices that are used to match the parameter types.
/// These indices are consumed by the matchers themselves.
const MatcherIndicesIndex matcher_indices;
};
/// TemplateInfo describes an template
struct TemplateInfo {
/// An enumerator of template kind
enum class Kind : uint8_t { kType, kNumber };
/// Name of the template type (e.g. 'T')
const char* name;
/// Index of the type matcher indices that are used to match the template types.
/// These indices are consumed by the matchers themselves.
const MatcherIndicesIndex matcher_indices;
/// The template kind
const Kind kind;
};
/// OverloadInfo describes a single function overload
struct OverloadInfo {
/// The flags for the overload
const OverloadFlags flags;
/// Total number of parameters for the overload
const uint8_t num_parameters;
/// Total number of explicit templates for the overload
const uint8_t num_explicit_templates;
/// Total number of implicit and explicit templates for the overload
const uint8_t num_templates;
/// Index of the first template in TableData::templates
/// This is a list of explicit template types followed by the implicit template types.
const TemplateIndex templates;
/// Index of the first parameter in TableData::parameters
const ParameterIndex parameters;
/// Index of a list of type matcher indices that are used to build the return type.
const MatcherIndicesIndex return_matcher_indices;
/// The function used to evaluate the overload at shader-creation time.
const ConstEvalFunctionIndex const_eval_fn;
};
/// IntrinsicInfo describes a builtin function or operator overload
struct IntrinsicInfo {
/// Number of overloads of the intrinsic
const uint8_t num_overloads;
/// Index of the first overload for the function
const OverloadIndex overloads;
};
/// A IntrinsicInfo with no overloads
static constexpr IntrinsicInfo kNoOverloads{0, OverloadIndex(OverloadIndex::kInvalid)};
/// 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
class Number {
enum State : uint8_t {
kInvalid,
kValid,
kAny,
};
constexpr explicit Number(State state) : state_(state) {}
public:
/// A special number representing any number
static const Number any;
/// An invalid number
static const Number invalid;
/// Constructed as a valid number with the value v
/// @param v the value for the number
explicit constexpr 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
/// @param n the new value for the number
/// @returns this so calls can be chained
inline Number& operator=(uint32_t n) {
value_ = n;
state_ = kValid;
return *this;
}
private:
uint32_t value_ = 0;
State state_ = kInvalid;
};
/// A special type that matches all TypeMatchers
class Any final : public Castable<Any, core::type::Type> {
public:
Any();
~Any() override;
/// @copydoc core::type::UniqueNode::Equals
bool Equals(const core::type::UniqueNode& other) const override;
/// @copydoc core::type::Type::FriendlyName
std::string FriendlyName() const override;
/// @copydoc core::type::Type::Clone
core::type::Type* Clone(core::type::CloneContext& ctx) const override;
};
/// TemplateState holds the state of the template numbers and types.
/// Used by the MatchState.
class TemplateState {
public:
/// If the template type with index @p idx is undefined, then it is defined with the @p ty
/// and Type() returns @p ty. If the template type is defined, and @p 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 @p ty, then the template type is replaced with
/// @p ty, and @p ty is returned. If none of the above applies, then @p ty is a type
/// mismatch for the template type, and nullptr is returned.
/// @param idx the index of the template type
/// @param ty the type
/// @returns true on match or newly defined
const core::type::Type* Type(size_t idx, const core::type::Type* ty) {
if (idx >= types_.Length()) {
types_.Resize(idx + 1);
}
auto& t = types_[idx];
if (t == nullptr) {
t = ty;
return ty;
}
ty = core::type::Type::Common(Vector{t, ty});
if (ty) {
t = ty;
}
return ty;
}
/// If the number with index @p 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 @p ty.
/// @param idx the index of the template number
/// @param number the number
/// @returns true on match or newly defined
bool Num(size_t idx, Number number) {
if (idx >= numbers_.Length()) {
numbers_.Resize(idx + 1, Number::any);
}
auto& n = numbers_[idx];
if (n.IsAny()) {
n = number.Value();
return true;
}
return n.Value() == number.Value();
}
/// @param idx the index of the template type
/// @returns the template type with index @p idx, or nullptr if the type was not
/// defined.
const core::type::Type* Type(size_t idx) const {
if (idx >= types_.Length()) {
return nullptr;
}
return types_[idx];
}
/// SetType replaces the template type with index @p idx with type @p ty.
/// @param idx the index of the template type
/// @param ty the new type for the template
void SetType(size_t idx, const core::type::Type* ty) {
if (idx >= types_.Length()) {
types_.Resize(idx + 1);
}
types_[idx] = ty;
}
/// @returns the number type with index @p idx.
/// @param idx the index of the template number
Number Num(size_t idx) const {
if (idx >= numbers_.Length()) {
return Number::invalid;
}
return numbers_[idx];
}
/// SetNum replaces the template number with index @p idx with number @p num.
/// @param idx the index of the template number
/// @param num the new number for the template
void SetNum(size_t idx, Number num) {
if (idx >= numbers_.Length()) {
numbers_.Resize(idx + 1, Number::any);
}
numbers_[idx] = num;
}
/// @return the total number of type and number templates
size_t Count() const { return types_.Length() + numbers_.Length(); }
private:
Vector<const core::type::Type*, 4> types_;
Vector<Number, 2> numbers_;
};
/// The current overload match state
/// MatchState holds the state used to match an overload.
class MatchState {
public:
/// Constructor
/// @param ty_mgr the type manager
/// @param syms the symbol table
/// @param t the template state
/// @param d the table data
/// @param o the current overload
/// @param matcher_indices the remaining matcher indices
/// @param s the required evaluation stage of the overload
MatchState(core::type::Manager& ty_mgr,
SymbolTable& syms,
TemplateState& t,
const TableData& d,
const OverloadInfo& o,
const MatcherIndex* matcher_indices,
EvaluationStage s)
: types(ty_mgr),
symbols(syms),
templates(t),
data(d),
overload(o),
earliest_eval_stage(s),
matcher_indices_(matcher_indices) {}
/// The type manager
core::type::Manager& types;
/// The symbol manager
SymbolTable& symbols;
/// The template types and numbers
TemplateState& templates;
/// The table data
const TableData& data;
/// The current overload being evaluated
const OverloadInfo& overload;
/// The earliest evaluation stage of the builtin call
EvaluationStage earliest_eval_stage;
/// Type uses the next TypeMatcher from the matcher indices to match the type @p ty.
/// @param ty the type to try matching
/// @returns the canonical expected type if the type matches, otherwise nullptr.
/// @note: The matcher indices are progressed on calling.
inline const core::type::Type* Type(const core::type::Type* ty);
/// Num uses the next NumMatcher from the matcher indices to match @p number.
/// @param number the number to try matching
/// @returns the canonical expected number if the number matches, otherwise an invalid
/// number.
/// @note: The matcher indices are progressed on calling.
inline Number Num(Number number);
/// Prints the type matcher representation to @p out
/// @note: The matcher indices are progressed on calling.
inline void PrintType(StyledText& out);
/// Prints the number matcher representation to @p out
/// @note: The matcher indices are progressed on calling.
inline void PrintNum(StyledText& out);
private:
const MatcherIndex* matcher_indices_ = nullptr;
};
/// A TypeMatcher is the interface used to match an type used as part of an
/// overload's parameter or return type.
struct TypeMatcher {
/// 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.
/// The parameter `type` is the type to match
/// Returns the canonicalized type on match, otherwise nullptr
using MatchFn = const core::type::Type*(MatchState& state, const core::type::Type* type);
/// @see #MatchFn
MatchFn* const match;
/// Prints the representation of the matcher.
/// Used for printing error messages when no overload is found.
using PrintFn = void(MatchState* state, StyledText& out);
/// @see #PrintFn
PrintFn* const print;
};
/// A NumberMatcher is the interface used to match a number or enumerator used
/// as part of an overload's parameter or return type.
struct NumberMatcher {
/// Checks whether the given number matches the matcher rules.
/// Match may define template numbers in state.
/// The parameter `number` is the number to match
/// Returns true if the argument type is as expected.
using MatchFn = Number(MatchState& state, Number number);
/// @see #MatchFn
MatchFn* const match;
/// Prints the representation of the matcher.
/// Used for printing error messages when no overload is found.
using PrintFn = void(MatchState* state, StyledText& out);
/// @see #PrintFn
PrintFn* const print;
};
/// TableData holds the immutable data that holds the intrinsic data for a language.
struct TableData {
/// @param idx the index of the TemplateInfo in the table data
/// @returns the TemplateInfo with the given index
template <typename T>
const TemplateInfo& operator[](TableIndex<TableIndexNamespace::kTemplate, T> idx) const {
return templates[idx.value];
}
/// @param idx the index of the MatcherIndices in the table data
/// @returns the MatcherIndices with the given index
template <typename T>
const MatcherIndex* operator[](TableIndex<TableIndexNamespace::kMatcherIndices, T> idx) const {
if (idx.IsValid()) {
return &matcher_indices[idx.value];
}
return nullptr;
}
/// @param idx the index of the TypeMatcher in the table data
/// @returns the TypeMatcher with the given index
template <typename T>
const TypeMatcher& operator[](TableIndex<TableIndexNamespace::kTypeMatcher, T> idx) const {
return type_matchers[idx.value];
}
/// @param idx the index of the NumberMatcher in the table data
/// @returns the NumberMatcher with the given index
template <typename T>
const NumberMatcher& operator[](TableIndex<TableIndexNamespace::kNumberMatcher, T> idx) const {
return number_matchers[idx.value];
}
/// @param idx the index of the ParameterInfo in the table data
/// @returns the ParameterInfo with the given index
template <typename T>
const ParameterInfo& operator[](TableIndex<TableIndexNamespace::kParameter, T> idx) const {
return parameters[idx.value];
}
/// @param idx the index of the OverloadInfo in the table data
/// @returns the OverloadInfo with the given index
template <typename T>
const OverloadInfo& operator[](TableIndex<TableIndexNamespace::kOverload, T> idx) const {
return overloads[idx.value];
}
/// @param idx the index of the constant::Eval::Function in the table data
/// @returns the constant::Eval::Function with the given index
template <typename T>
constant::Eval::Function operator[](
TableIndex<TableIndexNamespace::kConstEvalFunction, T> idx) const {
return idx.IsValid() ? const_eval_functions[idx.value] : nullptr;
}
/// The list of templates used by the intrinsic overloads
const Slice<const TemplateInfo> templates;
/// The list of type matcher indices
const Slice<const MatcherIndex> matcher_indices;
/// The list of type matchers used by the intrinsic overloads
const Slice<const TypeMatcher> type_matchers;
/// The list of number matchers used by the intrinsic overloads
const Slice<const NumberMatcher> number_matchers;
/// The list of parameters used by the intrinsic overloads
const Slice<const ParameterInfo> parameters;
/// The list of overloads used by the intrinsics
const Slice<const OverloadInfo> overloads;
/// The list of constant evaluation functions used by the intrinsics
const Slice<const constant::Eval::Function> const_eval_functions;
/// The type constructor and convertor intrinsics
const Slice<const IntrinsicInfo> ctor_conv;
/// The builtin function intrinsic
const Slice<const IntrinsicInfo> builtins;
/// The IntrinsicInfo for the binary operator 'plus'
const IntrinsicInfo& binary_plus;
/// The IntrinsicInfo for the binary operator 'minus'
const IntrinsicInfo& binary_minus;
/// The IntrinsicInfo for the binary operator 'star'
const IntrinsicInfo& binary_star;
/// The IntrinsicInfo for the binary operator 'divide'
const IntrinsicInfo& binary_divide;
/// The IntrinsicInfo for the binary operator 'modulo'
const IntrinsicInfo& binary_modulo;
/// The IntrinsicInfo for the binary operator 'xor'
const IntrinsicInfo& binary_xor;
/// The IntrinsicInfo for the binary operator 'and'
const IntrinsicInfo& binary_and;
/// The IntrinsicInfo for the binary operator 'or'
const IntrinsicInfo& binary_or;
/// The IntrinsicInfo for the binary operator 'logical_and'
const IntrinsicInfo& binary_logical_and;
/// The IntrinsicInfo for the binary operator 'logical_or'
const IntrinsicInfo& binary_logical_or;
/// The IntrinsicInfo for the binary operator 'equal'
const IntrinsicInfo& binary_equal;
/// The IntrinsicInfo for the binary operator 'not_equal'
const IntrinsicInfo& binary_not_equal;
/// The IntrinsicInfo for the binary operator 'less_than'
const IntrinsicInfo& binary_less_than;
/// The IntrinsicInfo for the binary operator 'greater_than'
const IntrinsicInfo& binary_greater_than;
/// The IntrinsicInfo for the binary operator 'less_than_equal'
const IntrinsicInfo& binary_less_than_equal;
/// The IntrinsicInfo for the binary operator 'greater_than_equal'
const IntrinsicInfo& binary_greater_than_equal;
/// The IntrinsicInfo for the binary operator 'shift_left'
const IntrinsicInfo& binary_shift_left;
/// The IntrinsicInfo for the binary operator 'shift_right'
const IntrinsicInfo& binary_shift_right;
/// The IntrinsicInfo for the unary operator 'not'
const IntrinsicInfo& unary_not;
/// The IntrinsicInfo for the unary operator 'complement'
const IntrinsicInfo& unary_complement;
/// The IntrinsicInfo for the unary operator 'minus'
const IntrinsicInfo& unary_minus;
/// The IntrinsicInfo for the unary operator 'star'
const IntrinsicInfo& unary_star;
/// The IntrinsicInfo for the unary operator 'and'
const IntrinsicInfo& unary_and;
};
const core::type::Type* MatchState::Type(const core::type::Type* ty) {
TypeMatcherIndex matcher_index{(*matcher_indices_++).value};
auto& matcher = data[matcher_index];
return matcher.match(*this, ty);
}
Number MatchState::Num(Number number) {
NumberMatcherIndex matcher_index{(*matcher_indices_++).value};
auto& matcher = data[matcher_index];
return matcher.match(*this, number);
}
void MatchState::PrintType(StyledText& out) {
TypeMatcherIndex matcher_index{(*matcher_indices_++).value};
auto& matcher = data[matcher_index];
matcher.print(this, out);
}
void MatchState::PrintNum(StyledText& out) {
NumberMatcherIndex matcher_index{(*matcher_indices_++).value};
auto& matcher = data[matcher_index];
matcher.print(this, out);
}
/// 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
template <size_t INDEX>
struct TemplateTypeMatcher {
/// The TypeMatcher for the template type with the index `INDEX`
static constexpr TypeMatcher matcher{
/* match */
[](MatchState& state, const core::type::Type* type) -> const core::type::Type* {
if (type->Is<Any>()) {
return state.templates.Type(INDEX);
}
if (auto* templates = state.templates.Type(INDEX, type)) {
return templates;
}
return nullptr;
},
/* print */
[](MatchState* state, StyledText& out) {
out << style::Type(state->data[state->overload.templates + INDEX].name);
},
};
};
/// 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)
template <size_t INDEX>
struct TemplateNumberMatcher {
/// The NumberMatcher for the template number with the index `INDEX`
static constexpr NumberMatcher matcher{
/* match */
[](MatchState& state, Number number) -> Number {
if (number.IsAny()) {
return state.templates.Num(INDEX);
}
return state.templates.Num(INDEX, number) ? number : Number::invalid;
},
/* print */
[](MatchState* state, StyledText& out) {
out << style::Variable(state->data[state->overload.templates + INDEX].name);
},
};
};
} // namespace tint::core::intrinsic
#endif // SRC_TINT_LANG_CORE_INTRINSIC_TABLE_DATA_H_