naga/proc/overloads/
mod.rs

1/*! Overload resolution for builtin functions.
2
3This module defines the [`OverloadSet`] trait, which provides methods the
4validator and typifier can use to check the types to builtin functions,
5determine their result types, and produce diagnostics that explain why a given
6application is not allowed and suggest fixes.
7
8You can call [`MathFunction::overloads`] to obtain an `impl OverloadSet`
9representing the given `MathFunction`'s overloads.
10
11[`MathFunction::overloads`]: crate::ir::MathFunction::overloads
12
13*/
14
15mod constructor_set;
16mod regular;
17mod scalar_set;
18
19mod any_overload_set;
20mod list;
21mod mathfunction;
22mod one_bits_iter;
23mod rule;
24mod utils;
25
26pub use rule::{Conclusion, MissingSpecialType, Rule};
27
28use crate::ir;
29use crate::proc::TypeResolution;
30
31use alloc::vec::Vec;
32use core::fmt;
33
34#[expect(rustdoc::private_intra_doc_links)]
35/// A trait for types representing of a set of Naga IR type rules.
36///
37/// Given an expression like `max(x, y)`, there are multiple type rules that
38/// could apply, depending on the types of `x` and `y`, like:
39///
40/// - `max(i32, i32) -> i32`
41/// - `max(vec4<f32>, vec4<f32>) -> vec4<f32>`
42///
43/// and so on. Borrowing WGSL's terminology, Naga calls the full set of type
44/// rules that might apply to a given expression its "overload candidates", or
45/// "overloads" for short.
46///
47/// This trait is meant to be implemented by types that represent a set of
48/// overload candidates. For example, [`MathFunction::overloads`] returns an
49/// `impl OverloadSet` describing the overloads for the given Naga IR math
50/// function. Naga's typifier, validator, and WGSL front end use this trait for
51/// their work.
52///
53/// [`MathFunction::overloads`]: ir::MathFunction::overloads
54///
55/// # Automatic conversions
56///
57/// In principle, overload sets are easy: you simply list all the overloads the
58/// function supports, and then when you're presented with a call to typecheck,
59/// you just see if the actual argument types presented in the source code match
60/// some overload from the list.
61///
62/// However, Naga supports languages like WGSL, which apply certain [automatic
63/// conversions] if necessary to make a call fit some overload's requirements.
64/// This means that the set of calls that are effectively allowed by a given set
65/// of overloads can be quite large, since any combination of automatic
66/// conversions might be applied.
67///
68/// For example, if `x` is a `u32`, and `100` is an abstract integer, then even
69/// though `max` has no overload like `max(u32, AbstractInt) -> ...`, the
70/// expression `max(x, 100)` is still allowed, because AbstractInt automatically
71/// converts to `u32`.
72///
73/// [automatic conversions]: https://gpuweb.github.io/gpuweb/wgsl/#feasible-automatic-conversion
74///
75/// # How to use `OverloadSet`
76///
77/// The general process of using an `OverloadSet` is as follows:
78///
79/// - Obtain an `OverloadSet` for a given operation (say, by calling
80///   [`MathFunction::overloads`]). This set is fixed by Naga IR's semantics.
81///
82/// - Call its [`arg`] method, supplying the type of the argument passed to the
83///   operation at a certain index. This returns a new `OverloadSet` containing
84///   only those overloads that could accept the given type for the given
85///   argument. This includes overloads that only match if automatic conversions
86///   are applied.
87///
88/// - If, at some point, the overload set becomes empty, then the set of
89///   arguments is not allowed for this operation, and the program is invalid.
90///   The `OverloadSet` trait provides an [`is_empty`] method.
91///
92/// - After all arguments have been supplied, if the overload set is still
93///   non-empty, you can call its [`most_preferred`] method to find out which
94///   overload has the least cost in terms of automatic conversions.
95///
96/// - If the call is rejected, you can use `OverloadSet` to help produce
97///   diagnostic messages that explain exactly what went wrong. `OverloadSet`
98///   implementations are meant to be cheap to [`Clone`], so it is fine to keep
99///   the original overload set value around, and re-run the selection process,
100///   attempting to supply the rejected argument at each step to see exactly
101///   which preceding argument ruled it out. The [`overload_list`] and
102///   [`allowed_args`] methods are helpful for this.
103///
104/// [`arg`]: OverloadSet::arg
105/// [`is_empty`]: OverloadSet::is_empty
106/// [`most_preferred`]: OverloadSet::most_preferred
107/// [`overload_list`]: OverloadSet::overload_list
108/// [`allowed_args`]: OverloadSet::allowed_args
109///
110/// # Concrete implementations
111///
112/// This module contains two private implementations of `OverloadSet`:
113///
114/// - The [`List`] type is a straightforward list of overloads. It is general,
115///   but verbose to use. The [`utils`] module exports functions that construct
116///   `List` overload sets for the functions that need this.
117///
118/// - The [`Regular`] type is a compact, efficient representation for the kinds
119///   of overload sets commonly seen for Naga IR mathematical functions.
120///   However, in return for its simplicity, it is not as flexible as [`List`].
121///   This module use the [`regular!`] macro as a legible notation for `Regular`
122///   sets.
123///
124/// [`List`]: list::List
125/// [`Regular`]: regular::Regular
126/// [`regular!`]: regular::regular
127pub trait OverloadSet: Clone {
128    /// Return true if `self` is the empty set of overloads.
129    fn is_empty(&self) -> bool;
130
131    /// Return the smallest number of arguments in any type rule in the set.
132    ///
133    /// # Panics
134    ///
135    /// Panics if `self` is empty.
136    fn min_arguments(&self) -> usize;
137
138    /// Return the largest number of arguments in any type rule in the set.
139    ///
140    /// # Panics
141    ///
142    /// Panics if `self` is empty.
143    fn max_arguments(&self) -> usize;
144
145    /// Find the overloads that could accept a given argument.
146    ///
147    /// Return a new overload set containing those members of `self` that could
148    /// accept a value of type `ty` for their `i`'th argument, once
149    /// feasible automatic conversions have been applied.
150    fn arg(&self, i: usize, ty: &ir::TypeInner, types: &crate::UniqueArena<ir::Type>) -> Self;
151
152    /// Limit `self` to overloads whose arguments are all concrete types.
153    ///
154    /// Naga's overload resolution is based on WGSL's [overload resolution
155    /// algorithm][ora], which includes the following step:
156    ///
157    /// > Eliminate any candidate where one of its subexpressions resolves to
158    /// > an abstract type after feasible automatic conversions, but another of
159    /// > the candidate’s subexpressions is not a const-expression.
160    /// >
161    /// > Note: As a consequence, if any subexpression in the phrase is not a
162    /// > const-expression, then all subexpressions in the phrase must have a
163    /// > concrete type.
164    ///
165    /// Essentially, if any one of the arguments is not a constant expression,
166    /// then the operation is going to be evaluated at runtime, so all its
167    /// arguments must be converted to a concrete type. If you determine that an
168    /// argument is non-constant, you can use this trait method to toss out any
169    /// overloads that would accept abstract types.
170    ///
171    /// In almost all cases, this operation has no effect. Only constant
172    /// expressions can have abstract types, so if any argument is not a
173    /// constant expression, it must have a concrete type. Although many
174    /// operations in Naga IR have overloads for both abstract types and
175    /// concrete types, few operations have overloads that accept a mix of
176    /// abstract and concrete types. Thus, a single concrete argument will
177    /// usually have eliminated all overloads that accept abstract types anyway.
178    /// (The exceptions are oddities like `Expression::Select`, where the
179    /// `condition` operand could be a runtime expression even as the `accept`
180    /// and `reject` operands have abstract types.)
181    ///
182    /// Note that it is *not* correct to just [concretize] all arguments once
183    /// you've noticed that some argument is non-constant. The type to which
184    /// each argument is converted depends on the overloads available, not just
185    /// the argument's own type.
186    ///
187    /// [ora]: https://gpuweb.github.io/gpuweb/wgsl/#overload-resolution-section
188    /// [concretize]: https://gpuweb.github.io/gpuweb/wgsl/#concretization
189    fn concrete_only(self, types: &crate::UniqueArena<ir::Type>) -> Self;
190
191    /// Return the most preferred candidate.
192    ///
193    /// Rank the candidates in `self` as described in WGSL's [overload
194    /// resolution algorithm][ora], and return a singleton set containing the
195    /// most preferred candidate.
196    ///
197    /// # Simplifications versus WGSL
198    ///
199    /// Naga's process for selecting the most preferred candidate is simpler
200    /// than WGSL's:
201    ///
202    /// - WGSL allows for the possibility of ambiguous calls, where multiple
203    ///   overload candidates exist, no one candidate is clearly better than all
204    ///   the others. For example, if a function has the two overloads `(i32,
205    ///   f32) -> bool` and `(f32, i32) -> bool`, and the arguments are both
206    ///   AbstractInt, neither overload is preferred over the other. Ambiguous
207    ///   calls are errors.
208    ///
209    ///   However, Naga IR includes no operations whose overload sets allow such
210    ///   situations to arise, so there is always a most preferred candidate.
211    ///   Thus, this method infallibly returns a `Rule`, and has no way to
212    ///   indicate ambiguity.
213    ///
214    /// - WGSL says that the most preferred candidate depends on the conversion
215    ///   rank for each argument, as determined by the types of the arguments
216    ///   being passed.
217    ///
218    ///   However, the overloads of every operation in Naga IR can be ranked
219    ///   even without knowing the argument types. So this method does not
220    ///   require the argument types as a parameter.
221    ///
222    /// # Panics
223    ///
224    /// Panics if `self` is empty, or if no argument types have been supplied.
225    ///
226    /// [ora]: https://gpuweb.github.io/gpuweb/wgsl/#overload-resolution-section
227    fn most_preferred(&self) -> Rule;
228
229    /// Return a type rule for each of the overloads in `self`.
230    fn overload_list(&self, gctx: &crate::proc::GlobalCtx<'_>) -> Vec<Rule>;
231
232    /// Return a list of the types allowed for argument `i`.
233    fn allowed_args(&self, i: usize, gctx: &crate::proc::GlobalCtx<'_>) -> Vec<TypeResolution>;
234
235    /// Return an object that can be formatted with [`core::fmt::Debug`].
236    fn for_debug(&self, types: &crate::UniqueArena<ir::Type>) -> impl fmt::Debug;
237}