Source code
Revision control
Copy as Markdown
Other Tools
/*! Overload resolution for builtin functions.
This module defines the [`OverloadSet`] trait, which provides methods the
validator and typifier can use to check the types to builtin functions,
determine their result types, and produce diagnostics that explain why a given
application is not allowed and suggest fixes.
You can call [`MathFunction::overloads`] to obtain an `impl OverloadSet`
representing the given `MathFunction`'s overloads.
[`MathFunction::overloads`]: crate::ir::MathFunction::overloads
*/
mod constructor_set;
mod regular;
mod scalar_set;
mod any_overload_set;
mod list;
mod mathfunction;
mod one_bits_iter;
mod rule;
mod utils;
pub use rule::{Conclusion, MissingSpecialType, Rule};
use crate::ir;
use crate::proc::TypeResolution;
use alloc::vec::Vec;
use core::fmt;
#[expect(rustdoc::private_intra_doc_links)]
/// A trait for types representing of a set of Naga IR type rules.
///
/// Given an expression like `max(x, y)`, there are multiple type rules that
/// could apply, depending on the types of `x` and `y`, like:
///
/// - `max(i32, i32) -> i32`
/// - `max(vec4<f32>, vec4<f32>) -> vec4<f32>`
///
/// and so on. Borrowing WGSL's terminology, Naga calls the full set of type
/// rules that might apply to a given expression its "overload candidates", or
/// "overloads" for short.
///
/// This trait is meant to be implemented by types that represent a set of
/// overload candidates. For example, [`MathFunction::overloads`] returns an
/// `impl OverloadSet` describing the overloads for the given Naga IR math
/// function. Naga's typifier, validator, and WGSL front end use this trait for
/// their work.
///
/// [`MathFunction::overloads`]: ir::MathFunction::overloads
///
/// # Automatic conversions
///
/// In principle, overload sets are easy: you simply list all the overloads the
/// function supports, and then when you're presented with a call to typecheck,
/// you just see if the actual argument types presented in the source code match
/// some overload from the list.
///
/// However, Naga supports languages like WGSL, which apply certain [automatic
/// conversions] if necessary to make a call fit some overload's requirements.
/// This means that the set of calls that are effectively allowed by a given set
/// of overloads can be quite large, since any combination of automatic
/// conversions might be applied.
///
/// For example, if `x` is a `u32`, and `100` is an abstract integer, then even
/// though `max` has no overload like `max(u32, AbstractInt) -> ...`, the
/// expression `max(x, 100)` is still allowed, because AbstractInt automatically
/// converts to `u32`.
///
///
/// # How to use `OverloadSet`
///
/// The general process of using an `OverloadSet` is as follows:
///
/// - Obtain an `OverloadSet` for a given operation (say, by calling
/// [`MathFunction::overloads`]). This set is fixed by Naga IR's semantics.
///
/// - Call its [`arg`] method, supplying the type of the argument passed to the
/// operation at a certain index. This returns a new `OverloadSet` containing
/// only those overloads that could accept the given type for the given
/// argument. This includes overloads that only match if automatic conversions
/// are applied.
///
/// - If, at some point, the overload set becomes empty, then the set of
/// arguments is not allowed for this operation, and the program is invalid.
/// The `OverloadSet` trait provides an [`is_empty`] method.
///
/// - After all arguments have been supplied, if the overload set is still
/// non-empty, you can call its [`most_preferred`] method to find out which
/// overload has the least cost in terms of automatic conversions.
///
/// - If the call is rejected, you can use `OverloadSet` to help produce
/// diagnostic messages that explain exactly what went wrong. `OverloadSet`
/// implementations are meant to be cheap to [`Clone`], so it is fine to keep
/// the original overload set value around, and re-run the selection process,
/// attempting to supply the rejected argument at each step to see exactly
/// which preceding argument ruled it out. The [`overload_list`] and
/// [`allowed_args`] methods are helpful for this.
///
/// [`arg`]: OverloadSet::arg
/// [`is_empty`]: OverloadSet::is_empty
/// [`most_preferred`]: OverloadSet::most_preferred
/// [`overload_list`]: OverloadSet::overload_list
/// [`allowed_args`]: OverloadSet::allowed_args
///
/// # Concrete implementations
///
/// This module contains two private implementations of `OverloadSet`:
///
/// - The [`List`] type is a straightforward list of overloads. It is general,
/// but verbose to use. The [`utils`] module exports functions that construct
/// `List` overload sets for the functions that need this.
///
/// - The [`Regular`] type is a compact, efficient representation for the kinds
/// of overload sets commonly seen for Naga IR mathematical functions.
/// However, in return for its simplicity, it is not as flexible as [`List`].
/// This module use the [`regular!`] macro as a legible notation for `Regular`
/// sets.
///
/// [`List`]: list::List
/// [`Regular`]: regular::Regular
/// [`regular!`]: regular::regular
pub trait OverloadSet: Clone {
/// Return true if `self` is the empty set of overloads.
fn is_empty(&self) -> bool;
/// Return the smallest number of arguments in any type rule in the set.
///
/// # Panics
///
/// Panics if `self` is empty.
fn min_arguments(&self) -> usize;
/// Return the largest number of arguments in any type rule in the set.
///
/// # Panics
///
/// Panics if `self` is empty.
fn max_arguments(&self) -> usize;
/// Find the overloads that could accept a given argument.
///
/// Return a new overload set containing those members of `self` that could
/// accept a value of type `ty` for their `i`'th argument, once
/// feasible automatic conversions have been applied.
fn arg(&self, i: usize, ty: &ir::TypeInner, types: &crate::UniqueArena<ir::Type>) -> Self;
/// Limit `self` to overloads whose arguments are all concrete types.
///
/// Naga's overload resolution is based on WGSL's [overload resolution
/// algorithm][ora], which includes the following step:
///
/// > Eliminate any candidate where one of its subexpressions resolves to
/// > an abstract type after feasible automatic conversions, but another of
/// > the candidate’s subexpressions is not a const-expression.
/// >
/// > Note: As a consequence, if any subexpression in the phrase is not a
/// > const-expression, then all subexpressions in the phrase must have a
/// > concrete type.
///
/// Essentially, if any one of the arguments is not a constant expression,
/// then the operation is going to be evaluated at runtime, so all its
/// arguments must be converted to a concrete type. If you determine that an
/// argument is non-constant, you can use this trait method to toss out any
/// overloads that would accept abstract types.
///
/// In almost all cases, this operation has no effect. Only constant
/// expressions can have abstract types, so if any argument is not a
/// constant expression, it must have a concrete type. Although many
/// operations in Naga IR have overloads for both abstract types and
/// concrete types, few operations have overloads that accept a mix of
/// abstract and concrete types. Thus, a single concrete argument will
/// usually have eliminated all overloads that accept abstract types anyway.
/// (The exceptions are oddities like `Expression::Select`, where the
/// `condition` operand could be a runtime expression even as the `accept`
/// and `reject` operands have abstract types.)
///
/// Note that it is *not* correct to just [concretize] all arguments once
/// you've noticed that some argument is non-constant. The type to which
/// each argument is converted depends on the overloads available, not just
/// the argument's own type.
///
fn concrete_only(self, types: &crate::UniqueArena<ir::Type>) -> Self;
/// Return the most preferred candidate.
///
/// Rank the candidates in `self` as described in WGSL's [overload
/// resolution algorithm][ora], and return a singleton set containing the
/// most preferred candidate.
///
/// # Simplifications versus WGSL
///
/// Naga's process for selecting the most preferred candidate is simpler
/// than WGSL's:
///
/// - WGSL allows for the possibility of ambiguous calls, where multiple
/// overload candidates exist, no one candidate is clearly better than all
/// the others. For example, if a function has the two overloads `(i32,
/// f32) -> bool` and `(f32, i32) -> bool`, and the arguments are both
/// AbstractInt, neither overload is preferred over the other. Ambiguous
/// calls are errors.
///
/// However, Naga IR includes no operations whose overload sets allow such
/// situations to arise, so there is always a most preferred candidate.
/// Thus, this method infallibly returns a `Rule`, and has no way to
/// indicate ambiguity.
///
/// - WGSL says that the most preferred candidate depends on the conversion
/// rank for each argument, as determined by the types of the arguments
/// being passed.
///
/// However, the overloads of every operation in Naga IR can be ranked
/// even without knowing the argument types. So this method does not
/// require the argument types as a parameter.
///
/// # Panics
///
/// Panics if `self` is empty, or if no argument types have been supplied.
///
fn most_preferred(&self) -> Rule;
/// Return a type rule for each of the overloads in `self`.
fn overload_list(&self, gctx: &crate::proc::GlobalCtx<'_>) -> Vec<Rule>;
/// Return a list of the types allowed for argument `i`.
fn allowed_args(&self, i: usize, gctx: &crate::proc::GlobalCtx<'_>) -> Vec<TypeResolution>;
/// Return an object that can be formatted with [`core::fmt::Debug`].
fn for_debug(&self, types: &crate::UniqueArena<ir::Type>) -> impl fmt::Debug;
}