Trait OverloadSet

Help

pub trait OverloadSet: Clone {
    // Required methods
    fn is_empty(&self) -> bool;
    fn min_arguments(&self) -> usize;
    fn max_arguments(&self) -> usize;
    fn arg(&self, i: usize, ty: &TypeInner, types: &UniqueArena<Type>) -> Self;
    fn concrete_only(self, types: &UniqueArena<Type>) -> Self;
    fn most_preferred(&self) -> Rule;
    fn overload_list(&self, gctx: &GlobalCtx<'_>) -> Vec<Rule>;
    fn allowed_args(
        &self,
        i: usize,
        gctx: &GlobalCtx<'_>,
    ) -> Vec<TypeResolution>;
    fn for_debug(&self, types: &UniqueArena<Type>) -> impl Debug;
}

Expand description

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.

§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.

§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.

Required Methods§

Source

fn is_empty(&self) -> bool

Return true if self is the empty set of overloads.

Source

fn min_arguments(&self) -> usize

Return the smallest number of arguments in any type rule in the set.

§Panics

Panics if self is empty.

Source

fn max_arguments(&self) -> usize

Return the largest number of arguments in any type rule in the set.

§Panics

Panics if self is empty.

Source

fn arg(&self, i: usize, ty: &TypeInner, types: &UniqueArena<Type>) -> Self

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.

Source

fn concrete_only(self, types: &UniqueArena<Type>) -> Self

Limit self to overloads whose arguments are all concrete types.

Naga’s overload resolution is based on WGSL’s overload resolution algorithm, 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.

Source

fn most_preferred(&self) -> Rule

Return the most preferred candidate.

Rank the candidates in self as described in WGSL’s overload resolution algorithm, 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.